Løse en lineær ligning

stemmer
35

Jeg trenger å programma løse et system av lineære ligninger i C, Objective C, eller (hvis nødvendig) C ++.

Her er et eksempel på ligningene:

-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

Fra dette, vil jeg gjerne få den beste tilnærming for a, bog tx.

Publisert på 03/08/2008 klokken 18:14
kilden bruker
På andre språk...                            


10 svar

stemmer
17

Cramers regel og Gauss eliminasjon er to gode, generelle algoritmer (se også Lineære likninger ). Hvis du leter etter kode, sjekk ut GiNaC , Maxima , og SymbolicC ++ (avhengig av lisenskravene, selvfølgelig).

EDIT: Jeg vet du jobber i C land, men jeg må også legge inn et godt ord for SymPy (en datamaskin algebra system i Python). Du kan lære mye fra sine algoritmer (hvis du kan lese litt av Python). Dessuten er det under den nye BSD-lisensen, mens de fleste av de gratis matematiske pakker er GPL.

Svarte 03/08/2008 kl. 18:37
kilden bruker

stemmer
15

Du kan løse dette med et program nøyaktig samme måte som du løse det for hånd (med multiplikasjon og subtraksjon, deretter fôre resultater tilbake i ligningene). Dette er ganske standard videregående skole-nivå matematikk.

-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)

Slik at du ender opp med:

a =   0.0785250
b =  -0.1806125
c = -41.6375875

Hvis du kobler disse verdiene tilbake til A, B og C, vil du finne at de er riktige.

Kunsten er å bruke en enkel 4x3 matrise som reduserer i sin tur til en 3x2 matrise, da en 2x1 som er "a = n", hvor n er et faktisk antall. Når du har det, du mate den inn i neste matrise opp for å få en annen verdi, da disse to verdiene i neste matrisen opp før du har løst alle variabler.

Forutsatt at du har N forskjellige ligninger, kan du alltid løse for N variabler. Jeg sier tydelig fordi disse to er ikke:

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

De er de samme ligningen multiplisert med to, slik at du ikke kan få en løsning fra dem - å multiplisere den første av to deretter trekke etterlater deg med den sanne, men ubrukelig uttalelse:

0 = 0 + 0

Som et eksempel, her er noen C-kode som funker de likninger som du plassert i spørsmålet ditt. Først noen nødvendige typer, variabler, en støttefunksjon for å skrive ut en ligning, og starten på 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;

Neste, reduksjon av de tre ligninger med tre ukjente til to ligninger med to ukjente:

    // 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 ("");

Neste, reduksjon av de to ligninger med to ukjente i en likning med en ukjent:

    // 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 ("");

Nå som vi har en formel av typen number1 = unknown * number2, kan vi bare regne ut den ukjente verdien med unknown <- number1 / number2. Deretter, når du har funnet denne verdien ut, erstatte den til en av de ligninger med to ukjente og trene den andre verdien. Deretter erstatte begge disse (nå kjente) ukjente inn i en av de opprinnelige ligningene og du har nå verdier for alle tre ukjente:

    // 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;
}

Utgangen av den koden samsvarer med tidligere beregninger i dette svaret:

         >: -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)
Svarte 26/02/2009 kl. 10:59
kilden bruker

stemmer
7

For et 3x3 system av lineære ligninger Jeg tror det ville være greit å rulle ut dine egne algoritmer.

Men kanskje du trenger å bekymre deg nøyaktighet, divisjon med null eller veldig små tall og hva de skal gjøre om uendelig mange løsninger. Mitt forslag er å gå med en standard numerisk lineær algebra pakke som LAPACK .

Svarte 08/08/2008 kl. 17:59
kilden bruker

stemmer
6

Ta en titt på Microsoft Solver Foundation .

Med det kan du skrive kode som dette:

  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); 

Her er resultatet:
=== Solver Foundation Tjeneste Rapporter ===
Datetime: 04/20/2009 23:29:55
Modellnavn: Standard
Capabilities spurt: LP
Løs tid (ms): 1027
Total tid (ms): 1414
Løs ferdigstillelse Status: Optimale
Solver Utvalgte: Microsoft.SolverFoundation.Solvers.SimplexSolver
direktiver:
Microsoft.SolverFoundation.Services.Directive
algoritme: Primal
Arithmetic: hybrid
Pricing (eksakt): Standard
Priser (dobbel): SteepestEdge
Begrunnelse: Slack
Pivot Count: 3
== = Løsning Detaljer ===
Mål:

Vedtak:
a: 0,0785250000000004
b: -,180612500000001
c: -41.6375875

Svarte 21/04/2009 kl. 03:33
kilden bruker

stemmer
3

Mal Numerisk Toolkit fra NIST har verktøy for å gjøre det.

En av de mer pålitelige måter er å bruke en QR Dekomponering .

Her er et eksempel på en wrapper slik at jeg kan kalle "GetInverse (A, InvA)" i min kode og det vil sette den inverse inn InvA.

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

Array2D er definert i biblioteket.

Svarte 25/08/2008 kl. 18:53
kilden bruker

stemmer
3

Er du ute etter en programvarepakke som skal gjøre jobben, eller å faktisk gjøre matriseoperasjoner og slikt og gjøre hvert trinn?

Den første, en kollega av meg bare brukt Objective Caml GLPK . Det er bare en wrapper for GLPK , men det fjerner mye av trinnene for å sette ting opp. Det ser ut som du er nødt til å feste med GLPK, i C, skjønt. For sistnevnte, takket være deilig for lagring av en gammel artikkel jeg pleide å lære LP stund tilbake, PDF . Hvis du trenger spesifikk hjelp til å sette opp videre, gi oss beskjed, og jeg er sikker på, meg eller noen vil vandre tilbake inn og hjelpe, men jeg tror det er ganske rett frem herfra. Lykke til!

Svarte 03/08/2008 kl. 18:27
kilden bruker

stemmer
2

I forhold til kjøretid effektivitet, har andre svarte bedre enn I. Hvis du alltid vil ha samme antall ligninger som variabler, jeg liker Cramers regel som det er lett å implementere. Bare skrive en funksjon for å beregne determinanten til en matrise (eller bruke en som allerede er skrevet, jeg er sikker på at du kan finne en der ute), og dele determinants av to matriser.

Svarte 19/09/2008 kl. 03:36
kilden bruker

stemmer
2

Av ordlyden i spørsmålet ditt, virker det som om du har flere ligninger enn ukjente, og du ønsker å minimere uoverensstemmelser. Dette gjøres typisk med lineær regresjon, som minimaliserer summen av kvadratene av uoverensstemmelser. Avhengig av størrelsen på data, kan du gjøre dette i et regneark eller i en statistikkpakke. R er en høy kvalitet, gratis pakke som gjør lineær regresjon, blant mange andre ting. Det er mye å lineær regresjon (og mye fikser tallet), men som det er enkelt å gjøre for enkle tilfeller. Her er en R eksempel ved hjelp av dine data. Merk at "tx" er skjærings til din modell.

> 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  
Svarte 17/09/2008 kl. 14:22
kilden bruker

stemmer
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
Svarte 30/12/2014 kl. 15:24
kilden bruker

stemmer
1

Personlig er jeg delvis til algoritmer for Numerical Recipes . (Jeg er glad i C ++ utgave.)

Denne boken vil lære deg hvorfor algoritmer fungerer, pluss vise deg noen ganske brønner feilsøkt implementeringer av disse algoritmene.

Selvfølgelig kan du bare blindt bruke CLAPACK (Jeg har brukt det med stor suksess), men jeg vil først hånd skriver en Gaussisk eliminasjon algoritme for å i det minste ha en svak idé om hva slags arbeid som har gått til å gjøre disse algoritmene stabil.

Senere, hvis du gjør mer interessant lineær algebra, ser rundt kildekoden til Octave vil svare på en rekke spørsmål.

Svarte 25/08/2008 kl. 18:22
kilden bruker

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