3. Linjära ekvationssystem

Linjära ekvationssystem

Gausseliminering och LU-faktorisering, konditionstal och felförstärkning samt hur beräkningsarbetet växer med antalet obekanta.

Översikt

Kärnan i linjära ekvationssystem

Gausseliminering delar upp systemmatrisen i en undertriangulär och en övertriangulär faktor, och sedan löses två triangulära system i följd.

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

Exempel

Metod och kontroll

Konditionstalet mäter hur mycket ett fel i högerledet kan förstoras i lösningen, och sätter därmed en gräns för hur många decimaler som är säkra.

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

Fördjupning

Vanliga fallgropar

Ett stort konditionstal betyder inte att beräkningen är fel, bara att indata måste vara noggrannare för samma säkerhet i svaret. Notera också att faktoriseringen är den dyra delen: när flera högerled ska lösas med samma matris återanvänds LU i stället för att eliminationen görs om.

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.

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.

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.

Hänger ihop med

Förkunskap

Felanalys och beräkningskomplexitetMät felet absolut och relativt, bestäm noggrannhets- och konvergensordning ur en tabell och bedöm hur arbetet växer med problemstorleken.

Kan du använda linjära ekvationssystem?

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

Prova en uppgift