math - Résolution d'une équation linéaire

Translate

J'ai besoin de résoudre par programme un système d'équations linéaires en C, Objective C ou (si nécessaire) C ++.

Voici un exemple des équations:

-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

À partir de là, j'aimerais obtenir la meilleure approximation poura, b, ettx.

This question and all comments follow the "Attribution Required."

Toutes les réponses

Translate

Règle de CrameretÉlimination gaussiennesont deux bons algorithmes à usage général (voir aussiEquations linéaires simultanées). Si vous cherchez du code, consultezGiNaC, Maxima, etSymboliqueC ++(en fonction de vos exigences de licence, bien sûr).

EDIT: Je sais que vous travaillez en terre C, mais je dois aussi mettre un bon mot pourSymPy(un système d'algèbre informatique en Python). Vous pouvez apprendre beaucoup de ses algorithmes (si vous pouvez lire un peu de python). En outre, il est sous la nouvelle licence BSD, alors que la plupart des packages mathématiques gratuits sont sous GPL.

La source
Translate

Vous pouvez résoudre cela avec un programme exactement de la même manière que vous le résolvez à la main (avec multiplication et soustraction, puis réinjection des résultats dans les équations). Ce sont des mathématiques assez classiques au niveau du secondaire.

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

Donc vous vous retrouvez avec:

a =   0.0785250
b =  -0.1806125
c = -41.6375875

Si vous rebranchez ces valeurs dans A, B et C, vous constaterez qu'elles sont correctes.

L'astuce consiste à utiliser une simple matrice 4x3 qui se réduit à son tour à une matrice 3x2, puis un 2x1 qui est "a = n", n étant un nombre réel. Une fois que vous avez cela, vous l'introduisez dans la matrice suivante pour obtenir une autre valeur, puis ces deux valeurs dans la matrice suivante jusqu'à ce que vous ayez résolu toutes les variables.

À condition que vous ayez N équations distinctes, vous pouvez toujours résoudre N variables. Je dis distinct parce que ces deux ne sont pas:

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

Ils sont lesmêmeéquation multipliée par deux pour que vous ne puissiez pas en obtenir une solution - multiplier le premier par deux puis soustraire vous laisse la déclaration vraie mais inutile:

0 = 0 + 0

À titre d'exemple, voici un code C qui calcule les équations simultanées que vous placez dans votre question. D'abord quelques types nécessaires, des variables, une fonction de support pour imprimer une équation et le début demain:

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

Ensuite, la réduction des trois équations à trois inconnues à deux équations à deux inconnues:

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

Ensuite, la réduction des deux équations avec deux inconnues en une équation avec une inconnue:

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

Maintenant que nous avons une formule du typenumber1 = unknown * number2, nous pouvons simplement calculer la valeur inconnue avecunknown <- number1 / number2. Ensuite, une fois que vous avez déterminé cette valeur, remplacez-la par l'une des équations à deux inconnues et calculez la deuxième valeur. Remplacez ensuite ces deux inconnues (maintenant connues) dans l'une des équations d'origine et vous avez maintenant les valeurs pour les trois inconnues:

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

La sortie de ce code correspond aux calculs précédents dans cette réponse:

         >: -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)
La source
Translate

Pour un système 3x3 d'équations linéaires, je suppose que ce serait bien de déployer vos propres algorithmes.

Cependant, vous devrez peut-être vous soucier de la précision, de la division par zéro ou de très petits nombres et de ce qu'il faut faire pour une infinité de solutions. Ma suggestion est d'aller avec un package standard d'algèbre linéaire numérique tel queLAPACK.

La source
Marjorie Lee
Translate

Jetez un œil auFondation Microsoft Solver.

Avec lui, vous pouvez écrire un code comme celui-ci:

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

Voici la sortie:
=== Rapport du service Solver Foundation ===
Datetime: 04/20/2009 23:29:55
Nom du modèle: par défaut
Capacités demandées: LP
Temps de résolution (ms): 1027
Temps total (ms): 1414
Résoudre l'état d'achèvement: Optimal
Solveur sélectionné: Microsoft.SolverFoundation.Solvers.SimplexSolver
Directives:
Microsoft.SolverFoundation.Services.Directive
Algorithme: Primal
Arithmétique: hybride
Prix (exact): par défaut
Prix (double): SteepestEdge
Base: Slack
Nombre de pivot: 3
=== Détails de la solution ===
Buts:

Les décisions:
un: 0,0785250000000004
b: -0.180612500000001
c: -41.6375875

La source
Translate

Êtes-vous à la recherche d'un progiciel qui fera le travail ou effectuera réellement les opérations matricielles et autres et effectuera chaque étape?

Le premier, un de mes collègues vient d'utiliserOcaml GLPK. C'est juste un emballage pour leGLPK, mais cela supprime de nombreuses étapes de configuration. Il semble que vous allez devoir vous en tenir au GLPK, en C, cependant. Pour ce dernier, merci à Delicious d'avoir sauvé un vieil article que j'avais l'habitude d'apprendre il y a quelques temps,PDF. Si vous avez besoin d'une aide spécifique pour vous installer davantage, faites-le nous savoir et je suis sûr que quelqu'un ou moi reviendrons et aiderons, mais je pense que c'est assez simple à partir d'ici. Bonne chance!

La source
Translate

Boîte à outils numérique de modèledu NIST a des outils pour le faire.

L'un des moyens les plus fiables consiste à utiliser unDécomposition QR.

Voici un exemple de wrapper pour que je puisse appeler "GetInverse (A, InvA)" dans mon code et il mettra l'inverse dans InvA.

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

Array2D est défini dans la bibliothèque.

La source
Translate

D'après le libellé de votre question, il semble que vous ayez plus d'équations que d'inconnues et que vous vouliez minimiser les incohérences. Cela se fait généralement avec une régression linéaire, qui minimise la somme des carrés des incohérences. Selon la taille des données, vous pouvez le faire dans une feuille de calcul ou dans un progiciel statistique. R est un package gratuit de haute qualité qui effectue une régression linéaire, entre autres. Il y a beaucoup de régression linéaire (et beaucoup de pièges), mais comme c'est simple à faire pour des cas simples. Voici un exemple R utilisant vos données. Notez que le "tx" est l'interception de votre modèle.

> 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  
La source
Translate

En termes d'efficacité d'exécution, d'autres ont mieux répondu que moi. Si vous aurez toujours le même nombre d'équations que de variables, j'aimeRègle de Cramercar il est facile à mettre en œuvre. Écrivez simplement une fonction pour calculer le déterminant d'une matrice (ou utilisez-en une qui est déjà écrite, je suis sûr que vous pouvez en trouver une là-bas), et divisez les déterminants de deux matrices.

La source
Translate

Personnellement, je suis partisan des algorithmes deRecettes numériques. (J'adore l'édition C ++.)

Ce livre vous apprendra pourquoi les algorithmes fonctionnent, et vous montrera quelques implémentations assez bien déboguées de ces algorithmes.

Bien sûr, vous pouvez simplement utiliser aveuglémentCLAPACK(Je l'ai utilisé avec beaucoup de succès), mais je voudrais d'abord taper un algorithme d'élimination gaussienne pour au moins avoir une faible idée du type de travail qui a permis de stabiliser ces algorithmes.

Plus tard, si vous faites de l'algèbre linéaire plus intéressante, regardez autour du code source deOctaverépondra à beaucoup de questions.

La source
Translate
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
La source
précédent:
Python et MySQL