Enkel iterationsmetod

Den enkla iterationsmetoden är en av de enklaste numeriska metoderna för att lösa ekvationer . Metoden bygger på principen om komprimerande kartläggning , som i förhållande till numeriska metoder i allmänna termer också kan kallas metoden för enkel iteration eller metoden för successiva approximationer [1] . I synnerhet finns det en liknande iterationsmetod för system med linjära algebraiska ekvationer .

Metodidé

Tanken med den enkla iterationsmetoden är att reducera ekvationen till en ekvivalent ekvation $f(x)=0$

x=\varphi(x)

så att displayen är komprimerande. Om detta lyckas konvergerar sekvensen av iterationer. Denna omvandling kan göras på olika sätt. I synnerhet formens ekvation $\varphi(x)$ $x_{i+1}=\varphi(x_i)$

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

om på det studerade segmentet. Det optimala valet är , vilket leder till Newtons metod , som är snabb, men kräver beräkning av derivatan. Om vi väljer en konstant med samma tecken som derivatan i närheten av roten, får vi den enklaste iterationsmetoden. ${\lambda}(x) \neq 0$ $\lambda(x) = \frac{1}{f'(x)}$ $\lambda(x)$

Beskrivning

Någon konstant tas som en funktion , vars tecken sammanfaller med tecknet för derivatan i någon grannskap av roten (och i synnerhet på segmentet som förbinder och ). Konstanten är vanligtvis inte heller beroende av stegnumret. Ibland tar de och kallar denna metod för en tangeringsmetod . Iterationsformeln visar sig vara extremt enkel: ${\lambda }(x)$ ${\lambda }_{0}$ $f'(x)$ ${\displaystyle x_{0))$ $x^{*}$ ${\lambda }_{0}$ ${\lambda}_0=\frac{1}{f'(x_0)}$

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

och vid varje iteration måste du beräkna värdet på funktionen en gång . $f(x)$

Denna formel, liksom kravet på att tecknen sammanfaller , kan lätt härledas från geometriska överväganden. Betrakta en rät linje som går genom en punkt på en graf med en lutning . Då blir ekvationen för denna linje $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}).

Hitta skärningspunkten för denna linje med axeln från ekvationen $OX$

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

varifrån . Därför skär denna räta linje axeln precis vid punkten för nästa approximation. Således får vi följande geometriska tolkning av successiva approximationer. Med utgångspunkt från punkten dras räta linjer genom motsvarande punkter i grafen med en lutning med samma tecken som derivatan . (Observera att det för det första inte är nödvändigt att beräkna värdet på derivatan, det räcker bara att veta om funktionen minskar eller ökar; för det andra att linjerna som ritas på olika har samma lutning och därför är parallella till varandra. ) Som nästa approximation till roten tas skärningspunkten för den konstruerade linjen med axeln . ${\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$

Ritningen till höger visar iterationer för in case och in case . Vi ser att i det första fallet "hoppar" ändringspunkten redan vid första steget på andra sidan roten , och iterationerna börjar närma sig roten från andra sidan. I det andra fallet närmar sig på varandra följande punkter roten och förblir hela tiden på ena sidan av den. $f'(x)>0$ $k={\dfrac {1}{{\lambda }_{0}}}<f'(x_{0})$ $k={\dfrac {1}{{\lambda }_{0}}}>f'(x_{0})$ $x_i$ $x^{*}$ $x_i$

Konvergensvillkor

Ett tillräckligt villkor för konvergens är:

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

Denna ojämlikhet kan skrivas om som

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

varifrån vi får den konvergensen garanteras när, först,

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

sedan (således förtydligas innebörden av att välja talets tecken ), och för det andra, när för alla på hela segmentet under övervägande kring roten. Denna andra ojämlikhet är verkligen tillfredsställd om $-{\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)),

var . Således bör lutningen inte vara för liten i absolut värde: med en liten lutning, redan vid det första steget, kan punkten hoppa ut ur den övervägda grannskapet av roten , och det kanske inte finns konvergens till roten. $M_{1}=\max \limits _{x}\vert f'(x)\vert$ $k$ $x_1$ $x^{*}$

Anteckningar

↑ Matematisk encyklopedisk ordbok . - M . : "Ugglor. encyclopedia" , 1988. - S. 847 .

Enkel iterationsmetod

Metodidé

Beskrivning

Konvergensvillkor

Anteckningar

Se även