Mullers metod

Mullermetoden är en iterativ numerisk metod för att lösa ekvationen för en kontinuerlig funktion. Introducerad av David Müller 1956. $f(x)=0$

Mullers metod utvecklar idén om sekantmetoden , som plottar, vid varje iterationssteg , linjer som passerar genom två punkter på grafen y = f ( x ). Istället använder Mullers metod tre punkter, konstruerar en parabel genom dessa tre punkter och tar skärningspunkten mellan parabeln och x - axeln som nästa approximation .

Återkommande formel

De tre initialt nödvändiga värdena betecknas som x k , x k −1 och x k −2 . En parabel som går genom tre punkter ( x k , f ( x k )), ( x k −1 , f ( x k −1 )) och ( x k −2 , f ( x k −2 )) skrivs av Newtons formeln på följande sätt

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}],

där f [ x k , x k −1 ] och f [ x k , x k −1 , x k −2 ] är de delade skillnaderna . Denna ekvation kan skrivas om som

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

var

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

Nästa iteration ger roten till andragradsekvationen y = 0. Detta ger den rekursiva formeln

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 denna formel är tecknet valt så att nämnaren är större i absolut värde. Standardformeln för att lösa andragradsekvationer används inte, eftersom detta kan leda till förlust av signifikanta siffror.

Approximationen x k +1 kan vara ett komplext tal , även om alla tidigare approximationer var reella , till skillnad från andra numeriska rotsökningsalgoritmer (sekantmetod eller Newtons metod ), där approximationerna förblir reella om man börjar med ett reellt tal. Närvaron av komplexa iterationer kan vara både en fördel (om en komplex rot eftersträvas) eller en nackdel (om man vet att alla rötter är verkliga).

Konvergenshastighet

Konvergenshastigheten för Muller-metoden är ungefär 1,84. Det kan jämföras med 1,62 för sekantmetoden och 2 för Newtonmetoden. Således kommer sekantmetoden att köras i fler steg än Mullermetoden och Newtonmetoden.

Mer exakt, om betecknar en icke-multipel rot (det vill säga , är tre gånger kontinuerligt differentierbar, och de initiala approximationerna , , och var tillräckligt nära , så uppfyller iterationerna förhållandet $\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))}=\left|{\frac {f'''(\xi )}{6f'(\xi )}}\right|^{(p-1)/2},

där p ≈ 1,84 är den positiva roten av ekvationen . $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:a upplagan, avsnitt 2.4. John Wiley & Sons, New York. ISBN 0-471-50023-2 .
Burden, R. L. och Faires, J. D. Numerical Analysis , 4:e upplagan, sidorna 77ff.
Press, William H., et al. (1992). Numeriska recept i Fortran 77: The Art of Scientific Computing , 2:a upplagan, sidan 364. ISBN 0-521-43064-X .

Se även

Länkar

Modul för Muller-metoden av John H. Mathews