Как найти дельта квадрат

В численном анализе , дельта-квадрате процесс Эйткена или Эйткена Экстраполяция является серия ускорения метод, используемые для ускорения скорости сходимости последовательности. Он назван в честь Александра Айткена , который ввел этот метод в 1926 году. Его ранняя форма была известна Секи Куве (конец 17 века) и использовалась для выпрямления круга, то есть для вычисления π. Это наиболее полезно для ускорения сходимости линейно сходящейся последовательности.

Определение

Учитывая последовательность , с этой последовательностью связывается новая последовательность

который с улучшенной числовой стабильностью можно также записать как

или эквивалентно как

куда

и

для

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

С теоретической точки зрения, если это происходит только для конечного числа индексов, можно легко согласиться рассматривать последовательность, ограниченную индексами с достаточно большим . С практической точки зрения, как правило, учитываются только первые несколько членов последовательности, которые обычно обеспечивают необходимую точность. Более того, при численном вычислении последовательности необходимо позаботиться о том, чтобы остановить вычисление, когда ошибки округления в знаменателе становятся слишком большими, когда операция Δ² может отменить слишком много значащих цифр . (Было бы лучше использовать численный расчет, а не .)

Характеристики

Дельта-квадратный процесс Эйткена – это метод ускорения сходимости и частный случай нелинейного преобразования последовательности .

будет сходятся линейно , чтобы , если существует число М ∈ (0, 1) такое , что

Метод Эйткена ускорит последовательность, если

не является линейным оператором, но выпадает постоянный член, а именно:, если является константой. Это ясно из выражения через оператор конечных разностей .

Хотя новый процесс, как правило, не сходится квадратично, можно показать, что для процесса с фиксированной точкой , то есть для повторяющейся последовательности функций для некоторой функции , сходящейся к фиксированной точке, сходимость является квадратичной. В данном случае метод известен как метод Стеффенсена .

Эмпирически A -операция устраняет «наиболее важную ошибку». Это можно проверить, рассмотрев последовательность в форме , где : Затем последовательность достигнет предела, как если бы она дошла до нуля.

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

Можно также показать, что если он достигает своего предела со скоростью, строго превышающей 1, не имеет лучшей скорости сходимости. (На практике редко бывает, например, квадратичная сходимость, что означает более 30 или 100 правильных десятичных знаков после 5 или 7 итераций (начиная с 1 правильной цифры); обычно в этом случае ускорение не требуется.)

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

Примеры расчетов

Пример 1. Значение может быть приблизительно определено путем принятия начального значения и повторения следующего:

Начиная с

Здесь стоит отметить, что метод Эйткена не сохраняет два шага итерации; вычисление первых трех значений Ax потребовало первых пяти значений x . Кроме того, второе значение Ax явно уступает 4-му значению x, в основном из-за того, что процесс Эйткена предполагает линейную, а не квадратичную сходимость.

Пример 2 : Значение может быть вычислено как бесконечная сумма:

В этом примере метод Эйткена применяется к сублинейно сходящемуся ряду, что значительно ускоряет сходимость. Он по-прежнему сублинейный, но намного быстрее, чем исходная сходимость: первое значение Ax, для вычисления которого потребовались первые три значения x, ближе к пределу, чем восьмое значение x.

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

Этот псевдокод также вычисляет приближение Эйткена к . Экстраполяции Эйткена будут обозначены . Во время вычисления экстраполяции важно проверить, не станет ли знаменатель слишком маленьким, что могло бы произойти, если бы у нас уже была большая точность; без этой проверки деление может привести к большим ошибкам. Это небольшое число будет обозначено . Поскольку двоичное представление фиксированной точки может быть бесконечным (или, по крайней мере, слишком большим, чтобы поместиться в доступной памяти), вычисление остановится, когда приближение окажется в пределах истинного значения.
aitkenXepsilontolerance

%These choices depend on the problem being solved
x0 = 1                      %The initial value
f(x) = (1/2)*(x + 2/x)      %The function that finds the next element in the sequence
tolerance = 10^-10          %10 digit accuracy is desired
epsilon = 10^-16            %Do not divide by a number smaller than this

maxIterations = 20          %Do not allow the iterations to continue indefinitely
haveWeFoundSolution = false %Were we able to find the solution to within the desired tolerance? not yet

for i = 1 : maxIterations 
    x1 = f(x0)
    x2 = f(x1)

    if (x1 ~= x0)
        lambda = absoluteValue((x2 - x1)/(x1 - x0))  %OPTIONAL: Computes an approximation of |f'(fixedPoint)|, which is denoted by lambda
    end

    denominator = (x2 - x1) - (x1 - x0);

    if (absoluteValue(denominator) < epsilon)        %To avoid greatly increasing error, do not divide by too small of a number
        print('WARNING: denominator is too small')
        break;                                       %Leave the loop
    end

    aitkenX = x2 - ( (x2 - x1)^2 )/denominator
    
    if (absoluteValue(aitkenX - x2) < tolerance)     %If the value is within tolerance
        print("The fixed point is ", aitkenX))       %Display the result of the Aitken extrapolation
        haveWeFoundSolution = true
        break;                                       %Done, so leave the loop
    end

    x0 = aitkenX                                     %Update x0 to start again                  
end

if (haveWeFoundSolution == false)   %If we were not able to find a solution to within the desired tolerance
    print("Warning: Not able to find solution to within the desired tolerance of ", tolerance)
    print("The last computed extrapolate was ", aitkenX)
end

Смотрите также

• Скорость сходимости
• Предел последовательности
• Итерация с фиксированной точкой
• Экстраполяция Ричардсона
• Преобразование последовательности
• Трансформация хвостовика
• Метод Стеффенсена

Примечания

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

• Уильям Х. Пресс и др. , Числовые рецепты на языке 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

Войти на сайт

или

Забыли пароль?
Еще не зарегистрированы?