1. Felanalys och beräkningskomplexitet

Felanalys och beräkningskomplexitet

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

Översikt

Kärnan i felanalys och beräkningskomplexitet

En numerisk metod ger alltid ett approximativt svar, så felets storlek är lika viktig som värdet självt. Noggrannhetsordningen säger hur snabbt felet krymper när steglängden halveras.

$E(h)\approx Ch^{p},\qquad \frac{E(h)}{E(h/2)}\approx 2^{p}$

Exempel

Metod och kontroll

Med tabellvärden för olika steglängder skattas felen som skillnaden mellan successiva approximationer, och kvoten mellan två sådana fel ger ordningen.

$E(h)\approx|F(h)-F(h/2)|,\qquad p\approx\log_{2}\!\left(\frac{E(h)}{E(h/2)}\right)$

Fördjupning

Vanliga fallgropar

Blanda inte ihop noggrannhetsordning med konvergensordning: den första beskriver hur felet beror på steglängden i en diskretisering, den andra hur felet i en iterationsföljd krymper från ett steg till nästa. Använd dessutom bara de mest noggranna tabellraderna, eftersom avrundningen i grova approximationer annars förstör kvoten.

Formler i området

Absolut och relativt fel

|\Delta x|=|\tilde{x}-x|,\qquad |\delta x|=\frac{|\tilde{x}-x|}{|x|}

Vad gör formeln?: Mäter felet i en approximation både i absoluta tal och i förhållande till storleken.
När får den användas?: Det exakta värdet betecknas x och approximationen x̃; det relativa felet kräver att x inte är noll.

Antal korrekta decimaler

|\tilde{x}-x|\le\tfrac{1}{2}\cdot 10^{-d}

Vad gör formeln?: Översätter en felgräns till hur många decimaler som kan anges med säkerhet.
När får den användas?: Gäller när felgränsen avser avrundning till d decimaler i det aktuella talet.

Noggrannhetsordning

E(h)\approx Ch^{p},\qquad \frac{E(h)}{E(h/2)}\approx 2^{p}

Vad gör formeln?: Beskriver hur snabbt diskretiseringsfelet krymper när steglängden halveras.
När får den användas?: Steglängden är så liten att den ledande feltermen dominerar, men inte så liten att avrundningsfel tar över.

Felskattning ur successiva approximationer

E(h)\approx|F(h)-F(h/2)|

Vad gör formeln?: Skattar felet i en approximation med skillnaden till nästa förfining, när det exakta värdet saknas.
När får den användas?: Kräver att metoden konvergerar och att den finare approximationen är klart noggrannare än den grövre.

Konvergensordning för en iteration

|e_{n+1}|\approx C|e_n|^{p},\qquad e_n=x_n-\alpha

Vad gör formeln?: Beskriver hur snabbt felet i en iterationsföljd minskar från ett steg till nästa.
När får den användas?: Gäller lokalt nära roten α och för tillräckligt stora iterationsnummer.

Kan du använda felanalys och beräkningskomplexitet?

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

Prova en uppgift