Sistem linearnih jednačina

U matematici i linearnoj algebri, sistem linearnih jednačina je skup linearnih jednačina, kao što je:

${\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}}$

Standardni problem predstavlja utvrđivanje postoji li skup vrijednosti za nepoznate $x_{1},x_{2},x_{3}\,\!$, koji zadovoljava sve jednačine istovremeno, kao i pronalaženje takovog skupa ako postoji. Postojanje skupa rješenja ovisi od jednačina, ali i od dostupnih vrijednosti (radi li se o cijelim brojevima, realnim brojevima, i slično).

Sistemi linearnih jednačina 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 sistem linearnih jednačina. Međutim, među najučinkovitijima su Gaussov postupak i dekompozicija Choleskyja.

Poopćeno, sistem sa m linearnih jednačina i n nepoznatih se zapisuje na sljedeći :

${\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}}$

gdje su $x_{1},\ x_{2},...,x_{n}$ nepoznate, a brojevi $a_{11},\ a_{12},...,\ a_{mn}$ su koeficijenti sistema. Stavljamo koeficijente u matricu na sljedeći način:

${\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}}$

Ako predstavimo svaku matricu slovom, ovo postaje

$A\mathbf {x} =\mathbf {b}$

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 sisteme, č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 (tačno će jedan biti tačan) za svaki dani sistem linearnih jednadžbi:

• sistem nema rješenja (sistem je proturječan)
• sistem ima tačno jedno rješenje
• sistem ima beskonačno mnogo rješenja

Sistem oblika

$A\mathbf {x} =\mathbf {0}$

se naziva homogenim sistemom linearnih jednačina. 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(n²) (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 verzija. 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 srednje matrice. Ako je bilo koja od singularnih vrijednosti preblizu nule, i stoga blizu singularnosti, postavlja se na nulu.

Vanjski linkovi

• Online linearni rješavač
• Sistemi linearnih diferencijalnih jednadžbi
• Rješenje linearnih sistema Arhivirano 15. 9. 2007. na Wayback Machine (fr)