Míra konvergence - Rate of convergence

V numerické analýze je pořadí konvergence a rychlost konvergence části konvergentní sekvence jsou veličiny, které představují, jak rychle se sekvence blíží limit. O sekvenci, která konverguje, se říká, že má pořadí konvergence a rychlost konvergence, pokud

Rychlost konvergence se také nazývá asymptotická chybová konstanta . Upozorňujeme, že tato terminologie není standardizovaná a někteří autoři použijí sazbu, pokud tento článek používá pořadí (např.).

V praxi rychlost a pořadí konvergence poskytují užitečné poznatky při použití iteračních metod pro výpočet numerických aproximací. Pokud je pořadí konvergence vyšší, je obvykle zapotřebí méně iterací, aby se získala užitečná aproximace. Přísně vzato však asymptotické chování sekvence neposkytuje přesvědčivé informace o žádné konečné části sekvence.

Podobné koncepty se používají pro diskretizační metody. Řešení diskretizovaného problému konverguje k řešení spojitého problému, protože velikost mřížky klesá na nulu a rychlost konvergence je jedním z faktorů účinnosti metody. Terminologie se však v tomto případě liší od terminologie iteračních metod.

Sériové zrychlení je sbírka technik pro zlepšení rychlosti konvergence diskretizace řady. Takové zrychlení se běžně provádí sekvenčními transformacemi .

Rychlost konvergence pro iterační metody

Definice Q-konvergence

Předpokládejme, že posloupnost konverguje k číslu . Sekvence se říká, že se setkají Q-lineárně se v případě, že existuje velké množství tak, že

Číslo se nazývá míra konvergence.

Sekvence se říká, že konverguje Q-superlineárně na (tj. Rychlejší než lineárně), pokud

a říká se, že konverguje Q-sublearně na (tj. pomaleji než lineárně), pokud

Pokud sekvence sublearně a dodatečně konverguje

pak se říká, že posloupnost logaritmicky konverguje k . Všimněte si, že na rozdíl od předchozích definic se logaritmická konvergence nenazývá „Q-logaritmická“.

Za účelem další klasifikace konvergence je pořadí konvergence definováno následovně. Sekvence se říká, konvergovat, aby se pro pokud

pro nějakou kladnou konstantu (ne nutně menší než 1, pokud ). Zejména konvergence s řádem

  • se nazývá lineární konvergence (pokud ),
  • se nazývá kvadratická konvergence ,
  • se nazývá kubická konvergence ,
  • atd.

Některé zdroje vyžadují, aby to bylo přísně větší, než je tomu v případě, že je to třeba řešit samostatně. Není však nutné, aby to bylo celé číslo. Například metoda secant , když konverguje na pravidelný jednoduchý kořen , má řád φ ≈ 1,618.

Ve výše uvedených definicích znamená „Q-“ „kvocient“, protože termíny jsou definovány pomocí kvocientu mezi dvěma po sobě následujícími termíny. Často však „Q-“ klesá a o sekvenci se jednoduše říká, že má lineární konvergenci , kvadratickou konvergenci atd.

Odhad objednávky

Praktickou metodou pro výpočet pořadí konvergence pro sekvenci je výpočet následující sekvence, která konverguje k

Definice R-konvergence

Definice Q-konvergence mají nedostatek v tom, že neobsahují některé sekvence, jako je sekvence níže, které konvergují přiměřeně rychle, ale jejichž rychlost je proměnlivá. Proto je definice míry konvergence rozšířena následovně.

Předpokládejme, že konverguje k . Sekvence se říká, že se setkají R-lineárně se v případě, že existuje sekvenci tak, že

a konverguje Q-lineárně na nulu. Předpona „R-“ znamená „root“.

Příklady

Zvažte sekvenci

Je možné ukázat, že tato posloupnost konverguje k . Abychom určili typ konvergence, zapojíme sekvenci do definice Q-lineární konvergence,

Zjistili jsme tedy, že konverguje Q-lineárně a má míru konvergence . Obecněji řečeno, pro libovolnou sekvenci konverguje lineárně s rychlostí .

Sekvence

také konverguje lineárně na 0 s rychlostí 1/2 podle definice R-konvergence, ale ne podle definice Q-konvergence. (Všimněte si, že jde o funkci floor , která dává největší celé číslo, které je menší nebo rovno .)

Sekvence

konverguje superlineárně. Ve skutečnosti je to kvadraticky konvergentní.

Nakonec sekvence

konverguje sublimačně a logaritmicky.

Graf znázorňující různé rychlosti konvergence pro sekvence ak, bk, ck a dk.
Lineární, lineární, superlineární (kvadratické) a sublearní rychlosti konvergence

Rychlost konvergence pro diskretizační metody

Podobná situace existuje u diskretizačních metod. Důležitým parametrem pro rychlost konvergence není iterační číslo k , ale počet bodů mřížky a rozteč mřížky. V tomto případě je počet bodů mřížky n v procesu diskretizace nepřímo úměrný rozteči mřížky.

V tomto případě se říká , že posloupnost konverguje k L s řádem q, pokud existuje konstanta C taková, že

Toto je psáno jako použití velké O notace .

Toto je relevantní definice při diskusi o metodách numerické kvadratury nebo řešení obyčejných diferenciálních rovnic .

Praktický způsob pro odhad pořadí konvergenci způsobu diskretizace, je vybrat velikost kroku a a výpočtu výsledné chyby a . Pořadí konvergence je pak aproximováno následujícím vzorcem:

Příklady (pokračování)

Sekvence s byla zavedena výše. Tato posloupnost konverguje s řádem 1 podle konvence pro diskretizační metody.

Sekvence s , která byla také zavedena výše, konverguje s řádem q pro každé číslo q . Říká se, že exponenciálně konverguje pomocí konvence pro diskretizační metody. Konverguje však pouze lineárně (tj. S řádem 1) pomocí konvence pro iterační metody.

Pořadí konvergence diskretizační metody souvisí s její chybou globálního zkrácení (GTE) .

Zrychlení konvergence

Existuje mnoho metod ke zvýšení rychlosti konvergence dané sekvence, tj. K transformaci dané sekvence do jedné konvergující rychleji na stejnou hranici. Takové techniky jsou obecně známé jako „ sériové zrychlení “. Cílem transformované sekvence je snížit výpočetní náklady výpočtu. Jedním z příkladů sériového zrychlení je Aitkenův delta-kvadrát proces .

Reference

  1. ^ Ruye, Wang (2015-02-12). "Pořadí a rychlost konvergence" . hmc.edu . Citováno 2020-07-31 .
  2. ^ Senning, Jonathan R. „Výpočet a odhad míry konvergence“ (PDF) . gordon.edu . Citováno 2020-08-07 .
  3. ^ a b Bockelman, Brian (2005). "Sazby konvergence" . math.unl.edu . Citováno 2020-07-31 .
  4. ^ Van Tuyl, Andrew H. (1994). "Zrychlení konvergence rodiny logaritmicky konvergentních sekvencí" (PDF) . Matematika výpočtu . 63 (207): 229–246. doi : 10,2307 / 2153571 . JSTOR   2153571 . Citováno 2020-08-02 .
  5. ^ Porta, FA (1989). „O pořadí Q a pořadí R“ (PDF) . Journal of Optimization Theory and Applications . 63 (3): 415–431. doi : 10,1007 / BF00939805 . S2CID   116192710 . Citováno 2020-07-31 .
  6. ^ a b Nocedal, Jorge; Wright, Stephen J. (2006). Numerická optimalizace (2. vyd.). Berlín, New York: Springer-Verlag . ISBN   978-0-387-30303-1 .
  7. ^ Senning, Jonathan R. „Výpočet a odhad míry konvergence“ (PDF) . gordon.edu . Citováno 2020-08-07 .

Literatura

Jednoduchá definice se používá v

Rozšířená definice se používá v

Definice Big O se používá v

  • Richard L. Burden a J. Douglas Faires (2001), Numerical Analysis (7. vydání), Brooks / Cole. ISBN   0-534-38216-9

Pojmy Q-lineární a R-lineární jsou používány v; Definice Big O při použití Taylorovy řady se používá v