Скорость сходимости - Rate of convergence

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

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

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

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

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

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

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

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

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

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

Номер ${\displaystyle \mu }$ называется скорость сходимости.^[2]

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

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

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

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

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

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

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

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

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

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

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

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

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

Оценка заказа

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

${\displaystyle q\approx {\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|}}.}$^[6]

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

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

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

${\displaystyle |x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k\,,}$

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

Примеры

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

${\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 L=0}$. Чтобы определить тип сходимости, мы подставляем последовательность в определение Q-линейной сходимости,

${\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}}}={\frac {1}{2}}.}$

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

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

${\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-сходимости. (Обратите внимание, что ${\displaystyle \lfloor x\rfloor }$ это функция пола, что дает наибольшее целое число, меньшее или равное ${\displaystyle x}$.)

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

${\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 (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\}}$

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

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

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

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

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

${\displaystyle |x_{n}-L|<Cn^{-q}{\text{ for all }}n.}$

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

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

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

${\displaystyle q\approx {\frac {\log(e_{\text{new}}/e_{\text{old}})}{\log(h_{\text{new}}/h_{\text{old}})}}.}$^{[нужна цитата ]}

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

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

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

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

Ускорение конвергенции

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

Рекомендации

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

Литература

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

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

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

• http://web.mit.edu/rudin/www/MukherjeeRuSc11COLT.pdf
• Уолтер Гаучи (1997), Численный анализ: введение, Биркхойзер, Бостон. ISBN  0-8176-3895-4.
• Эндре Сюли и Дэвид Майерс (2003), Введение в численный анализ, Издательство Кембриджского университета. ISBN  0-521-00794-1.

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

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

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

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