Metodă simplă de iterație

Metoda iterației simple este una dintre cele mai simple metode numerice de rezolvare a ecuațiilor . Metoda se bazează pe principiul mapării compresive , care, în raport cu metodele numerice în termeni generali, mai poate fi numită și metoda iterației simple sau metoda aproximărilor succesive [1] . În special, există o metodă similară de iterație pentru sistemele de ecuații algebrice liniare .

Ideea metodei

Ideea metodei simple de iterație este de a reduce ecuația la o ecuație echivalentă $f(x)=0$

x=\varphi(x)

astfel încât afișajul să fie compresiv. Dacă acest lucru reușește, atunci succesiunea iterațiilor converge. Această transformare se poate face în diferite moduri. În special, ecuația formei $\varphi(x)$ $x_{i+1}=\varphi(x_i)$

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

dacă pe segmentul studiat. Alegerea optimă este , ceea ce duce la metoda lui Newton , care este rapidă, dar necesită calcularea derivatei. Dacă alegem o constantă de același semn ca și derivata în vecinătatea rădăcinii, atunci obținem cea mai simplă metodă de iterație. ${\lambda}(x) \neq 0$ $\lambda(x) = \frac{1}{f'(x)}$ $\lambda(x)$

Descriere

O anumită constantă este luată ca funcție , al cărei semn coincide cu semnul derivatei într-o vecinătate a rădăcinii (și, în special, pe segmentul care leagă și ). De obicei, constanta nu depinde nici de numărul pasului. Uneori ei iau și numesc această metodă o metodă tangentă . Formula de iterație se dovedește a fi extrem de simplă: ${\lambda }(x)$ ${\lambda }_{0)$ $f'(x)$ $x_{0)$ $x^{*}$ ${\lambda }_{0)$ ${\lambda}_0=\frac{1}{f'(x_0)}$

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

și la fiecare iterație, trebuie să calculați valoarea funcției o dată . $f(x)$

Această formulă, precum și cerința ca semnele să coincidă , sunt ușor de dedus din considerente geometrice. Să considerăm o dreaptă care trece printr-un punct dintr-un grafic cu o pantă . Atunci ecuația acestei linii va fi $f'$ ${\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}).

Aflați punctul de intersecție al acestei drepte cu axa din ecuație $OX$

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

de unde . Prin urmare, această linie dreaptă intersectează axa chiar în punctul următoarei aproximări. Astfel, obținem următoarea interpretare geometrică a aproximărilor succesive. Pornind de la punctul , se trasează drepte prin punctele corespunzătoare ale graficului cu o pantă de același semn ca și derivata . (Rețineți că, în primul rând, nu este necesar să se calculeze valoarea derivatei, este suficient doar să știm dacă funcția este descrescătoare sau crescătoare; în al doilea rând, că dreptele trasate la diferite au aceeași pantă și, prin urmare, sunt paralele unul față de celălalt. ) Ca următoarea aproximare a rădăcinii, se ia punctul de intersecție a dreptei construite cu axa . $x=x_{i}-{\lambda }_{0}f(x_{i})=x_{i+1)$ $OX$ $x_{0)$ $y=f(x)$ $k={\dfrac {1}{{\lambda }_{0)))$ $f'(x_{0})$ $f(x)$ $x_i$ $k$ $OX$

Desenul din dreapta arată iterații pentru caz și caz . Vedem că în primul caz, punctul de schimbare deja la primul pas „sare” de cealaltă parte a rădăcinii , iar iterațiile încep să se apropie de rădăcină din cealaltă parte. În al doilea caz, punctele succesive se apropie de rădăcină, rămânând tot timpul pe o parte a acesteia. $f'(x)>0$ $k={\dfrac {1}{{\lambda }_{0}}}<f'(x_{0})$ $k={\dfrac {1}{{\lambda }_{0}}}>f'(x_{0})$ $x_i$ $x^{*}$ $x_i$

Condiție de convergență

O condiție suficientă pentru convergență este:

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

Această inegalitate poate fi rescrisă ca

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

de unde obținem că convergența este garantată atunci când, mai întâi,

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

întrucât (astfel se clarifică semnificația alegerii semnului numărului ) și, în al doilea rând, când pentru toți pe întregul segment luat în considerare care înconjoară rădăcina. Această a doua inegalitate este cu siguranță satisfăcută dacă $-{\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)),

unde . Astfel, panta nu trebuie să fie prea mică în valoare absolută: cu o pantă mică, deja la primul pas, punctul poate sări din vecinătatea considerată a rădăcinii și poate să nu existe convergență către rădăcină. $M_{1}=\max \limits _{x}\vert f'(x)\vert$ $k$ $x_1$ $x^{*}$

Note

↑ Dicţionar enciclopedic matematic . - M .: „Bufnițe. enciclopedie " , 1988. - S. 847 .

Metodă simplă de iterație

Ideea metodei

Descriere

Condiție de convergență

Note

Vezi și