Avslappning (iterativ metod)

Den här artikeln handlar om iterativa metoder för att lösa ekvationssystem. För annan användning, se Avslappning (disambiguation) .

I numerisk matematik är avslappningsmetoder iterativa metoder för att lösa ekvationssystem , inklusive olinjära system.

Avslappningsmetoder utvecklades för att lösa stora glesa linjära system , som uppstod som diskretiseringar av differentialekvationer med ändlig skillnad . De används också för att lösa linjära ekvationer för linjära minsta kvadraters problem och även för system med linjära olikheter, såsom de som uppstår i linjär programmering . De har också utvecklats för att lösa icke-linjära ekvationssystem.

Avslappningsmetoder är viktiga särskilt i lösningen av linjära system som används för att modellera elliptiska partiella differentialekvationer, såsom Laplaces ekvation och dess generalisering, Poissons ekvation . Dessa ekvationer beskriver gränsvärdeproblem , där lösningsfunktionens värden specificeras på gränsen för en domän; problemet är att beräkna en lösning även på dess inre. Relaxationsmetoder används för att lösa de linjära ekvationer som är resultatet av en diskretisering av differentialekvationen, till exempel genom ändliga skillnader.

Iterativ avslappning av lösningar kallas vanligtvis utjämning eftersom det med vissa ekvationer, såsom Laplaces ekvation , liknar upprepad applicering av ett lokalt utjämningsfilter på lösningsvektorn. Dessa ska inte förväxlas med avslappningsmetoder i matematisk optimering , som approximerar ett svårt problem med ett enklare problem vars "avslappnade" lösning ger information om lösningen av det ursprungliga problemet.

Modellproblem av potentiell teori

Huvudartikel: Diskret Poisson-ekvation

När φ är en jämn realvärderad funktion på de reella talen, kan dess andraderivata approximeras med:

${\frac {d^{2}\varphi (x)}{{dx}^{2}}}={\frac {\varphi (x{-}h)-2\varphi (x)+ \varphi (x{+}h)}{h^{2}}}\,+\,{\mathcal {O}}(h^{2})\,.$

Att använda detta i båda dimensionerna för en funktion φ av två argument i punkten ( x , y ), och lösa för φ( x , y ), resulterar i:

$\varphi (x,y)={\tfrac {1}{4}}\left(\varphi (x{+}h,y)+\varphi (x,y{+}h)+\varphi (x{-}h,y)+\varphi (x,y{-}h)\,-\,h^{2}{\nabla }^{2}\varphi (x,y)\right)\ ,+\,{\mathcal {O}}(h^{4})\,.$

För att approximera lösningen av Poissons ekvation:

${\nabla }^{2}\varphi =f\,$

numeriskt på ett tvådimensionellt rutnät med rutnätsavstånd h , tilldelar relaxationsmetoden de givna värdena för funktion φ till rutnätspunkterna nära gränsen och godtyckliga värden till de inre rutnätspunkterna, och utför sedan tilldelningen φ := φ* upprepade gånger på de inre punkterna, där φ* definieras av:

$\varphi ^{*}(x,y)={\tfrac {1}{4}}\left(\varphi (x{+}h,y)+\varphi ( x,y{+}h)+\varphi (x{-}h,y)+\varphi (x,y{-}h)\,-\,h^{2}f(x,y)\right )\,,$

tills konvergens.

Metoden är lätt att generalisera till andra antal dimensioner.

Konvergens och acceleration

Även om metoden konvergerar under allmänna förhållanden, gör den vanligtvis långsammare framsteg än konkurrerande metoder. Ändå förblir studiet av avslappningsmetoder en central del av linjär algebra, eftersom transformationerna av avslappningsteorin ger utmärkta förberedelser för nya metoder. Ja, valet av förkonditioneringsmedel är ofta viktigare än valet av iterativ metod.

Multigrid-metoder kan användas för att accelerera metoderna. Man kan först beräkna en approximation på ett grövre rutnät – vanligtvis det dubbla avståndet 2 timmar – och använda den lösningen med interpolerade värden för de andra rutnätspunkterna som den initiala tilldelningen. Detta kan då också göras rekursivt för den grövre beräkningen.

Se även

• I linjära system är de två huvudklasserna av avslappningsmetoder stationära iterativa metoder och de mer allmänna Krylov-underrumsmetoderna .
• Jacobimetoden är en enkel avslappningsmetod .
• Gauss -Seidel-metoden är en förbättring av Jacobi-metoden.
• Successiv överavslappning kan tillämpas på endera av Jacobi- och Gauss-Seidel-metoderna för att påskynda konvergensen.
• Multigrid metoder

Anteckningar

•   Abraham Berman, Robert J. Plemmons, Nonegative Matrices in the Mathematical Sciences , 1994, SIAM. ISBN 0-89871-321-8 .
•    Ortega, JM; Rheinboldt, VM (2000). Iterativ lösning av olinjära ekvationer i flera variabler . Klassiker i tillämpad matematik. Vol. 30 (Reprint of the 1970 Academic Press ed.). Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). s. xxvi+572. ISBN 0-89871-461-3 . MR 1744713 .
•   Tryck, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Avsnitt 18.3. Avslappningsmetoder" . Numeriska recept: The Art of Scientific Computing (3:e upplagan). New York: Cambridge University Press. ISBN 978-0-521-88068-8 .
• Yousef Saad , Iterative Methods for Sparse Linear Systems , 1:a upplagan, PWS, 1996.
• Richard S. Varga 2002 Matrix Iterative Analysis , andra upplagan. (av 1962 Prentice Hall-upplagan), Springer-Verlag.
• David M. Young, Jr. Iterative Solution of Large Linear Systems , Academic Press, 1971. (omtryckt av Dover, 2003)

Vidare läsning

• Southwell, RV (1940) Avslappningsmetoder i ingenjörsvetenskap . Oxford University Press, Oxford.
• Southwell, RV (1946) Avslappningsmetoder i teoretisk fysik . Oxford University Press, Oxford.
•   John. D. Jackson (1999). Klassisk elektrodynamik . New Jersey: Wiley. ISBN 0-471-30932-X .
• MNO Sadiku (1992). Numeriska tekniker inom elektromagnetik . Boca Raton: CRC Pres.
• P.-B. Zhou (1993). Numerisk analys av elektromagnetiska fält . New York: Springer.