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 + 2x2 − x3 = 1
- 2x1 − 2x2 + 4x3 = −2
- −x1 + ½x2 − x3 = 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:
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.