Numerisk løsning af ligninger

Den numeriske løsning af ligninger og deres systemer består i en omtrentlig bestemmelse af rødderne til en ligning eller et ligningssystem og bruges i tilfælde, hvor den nøjagtige løsningsmetode er ukendt eller besværlig.

Udtalelse af problemet

Overvej metoder til numerisk løsning af ligninger og ligningssystemer :

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 numeriske løsning af problemet kan udføres både direkte (ved hjælp af metoderne af samme navn ) og ved hjælp af optimeringsmetoder , hvilket bringer problemet til den passende form. Den sidste er helliget artiklen Gradient Methods .

Numeriske metoder til løsning af ligninger

Lad os vise, hvordan du kan løse det originale ligningssystem uden at ty til optimeringsmetoder . Hvis vores system er et SLAE , er det tilrådeligt at ty til metoder som Gauss -metoden eller Richardson-metoden . Vi vil dog stadig gå ud fra den antagelse, at funktionens form er ukendt for os, og vi vil bruge en af de iterative metoder til numerisk løsning . Blandt den brede vifte af dem vil vi vælge en af de mest berømte - Newtons metode . Denne metode er til gengæld baseret på princippet om kontraktionskortlægning. Derfor vil essensen af sidstnævnte blive angivet først.

Komprimerende kortlægning

Lad os definere terminologien:

En funktion siges at udføre en sammentrækningsmapping 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}||$

Så gælder følgende hovedsætning:

Banachs sætning (princippet om sammentrækningskortlægning).
Hviser en sammentrækningskortlægning på, så:

\varphi

[a,\;b]

Ligningen har en enkelt rod i ; $x=\varphi(x)$ $x^{*}$ $[a,\;b]$
Den iterative sekvens konvergerer til denne rod; $x_{i+1}=\varphi(x_i)$
For det næste medlem er sandt . $x_{n}$ $||x_{n}-x^{*}||\leq {\frac {\alpha ^{n}||x_{1}-x_{0}||}{1-\alpha ))$

Det følger af det sidste punkt i sætningen, at konvergenshastigheden for enhver metode baseret på kontraktionsafbildninger mindst er lineær.

Lad os forklare betydningen af parameteren for tilfældet med én variabel. Ifølge Lagrange-sætningen 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})

Derfor følger det . For at metoden kan konvergere , er det således tilstrækkeligt at $\alpha \approx |\varphi '(\xi )|$ $\forall x\in [a,\;b]\quad |\varphi '(x)|\leq 1.$

Generel algoritme for successive tilnærmelser

Ligningen omdannes til en ligning med samme rod af formen , hvor er en sammentrækningsmapping. $f(x)=0$ $x=\varphi(x)$ $\varphi(x)$
Indstil indledende tilnærmelse og nøjagtighed $x_{0},\quad \varepsilon ,\quad i=0$
Den næste iteration beregnes $x_{i+1}=\varphi(x_i)$
- Hvis , så vend tilbage til trin 3. $||x_{i+1}-x_{i}||>\varepsilon$ $i=i+1$
- Ellers stop. $x=x_{i+1}$

Som anvendt på det generelle tilfælde af operatorligninger, kaldes denne metode metoden med successive tilnærmelser eller metoden til simpel iteration . Ligningen kan dog transformeres til kontraktionsafbildningen , som har samme rod, på forskellige måder. Dette giver anledning til en række særlige metoder, der har både lineære og højere konvergenshastigheder. $f(x)=0$ $x=\varphi(x)$

Med hensyn til SLAU

Overvej 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.$

For det vil den iterative beregning se sådan ud:

$\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 vil konvergere med en lineær hastighed if $\left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn }+1\end{array}}\right\|<1$

Dobbelte lodrette streger betyder en eller anden matrixnorm .

Newtons metode (metode for tangenter)

Endimensionel kasus

Optimering af transformationen af den oprindelige ligning til en sammentrækningskortlægning gør det muligt at opnå en metode med en kvadratisk konvergenshastighed. $f(x)=0$ $x=\varphi(x)$

For at kortlægningen skal være mest effektiv, er det nødvendigt, at ved næste iteration , . Vi vil lede efter en løsning på denne ligning i formen , så: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Lad os bruge det faktum, at , og få den endelige formel for : $f(x)=0$ $\alfa(x)$

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

Med dette i tankerne vil sammentrækningsfunktionen have formen:

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

Derefter reduceres algoritmen til at finde en numerisk løsning til ligningen til en iterativ beregningsprocedure: $f(x)=0$

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

Multidimensional sag

Lad os generalisere det opnåede resultat til det multidimensionelle tilfælde.

Ved at vælge en indledende tilnærmelse , findes successive tilnærmelser ved at løse ligningssystemer: ${\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

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

Se også

Litteratur

Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Beregningsmetoder for ingeniører. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeriske metoder. - 8. udg. - M . : Laboratoriet for grundlæggende viden, 2000.
Volkov E. A. Numeriske metoder. — M .: Fizmatlit, 2003.
Korshunov Yu. M., Korshunov Yu. M. Matematiske grundlag for kybernetik. — M .: Energoatomizdat, 1972.
Kalitkin N. N. Numeriske metoder. — M .: Nauka, 1978.