Преобразование Эйткена

Введение

Непрерывные дроби

Основная гипотеза

О доказательствах

Константа Эйлера

ZIP-файлы

        Сумма всякого ряда есть значение того конечного выражения, 

из развертывания которого возникает этот ряд

Леонард Эйлер

Введение

Не знаю, как Вас, а меня давно раздражало, что ряд

1 + z + z^2 + z^3 + z^4 + z^5 + z^6+... ( z - комплексное, чего уж там )

дает отличные результаты при | z | < 1 по формуле S = 1 / ( 1 - z ) и не работает при | z | >= 1. Я еще понимаю про точку z = 1, но остальным то что мешает? - Ах, круг сходимости... Рассмотрим символьные частичные суммы

A₀( z ) = 1

A₁( z ) = 1 + z

A₂( z ) = 1 + z + z^2

A₃( z ) = 1 + z + z^2 + z^3

A₄( z ) = 1 + z + z^2 + z^3 + z^4

Вычислим некую комбинацию из этих сумм

B₂( z ) = ( A₂ * A₀ - A₁^2 ) / ( A₂ + A₀ - A₁*2 ) = 1 / ( 1 - z )

B₃( z ) = ( A₃ * A₁ - A₂^2 ) / ( A₃ + A₁ - A₂*2 ) = 1 / ( 1 - z )

B₄( z ) = ( A₄ * A₂ - A₃^2 ) / ( A₄ + A₂ - A₃*2 ) = 1 / ( 1 - z )

Наши суммы стабилизировались, причем именно на формуле суммы геометрической прогрессии. И никаких проблем при переходе через окружность | z | = 1 эта формула не встретит.

Вот эти формулы

 и называются преобразованием Эйткена.

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

Что же делает это преобразование с частичными суммами степенного ряда? - Преобразует их в дробно-рациональную функцию P_n( z ) / Q_m( z ). В самом деле, с чего мы взяли, что именно полиномы лучше всего описывают встречающиеся функции?

Непрерывные дроби

Такой подход исследовал еще в 1892 французский математик Паде. Полиномы A_i - это отрезки ряда Мак-Лорена, их производные в нуле вплоть до i-ого порядка совпадают с производными исходной функции. Полином A_i имеет i+1 коэффициент. Естественно потребовать, чтобы дробь P_n( z ) / Q_m( z ), аппроксимирующая A_i имела столько же коэффициентов (так сказать, уравнять число настраиваемых параметров ). Отсюда m+1+n+1-1 = i+1 (один коэффициент можно  сэкономить, сократив дробь на старший коэффициент знаменателя ). И все эти дроби должны сохранять неизменными первые i производных. Паде выписал целую матрицу таких дробей (n - по вертикали, m - по горизонтали).

Позже была выведена формула для коэффициентов полиномов P_n( z ) и Q_m( z ), и доказано, что наивысшая скорость сходимости у дробей, где m=n и m=n-1 (диагонали Паде-таблицы ) - именно эти дроби являются представителями класса непрерывных дробей.

Непрерывная дробь - это способ записи ряда, альтернативный полиному. Вот пример

Красиво, не правда ли?

Не менее красиво, чем Ln(1 + z) = 0 + z / 1 - z^2 / 2 + z^3 / 3 - z^4 / 4 + z^5 / 5 - z^6 / 6 + ...

 Основная гипотеза

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

Преобразование Эйткена, проведенное один раз (из полиномов A_i получить дроби B_i), приводит к первому столбцу Паде-таблицы (дроби вида P_i-1( z ) / Q₁( z )). Но, преобразование Эйткена можно применить и к B_i, преобразовав их в C_i ( i=4, ... ), и к C_i, преобразовав их в D_i ( i=6, ... ), и так далее.

Вот здесь уже о минимизации числа коэффициентов говорить не приходится - растет степень знаменателя: ряд C_i это дроби вида P_i-1( z ) / Q₃( z ), ряд D_i это дроби вида P_i-1( z ) / Q₅( z ). Т.е. нарушается соотношение m+n = i. Подгоночных параметров слишком много, но они подбираются автоматически и с толком!

Сравним качество приближения исходной функции ( Ln(1 + z ) ) тремя способами: степенным рядом, непрерывной дробью, преобразованием Эйткена. Для конкретности я ограничился значениями первых шести производных и рассматривал круг | z | < 2. Белая окружность - это граница круга сходимости | z | = 1. Как видим по логарифмической шкале,

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

 О доказательствах

Как и все, умею доказывать, что преобразование Эйткена не портит соответствующее число первых производных. 

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

Не знаю ни одного доказательства сходимости преобразований Эйткена для какой-либо другой функции. На компьютере я перебрал довольно много функций: EXP(z), SIN(z), COS(z), SH(z), CH(z), TG(z), arc SIN(z), arc TG(z), arc SH(z), arc TH(z), 1/(1-z) + 1/(1-2*z), (1-z+z^3)/(1-2*z+z^2) /Грэгг, 1972/ и всюду наблюдал этот результат - лучшую сходимость.

А вот, казалось бы, "контрпример". F( z ) = ( 1 + z + z^2 ) / ( 1 + z + z^2 + z^3 ).

A₀( z ) = 1

A₁( z ) = 1

A₂( z ) = 1

A₃( z ) = 1 - z^3

A₄( z ) = 1 - z^3

A₅( z ) = 1 - z^3 + z^4

Очень тяжело для преобразования Эйткена идти по таким частично постоянным членам ряда. Но ... C₅( z ) = ( 1 + z + z^2 ) / ( 1 + z^2 ) / ( 1 + z ) = F( z ).

Константа Эйлера

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

Известно, что 1 + z + 2! * z^2 + 3! * z^3 + 4! * z^4 + 5! * z^5 + ... @ 0.5963 при z = -1. Применим преобразование Эйткена непосредственно к ряду из чисел

ZIP-файлы

Aitken_Ln.bmp(16Kb)