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

Дифференциальные уравнения
Дифференциальные уравнения Навье – Стокса, используемые для моделирования воздушного потока вокруг препятствия
Сфера Природные науки Инженерное дело Астрономия Физика Химия Биология Геология Прикладная математика Механика сплошной среды Теория хаоса Динамические системы Социальные науки Экономика Динамика населения
Классификация
Типы Обычный Частичное Дифференциально-алгебраический Интегро-дифференциал Дробное Линейный Нелинейный По типу переменной Зависимые и независимые переменные Автономный Сложный Связано / развязано Точный Однородный  / неоднородный Функции Заказ Оператор Обозначение
Отношение к процессам Разница (дискретный аналог) Стохастик Стохастический частичный Задерживать
Решение
Существование и уникальность Теорема Пикара – Линделёфа Теорема существования Пеано Теорема существования Каратеодори Теорема Коши – Ковалевского
Общие темы Вронскиан Фазовый портрет Фазовое пространство Ляпунов  / Асимптотика  / Экспоненциальная устойчивость Скорость сходимости Серии  / Интегральные решения Численное интегрирование Дельта-функция Дирака
Методы решения Осмотр Метод характеристик Эйлер Формула экспоненциального отклика Конечная разность  ( Кривошип – Николсон ) Заключительный элемент Бесконечный элемент Конечный объем Галёркин Петров – Галеркин Интегрирующий фактор Интегральные преобразования Теория возмущений Рунге-Кутта Разделение переменных Неопределенные коэффициенты Вариация параметров
Люди Исаак Ньютон Готфрид Лейбниц Леонард Эйлер Эмиль Пикар Юзеф Мария Хене-Вроньски Эрнст Линделёф Рудольф Липшиц Огюстен-Луи Коши Джон Крэнк Филлис Николсон Карл Давид Толме Рунге Мартин Кутта
v т е

В численном анализе , то порядок сходимости и скорость сходимости в виде сходящейся последовательности являются величинами , которые представляют , как быстро последовательность приближается к своему пределу. Говорят, что последовательность , сходящаяся к , имеет порядок сходимости и скорость сходимости, если ${\ 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]

Скорость сходимости также называется константой асимптотической ошибки . Обратите внимание, что эта терминология не стандартизирована, и некоторые авторы будут использовать курс там, где в этой статье используется порядок (например, ^[2] ).${\ displaystyle \ mu}$

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

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

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

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

Определения Q-сходимости [ править ]

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

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

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

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

${\ Displaystyle \ lim _ {к \ к \ 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,}$

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

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

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

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

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

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

В приведенных выше определениях «Q-» означает «частное», потому что термины определяются с использованием отношения между двумя последовательными терминами. ^{[6] : 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|}}.}$^[7]

Определение R-конвергенции [ править ]

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

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

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

и сходится Q-линейно к нулю. ^[3] Префикс «R-» означает «корень».^{[6] : 620}${\displaystyle (\varepsilon _{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\}.}$

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

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

Таким образом, мы находим, что сходится Q-линейно и имеет скорость сходимости . В более общем смысле, для любого , последовательность сходится линейно со скоростью .${\displaystyle (a_{k})}$${\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\}}$

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

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

Этот раздел может потребовать очистки для соответствия стандартам качества Википедии . Конкретная проблема заключается в следующем: похоже, существует смесь определения сходимости в отношении точек сетки и размера шага . Раздел должен быть изменен для единообразия и включать и объяснять альтернативные (эквивалентные?) Определения. ${\displaystyle n}$${\displaystyle h}$Пожалуйста, помогите улучшить этот раздел, если можете. ( Август 2020 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

Практический метод для оценки порядка сходимости для метода дискретизации выбрать размер шага и и вычислить результирующие ошибки и . Затем порядок сходимости аппроксимируется следующей формулой:${\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}})}}.}$^{[ необходима цитата ]}

Примеры (продолжение) [ править ]

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

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

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

Ускорение конвергенции [ править ]

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

Ссылки [ править ]

Литература [ править ]

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

• Мишель Шацман (2002), Численный анализ: математическое введение , Clarendon Press, Oxford. 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-linear и R-linear используются в; Определение Big O при использовании ряда Тейлора используется в

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