Millersův opakovací algoritmus - Millers recurrence algorithm - Wikipedia

Millerův opakovací algoritmus je postup pro výpočet rychle klesajícího řešení lineárního relace opakování vyvinutý uživatelem J. C. P. Miller.^[1] Původně byl vyvinut k výpočtu tabulek upravených Besselova funkce^[2] ale také platí pro Besselovy funkce prvního druhu a má další aplikace, jako je výpočet koeficientů Čebyševovy expanze dalších speciálních funkcí.^[3]

Mnoho rodin speciálních funkcí uspokojuje relaci opakování, která spojuje hodnoty funkcí různých řádů se společným argumentem ${ displaystyle x}$.

Upravené Besselovy funkce prvního druhu ${ displaystyle I_ {n} (x)}$ uspokojit relaci opakování

${ displaystyle I_ {n-1} (x) = { frac {2n} {x}} I_ {n} (x) + I_ {n + 1} (x)}$.

Upravené Besselovy funkce druhého druhu ${ displaystyle K_ {n} (x)}$ také uspokojit stejný vztah opakování

${ displaystyle K_ {n-1} (x) = { frac {2n} {x}} K_ {n} (x) + K_ {n + 1} (x)}$.

První řešení rychle klesá s ${ displaystyle n}$. Druhé řešení rychle roste s ${ displaystyle n}$. Millerův algoritmus poskytuje numericky stabilní postup pro získání klesajícího řešení.

Vypočítat podmínky opakování ${ displaystyle a_ {0}}$ přes ${ displaystyle a_ {N}}$ podle Millerova algoritmu si nejdříve zvolí hodnotu ${ displaystyle M}$ mnohem větší než ${ displaystyle N}$ a spočítá zkušební řešení s počáteční podmínkou${ displaystyle a_ {M}}$ na libovolnou nenulovou hodnotu (například 1) a převzetí ${ displaystyle a_ {M + 1}}$ a pozdější termíny nulové. Potom se relace opakování používá k postupnému výpočtu zkušebních hodnot pro ${ displaystyle a_ {M-1}}$, ${ displaystyle a_ {M-2}}$ dolů ${ displaystyle a_ {0}}$. Všimněte si, že druhá sekvence získaná ze zkušební sekvence vynásobením konstantním normalizačním faktorem bude stále uspokojovat stejný relační opakování, lze pak použít samostatný normalizační vztah k určení normalizačního faktoru, který poskytuje skutečné řešení.

V příkladu upravených Besselových funkcí je vhodným normalizačním vztahem součet zahrnující sudé termíny opakování:

${ displaystyle I_ {0} (x) +2 sum _ {m = 1} ^ { infty} (- 1) ^ {m} I_ {2m} (x) = 1}$

kde nekonečný součet se stává konečným kvůli aproximaci ${ displaystyle a_ {M + 1}}$ a pozdější termíny jsou nulové.

Nakonec se potvrzuje, že chyba aproximace postupu je přijatelná opakováním postupu s druhou volbou ${ displaystyle M}$ větší než původní volba a potvrzení, že druhá sada výsledků pro ${ displaystyle a_ {0}}$ přes ${ displaystyle a_ {N}}$ dohodnout se v rámci první sady v rámci požadované tolerance. Upozorňujeme, že pro získání této dohody je hodnota ${ displaystyle M}$ musí být dostatečně velký, aby tento výraz ${ displaystyle a_ {M}}$ je malý ve srovnání s požadovanou tolerancí.

Na rozdíl od Millerova algoritmu se pokusí použít relaci opakování v dopředném směru počínaje známými hodnotami ${ displaystyle I_ {0} (x)}$ a ${ displaystyle I_ {1} (x)}$ získané jinými metodami selžou, protože chyby zaokrouhlování zavádějí komponenty rychle rostoucího řešení.^[4]

Olver^[2] a Gautschi^[5] podrobně analyzuje šíření chyb algoritmu.

Pro Besselovy funkce prvního druhu jsou ekvivalentní relace opakování a normalizační vztah:^[6]

${ displaystyle J_ {n-1} (x) = { frac {2n} {x}} J_ {n} (x) -J_ {n + 1} (x)}$

${ displaystyle J_ {0} (x) +2 suma _ {m = 1} ^ { infty} J_ {2m} (x) = 1}$.

Algoritmus je obzvláště efektivní v aplikacích, které vyžadují hodnoty Besselových funkcí pro všechny objednávky ${ displaystyle 0 cdots N}$ pro každou hodnotu ${ displaystyle x}$ ve srovnání s přímými nezávislými výpočty ${ displaystyle N + 1}$ samostatné funkce.

Reference