К разделу 'Математика' сайта AlgoList.

Назад Оглавление Вперед

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

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

Ряды

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

, где tn+1 = g(tn). Вычисления производятся стандартным способом:

(1) s0 = 0; sn+1 = sn + tn, n > 0;

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

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

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

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

(3) |tn| Ј e .

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

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

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

/* P1 */   sum = term = t0;
           do
/* P2 */     term = g(term); s = sum; sum = s + term;
/* P3 */   while abs(s - sum) >
e ;
           return sum;
Рис. 1. Структура алгоритма, вычисляющего разложение в ряд.

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

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

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

 

Цепные дроби

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

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

Из-за громоздкости этого способа записи он почти не используется. Обычно цепную дробь записывают в виде

(5) 
или

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

Дробь называется n-м звеном цепной дроби; an и bn – членами ее n-го звена; a1, a2,… называют ее частными числителями, а b1, b2,… – ее частными знаменателями; b0 называют нулевым звеном цепной дроби.

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

(6) 

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

Способ 1

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

(7) rn-i = bn-i + sn-i+1, sn-i = an-i/rn-i, i = 0, 1, …, n-1,

где s0 = 0. При этом n-я подходящая дробь wn = b0 + s1.

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

Способ 2

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

(8) 

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

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

Способ 3

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

(9) ,

в котором

(10) rk = ak/(bk-1bk), 1+ rk+1 = 1/(1 + rk+1(1+ rk)), k і 2,

причем r1 = r1 = a1/b1, 1+ r2 = 1/(1 + r2).

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

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

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

(11) .

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

; Здесь использовано соотношение (8). Но из (8) также следует qn+1= (qn- anqn-2)/bn Положим . Так как rn = - anqn-2/qn, получаем rn+1 = - rn+1(1+rn)/(1+rn+1(1+rn)). Отсюда и из (11) следуют соотношения (9)-(10).

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

/*F1 */ t = b0; term = a1/b1; s = t+term; rho = 1/(1+a2/b1/b2);
        term = (rho-1)*term; sum = s+term; k=3;
        do
/*F2 */    r = ak/bk-1/bk; rho = 1/(1+r*rho);
           term = (rho-1)*term; t = s; s = sum; sum = s+term;
           k = k+1;
/*F3 */ while abs(t-s) > e & abs(s-sum) > e ;
        return sum;
Рис. 2. Структура алгоритма, вычисляющего цепную дробь.

Комментарии

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

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

/*F'1 */ p0 = b0; q0 = 1; q1 = b1; p1 = p0*q1+a1; sum = p1/q1; k = 1; и /*F'2 */ k = k+1; t = bkp1+ak*p0; p0 = p1; p1 = t;
t = bk*q1+ak*q0; q0 = q1; q1 = t;
t = s; s = sum; sum = p1/q1;
Мы видим, что число операций, выполняемых в теле цикла, при этом не уменьшилось бы.

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

На правах рекламы
воронежский интернет магазин обуви.