Sustav linearnih jednadžbi
U matematici i linearnoj algebri, sustav linearnih jednadžbi je skup linearnih jednadžbi, kao što je
- [math]\displaystyle{ \begin{array}{rcrcrcc} 3x_1 &+& 2x_2 &-& x_3 &=& 1 \\ 2x_1 &-& 2x_2 &+& 4x_3 &=& -2 \\ -x_1 &+& \frac{1}{2}x_2 &-& x_3 &=& 0 \end{array} }[/math]
Standardni problem predstavlja utvrđivanje postoji li skup vrijednosti za nepoznate [math]\displaystyle{ x_1, x_2, x_3\,\! }[/math], koji zadovoljava sve jednadžbe istovremeno, kao i pronalaženje takovog skupa ako postoji. Postojanje skupa rješenja ovisi od jednadžbi, ali i od dostupnih vrijednosti (radi li se o cijelim brojevima, realnim brojevima, i slično).
Sustavi linearnih jednadžbi spadaju među najstarije matematičke probleme, i imaju mnoge primjene, kao što su obrada digitalnih signala, procjene, predviđanja, kao i linearno programiranje ili aproksimacija nelinearnih problema u numeričkoj analizi. Postoji mnogo načina da se riješi sustav linearnih jednadžbi. Međutim, među najučinkovitijima su Gaussov postupak i dekompozicija Choleskyja.
Poopćeno, sustav sa m linearnih jednadžbi i n nepoznanica se zapisuje na sljedeći način
- [math]\displaystyle{ \begin{array}{rcrcccrcl} a_{11}x_1 &+& a_{12}x_2 &+& \cdots &+& a_{1n}x_n &=& b_1 \\ a_{21}x_1 &+& a_{22}x_2 &+& \cdots &+& a_{2n}x_n &=& b_2 \\ &&&\vdots&&&&&\vdots \\ a_{m1}x_1 &+& a_{m2}x_2 &+& \cdots &+& a_{mn}x_n &=& b_m \end{array} }[/math]
gdje su [math]\displaystyle{ x_1,\ x_2,...,x_n }[/math] nepoznanice, a brojevi [math]\displaystyle{ a_{11},\ a_{12},...,\ a_{mn} }[/math] su koeficijenti sustava. Stavljamo koeficijente u matricu na sljedeći način:
- [math]\displaystyle{ \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} }[/math]
Ako predstavimo svaku matricu slovom, ovo postaje
- [math]\displaystyle{ A\mathbf{x} = \mathbf{b} }[/math]
gdje je A a m×n matrica, x je vektor stupac sa n članova, a b je vektor stupac sa m članova. Gaus-Jordanova eliminacija se primjenjuje na sve ove sustave, čak i ako su koeficijenti iz nekog proizvoljnog polja.
Ako je polje beskonačno (kao u slučaju realnih ili kompleksnih brojeva), moguća su samo sljedeća tri slučaja (točno će jedan biti točan) za svaki dani sustav linearnih jednadžbi:
- sustav nema rješenja (sustav je proturječan, tj. nemoguć)
- sustav ima točno jedno rješenje (sustav je istinit)
- sustav ima beskonačno mnogo rješenja (sustav je neodređen)
Sustav oblika
- [math]\displaystyle{ A\mathbf{x} = \mathbf{0} }[/math]
se naziva homogenim sustavom linearnih jednadžbi. Skup svih rješenja se naziva nul prostorom matrice A.
Posebno u svjetlu obilja gorenavedenih primjena, nekoliko učinkovitijih zamjena Gauss-Jordanovoj eliminaciji je razvijeno za širok spektar specijalnih slučajeva. Mnogi od ovih poboljšanih algoritama su složenosti O(n2) (vidi: Veliko-O notacija). Neki od najuobičajenijih specijalnih slučajeva su:
- Za probleme oblika Ax = b, gdje je A simetrična Toeplitzova matrica, može se koristiti Levinsonova rekurzija ili neka od njenih inačica. Jedna od često korištenih varijacija je Schurova rekurzija, koja se koristi u obradi digitalnih signala.
- Za probleme oblika Ax = b, gdje je A singularna matrica, ili gotovo singularna, matrica A se dekomponira u umnožak triju matrica. Matrice s lijeve i desne strane su lijevi i desni singularni vektori. Matrica u sredini je dijagonalna matrica i sadrži singularne vrijednosti. Matrica tada može biti invertirana jednostavnom zamjenom redoslijeda tri komponente, transponiranjem matrica singularnih vektora, te uzimanjem recipročne vrijednosti dijagonalnih elemenata središnje matrice. Ako je bilo koja od singularnih vrijednosti preblizu nule, i stoga blizu singularnosti, postavlja se na nulu.