Numerické řešení rovnic

Numerické řešení rovnic a jejich soustav spočívá v přibližném určení kořenů rovnice nebo soustavy rovnic a používá se v případech, kdy je přesná metoda řešení neznámá nebo pracná.

Prohlášení o problému

Zvažte metody pro numerické řešení rovnic a soustav rovnic :

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

nebo

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

Numerické řešení úlohy lze provést jak přímo (stejnojmennými metodami ), tak pomocí optimalizačních metod , dovést problém do vhodné podoby. Poslední je věnována článku Gradientní metody .

Numerické metody řešení rovnic

Pojďme si ukázat, jak můžete vyřešit původní systém rovnic bez použití optimalizačních metod . Pokud je náš systém SLAE , je vhodné uchýlit se k metodám, jako je Gaussova metoda nebo Richardsonova metoda . Stále však budeme vycházet z předpokladu, že tvar funkce nám není znám, a použijeme některou z iteračních metod numerického řešení . Z široké škály z nich vybereme jednu z nejznámějších - Newtonovu metodu . Tato metoda je zase založena na principu mapování kontrakcí. Proto bude nejprve uvedena podstata toho druhého.

Kompresivní mapování

Definujme terminologii:

Říká se, že funkce provádí mapování kontrakce na 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}||$

Pak platí následující hlavní věta:

Banachova věta (princip kontrakčního zobrazení).
Pokudje mapování kontrakce na, pak:

\varphi

[a,\;b]

Rovnice má jeden kořen v ; $x=\varphi(x)$ $x^{*}$ $[a,\;b]$
Iterační sekvence konverguje k tomuto kořenu; $x_{i+1}=\varphi(x_i)$
Pro dalšího člena je to pravda . $x_{n}$ $||x_{n}-x^{*}||\leq {\frac {\alpha ^{n}||x_{1}-x_{0}||}{1-\alpha ))$

Z posledního bodu věty vyplývá, že rychlost konvergence jakékoli metody založené na kontrakčních zobrazeních je přinejmenším lineární.

Vysvětlíme si význam parametru pro případ jedné proměnné. Podle Lagrangeovy věty máme: $\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})

Z toho plyne, že . K tomu , aby metoda konvergovala , tedy stačí, že $\alpha \approx |\varphi '(\xi )|$ $\forall x\in [a,\;b]\quad |\varphi '(x)|\leq 1.$

Obecný algoritmus postupných aproximací

Rovnice je transformována na rovnici se stejným kořenem tvaru , kde je zobrazení kontrakce. $f(x)=0$ $x=\varphi(x)$ $\varphi(x)$
Nastavte počáteční aproximaci a přesnost $x_{0},\quad \varepsilon ,\quad i=0$
Vypočítá se další iterace $x_{i+1}=\varphi(x_i)$
- Pokud ano, vraťte se ke kroku 3. $||x_{i+1}-x_{i}||>\varepsilon$ $i=i+1$
- Jinak přestaň. $x=x_{i+1}$

V obecném případě operátorových rovnic se tato metoda nazývá metoda postupných aproximací nebo metoda jednoduché iterace . Rovnici však lze převést na mapování kontrakcí , které má stejný kořen, různými způsoby. To vede k řadě konkrétních metod, které mají jak lineární, tak vyšší míru konvergence. $f(x)=0$ $x=\varphi(x)$

S ohledem na SLAU

Zvažte systém:

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

Pro něj bude iterativní výpočet vypadat takto:

$\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}\\\vtečky \\b_{n}\end{array}}\right)$

Metoda bude konvergovat lineární rychlostí, pokud $\left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn }+1\end{array}}\right\|<1$

Dvojité svislé pruhy znamenají určitou maticovou normu .

Newtonova metoda (metoda tečen)

Jednorozměrný případ

Optimalizace transformace původní rovnice na mapování kontrakce umožňuje získat metodu s kvadratickou rychlostí konvergence. $f(x)=0$ $x=\varphi(x)$

Aby bylo mapování co nejefektivnější, je nutné, aby v bodě další iterace , . Budeme hledat řešení této rovnice ve tvaru , pak: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Využijme toho a získáme konečný vzorec pro : $f(x)=0$ $\alpha(x)$

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

S ohledem na to bude mít funkce kontrakce podobu:

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

Poté je algoritmus pro nalezení numerického řešení rovnice redukován na postup iterativního výpočtu: $f(x)=0$

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

Vícerozměrné pouzdro

Zobecněme získaný výsledek na vícerozměrný případ.

Vybereme-li si nějakou počáteční aproximaci , následná aproximace se nalézají řešením soustav rovnic: ${\textstyle {\vec {x}}^{[0]}}$ ${\vec {x}}^{[j+1]}$

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

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

Viz také

Literatura

Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Výpočtové metody pro inženýry. — M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numerické metody. - 8. vyd. - M . : Laboratoř základních znalostí, 2000.
Volkov E. A. Numerické metody. — M .: Fizmatlit, 2003.
Korshunov Yu.M., Korshunov Yu.M. Matematické základy kybernetiky. — M .: Energoatomizdat, 1972.
Kalitkin N. N. Numerické metody. — M .: Nauka, 1978.