Некоторые вычислительные применения арифметико-геометрических последовательностей и их обобщений тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи УДК 519.677

Дмитриева Оксана Михайловна

НЕКОТОРЫЕ ВЫЧИСЛИТЕЛЬНЫЕ

ПРИМЕНЕНИЯ АРИФМЕТИКО-ГЕОМЕТРИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ И ИХ ОБОБЩЕНИЙ

01.01.07 — вычислительная математика

|ч'Б ОА 1 а.йсл

АВТОРЕФЕРАТ

Диссертации на соискание ученой степени кандидата физико-математических наук

Санкт- Петербург 1996 г.

Работа выполнена на кафедре исследования операций математик о-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель — доктор физико-математических наук, профессор Малоземов Василий Николаевич

Официальные оппоненты — доктор физико-математических наук, профессор Рябов Виктор Михайлович

кандидат физико-математических наук, доцент Певный Александр Борисович

Ведущая организация — Российский государственный педагогический университет им. А. И. Герцена

Защита состоится « и » йС/иЬь/и^ 1996 г.

в часов на заседании диссертационного совета Д 063.57.30 по

защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, г. Санкт-Петербург, Петродворец, Библиотечная пл., 2, математик о-механический факультет.

С диссертацией можно ознакомиться в научной библиотеке университета по адресу: 199034, г. Санкт-Петербург, Университетская наб., 7/9.

Автореферат разослан <* % МЩЛ' 1996 г.

Ученый секретарь диссертационного совета

Ю. А. Сушков

Обшдя характеристика работы

Актуальность темы. Впервые АО-последовательности ввел и исследовал Гаусс. Эти последовательности строятся по рекуррентным формулам

Оп+1 =

*„+1 = \АХ> г» = 0,1,2,..., (1)

где а0 = 1, Ьо = к при к € (0,1). Монотонные последовательности {а„} и {Ь„} сходятся и имеют общий продел у. = который

выражается в терминах эллиптического интеграла:

где

*/з

1(1,*)= /

tЬр

о \/cos2 V + к7 sin2 <р

В середине 70-х годов Р. Бреит н Ю. Саламнн аредложшш квадратично сходящийся алгоритм вычисления тг, основанный на AG-последователыгостях. Д. в П. Борэейны разработали общую методику построения аналогичных алгоритмов, сходящихся к ir, а также к некоторым другим величинам. На основании исследований Борвейнов достигнут рекордный результат: тг вычислено с двумя миллиардами десятичных знаков.

Различные обобщения AG-последовательностей также служат базой для построения эффективных алгоритмов вычисления специальных функций. К простым схемам вычисления обратных тригонометрических и гиперболических функций приводит алгоритм Борхарда. Числовые последовательности Борхарда строятся по правилу

"i* Уп

Зм-1 = -" №»+1 = y/xn+iу„, п = 0,1,2,... (2)

Эти последовательности сходятся к общему пределу, являющемуся

функцией от начальных значений хо, Уо'

В(*о,Уо) =

Одно из возможных обобщений AG-последовательностей связано с увеличением количества начальных данных. В частности, представляют интерес арифметгасо-геометричесхи-гармонические (AGII) последовательности.

Другое обобщение AG-последовательностей приводит к вырожденным средним. Пусть 0 = cj = аг = ... = ота < am+i < а.т+2 < < ... < а„, где т 6 1 : п — 1. Вырожденным средним порядка р называется величина

мы А 14)11 р>0'

[ 0 при р ^ 0.

Исследование AG-последовательностей и кх обобщений связано с построением эффективных алгоритмов вычисления математических констант и специальных функций. Б. А. Карацубой показано, что алгоритмы, основанные па AG-последовательностях, являются оптимальными. Извлечение квадратного корня считается в таких алгоритмах элементарной операцией подобно сложению, умножению и делению.

Цель работы.

1. Провести детальное исследование быстрого алгоритма Борвей-нов вычисления ст.

2. Исследовать все возможные варианты алгоритма Еорхарда, в которых наряду со средними арифметическими и средними геометрическими используются и средние гармонические.

3. Изучить поведение арифметихо-геометрически-гармонических последовательностей.

4. Провести исследование дифференциальных свойств вырожденных средних.

УУо-Др п <- nr ^ ,,„ -—г-т, 0 ^ хо < Уо,

arccos(x0/ifo) У^р-Уо

aicb(xn/va)'

0 < < хо.

Методика исследования. Исследование опирается на теорию классических средних а технику оценивания скоростей сходимости вычислительных алгоритмов.

Научная новизна. В диссертации получены следующие основные результаты.

1. Проведено детальное исследование быстрого алгоритма Бор-вейнов вычисления л. Дано более естественное (без выхода в комплексную плоскость) обоснование сходимости алгоритма. Установлены более точные оценки скорости сходимости.

2. Исследованы все варианты алгоритма Борхарда, в которых наряду со средними арифметическими и средними геометрическими используются и средние гармонические. Найдены выражения для предельных величин как функций начальных значений.

3. Изучено поведение арифметик»-геометрически-гармонических последовательностей. Доказано, что все три последовательности сходятся и имеют общий предел. Установлено, что скорость сходимости всех трех последовательностей к общему пределу — квадратичная.

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

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

Апробация работы и публикации. По результатам диссертации сделаны доклады на семинаре кафедры исследования операций, кафедры вычислительной математики и на семинаре по нелинейным экстремальным задачам при С.-Петербургском университете, на С.-Петербургском городском семинаре по сложности алгоритмов. По теме диссертации опубликованы дае работы.

Структура и объем работы. Диссертация состоит из введения, трех глав, разбитых на 14 параграфов, двух добавлений и списка литературы. Объем диссертации — 97 страниц основного текста. Список литературы насчитывает 40 наименований. В диссертации имеется 23 рисунка и 1 таблица.

Содержание работы

Во введении дан краткий исторический обзор и сформулированы основные результаты диссертации.

Глава I посвящена исследованию быстрого алгоритма Борвейнов вычисления тг:

тго = 2 + л/2, а0 = \/2, & = </2\

п = 0,1,2,...

ап+1 + 1

Тп+1 П = 0,1,2,...

(3)

Алгоритм основан на дифференцировании по параметру к рекуррентных соотношений (1), оиределяющих АС-последователыюсти. Оказалось, что такой алгоритм имеет высокую скорость сходимости. Борвейками установлены оценки: при п > 1

1

"п+1 — я* < ^О^п ~ "")

и при п ^ 2

7Г„ - 1Г < 10 2

В главе I дано более естественное (без выхода в комплексную плоскость) обоснование сходимости алгоритма (3) и установлены более точные оценки скорости сходимости: при п > 1

Тп+1 " * < ¿(^ ~ (4)

и при га ^ 2

7Гп-7г<10-гП+1-2П"1+2. (5)

В §1.2,1.3 указаны известные, в основном, свойства АС-последо-вателыюстей в том ввде, в каком они в дальнейшем используются. В §1.4 изучаются вспомогательные рекуррентные последовательности {х„} и {уп}, {<*«} и {/?„}• На базе результатов §1.4 в §1.5 дается обоснование предельного соотношения Борвейнов для х.

В §1.6 выводятся рекуррентные формулы (3). В §1.7 доказываются оценки (4) и (5).

Отметим, что в §1.7 получены апостериорные оценки, имеющие и самостоятельный интерес: при п > 1

1.57 < , Жп~7Г < 1.58.

<n+l ~ «п+1

Кроме того, установлено предельное соотношение

Иш

n-++co £п+1 — а„+1 2

Наряду с (5) выведена асимптотически более точная оценка: при п> 1

тг„ — 7Г < 80 • 2n+1 • 20~2"+1.

Глава II посвящена анализу алгоритма Ворхарда и его обобщений. В §2.2 вместе с (2) изучается поведение последовательностей {Х„} и {У„}, построенных по рекуррентным формулам

Уп+i = s/YnX„, Xn+i д '" Г>+1' n = 0,1,2,...

с начальными данными Хд = 1, ¥о = к и .Хо = к, Уо — 1 при Ар е (0,1).

В §2.3 исследованы все варианты алгоритма Борхарда, в которых наряду со средними арифметическими и средними геометрическими используются и средние гармонические. Аналогично алгоритму Борхарда строится итерационная процедура на основе среднего гармонического и среднего геометрического

«T»+I = 2UnVv , t>„+l = v/lin+lWn, 71 = 0,1,2,... (6)

«п "Г Vn

Рассматриваются два случая начальных данных: Uo = 1, vo = к и «о = к, vq = 1 при к 6 (0,1). Кроме итерационной процедуры (б), проводится исследование алгоритма, построенного по принципу алгоритма Борхарда, на основе среднего арифметического и среднего гармонического

... ^n + 7n „ _ 2^п+Пп „_П10

шп+1 =---, VI = ,, г- » « = 0,1,2,...

* wn+1 + 7п

с начальными данными = 1, 70 — А и и>о — к, 70 = 1 при к € (0,1). Последовательности {о>п} и {7п} стремятся к общему пределу. Для него установлена явная формула. Всего в главе II представлено двенадцать вариантов алгоритма Борхарда, из них шесть — новых. Найдены выражения для предельных величин как функций начальных значений.

В главе III рассматриваются некоторые вопросы, связанные с обобщенными средними. В §3.2 строятся три последовательности на основе среднего арифметического, среднего геометрического и среднего гармонического трех положительных чисел. Доказывается, что все три последовательности сходятся и имеют общий предел, который и назван AGH-средним. Установлено, что скорость сходимости всех трех последовательностей к общему пределу — квадратичная.

В §3.3 рассматриваются средние L(p) порядка р чисел 0 < bx ^ ^ Ь2 < ... < Ьп при условии bi < Ьп. Доказывается, что функция L{p) является бесконечно дифференцируемой при всех вещественных р.

В §3.4 изучаются вырожденные средние. Установлено, что вырожденное среднее как функция своего порядка является бесконечно дифференцируемой и что все ее производные в нуле равны нулю.

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

Основное содержание диссертации опубликовано в работах:

1. Дмитриева О. М. Средние Борхарда. Деп. в ВИНИТИ от 12 апреля 1996 г., № 1182-В96.

2. Дмитриева О. М., Малоземов В. Н. Об одном бистром алгоритме вычисления тт. Деп. в ВИНИТИ от 22 июня 1995 г., № 1807-В95.

Подписано к печати 14.11.96г. Заказ 152. Тираж 100 экз. Объем 0,8 п.л. ПМЛ СИГУ. 199034, Санкт-Петербург, наб. Макарова, 6.