В численном анализе , дельта-квадрате процесс Эйткена или Эйткена Экстраполяция является серия ускорения метод, используемые для ускорения скорости сходимости последовательности. Он назван в честь Александра Айткена , который ввел этот метод в 1926 году. [1] Его ранняя форма была известна Секи Куве (конец 17 века) и использовалась для выпрямления круга, то есть для вычисления π. Это наиболее полезно для ускорения сходимости линейно сходящейся последовательности.
Определение
Учитывая последовательность , с этой последовательностью ассоциируется новая последовательность
который с улучшенной числовой стабильностью можно также записать как
или эквивалентно как
где
а также
для
Очевидно, некорректно определено, если содержит нулевой элемент или, что то же самое, если последовательность первых разностей имеет повторяющийся член.
С теоретической точки зрения, если это происходит только для конечного числа индексов, можно легко согласиться рассмотреть последовательность ограничено индексами с достаточно большим . С практической точки зрения, как правило, учитываются только первые несколько членов последовательности, которые обычно обеспечивают необходимую точность. Более того, при численном вычислении последовательности нужно позаботиться о том, чтобы остановить вычисление, когда ошибки округления в знаменателе становятся слишком большими, когда операция Δ² может отменить слишком много значащих цифр . (Для численного расчета лучше использовать скорее, чем .)
Характеристики
Дельта-квадратный процесс Эйткена - это метод ускорения сходимости и частный случай нелинейного преобразования последовательности .
будет сходиться линейно к если существует такое число μ ∈ (0, 1), что
Метод Эйткена ускорит последовательность если
не является линейным оператором, но выпадает постоянный член, а именно: , если является константой. Это видно из выраженияв терминах оператора конечных разностей.
Хотя новый процесс, как правило, не сходится квадратично, можно показать, что для процесса с фиксированной точкой , то есть для повторяющейся последовательности функций для какой-то функции , сходящаяся к неподвижной точке, сходимость квадратичная. В данном случае метод известен как метод Стеффенсена .
Эмпирически A -операция устраняет «наиболее важную ошибку». В этом можно убедиться, рассмотрев последовательность вида, где : Последовательность затем дойдет до предела, например уходит в ноль.
Геометрически график экспоненциальной функции это удовлетворяет , а также имеет горизонтальную асимптоту при (если ).
Можно также показать, что если идет к своему пределу со скоростью строго больше 1, не имеет лучшей скорости сходимости. (На практике редко бывает, например, квадратичная сходимость, что означает более 30 или 100 правильных десятичных знаков после 5 или 7 итераций (начиная с 1 правильной цифры); обычно в этом случае ускорение не требуется.)
На практике, сходится к пределу намного быстрее, чем делает, как показано в приведенных ниже примерах расчетов. Обычно гораздо дешевле рассчитать (включая только вычисление разностей, одно умножение и одно деление), чем для вычисления большего количества членов последовательности . Однако следует проявлять осторожность, чтобы избежать ошибок из-за недостаточной точности при вычислении разницы в числителе и знаменателе выражения.
Примеры расчетов
Пример 1 : значение можно аппроксимировать, приняв начальное значение для и повторяя следующее:
Начиная с
п | x = повторное значение | Топор |
0 | 1 | 1,4285714 |
1 | 1.5 | 1,4141414 |
2 | 1,4166667 | 1,4142136 |
3 | 1,4142157 | - |
4 | 1,4142136 | - |
Здесь стоит отметить, что метод Эйткена не сохраняет два шага итерации; вычисление первых трех значений Ax потребовало первых пяти значений x . Кроме того, второе значение Ax явно уступает 4-му значению x, в основном из-за того, что процесс Эйткена предполагает линейную, а не квадратичную сходимость [ необходима цитата ] .
Пример 2 : значение можно рассчитать как бесконечную сумму:
п | срок | x = частичная сумма | Топор |
0 | 1 | 1 | 0,79166667 |
1 | -0,33333333 | 0,66666667 | 0,78333333 |
2 | 0,2 | 0,86666667 | 0,78630952 |
3 | -0,14285714 | 0,72380952 | 0,78492063 |
4 | 0,11111111 | 0,83492063 | 0,78567821 |
5 | −9.0909091 × 10 −2 | 0,74401154 | 0,78522034 |
6 | 7,6923077 × 10 −2 | 0,82093462 | 0,78551795 |
7 | -6,6666667 × 10 -2 | 0,75426795 | - |
8 | 5,8823529 × 10 −2 | 0,81309148 | - |
В этом примере метод Эйткена применяется к сублинейно сходящемуся ряду, что значительно ускоряет сходимость. Он по-прежнему сублинейный, но намного быстрее, чем исходная сходимость: первое значение Ax, для вычисления которого потребовались первые три значения x, ближе к пределу, чем восьмое значение x.
Пример псевдокода для экстраполяции Эйткена
Ниже приведен пример использования экстраполяции Эйткена, чтобы помочь найти предел последовательности. при наличии некоторого начального где предел этой последовательности предполагается фиксированной точкой (сказать ). Например, если последовательность задана как с отправной точкой тогда функция будет у которого есть как фиксированная точка (см. Методы вычисления квадратных корней ); именно эта фиксированная точка будет приближена к значению.
Этот псевдокод также вычисляет приближение Эйткена к . Экстраполяции Эйткена будут обозначены aitkenX
. Во время вычисления экстраполяции важно проверить, не станет ли знаменатель слишком маленьким, что могло бы произойти, если бы у нас уже была большая точность; без этой проверки деление может привести к большим ошибкам. Это небольшое число будет обозначено epsilon
. Поскольку двоичное представление фиксированной точки может быть бесконечным (или, по крайней мере, слишком большим, чтобы поместиться в доступной памяти), вычисление остановится, когда приближение окажется в пределах tolerance
истинного значения.
% Эти варианты зависят от решаемой проблемыx0 = 1 % Начальное значение е ( х ) = ( 1 / 2 ) * ( х + 2 / х ) % Функция , которая находит следующий элемент в последовательности Допуск = 10 ^ - 10 % Требуется 10-значная точность epsilon = 10 ^ - 16 % Не делите на меньшее число maxIterations = 20 % Не позволять итерациям продолжаться бесконечно haveWeFoundSolution = false % Удалось ли найти решение в пределах желаемого допуска? еще нет для i = 1 : maxIterations x1 = f ( x0 ) х2 = е ( х1 ) если ( x1 ~ = x0 ) lambda = absoluteValue (( x2 - x1 ) / ( x1 - x0 )) % ДОПОЛНИТЕЛЬНО: вычисляет приближение | f '(fixedPoint) |, которое обозначается лямбда конец знаменатель = ( x2 - x1 ) - ( x1 - x0 ); if ( absoluteValue ( знаменатель ) < epsilon ) % Чтобы избежать значительного увеличения ошибки, не делите на слишком маленькое число print ( 'ВНИМАНИЕ: знаменатель слишком мал' ) перерыв ; % Выйти из цикла конец aitkenX = x2 - ( ( x2 - x1 ) ^ 2 ) / знаменатель if ( absoluteValue ( aitkenX - x2 ) < толерантность ) % Если значение находится в пределах допуска print ( "Фиксированная точка" , aitkenX )) % Отобразить результат экстраполяции Эйткена haveWeFoundSolution = true перерыв ; % Готово, выходите из цикла конец x0 = aitkenX % Обновите x0, чтобы начать заново конецif ( haveWeFoundSolution == false ) % Если мы не смогли найти решение в пределах желаемого допуска print ( «Предупреждение: невозможно найти решение в пределах желаемого допуска» , толерантность ) print ( "Последняя вычисленная экстраполяция была" , aitkenX ) конец
Смотрите также
Заметки
- ↑ Александр Эйткен, «О численном решении Бернулли алгебраических уравнений», Труды Королевского общества Эдинбурга (1926), 46 стр. 289–305.
Рекомендации
- Уильям Х. Пресс и др. , Числовые рецепты на языке C , (1987) Cambridge University Press, ISBN 0-521-43108-5 (см. Раздел 5.1 )
- Абрамовиц и Стегун, Справочник по математическим функциям , раздел 3.9.7.
- Кендалл Э. Аткинсон, Введение в численный анализ , (1989) John Wiley & Sons, Inc., ISBN 0-471-62489-6