2. Linjära ekvationssystem

Linjära ekvationssystem

Lös linjära system med LU-faktorisering, uppskatta beräkningsarbetet och avgör hur störningar i högerledet slår mot lösningen.

Översikt

Kärnan i linjära system

Gausselimination skrivs som en faktorisering i en undertriangulär och en övertriangulär faktor. Faktoriseringen görs en gång och kan sedan återanvändas för flera högerled.

$A=LU,\qquad Ly=b,\quad Ux=y$

Exempel

Metod och kontroll

Konditionstalet är den faktor som en relativ störning i högerledet som mest förstoras med. Ett stort konditionstal betyder att indata måste ha motsvarande fler säkra siffror.

$\frac{\|\Delta x\|}{\|x\|}\le\kappa(A)\,\frac{\|\Delta b\|}{\|b\|}$

Fördjupning

Vanliga fallgropar

Faktoriseringen kostar i storleksordningen kuben på antalet obekanta medan varje triangulär lösning bara kostar kvadraten, så det är faktoriseringen som ska återanvändas och inte upprepas. Ett illakonditionerat system ger dessutom ett svar som ser rimligt ut även när det saknar säkra siffror.

Formler i området

LU-faktorisering

A=LU,\qquad Ly=b,\quad Ux=y

Vad gör formeln?: Delar upp systemmatrisen i triangulära faktorer så att lösningen fås ur två billiga substitutioner.
När får den användas?: Faktoriseringen finns för en inverterbar matris, vid behov efter radbyten genom pivotering.

Beräkningskomplexitet för Gausseliminering

N\approx\frac{2n^{3}}{3},\qquad \frac{t(n_2)}{t(n_1)}\approx\left(\frac{n_2}{n_1}\right)^{3}

Vad gör formeln?: Arbetet växer med kuben på antalet obekanta, så en fördubblad problemstorlek kostar ungefär åtta gånger mer.
När får den användas?: Gäller en full matris utan särskild struktur, där n är antalet obekanta och n är stort.

Beräkningskomplexitet för triangulära system

N\approx n^{2},\qquad \frac{t(n_2)}{t(n_1)}\approx\left(\frac{n_2}{n_1}\right)^{2}

Vad gör formeln?: Substitution i ett triangulärt system kostar kvadratiskt, alltså en potens mindre än elimineringen.
När får den användas?: Systemet är redan triangulärt och löses med framåt- eller bakåtsubstitution.

Maxnorm för vektor och matris

\|x\|_\infty=\max_i|x_i|,\qquad \|A\|_\infty=\max_i\sum_{j}|a_{ij}|

Vad gör formeln?: Mäter storleken på en vektor som dess största komponent och på en matris som den största radsumman.
När får den användas?: Matrisnormen är den norm som induceras av vektorns maxnorm, alltså den största absoluta radsumman.

Konditionstal

\kappa(A)=\|A\|\,\|A^{-1}\|

Vad gör formeln?: Mäter hur känslig lösningen till ett linjärt system är för störningar i indata.
När får den användas?: A är inverterbar och samma norm används för båda faktorerna; konditionstalet är alltid minst ett.

Felförstärkning i linjära system

\frac{\|\Delta x\|}{\|x\|}\le\kappa(A)\,\frac{\|\Delta b\|}{\|b\|}

Vad gör formeln?: Begränsar det relativa felet i lösningen med konditionstalet gånger det relativa felet i högerledet.
När får den användas?: Störningen ligger i högerledet och systemmatrisen antas exakt; olikheten är en övre gräns, inte ett väntevärde.

Kan du använda linjära ekvationssystem?

Lös en riktig tentauppgift från SF1547 med ledtrådar och lösningsförslag. Inget konto behövs.

Prova en uppgift