Rezolvarea unei ecuații liniare

Î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 qⁿ 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 = a₀...a_n-1 of length n on the alphabet F, associate the element β of K given by β = a₀θ + a₁θ^q + ... + a_n-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.

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

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ă.

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.

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!

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.

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)

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  

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.

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.

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ă.

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

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