Metoda pro domácnosti - Householders method - Wikipedia

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Metoda domácnosti“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (listopad 2013) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika a konkrétněji v numerická analýza, Metody domácnosti jsou třídou algoritmy hledání kořenů které se používají pro funkce jedné reálné proměnné se spojitými derivacemi do určitého řádu d + 1. Každá z těchto metod je charakterizována počtem d, který je známý jako objednat metody. Algoritmus je iterativní a má a rychlost konvergence z d + 1.

Tyto metody jsou pojmenovány po americkém matematikovi Alston Scott Householder.

Metoda

Metoda domácnosti je numerický algoritmus pro řešení nelineární rovnice F(X) = 0. V tomto případě funkce F musí být funkcí jedné reálné proměnné. Metoda se skládá ze sekvence iterací

${ displaystyle x_ {n + 1} = x_ {n} + d ; { frac { left (1 / f right) ^ {(d-1)} (x_ {n})} { left ( 1 / f vpravo) ^ {(d)} (x_ {n})}}}$

počínaje počátečním odhadem X₀.^[1]

Li F je d + 1 časy nepřetržitě diferencovatelné funkce a A je nula F ale ne z jeho derivátu, tedy v sousedství A, iteruje X_n uspokojit:^{[Citace je zapotřebí ]}

${ displaystyle | x_ {n + 1} -a | leq K cdot {| x_ {n} -a |} ^ {d + 1}}$, pro některé ${ displaystyle K> 0. !}$

To znamená, že iterace konvergují k nule, pokud je počáteční odhad dostatečně blízko, a že konvergence má pořádek d + 1.

Přes jejich pořadí konvergence nejsou tyto metody široce používány, protože nárůst přesnosti není přiměřený nárůstu úsilí o velké d. The Ostrowského index vyjadřuje snížení chyb v počtu vyhodnocení funkcí namísto počtu iterací.^[2]

• U polynomů vyhodnocení prvního d deriváty F na X_n za použití Hornerova metoda má snahu d + 1 polynomiální hodnocení. Od té doby n(d + 1) hodnocení přes n iterace dávají chybový exponent (d + 1)ⁿ, exponent pro vyhodnocení jedné funkce je ${ displaystyle { sqrt [{d + 1}] {d + 1}}}$, číselně 1.4142, 1.4422, 1.4142, 1.3797 pro d = 1, 2, 3, 4a poté padat.
• Pro obecné funkce je derivační vyhodnocení pomocí Taylorovy aritmetiky automatické rozlišení vyžaduje ekvivalent (d + 1)(d + 2)/2 vyhodnocení funkcí. Jedno vyhodnocení funkce tak redukuje chybu exponentem ${ displaystyle { sqrt [{3}] {2}} přibližně 1,2599}$ pro Newtonovu metodu, ${ displaystyle { sqrt [{6}] {3}} přibližně 1,2009}$ pro Halleyovu metodu a klesající k 1 nebo lineární konvergenci pro metody vyššího řádu.

Motivace

První přístup

Přibližná představa o metodě domácnosti je odvozena z geometrické řady. Nech nemovitý -hodnota, nepřetržitě rozlišitelný funkce f (x) mít jednoduchou nulu na X = A, to je kořen F(A) = 0 z multiplicity jedna, což je ekvivalentní k ${ displaystyle f '(a) neq 0}$. Pak 1/F(X) má jedinečnost v A, konkrétně jednoduchý pól (také multiplicitní), a blízký A chování 1/F(X) dominuje 1/(X − A). Přibližně jeden dostane

${ displaystyle { frac {1} {f (x)}} = { frac {1} {f (x) -f (a)}} = { frac {xa} {f (x) -f ( a)}} cdot { frac {-1} {a (1-x / a)}} přibližně { frac {-1} {af '(a)}} cdot sum _ {k = 0 } ^ { infty} left ({ frac {x} {a}} right) ^ {k}.}$

Tady ${ displaystyle f '(a) neq 0}$ protože A je jednoduchá nula F(X). Koeficient stupně d má hodnotu ${ displaystyle C , a ^ {- d}}$. Nyní tedy můžeme rekonstruovat nulu A dělením koeficientu stupně d − 1 koeficientem stupně d. Protože tato geometrická řada je přibližná k Taylorova expanze z 1/F(X), lze získat odhady nuly F(X) - nyní bez předchozí znalosti umístění této nuly - vydělením odpovídajících koeficientů Taylorovy expanze 1/F(X) nebo obecněji 1/F(b+X). Z toho dostane pro každé celé číslo d, a pokud existují odpovídající deriváty,

${ displaystyle a cca b + { frac {(1 / f) ^ {(d-1)} (b)} {(d-1)!}} ; { frac {d!} {(1 / f) ^ {(d)} (b)}} = b + d ; { frac {(1 / f) ^ {(d-1)} (b)} {(1 / f) ^ {(d )} (b)}}.}$

Druhý přístup

Předpokládat X = A je jednoduchý kořen. Pak blízko X = A, (1/F)(X) je meromorfní funkce. Předpokládejme, že máme Taylorova expanze:

${ displaystyle (1 / f) (x) = součet _ {d = 0} ^ { infty} { frac {(1 / f) ^ {(d)} (b)} {d!}} ( xb) ^ {d}.}$

Podle Königova věta, my máme:

${ displaystyle ab = lim _ {d rightarrow infty} { frac { frac {(1 / f) ^ {(d-1)} (b)} {(d-1)!}} { frac {(1 / f) ^ {(d)} (b)} {d!}}} = lim _ {d rightarrow infty} d { frac {(1 / f) ^ {(d-1 )} (b)} {(1 / f) ^ {(d)} (b)}}.}$

To naznačuje, že iterace domácnosti může být dobrou konvergentní iterací. Skutečný důkaz konvergence je také založen na této myšlence.

Metody nižšího řádu

Metoda domácnosti pro objednávku 1 je spravedlivá Newtonova metoda, od té doby:

${ displaystyle { begin {array} {rl} x_ {n + 1} = & x_ {n} +1 , { frac { left (1 / f right) (x_ {n})} { left (1 / f right) ^ {(1)} (x_ {n})}} [. 7em] = & x_ {n} + { frac {1} {f (x_ {n})}} cdot left ({ frac {-f '(x_ {n})} {f (x_ {n}) ^ {2}}} right) ^ {- 1} [. 7em] = & x_ {n } - { frac {f (x_ {n})} {f '(x_ {n})}}. end {pole}}}$

Za metodu objednávky 2 dostane jeden Halleyova metoda, protože totožnosti

${ displaystyle textstyle (1 / f) '(x) = - { frac {f' (x)} {f (x) ^ {2}}} }$

a

${ displaystyle textstyle (1 / f) '' (x) = - { frac {f '' (x)} {f (x) ^ {2}}} + 2 { frac {f '(x ) ^ {2}} {f (x) ^ {3}}}}$

výsledek v

${ displaystyle { begin {array} {rl} x_ {n + 1} = & x_ {n} +2 , { frac { left (1 / f right) '(x_ {n})} { left (1 / f right) '' (x_ {n})}} [1em] = & x_ {n} + { frac {-2f (x_ {n}) , f '(x_ {n} )} {- f (x_ {n}) f '' (x_ {n}) + 2f '(x_ {n}) ^ {2}}} [1em] = & x_ {n} - { frac { f (x_ {n}) f '(x_ {n})} {f' (x_ {n}) ^ {2} - { tfrac {1} {2}} f (x_ {n}) f '' (x_ {n})}} [1em] = & x_ {n} + h_ {n} ; { frac {1} {1 + { frac {1} {2}} (f '' / f ') (x_ {n}) , h_ {n}}}. end {pole}}}$

V posledním řádku ${ displaystyle h_ {n} = - { tfrac {f (x_ {n})} {f '(x_ {n})}}}$ je aktualizace Newtonovy iterace v bodě ${ displaystyle x_ {n}}$. Tento řádek byl přidán, aby demonstroval, kde spočívá rozdíl oproti jednoduché Newtonově metodě.

Metoda třetího řádu se získává z identity derivátu třetího řádu 1/F

${ displaystyle textstyle (1 / f) '' '(x) = - { frac {f' '' (x)} {f (x) ^ {2}}} + 6 { frac {f '( x) , f '' (x)} {f (x) ^ {3}}} - 6 { frac {f '(x) ^ {3}} {f (x) ^ {4}}}}$

a má vzorec

${ displaystyle { begin {array} {rl} x_ {n + 1} = & x_ {n} +3 , { frac { left (1 / f right) '' (x_ {n})} { left (1 / f right) '' '(x_ {n})}} [1em] = & x_ {n} - { frac {6f (x_ {n}) , f' (x_ {n }) ^ {2} -3f (x_ {n}) ^ {2} f '' (x_ {n})} {6f '(x_ {n}) ^ {3} -6f (x_ {n}) f '(x_ {n}) , f' '(x_ {n}) + f (x_ {n}) ^ {2} , f' '' (x_ {n})}} [1em] = & x_ {n} + h_ {n} { frac {1 + { frac {1} {2}} (f '' / f ') (x_ {n}) , h_ {n}} {1+ ( f '' / f ') (x_ {n}) , h_ {n} + { frac {1} {6}} (f' '' / f ') (x_ {n}) , h_ {n } ^ {2}}} end {pole}}}$

a tak dále.

Příklad

Prvním problémem, který Newton vyřešil Newton-Raphson-Simpsonovou metodou, byla polynomická rovnice ${ displaystyle y ^ {3} -2r-5 = 0}$. Všiml si, že by mělo existovat řešení blízké 2. Výměně y = X + 2 transformuje rovnici na

${ displaystyle 0 = f (x) = - 1 + 10x + 6x ^ {2} + x ^ {3}}$.

Taylorova řada vzájemné funkce začíná

${ displaystyle { begin {array} {rl} 1 / f (x) = & - 1-10 , x-106 , x ^ {2} -1121 , x ^ {3} -11856 , x ^ {4} -125392 , x ^ {5} & - 1326177 , x ^ {6} -14025978 , x ^ {7} -148342234 , x ^ {8} -1568904385 , x ^ { 9} & - 16593123232 , x ^ {10} + O (x ^ {11}) end {pole}}}$

Výsledek použití metod domácnosti pro různé objednávky na X = 0 se také získá dělením sousedních koeficientů druhé výkonové řady. U prvních objednávek získá člověk následující hodnoty po jediném iteračním kroku: Například v případě 3. objednávky${ displaystyle x_ {1} = 0,0 + 106/1121 = 0,09455842997324}$.

Jak je vidět, je jich trochu víc než d správná desetinná místa pro každou objednávku d. Prvních sto číslic správného řešení je 0.0945514815423265914823865405793029638573061056282391803041285290453121899834836671462672817771577578.

Pojďme vypočítat ${ displaystyle x_ {2}, x_ {3}, x_ {4}}$ hodnoty pro nějaký nejnižší řád,

${ displaystyle f = -1 + 10x + 6x ^ {2} + x ^ {3}}$

${ displaystyle f ^ { prime} = 10 + 12x + 3x ^ {2}}$

${ displaystyle f ^ { prime prime} = 12 + 6x}$

${ displaystyle f ^ { prime prime prime} = 6}$

A pomocí následujících vztahů,

1. objednávka; ${ displaystyle x_ {i + 1} = x_ {i} -f (x_ {i}) / f ^ { prime} (x_ {i})}$

2. řád; ${ displaystyle x_ {i + 1} = x_ {i} + (- 2ff ^ { prime}) / (2 {f ^ { prime}} ^ {2} -ff ^ { prime prime})}$

3. objednávka; ${ displaystyle x_ {i + 1} = x_ {i} - { frac {6f {f ^ { prime}} ^ {2} -3f ^ {2} f ^ { prime prime}} {6 { f ^ { prime}} ^ {3} -6ff ^ { prime} f ^ { prime prime} + f ^ {2} f ^ { prime prime prime}}}}$

Derivace

Přesná derivace metod domácnosti je od Aproximace Padé řádu d + 1 funkce, kde aproximant s lineárním čitatel je vybrán. Jakmile toho bylo dosaženo, aktualizace další aproximace vychází z výpočtu jedinečné nuly čitatele.

Aproximace Padé má formu

${ displaystyle f (x + h) = { frac {a_ {0} + h} {b_ {0} + b_ {1} h + cdots + b_ {d-1} h ^ {d-1}}} + O (h ^ {d + 1}).}$

Racionální funkce má nulu v ${ displaystyle h = -a_ {0}}$.

Stejně jako Taylorův polynom stupně d má d + 1 koeficienty, které závisí na funkci F, aproximace Padé také má d + 1 koeficienty závislé na F a jeho deriváty. Přesněji řečeno, v kterémkoli aproximátoru Padé se stupně polynomálu čitatele a jmenovatele musí přidat k řádu aproximantu. Proto, ${ displaystyle b_ {d} = 0}$ musí držet.

Dalo by se určit přibližný Padé vycházející z Taylorova polynomu z F použitím Euklidův algoritmus. Počínaje Taylorovým polynomem z 1/F je kratší a vede přímo k danému vzorci. Od té doby

${ Displaystyle (1 / f) (x + h) = (1 / f) (x) + (1 / f) '(x) h + cdots + (1 / f) ^ {(d-1)} ( x) { frac {h ^ {d-1}} {(d-1)!}} + (1 / f) ^ {(d)} (x) { frac {h ^ {d}} {d !}} + O (h ^ {d + 1})}$

se musí rovnat inverzní hodnotě požadované racionální funkce, dostaneme po vynásobení s ${ displaystyle a_ {0} + h}$ v moci ${ displaystyle h ^ {d}}$ rovnice

${ displaystyle 0 = b_ {d} = a_ {0} (1 / f) ^ {(d)} (x) { frac {1} {d!}} + (1 / f) ^ {(d- 1)} (x) { frac {1} {(d-1)!}}}$.

Nyní řešíme poslední rovnici pro nulu ${ displaystyle h = -a_ {0}}$ výsledků čitatele v

${ displaystyle { begin {array} {rl} h = & - a_ {0} = { frac {{ frac {1} {(d-1)!}} (1 / f) ^ {(d- 1)} (x)} {{ frac {1} {d!}} (1 / f) ^ {(d)} (x)}} [1em] = & d , { frac {(1 / f) ^ {(d-1)} (x)} {(1 / f) ^ {(d)} (x)}} end {pole}}}$.

To implikuje iterační vzorec

${ displaystyle x_ {n + 1} = x_ {n} + d ; { frac { left (1 / f right) ^ {(d-1)} (x_ {n})} { left ( 1 / f vpravo) ^ {(d)} (x_ {n})}}}$.

Vztah k Newtonově metodě

Metoda domácnosti použitá pro funkci se skutečnou hodnotou F(X) je stejný jako Newtonova metoda aplikovaná na funkci G(X):

${ displaystyle x_ {n + 1} = x_ {n} - { frac {g (x_ {n})} {g '(x_ {n})}}}$

s

${ displaystyle g (x) = vlevo | (1 / f) ^ {(d-1)} vpravo | ^ {- 1 / d} ,.}$

Zejména, d = 1 dává Newtonovu metodu nezměněnou a d = 2 dává Halleyovu metodu.

Reference

externí odkazy

• Pascal Sebah a Xavier Gourdon (2001). „Newtonova metoda a iterace vyšších řádů“. Poznámka: Použijte PostScript verze tohoto odkazu; verze webu není správně zkompilována.