Yhtälöiden numeerinen ratkaisu

Yhtälöiden ja niiden järjestelmien numeerinen ratkaisu koostuu yhtälön tai yhtälöjärjestelmän juurien likimääräisestä määrittämisestä ja sitä käytetään tapauksissa, joissa tarkka ratkaisumenetelmä on tuntematon tai työläs.

Ongelman selvitys

Harkitse menetelmiä yhtälöiden ja yhtälöjärjestelmien numeeriseen ratkaisemiseen :

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

tai

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

Tehtävän numeerinen ratkaisu voidaan suorittaa sekä suoraan ( samannimisellä menetelmällä ) että optimointimenetelmillä , jolloin ongelma saatetaan sopivaan muotoon. Viimeinen on omistettu artikkelille Gradient Methods .

Numeeriset menetelmät yhtälöiden ratkaisemiseksi

Näytämme, kuinka voit ratkaista alkuperäisen yhtälöjärjestelmän turvautumatta optimointimenetelmiin . Jos järjestelmämme on SLAE , on suositeltavaa turvautua menetelmiin, kuten Gaussin menetelmään tai Richardsonin menetelmään . Lähdemme kuitenkin edelleen oletukseen, että funktion muoto on meille tuntematon, ja käytämme yhtä iteratiivisista numeerisen ratkaisun menetelmistä . Niiden laajasta valikoimasta valitsemme yhden tunnetuimmista - Newtonin menetelmästä . Tämä menetelmä puolestaan perustuu supistumiskartoituksen periaatteeseen. Siksi jälkimmäisen olemus ilmaistaan ensin.

Pakkaava kartoitus

Määritellään terminologia:

Funktion sanotaan suorittavan supistumiskartoituksen jos $\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}||$

Sitten seuraava päälause pätee:

Banachin lause (supistusmappausten periaate).
Jossupistumiskartoitus on, niin:

\varphi

[a,\;b]

Yhtälöllä on yksi juuri ; $x=\varphi(x)$ $x^{*}$ $[a,\;b]$
Iteratiivinen sekvenssi konvergoi tähän juureen; $x_{i+1}=\varphi(x_i)$
Seuraavalle jäsenelle on totta . $x_{n}$ $||x_{n}-x^{*}||\leq {\frac {\alpha ^{n}||x_{1}-x_{0}||}{1-\alpha ))$

Lauseen viimeisestä kohdasta seuraa, että minkä tahansa supistumiskartoituksiin perustuvan menetelmän konvergenssinopeus on vähintään lineaarinen.

Selitetään parametrin merkitys yhden muuttujan tapauksessa. Lagrangen lauseen mukaan meillä on: $\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})

Tästä seuraa, että . Näin ollen menetelmän konvergoimiseksi riittää, että $\alpha \approx |\varphi '(\xi )|$ $\forall x\in [a,\;b]\quad |\varphi '(x)|\leq 1.$

Peräkkäisten approksimaatioiden yleinen algoritmi

Yhtälö muunnetaan yhtälöksi, jolla on sama muodon juuri , jossa on supistumiskuvaus. $f(x) = 0$ $x=\varphi(x)$ $\varphi(x)$
Aseta alkuperäinen likiarvo ja tarkkuus $x_{0},\quad \varepsilon ,\quad i=0$
Seuraava iteraatio lasketaan $x_{i+1}=\varphi(x_i)$
- Jos , palaa vaiheeseen 3. $||x_{i+1}-x_{i}||>\varepsilon$ $i=i+1$
- Muuten lopeta. $x=x_{i+1}$

Operaattoriyhtälöiden yleisessä tapauksessa tätä menetelmää kutsutaan peräkkäisten approksimaatioiden menetelmäksi tai yksinkertaisen iteroinnin menetelmäksi . Yhtälö voidaan kuitenkin muuntaa supistumismappaukseksi , jolla on sama juuri, eri tavoin. Tämä synnyttää useita erityisiä menetelmiä, joilla on sekä lineaariset että korkeammat konvergenssinopeudet. $f(x) = 0$ $x=\varphi(x)$

Mitä tulee SLAU:hun

Harkitse järjestelmää:

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

Sitä varten iteratiivinen laskenta näyttää tältä:

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

Menetelmä konvergoi lineaarisella nopeudella, jos $\left\|{\begin{array} }+1\end{array}}\right\|<1$

Kaksinkertaiset pystypalkit tarkoittavat matriisinormia .

Newtonin menetelmä (tangenttien menetelmä)

Yksiulotteinen kotelo

Optimoimalla alkuperäisen yhtälön muunnos supistumismappaukseksi mahdollistaa menetelmän, jolla on neliöllinen konvergenssinopeus. $f(x) = 0$ $x=\varphi(x)$

Jotta kartoitus olisi tehokkain, on välttämätöntä, että seuraavan iteraation kohdassa , . Etsimme ratkaisua tähän yhtälöön muodossa , sitten: $x^{*}$ $\varphi '(x^{*})=0$ $\varphi (x)=x+\alpha (x)f(x)$

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

Käytetään faktaa, että , ja saadaan lopullinen kaava : $f(x) = 0$ $\alpha(x)$

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

Tätä silmällä pitäen supistumisfunktio on muodossa:

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

Sitten yhtälön numeerisen ratkaisun löytämisalgoritmi pelkistetään iteratiiviseksi laskentamenettelyksi: $f(x) = 0$

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

Moniulotteinen tapaus

Yleistetään saatu tulos moniulotteiseksi tapaukseksi.

Kun valitaan jokin alkuperäinen approksimaatio , peräkkäiset approksimaatiot löydetään ratkaisemalla yhtälöjärjestelmiä: ${\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

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

Katso myös

Kirjallisuus

Amosov A. A., Dubinsky Yu. A., Kopchenova N. P. Laskennalliset menetelmät insinööreille. - M .: Mir, 1998.
Bakhvalov N. S., Zhidkov N. P. , Kobelkov G. G. Numeeriset menetelmät. - 8. painos - M . : Perustiedon laboratorio, 2000.
Volkov E. A. Numeeriset menetelmät. - M .: Fizmatlit, 2003.
Korshunov Yu. M., Korshunov Yu. M. Kybernetiikan matemaattiset perusteet. - M .: Energoatomizdat, 1972.
Kalitkin N. N. Numeeriset menetelmät. - M .: Nauka, 1978.