Methode van Muller

De methode van Muller, bedacht door David E. Muller van de University of Illinois en naar hem genoemd, is een numerieke methode die algemeen bruikbaar is om de nulpunten van een analytische functie te bepalen. De methode wordt vooral gebruikt om de wortels van een veelterm te vinden, ook wanneer die complex zijn. De methode convergeert voor enkelvoudige wortels met een snelheid 1,84, dus net onder de kwadratische snelheid van de Newton-Raphsonmethode, en ze is weinig afhankelijk van de gekozen beginschattingen. Nadat een wortel van een veelterm bepaald is, kan hij, eventueel samen met zijn complex toegevoegde wortel, worden weggedeeld, de zogenaamde deflatie, waarna de volgende wortel bepaald kan worden, tot alle wortels gevonden zijn. Een alternatieve methode voor veeltermen is de methode van Bairstow.

Methode

Daar waar de secant-methode gebruikmaakt van het nulpunt van een rechte door twee punten op de grafiek van de betrokken functie, gebruikt de methode van Muller een nulpunt van een parabool door drie punten. Hierdoor krijgt men toegang tot complexe wortels.

De parabool $p_{i}$ door drie gegeven punten $(x_{i-2},f(x_{i-2})),(x_{i-1},f(x_{i-1})),(x_{i},f(x_{i}))$ is van de vorm:

$p_{i}(x)=A(x-x_{i})^{2}+B(x-x_{i})+C$,

waarin de coëfficiënten $A,B$ en $C$ bepaald zijn door

$A={\frac {d_{1}-d_{0}}{h_{1}+h_{0}}}$

$B=A\,h_{1}+d_{1}$

$C=f(x_{i})$

met

$h_{0}=x_{i-1}-x_{i-2}$

$h_{1}=x_{i}-x_{i-1}$

$d_{0}={\frac {f(x_{i-1})-f(x_{x-2})}{h_{0}}}$

$d_{1}={\frac {f(x_{i})-f(x_{x-1})}{h_{1}}}$

De parabool heeft twee wortels, die met een minder bekende formule gegeven worden door:

$x_{\pm }=x_{i}+{\frac {-2C}{B\pm {\sqrt {B^{2}-4AC}}}}$

Kies

$x_{i+1}=x_{+}$ of $x_{i+1}=x_{-}$

Het plus- of minteken wordt bepaald door die noemer die in absolute waarde het grootst is.

Ook reële wortels blijken soms via complexe iteraties benaderd worden, zodat nog een (verwaarloosbaar) klein complex deel kan overblijven nadat de gewenste nauwkeurigheid bereikt is.

Deflatie

Indien een reële wortel $x_{i+1}=a$ gevonden is kan die in de veelterm worden weggedeeld door middel van een factor $(x-a)$. Indien de wortel complex is $x_{i+1}=a+jb$, dan is ook zijn complex toegevoegde een wortel, en kunnen ze samen worden weggedeeld door de factor $(x^{2}-2ax+a^{2}+b^{2})$. Dit proces van deflatie wordt toegepast tot alle wortels gevonden zijn.

Voorbeeld

De veelterm

$p(x)=x^{5}-11x^{4}+46x^{3}-106x^{2}-15x-875$

heeft vijf wortels:

$-1\pm 2j,\quad 3\pm 4j$ en $7$

Met de beginwaarden:

$x_{0}=-1,\quad x_{1}=0,\quad x_{2}=1$

krijgt men als opeenvolgende iteraties :

${\begin{aligned}x_{3}&=&0{,}13675+2{,}73129j\\x_{4}&=&-2{,}09597+1{,}84751j\\x_{5}&=&-0{,}85137+2{,}36063j\\x_{6}&=&-1{,}07320+2{,}02847j\\x_{7}&=&-0{,}99693+1{,}99546j\\x_{8}&=&-0{,}99999+2{,}00002j\\x_{9}&=&-1{,}00000+2{,}00000j\\x_{10}&=&-1{,}00000+2{,}00000j\end{aligned}}$

Bijgevolg is ook

$x_{9}^{*}=-1-2j$

een wortel, en kan in de veelterm een factor

$(x+1-2j)(x+1+2j)=x^{2}+2x+5$

worden weggedeeld, tot

$p(x)=x^{3}-5x^{2}-9x-35$.

Van deze restveelterm kunnen dan weer verdere wortels bepaald worden.