Введение к работе
Актуальность темы. Впервые AG-последовательности ввел и исследовал Гаусс. Эти последовательности строятся по рекуррентным формулам
Оп+1 =
^~, *„+i = \AX. 11 = 0,1,2,..., (1)
где а0 = 1, bo = к при к Є (0,1). Монотонные последовательности {а„} и {Ьп} сходятся и имеют общий продел /і = и(1>&Ь который выражается в терминах эллиптического интеграла:
л-fpKi.*)]-1.
*/3
[(!,*)= у
\/cos2 <р + к1 sin2 <р
В середине 70-х годов Р. Брент и Ю. Саламжі предложили квадратично сходящийся алгоритм вычисления тт. основанный на AG-последовательностях. Д. и П. Борзейны разработали общую методику построения аналогичных алгоритмов, сходящихся к -лг, а также к некоторым другим величинам. На основании исследований Борвейнов достигнут рехордныЙ результат: тг вычислено с двумя миллиардами десятичных знаков.
Различные обобщения AG-последрвательностеа также служат базой для построения эффективных алгоритмов вычисления специальных функций. К простым схемам вычисления обратных тригонометрических и гиперболических функций приводит алгоритм Борхарда. Числовые последовательности Борхарда строятся по правилу
»п+і = -"2 "' Уп+ї = у/х^ЦШ, п = 0,1,2,... (2) Эти последовательности сходятся к общему пределу, являющемуся
функцией от начальных значений хо, Уо'
н *-г-, О ^ іо < Jfet
О < ш < аго-
В(х0,уо) =
arccos(x0/jfo)' ь arch(s0/»o)'
Одно из возможных обобщений AG-последовательностей связано с увеличением количества начальных данных. В частности, представляют интерес арифметико-геометричесхи-гармонические (AGH) последовательности.
Другое обобщение AG-последовательностей приводит к вырожденным среДНИМ. ПуСТЬ 0 = Oj = Qi — ... = Ота < Om+l ^ <*m+2 ^ < ... < o„, где m Є 1 : n — 1. Вырожденным средним порядка p называется величина
МІР)-і (*&*)
при р > О, при р < 0.
Исследование AG-послєдовательностей и их обобщений связано с построением эффективных алгоритмов вычисления математических констант и специальных функций. Б. А. Карацубой показано, что алгоритмы, основанные па AG-последовательностях, являются оптимальными. Извлеченне квадратного корня считается в таких алгоритмах элементарной операцией подобно сложению, умножению и делению.
Цель работы.
1. Провести детальное исследование быстрого алгоритма Борвей-
HOB ВЫЧИСЛеНИЯ 7Г.
-
Исследовать все возможные варианты алгоритма Борхарда, в которых наряду со средними арифметическими и средними геометрическими используются и средние гармонические.
-
Изучить поведение арифметихо-геометрически-гармонических последовательностей.
-
Провести исследование дифференциальных свойств вырожденных средних.
Методика исследования. Исследование опирается на теорию классических средних а технику оценивания скоростей сходимости вычислительных алгоритмов.
Научная новизна. В диссертации получены следующие основные результаты.
-
Проведено детальное исследование быстрого алгоритма Бор-вейнов вычисления 7Г. Дано более естественное (без выхода в комплексную плоскость) обоснование сходимости алгоритма. Установлены более точные оценки скорости сходимости.
-
Исследованы все варианты алгоритма Борхарда, в которых наряду со средними арифметическими и средними геометрическими используются и средние гармонические. Найдены выражения для предельных величин как функций начальных значений.
-
Изучено поведение арнфметико-геометрнчески-гармонических последовательносгеЯ. Доказано, что все три последовательности сходятся и имеют общий предел. Установлено, что скорость сходимости всех трех последовательностей к общему пределу — квадратичная.
4. Проведено исследование дифференциальных свойств выро
жденных средних. Доказало, что вырожденное среднее как функ
ция своего порядка является бесконечно дифференцируемой: п что
все ее производные з пуле равны нулю.
Практическая ценность. Результаты диссертации могут быть использованы пра построении эффективных алгоритмов вычисления математических констант и специальных функций (в частности, для спецпроцессоров), при анализе высоких скоростей сходимости.
Апробация работы и публикации. По результатам диссертации сделаны доклады на семинаре кафедры исследования операций, кафедры вычислительной математики и на семинаре по нелинейным экстремальным задачам при С.-Петербургском университете, на С.-Петербургском городском семинаре по сложности алгоритмов. По теме диссертации опубликованы две работы.
Структура и объем работы. Диссертация состоит из введения, трех глав, разбитых на 14 параграфов, двух добавлений и списка литературы. Объем диссертации — 97 страниц основного текста. Список литературы насчитывает 40 наименований. В диссертации имеется 23 рисунка и 1 таблица.
