Numerisk lösning av ekvationer

Den numeriska lösningen av ekvationer och deras system består i en ungefärlig bestämning av rötterna till en ekvation eller ett ekvationssystem och används i de fall där den exakta lösningsmetoden är okänd eller mödosam.

Förklaring av problemet

Överväg metoder för att numeriskt lösa ekvationer och ekvationssystem :

f(x_{1},x_{2},\ldots ,x_{n})=0

eller

$\left\{{\begin{array}{lcr}f_{1}(x_{1},x_{2},\ldots ,x_{n})&=&0\\\ldots &&\\f_ {n}(x_{1},x_{2},\ldots,x_{n})&=&0\end{array}}\right.$

Den numeriska lösningen av problemet kan utföras både direkt (med metoderna med samma namn ) och med hjälp av optimeringsmetoder , vilket bringar problemet till lämplig form. Den sista ägnas åt artikeln Gradient Methods .

Numeriska metoder för att lösa ekvationer

Låt oss visa hur du kan lösa det ursprungliga ekvationssystemet utan att använda optimeringsmetoder . Om vårt system är ett SLAE , är det tillrådligt att tillgripa metoder som Gauss- metoden eller Richardson-metoden . Men vi kommer fortfarande att utgå från antagandet att formen av funktionen är okänd för oss, och vi kommer att använda en av de iterativa metoderna för numerisk lösning . Bland det stora utbudet av dessa kommer vi att välja en av de mest kända - Newtons metod . Denna metod bygger i sin tur på principen om kontraktionskartläggning. Därför kommer essensen av det senare att anges först.

Komprimerande mappning

Låt oss definiera terminologin:

En funktion sägs utföra en kontraktionsmappning på if $\varphi$ $[a,\;b]$

$\forall x\in [a,\;b]:\varphi (x)\in [a,\;b]$
$\exists \alpha <1:\forall x_{1},x_{2}\in [a,\;b]\quad ||\varphi (x_{1})-\varphi (x_{2} )||\leq \alpha ||x_{1}-x_{2}||$

Då gäller följande huvudsats:

Banachs sats (principen för sammandragningsavbildningar).
Omär en sammandragningsmappning på, då:

\varphi

[a,\;b]

Ekvationen har en enda rot i ; $x=\varphi(x)$ $x^{*}$ $[a,\;b]$
Den iterativa sekvensen konvergerar till denna rot; $x_{i+1}=\varphi(x_i)$
För nästa medlem är sant . $x_{n}$ $||x_{n}-x^{*}||\leq {\frac {\alpha ^{n}||x_{1}-x_{0}||}{1-\alpha ))$

Det följer av den sista punkten i satsen att konvergenshastigheten för varje metod baserad på kontraktionsavbildningar är åtminstone linjär.

Låt oss förklara betydelsen av parametern för fallet med en variabel. Enligt Lagrangesatsen har vi: $\alfa$

\varphi (x)\in C^{1}[a,\;b].\quad \forall x_{1},x_{2}\in (a,\;b),\quad x_{ 1}<x_{2}\quad \exists \xi \in (x_{1},\;x_{2}):\quad \varphi '(\xi )(x_{2}-x_{1})= \varphi (x_{2})-\varphi (x_{1})

Därav följer att . För att metoden ska konvergera är det alltså tillräckligt att $\alpha \approx |\varphi '(\xi )|$ $\forall x\in [a,\;b]\quad |\varphi '(x)|\leq 1.$

Allmän algoritm för successiva approximationer

Ekvationen omvandlas till en ekvation med samma rot av formen , där är en sammandragningsmappning. $f(x)=0$ $x=\varphi(x)$ $\varphi(x)$
Ställ in initial approximation och noggrannhet $x_{0},\quad \varepsilon ,\quad i=0$
Nästa iteration beräknas $x_{i+1}=\varphi(x_i)$
- Om , gå tillbaka till steg 3. $||x_{i+1}-x_{i}||>\varepsilon$ $i=i+1$
- Annars sluta. $x=x_{i+1}$

Som tillämpat på det allmänna fallet med operatorekvationer kallas denna metod metoden för successiva approximationer eller metoden för enkel iteration . Ekvationen kan dock transformeras till kontraktionsmappningen , som har samma rot, på olika sätt. Detta ger upphov till ett antal särskilda metoder som har både linjära och högre konvergenshastigheter. $f(x)=0$ $x=\varphi(x)$

När det gäller SLAU

Tänk på systemet:

$\left\{{\begin{array}{ccc}a_{11}x_{1}+\ldots +a_{1n}x_{n}&=&b_{1}\\\ldots &&\\a_ {n1}x_{1}+\ldots +a_{nn}x_{n}&=&b_{n}\end{array}}\right.$

För det kommer den iterativa beräkningen att se ut så här:

$\left({\begin{array}{c}x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i+1} =\left({\begin{array}{cccc}a_{11}+1&a_{12}&\ldots &a_{1n}\\a_{21}&a_{22}+1&\ldots &a_{2n}\\\ vdots &\vdots &\ddots &\vdots \\a_{n1}&a_{n2}&\ldots &a_{nn}+1\end{array}}\right)\left({\begin{array}{c} x_{1}\\x_{2}\\\vdots \\x_{n}\end{array}}\right)^{i}-\left({\begin{array}{c}b_{1} \\b_{2}\\\vdots \\b_{n}\end{array}}\right)$

Metoden kommer att konvergera med en linjär hastighet if $\left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn }+1\end{array}}\right\|<1$

Dubbla vertikala streck betyder någon matrisnorm .

Newtons metod (metod för tangenter)

Endimensionellt fall

Genom att optimera omvandlingen av den ursprungliga ekvationen till en sammandragningsmappning kan man erhålla en metod med en kvadratisk konvergenshastighet. $f(x)=0$ $x=\varphi(x)$

För att mappningen ska bli mest effektiv är det nödvändigt att vid punkten för nästa iteration . Vi kommer att leta efter en lösning på denna ekvation i formen , sedan: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

\varphi '(x^{*})=1+\alpha '(x^{*})f(x^{*})+\alpha (x^{*})f'(x^{ *})=0

Låt oss använda det faktum att , och få den slutliga formeln för : $f(x)=0$ $\alfa(x)$

\alpha (x)=-{\frac {1}{f'(x)))

Med detta i åtanke kommer kontraktionsfunktionen att ha formen:

\varphi (x)=x-{\frac {f(x)}{f'(x)))

Sedan reduceras algoritmen för att hitta en numerisk lösning till ekvationen till en iterativ beräkningsprocedur: $f(x)=0$

x_{i+1}=x_{i}-{\frac {f(x_{i})}{f'(x_{i))}}

Flerdimensionellt fall

Låt oss generalisera det erhållna resultatet till det flerdimensionella fallet.

Genom att välja någon initial approximation , hittas successiva approximationer genom att lösa ekvationssystem: ${\textstyle {\vec {x}}^{[0]}}$ ${\vec {x}}^{[j+1]}$

f_{i}+\sum _{k=1}^{n}{\frac {\partial f_{i}}{\partial x_{k}}}(x_{k}^{[j+ 1 ]}-x_{k}^{[j]})=0,\quad i=1,2,\ldots ,n

var . $x^{[j]}=\left(x_{1}^{[j]}\ldots x_{k}^{[j]}\ldots x_{n}^{[j]}\right ),\quad j=0,1,2,\ldots$

Se även

Litteratur

Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Beräkningsmetoder för ingenjörer. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriska metoder. - 8:e uppl. - M . : Laboratory of Basic Knowledge, 2000.
Volkov E. A. Numeriska metoder. — M .: Fizmatlit, 2003.
Korshunov Yu. M., Korshunov Yu. M. Matematiska grunder för cybernetik. — M .: Energoatomizdat, 1972.
Kalitkin N. N. Numeriska metoder. — M .: Nauka, 1978.