Simpel iterationsmetode

Den simple iterationsmetode er en af de enkleste numeriske metoder til at løse ligninger . Metoden bygger på princippet om komprimerende kortlægning , som i forhold til numeriske metoder i generelle termer også kan kaldes metoden med simpel iteration eller metoden med successive tilnærmelser [1] . Især er der en lignende iterationsmetode for systemer med lineære algebraiske ligninger .

Metode idé

Ideen med den simple iterationsmetode er at reducere ligningen til en ækvivalent ligning $f(x)=0$

x=\varphi(x)

så skærmen er komprimerende. Hvis dette lykkes, så konvergerer sekvensen af iterationer . Denne transformation kan udføres på forskellige måder. Især formens ligning $\varphi(x)$ $x_{i+1}=\varphi(x_i)$

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

hvis på det undersøgte segment. Det optimale valg er , hvilket fører til Newtons metode , som er hurtig, men kræver beregning af den afledte. Hvis vi vælger en konstant med samme fortegn som den afledede i nærheden af roden, så får vi den enkleste iterationsmetode. ${\lambda}(x) \neq 0$ $\lambda(x) = \frac{1}{f'(x)}$ $\lambda(x)$

Beskrivelse

En eller anden konstant tages som en funktion , hvis fortegn falder sammen med tegnet for den afledede i et eller andet område af roden (og især på segmentet, der forbinder og ). Konstanten afhænger normalt heller ikke af trintallet. Nogle gange tager de og kalder denne metode en tangentmetode . Iterationsformlen viser sig at være ekstremt 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)\!,

og ved hver iteration skal du beregne værdien af funktionen én gang . $f(x)$

Denne formel, såvel som kravet om, at tegnene er sammenfaldende , kan let udledes af geometriske overvejelser. Betragt en ret linje, der går gennem et punkt på en graf med en hældning . Så vil ligningen for denne linje være $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}).

Find skæringspunktet for denne linje med aksen fra ligningen $OX$

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

hvorfra . Derfor skærer denne rette linje aksen lige ved punktet for den næste tilnærmelse. Således opnår vi følgende geometriske fortolkning af successive tilnærmelser. Startende fra punktet tegnes lige linjer gennem de tilsvarende punkter på grafen med en hældning med samme fortegn som den afledede . (Bemærk, at det for det første ikke er nødvendigt at beregne værdien af den afledte, det er nok blot at vide, om funktionen er faldende eller stigende; for det andet, at linjerne tegnet ved forskellige har samme hældning og derfor er parallelle til hinanden. ) Som den næste tilnærmelse til roden tages skæringspunktet for den konstruerede linje med aksen . ${\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$

Tegningen til højre viser iterationer for i tilfælde og i tilfælde . Vi ser, at i det første tilfælde "springer" skiftepunktet allerede ved første trin på den anden side af roden , og iterationerne begynder at nærme sig roden fra den anden side. I det andet tilfælde nærmer successive punkter roden og forbliver hele tiden på den ene side af 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$

Konvergensbetingelse

En tilstrækkelig betingelse for konvergens er:

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

Denne ulighed kan omskrives som

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

hvorfra vi opnår, at konvergens er garanteret, når først,

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

siden (således tydeliggøres betydningen af at vælge fortegn for tallet ), og for det andet, når for alle på hele segmentet under overvejelse omkring roden. Denne anden ulighed er bestemt tilfreds hvis $-{\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)),

hvor . Hældningen bør således ikke være for lille i absolut værdi: med en lille hældning, allerede ved det første trin, kan punktet springe ud af det betragtede kvarter af roden , og der er muligvis ikke konvergens til roden. $M_{1}=\max \limits _{x}\vert f'(x)\vert$ $k$ $x_1$ $x^{*}$

Noter

↑ Matematisk encyklopædisk ordbog . - M . : "Ugler. encyklopædi" , 1988. - S. 847 .

Simpel iterationsmetode

Metode idé

Beskrivelse

Konvergensbetingelse

Noter

Se også