Скорость сходимости

редактировать

В числовом анализе, порядок сходимости и скорость сходимости сходящейся последовательности - это величины, которые представляют, насколько быстро последовательность приближается к своему пределу. Последовательность $(xn) {\ displaystyle (x_ {n})}$ $(x_ {n})$ , сходящаяся к $x ∗ {\ displaystyle x ^ {*}}$ $x ^ {*}$ , называется иметь порядок сходимости $q ≥ 1 {\ displaystyle q \ geq 1}$ $q \ geq 1$ и скорость сходимости $μ {\ displaystyle \ mu}$ $\ mu$ , если

lim n → ∞ | x n + 1 - x ∗ | | x n - x ∗ | q = μ. {\ displaystyle \ lim _ {n \ rightarrow \ infty} {\ frac {\ left | x_ {n + 1} -x ^ {*} \ right |} {\ left | x_ {n} -x ^ {*} \ right | ^ {q}}} = \ mu.}

{\ displaystyle \ lim _ {n \ rightarrow \ infty} {\ frac {\ left | x_ {n + 1} -x ^ {*} \ right |} {\ left | x_ {n} -x ^ {*} \ right | ^ {q}}} = \ mu.}

Скорость сходимости $μ {\ displaystyle \ mu}$ $\ mu$ также называется константой асимптотической ошибки.

На практике скорость и порядок сходимости дают полезную информацию при использовании итерационных методов для вычисления численных приближений. Если порядок сходимости выше, то обычно требуется меньше итераций, чтобы получить полезное приближение. Строго говоря, однако, асимптотическое поведение последовательности не дает окончательной информации ни о какой конечной части последовательности.

Подобные концепции используются для методов дискретизации. Решение дискретизированной задачи сходится к решению непрерывной задачи, когда размер сетки стремится к нулю, а скорость сходимости является одним из факторов эффективности метода. Однако терминология в этом случае отличается от терминологии для итерационных методов.

Последовательное ускорение - это набор методов для повышения скорости сходимости последовательной дискретизации. Такое ускорение обычно достигается с помощью преобразований последовательности.

Содержание

1 Скорость сходимости для итерационных методов
- 1.1 Определения Q-сходимости
  - 1.1.1 Оценка порядка
- 1.2 Определение R-сходимости
- 1.3 Примеры
2 Скорость сходимости для методов дискретизации
- 2.1 Примеры (продолжение)
3 Ускорение сходимости
4 Ссылки
5 Литература

Скорость сходимости для итерационных методов

Определения Q-сходимости

Предположим, что последовательность $(xk) {\ displaystyle (x_ {k})}$ $(x_k)$ сходится к числу $L {\ Displaystyle L}$ $L$ . Говорят, что последовательность сходится Q-линейно к $L {\ displaystyle L}$ $L$ , если существует число $μ ∈ (0, 1) {\ displaystyle \ mu \ in (0, 1)}$ ${\ displaystyle \ mu \ in (0,1)}$ такое, что

lim k → ∞ | х к + 1 - L | | х к - L | = μ. {\ displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = \ mu.}

{\ displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k } -L |}} = \ mu.}

Число $μ {\ displaystyle \ mu}$ $\ mu$ называется скоростью сходимости.

Говорят, что последовательность сходится Q-суперлинейно к $L {\ displaystyle L}$ $L$ (т.е. быстрее, чем линейно), если

lim k → ∞ | х к + 1 - L | | х к - L | = 0 {\ displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = 0}

{\ displaystyle \ lim _ {k \ to \ infty} { \ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = 0}

и это сказано, что сходится Q-сублинейно к $L {\ displaystyle L}$ $L$ (т.е. медленнее, чем линейно), если

lim k → ∞ | х к + 1 - L | | х к - L | = 1. {\ displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L |}} = 1.}

{\ displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} - L |}} = 1.}

Если последовательность сходится сублинейно и дополнительно

lim k → ∞ | х к + 2 - х к + 1 | | х к + 1 - х к | Знак равно 1, {\ displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 2} -x_ {k + 1} |} {| x_ {k + 1} -x_ {k} | }} = 1,}

{\ displaystyle \ lim _ {k \ to \ infty} {\ frac {| x_ {k + 2} -x_ {k + 1} |} {| x_ {к + 1} -x_ {k} |}} = 1,}

, тогда говорят, что последовательность $(xk) {\ displaystyle (x_ {k})}$ $(x_k)$ логарифмически сходится к $L {\ displaystyle L}$ $L$ . Обратите внимание, что в отличие от предыдущих определений, логарифмическая сходимость не называется «Q-логрифмической».

Для дальнейшей классификации сходимости порядок сходимости определяется следующим образом. Говорят, что последовательность сходится с порядком $q {\ displaystyle q}$ $q$ к $L {\ displaystyle L}$ $L$ для $q ≥ 1 {\ displaystyle q \ geq 1}$ $q \ geq 1$ , если

lim k → ∞ | х к + 1 - L | | х к - L | q < M {\displaystyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|^{q}}}

{\ displaystyle \ lim _ { k \ to \ infty} {\ frac {| x_ {k + 1} -L |} {| x_ {k} -L | ^ {q}}} <M}

для некоторой положительной константы $M>0 {\ displaystyle M>0}$ $M>0$ (не обязательно меньше 1). В частности, сходимость с порядком

$q = 1 {\ displaystyle q = 1}$ ${\ displaystyle q = 1}$ называется линейной сходимостью,
$q = 2 {\ displaystyle q = 2}$ $q = 2$ называется квадратичной сходимостью,
$q = 3 {\ displaystyle q = 3}$ ${\ displaystyle q = 3}$ называется кубической сходимостью,
и т. д.

Некоторые источники требуют, чтобы $q {\ displaystyle q}$ $q$ было строго больше, чем $1 {\ displaystyle 1}$ $1$ . Однако не обязательно, чтобы $q {\ displaystyle q}$ $q$ было целым числом. Например, метод секущей, при сходимости к регулярному, простой корень, имеет порядок φ ≈ 1,618.

В приведенных выше определениях «Q-» означает «частное», потому что термины определены используя частное между двумя последовательными терминами. Однако часто "Q-" опускается, и просто говорят, что последовательность имеет линейную сходимость, квадратичную сходимость и т. Д.

Оценка порядка

Практический метод вычисления порядка сходимости для последовательности - вычислить следующую последовательность, которая сходится к $q {\ displaystyle q}$ $q$

q ≈ log ⁡ | х к + 1 - х к х к - х к - 1 | журнал ⁡ | х к - х к - 1 х к - 1 - х к - 2 |. {\ displaystyle q \ приблизительно {\ frac {\ log \ left | {\ frac {x_ {k + 1} -x_ {k}} {x_ {k} -x_ {k-1}}}} \ right |} { \ log \ left | {\ frac {x_ {k} -x_ {k-1}} {x_ {k-1} -x_ {k-2}}} \ right |}}.}

{\ displaystyle q \ приблизительно {\ frac {\ log \ left | {\ frac {x_ {k + 1} -x_ {k}} {x_ {k} -x_ {k-1}) }} \ right |} {\ log \ left | {\ frac {x_ {k} -x_ {k-1}} {x_ {k-1} -x_ {k-2}}} \ right |}}. }

R-конвергенция определение

Определения Q-сходимости имеют недостаток в том, что они не включают некоторые последовательности, такие как последовательность $(bk) {\ displaystyle (b_ {k})}$ ${\ displaystyle (b_ {k})}$ ниже, которые сходятся достаточно быстро, но скорость варьируется. Таким образом, определение скорости сходимости расширяется следующим образом.

Предположим, что $(x k) {\ displaystyle (x_ {k})}$ $(x_k)$ сходится к $L {\ displaystyle L}$ $L$ . Говорят, что последовательность сходится R-линейно к $L {\ displaystyle L}$ $L$ , если существует, то существует последовательность $(ε k) {\ displaystyle (\ varepsilon _ {k}) }$ ${\ displaystyle (\ varepsilon _ {k})}$ такие, что

| х к - L | ≤ ε К для всех k, {\ displaystyle | x_ {k} -L | \ leq \ varepsilon _ {k} \ quad {\ text {для всех}} k \,,}

{\ displaystyle | x_ {k} -L | \ leq \ varepsilon _ {k} \ quad {\ text {для всех}} k \,, }

и $(ε k) {\ displaystyle (\ varepsilon _ {k})}$ ${\ displaystyle (\ varepsilon _ {k})}$ сходится Q-линейно к нулю. Префикс «R-» означает «корень».

Примеры

Рассмотрим последовательность

(a k) = {1, 1 2, 1 4, 1 8, 1 16, 1 32,…, 1 2 k,... }. {\ displaystyle (a_ {k}) = \ left \ {1, {\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1} {8}}, { \ frac {1} {16}}, {\ frac {1} {32}}, \ ldots, {\ frac {1} {2 ^ {k}}},... \ right \}.}

{\ displaystyle (a_ {k}) = \ left \ {1, {\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1 } {8}}, {\ frac {1} {16}}, {\ frac {1} {32}}, \ ldots, {\ frac {1} {2 ^ {k}}},... \ вправо \}.}

Можно показать, что эта последовательность сходится к $L = 0 {\ displaystyle L = 0}$ $L = 0$ . Чтобы определить тип сходимости, мы подставляем последовательность в определение Q-линейной сходимости,

lim k → ∞ | 1/2 k + 1 - 0 | | 1/2 к - 0 | = lim К → ∞ 2 К 2 К + 1 знак равно 1 2. {\ Displaystyle \ lim _ {к \ к \ infty} {\ frac {\ left | 1/2 ^ {k + 1} -0 \ right |} {\ left | 1/2 ^ {k} -0 \ right |}} = \ lim _ {k \ to \ infty} {\ frac {2 ^ {k}} {2 ^ {k + 1}}} = {\ frac {1} {2}}.}

{\ displaystyle \ lim _ {k \ to \ infty} {\ frac {\ left | 1/2 ^ {k + 1} -0 \ right |} {\ left | 1/2 ^ {k} -0 \ right |}} = \ lim _ {k \ to \ infty} {\ frac {2 ^ {k}} {2 ^ {k + 1}}} = {\ гидроразрыв {1} {2}}.}

Таким образом, мы находим, что $(ak) {\ displaystyle (a_ {k})}$ $(a_ {k})$ сходится Q-линейно и имеет скорость сходимости $μ = 1/2 {\ displaystyle \ mu = 1/2}$ ${\ displaystyle \ mu = 1/2}$ . В более общем смысле, для любого $c ∈ R, μ ∈ (- 1, 1) {\ displaystyle c \ in \ mathbb {R}, \ mu \ in (-1,1)}$ ${\ displaystyle c \ in \ mathbb {R}, \ mu \ in (-1,1)}$ , последовательность $(c μ k) {\ displaystyle (c \ mu ^ {k})}$ ${\ displaystyle (c \ mu ^ {k})}$ сходится линейно со скоростью $μ {\ displaystyle \ mu}$ $\ mu$ .

Последовательность

(bk) = {1, 1, 1 4, 1 4, 1 16, 1 16,…, 1 4 ⌊ К 2 ⌋,…} {\ displaystyle (b_ {k}) = \ left \ {1,1, {\ frac {1} {4}}, {\ frac {1} {4}}, {\ frac {1} {16}}, {\ frac {1} {16}}, \ ldots, {\ frac {1} {4 ^ {\ left \ lfloor {\ frac {k} {2}} \ right \ rfloor}}}, \, \ ldots \ right \}}

{\ displaystyle (b_ {k}) = \ left \ {1,1, {\ frac {1} {4} }, {\ frac {1} {4}}, {\ frac {1} {16}}, {\ frac {1} {16}}, \ ldots, {\ frac {1} {4 ^ {\ left \ lfloor {\ frac {k} {2}} \ right \ rfloor}}}, \, \ ldots \ right \}}

также линейно сходится к 0 со скоростью 1 / 2 по определению R-сходимости, но не по определению Q-сходимости. (Обратите внимание, что $⌊ x ⌋ {\ displaystyle \ lfloor x \ rfloor}$ $\ lfloor x \ rfloor$ - это функция пола, которая дает наибольшее целое число, которое меньше или равно $x {\ displaystyle x}$ $x$ .)

Последовательность

(ck) = {1 2, 1 4, 1 16, 1 256, 1 65, 536,…, 1 2 2 к,…} {\ displaystyle (c_ {k}) = \ left \ {{\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1} {16 }}, {\ frac {1} {256}}, {\ frac {1} {65, \! 536}}, \ ldots, {\ frac {1} {2 ^ {2 ^ {k}}}}, \ ldots \ right \}}

{\ displaystyle (c_ {k}) = \ left \ {{\ frac {1} {2}}, {\ frac {1} {4}}, {\ frac {1} {16}}, {\ frac {1} {256}}, {\ frac {1} {65, \! 536}}, \ ldots, {\ frac {1} {2 ^ {2 ^ {k}}}}, \ ldots \ right \}}

сходится сверхлинейно. Фактически, оно сходится квадратично.

Наконец, последовательность

(dk) = {1, 1 2, 1 3, 1 4, 1 5, 1 6,…, 1 k + 1,…} {\ displaystyle (d_ { k}) = \ left \ {1, {\ frac {1} {2}}, {\ frac {1} {3}}, {\ frac {1} {4}}, {\ frac {1} { 5}}, {\ frac {1} {6}}, \ ldots, {\ frac {1} {k + 1}}, \ ldots \ right \}}

{\ displaystyle (d_ {k}) = \ left \ {1, {\ frac {1} {2}}, {\ frac {1} {3}}, {\ frac {1 } {4}}, {\ frac {1} {5}}, {\ frac {1} {6}}, \ ldots, {\ frac {1} {k + 1}}, \ ldots \ right \} }

сходится сублинейно и логарифмически.

График, показывающий разные скорости сходимости последовательностей ak, bk, ck и dk.

Линейная, линейная, суперлинейная (квадратичная) и сублинейная скорости сходимости

Скорость сходимости для методов дискретизации

Аналогичная ситуация существует для методов дискретизации. Здесь важным параметром для скорости сходимости является не номер итерации k, а количество узлов сетки и шаг сетки. В этом случае количество узлов сетки n в процессе дискретизации обратно пропорционально шагу сетки.

В этом случае последовательность $(xn) {\ displaystyle (x_ {n})}$ $(x_ {n})$ , как говорят, сходится к L с порядком q, если существует константа C такая что

| x n - L | < C n − q for all n. {\displaystyle |x_{n}-L|

{\ displaystyle | x_ {n} -L | <Cn ^ {- q} {\ text {для всех}} n.}

Это записывается как $| x n - L | = O (n - q) {\ displaystyle | x_ {n} -L | = {\ mathcal {O}} (n ^ {- q})}$ ${\ displaystyle | x_ {n} -L | = {\ mathcal {O}} (n ^ {- q})}$ с использованием нотации большого O.

Это подходящее определение при обсуждении методов числовой квадратуры или решения обыкновенных дифференциальных уравнений.

Практическим методом оценки порядка сходимости для метода дискретизации является выбор размеров шага $h новый {\ displaystyle h _ {\ text {new}}}$ ${\ displaystyle h _ {\ text {new}}}$ и $h old {\ displaystyle h _ {\ text {old}}}$ ${\ displaystyle h _ {\ text {old}}}$ и вычислите полученные ошибки $e new {\ displaystyle e _ {\ text {new}}}$ ${\ displaystyle e _ {\ text {new}}}$ и $e old {\ displaystyle e _ {\ text {old}}}$ ${ \ displaystyle е _ {\ текст {старый}}}$ . Затем порядок сходимости аппроксимируется следующей формулой:

q ≈ log ⁡ (e new / e old) log ⁡ (h new / h old). {\ displaystyle q \ приблизительно {\ frac {\ log (e _ {\ text {new}} / e _ {\ text {old}})} {\ log (h _ {\ text {new}} / h _ {\ text { old}})}}.}

{\ displaystyle q \ приблизительно {\ frac {\ log (e _ {\ text {new}} / e _ {\ text {old}})} {\ log (h _ {\ text {новый}} / ч _ {\ текст {старый}})}}.}

Примеры (продолжение)

Последовательность $(dk) {\ displaystyle (d_ {k})}$ $(d_ { k})$ с $dk = 1 / (k + 1) {\ displaystyle d_ {k} = 1 / (k + 1)}$ ${\ displaystyle d_ {k} = 1 / (k + 1)}$ было введено выше. Эта последовательность сходится с порядком 1. согласно соглашению для методов дискретизации.

Последовательность $(ak) {\ displaystyle (a_ {k})}$ $(a_ {k})$ с $ak = 2 - k {\ displaystyle a_ {k} = 2 ^ {- k}}$ ${\ displaystyle a_ {k} = 2 ^ {- k}}$ , который также был введен выше, сходится с порядком q для каждого числа q. Говорят, что он экспоненциально сходится с использованием соглашения о методах дискретизации. Однако он сходится только линейно (то есть с порядком 1), используя соглашение для итерационных методов.

Порядок сходимости метода дискретизации связан с его глобальной ошибкой усечения (GTE).

Ускорение сходимости

Существует множество методов для увеличения скорости сходимости заданной последовательности, то есть для преобразования заданной последовательности в последовательность, сходящуюся быстрее до того же предела. Такие методы обычно известны как «последовательное ускорение ». Цель преобразованной последовательности - уменьшить вычислительные затраты вычисления. Одним из примеров последовательного ускорения является процесс вычисления квадрата дельты Эйткена.

Ссылки

^Руй, Ван (2015-02-12). «Порядок и скорость сходимости». hmc.edu. Проверено 31 июля 2020 г.
^ Бокельман, Брайан (2005). «Скорость конвергенции». math.unl.edu. Проверено 31 июля 2020 г.
^Ван Туйл, Эндрю Х. (1994). «Ускорение сходимости семейства логарифмически сходящихся последовательностей» (PDF). Математика вычислений. 63 (207): 229–246. DOI : 10.2307 / 2153571. JSTOR 2153571. Проверено 2 августа 2020 г.
^Порта, Ф. А. (1989). «О Q-порядке и R-порядке сходимости» (PDF). Журнал теории оптимизации и приложений. 63 (3): 415–431. doi : 10.1007 / BF00939805. S2CID 116192710. Проверено 31 июля 2020 г.
^ Носедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag. ISBN 978-0-387-30303-1.
^Сеннинг, Джонатан Р. «Вычисление и оценка скорости сходимости» (PDF). gordon.edu. Проверено 07 августа 2020 г.

Литература

Простое определение используется в

Мишель Шацман (2002), Численный анализ: введение в математику, Clarendon Press, Oxford. ISBN 0-19-850279-6.

Расширенное определение используется в

http://web.mit.edu/rudin/www/MukherjeeRuSc11COLT.pdf
Walter Gautschi (1997), Численный анализ: введение, Birkhäuser, Boston. ISBN 0-8176-3895-4.
Эндре Сюли и Дэвид Майерс (2003), Введение в численный анализ, Cambridge University Press. ISBN 0-521-00794-1.

Определение Big O используется в

Ричард Л. Бёрден и Дж. Дуглас Фейрес (2001), Численный анализ (7-я ред.), Брукс / Коул. ISBN 0-534-38216-9

Термины Q-линейный и R-линейный используются в; Определение Big O при использовании ряда Тейлора используется в

Nocedal, Jorge; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag. С. 619 + 620. ISBN 978-0-387-30303-1..