Vă mulțumim pentru susținere

Rezolvarea unei ecuații liniare

Trebuie să rezolv programatic un sistem de ecuații liniare în C, Obiectiv C sau (dacă este necesar) C ++.

Iată un exemplu de ecuații:

-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

Din aceasta, aș dori să obțin cea mai bună aproximare pentru a , b și tx .

0
adăugat editat
Alți oameni au răspuns la acest lucru, dar verificați cartea Analiza numerică: matematică a computerelor științifice de Kincaid și Cheney. Cartea se referă în mare parte la rezolvarea diferitelor sisteme de ecuații.
adăugat autor Matthew

13 răspunsuri

În "Algebrele libere de minciună" de la Reutenauer, secțiunea 7.6.2:

A direct bijection between primitive necklaces of length n over F and the set of irreducible polynomials of degree n in F[x] may be described as follows: let K be the field with qn elements; it is a vector space of dimension n over F, so there exists in K an element θ such that the set {θ, θq, ..., θqn-1} is a linear basis of K over F.

With each word w = a0...an-1 of length n on the alphabet F, associate the element β of K given by β = a0θ + a1θq + ... + an-1 θqn-1. It is easily shown that to conjugate words w, w' correspond conjugate elements β, β' in the field extension K/F, and that w \mapsto β is a bijection. Hence, to a primitive conjugation class corresponds a conjugation class of cardinality n in K; to the latter corresponds a unique irreducible polynomial of degree n in F[x]. This gives the desired bijection.

25
adăugat

See section 38.10 "Generating irreducible polynomials from Lyndon words" of http://www.jjj.de/fxt/#fxtbook

4
adăugat

Cred că o astfel de bijecție este prezentată în

S. Golomb. Ineducabile polinoame, coduri de sincronizare, coliere primitive și algebra ciclotomică. În Proc. Conf matematică combinatorie. și Appl., pag. 358- 370, Chapel Hill, 1969. Univ. din North Carolina Press.

dar nu am acces imediat la această lucrare - sunt destul de sigur că există.

3
adăugat
Un pic de dovezi suplimentare (încă nu concludente): springerlink.com/index/P6X9P2BV73L2X2GG.pdf "Deoarece există o bijecție între cuvinte Lyndon peste un alfabet de cardinalitate k și polinoame ireductibile peste Fk [10] ...", unde referința [10] este la hârtia lui Golomb.
adăugat autor CodingWithoutComments
Nu par să aibă acces la ea, dar cel puțin o altă lucrare ( Berstel "rel =" nofollow noreferrer "> jstor.org/stable/2001573"> Berstel și Reutenauer ) sugerează că aceasta este o problemă deschisă. Într-adevăr, am aceeași motivație ca și ei pentru a pune această întrebare, deci presupun că ar fi trebuit să citim mai atent acest document.
adăugat autor Qiaochu Yuan

Corespondența inventată de Golomb se bazează pe alegerea unui element primitiv în domeniul ordinii q ^ n. Apoi, la fiecare cuvânt Lyndon L = (l_0, l_1, ..., l_ {n-1}) se atribuie polinomul primitiv având ca rădăcină elementul a ^ {m (L)} unde m (L) suma întregului lui li * q ^ i peste i = 0,1, ..., n-1.

3
adăugat

Căutați un pachet software care să facă lucrarea sau să facă efectiv operațiunile de matrice și astfel și să faceți fiecare pas?

Primul, un coleg al meu a folosit doar Ocaml GLPK . Este doar un pachet pentru GLPK , dar elimină o mulțime de pași de a stabili lucrurile. Se pare că va trebui să rămâi cu GLPK, în C, totuși. Pentru aceasta din urmă, datorită deliciosului pentru salvarea unui articol vechi, am învățat o clipă înapoi, PDF . Dacă aveți nevoie de ajutor specific pentru a vă stabili mai departe, anunțați-ne și sunt sigur că eu sau cineva mă voi întoarce și voi ajuta, dar cred că este destul de direct de aici. Mult noroc!

0
adăugat

Personal, eu sunt parțială cu algoritmii de Rețete Numerice . (Mă bucur de ediția C ++.)

Această carte vă va învăța de ce funcționează algoritmii și vă va arăta câteva implementări destul de bine depuse de acești algoritmi.

Desigur, ai putea folosi doar orbește CLAPACK (am folosit-o cu mare succes), dar Mai întâi aș scrie un algoritm de eliminare Gaussian pentru a avea cel puțin o idee slabă despre tipul de lucru care a trecut în a face acești algoritmi stabili.

Mai târziu, dacă faci algebră liniară mai interesantă, uită-te în jurul codului sursă al Octave va răspunde la multe întrebări.

0
adăugat

Puteți rezolva acest lucru cu un program exact la fel cum îl rezolvi manual (cu înmulțire și scădere, apoi hrănirea rezultatelor înapoi în ecuații). Aceasta este destul de standard la nivel secundar la nivel de școală matematică.

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

Deci, ați terminat cu:

a =   0.0785250
b =  -0.1806125
c = -41.6375875

Dacă conectați aceste valori înapoi la A, B și C, veți găsi că sunt corecte.

Trucul este de a folosi o simplă matrice 4x3 care reduce la rândul său la o matrice 3x2, apoi o 2x1 care este "a = n", n fiind un număr efectiv. Odată ce ați făcut asta, îl hrăniți în matricea următoare pentru a obține o altă valoare, apoi cele două valori în matricea următoare până când ați rezolvat toate variabilele.

Cu condiția să aveți N ecuații distincte, puteți rezolva întotdeauna pentru variabilele N. Spun distinct, deoarece aceste două nu sunt:

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

Acestea sunt ecuația aceleași înmulțite cu două, astfel încât să nu puteți obține o soluție din ele - înmulțirea primului cu doi, apoi scăderea frunzelor cu declarația adevărată, dar inutilă:

0 = 0 + 0

De exemplu, iată un cod C care elaborează ecuațiile simultane pe care le-ați plasat în întrebarea dvs. Mai întâi, unele tipuri necesare, variabile, o funcție de suport pentru imprimarea unei ecuații și începutul main :

#include 

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;

Apoi, reducerea celor trei ecuații cu trei necunoscute la două ecuații cu două necunoscute:

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

Apoi, reducerea celor două ecuații cu două necunoscute la o ecuație cu una necunoscută:

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

Now that we have a formula of the type number1 = unknown * number2, we can simply work out the unknown value with unknown <- number1 / number2. Then, once you've figured that value out, substitute it into one of the equations with two unknowns and work out the second value. Then substitute both those (now-known) unknowns into one of the original equations and you now have the values for all three unknowns:

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

Rezultatul acestui cod corespunde calculelor anterioare din acest răspuns:

         >: -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)
0
adăugat

Din formularea întrebării dvs., se pare că aveți mai multe ecuații decât necunoscute și doriți să minimalizați inconsecvențele. Acest lucru se face, de obicei, cu regresie liniară, care minimizează suma pătratelor de neconcordanțe. În funcție de mărimea datelor, puteți face acest lucru într-o foaie de calcul sau într-un pachet statistic. R este un pachet de înaltă calitate, gratuit, care face regresie liniară, printre multe alte lucruri. Există o mulțime de regresie liniară (și o mulțime de gotcha's), dar pentru că este simplu de făcut pentru cazurile simple. Iată un exemplu R care utilizează datele dvs. Rețineți că "tx" este interceptarea modelului dvs.

> 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  
0
adăugat

In terms of run-time efficiency, others have answered better than I. If you always will have the same number of equations as variables, I like Cramer's rule as it's easy to implement. Just write a function to calculate determinant of a matrix (or use one that's already written, I'm sure you can find one out there), and divide the determinants of two matrices.

0
adăugat

Cramer's Rule and Gaussian Elimination are two good, general-purpose algorithms (also see Simultaneous Linear Equations). If you're looking for code, check out GiNaC, Maxima, and SymbolicC++ (depending on your licensing requirements, of course).

EDIT: Știu că lucrezi la terenul C, dar trebuie să pun un cuvânt bun și pentru SymPy (un sistem de algebră în Python). Puteți învăța o mulțime de algoritmi (dacă puteți citi un pic de Python). De asemenea, este sub noua licență BSD, în timp ce majoritatea pachetelor de matematică gratuite sunt GPL.

0
adăugat
de fapt, nici regula guvernatorului, nici eliminarea gaussiană nu sunt foarte bune în lumea reală. nu au proprietăți numerice bune și nici nu sunt folosite mult pentru aplicații serioase. încercați factorizarea LDU. sau mai bine, nu vă faceți griji cu privire la algoritm și utilizați în schimb LAPACK.
adăugat autor Peter
pentru variabilele număr mai puțin de 4, regula lui Cramer este cea mai bună pentru scrierea codului de rezolvare imo
adăugat autor Ge Rong

Template Numerical Toolkit from NIST has tools for doing that.

Una dintre modalitățile mai fiabile este utilizarea unei Descompunere QR .

Iată un exemplu de pachet, astfel încât să pot numi "GetInverse (A, InvA)" în codul meu și va pune inversul în InvA.

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

Array2D este definit în bibliotecă.

0
adăugat
Ce este I în qr.solve (I) ?
adăugat autor Ponkadoodle

Uitați-vă la Microsoft Solver Foundation .

Cu ajutorul acestuia puteți scrie codul astfel:

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

Here is the output:
===Solver Foundation Service Report===
Datetime: 04/20/2009 23:29:55
Model Name: Default
Capabilities requested: LP
Solve Time (ms): 1027
Total Time (ms): 1414
Solve Completion Status: Optimal
Solver Selected: Microsoft.SolverFoundation.Solvers.SimplexSolver
Directives:
Microsoft.SolverFoundation.Services.Directive
Algorithm: Primal
Arithmetic: Hybrid
Pricing (exact): Default
Pricing (double): SteepestEdge
Basis: Slack
Pivot Count: 3
===Solution Details===
Goals:

Decisions:
a: 0.0785250000000004
b: -0.180612500000001
c: -41.6375875

0
adăugat
Deci, ce proprietati numerice de stabilitate ne putem astepta din aceasta? Deoarece aceasta nu este o sursă deschisă, se presupune că va veni cu due diligence, repere împotriva bibliotecilor mainstream precum LAPACK etc. Trebuie să existe un avantaj substanțial pentru a depăși necesitatea de a merge cu o soluție de proprietate.
adăugat autor Evgeni Sergeev
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
0
adăugat
Deci, dacă A (n, n) este zero?
adăugat autor Evgeni Sergeev