Mullersova metoda - Mullers method - Wikipedia

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale její zdroje zůstávají nejasné, protože jí chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Únor 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

Mullerova metoda je algoritmus hledání kořenů, a numerické metoda řešení rovnic tvaru F(X) = 0. Poprvé to představil David E. Muller v roce 1956.

Mullerova metoda je založena na sekansová metoda, který při každé iteraci vytvoří čáru procházející dvěma body v grafu F. Místo toho Mullerova metoda používá tři body, konstruuje parabola skrz tyto tři body a vezme průsečík X-osa s parabolou jako další aproximace.

Vztah opakování

Mullerova metoda je rekurzivní metoda, která generuje aproximaci vykořenit ξ z F při každé iteraci. Počínaje třemi počátečními hodnotami X₀, X₋₁ a X₋₂, první iterace vypočítá první aproximaci X₁, druhá iterace vypočítá druhou aproximaci X₂, třetí iterace vypočítá třetí aproximaci X₃atd. Proto tedy k^th iterace generuje aproximaci X_k. Každá iterace bere jako vstup poslední tři generované aproximace a hodnotu F při těchto aproximacích. Proto k^th iterace bere jako vstup hodnoty X_k-1, X_k-2 a X_k-3 a hodnoty funkcí F(X_k-1), F(X_k-2) a F(X_k-3). Aproximace X_k se vypočítá následovně.

Parabola y_k(X) je konstruován tak, že prochází třemi body (X_k-1, F(X_k-1)), (X_k-2, F(X_k-2)) a (X_k-3, F(X_k-3)). Když je napsáno v Newtonova forma, y_k(X) je

${ displaystyle y_ {k} (x) = f (x_ {k-1}) + (x-x_ {k-1}) f [x_ {k-1}, x_ {k-2}] + (x -x_ {k-1}) (x-x_ {k-2}) f [x_ {k-1}, x_ {k-2}, x_ {k-3}], ,}$

kde F[X_k-1, X_k-2] a F[X_k-1, X_k-2, X_k-3] označují rozdělené rozdíly. To lze přepsat jako

${ displaystyle y_ {k} (x) = f (x_ {k-1}) + w (x-x_ {k-1}) + f [x_ {k-1}, x_ {k-2}, x_ {k-3}] , (x-x_ {k-1}) ^ {2} ,}$

kde

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

Další iterace X_k se nyní uvádí jako nejbližší řešení X_k-1 kvadratické rovnice y_k(X) = 0. Tím se získá relace opakování

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

V tomto vzorci by mělo být znaménko zvoleno tak, aby jmenovatel byl co největší. Pro řešení nepoužíváme standardní vzorec kvadratické rovnice protože to může vést k ztráta významu.

Všimněte si, že X_k může být složitý, i když předchozí iteráty byly všechny skutečné. To je v kontrastu s jinými algoritmy pro hledání kořenů, jako je sekansová metoda, Sidiho zobecněná metoda sekans nebo Newtonova metoda, jehož iterace zůstanou reálné, pokud začínáme reálnými čísly. Mít složité iterace může být výhodou (pokud hledáte komplexní kořeny) nebo nevýhodou (pokud je známo, že všechny kořeny jsou skutečné) v závislosti na problému.

Rychlost konvergence

The pořadí konvergence Mullerovy metody je přibližně 1,84. To lze porovnat s 1,62 pro sekansová metoda a 2 pro Newtonova metoda. Takže secant metoda dělá menší pokrok na iteraci než Mullerova metoda a Newtonova metoda dělá větší pokrok.

Přesněji, pokud if označuje jeden kořen F (tak F(ξ) = 0 a F„(ξ) ≠ 0), F je třikrát průběžně diferencovatelné a počáteční odhady X₀, X₁, a X₂ jsou brány dostatečně blízko k ξ, pak iteráty uspokojí

${ displaystyle lim _ {k to infty} { frac {| x_ {k} - xi |} {| x_ {k-1} - xi | ^ { mu}}} = vlevo | { frac {f '' '( xi)} {6f' ( xi)}} doprava | ^ {( mu -1) / 2},}$

kde μ ≈ 1,84 je kladné řešení ${ displaystyle x ^ {3} -x ^ {2} -x-1 = 0}$.

Zobecnění a související metody

Mullerova metoda zapadá do paraboly, tj. Druhého řádu polynomiální, na poslední tři získané body F(X_k-1), F(X_k-2) a F(X_k-3) v každé iteraci. Dá se to zobecnit a vejít na polynom p_{k, m}(X) z stupeň m do posledního m+1 body v k^th opakování. Naše parabola y_k je psán jako p_k,2 v této notaci. Titul m musí být 1 nebo větší. Další aproximace X_k je nyní jedním z kořenů p_{k, m}, tj. jedno z řešení p_{k, m}(X) = 0. Brát m= 1 získáme sečanovou metodu, zatímco m= 2 dává Mullerovu metodu.

Muller vypočítal, že posloupnost {X_k} generovaný tímto způsobem konverguje ke kořenu ξ s řádem μ_m kde μ_m je pozitivní řešení ${ displaystyle x ^ {m + 1} -x ^ {m} -x ^ {m-1} - tečky -x-1 = 0}$.

Metoda je však mnohem obtížnější m> 2, než je pro m= 1 nebo m= 2, protože je mnohem těžší určit kořeny polynomu stupně 3 nebo vyššího. Dalším problémem je, že se zdá, že neexistuje předpis, který z kořenů p_{k, m} vybrat jako další aproximaci X_k pro m>2.

Tyto potíže překonává Sidiho zobecněná metoda sekans který také využívá polynom p_{k, m}. Místo toho, abychom se snažili vyřešit p_{k, m}(X) = 0, další aproximace X_k se vypočítá pomocí derivátu p_{k, m} na X_k-1 v této metodě.

Reference

• Muller, David E., „Metoda řešení algebraických rovnic pomocí automatického počítače“ Matematické tabulky a další pomůcky k výpočtu, 10 (1956), 208-215. JSTOR  2001916
• Atkinson, Kendall E. (1989). Úvod do numerické analýzy, 2. vydání, oddíl 2.4. John Wiley & Sons, New York. ISBN  0-471-50023-2.
• Burden, R. L. a Faires, J. D. Numerická analýza, 4. vydání, strany 77 a násl.
• Stiskněte, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). „Oddíl 9.5.2. Mullerova metoda“. Numerické recepty: Umění vědecké práce na počítači (3. vyd.). New York: Cambridge University Press. ISBN  978-0-521-88068-8.