La résolution d'une équation linéaire

voix
35

Je dois résoudre un programme 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

De cela, je voudrais obtenir la meilleure approximation a, bet tx.

Créé 03/08/2008 à 19:14
source utilisateur
Dans d'autres langues...                            


10 réponses

voix
17

Règle de Cramer et élimination gaussienne sont deux bons, des algorithmes d'usage général (voir aussi les équations linéaires simultanées ). Si vous êtes à la recherche pour le code, consultez GiNaC , Maxima et SymbolicC ++ ( en fonction de vos besoins de licence, bien sûr).

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

Créé 03/08/2008 à 19:37
source utilisateur

voix
15

Vous pouvez résoudre ce avec un programme exactement de la même façon que vous le résoudre manuellement (avec la multiplication et la soustraction, puis les résultats réinjectant dans les équations). Ceci est assez standard en mathématiques 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 branchez ces valeurs A nouveau dans, B et C, vous trouverez qu'ils sont corrects.

L'astuce consiste à utiliser une simple matrice 4x3 qui 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, vous nourrir dans la matrice suivante jusqu'à obtenir une autre valeur, ces deux valeurs dans la matrice suivante jusqu'à ce que vous avez résolu toutes les variables.

Pourvu que vous avez N équations distinctes, vous pouvez toujours résoudre pour les variables N. Je dis distincts parce que ces deux ne sont pas:

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

Ils sont la même équation multipliée par deux pour que vous ne pouvez pas obtenir une solution d'eux - multiplier la première par deux feuilles puis en retranchant vous avec l'énoncé vrai , mais inutile:

0 = 0 + 0

A titre d'exemple, voici un code C qui fonctionne les équations simultanées que vous êtes placé dans votre question. Tout d' abord quelques types nécessaires, les variables, une fonction de support pour l' impression d'une équation, et le début 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;

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 à deux inconnues à une équation à 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 type number1 = unknown * number2, nous pouvons simplement travailler sur la valeur inconnue avec unknown <- number1 / number2. Ensuite, une fois que vous avez compris que la valeur à, substituer dans l' une des équations à deux inconnues et établir la deuxième valeur. Ensuite , remplacer ces deux (maintenant connues) inconnues 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)
Créé 26/02/2009 à 11:59
source utilisateur

voix
7

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

Cependant, vous pourriez avoir à vous soucier de la précision, division par zéro ou vraiment un petit nombre et ce qu'il faut faire une infinité de solutions. Ma suggestion est d'aller avec un paquet d'algèbre linéaire numérique standard tel que LAPACK .

Créé 08/08/2008 à 18:59
source utilisateur

voix
6

Jetez un oeil à la Fondation Microsoft Solver .

Avec elle, vous pouvez écrire du code comme ceci:

  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:
=== Solver Foundation Report Service ===
Datetime: 04/20/2009 23:29:55
Nom du modèle: par défaut
Capacités demandé: LP
Solve Temps (ms): 1027
Durée totale (ms): 1414
Résoudre État d' achèvement: Optimal
Solver sélectionnés: Microsoft.SolverFoundation.Solvers.SimplexSolver
directives:
Microsoft.SolverFoundation.Services.Directive
algorithme: Primal
arithmétique: hybride
Prix (exact): Par défaut
Prix (double): SteepestEdge
Base: Slack
Pivot Count: 3
== = Solution Détails ===
Objectifs:

décisions:
a: ,0785250000000004
b: -0,180612500000001
c: -41.6375875

Créé 21/04/2009 à 04:33
source utilisateur

voix
3

Modèle numérique Toolkit du NIST a des outils pour le faire.

L' une des façons les plus fiables est d'utiliser une décomposition QR .

Voici un exemple d'une enveloppe pour que je puisse appeler « GetInverse (A, Inva) » dans mon code et il va mettre l'inverse en 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.

Créé 25/08/2008 à 19:53
source utilisateur

voix
3

Vous cherchez un logiciel qui va faire le travail ou en train de faire les opérations de matrice et tel et faire chaque étape?

Le premier, un collègue de travail de la mine juste utilisé Ocaml GLPK . Il est juste une enveloppe pour le GLPK , mais il enlève beaucoup des étapes de la mise en place des choses. On dirait que vous allez avoir à coller avec le GLPK, en C, cependant. Pour ce dernier, grâce à délicieux pour sauver un vieil article que j'apprenions quelque temps LP arrière, PDF . Si vous avez besoin d' aide spécifique mise en place plus loin, laissez - nous savoir et je suis sûr, moi ou quelqu'un va se balader et aider, mais je pense qu'il est assez simple en avant d'ici. Bonne chance!

Créé 03/08/2008 à 19:27
source utilisateur

voix
2

En termes d'efficacité de l' exécution, d' autres ont répondu mieux que moi si vous aurez toujours le même nombre d'équations comme variables, j'aime la règle de Cramer comme il est facile à mettre en œuvre. Il suffit d' écrire une fonction pour calculer déterminant d'une matrice (ou utiliser celui qui est déjà écrit, je suis sûr que vous pouvez trouver un là - bas), et diviser les déterminants de deux matrices.

Créé 19/09/2008 à 04:36
source utilisateur

voix
2

De la formulation de votre question, il semble que vous avez plus d'équations que d'inconnues et que vous voulez minimiser les incohérences. Cela se fait habituellement par régression linéaire, ce qui minimise la somme des carrés des incohérences. En fonction de la taille des données, vous pouvez le faire dans une feuille de calcul ou dans un ensemble statistique. R est une haute qualité, forfait gratuit qui fait la régression linéaire, parmi beaucoup d'autres choses. Il y a beaucoup de régression linéaire (et bien sûr beaucoup de Gotcha), mais comme il est facile de le faire pour les cas simples. Voici un exemple R en utilisant vos données. Notez que le « tx » est l'interception à 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  
Créé 17/09/2008 à 15:22
source utilisateur

voix
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
Créé 30/12/2014 à 15:24
source utilisateur

voix
1

Personnellement, je suis partie aux algorithmes de recettes numériques . (Je suis friand de l'édition C ++.)

Ce livre vous apprendra pourquoi les algorithmes de travail, plus vous montrer quelques implémentations assez-bien déboguée de ces algorithmes.

Bien sûr, vous pouvez simplement utiliser aveuglément CLAPACK (je l' ai utilisé avec grand succès), mais je voudrais d' abord la main un algorithme de type élimination gaussienne au moins avoir une faible idée du genre de travail qui a été fait pour rendre ces algorithmes stable.

Par la suite, si vous faites l' algèbre linéaire plus intéressant, regardant autour du code source d' Octave répondra à beaucoup de questions.

Créé 25/08/2008 à 19:22
source utilisateur

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