Yksinkertainen iterointimenetelmä

Yksinkertainen iterointimenetelmä on yksi yksinkertaisimmista numeerisista menetelmistä yhtälöiden ratkaisemiseksi . Menetelmä perustuu kompressiivisen mappauksen periaatteeseen , jota voidaan yleisesti ottaen numeeristen menetelmien suhteen kutsua myös yksinkertaisen iteroinnin menetelmäksi tai peräkkäisten approksimaatioiden menetelmäksi [1] . Erityisesti on olemassa samanlainen iterointimenetelmä lineaarisille algebrallisille yhtälöille .

Menetelmäidea

Yksinkertaisen iterointimenetelmän ideana on pelkistää yhtälö ekvivalentiksi yhtälöksi $f(x) = 0$

x=\varphi(x)

niin, että näyttö puristuu. Jos tämä onnistuu, iteraatioiden sarja konvergoi. Tämä muunnos voidaan tehdä eri tavoin. Erityisesti muodon yhtälö $\varphi(x)$ $x_{i+1}=\varphi(x_i)$

\varphi (x)=x-{\lambda }(x)f(x)\!,

jos tutkittavalla segmentillä. Optimaalinen valinta on , joka johtaa Newtonin menetelmään , joka on nopea, mutta vaatii derivaatan laskemisen. Jos valitsemme samanmerkkisen vakion kuin derivaatan juuren läheisyydestä, saadaan yksinkertaisin iterointimenetelmä. ${\lambda}(x) \neq 0$ $\lambda(x) = \frac{1}{f'(x)}$ $\lambda(x)$

Kuvaus

Jokin vakio otetaan funktioksi , jonka etumerkki on sama kuin derivaatan merkki jossain juuren naapurustossa (ja erityisesti segmentillä, joka yhdistää ja ). Vakio ei yleensä myöskään riipu askelnumerosta. Joskus he ottavat ja kutsuvat tätä menetelmää yhdeksi tangenttimenetelmäksi . Iteraatiokaava osoittautuu erittäin yksinkertaiseksi: ${\lambda }(x)$ ${\lambda }_{0}$ $f'(x)$ ${\näyttötyyli x_{0))$ $x^{*}$ ${\lambda }_{0}$ ${\lambda}_0=\frac{1}{f'(x_0)}$

\displaystyle x_{i+1}=x_i-{\lambda}_0f(x_i)\!,

ja jokaisessa iteraatiossa sinun on laskettava funktion arvo kerran . $f(x)$

Tämä kaava sekä vaatimus siitä, että merkit ovat yhteneväiset , ovat helposti pääteltävissä geometrisistä näkökohdista. Tarkastellaan suoraa, joka kulkee kaavion pisteen läpi , jonka kaltevuus on . Sitten tämän suoran yhtälö on $f'$ ${\lambda }_{0}$ ${\näyttötyyli (x_{i};f(x_{i}))}$ $y=f(x)$ $\tan \nolimits \alpha ={\frac {1}{\lambda }}_{0}$

\displaystyle y=f(x_{i})+{\frac {1}{{\lambda }_{0}}}(x-x_{i}).

Etsi tämän suoran ja akselin leikkauspiste yhtälöstä $OX$

\displaystyle f(x_{i})+{\dfrac {1}({\lambda }_{0))}(x-x_{i})=0,

mistä . Siksi tämä suora leikkaa akselin juuri seuraavan approksimoinnin pisteessä. Siten saamme seuraavan geometrisen tulkinnan peräkkäisistä approksimaatioista. Pisteestä alkaen piirretään kaavion vastaavien pisteiden läpi suorat , joiden kaltevuus on sama kuin derivaatan . (Huomaa, että ensinnäkin ei ole tarpeen laskea derivaatan arvoa, riittää kun tietää onko funktio pienenevä vai kasvava; toiseksi, että eri kohdissa piirretyillä viivoilla on sama kaltevuus ja siksi ne ovat yhdensuuntaisia toisiinsa. ) Seuraavaksi juuren approksimaatioksi otetaan konstruoidun suoran leikkauspiste akselin kanssa . ${\displaystyle x=x_{i}-{\lambda }_{0}f(x_{i})=x_{i+1))$ $OX$ ${\näyttötyyli x_{0))$ $y=f(x)$ ${\displaystyle k={\dfrac {1}{{\lambda }_{0))))$ $f'(x_{0})$ $f(x)$ $x_i$ $k$ $OX$

Oikeanpuoleinen piirros näyttää iteraatiot tapaukselle ja tapaukselle . Näemme, että ensimmäisessä tapauksessa muuttuva piste jo ensimmäisessä vaiheessa "hyppää" juuren toiselle puolelle ja iteraatiot alkavat lähestyä juuria toiselta puolelta. Toisessa tapauksessa peräkkäiset pisteet lähestyvät juuria pysyen koko ajan sen toisella puolella. $f'(x)>0$ $k={\dfrac {1}{{\lambda }_{0}}}<f'(x_{0})$ $k={\dfrac {1}{{\lambda }_{0}}}>f'(x_{0})$ $x_i$ $x^{*}$ $x_i$

Konvergenssiehto

Riittävä ehto lähentymiselle on:

\displaystyle \vert {\varphi }'(x)\vert =\vert 1-{\lambda }_{0}f'(x)\vert \leqslant {\gamma }<1.

Tämä eriarvoisuus voidaan kirjoittaa uudelleen muotoon

\displaystyle -{\gamma }+1\leqslant {\lambda }_{0}f'(x)\leqslant {\gamma }+1,

mistä saamme sen, että lähentyminen on taattu, kun ensin

\displaystyle {\lambda }_{0}f'(x)>0,

koska (täten luvun merkin valinnan merkitys selkiytyy ), ja toiseksi, kun kaikki tarkasteltavana olevalla juuria ympäröivällä segmentillä. Tämä toinen epätasa-arvo on varmasti tyytyväinen, jos $-{\gamma }+1>0$ ${\lambda }_{0}$ ${\lambda }_{0}f'(x)<2$ $x$

\displaystyle \vert k\vert ={\dfrac {1}{\vert {\lambda }_{0}\vert }}>{\dfrac {M_{1}}{2)),

missä . Siten kaltevuus ei saa olla itseisarvoltaan liian pieni: pienellä kaltevalla pisteellä voi jo ensimmäisessä askeleessa hypätä pois juuren tarkastelusta naapurustosta, eikä konvergenssia juuri tapahdu. $M_{1}=\max \limits _{x}\vert f'(x)\vert$ $k$ $x_1$ $x^{*}$

Muistiinpanot

↑ Matemaattinen tietosanakirja . - M . : "Pöllöt. tietosanakirja" , 1988. - S. 847 .

Yksinkertainen iterointimenetelmä

Menetelmäidea

Kuvaus

Konvergenssiehto

Muistiinpanot

Katso myös