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

Скорость сходимости математической последовательности

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

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

В практических численных вычислениях асимптотические скорости и порядки сходимости следуют двум общим соглашениям для двух типов последовательностей: первое для последовательностей итераций итеративного численного метода и второе для последовательностей последовательно более точных числовых дискретизаций цели. В формальной математике скорости сходимости и порядки сходимости часто описываются сравнительно с использованием асимптотической нотации, обычно называемой « большой нотацией O », которая может использоваться для охвата обоих предыдущих соглашений; это приложение асимптотического анализа .

Для итеративных методов говорят , что последовательность , которая сходится к , имеет асимптотический порядок сходимости и асимптотическую скорость сходимости, если ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle q\geq 1}$ ${\displaystyle \mu }$

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

В случаях, когда требуется методологическая точность, эти скорости и порядки сходимости известны как скорости и порядки Q-сходимости, сокращенно от фактор-сходимости, поскольку рассматриваемый предел является частным от ошибок. ^[1] Скорость сходимости также может называться асимптотической константой ошибки , и некоторые авторы будут использовать скорость там, где в этой статье используется порядок. ^{[2] Методы} ускорения рядов — это методы улучшения скорости сходимости последовательности частичных сумм ряда и , возможно, также порядка его сходимости. ${\displaystyle \mu }$

Аналогичные концепции используются для последовательностей дискретизаций. Например, в идеале решение дифференциального уравнения, дискретизированного с помощью регулярной сетки, будет сходиться к решению непрерывного уравнения, когда шаг сетки стремится к нулю, и если это так, то асимптотическая скорость и порядок этой сходимости являются важными свойствами метода сетки. Последовательность приближенных сеточных решений некоторой задачи, которая сходится к истинному решению с соответствующей последовательностью регулярных шагов сетки , которые сходятся к 0, называется имеющей асимптотический порядок сходимости и асимптотическую скорость сходимости, если ${\displaystyle (y_{k})}$ ${\displaystyle S}$ ${\displaystyle (h_{k})}$ ${\displaystyle q}$ ${\displaystyle \mu }$

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|y_{k}-S\right|}{h_{k}^{q}}}=\mu ,}$$

где символы абсолютного значения обозначают метрику для пространства решений, такую ​​как равномерная норма . Аналогичные определения применимы также к схемам дискретизации без сетки, таким как полигональные сетки метода конечных элементов или базисные наборы в вычислительной химии : в общем случае соответствующее определение асимптотической скорости будет включать асимптотический предел отношения члена ошибки аппроксимации выше к асимптотической степени порядка параметра масштаба дискретизации ниже. ${\displaystyle \mu }$ ${\displaystyle q}$

В общем случае, сравнительно, одна последовательность , которая сходится к пределу, считается асимптотически сходящейся быстрее, чем другая последовательность , которая сходится к пределу, если ${\displaystyle (a_{k})}$ ${\displaystyle L_{a}}$ ${\displaystyle (b_{k})}$ ${\displaystyle L_{b}}$

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L_{a}\right|}{|b_{k}-L_{b}|}}=0,}$$

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

Асимптотические скорости сходимости для итерационных методов

Определения

Предположим, что последовательность итераций итерационного метода сходится к предельному числу как . Говорят, что последовательность сходится с порядком к и со скоростью сходимости, если предел частных абсолютных разностей последовательных итераций от их предела удовлетворяет ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle k\rightarrow \infty }$ ${\displaystyle q}$ ${\displaystyle L}$ ${\displaystyle \mu }$ ${\displaystyle k\rightarrow \infty }$ ${\displaystyle x_{k},x_{k+1}}$ ${\displaystyle L}$

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

для некоторой положительной константы , если и если . ^{[1] [3] [4]} Другие, более технические определения скорости необходимы, если последовательность сходится, но ^[5] или предел не существует. ^[1] Это определение технически называется Q-сходимостью, сокращением от фактор-сходимости, а скорости и порядки называются скоростями и порядками Q-сходимости, когда необходима эта техническая специфика. § R-сходимость, приведенная ниже, является подходящей альтернативой, когда этот предел не существует. ${\displaystyle \mu \in (0,1)}$ ${\displaystyle q=1}$ ${\displaystyle \mu \in (0,\infty )}$ ${\displaystyle q>1}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=1}$

Последовательности с большими порядками сходятся быстрее, чем с меньшими порядками, а последовательности с меньшими скоростями сходятся быстрее, чем последовательности с большими скоростями для данного порядка. Это поведение «меньшие скорости сходятся быстрее» среди последовательностей одного порядка является стандартным, но оно может быть нелогичным. Поэтому его также часто определяют как скорость; это «количество дополнительных десятичных знаков точности на итерацию» для последовательностей, которые сходятся с порядком 1. ^[1] ${\displaystyle q}$ ${\displaystyle \mu }$ ${\displaystyle -\log _{10}\mu }$

Целые степени являются общими и имеют общие названия. Сходимость с порядком и называется линейной сходимостью , а последовательность, как говорят, сходится линейно к . Сходимость с и любым называется квадратичной сходимостью , а последовательность, как говорят, сходится квадратично . Сходимость с и любым называется кубической сходимостью . Однако не обязательно, чтобы было целым числом. Например, метод секущей при сходимости к правильному простому корню имеет порядок золотого сечения φ ≈ 1,618. ^[6] ${\displaystyle q}$ ${\displaystyle q=1}$ ${\displaystyle \mu \in (0,1)}$ ${\displaystyle L}$ ${\displaystyle q=2}$ ${\displaystyle \mu }$ ${\displaystyle q=3}$ ${\displaystyle \mu }$ ${\displaystyle q}$

Общие названия для целых порядков сходимости связаны с асимптотическим большим обозначением O , где сходимость частного подразумевает Это линейные, квадратичные и кубические полиномиальные выражения, когда это 1, 2 и 3 соответственно. Точнее, пределы подразумевают, что ошибка ведущего порядка в точности равна , что может быть выражено с помощью асимптотического малого обозначения o как ${\textstyle |x_{k+1}-L|=O(|x_{k}-L|^{q}).}$ ${\displaystyle q}$ ${\textstyle \mu |x_{k}-L|^{q},}$ ${\textstyle |x_{k+1}-L|=\mu |x_{k}-L|^{q}+o(|x_{k}-L|^{q}).}$

В общем случае, когда для последовательности или для любой последовательности, которая удовлетворяет , то говорят, что эти последовательности сходятся сверхлинейно (т. е. быстрее, чем линейно). ^[1] Говорят, что последовательность сходится сублинейно (т. е. медленнее, чем линейно), если она сходится и Важно, что неверно говорить, что эти последовательности сублинейного порядка сходятся линейно с асимптотической скоростью сходимости 1. Последовательность сходится логарифмически к , если последовательность сходится сублинейно и также ^[5] ${\displaystyle q>1}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=0,}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-L|}{|x_{k}-L|}}=1.}$ ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\textstyle \lim _{k\to \infty }{\frac {|x_{k+1}-x_{k}|}{|x_{k}-x_{k-1}|}}=1.}$

R-сходимость

Определения скоростей Q-сходимости имеют тот недостаток, что они не отражают естественным образом поведение сходимости последовательностей, которые сходятся, но не сходятся с асимптотически постоянной скоростью на каждом шаге, так что предела Q-сходимости не существует. Одним из классов примеров являются ступенчатые геометрические прогрессии, которые приближаются к своим пределам только через шаг или каждые несколько шагов, например, пример, подробно описанный ниже (где функция пола применяется к ). Определяющие пределы Q-линейной сходимости не существуют для этой последовательности, потому что одна подпоследовательность коэффициентов ошибок, начинающаяся с нечетных шагов, сходится к 1, а другая подпоследовательность коэффициентов, начинающаяся с четных шагов, сходится к 1/4. Когда две подпоследовательности последовательности сходятся к разным пределам, сама последовательность не сходится к пределу. ${\textstyle (b_{k})=1,1,1/4,1/4,1/16,1/16,\ldots ,1/4^{\left\lfloor {\frac {k}{2}}\right\rfloor },\ldots }$ ${\textstyle \lfloor x\rfloor }$ ${\displaystyle x}$

В таких случаях более уместно близкое, но более техническое определение скорости сходимости, называемое R-сходимостью. Префикс «R-» означает «корень». ^{[1] [7] : 620} Последовательность , которая сходится к , считается сходящейся по крайней мере R-линейно, если существует ограничивающая ошибку последовательность такая, что и сходится Q-линейно к нулю; аналогичные определения справедливы для R-суперлинейной сходимости, R-сублинейной сходимости, R-квадратичной сходимости и т. д. ^[1] ${\displaystyle (x_{k})}$ ${\displaystyle L}$ ${\displaystyle (\varepsilon _{k})}$ ${\textstyle |x_{k}-L|\leq \varepsilon _{k}\quad {\text{for all }}k}$ ${\displaystyle (\varepsilon _{k})}$

Любая последовательность, ограничивающая ошибку, обеспечивает нижнюю границу скорости и порядка R-сходимости, а наибольшая нижняя граница дает точную скорость и порядок R-сходимости. Что касается Q-сходимости, последовательности с большими порядками сходятся быстрее, а последовательности с меньшими скоростями сходятся быстрее для заданного порядка, поэтому эти последовательности с наибольшей скоростью, нижней границей и верхней границей ошибки — это те, которые имеют наибольшее возможное и наименьшее возможное значение, учитывая, что . ${\displaystyle (\varepsilon _{k})}$ ${\displaystyle q}$ ${\displaystyle \mu }$ ${\displaystyle q}$ ${\displaystyle \mu }$ ${\displaystyle q}$

Для приведенного выше примера , плотно ограничивающая последовательность сходится Q-линейно со скоростью 1/2, поэтому сходится R-линейно со скоростью 1/2. Как правило, для любой ступенчатой ​​геометрической прогрессии последовательность не будет сходиться Q-линейно, но будет сходиться R-линейно со скоростью Эти примеры показывают, почему «R» в R-линейной сходимости является сокращением от «корень». ${\textstyle (b_{k})}$ ${\textstyle (\varepsilon _{k})=2,1,1/2,1/4,1/8,1/16,\ldots ,1/2^{k-1},\ldots }$ ${\textstyle (b_{k})}$ ${\displaystyle (ar^{\lfloor k/m\rfloor })}$ ${\textstyle {\sqrt[{m}]{|r|}}.}$

Примеры

Геометрическая прогрессия сходится к . Подстановка последовательности в определение Q-линейной сходимости (т.е. порядка сходимости 1) показывает, что ${\textstyle (a_{k})=1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},{\frac {1}{32}},\ldots ,1/{2^{k}},\dots }$ ${\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}$

В более общем случае, для любого начального значения в действительных числах и общего отношения действительных чисел от -1 до 1, геометрическая прогрессия сходится линейно со скоростью и последовательность частичных сумм геометрического ряда также сходится линейно со скоростью . То же самое справедливо и для геометрических прогрессий и геометрических рядов, параметризованных любыми комплексными числами ${\displaystyle a}$ ${\displaystyle r}$ ${\displaystyle (ar^{k})}$ ${\displaystyle |r|}$ ${\textstyle (\sum _{n=0}^{k}ar^{n})}$ ${\displaystyle |r|}$ ${\displaystyle a\in \mathbb {C} ,r\in \mathbb {C} ,|r|<1.}$

Ступенчатая геометрическая прогрессия, использующая функцию пола , которая дает наибольшее целое число, которое меньше или равно, сходится R-линейно к 0 со скоростью 1/2, но не сходится Q-линейно; см. второй график рисунка ниже. Определяющие пределы Q-линейной сходимости не существуют для этой последовательности, потому что одна подпоследовательность коэффициентов ошибок, начинающаяся с нечетных шагов, сходится к 1, а другая подпоследовательность коэффициентов, начинающаяся с четных шагов, сходится к 1/4. Когда две подпоследовательности последовательности сходятся к разным пределам, последовательность сама по себе не сходится к пределу. Как правило, для любой ступенчатой ​​геометрической прогрессии последовательность не будет сходиться Q-линейно, но будет сходиться R-линейно со скоростью эти примеры показывают, почему «R» в R-линейной сходимости является сокращением от «корня». ${\textstyle (b_{k})=1,1,{\frac {1}{4}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{16}},\ldots ,1/4^{\left\lfloor {\frac {k}{2}}\right\rfloor },\ldots ,}$ ${\textstyle \lfloor x\rfloor }$ ${\displaystyle x,}$ ${\displaystyle (ar^{\lfloor k/m\rfloor })}$ ${\textstyle {\sqrt[{m}]{|r|}};}$

Последовательность сходится к нулю Q-суперлинейно. Фактически, она квадратично сходится с квадратичной скоростью сходимости 1. Это показано на третьем графике рисунка ниже. $${\displaystyle (c_{k})={\frac {1}{2}},{\frac {1}{4}},{\frac {1}{16}},{\frac {1}{256}},{\frac {1}{65,\!536}},\ldots ,{\frac {1}{2^{2^{k}}}},\ldots }$$

Наконец, последовательность сходится к нулю Q-сублинейно и логарифмически, и ее сходимость показана в виде четвертого графика на рисунке ниже. $${\displaystyle (d_{k})=1,{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}},{\frac {1}{5}},{\frac {1}{6}},\ldots ,{\frac {1}{k+1}},\ldots }$$

Логлинейные графики примеров последовательностей a _k , b _k , c _k и d _k , иллюстрирующих линейную, линейную, сверхлинейную (квадратичную) и сублинейную скорости сходимости соответственно.

Скорости сходимости к фиксированным точкам рекуррентных последовательностей

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

Заказать оценку

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

Для численного приближения точного значения с помощью численного метода порядка см. ^[9] ${\displaystyle q}$

Ускорение темпов конвергенции

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

Асимптотические скорости сходимости для методов дискретизации

Определения

Говорят, что последовательность дискретизированных приближений некоторой функции непрерывной области , которая сходится к этой цели, вместе с соответствующей последовательностью параметров шкалы дискретизации , которые сходятся к 0, имеет асимптотический порядок сходимости и асимптотическую скорость сходимости, если ${\displaystyle (y_{k})}$ ${\displaystyle S}$ ${\displaystyle (h_{k})}$ ${\displaystyle q}$ ${\displaystyle \mu }$

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|y_{k}-S\right|}{h_{k}^{q}}}=\mu ,}$$

для некоторых положительных констант и и используя для обозначения соответствующей метрики расстояния на пространстве решений , чаще всего либо равномерной нормы , абсолютной разности или евклидова расстояния . Параметрами масштаба дискретизации могут быть интервалы регулярной сетки в пространстве или во времени, обратные числа точек сетки в одном измерении, среднее или максимальное расстояние между точками в сетке полигона , одномерные интервалы нерегулярной разреженной сетки или характерный квант энергии или импульса в квантово-механическом базисном наборе . ${\displaystyle \mu }$ ${\displaystyle q}$ ${\displaystyle |x|}$

Когда все дискретизации генерируются с использованием одного общего метода, обычно обсуждают асимптотическую скорость и порядок сходимости для самого метода, а не для каких-либо конкретных дискретных последовательностей дискретизированных решений. В этих случаях рассматривается одно абстрактное дискретизированное решение, сгенерированное с использованием метода с параметром масштаба , и тогда говорят, что метод имеет асимптотический порядок сходимости и асимптотическую скорость сходимости, если ${\displaystyle y_{h}}$ ${\displaystyle h}$ ${\displaystyle q}$ ${\displaystyle \mu }$

$${\displaystyle \lim _{h\rightarrow 0}{\frac {\left|y_{h}-S\right|}{h^{q}}}=\mu ,}$$

снова для некоторых положительных констант и и подходящей метрики Это подразумевает, что ошибка дискретизации асимптотически масштабируется подобно параметру масштаба дискретизации в степени , или с использованием асимптотической большой нотации O. Точнее, это подразумевает, что ошибка ведущего порядка равна , которая может быть выражена с использованием асимптотической малой нотации o как ${\displaystyle \mu }$ ${\displaystyle q}$ ${\displaystyle |x|.}$ ${\displaystyle q}$ ${\textstyle \left|y_{h}-S\right|=O(h^{q})}$ ${\displaystyle \mu h^{q},}$ ${\textstyle \left|y_{h}-S\right|=\mu h^{q}+o(h^{q}).}$

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

Пример

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

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

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

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

что подразумевает линейную рекуррентность первого порядка с постоянными коэффициентами

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

При условии , что последовательность, удовлетворяющая условию повторения, является геометрической прогрессией ${\displaystyle y(0)=y_{0}}$

$${\displaystyle y_{n}=y_{0}(1-h\kappa )^{n}=y_{0}\left(1-nh\kappa +{\frac {n(n-1)}{2}}h^{2}\kappa ^{2}+....\right).}$$

Точное аналитическое решение дифференциального уравнения имеет вид , что соответствует следующему разложению Тейлора в : ${\displaystyle y=f(x)=y_{0}\exp(-\kappa x)}$ ${\displaystyle nh\kappa }$ $${\displaystyle f(x_{n})=f(nh)=y_{0}\exp(-\kappa nh)=y_{0}\left(1-nh\kappa +{\frac {n^{2}h^{2}\kappa ^{2}}{2}}+...\right).}$$

Поэтому ошибка дискретного приближения в каждой дискретной точке равна

$${\displaystyle |y_{n}-f(x_{n})|={\frac {nh^{2}\kappa ^{2}}{2}}+\ldots }$$

Для любого конкретного заданного ряда приближений Эйлера , каждое из которых использует сетку с шагом , который делится так, что , имеем ${\displaystyle x=p}$ ${\displaystyle ((y_{n})_{k})}$ ${\displaystyle h_{k}}$ ${\displaystyle p}$ ${\displaystyle n_{p,k}=p/h_{k}}$

$${\displaystyle \lim _{h_{k}\rightarrow 0}{\frac {|y_{k}(p)-f(p)|}{h_{k}}}=\lim _{h_{k}\rightarrow 0}{\frac {|y_{k,n_{p,k}}-f(h_{k}n_{p,k})|}{h_{k}}}={\frac {h_{k}n_{p,k}\kappa ^{2}}{2}}={\frac {p\kappa ^{2}}{2}}}$$

для любой последовательности сеток с последовательно уменьшающимися шагами сетки . Таким образом, сходится к поточечно с порядком сходимости и асимптотической ошибкой, постоянной в каждой точке Аналогично, последовательность сходится равномерно с тем же порядком и скоростью на любом ограниченном интервале , но она не сходится равномерно на неограниченном множестве всех положительных действительных значений, ${\displaystyle h_{k}}$ ${\displaystyle ((y_{n})_{k})}$ ${\displaystyle f(x)}$ ${\displaystyle q=1}$ ${\displaystyle p\kappa ^{2}/2}$ ${\displaystyle p>0.}$ ${\displaystyle L\kappa ^{2}/2}$ ${\displaystyle p\leq L}$ ${\displaystyle [0,\infty ).}$

Сравнение асимптотических скоростей сходимости

Определения

В асимптотическом анализе в целом говорят, что одна последовательность , которая сходится к пределу , асимптотически сходится к с более быстрым порядком сходимости, чем другая последовательность , которая сходится к в общем метрическом пространстве с метрикой расстояния, такой как действительные числа или комплексные числа с обычными метриками абсолютной разности , если ${\displaystyle (a_{k})_{k\in \mathbb {N} }}$ ${\displaystyle L}$ ${\displaystyle L}$ ${\displaystyle (b_{k})_{k\in \mathbb {N} }}$ ${\displaystyle L}$ ${\displaystyle |\cdot |,}$

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=0,}$$

Говорят, что эти два числа асимптотически сходятся с одинаковым порядком сходимости, если ${\displaystyle L}$

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=\mu }$$

для некоторой положительной конечной константы и говорят, что они асимптотически сходятся к с той же скоростью и порядком сходимости, если ${\displaystyle \mu ,}$ ${\displaystyle L}$

$${\displaystyle \lim _{k\rightarrow \infty }{\frac {\left|a_{k}-L\right|}{|b_{k}-L|}}=1.}$$

Эти сравнительные определения скорости и порядка асимптотической сходимости являются основополагающими в асимптотическом анализе . ^{[10] [11]} Для первых двух из них имеются соответствующие выражения в асимптотической нотации O : первое — это нотация в малых o ^[12] , а второе — это нотация Кнута. ^[13] Третье также называется асимптотической эквивалентностью, выраженной ^{[14] [15]} ${\displaystyle a_{k}-L=o(b_{k}-L)}$ ${\displaystyle a_{k}-L=\Theta (b_{k}-L)}$ ${\displaystyle a_{k}-L\sim b_{k}-L.}$

Примеры

Для любых двух геометрических прогрессий и с общим пределом ноль, две последовательности асимптотически эквивалентны тогда и только тогда, когда обе и Они сходятся с тем же порядком тогда и только тогда, когда сходится с более быстрым порядком, чем тогда и только тогда, когда Сходимость любой геометрической прогрессии к своему пределу имеет погрешности, которые равны геометрической прогрессии, поэтому аналогичные соотношения справедливы и для геометрических рядов. Любая последовательность, которая асимптотически эквивалентна сходящейся геометрической последовательности, может быть либо «сходится геометрически», либо «сходится экспоненциально» относительно абсолютной разницы от ее предела, или можно сказать, что она «сходится линейно» относительно логарифма абсолютной разницы, такой как «число десятичных знаков точности». Последнее является стандартным в численном анализе. ${\displaystyle (ar^{k})_{k\in \mathbb {N} }}$ ${\displaystyle (bs^{k})_{k\in \mathbb {N} },}$ ${\displaystyle a=b}$ ${\displaystyle r=s.}$ ${\displaystyle r=s.}$ ${\displaystyle (ar^{k})}$ ${\displaystyle (bs^{k})}$ ${\displaystyle r<s.}$

Для любых двух последовательностей элементов, пропорциональных обратной степени и с общим пределом ноль, эти две последовательности асимптотически эквивалентны тогда и только тогда, когда обе и Они сходятся с тем же порядком тогда и только тогда, когда сходится с более быстрым порядком, чем тогда и только тогда, когда ${\displaystyle k,}$ ${\displaystyle (ak^{-n})_{k\in \mathbb {N} }}$ ${\displaystyle (bk^{-m})_{k\in \mathbb {N} },}$ ${\displaystyle a=b}$ ${\displaystyle n=m.}$ ${\displaystyle n=m.}$ ${\displaystyle (ak^{-n})}$ ${\displaystyle (bk^{-m})}$ ${\displaystyle n>m.}$

Для любой последовательности с пределом, равным нулю, ее сходимость можно сравнить со сходимостью сдвинутой последовательности, перемасштабированной сдвинутой последовательности на константу и масштабированные -степени сдвинутой последовательности. Эти сравнения являются основой для классификаций Q-сходимости для итеративных численных методов, как описано выше: когда последовательность итерационных ошибок численного метода асимптотически эквивалентна сдвинутой, возведенной в степень и перемасштабированной последовательности итерационных ошибок, говорят, что она сходится с порядком и скоростью ${\displaystyle (a_{k})_{k\in \mathbb {N} }}$ ${\displaystyle (a_{k-1})_{k\in \mathbb {N} },}$ ${\displaystyle \mu ,}$ ${\displaystyle (\mu a_{k-1})_{k\in \mathbb {N} },}$ ${\displaystyle q}$ ${\displaystyle (\mu a_{k-1}^{q})_{k\in \mathbb {N} }.}$ ${\displaystyle (|x_{k}-L|)_{k\in \mathbb {N} }}$ ${\displaystyle (\mu |x_{k-1}-L|^{q})_{k\in \mathbb {N} },}$ ${\displaystyle q}$ ${\displaystyle \mu .}$

Неасимптотические скорости сходимости

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

Для итерационных методов одним из распространенных практических подходов является обсуждение этих скоростей с точки зрения количества итераций или машинного времени, необходимых для достижения близких окрестностей предела из начальных точек, далеких от предела. Неасимптотическая скорость тогда является обратной величиной этого количества итераций или машинного времени. В практических приложениях итерационный метод, который потребовал меньше шагов или меньше машинного времени, чем другой, для достижения целевой точности, будет считаться сходившимся быстрее, чем другой, даже если его асимптотическая сходимость медленнее. Эти скорости, как правило, будут разными для разных начальных точек и разных порогов погрешности для определения окрестностей. Чаще всего обсуждаются сводки статистических распределений этих единичных точечных скоростей, соответствующих распределениям возможных начальных точек, таких как «средняя неасимптотическая скорость», «медианная неасимптотическая скорость» или «наихудшая неасимптотическая скорость» для некоторого метода, примененного к некоторой проблеме с некоторым фиксированным порогом погрешности. Эти ансамбли начальных точек могут быть выбраны в соответствии с такими параметрами, как начальное расстояние от конечного предела, чтобы определить такие величины, как «средняя неасимптотическая скорость сходимости с заданного расстояния».

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

Ссылки

1. Нокедал, Хорхе; Райт, Стивен Дж. (1999). Численная оптимизация (1-е изд.). Нью-Йорк, Нью-Йорк: Springer. С. 28–29. ISBN 978-0-387-98793-4.
2. Сеннинг, Джонатан Р. «Вычисление и оценка скорости сходимости» (PDF) . gordon.edu . Получено 2020-08-07 .
3. Хандли, Дуглас. «Скорость сходимости» (PDF) . Whitman College . Получено 2020-12-13 .
4. Порта, ФА (1989). «О Q-порядке и R-порядке сходимости» (PDF) . Журнал теории оптимизации и приложений . 63 (3): 415–431. doi :10.1007/BF00939805. S2CID  116192710 . Получено 31 июля 2020 г. .
5. Van Tuyl, Andrew H. (1994). "Ускорение сходимости семейства логарифмически сходящихся последовательностей" (PDF) . Mathematics of Computation . 63 (207): 229–246. doi :10.2307/2153571. JSTOR  2153571 . Получено 02.08.2020 .
6. Чансон, Джеффри Р. (3 октября 2024 г.). «Порядок сходимости». LibreTexts Mathematics . Получено 3 октября 2024 г. .{{cite web}}: CS1 maint: url-status (link)
7. Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин, Нью-Йорк: Springer-Verlag . ISBN 978-0-387-30303-1.
8. Сеннинг, Джонатан Р. «Вычисление и оценка скорости сходимости» (PDF) . gordon.edu . Получено 2020-08-07 .
9. Сеннинг, Джонатан Р. "Проверка скоростей числовой сходимости" (PDF) . Получено 2024-02-09 .
10. Балькасар, Хосе Л.; Габарро, Хоаким. «Классы неоднородной сложности, определяемые нижними и верхними границами» (PDF) . RAIRO – Теоретическая информатика и приложения – Informatique Théorique et Applications . 23 (2): 180. ISSN  0988-3754. Архивировано (PDF) из оригинала 14 марта 2017 года . Проверено 14 марта 2017 г. - через Numdam.
11. Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons". Условие: Геометрия численных алгоритмов . Берлин, Гейдельберг: Springer. стр. 467–468. doi :10.1007/978-3-642-38896-5. ISBN 978-3-642-38896-5.
12. Апостол, Том М. (1967). Calculus . Т. 1 (2-е изд.). США: John Wiley & Sons. стр. 286. ISBN 0-471-00005-1.{{cite book}}: CS1 maint: date and year (link)
13. Кнут, Дональд (апрель–июнь 1976 г.). «Большой Омикрон и большая Омега и большая Тета». SIGACT News . 8 (2): 18–24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . 
14. Апостол, Том М. (1967). Calculus . Т. 1 (2-е изд.). США: John Wiley & Sons. стр. 396. ISBN 0-471-00005-1.{{cite book}}: CS1 maint: date and year (link)
15. "Асимптотическое равенство", Энциклопедия математики , EMS Press , 2001 [1994]