Muller metode

Muller-metoden er en iterativ numerisk metode til løsning af ligningen for en kontinuert funktion. Introduceret af David Müller i 1956. $f(x)=0$

Mullers metode udvikler ideen om sekantmetoden , som ved hvert iterationstrin plotter linjer , der går gennem to punkter på grafen y = f ( x ). I stedet bruger Mullers metode tre punkter, konstruerer en parabel gennem disse tre punkter og tager skæringspunktet mellem parablen og x - aksen som den næste tilnærmelse .

Tilbagevendende formel

De tre oprindeligt nødvendige værdier er angivet som x k , x k −1 og x k −2 . En parabel, der går gennem tre punkter ( x k , f ( x k )), ( x k −1 , f ( x k −1 )) og ( x k −2 , f ( x k −2 )), er skrevet af Newtons formel på følgende måde

y=f(x_{k})+(x-x_{k})f[x_{k},x_{k-1}]+(x-x_{k})(x-x_{k -1})f[x_{k},x_{k-1},x_{k-2}],

hvor f [ x k , x k −1 ] og f [ x k , x k −1 , x k −2 ] er de dividerede forskelle . Denne ligning kan omskrives som

y=f(x_{k})+w(x-x_{k})+f[x_{k},x_{k-1},x_{k-2}]\,(x-x_ {k})^{2},

hvor

w=f[x_{k},x_{k-1}]+f[x_{k},x_{k-2}]-f[x_{k-1},x_{k-2} ].

Den næste iteration giver roden af andengradsligningen y = 0. Dette giver den rekursive formel

x_{k+1}=x_{k}-{\frac {2f(x_{k})}{w\pm {\sqrt {w^{2}-4f(x_{k})f[ x_{k},x_{k-1},x_{k-2}]}}}}.

I denne formel er tegnet valgt, så nævneren er større i absolut værdi. Standardformlen til løsning af andengradsligninger bruges ikke, da dette kan føre til tab af signifikante cifre.

Tilnærmelsen x k +1 kan være et komplekst tal , selvom alle tidligere tilnærmelser var reelle , i modsætning til andre numeriske rodfindingsalgoritmer (sekantmetode eller Newtons metode ), hvor tilnærmelserne forbliver reelle, hvis man starter med et reelt tal. Tilstedeværelsen af komplekse iterationer kan både være en fordel (hvis der søges en kompleks rod) eller en ulempe (hvis man ved, at alle rødder er ægte).

Konvergenshastighed

Muller-metodens konvergenshastighed er ca. 1,84. Det kan sammenlignes med 1,62 for sekantmetoden og 2 for Newtonmetoden. Således vil sekantmetoden køre i flere trin end Muller-metoden og Newton-metoden.

Mere præcist, hvis betegner en ikke-multipel rod (det vil sige , , er tre gange kontinuerligt differentierbar, og de indledende tilnærmelser , , og var tilstrækkelig tæt på , så opfylder iterationerne relationen $\xi$ $f$ $f(\xi )=0,\ f'(\xi )\neq 0)$ $f$ $x_{0}$ $x_{1}$ $x_{2}$ $\xi$

\lim _{k\to \infty }{\frac {|x-x_{k}|}{|x-x_{k-1}|^{p))}=\venstre|{\frac {f'''(\xi )}{6f'(\xi )}}\right|^{(p-1)/2},

hvor p ≈ 1,84 er den positive rod af ligningen . $x^{3}-x^{2}-x-1=0$

Litteratur

Muller, David E., "A Method for Solving Algebraic Equations Using an Automatic Computer", MTAC, 10 (1956), 208-215.
Atkinson, Kendall E. (1989). An Introduction to Numerical Analysis , 2. udgave, afsnit 2.4. John Wiley & Sons, New York. ISBN 0-471-50023-2 .
Burden, R. L. og Faires, J. D. Numerical Analysis , 4. udgave, side 77ff.
Press, William H., et al. (1992). Numeriske opskrifter i Fortran 77: The Art of Scientific Computing , 2. udgave, side 364. ISBN 0-521-43064-X .

Muller metode

Tilbagevendende formel

Konvergenshastighed

Litteratur

Se også

Links