Sidis zobecnil sekansovou metodu - Sidis generalized secant method - Wikipedia

Sidiho zobecněná metoda sekans je algoritmus hledání kořenů, tj numerická metoda k řešení rovnice formuláře ${ displaystyle f (x) = 0}$ . Metodu publikoval Avram Sidi.^[1]

Metoda je zobecněním sekansová metoda. Stejně jako metoda secant je to iterační metoda což vyžaduje jedno hodnocení ${ displaystyle f}$ v každé iteraci a č deriváty z ${ displaystyle f}$. Metoda může konvergovat mnohem rychleji, ale s objednat který se blíží 2 za předpokladu, že ${ displaystyle f}$ splňuje níže uvedené podmínky pravidelnosti.

Algoritmus

Voláme ${ displaystyle alpha}$ kořen ${ displaystyle f}$, to znamená, ${ displaystyle f ( alpha) = 0}$. Sidiho metoda je iterační metoda, která generuje a sekvence ${ displaystyle {x_ {i} }}$ aproximací ${ displaystyle alpha}$. Začínání s k + 1 počáteční aproximace ${ displaystyle x_ {1}, dots, x_ {k + 1}}$, aproximace ${ displaystyle x_ {k + 2}}$ se počítá v první iteraci, aproximaci ${ displaystyle x_ {k + 3}}$ se počítá ve druhé iteraci atd. Každá iterace bere jako vstup poslední k + 1 přibližné hodnoty a hodnota ${ displaystyle f}$ při těchto aproximacích. Proto niterace bere jako vstup aproximace ${ displaystyle x_ {n}, tečky, x_ {n + k}}$ a hodnoty ${ displaystyle f (x_ {n}), tečky, f (x_ {n + k})}$.

Číslo k musí být 1 nebo větší: k = 1, 2, 3, .... Zůstává fixní během provádění algoritmu. Abychom získali počáteční aproximace ${ displaystyle x_ {1}, dots, x_ {k + 1}}$ dalo by se provést několik inicializačních iterací s nižší hodnotou k.

Aproximace ${ displaystyle x_ {n + k + 1}}$ se vypočítá následovně v nth iterace. A polynom interpolace ${ displaystyle p_ {n, k} (x)}$ z stupeň k je namontován na k + 1 bod ${ displaystyle (x_ {n}, f (x_ {n})), tečky (x_ {n + k}, f (x_ {n + k}))}$. S tímto polynomem další aproximace ${ displaystyle x_ {n + k + 1}}$ z ${ displaystyle alpha}$ se počítá jako

${ displaystyle x_ {n + k + 1} = x_ {n + k} - { frac {f (x_ {n + k})} {p_ {n, k} '(x_ {n + k})} }}$

(1)

s ${ displaystyle p_ {n, k} '(x_ {n + k})}$ derivát ${ displaystyle p_ {n, k}}$ na ${ displaystyle x_ {n + k}}$. Po výpočtu ${ displaystyle x_ {n + k + 1}}$ jeden vypočítá ${ displaystyle f (x_ {n + k + 1})}$ a algoritmus může pokračovat s (n + 1) iterace. Je zřejmé, že tato metoda vyžaduje tuto funkci ${ displaystyle f}$ hodnotit pouze jednou za iteraci; nevyžaduje žádné deriváty ${ displaystyle f}$.

Iterativní cyklus se zastaví, pokud je splněno příslušné kritérium zastavení. Kritériem je obvykle to, že poslední vypočítaná aproximace je dostatečně blízko vyhledávanému kořenu ${ displaystyle alpha}$.

Pro efektivní provedení algoritmu vypočítá Sidiho metoda interpolační polynom ${ displaystyle p_ {n, k} (x)}$ v jeho Newtonova forma.

Konvergence

Sidi ukázal, že pokud funkce ${ displaystyle f}$ je (k + 1) -krát průběžně diferencovatelné v otevřený interval ${ displaystyle I}$ obsahující ${ displaystyle alpha}$ (to znamená, ${ displaystyle f v C ^ {k + 1} (I)}$), ${ displaystyle alpha}$ je jednoduchý kořen ${ displaystyle f}$ (to znamená, ${ displaystyle f '( alpha) neq 0}$) a počáteční aproximace ${ displaystyle x_ {1}, dots, x_ {k + 1}}$ jsou vybrány dostatečně blízko k ${ displaystyle alpha}$, pak sekvence ${ displaystyle {x_ {i} }}$ konverguje k ${ displaystyle alpha}$, což znamená, že následující omezit drží: ${ displaystyle lim limity _ {n až infty} x_ {n} = alfa}$.

Sidi to navíc ukázal

${ displaystyle lim _ {n to infty} { frac {x_ {n + 1} - alpha} { prod _ {i = 0} ^ {k} (x_ {ni} - alpha)} } = L = { frac {(-1) ^ {k + 1}} {(k + 1)!}} { Frac {f ^ {(k + 1)} ( alpha)} {f '( alpha)}},}$

a to sekvence konverguje na ${ displaystyle alpha}$ řádu ${ displaystyle psi _ {k}}$, tj.

${ displaystyle lim limits _ {n to infty} { frac {| x_ {n + 1} - alpha |} {| x_ {n} - alpha | ^ { psi _ {k}} }} = | L | ^ {( psi _ {k} -1) / k}}$

Pořadí konvergence ${ displaystyle psi _ {k}}$ je pouze pozitivní kořen polynomu

${ displaystyle s ^ {k + 1} -s ^ {k} -s ^ {k-1} - tečky -s-1}$

Máme např. ${ displaystyle psi _ {1} = (1 + { sqrt {5}}) / 2}$ ≈ 1.6180, ${ displaystyle psi _ {2}}$ ≈ 1,8393 a ${ displaystyle psi _ {3}}$ ≈ 1,9276. Pořadí se blíží 2 zdola, pokud k se zvětší: ${ displaystyle lim limity _ {k až infty} psi _ {k} = 2}$^[2][3]

Související algoritmy

Sidiho metoda se redukuje na secantovou metodu, pokud vezmeme k = 1. V tomto případě polynom ${ displaystyle p_ {n, 1} (x)}$ je lineární aproximace ${ displaystyle f}$ kolem ${ displaystyle alpha}$ který se používá v niterace sekansové metody.

Můžeme očekávat, že čím větší si vybereme k, ten lepší ${ displaystyle p_ {n, k} (x)}$ je aproximace ${ displaystyle f (x)}$ kolem ${ displaystyle x = alpha}$. Také tím lépe ${ displaystyle p_ {n, k} '(x)}$ je aproximace ${ displaystyle f '(x)}$ kolem ${ displaystyle x = alpha}$. Pokud vyměníme ${ displaystyle p_ {n, k} '}$ s ${ displaystyle f '}$ v (1) získáme, že další aproximace v každé iteraci se vypočítá jako

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

(2)

To je Newton – Raphsonova metoda. Začíná to jedinou aproximací ${ displaystyle x_ {1}}$ abychom mohli vzít k = 0 v (2). Nevyžaduje interpolační polynom, ale místo toho je třeba vyhodnotit derivaci ${ displaystyle f '}$ v každé iteraci. V závislosti na povaze ${ displaystyle f}$ to nemusí být možné nebo praktické.

Jednou interpolační polynom ${ displaystyle p_ {n, k} (x)}$ bylo vypočítáno, lze také vypočítat další aproximaci ${ displaystyle x_ {n + k + 1}}$ jako řešení ${ displaystyle p_ {n, k} (x) = 0}$ místo použití (1). Pro k = 1 tyto dvě metody jsou identické: je to metoda secant. Pro k = 2 je tato metoda známá jako Mullerova metoda.^[3] Pro k = 3 tento přístup zahrnuje nalezení kořenů a kubická funkce, což je neatraktivně komplikované. Tento problém se zhoršuje u ještě větších hodnotk. Další komplikací je rovnice ${ displaystyle p_ {n, k} (x) = 0}$ bude obecně mít více řešení a musí být vydán předpis, které z těchto řešení je další aproximací ${ displaystyle x_ {n + k + 1}}$. Muller to pro tento případ dělá k = 2, ale zdá se, že žádné takové předpisy neexistují k > 2.

Reference