Sistem linearnih jednačina

Iz Vikipedije, slobodne enciklopedije
Idi na: navigaciju, pretragu
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

Standardni problem je da se utvrdi da li postoji skup vrednosti za nepoznate , 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:

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

gde su nepoznate, a brojevi su koeficijenti sistema. Stavljamo koeficijente u matricu na sledeći način:

Ako predstavimo svaku matricu slovom, ovo postaje

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

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]