Clenshawův algoritmus - Clenshaw algorithm

v numerická analýza, Clenshawův algoritmus, také zvaný Clenshawův součet, je rekurzivní metoda pro vyhodnocení lineární kombinace Čebyševovy polynomy.^[1][2] Jedná se o zobecnění Hornerova metoda pro vyhodnocení lineární kombinace monomials.

Zobecňuje se na více než jen Čebyševovy polynomy; vztahuje se na jakoukoli třídu funkcí, kterou lze definovat třemi termíny relace opakování.^[3]

Clenshawův algoritmus

V plné obecnosti algoritmus Clenshaw počítá vážený součet konečné řady funkcí ${ displaystyle phi _ {k} (x)}$:

${ displaystyle S (x) = součet _ {k = 0} ^ {n} a_ {k} phi _ {k} (x)}$

kde ${ displaystyle phi _ {k}, ; k = 0,1, ldots}$ je posloupnost funkcí, které uspokojují vztah lineární rekurence

${ displaystyle phi _ {k + 1} (x) = alpha _ {k} (x) , phi _ {k} (x) + beta _ {k} (x) , phi _ {k-1} (x),}$

kde koeficienty ${ displaystyle alpha _ {k} (x)}$ a ${ displaystyle beta _ {k} (x)}$ jsou známy předem.

Algoritmus je nejužitečnější, když ${ displaystyle phi _ {k} (x)}$ jsou funkce, které se komplikovaně počítají přímo, ale ${ displaystyle alpha _ {k} (x)}$ a ${ displaystyle beta _ {k} (x)}$ jsou obzvláště jednoduché. V nejběžnějších aplikacích ${ displaystyle alpha (x)}$ nezávisí na ${ displaystyle k}$, a ${ displaystyle beta}$ je konstanta, která nezávisí na žádném ${ displaystyle x}$ ani ${ displaystyle k}$.

Provést součet pro danou řadu koeficientů ${ displaystyle a_ {0}, ldots, a_ {n}}$, spočítat hodnoty ${ displaystyle b_ {k} (x)}$ podle vzorce „zpětného“ opakování:

${ displaystyle { begin {aligned} b_ {n + 1} (x) & = b_ {n + 2} (x) = 0, b_ {k} (x) & = a_ {k} + alpha _ {k} (x) , b_ {k + 1} (x) + beta _ {k + 1} (x) , b_ {k + 2} (x). end {zarovnáno}}}$

Všimněte si, že tento výpočet neobsahuje žádný přímý odkaz na funkce ${ displaystyle phi _ {k} (x)}$. Po výpočtu ${ displaystyle b_ {2} (x)}$ a ${ displaystyle b_ {1} (x)}$, lze požadovaný součet vyjádřit pomocí nich a nejjednodušších funkcí ${ displaystyle phi _ {0} (x)}$ a ${ displaystyle phi _ {1} (x)}$:

${ displaystyle S (x) = phi _ {0} (x) , a_ {0} + phi _ {1} (x) , b_ {1} (x) + beta _ {1} ( x) , phi _ {0} (x) , b_ {2} (x).}$

Viz Fox a Parker^[4] pro více informací a analýzy stability.

Příklady

Horner jako zvláštní případ Clenshawa

Obzvláště jednoduchý případ nastane při hodnocení polynomu formy

${ displaystyle S (x) = součet _ {k = 0} ^ {n} a_ {k} x ^ {k}}$.

Funkce jsou jednoduše

${ displaystyle { begin {aligned} phi _ {0} (x) & = 1, phi _ {k} (x) & = x ^ {k} = x phi _ {k-1} (x) end {zarovnáno}}}$

a jsou vytvářeny koeficienty rekurence ${ displaystyle alpha (x) = x}$ a ${ displaystyle beta = 0}$.

V tomto případě je vzorec opakování pro výpočet součtu

${ displaystyle b_ {k} (x) = a_ {k} + xb_ {k + 1} (x)}$

a v tomto případě je součet jednoduše

${ displaystyle S (x) = a_ {0} + xb_ {1} (x) = b_ {0} (x)}$,

což je přesně obvyklé Hornerova metoda.

Speciální případ pro Čebyševovu sérii

Zvažte zkrácenou Čebyševova série

${ displaystyle p_ {n} (x) = a_ {0} + a_ {1} T_ {1} (x) + a_ {2} T_ {2} (x) + cdots + a_ {n} T_ {n }(X).}$

Koeficienty v relaci rekurze pro Čebyševovy polynomy jsou

${ displaystyle alpha (x) = 2x, quad beta = -1,}$

s původními podmínkami

${ displaystyle T_ {0} (x) = 1, quad T_ {1} (x) = x.}$

Opakování tedy je

${ displaystyle b_ {k} (x) = a_ {k} + 2xb_ {k + 1} (x) -b_ {k + 2} (x)}$

a konečná částka je

${ displaystyle p_ {n} (x) = a_ {0} + xb_ {1} (x) -b_ {2} (x).}$

Jedním ze způsobů, jak to vyhodnotit, je pokračovat v opakování ještě o jeden krok a vypočítat

${ displaystyle b_ {0} (x) = 2a_ {0} + 2xb_ {1} (x) -b_ {2} (x),}$

(všimněte si zdvojnásobení A₀ koeficient) následovaný

${ displaystyle p_ {n} (x) = { frac {1} {2}} vlevo [b_ {0} (x) -b_ {2} (x) vpravo].}$

Délka poledníku na elipsoidu

Clenshawův součet se hojně používá v geodetických aplikacích.^[2] Jednoduchá aplikace spočítá trigonometrickou řadu k výpočtu poledníkový oblouk vzdálenost na povrchu elipsoidu. Ty mají formu

${ displaystyle m ( theta) = C_ {0} , theta + C_ {1} sin theta + C_ {2} sin 2 theta + cdots + C_ {n} sin n theta. }$

Ponechání počáteční ${ displaystyle C_ {0} , theta}$ termín, zbytek je součtem příslušné formy. Neexistuje žádný vedoucí termín, protože ${ displaystyle phi _ {0} ( theta) = sin 0 theta = sin 0 = 0}$.

The relace opakování pro ${ displaystyle sin k theta}$ je

${ Displaystyle sin (k + 1) theta = 2 cos theta sin k theta - sin (k-1) theta}$,

vytváření koeficientů v relaci rekurze

${ displaystyle alpha _ {k} ( theta) = 2 cos theta, quad beta _ {k} = - 1.}$

a vyhodnocení série je dáno

${ displaystyle { begin {sladěno} b_ {n + 1} ( theta) & = b_ {n + 2} ( theta) = 0, b_ {k} ( theta) & = C_ {k} +2 cos theta , b_ {k + 1} ( theta) -b_ {k + 2} ( theta), quad mathrm {pro } n geq k geq 1. end {zarovnáno }}}$

Poslední krok je obzvláště jednoduchý, protože ${ displaystyle phi _ {0} ( theta) = sin 0 = 0}$, takže konec opakování je jednoduše ${ displaystyle b_ {1} ( theta) sin ( theta)}$; the ${ displaystyle C_ {0} , theta}$ termín je přidán samostatně:

${ displaystyle m ( theta) = C_ {0} , theta + b_ {1} ( theta) sin theta.}$

Všimněte si, že algoritmus vyžaduje pouze vyhodnocení dvou trigonometrických veličin ${ displaystyle cos theta}$ a ${ displaystyle sin theta}$.

Rozdíl v délkách oblouku poledníku

Někdy je nutné vypočítat rozdíl dvou oblouků meridiánů způsobem, který udržuje vysokou relativní přesnost. Toho je dosaženo použitím trigonometrických identit k zápisu

${ displaystyle m ( theta _ {1}) - m ( theta _ {2}) = C_ {0} ( theta _ {1} - theta _ {2}) + součet _ {k = 1 } ^ {n} 2C_ {k} sin { bigl (} { textstyle { frac {1} {2}}} k ( theta _ {1} - theta _ {2}) { bigr) } cos { bigl (} { textstyle { frac {1} {2}}} k ( theta _ {1} + theta _ {2}) { bigr)}.}$

V tomto případě lze použít Clenshawův součet^[5]za předpokladu, že současně počítáme ${ displaystyle m ( theta _ {1}) + m ( theta _ {2})}$a provést maticový součet,

${ displaystyle { mathsf {M}} ( theta _ {1}, theta _ {2}) = { begin {bmatrix} (m ( theta _ {1}) + m ( theta _ {2 })) / 2 (m ( theta _ {1}) - m ( theta _ {2})) / ( theta _ {1} - theta _ {2}) end {bmatrix}} = C_ {0} { begin {bmatrix} mu 1 end {bmatrix}} + sum _ {k = 1} ^ {n} C_ {k} { mathsf {F}} _ {k} ( theta _ {1}, theta _ {2}),}$

kde

${ displaystyle { begin {aligned} delta & = { textstyle { frac {1} {2}}} ( theta _ {1} - theta _ {2}), mu & = { textstyle { frac {1} {2}}} ( theta _ {1} + theta _ {2}), { mathsf {F}} _ {k} ( theta _ {1}, theta _ {2}) & = { begin {bmatrix} cos k delta sin k mu displaystyle { frac { sin k delta} { delta}} cos k mu konec {bmatrix}}. end {zarovnáno}}}$

První prvek ${ displaystyle { mathsf {M}} ( theta _ {1}, theta _ {2})}$ je průměrná hodnota ${ displaystyle m}$ a druhým prvkem je průměrný sklon.${ displaystyle { mathsf {F}} _ {k} ( theta _ {1}, theta _ {2})}$ uspokojuje recidivu

${ displaystyle { mathsf {F}} _ {k + 1} ( theta _ {1}, theta _ {2}) = { mathsf {A}} ( theta _ {1}, theta _ {2}) { mathsf {F}} _ {k} ( theta _ {1}, theta _ {2}) - { mathsf {F}} _ {k-1} ( theta _ {1 }, theta _ {2}),}$

kde

${ displaystyle { mathsf {A}} ( theta _ {1}, theta _ {2}) = 2 { begin {bmatrix} cos delta cos mu & - delta sin delta sin mu - displaystyle { frac { sin delta} { delta}} sin mu & cos delta cos mu end {bmatrix}}}$

nahrazuje ${ displaystyle alpha}$ v relaci opakování a ${ displaystyle beta = -1}$Na výtěžek lze nyní použít standardní algoritmus Clenshaw

${ displaystyle { begin {aligned} { mathsf {B}} _ {n + 1} & = { mathsf {B}} _ {n + 2} = { mathsf {0}}, { mathsf {B}} _ {k} & = C_ {k} { mathsf {I}} + { mathsf {A}} { mathsf {B}} _ {k + 1} - { mathsf {B} } _ {k + 2}, qquad mathrm {pro } n geq k geq 1, { mathsf {M}} ( theta _ {1}, theta _ {2}) & = C_ {0} { begin {bmatrix} mu 1 end {bmatrix}} + { mathsf {B}} _ {1} { mathsf {F}} _ {1} ( theta _ {1 }, theta _ {2}), end {zarovnáno}}}$

kde ${ displaystyle { mathsf {B}} _ {k}}$ jsou matice 2 × 2. Konečně máme

${ displaystyle { frac {m ( theta _ {1}) - m ( theta _ {2})} { theta _ {1} - theta _ {2}}} = { mathsf {M} } _ {2} ( theta _ {1}, theta _ {2}).}$

Tuto techniku ​​lze použít v omezit ${ displaystyle theta _ {2} = theta _ {1} = mu}$a ${ displaystyle delta = 0 ,}$ současně počítat ${ displaystyle m ( mu)}$ a derivát${ displaystyle dm ( mu) / d mu}$, za předpokladu, že při hodnocení ${ displaystyle { mathsf {F}} _ {1}}$ a ${ displaystyle { mathsf {A}}}$,bereme ${ displaystyle lim _ { delta rightarrow 0} ( sin delta) / delta = 1}$.

Viz také

• Hornerovo schéma vyhodnotit polynomy v monomiální forma
• De Casteljauův algoritmus vyhodnotit polynomy v Bézierova forma

Reference