Sistem linearnih jednačina

Iz Vikipedije, slobodne enciklopedije
Skoči na: navigacija, pretraga
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(n2) (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[uredi]

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

Vidi još[uredi]

Spoljašnje veze[uredi]