Sistem linearnih jednačina

Linearni sistem sa tri promenljive određuje skup ravni. Presek svih ravni je rešenje.

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 je da se utvrdi da li postoji skup vrednosti za nepoznate $x_1, x_2, x_3\,\!$, koji zadovoljava sve jednačine istovremeno, i da se nađe takav skup ukoliko postoji. Postojanje skupa rešenja zavisi od jednačina, ali i od dostupnih vrednosti (da li se radi o celim brojevima, realnim brojevima, i slično). Sistem iz gornjeg primera ima jedinstveno rešenje:

$\begin{alignat}{2} x_1 & = & 1 \\ x_2 & = & -2 \\ x_3 & = & -2 \end{alignat}$

Sistemi linearnih jednačina spadaju među najstarije matematičke probleme, i imaju mnoge primene, kao što su obrada digitalnih signala, procene, predviđanje, kao i linearno programiranje, i aproksimacija nelinearnih problema u numeričkoj analizi. Postoji mnogo načina da se reši sistem linearnih jednačina. Međutim, među najefikasnijima su Gausov postupak i dekompozicija Čoleskog.

Uopšteno, sistem sa m linearnih jednačina i n nepoznatih se zapisuje na sledeći način

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

gde su $x_1,\ x_2,...,x_n$ nepoznate, a brojevi $a_{11},\ a_{12},...,\ a_{mn}$ su koeficijenti sistema. Stavljamo koeficijente u matricu na sledeć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\bold{x} = \bold{b}$

gde je A a m×n matrica, x je vektor kolona sa n članova, a b je vektor kolona sa m članova. Gaus-Žordanova eliminacija se primenjuje 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 sledeća tri slučaja (tačno jedan će biti tačan) za svaki dati sistem linearnih jednačina:

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

Sistem oblika

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

se naziva homogenim sistemom linearnih jednačina. Skup svih rešenja se naziva nula prostorom matrice A.

Posebno u svetlu obilja gorenavedenih primena, nekoliko efikasnijih alternativa Gaus-Žordanovoj eliminaciji je razvijeno za širok spektar specijalnih slučajeva. Mnogi od ovih poboljšanih algoritama su složenosti O(n²) (vidi: notacija velikog O). Neki od najuobičajenijih specijalnih slučajeva su:

• Za probleme oblika Ax = b, gde je A simetrična Teplicova matrica, može se koristiti Levinsonova rekurzija ili neka od njenih varijacija. Jedna od često okrišćenih varijacija je Šurova rekurzija, koja se koristi u obradi digitalnih signala.
• Za probleme oblika Ax = b, gde je A singularna matrica, ili gotovo singularna, matrica A se dekomponuje u proizvod tri matrica. Matrice sa leve i desne strane su levi i desni singularni vektori. Matrica u sredini je dijagonalna matrica i sadrži singularne vrednosti. Matrica tada može biti invertovanja prostom zamenom redosleda tri komponente, transponovanjem matrica singularnih vektora, i uzimanjem recipročne vrednosti dijagonalnih elemenata središnje matrice. Ako je bilo koja od singularnih vrednosti suviše blizu nule, i stoga blizu singularnosti, postavlja se na nulu.

Literatura

• Ayres, Frank, Schaum's Outline of Modern Abstract Algebra, McGraw-Hill; 1st edition (June 1, 1965). ISBN 0070026556.

Vidi još

• Gaus-Zajdelova metoda
• Kramerovo pravilo
• Metod zamene

Spoljašnje veze

• Onlajn linearni rešavač
• Sistem linearnih jednačina sa kalkulatorom
• Sistemi linearnih diferencijalnih jednačina
• ((fr)) Rešenje linearnih sistema