Sistem linearnih jednačina

Sa Wikipedije, slobodne enciklopedije
Idi na: navigacija, traži
Question book-new.svg Ovaj članak ili neka od njegovih sekcija nije dovoljno potkrijepljena izvorima (literatura, web stranice ili drugi izvori).
Sporne rečenice i navodi bi mogli, ukoliko se pravilno ne označe validnim izvorima, biti obrisani i uklonjeni. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci, te nakon toga možete ukloniti ovaj šablon.
Gnome-emblem-important.svg Na ovoj stranici su konstatovane greške u izvornom kodu koje moguće dovode do nepoželjnih rezultata.
Ispravite ove greške i zatim uklonite ovaj šablon. Ako ne znate kako da ispravite ove greške onda se obratite na čaršiji za pomoć.

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\bold{x} = \bold{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\bold{x} = \bold{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(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 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[uredi | uredi izvor]