Beregningsmæssig stabilitet

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 14. februar 2022; checks kræver 2 redigeringer .

I beregningsmatematik er beregningsmæssig robusthed normalt en ønskelig egenskab ved numeriske algoritmer.

Den nøjagtige definition af bæredygtighed afhænger af konteksten. En af dem er numerisk lineær algebra, den anden er algoritmer til løsning af almindelige ligninger og partielle differentialligninger ved hjælp af diskret tilnærmelse.

I numerisk lineær algebra er hovedproblemet ustabilitet forårsaget af nærhed til forskellige funktioner, såsom meget små eller næsten identiske egenværdier.

På den anden side er problemet i numeriske algoritmer til differentialligninger stigningen i afrundingsfejl og/eller initialt små udsving i inputdataene, hvilket kan føre til en væsentlig afvigelse af det endelige svar fra den nøjagtige løsning.

Nogle numeriske algoritmer kan dæmpe små afvigelser (fejl) i inputdataene; andre kan øge sådanne fejl. Beregninger, der kan påvises ikke at øge tilnærmelsesfejl, siges at være beregningsmæssigt robuste. Et af de almindelige problemer i numerisk analyse er at forsøge at vælge robuste algoritmer, det vil sige ikke at give et meget anderledes resultat med en meget lille ændring i inputdata.

Det modsatte er ustabilitet. Algoritmen indeholder som regel en tilnærmelsesmetode, og i nogle tilfælde kan det bevises, at algoritmen vil tilnærme den korrekte løsning i en eller anden grænse (ved at bruge faktiske reelle tal , ikke flydende kommatal ).

Selv i dette tilfælde er der ingen garanti for, at det vil konvergere til den korrekte løsning, fordi flydende-komma-afrunding eller trunkeringsfejl kan stige snarere end falde, hvilket fører til en eksponentiel stigning i afvigelsen fra den nøjagtige løsning. [en]

Stabilitet i numeriske metoder for lineær algebra

Der er forskellige måder at formalisere begrebet bæredygtighed på. Følgende definitioner af direkte, omvendt og blandet stabilitet bruges ofte i numerisk lineær algebra.

Betragt et problem løst af en numerisk algoritme som en funktion f , der kortlægger data x til løsning y . Resultatet af algoritmen, siger y* , vil normalt afvige fra den "sande" løsning y . De vigtigste årsager til fejlen er afrundingsfejl og trunkeringsfejl . Algoritmens direkte fejl er forskellen mellem resultatet og løsningen; i dette tilfælde Δ y = y * − y . Den omvendte fejl er den mindste Δ x således at f  ( x + Δ x ) = y * ; med andre ord fortæller baglænsfejlen os, hvilket problem algoritmen faktisk løste. Frem- og bagudfejlene er relateret til betingelsesnummeret : fremadrettet fejl er ikke større i størrelsesorden end betingelsestallet gange den omvendte fejl.

I mange tilfælde er det mere naturligt[ afklare ] overveje relativ fejl

i stedet for absolut Δx .

Selvfølgelig er "lille" et relativt begreb, og dets definition vil afhænge af konteksten. Ofte ønsker vi, at fejlen skal have samme størrelsesorden, eller måske flere størrelsesordener større end afrundingsenheden .

Den sædvanlige definition af beregningsmæssig robusthed bruger et mere generelt begreb kaldet blandet robusthed , som kombinerer fremadrettet fejl og baglæns fejl. En algoritme i denne forstand er stabil, hvis den tilnærmelsesvis løser et naboproblem, det vil sige, hvis der eksisterer Δ x således, at både Δ x er lille og f  ( x + Δ x ) − y * er lille. Derfor er en baglæns stabil algoritme altid stabil.

Dette betyder, at en algoritme er fremadstabil, hvis den har en fremadstorhedsfejl svarende til baglænsfejlen for en stabil algoritme.

Stabilitet af differensskemaer af differentialligninger

Ovenstående definitioner er især relevante i situationer, hvor trunkeringsfejl ikke er vigtige. I andre sammenhænge, ​​såsom ved løsning af differentialligninger, bruges en anden definition af numerisk stabilitet.

I numeriske almindelige differentialligninger er der forskellige begreber om numerisk stabilitet, for eksempel A-stabilitet . Når man løser en stiv ligning , er det vigtigt at bruge en stabil metode.

En anden definition bruges i numeriske partielle differentialligninger. En algoritme til løsning af en lineær evolutionær partiel differentialligning er stabil, hvis den samlede variation af den numeriske løsning på et fast tidspunkt forbliver begrænset, når trinstørrelsen nærmer sig nul. Lax' ækvivalenssætning siger, at en algoritme konvergerer, hvis den er konsistent og stabil (i denne forstand). Stabilitet opnås nogle gange ved at inkludere numerisk diffusion . Numerisk diffusion er et matematisk udtryk, der sikrer, at afrunding og andre fejl i beregninger forplanter sig og ikke lægger op til en "eksplosion" af beregninger. Neumann stabilitetsanalyse er en udbredt procedure til at analysere stabiliteten af ​​endelige differensskemaer som anvendt på lineære partielle differentialligninger. Disse resultater gælder ikke for ikke-lineære partielle differentialligninger, hvor den generelle konsistente definition af stabilitet er kompliceret af mange egenskaber, der mangler i lineære ligninger.

Se også

Noter

  1. ↑ Giesela Engeln-Müllges. Numeriske algoritmer  med C ]  / Giesela Engeln-Müllges, Frank Uhlig. - 1. - Springer, 2. juli 1996. - S. 10. - ISBN 978-3-540-60530-0 . Arkiveret 19. august 2020 på Wayback Machine

Litteratur