Приложение А:
Вычисление рядов и цепных дробей

Все описанные в данном тексте алгоритмы устроены по единой схеме. Здесь описывается эта схема.

Ряды

В данной работе нам нужно суммировать ряды вида

,

(1) s₀ = 0; s_n+1 = s_n + t_n, n > 0;

в качестве условия останова фигурирует

(2) |s_n+1 - s_n| Ј e ,

где e – требуемая точность счета.

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

(3) |t_n| Ј e .

Однако, вычисления производятся с конечной разрядностью, и потому при уравнивании порядков, необходимом для выполнения операции сложения, прибавляемая к s_n величина t _n+1 может и не совпадать с t_n+1 (т.к. t_n << s_n-1, то при достаточно больших n обязательно будет t _n < t_n). При этом условие (3) начинает выполняться позже условия (2), означающего, что t _n+1 Ј e Поэтому во всех алгоритмах условием останова является именно (2); это приводит к уменьшению числа суммируемых членов ряда.

Машинные эксперименты показали, что использование (3) в качестве условия останова лишь увеличивает время счета, не увеличивая в рассмотренных алгоритмах точность вычислений.

Алгоритмы, основанные на применении рядов, все имеют следующую структуру:

Отметим, что если в условии останова цикла (шаг P3) строгое неравенство заменить на нестрогое, то при e = 0 (т.е. при вычислениях с машинной точностью) алгоритм зациклится.

В нескольких алгоритмах, в которых приходится суммировать «плохо определенные» ряды с знакопеременными членами, условием останова является

(4) abs(s_n - s_n+1) Ј e && abs(s_n+1 - s_n) Ј e.

Цепные дроби

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

Цепной, или непрерывной, дробью называется выражение

(5) 
или

Лично я предпочитаю обозначение (5).

Дробь называется n-м звеном цепной дроби; a_n и b_n – членами ее n-го звена; a₁, a₂,… называют ее частными числителями, а b₁, b₂,… – ее частными знаменателями; b₀ называют нулевым звеном цепной дроби.

Конечная цепная дробь

(6) 

называется n-й подходящей дробью дроби (5). Я опишу здесь три способа, которые можно использовать для вычисления (6).

Способ 1

Этот способ состоит в последовательном осуществлении указанных в (6) действий. Формально процесс можно выразить следующими соотношениями

(7) r_n-i = b_n-i + s_n-i+1, s_n-i = a_n-i/r_n-i, i = 0, 1, …, n-1,

где s₀ = 0. При этом n-я подходящая дробь w_n = b₀ + s₁.

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

Способ 2

В этом способе n-я подходящая дробь вычисляется как отношение p_n/q_n, причем p_n и q_n находят из основных рекурсивных соотношений (см., например, [6]):

(8) 

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

Недостатком его является то, что величины p_n и q_n очень быстро возрастают, если a_n >1, b_n >1, и быстро убывают, если a_n <1, b_n <1. А это может привести либо к переполнению, либо к необходимости деления на (машинный) нуль. Для борьбы с этим применяются разнообразные нормировки, которые лишают алгоритм прозрачности и увеличивают распространяемую ошибку; тем не менее, бывают ситуации, когда без этого не обойтись.

Способ 3

Здесь для n-й подходящей дроби используется следующее соотношение

(9) ,

в котором

(10) r_k = a_k/(b_k-1b_k), 1+ r_k+1 = 1/(1 + r_k+1(1+ r_k)), k і 2,

причем r₁ = r₁ = a₁/b₁, 1+ r₂ = 1/(1 + r₂).

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

Поскольку соотношения (9)-(10) почти не встречаются в имеющейся на русском языке литературе, приведу здесь их вывод.

Широко известно следующее равенство (см., например, [6]):

(11) .

Положим и рассмотрим отношение r_n+1 =A_n-1/A_n. Имеем

;

Алгоритмы, основанные на разложении функции f(x) в цепную дробь, имеют в данном тексте следующую структуру:

Комментарии

Суммирование ряда (11) производится здесь на основе алгоритма P с условием останова (4).

Если бы для вычисления мы использовали соотношения (8), шаги F1 и F2 алгоритма приняли бы вид:

Дальнейшие сведения о цепных дробях и их приложениях можно почерпнуть из книг [3, 6]; изложение способов вычисления цепных дробей, а также множество поучительных численных примеров вы найдете в статье [14].