Numerisk stabilitet - Numerical stability

I det matematiske underfelt for numerisk analyse er numerisk stabilitet en generelt ønskelig egenskab ved numeriske algoritmer . Den præcise definition af stabilitet afhænger af konteksten. Den ene er numerisk lineær algebra, og den anden er algoritmer til løsning af almindelige og partielle differentialligninger ved diskret tilnærmelse.

I numerisk lineær algebra er hovedproblemet ustabilitet forårsaget af nærhed til singulariteter af forskellig art, såsom meget små eller næsten kolliderende egenværdier . På den anden side i numeriske algoritmer til differentialligninger er bekymringen væksten i afrundingsfejl og/eller små udsving i indledende data, som kan forårsage en stor afvigelse af det endelige svar fra den nøjagtige løsning.

Nogle numeriske algoritmer kan dæmpe de små udsving (fejl) i inputdataene; andre kan forstørre sådanne fejl. Beregninger, der kan bevises ikke at forstørre tilnærmelsesfejl, kaldes numerisk stabile . En af de almindelige opgaver for numerisk analyse er at prøve at vælge algoritmer, der er robuste  - det vil sige ikke giver et helt anderledes resultat for meget små ændringer i inputdataene.

Et modsat fænomen er ustabilitet . Typisk involverer en algoritme en tilnærmelsesvis metode, og i nogle tilfælde kunne man bevise, at algoritmen ville nærme sig den rigtige løsning i en eller anden grænse (ved brug af faktiske reelle tal, ikke flydende tal). Selv i dette tilfælde er der ingen garanti for, at den konvergerer til den korrekte løsning, fordi afrundings- eller afkortningsfejl ved flydende punkter kan forstørres i stedet for dæmpet, hvilket får afvigelsen fra den nøjagtige løsning til at vokse eksponentielt.

Stabilitet i numerisk lineær algebra

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

Diagram, der viser den fremadrettede fejl Δ y og den bagudrettede fejl Δ x , og deres relation til det nøjagtige løsningskort  f og den numeriske løsning  f *.

Betragt problemet, der skal løses af den numeriske algoritme som en funktion  f, der kortlægger data  x til løsningen  y . Resultatet af algoritmen, siger y *, vil normalt afvige fra den "sande" løsning  y . Hovedårsagerne til fejl er afrundingsfejl og afkortningsfejl . Den forreste fejl af algoritmen er forskellen mellem resultatet og opløsningen; i dette tilfælde er Δ y = y * - y . Den bagudrettede fejl er den mindste Δ x, således at f  ( x + Δ x ) = y * ; med andre ord, den tilbagestående fejl fortæller os, hvilket problem algoritmen faktisk løste. Forlæns og baglæns fejl hænger sammen med tilstandsnummeret : fremadrettede fejl er højst lige så store som betingelsestallet multipliceret med størrelsen af ​​den bagudrettede fejl.

I mange tilfælde er det mere naturligt at overveje den relative fejl

i stedet for den absolutte fejl Δ x .

Algoritmen siges at være bagudstabil, hvis den bagudrettede fejl er lille for alle input  x . Selvfølgelig er "lille" et relativt begreb, og dets definition vil afhænge af konteksten. Ofte ønsker vi, at fejlen skal være af samme rækkefølge som, eller måske kun et par størrelsesordener større end, enheden afrundes .

Blandet stabilitet kombinerer begreberne fremadgående fejl og bagudrettet fejl.

Den sædvanlige definition af numerisk stabilitet anvender et mere generelt begreb, kaldet blandet stabilitet , som kombinerer den fremadrettede fejl og den bagudrettede fejl. En algoritme er stabil i denne forstand, hvis den cirka løser et nærliggende problem, dvs. hvis der eksisterer en Δ x, så både Δ x er lille og f  ( x + Δ x ) - y * er lille. Derfor er en bagud stabil algoritme altid stabil.

En algoritme er fremadstabil, hvis dens fremadgående fejl divideret med problemets tilstandsnummer er lille. Det betyder, at en algoritme er fremadstabil, hvis den har en fremadrettet størrelsesfejl, der ligner en bagudstabil algoritme.

Stabilitet i numeriske differentialligninger

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

I numeriske almindelige differentialligninger findes forskellige begreber af numerisk stabilitet, for eksempel A-stabilitet . De er relateret til et eller andet koncept for stabilitet i den dynamiske systems forstand, ofte Lyapunov -stabilitet . Det er vigtigt at bruge en stabil metode, når man løser en stiv ligning .

Endnu en definition bruges i numeriske partielle differentialligninger . En algoritme til løsning af en lineær evolutionær delvis differentialligning er stabil, hvis den totale variation af den numeriske løsning på et bestemt tidspunkt forbliver afgrænset, når trinstørrelsen går til nul. Den Lax ækvivalens teorem , at en algoritme konvergerer hvis det er konsistent og stabil (i denne forstand). Stabilitet opnås undertiden ved at inkludere numerisk diffusion . Numerisk diffusion er et matematisk udtryk, der sikrer, at afrunding og andre fejl i beregningen bliver spredt ud og ikke summeres til at få beregningen til at "sprænge". Von Neumann stabilitetsanalyse er en almindeligt anvendt procedure til stabilitetsanalyse af endelige forskelsordninger, der anvendes på lineære partielle differentialligninger. Disse resultater gælder ikke for ikke -lineære PDE'er, hvor en generel, konsekvent definition af stabilitet kompliceres af mange egenskaber, der mangler i lineære ligninger.

Se også

Referencer