Rezolvarea numerică a ecuațiilor

Rezolvarea numerică a ecuațiilor și a sistemelor acestora constă într-o determinare aproximativă a rădăcinilor unei ecuații sau a unui sistem de ecuații și este utilizată în cazurile în care metoda de rezolvare exactă este necunoscută sau laborioasă.

Enunțul problemei

Luați în considerare metode pentru rezolvarea numerică a ecuațiilor și a sistemelor de ecuații :

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

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

Rezolvarea numerică a problemei poate fi efectuată atât direct (folosind metodele cu același nume ), cât și folosind metode de optimizare , aducând problema la forma corespunzătoare. Ultimul este dedicat articolului Gradient Methods .

Metode numerice pentru rezolvarea ecuațiilor

Să arătăm cum puteți rezolva sistemul original de ecuații fără a recurge la metode de optimizare . Dacă sistemul nostru este un SLAE , este indicat să apelăm la metode precum metoda Gauss sau metoda Richardson . Cu toate acestea, vom pleca în continuare de la presupunerea că forma funcției ne este necunoscută și vom folosi una dintre metodele iterative ale soluției numerice . Dintre marea varietate a acestora, vom alege una dintre cele mai faimoase - metoda lui Newton . Această metodă, la rândul său, se bazează pe principiul mapării contracției. Prin urmare, esența acestuia din urmă va fi enunțată mai întâi.

Maparea compresivă

Să definim terminologia:

Se spune că o funcție efectuează o mapare de contracție pe dacă $\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}||$

Atunci următoarea teoremă principală este valabilă:

Teorema lui Banach (principiul mapărilor de contracție).
Dacăeste o mapare de contracție pe, atunci:

\varphi

[a,\;b]

Ecuația are o singură rădăcină în ; $x=\varphi(x)$ $x^{*}$ $[a,\;b]$
Secvența iterativă converge către această rădăcină; $x_{i+1}=\varphi(x_i)$
Pentru următorul membru este adevărat . $x_{n}$ $||x_{n}-x^{*}||\leq {\frac {\alpha ^{n}||x_{1}-x_{0}||}{1-\alpha ))$

Din ultimul punct al teoremei rezultă că rata de convergență a oricărei metode bazate pe mapări de contracție este cel puțin liniară.

Să explicăm semnificația parametrului pentru cazul unei variabile. Conform teoremei Lagrange, avem: $\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})

De aici rezultă că . Astfel, pentru ca metoda să convergă , este suficient ca $\alpha \approx |\varphi '(\xi )|$ $\forall x\in [a,\;b]\quad |\varphi '(x)|\leq 1.$

Algoritm general al aproximărilor succesive

Ecuația este transformată într-o ecuație cu aceeași rădăcină a formei , unde este o mapare de contracție. $f(x)=0$ $x=\varphi(x)$ $\varphi(x)$
Setați aproximarea inițială și precizia $x_{0},\quad \varepsilon ,\quad i=0$
Următoarea iterație este calculată $x_{i+1}=\varphi(x_i)$
- Dacă , atunci reveniți la pasul 3. $||x_{i+1}-x_{i}||>\varepsilon$ $i=i+1$
- Altfel oprește-te. $x=x_{i+1}$

Așa cum este aplicată în cazul general al ecuațiilor operatorilor, această metodă se numește metoda aproximărilor succesive sau metoda iterației simple . Cu toate acestea, ecuația poate fi transformată în maparea contracției , care are aceeași rădăcină, în moduri diferite. Acest lucru dă naștere la o serie de metode particulare care au rate de convergență atât liniare, cât și mai mari. $f(x)=0$ $x=\varphi(x)$

În ceea ce privește SLAU

Luați în considerare sistemul:

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

Pentru aceasta, calculul iterativ va arăta astfel:

$\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)$

Metoda va converge la o rată liniară dacă $\left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn }+1\end{matrice}}\right\|<1$

Barele verticale duble înseamnă o normă de matrice .

Metoda lui Newton (metoda tangentelor)

Caz unidimensional

Optimizarea transformării ecuației originale într-o mapare de contracție permite obținerea unei metode cu o rată de convergență pătratică. $f(x)=0$ $x=\varphi(x)$

Pentru ca maparea să fie cât mai eficientă, este necesar ca în punctul următoarei iterații , . Vom căuta o soluție la această ecuație sub forma , apoi: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Să folosim faptul că , și să obținem formula finală pentru : $f(x)=0$ $\alpha(x)$

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

Având în vedere acest lucru, funcția de contracție va lua forma:

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

Apoi algoritmul pentru găsirea unei soluții numerice a ecuației este redus la o procedură de calcul iterativă: $f(x)=0$

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

Caz multidimensional

Să generalizăm rezultatul obţinut la cazul multidimensional.

Alegând o aproximare inițială , se găsesc aproximații succesive prin rezolvarea sistemelor de ecuații: ${\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

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

Vezi și

Literatură

Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Metode de calcul pentru ingineri. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Metode numerice. - Ed. a 8-a. - M . : Laboratorul de Cunoștințe de bază, 2000.
Volkov E. A. Metode numerice. — M. : Fizmatlit, 2003.
Korshunov Yu. M., Korshunov Yu. M. Fundamentele matematice ale ciberneticii. — M .: Energoatomizdat, 1972.
Kalitkin N. N. Metode numerice. — M .: Nauka, 1978.