Egyszerű iterációs módszer

Az egyszerű iterációs módszer az egyik legegyszerűbb numerikus módszer az egyenletek megoldására . A módszer a kompressziós leképezés elvén alapul , amelyet általánosságban a numerikus módszerek kapcsán nevezhetünk egyszerű iteráció módszerének vagy egymás utáni közelítések módszerének is [1] . Különösen létezik egy hasonló iterációs módszer a lineáris algebrai egyenletrendszerekhez .

Módszerötlet

Az egyszerű iterációs módszer lényege, hogy az egyenletet egy ekvivalens egyenletre redukáljuk $f(x)=0$

x=\varphi(x)

hogy a kijelző összenyomódjon. Ha ez sikerül, akkor az iterációk sorozata konvergál. Ezt az átalakítást többféleképpen is meg lehet valósítani. Különösen a forma egyenlete $\varphi(x)$ $x_{i+1}=\varphi(x_i)$

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

ha a vizsgált szegmensen. Az optimális választás a , ami a Newton-módszerhez vezet , amely gyors, de a derivált kiszámítását igényli. Ha a gyökér szomszédságában a deriválttal azonos előjelű konstanst választunk, akkor a legegyszerűbb iterációs módszert kapjuk. ${\lambda}(x) \neq 0$ $\lambda(x) = \frac{1}{f'(x)}$ $\lambda(x)$

Leírás

Valamelyik állandót függvénynek veszünk , amelynek előjele egybeesik a származék előjelével a gyök valamely szomszédságában (és különösen a és -t összekötő szakaszon ). A konstans általában nem függ a lépésszámtól sem. Néha ezt a módszert egy érintő módszernek nevezik . Az iterációs képlet rendkívül egyszerűnek bizonyul: ${\lambda}(x)$ ${\displaystyle {\lambda }_{0))$ $f'(x)$ ${\displaystyle x_{0))$ $x^{*}$ ${\displaystyle {\lambda }_{0))$ ${\lambda}_0=\frac{1}{f'(x_0)}$

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

és minden iterációnál egyszer ki kell számítanod a függvény értékét . $f(x)$

Ez a képlet, valamint a jelek egybeesésének követelménye könnyen levezethető geometriai megfontolásokból. Tekintsünk egy egyenest, amely egy meredekségű grafikon pontján halad át . Ekkor ennek az egyenesnek az egyenlete a következő lesz $f'$ ${\displaystyle {\lambda }_{0))$ $(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}).

Keresse meg ennek az egyenesnek a metszéspontját az egyenlet tengelyével $OX$

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

honnan . Ezért ez az egyenes éppen a következő közelítés pontjában metszi a tengelyt. Így az egymást követő közelítések alábbi geometriai értelmezését kapjuk. A pontból kiindulva a gráf megfelelő pontjain keresztül egyenesek húzódnak a deriválttal azonos előjelű meredekséggel . (Megjegyzendő, hogy először is nem szükséges kiszámítani a derivált értékét, elég csak azt tudni, hogy a függvény csökken vagy növekszik; másodszor, hogy a különböző pontokra húzott egyenesek ugyanolyan meredekségűek , ezért párhuzamosak egymáshoz. ) A gyök következő közelítéseként a megszerkesztett egyenes metszéspontját a tengellyel vesszük fel . ${\displaystyle x=x_{i}-{\lambda }_{0}f(x_{i})=x_{i+1))$ $OX$ ${\displaystyle x_{0))$ $y=f(x)$ ${\displaystyle k={\dfrac {1}{{\lambda }_{0))))$ $f'(x_{0})$ $f(x)$ $x_i$ $k$ $OX$

A jobb oldali rajz az eset és eset iterációit mutatja . Azt látjuk, hogy az első esetben a változó pont már az első lépésnél "ugrik" a gyökér másik oldalára , és az iterációk a másik oldalról kezdenek közelíteni a gyökérhez. A második esetben az egymást követő pontok közelednek a gyökérhez, és mindvégig annak egyik oldalán maradnak. $f'(x)>0$ $k={\dfrac {1}{{\lambda }_{0}}}<f'(x_{0})$ $k={\dfrac {1}{{\lambda }_{0}}}>f'(x_{0})$ $x_i$ $x^{*}$ $x_i$

Konvergencia feltétel

A konvergencia elégséges feltétele:

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

Ez az egyenlőtlenség átírható így

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

honnan kapjuk, hogy a konvergencia garantált, amikor először

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

mivel (így tisztázódik a szám jelének megválasztásának jelentése ), másodszor pedig, amikor mindenre a gyökér körüli vizsgált szegmensen. Ez a második egyenlőtlenség minden bizonnyal teljesül, ha $-{\gamma }+1>0$ ${\displaystyle {\lambda }_{0))$ ${\lambda }_{0}f'(x)<2$ $x$

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

ahol . Így a meredekség abszolút értékben ne legyen túl kicsi: kis meredekségnél már az első lépésnél kiugorhat a pont a gyökér figyelembe vett szomszédságából , és előfordulhat, hogy nincs konvergencia a gyökérhez. $M_{1}=\max \limits _{x}\vert f'(x)\vert$ $k$ $x_1$ $x^{*}$

Jegyzetek

↑ Matematikai enciklopédikus szótár . - M . : "Baglyok. enciklopédia" , 1988. - S. 847 .

Egyszerű iterációs módszer

Módszerötlet

Leírás

Konvergencia feltétel

Jegyzetek

Lásd még