Lineaarvõrrandisüsteem

Lineaarvõrrandisüsteem on lineaaralgebras lineaarvõrrandite komplekt, näiteks

3x₁ + 2x₂ − x₃ = 1

2x₁ − 2x₂ + 4x₃ = −2

−x₁ + ½x₂ − x₃ = 0.

Selle võrrandisüsteemi lahendamine seisneb muutujate x₁, x₂ ja x₃ väärtuste selliste komplektide leidmises, mis rahuldavad kõiki kolme võrrandit korraga.

Lineaarvõrrandisüsteemi lahendamine on üks vanemaid probleeme matemaatikas. Sellel on palju rakendusi. Lineaarvõrrandite süsteemide efektiivsed meetodid on Gaussi meetod ja Cholesky lahutus.

Üldjuhul võib n muutujaga m lineaarvõrrandi süsteemi esitada kujul

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = b₂

a_m1x₁ + a_m2x₂ + … + a_mnx_n = b_m,

kus x₁, ... ,x_n on tundmatud ja arvud (üldisemalt skalaarid) a_ij on süsteemi koefitsiendid. Koefitsiendid esitame maatriksina: $A=\begin{pmatrix} 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{pmatrix}.$

Võrrandisüsteemi võib esitada ka kujul

Ax = b,

kus A on ülaltoodud m×n-maatriks, x on n liikmega veeruvektor ja b on m liikmega veeruvektor. Gaussi meetod on rakendatav kõikide sellise kujuga süsteemide puhul, ka siis, kui koefitsiendid kuuluvad suvalisse korpusesse.

Kui korpus, millesse koefitsiendid kuuluvad, on lõpmatu (näiteks reaalarvude korpus või kompleksarvude korpus), siis iga antud lineaarvõrrandite süsteemi korral on võimalikud kolm juhtu:

süsteemil puuduvad lahendid
süsteemil on üksainus lahend
süsteemil on lõpmatu palju lahendeid.

Süsteemi kujuga

Ax = 0

nimetatakse homogeenseks lineaarvõrrandisüsteemiks. Homogeense süsteemi kõikide lahendite hulk on alati vektorruumi Fⁿ lineaarne alamruum, kus F on koefitsientide korpus.

Eriti ülalnimetatud rakenduste jaoks on erijuhtude puhuks välja töötatud Gaussi meetodist efektiivsemaid meetodeid. Paljudel neist on keerukus O(n²). Mainime tuntumaid:

Kui ülesandel on kuju Ax = b, kus A on sümmeetriline Toeplitzi maatriks, siis saab kasutada Levinson rekursiooni või mõnda selle tuletistest. Üks Levinsoni-laadne tuletis on Schuri rekursioon, mida kasutatakse sageli digitaalses signaalitöötluses.
Kui ülesandel on kuju Ax = b, kus A on singulaarmaatriks või peaaegu singulaarne maatriks, siis lahutatakse maatriks A kolme maatriksi korrutiseks, kasutades singulaarväärtuslahutust.