Egyenletek numerikus megoldása

Az egyenletek és rendszereik numerikus megoldása egy egyenlet vagy egyenletrendszer gyökereinek közelítő meghatározásából áll, és olyan esetekben használatos, amikor a pontos megoldási módszer ismeretlen vagy munkaigényes.

A probléma leírása

Fontolja meg az egyenletek és egyenletrendszerek numerikus megoldásának módszereit :

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

vagy

$\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{tömb}}\jobbra.$

A feladat numerikus megoldása egyaránt végrehajtható közvetlenül ( azonos nevű metódusokkal ), és optimalizálási módszerekkel , a feladat megfelelő formába hozásával. Az utolsót a Gradiens módszerek című cikknek szenteljük .

Numerikus módszerek egyenletek megoldására

Mutassuk meg, hogyan oldhatja meg az eredeti egyenletrendszert optimalizálási módszerek alkalmazása nélkül . Ha a rendszerünk SLAE , akkor tanácsos olyan módszereket használni , mint a Gauss módszer vagy a Richardson módszer . Azonban továbbra is abból a feltételezésből indulunk ki, hogy a függvény alakja számunkra ismeretlen, és a numerikus megoldás iteratív módszereinek egyikét fogjuk alkalmazni . A sokféleség közül az egyik leghíresebbet, a Newton-módszert választjuk . Ez a módszer pedig a kontrakciós térképezés elvén alapul. Ezért először az utóbbi lényegét mondjuk el.

Tömörítő leképezés

Határozzuk meg a terminológiát:

Egy függvényről azt mondják, hogy kontrakciós leképezést hajt végre az ifon $\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}||$

Ekkor teljesül a következő főtétel:

Banach tétele (kontrakciós leképezések elve).
Haegy összehúzódási leképezés van, akkor:

\varphi

[a,\;b]

Az egyenletnek egyetlen gyöke van ; $x=\varphi(x)$ $x^{*}$ $[a,\;b]$
Az iteratív sorozat ehhez a gyökhöz konvergál; $x_{i+1}=\varphi(x_i)$
A következő tag igaz . $x_{n}$ $||x_{n}-x^{*}||\leq {\frac {\alpha ^{n}||x_{1}-x_{0}||}{1-\alpha ))$

A tétel utolsó pontjából következik, hogy bármely kontrakciós leképezésen alapuló módszer konvergenciája legalább lineáris.

Magyarázzuk meg a paraméter jelentését egy változó esetére. A Lagrange-tétel szerint a következőket kapjuk: $\alpha$

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

Ebből következik, hogy . Így ahhoz, hogy a módszer konvergáljon , elegendő az $\alpha \approx |\varphi '(\xi )|$ $\forall x\in [a,\;b]\quad |\varphi '(x)|\leq 1.$

Az egymást követő közelítések általános algoritmusa

Az egyenletet olyan egyenletté alakítjuk, amelynek gyöke az alaknak megegyezik , ahol egy kontrakciós leképezés. $f(x)=0$ $x=\varphi(x)$ $\varphi(x)$
Állítsa be a kezdeti közelítést és pontosságot $x_{0},\quad \varepsilon ,\quad i=0$
A következő iteráció kerül kiszámításra $x_{i+1}=\varphi(x_i)$
- Ha , akkor térjen vissza a 3. lépéshez. $||x_{i+1}-x_{i}||>\varepsilon$ $i=i+1$
- Ellenkező esetben álljon meg. $x=x_{i+1}$

Az operátoregyenletek általános esetére alkalmazva ezt a módszert az egymást követő közelítések módszerének vagy az egyszerű iteráció módszerének nevezik . Az egyenlet azonban különböző módon transzformálható a kontrakciós leképezésre , amelynek ugyanaz a gyöke. Ez számos olyan speciális módszert eredményez, amelyek lineáris és magasabb konvergencia rátákkal rendelkeznek. $f(x)=0$ $x=\varphi(x)$

SLAU tekintetében

Fontolja meg a rendszert:

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

Ehhez az iteratív számítás így fog kinézni:

$\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}&\lpontok &a_{1n}\\a_{21}&a_{22}+1&\lpontok &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)$

A módszer lineáris sebességgel fog konvergálni, ha $\left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\lponts &a_{nn }+1\end{tömb}}\jobbra\|<1$

A dupla függőleges sávok valamilyen mátrixnormát jelentenek .

Newton- módszer (az érintők módszere)

Egydimenziós tok

Az eredeti egyenlet kontrakciós leképezéssé való transzformációjának optimalizálása lehetővé teszi, hogy egy négyzetes konvergenciasebességű módszert kapjunk. $f(x)=0$ $x=\varphi(x)$

Ahhoz, hogy a leképezés a leghatékonyabb legyen, szükséges, hogy a következő iteráció pontján , . Ennek az egyenletnek a megoldását keressük a következő formában : $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Használjuk azt a tényt, hogy , és kapjuk meg a végső képletet : $f(x)=0$ $\alpha(x)$

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

Ezt szem előtt tartva az összehúzódási függvény a következő formában lesz:

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

Ezután az egyenlet numerikus megoldásának megtalálására szolgáló algoritmus egy iteratív számítási eljárásra redukálódik: $f(x)=0$

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

Többdimenziós eset

A kapott eredményt általánosítsuk a többdimenziós esetre.

Valamilyen kezdeti közelítést választva az egymást követő közelítéseket egyenletrendszerek megoldásával találjuk meg: ${\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

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

Lásd még

Irodalom

Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Számítási módszerek mérnökök számára. - M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numerikus módszerek. - 8. kiadás - M . : Alapismeretek Laboratóriuma, 2000.
Volkov E. A. Numerikus módszerek. — M. : Fizmatlit, 2003.
Korshunov Yu. M., Korshunov Yu. M. A kibernetika matematikai alapjai. - M .: Energoatomizdat, 1972.
Kalitkin N. N. Numerikus módszerek. - M .: Nauka, 1978.