Methode van Müller

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De methode van Müller (naar David E. Müller, University of Illinois) is een numerieke methode die algemeen bruikbaar is om de nulpunten van een analytische functie te bepalen, maar die vooral gebruikt wordt 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 relatief onafhankelijk 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), en kan zo de volgende wortel bepaald worden, tot de veelterm volledig is opgelost. Een alternatieve methode voor veeltermen is de methode van Bairstow.

Methode[bewerken]

Daar waar de secant-methode gebruik maakt van het nulpunt van een rechte door twee punten van de op te lossen functie, gebruikt de methode van Müller een nulpunt van een parabool door drie punten; Hierdoor krijgt men toegang tot complexe wortels. Gegeven drie punten P_{i-2}(x_{i-2},f(x_{i-2})) \, P_{i-1}(x_{i-1},f(x_{i-1})) \, P_{}(x_{i},f(x_{i})) \! wordt de parabool bepaald door deze drie punten. Neemt men de parabool van de vorm

p(x) \, = \, A(x-x_i)^2 \, + \, B \, (x-x_i) \, + \, C \!

en definieert men :

h_o \, = \, x_{i-1}-x_{i-2}
h_1 \, = \, x_{i}-x_{i-1}
d_o \, = \frac{f(x_{i-1})-f(x_{x-2})}{h_o}
d_1 \, = \frac{f(x_{i})-f(x_{x-1})}{h_1}

dan is :

A \, = \, \frac{d_1-d_o}{h_1+h_o} \!
B \, = \, A \, h_1 \, + \, d_1 \!
C \, = \, f_i \!

De parabool heeft twee wortels :

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

De keuze van het plus- of minteken in de noemer wordt bepaald door die keuze voor wie de noemer 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[bewerken]

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[bewerken]

De veelterm :

p(x) \, = \, x^5-11x^4+46x^3-106x^2-15x-875 \!

heeft heeft vijf wortels:

-1 \pm 2j \!
3 \pm 4j \!
7 \!

Met de beginwaarden :

x(0) \, = \, -1 \, ; \, x(1) \, = \, 0 \, ; \, x(2) \, = \, 1 \!

bekomt men als opeenvolgende iteraties :

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 \!

Bijgevolg is ook

x(9)^* \, = \, -1 - 2j \!

een wortel, en kan in de veelterm een factor:

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.