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

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

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

Скорость конвергенции $\mu$ также называется асимптотической константой ошибки .Обратите внимание, что эта терминология не стандартизирована, и некоторые авторы будут использовать скорость , гдев этой статье используется порядок (например, ).

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

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

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

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

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

Предположим, что последовательность $(x_{k})$ сходится к числу $L$. Говорят, что последовательность сходится с порядком $q$ к $L$, и со скоростью сходимости из $\mu$, если

$$\lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|^{q}}}=\mu$$ (Определение 1)

для некоторой положительной константы $\mu \in (0,\infty )$ если $q>1$, и $\mu \in (0,1)$ если $q=1$. Однако не обязательно, чтобы $q$ быть целым числом. Например, метод секущей при сходимости к правильному простому корню имеет порядок φ ≈ 1,618.

Сближение с порядком

• $q=1$ называется линейной сходимостью, если $\mu \in (0,1)$, и говорят, что последовательность Q-линейно сходится к $L$.
• $q=2$ называется квадратичной сходимостью.
• $q=3$ называется кубической сходимостью.
• и т. д.

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

Практический метод расчета порядка сходимости последовательности, сгенерированной итерацией с фиксированной точкой, состоит в вычислении следующей последовательности, которая сходится к $q$: $$q\approx {\frac {\log \left|\displaystyle {\frac {x_{k+1}-x_{k}}{x_{k}-x_{k-1}}}\right|}{\log \left|\displaystyle {\frac {x_{k}-x_{k-1}}{x_{k-1}-x_{k-2}}}\right|}}.$$

О численном приближении точного значения численным методом порядка q см.

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

Помимо определенного ранее Q-линейной сходимости, существует несколько других определений Q-сходимости. Учитывая определение 1, определенное выше, говорят, что последовательность сходится Q-суперлинейно к $L$ (т.е. быстрее, чем линейно) во всех случаях, когда $q>1$ а также случай $q=1,\mu =0$. Учитывая определение 1, говорят, что последовательность Q-сублинейно сходится к $L$ (т.е. медленнее, чем линейно), если $q=1,\mu =1$. Последовательность $(x_{k})$ сходится логарифмически к $L$ если последовательность сходится сублинейно и, кроме того, если $$\lim _{k\to \infty }{\frac {|x_{k+1}-x_{k}|}{|x_{k}-x_{k-1}|}}=1.$$Обратите внимание, что в отличие от предыдущих определений логарифмическая сходимость не называется «Q-логарифмической».

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

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

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

Предположим, что $(x_{k})$ сходится к $L$. Говорят, что последовательность R-линейно сходится к $L$ если существует последовательность $(\varepsilon _{k})$ такой, что $$|x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k\,,$$и $(\varepsilon _{k})$ сходится Q-линейно к нулю. Префикс «R-» означает «корень».

Примеры

Рассмотрим последовательность $$(a_{k})=\left\{1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},{\frac {1}{32}},\ldots ,{\frac {1}{2^{k}}},\dots \right\}.$$Можно показать, что эта последовательность сходится к $L=0$. Чтобы определить тип сходимости, мы подставляем последовательность в определение Q-линейной сходимости: $$\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}}.$$Таким образом, мы находим, что $(a_{k})$ сходится Q-линейно и имеет скорость сходимости $\mu =1/2$.В более общем смысле для любого $c\in \mathbb {R} ,\mu \in (-1,1)$, последовательность $(c\mu ^{k})$ сходится линейно со скоростью $|\mu |$.

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

Последовательность $$(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\}$$сходится сверхлинейно. Фактически оно квадратично сходится.

Наконец, последовательность $$(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\}$$сходится сублинейно и логарифмически.

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

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

Аналогичная ситуация существует для методов дискретизации, предназначенных для аппроксимации функции $y=f(x)$, который может быть интегралом, аппроксимируемым числовой квадратурой , или решением обыкновенного дифференциального уравнения (см. пример ниже). Метод дискретизации генерирует последовательность ${y_{0},y_{1},y_{2},y_{3},...}$, где каждый последующий $y_{j}$ является функцией $y_{j-1},y_{j-2},...$ вместе с шагом сетки $h$ между последовательными значениями независимой переменной $x$. Важным параметром здесь является скорость сходимости $y=f(x)$ это шаг сетки $h$, обратно пропорционально количеству точек сетки, т.е. количеству точек в последовательности, необходимых для достижения заданного значения $x$.

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

$|y_{n}-f(x_{n})|<Ch^{q}{\text{ for all }}n.$

Это написано как $|y_{n}-f(x_{n})|={\mathcal {O}}(h^{q})$ используя большое обозначение O.

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

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

$q\approx {\frac {\log(e_{\text{new}}/e_{\text{old}})}{\log(h_{\text{new}}/h_{\text{old}})}},$

что происходит из-за записи ошибки усечения на старом и новом шагах сетки, как

$e=|y_{n}-f(x_{n})|={\mathcal {O}}(h^{q}).$

Ошибка $e$ более конкретно, это глобальная ошибка усечения (GTE), поскольку она представляет собой сумму ошибок, накопленных по всем $n$ итераций, в отличие от локальной ошибки усечения (LTE) всего за одну итерацию.

Пример методов дискретизации

Рассмотрим обыкновенное дифференциальное уравнение

${\frac {dy}{dx}}=-\kappa y$

с начальным состоянием $y(0)=y_{0}$. Мы можем решить это уравнение, используя схему прямого Эйлера для числовой дискретизации :

${\frac {y_{n+1}-y_{n}}{h}}=-\kappa y_{n},$

который генерирует последовательность

$y_{n+1}=y_{n}(1-h\kappa ).$

С точки зрения $y(0)=y_{0}$, эта последовательность выглядит следующим образом, исходя из биномиальной теоремы : $$y_{n}=y_{0}(1-h\kappa )^{n}=y_{0}\left(1-nh\kappa +n(n-1){\frac {h^{2}\kappa ^{2}}{2}}+....\right).$$

Точное решение этой ОДУ: $y=f(x)=y_{0}\exp(-\kappa x)$, что соответствует следующему разложению Тейлора в $h\kappa$ для $h\kappa \ll 1$: $$f(x_{n})=f(nh)=y_{0}\exp(-\kappa nh)=y_{0}\left[\exp(-\kappa h)\right]^{n}=y_{0}\left(1-h\kappa +{\frac {h^{2}\kappa ^{2}}{2}}+....\right)^{n}=y_{0}\left(1-nh\kappa +{\frac {n^{2}h^{2}\kappa ^{2}}{2}}+...\right).$$

В этом случае ошибка усечения равна

$e=|y_{n}-f(x_{n})|={\frac {nh^{2}\kappa ^{2}}{2}}={\mathcal {O}}(h^{2}),$

так $(y_{n})$ сходится к $f(x_{n})$ со скоростью сходимости $q=2$.

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

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

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

Рекуррентные последовательности и фиксированные точки

Случай повторяющихся последовательностей $x_{n+1}:=f(x_{n})$ который возникает в динамических системах и в контексте различных теорем о неподвижной точке, представляет особый интерес. Предполагая, что соответствующие производные f непрерывны, можно (легко) показать, что для фиксированной точки $f(p)=p$ такой, что $|f'(p)|<1$, имеется как минимум линейная сходимость для любого начального значения $x_{0}$ достаточно близко к p . Если $|f'(p)|=0$ и $|f''(p)|<1$, то имеет место по крайней мере квадратичная сходимость и так далее. Если $|f'(p)|>1$, то у нас есть отталкивающая фиксированная точка , и никакое начальное значение не приведет к созданию последовательности, сходящейся к p (если только мы не перейдем непосредственно к самой точке p ).

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

Основная статья: серийное ускорение

Существует множество методов увеличения скорости сходимости данной последовательности, т. е. преобразования данной последовательности в более быстро сходящуюся к тому же пределу. Такие методы обычно известны как « последовательное ускорение ». Цель состоит в том, чтобы снизить вычислительные затраты на аппроксимацию предела преобразованной последовательности. Одним из примеров последовательного ускорения является процесс Эйткена с квадратом дельты . Эти методы вообще (и метод Эйткена в частности) не повышают порядок сходимости и полезны только в том случае, если изначально сходимость не быстрее линейной: если $(x_{n})$ сходимости линейно, получается последовательность $(a_{n})$ которая по-прежнему сходится линейно (за исключением патологически спроектированных особых случаев), но быстрее в том смысле, что $\lim(a_{n}-L)/(x_{n}-L)=0$. С другой стороны, если сходимость уже имеет порядок ≥ 2, метод Эйткена не принесет улучшения.

Литература

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

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

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

• Вальтер Гаучи (1997), Численный анализ: введение, Биркхойзер, Бостон. ISBN   0-8176-3895-4 .
• Эндре Сюли и Дэвид Майерс (2003), Введение в численный анализ, Cambridge University Press. ISBN   0-521-00794-1 .

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

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

Термины Q-линейный и R-линейный используются в

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