Все описанные в данном тексте алгоритмы устроены по единой схеме. Здесь описывается эта схема. Ряды В данной работе нам нужно суммировать ряды вида , где 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].  8  Комментарии к статье  8 8  Обсудить в чате