Sistema lineal d'equacions

De Viquipèdia

En matemàtiques i àlgebra lineal, un sistema lineal d'equacions és un conjunt d'equacions lineals com el següent:

3x1 + 2x2x3 = 1
2x1 − 2x2 + 4x3 = −2
x1 + ½x2x3 = 0.

El problema consisteix a trobar els valors desconeguts de les variables x1, x2 i x3 que satisfan les tres equacions.

Els sistemes lineals d'equacions és un dels problemes més antics de les matemàtiques i ténen una infinitat d'aplicacions, com en el processament digital de senyals, l'estimació, la predicció i més generalment en la programació lineal així com en l'aproximació de problemes no lineals d'anàlisi numèric. Unes formes eficients per a resoldre sistemes d'equacions lineals són l'eliminació de Gauss-Jordan i la descomposició de Cholesky.

En general, un sistema amb m equacions lineals n incògnites pot ser escrit com

a11x1 + a12x2 + … + a1nxn = b1
a21x1 + a22x2 + … + a2nxn = b2
    :
    :
am1x1 + am2x2 + … + amnxn = bm,

on x1, ... ,xn són les incògnites i els nombres aij són els coeficients del sistema. És possible reescriure el sistema separant els coeficients amb notació matricial:

\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \end{bmatrix}   \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix}  = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{bmatrix}

Si representem cada matriu amb una única lletra obtenim:

Ax = b,

on A és una matriu m per n, x és un vector col·lumna de longitud n i b és un altre vector col·lumna de longitud m. El sistema de l'eliminació de Gauss-Jordan s'aplica a aquest tipus de sistemes, sigui quin sigui el cos del que provinguin els coeficients.

Si el cos és infinit (com és el cas dels nombres reals o complexos), aleshores només es poden donar els següents casos:

  • el sistema no té solució (en aquest cas diem que el sistema està sobredeterminat o que és incompatible)
  • el sistema té una única solució (en aquest cas diem que el sistema és compatible determinat)
  • el sistema té un nombre infinit de solucions (el sistema és compatible indeterminat).

Un sistema de la forma

Ax = 0

s'anomena homogeni. El conjunt de totes les sol·lucions d'aquest tipus de sistemes se'ls hi anomena nucli de la matriu i s'escriu Nuc A.

S'han desenvolupat algorismes alternatius molt més eficients a l'eliminació de Gauss-Jordan per a una gran quantitat de casos específics. La majoria d'aquests algorismes millorats ténen una complexitat computacional de O(n²). Alguns dels mètodes més usats són:

  • Per als problemes de la forma Ax = b, on A és una matriu Toeplitz simètrica, es pot utilitzar la recurssió de Levinson o algun dels mètodes derivats d'aquest. Un mètode derivat de la recursió de Levinson és la recurssió de Schur, que és àmpliament usat en el camp del processament digital de senyals.
  • Per als problemes de la forma Ax = b, on A és una matriu singular o casi singular, la matriz A es descomposa en el producto de tres matrius én un procés anomenat descomposició de valors singulares.

[edita] Enllaços externs