Współczynnik konwergencji - Rate of convergence
Równania różniczkowe |
---|
Klasyfikacja |
Rozwiązanie |
W analizie numerycznej The kolejność konwergencji i szybkość zbieżności z ciągu zbieżnego są wielkościami, które reprezentują jak szybko sekwencja zbliża swój limit. Mówi się, że sekwencja zbieżna ma porządek zbieżności i szybkość zbieżności, jeśli
Szybkość zbieżności nazywana jest również asymptotyczną stałą błędu . Należy pamiętać, że ta terminologia nie jest ustandaryzowana i niektórzy autorzy będą używać stawki, gdy w tym artykule użyto kolejności (np.).
W praktyce szybkość i kolejność zbieżności zapewniają przydatne spostrzeżenia przy stosowaniu metod iteracyjnych do obliczania przybliżeń numerycznych. Jeśli rząd zbieżności jest wyższy, zwykle potrzeba mniej iteracji, aby uzyskać przydatne przybliżenie. Ściśle mówiąc, asymptotyczne zachowanie ciągu nie dostarcza jednak rozstrzygających informacji o żadnej skończonej części ciągu.
Podobne pojęcia są używane w przypadku metod dyskretyzacji . Rozwiązanie problemu dyskretyzowanego jest zbieżne z rozwiązaniem problemu ciągłego, gdy rozmiar sieci spada do zera, a prędkość zbieżności jest jednym z czynników wpływających na skuteczność metody. Jednak terminologia w tym przypadku różni się od terminologii metod iteracyjnych.
Przyspieszenie szeregów to zbiór technik poprawiających stopień zbieżności dyskretyzacji szeregów. Takie przyspieszenie jest zwykle osiągane za pomocą transformacji sekwencji .
Szybkość zbieżności dla metod iteracyjnych
Definicje zbieżności Q
Załóżmy, że sekwencja zbiega się do liczby . Sekwencja mówi się, że zbiegają Q liniowo , jeśli istnieje szereg tak, że
Liczba nazywana jest stopniem zbieżności.
Mówi się, że sekwencja zbiega Q-superliniowo do (tj. Szybciej niż liniowo) jeśli
i mówi się, że zbiegają się Q-podliniowo do (tj. wolniej niż liniowo) jeśli
Jeśli sekwencja zbiega się podliniowo i dodatkowo
wtedy mówi się, że ciąg zbiega się logarytmicznie do . Zauważ, że w przeciwieństwie do poprzednich definicji, zbieżność logarytmiczna nie jest nazywana „logarytmiczną Q”.
W celu dalszej klasyfikacji zbieżności, kolejność zbieżności jest zdefiniowana w następujący sposób. Sekwencja mówi się zbliżały się, aby do na jeśli
dla jakiejś dodatniej stałej (niekoniecznie mniej niż 1 jeśli ). W szczególności zbieżność z porządkiem
- nazywa się zbieżnością liniową (jeśli ),
- nazywa się zbieżnością kwadratową ,
- nazywa się konwergencją sześcienną ,
- itp.
Niektóre źródła wymagają, aby było to ściśle większe niż to, czego wymaga dany przypadek , najlepiej traktować osobno. Nie jest jednak konieczne, aby była to liczba całkowita. Na przykład metoda siecznych , przy zbieżności do regularnego, prostego pierwiastka , ma rząd φ ≈ 1,618.
W powyższych definicjach „Q-” oznacza „iloraz”, ponieważ terminy są definiowane przy użyciu ilorazu między dwoma kolejnymi terminami. Często jednak „Q” jest usuwany i sekwencja jest tylko mówi się, że zbieżność liniowej , kwadratowej zbieżności itd
Zamów wycenę
Praktyczną metodą obliczenia kolejności zbieżności dla sekwencji jest obliczenie następującego ciągu, który jest zbieżny do
Definicja zbieżności R.
Definicje zbieżności Q mają wadę polegającą na tym, że nie obejmują niektórych sekwencji, takich jak sekwencja poniżej, które zbiegają się dość szybko, ale których szybkość jest zmienna. Dlatego definicja stopy konwergencji została rozszerzona w następujący sposób.
Załóżmy, że zbiega się do . Sekwencja mówi się, że zbiegają R liniowo , jeśli istnieje ciąg taki sposób, że
i zbiega Q-liniowo do zera. Przedrostek „R-” oznacza „root”.
Przykłady
Rozważ sekwencję
Można wykazać, że ta sekwencja jest zbieżna do . Aby określić typ zbieżności, podłączamy sekwencję do definicji zbieżności Q-liniowej,
W ten sposób stwierdzamy, że zbieżność Q jest liniowa i ma współczynnik zbieżności równy . Mówiąc bardziej ogólnie, dla każdego sekwencja jest zbieżna liniowo z szybkością .
Sekwencja
również zbiega liniowo do 0 ze stopniem 1/2 zgodnie z definicją zbieżności R, ale nie zgodnie z definicją zbieżności Q. (Zauważ, że jest to funkcja floor , która daje największą liczbę całkowitą mniejszą lub równą ).
Sekwencja
zbiega superliniowo. W rzeczywistości jest kwadratowo zbieżny.
Wreszcie sekwencja
zbiega się podliniowo i logarytmicznie.
Szybkość zbieżności dla metod dyskretyzacji
Podobna sytuacja ma miejsce w przypadku metod dyskretyzacji. Ważnym parametrem dla szybkości zbieżności nie jest liczba iteracji k , ale liczba punktów siatki i odstępy między siatkami. W tym przypadku liczba punktów siatki n w procesie dyskretyzacji jest odwrotnie proporcjonalna do rozstawu siatki.
W tym przypadku mówi się , że sekwencja zbiega się do L z porządkiem q, jeśli istnieje stała C taka, że
To jest napisane w użyciu asymptotyczne tempo wzrostu .
Jest to odpowiednia definicja przy omawianiu metod kwadratury numerycznej lub rozwiązywania zwykłych równań różniczkowych .
Praktyczna metoda oszacowania kolejność zbieżności dla metody dyskretyzacji to wybrać wielkości kroku i i obliczenia wynikowych błędów i . Kolejność zbieżności jest następnie przybliżana za pomocą następującego wzoru:
Przykłady (ciąg dalszy)
Sekwencja z została wprowadzona powyżej. Sekwencja ta zbiega się z porządkiem 1 zgodnie z konwencją metod dyskretyzacji.
Sekwencja z , która również została wprowadzona powyżej, zbiega się z porządkiem q dla każdej liczby q . Mówi się, że zbiegają się wykładniczo, stosując konwencję metod dyskretyzacji. Jednak jest zbieżny tylko liniowo (to znaczy z porządkiem 1) przy użyciu konwencji dla metod iteracyjnych.
Kolejność zbieżności metody dyskretyzacji jest związana z jej globalnym błędem obcięcia (GTE) .
Przyspieszenie konwergencji
Istnieje wiele metod zwiększania stopnia zbieżności danego ciągu, tj. Przekształcania danej sekwencji w jedną szybciej zbiegającą się do tej samej granicy. Takie techniki są ogólnie znane jako „ przyspieszenie szeregowe ”. Celem przekształconej sekwencji jest zmniejszenie kosztu obliczeniowego obliczeń. Jednym z przykładów przyspieszenia szeregowego jest proces Aitkena delta-kwadrat .
Bibliografia
- ^ Ruye, Wang (12.02.2015). „Kolejność i stopień zbieżności” . hmc.edu . Źródło 2020-07-31 .
- ^ Senning, Jonathan R. „Obliczanie i szacowanie tempa konwergencji” (PDF) . gordon.edu . Źródło: 07.08.2020 .
- ^ a b Bockelman, Brian (2005). „Stawki konwergencji” . math.unl.edu . Źródło 2020-07-31 .
- ^ Van Tuyl, Andrew H. (1994). „Przyspieszenie zbieżności rodziny logarytmicznie zbieżnych sekwencji” (PDF) . Matematyka obliczeniowa . 63 (207): 229–246. doi : 10.2307 / 2153571 . JSTOR 2153571 . Źródło 02-08-2020 .
- ^ Porta, FA (1989). „On Q-Order i R-Order of Convergence” (PDF) . Journal of Optimization Theory and Applications . 63 (3): 415–431. doi : 10.1007 / BF00939805 . S2CID 116192710 . Źródło 2020-07-31 .
- ^ a b Nocedal, Jorge; Wright, Stephen J. (2006). Optymalizacja numeryczna (wyd. 2). Berlin, Nowy Jork: Springer-Verlag . ISBN 978-0-387-30303-1 .
- ^ Senning, Jonathan R. „Obliczanie i szacowanie tempa konwergencji” (PDF) . gordon.edu . Źródło: 07.08.2020 .
Literatura
Prosta definicja jest używana w
- Michelle Schatzman (2002), Analiza numeryczna: wprowadzenie matematyczne , Clarendon Press, Oxford. ISBN 0-19-850279-6 .
Rozszerzona definicja jest używana w
- Walter Gautschi (1997), Analiza numeryczna: wprowadzenie, Birkhäuser, Boston. ISBN 0-8176-3895-4 .
- Endre Süli i David Mayers (2003), Wprowadzenie do analizy numerycznej, Cambridge University Press. ISBN 0-521-00794-1 .
Definicja Big O jest używana w programie
- Richard L. Burden i J. Douglas Faires (2001), Numerical Analysis (7. wyd.), Brooks / Cole. ISBN 0-534-38216-9 .Linki zewnętrzne
Terminy Q-linear i R-linear są używane w; Definicja Big O podczas korzystania z serii Taylora jest używana w programie
- Nocedal Jorge; Wright, Stephen J. (2006). Optymalizacja numeryczna (wyd. 2). Berlin, Nowy Jork: Springer-Verlag . s. 619 + 620. ISBN 978-0-387-30303-1 . .