В численном анализе , то порядок сходимости и скорость сходимости в виде сходящейся последовательности являются величинами , которые представляют , как быстро последовательность приближается к своему пределу. Последовательность что сходится к имеет порядок сходимости и скорость сходимости если
Скорость сходимости также называется константой асимптотической ошибки . Обратите внимание, что эта терминология не стандартизирована, и некоторые авторы будут использовать курс там, где в этой статье используется порядок (например, [2] ).
На практике скорость и порядок сходимости дают полезную информацию при использовании итерационных методов для расчета численных приближений. Если порядок сходимости выше, то обычно требуется меньше итераций, чтобы получить полезное приближение. Однако, строго говоря, асимптотическое поведение последовательности не дает окончательной информации ни о какой конечной части последовательности.
Аналогичные концепции используются для методов дискретизации . Решение дискретизированной задачи сходится к решению непрерывной задачи, когда размер сетки стремится к нулю, а скорость сходимости является одним из факторов эффективности метода. Однако терминология в этом случае отличается от терминологии итерационных методов.
Ускорение ряда - это набор методов для повышения скорости сходимости дискретизации ряда. Такое ускорение обычно достигается с помощью преобразований последовательности .
Скорость сходимости итерационных методов
Определения Q-сходимости
Предположим, что последовательность сходится к числу . Говорят, что последовательность сходится Q-линейно к если существует номер такой, что
Номер называется скоростью сходимости. [3]
Говорят, что последовательность Q-суперлинейно сходится к (т.е. быстрее, чем линейно), если
и говорят, что он сходится Q-сублинейно к (т.е. медленнее, чем линейно), если
Если последовательность сходится сублинейно и дополнительно
то говорят, что последовательность логарифмически сходится к . [4] Обратите внимание, что в отличие от предыдущих определений, логарифмическая сходимость не называется «Q-логарифмической».
Для дальнейшей классификации сходимости порядок сходимости определяется следующим образом. Говорят, что последовательность сходится с порядком к для если
для некоторой положительной постоянной (не обязательно меньше 1, если ). В частности, сходимость с порядком
- называется линейной сходимостью (если),
- называется квадратичной сходимостью ,
- называется кубической сходимостью ,
- и т.п.
Некоторые источники требуют, чтобы строго больше, чем так как случай требует так что лучше рассматривать отдельно. [5] Однако необязательно, чтобыбыть целым числом. Например, метод секущей при сходимости к правильному простому корню имеет порядок φ ≈ 1,618. [ необходима цитата ]
В приведенных выше определениях «Q-» означает «частное», потому что термины определяются с использованием отношения между двумя последовательными терминами. [6] : 619 Однако часто "Q-" опускается и просто говорят, что последовательность имеет линейную сходимость , квадратичную сходимость и т. Д.
Оценка заказа
Практический метод расчета порядка сходимости последовательности состоит в том, чтобы вычислить следующую последовательность, которая сходится к
Определение R-сходимости
Определения Q-сходимости имеют недостаток в том, что они не включают некоторые последовательности, такие как последовательность ниже, которые сходятся достаточно быстро, но скорость переменная. Поэтому определение скорости сходимости расширяется следующим образом.
Предположим, что сходится к . Говорят, что последовательность R-линейно сходится к если существует последовательность такой, что
а также сходится Q-линейно к нулю. [3] Префикс «R-» означает «корень». [6] : 620
Примеры
Рассмотрим последовательность
Можно показать, что эта последовательность сходится к . Чтобы определить тип сходимости, мы подставляем последовательность в определение Q-линейной сходимости,
Таким образом, мы находим, что сходится Q-линейно и имеет скорость сходимости . В общем, для любого, последовательность сходится линейно со скоростью .
Последовательность
также линейно сходится к 0 со скоростью 1/2 согласно определению R-сходимости, но не согласно определению Q-сходимости. (Обратите внимание, что- функция пола , которая дает наибольшее целое число, которое меньше или равно.)
Последовательность
сходится суперлинейно. Фактически, оно сходится квадратично.
Наконец, последовательность
сходится сублинейно и логарифмически.
Скорость сходимости для методов дискретизации
Аналогичная ситуация существует и для методов дискретизации. Здесь важным параметром для скорости сходимости является не номер итерации k , а количество узлов сетки и шаг сетки. В этом случае количество узлов сетки n в процессе дискретизации обратно пропорционально шагу сетки.
В этом случае последовательность Говорят, что она сходится к L с порядком q, если существует константа C такая, что
Это записывается как используя большое обозначение O .
Это подходящее определение при обсуждении методов численной квадратуры или решения обыкновенных дифференциальных уравнений . [ необходим пример ]
Практический метод оценки порядка сходимости для метода дискретизации - выбор размера шага а также и вычисляем полученные ошибки а также . Затем порядок сходимости аппроксимируется следующей формулой:
- [ необходима цитата ]
Примеры (продолжение)
Последовательность с участием было введено выше. Эта последовательность сходится с порядком 1 согласно соглашению для методов дискретизации. [ почему? ]
Последовательность с участием , который также был введен выше, сходится с порядком q для любого числа q . Говорят, что он экспоненциально сходится с использованием соглашения о методах дискретизации. Однако он сходится только линейно (то есть с порядком 1), используя соглашение для итерационных методов. [ почему? ]
Порядок сходимости метода дискретизации связан с его глобальной ошибкой усечения (GTE) . [ как? ]
Ускорение конвергенции
Существует множество методов для увеличения скорости сходимости заданной последовательности, то есть для преобразования заданной последовательности в одну, сходящуюся быстрее до того же предела. Такие методы обычно известны как « последовательное ускорение ». Цель преобразованной последовательности - снизить вычислительные затраты на вычисления. Одним из примеров последовательного ускорения является процесс вычисления квадрата дельты Эйткена .
Рекомендации
- ^ Ruye, Ван (2015-02-12). «Порядок и скорость сходимости» . hmc.edu . Проверено 31 июля 2020 .
- ^ Сеннинг, Джонатан Р. «Вычисление и оценка скорости сходимости» (PDF) . gordon.edu . Проверено 7 августа 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 . Проверено 7 августа 2020 .
Литература
Простое определение используется в
- Мишель Шацман (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..