Resolver uma equação linear

votos
35

Preciso resolver programaticamente um sistema de equações lineares em C, Objective C, ou (se necessário) C ++.

Aqui está um exemplo das equações:

-44.3940 = a * 50.0 + b * 37.0 + tx
-45.3049 = a * 43.0 + b * 39.0 + tx
-44.9594 = a * 52.0 + b * 41.0 + tx

A partir disso, eu gostaria de obter a melhor aproximação para a, b, e tx.

Publicado 03/08/2008 em 19:14
fonte usuário
Em outras línguas...                            


10 respostas

votos
17

Regra de Cramer e Gaussian Eliminação são dois algoritmos bom, de uso geral (ver também simultâneas equações lineares ). Se você está olhando para o código, consulte a GiNaC , Maxima , e SymbolicC ++ (dependendo de seus requisitos de licenciamento, é claro).

EDIT: Eu sei que você está trabalhando em terra C, mas também tenho que colocar em uma boa palavra para SymPy (um sistema de álgebra computacional em Python). Você pode aprender muito com seus algoritmos (se você pode ler um pouco de python). Além disso, é sob a nova licença BSD, enquanto a maioria dos pacotes de matemática livres são GPL.

Respondeu 03/08/2008 em 19:37
fonte usuário

votos
15

Você pode resolver isso com um programa exatamente da mesma maneira que você resolvê-lo com a mão (com a multiplicação e subtração, em seguida, alimentando os resultados de volta para as equações). Esta é a matemática-de nível secundário bastante padrão.

-44.3940 = 50a + 37b + c (A)
-45.3049 = 43a + 39b + c (B)
-44.9594 = 52a + 41b + c (C)

(A-B): 0.9109 =  7a -  2b (D)
(B-C): 0.3455 = -9a -  2b (E)

(D-E): 1.2564 = 16a (F)

(F/16):  a = 0.078525 (G)

Feed G into D:
       0.9109 = 7a - 2b
    => 0.9109 = 0.549675 - 2b (substitute a)
    => 0.361225 = -2b (subtract 0.549675 from both sides)
    => -0.1806125 = b (divide both sides by -2) (H)

Feed H/G into A:
       -44.3940 = 50a + 37b + c
    => -44.3940 = 3.92625 - 6.6826625 + c (substitute a/b)
    => -41.6375875 = c (subtract 3.92625 - 6.6826625 from both sides)

Então você acaba com:

a =   0.0785250
b =  -0.1806125
c = -41.6375875

Se você conectar esses valores de volta para A, B e C, você verá que eles estão corretos.

O truque é a utilização de uma matriz 4x3 simples que por sua vez reduz a uma matriz de 3x2, 2x1, em seguida, um que é "a = n", sendo n um número real. Uma vez que você tem isso, você alimentá-lo para a próxima matriz-se para obter um outro valor, então esses dois valores na matriz seguinte até que você já resolveu todas as variáveis.

Desde que você tenha N equações distintas, você sempre pode resolver para variáveis ​​N. Eu digo distinta, porque estes dois não são:

 7a + 2b =  50
14a + 4b = 100

Eles são a mesma equação multiplicado por dois para que você não pode obter uma solução a partir deles - multiplicando a primeira de duas folhas, em seguida, subtraindo-lhe a verdade, mas inútil declaração:

0 = 0 + 0

A título de exemplo, aqui está algum código C que trabalha fora as equações simultâneas que você é colocado na sua pergunta. Primeiro alguns tipos necessários, variáveis, uma função de suporte para imprimir uma equação, e o início de main:

#include <stdio.h>

typedef struct { double r, a, b, c; } tEquation;
tEquation equ1[] = {
    { -44.3940,  50, 37, 1 },      // -44.3940 = 50a + 37b + c (A)
    { -45.3049,  43, 39, 1 },      // -45.3049 = 43a + 39b + c (B)
    { -44.9594,  52, 41, 1 },      // -44.9594 = 52a + 41b + c (C)
};
tEquation equ2[2], equ3[1];

static void dumpEqu (char *desc, tEquation *e, char *post) {
    printf ("%10s: %12.8lf = %12.8lfa + %12.8lfb + %12.8lfc (%s)\n",
        desc, e->r, e->a, e->b, e->c, post);
}

int main (void) {
    double a, b, c;

Em seguida, a redução das três equações com três incógnitas para duas equações com duas incógnitas:

    // First step, populate equ2 based on removing c from equ.

    dumpEqu (">", &(equ1[0]), "A");
    dumpEqu (">", &(equ1[1]), "B");
    dumpEqu (">", &(equ1[2]), "C");
    puts ("");

    // A - B
    equ2[0].r = equ1[0].r * equ1[1].c - equ1[1].r * equ1[0].c;
    equ2[0].a = equ1[0].a * equ1[1].c - equ1[1].a * equ1[0].c;
    equ2[0].b = equ1[0].b * equ1[1].c - equ1[1].b * equ1[0].c;
    equ2[0].c = 0;

    // B - C
    equ2[1].r = equ1[1].r * equ1[2].c - equ1[2].r * equ1[1].c;
    equ2[1].a = equ1[1].a * equ1[2].c - equ1[2].a * equ1[1].c;
    equ2[1].b = equ1[1].b * equ1[2].c - equ1[2].b * equ1[1].c;
    equ2[1].c = 0;

    dumpEqu ("A-B", &(equ2[0]), "D");
    dumpEqu ("B-C", &(equ2[1]), "E");
    puts ("");

Em seguida, a redução das duas equações com duas incógnitas a uma equação com uma incógnita:

    // Next step, populate equ3 based on removing b from equ2.

    // D - E
    equ3[0].r = equ2[0].r * equ2[1].b - equ2[1].r * equ2[0].b;
    equ3[0].a = equ2[0].a * equ2[1].b - equ2[1].a * equ2[0].b;
    equ3[0].b = 0;
    equ3[0].c = 0;

    dumpEqu ("D-E", &(equ3[0]), "F");
    puts ("");

Agora que temos uma fórmula do tipo number1 = unknown * number2, podemos simplesmente trabalhar com o valor desconhecido com unknown <- number1 / number2. Então, uma vez que você figurou que o valor para fora, substituí-lo em uma das equações com duas incógnitas e elaborar o segundo valor. Em seguida, substituir essas duas incógnitas (agora conhecidos) em uma das equações originais e agora você tem os valores para todas as três incógnitas:

    // Finally, substitute values back into equations.

    a = equ3[0].r / equ3[0].a;
    printf ("From (F    ), a = %12.8lf (G)\n", a);

    b = (equ2[0].r - equ2[0].a * a) / equ2[0].b;
    printf ("From (D,G  ), b = %12.8lf (H)\n", b);

    c = (equ1[0].r - equ1[0].a * a - equ1[0].b * b) / equ1[0].c;
    printf ("From (A,G,H), c = %12.8lf (I)\n", c);

    return 0;
}

A saída desse código coincide com os cálculos anteriores desta resposta:

         >: -44.39400000 =  50.00000000a +  37.00000000b +   1.00000000c (A)
         >: -45.30490000 =  43.00000000a +  39.00000000b +   1.00000000c (B)
         >: -44.95940000 =  52.00000000a +  41.00000000b +   1.00000000c (C)

       A-B:   0.91090000 =   7.00000000a +  -2.00000000b +   0.00000000c (D)
       B-C:  -0.34550000 =  -9.00000000a +  -2.00000000b +   0.00000000c (E)

       D-E:  -2.51280000 = -32.00000000a +   0.00000000b +   0.00000000c (F)

From (F    ), a =   0.07852500 (G)
From (D,G  ), b =  -0.18061250 (H)
From (A,G,H), c = -41.63758750 (I)
Respondeu 26/02/2009 em 11:59
fonte usuário

votos
7

Para um sistema de equações lineares 3x3 Eu acho que seria bom para lançar seus próprios algoritmos.

No entanto, você pode ter que se preocupar com precisão, divisão por zero ou números realmente pequenos e o que fazer sobre infinitamente muitas soluções. Minha sugestão é ir com um pacote de álgebra linear numérica padrão, como LAPACK .

Respondeu 08/08/2008 em 18:59
fonte usuário

votos
6

Dê uma olhada no Solver Foundation Microsoft .

Com ele você pode escrever código como este:

  SolverContext context = SolverContext.GetContext();
  Model model = context.CreateModel();

  Decision a = new Decision(Domain.Real, "a");
  Decision b = new Decision(Domain.Real, "b");
  Decision c = new Decision(Domain.Real, "c");
  model.AddDecisions(a,b,c);
  model.AddConstraint("eqA", -44.3940 == 50*a + 37*b + c);
  model.AddConstraint("eqB", -45.3049 == 43*a + 39*b + c);
  model.AddConstraint("eqC", -44.9594 == 52*a + 41*b + c);
  Solution solution = context.Solve();
  string results = solution.GetReport().ToString();
  Console.WriteLine(results); 

Aqui está a saída:
=== Solver Foundation Service Relatório ===
Datetime: 2009/04/20 23:29:55
Nome do modelo: Padrão
Capacidades solicitado: LP
Resolva Tempo (ms): 1,027
Total de Tempo (MS): 1414
Solve status de conclusão: Optimal
selecionados Solver: Microsoft.SolverFoundation.Solvers.SimplexSolver
directivas:
Microsoft.SolverFoundation.Services.Directive
Algoritmo: Primal
Aritmética: híbrido
Preços (exata): padrão
de Preços (duplo): SteepestEdge
Base: Slack
Pivot Count: 3
== Detalhes = Solução ===
Objectivos:

decisões:
um: ,0785250000000004
b: -,180612500000001
c: -41.6375875

Respondeu 21/04/2009 em 04:33
fonte usuário

votos
3

Toolkit numérica modelo do NIST tem ferramentas para fazer isso.

Uma das maneiras mais confiáveis é usar um QR decomposição .

Aqui está um exemplo de uma embalagem de modo que eu possa chamar de "GetInverse (A, InvA)" em meu código e ele vai colocar o inverso em InvA.

void GetInverse(const Array2D<double>& A, Array2D<double>& invA)
   {
   QR<double> qr(A);  
   invA = qr.solve(I); 
   }

Array2D é definido na biblioteca.

Respondeu 25/08/2008 em 19:53
fonte usuário

votos
3

Você está procurando um pacote de software que vai fazer o trabalho ou realmente fazendo as operações da matriz e tal e fazer a cada passo?

O primeiro, um colega meu usado apenas Ocaml GLPK . É apenas um wrapper para o GLPK , mas remove um monte dos passos de arrumar as coisas. Parece que você vai ter que ficar com o GLPK, no C, no entanto. Para este último, graças ao delicioso para salvar um antigo artigo eu usei para aprender LP algum tempo atrás, PDF . Se você precisar configurar mais ajuda específica, deixe-nos saber e eu tenho certeza, eu ou alguém vai passear de volta e ajudar, mas, eu acho que é bastante para a frente a partir daqui. Boa sorte!

Respondeu 03/08/2008 em 19:27
fonte usuário

votos
2

Em termos de eficiência de tempo de execução, outros têm respondido melhor do que eu Se você sempre terá o mesmo número de equações como variáveis, eu gosto regra de Cramer como é fácil de implementar. Basta escrever uma função para calcular determinante de uma matriz (ou usar um que já está escrito, eu tenho certeza que você pode encontrar um lá fora), e dividir os determinantes de duas matrizes.

Respondeu 19/09/2008 em 04:36
fonte usuário

votos
2

Do teor da sua pergunta, parece que você tem mais equações do que incógnitas e que pretende minimizar as inconsistências. Isso geralmente é feito com a regressão linear, o que minimiza a soma dos quadrados dos inconsistências. Dependendo do tamanho dos dados, você pode fazer isso em uma planilha ou em um pacote estatístico. R é um de alta qualidade, pacote gratuito que faz regressão linear, entre um monte de outras coisas. Há muito a regressão linear (e muita das pegadinha), mas como é simples de fazer para casos simples. Aqui está um exemplo R usando seus dados. Note que o "tx" é a intercepção ao seu modelo.

> y <- c(-44.394, -45.3049, -44.9594)
> a <- c(50.0, 43.0, 52.0)
> b <- c(37.0, 39.0, 41.0)
> regression = lm(y ~ a + b)
> regression

Call:
lm(formula = y ~ a + b)

Coefficients:
(Intercept)            a            b  
  -41.63759      0.07852     -0.18061  
Respondeu 17/09/2008 em 15:22
fonte usuário

votos
1
function x = LinSolve(A,y)
%
% Recursive Solution of Linear System Ax=y
% matlab equivalent: x = A\y 
% x = n x 1
% A = n x n
% y = n x 1
% Uses stack space extensively. Not efficient.
% C allows recursion, so convert it into C. 
% ----------------------------------------------
n=length(y);
x=zeros(n,1);
if(n>1)
    x(1:n-1,1) = LinSolve( A(1:n-1,1:n-1) - (A(1:n-1,n)*A(n,1:n-1))./A(n,n) , ...
                           y(1:n-1,1) - A(1:n-1,n).*(y(n,1)/A(n,n))); 
    x(n,1) = (y(n,1) - A(n,1:n-1)*x(1:n-1,1))./A(n,n); 
else
    x = y(1,1) / A(1,1);
end
Respondeu 30/12/2014 em 15:24
fonte usuário

votos
1

Pessoalmente, eu sou parcial para os algoritmos de receitas numéricas . (Eu gosto da edição C ++.)

Este livro irá ensinar-lhe por que os algoritmos de trabalhar, além de mostrar-lhe algumas implementações bem-bem depurado de esses algoritmos.

Claro, você poderia apenas cegamente usar CLAPACK (Eu usei-o com grande sucesso), mas eu gostaria de primeira mão digite um algoritmo Gaussian eliminação para pelo menos ter uma pálida idéia do tipo de trabalho que tem ido para tornar esses algoritmos estável.

Mais tarde, se você está fazendo álgebra linear mais interessante, olhando ao redor do código-fonte do Octave responderá a uma série de perguntas.

Respondeu 25/08/2008 em 19:22
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more