О некоторых проблемах приближения и вычисления классических функций и констант тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Карацуба, Екатерина Анатольевна

• Карацуба, Екатерина Анатольевна
• доктор физико-математических наук
• 2002

Оглавление диссертации доктор физико-математических наук Карацуба, Екатерина Анатольевна

Введение. Специальные функции и их вычисление

I Проблемы приближения некоторых классических функций и констант

1 Проблема аппроксимации константы Эйлера гаммы

1.1 Введение. Постановка задачи.

12 Л-функция и её выражение через специальный интеграл

1.3 Асимптотическое представление для интеграла 1'{х).

1.4 Уточнение асимптотического выражения для интеграла ^{х)

1.5 Оценки для функций приближения к константе -у.

1.6 О вычислении константы Эйлера 7.

2 Проблема аппроксимации гамма-функции Эйлера на основе гипотезы Рамануджана

2.1 Введение. Постановка задачи. Функция.

2.2 Представление к{х) через специальный интеграл J{x).

2.3 Асимптотическое представление для интеграла J{x).

2.4 Асимптотическое представление и оценки для функции к{х)

2.5 Новая асимптотическая формула для гамма-функции Эйлера

2.6 Равномерная оценка остаточного члена.

2.7 Монотонность функции к(х).

2.8 Поведение функции Н{х) на интервале 1 < а; < 4.

Введение диссертации (часть автореферата) на тему «О некоторых проблемах приближения и вычисления классических функций и констант»

3.2 Основной результат.48

3.3 Приложения.58

II Метод БВБ и быстрое вычисление специальных функций математической физики 63

Введение. 64

4 Метод БВБ и быстрое вычисление дзета-функции Римана для целых значений аргумента s 76

4.1 Быстрое вычисление Лф для чётного и отрицательного л . . 76

4.2 Быстрое вычисление константы Апери С(3).78

4.3 Алгоритм быстрого вычисления для целого аргумента л. 81

4.4 Сложность промежуточных вычислений.88

4.5 Сложность вычисления (л(к) при натуральном к , к > 2 . . 90

5 Быстрое вычисление дзета-функции Гурвица и £-рядов Дирихле 92

5.1 Быстрое вычисление дзета-функции Гурвица для рационального аргумента.92

5.2 Быстрое вычисление дзета-функции Гурвица для алгебраического аргумента.98

5.3 Быстрое вычисление £-рядов Дирихле.105

6 Метод БВБ и быстрое вычисление некоторых специальных функций, интегралов и констант 107

6.1 Быстрое вычисление некоторых специальных интегралов математической физики.107

6.2 Быстрое вычисление полилогарифмов и некоторых, связанных с ними, специальных интегралов.112

6.3 Быстрое вычисление константы Каталана.116

6.4 Быстрое вычисление функций Бесселя методом БВБ.117

О тестировании и внедрении метода БВБ 122

Заключение 126

Список литературы 129

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

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

Постоянная Эйлера 7, которая участвует в определении Вейерштрасса гамма-функции Эйлера, является одной из самых важных математических констант. Поскольку подавляющее большинство специальных функций математической физики выражаются формулами, в которые входит гамма-функция Эйлера, то и гамма-функция и константа 7 пользуются большим вниманием как математиков аналитиков,так и математиков вычислителей. В частности, исследования Института Стандартов и Технологий США показали [85], что гамма-функция Эйлера является наиболее часто вычисляемой специальной функцией (занимает место N 1) в различных библиотеках и пакетах программ. Очень важна в приложениях и гипергеометрическая функция. Установлению новых свойств гипергеометрической функции, а также гамма-функции и постоянной Эйлера гаммы посвящена первая часть диссертации.

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

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

Н.С.Бахвалов [14] отмечает:". .в теории численных методов, также как в чистой математике, полезна разработка общих построений. Однако, есть разница в подходе "чистого" и "прикладного" математика к решению какой-либо проблемы. На языке первого понятие решить задачу означает доказать существование решения и предложить процесс, сходящийся к решению. Сами по себе эти результаты полезны для прикладника, но, кроме этого, ему нужно, чтобы процесс приближения не требовал больших затрат, например, времени или памяти ЭВМ. Ему важно не только то, что процесс сходится, но и то, как быстро он сходится." Создание быстрых методов и алгоритмов как раз и призвано решить проблему "оптимального" (по времени) вычислительного процесса.

Быстрые алгоритмы" — это область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью с использованием как можно меньшего числа битовых операций ЭВМ. Реализовав быстрые алгоритмы в программном (а иногда и аппаратном) обеспечении, можно существенно увеличить эффективность компьютера, а иногда и решить задачи, размер которых не позволял найти решение путём применения обычных методов вычисления.

Вторая часть диссертации содержит построение быстрых алгоритмов, основанных на авторском методе БВЕ (Быстрое Вычисление Е-функций), и доказательство оценок сложности вычисления. В 1986-1991 гг. автор разработал основы метода БВЕ и применил его к быстрому вычислению некоторых классов трансцендентных функций [51]-[57]. Были построены алгоритмы для быстрого вычисления простейших трансцендентных функций, классических констант е, тг и постоянной Эйлера 7, а также для вычисления таких высших трансцендентных функций как гамма-функция Эйлера и гипергеометрическая функция. Эти результаты послужили основой кандидатской диссертации автора в 1991 г [57].

В 1992-2001 гг. автор усовершенствовал метод БВЕ и расширил область его применения. На основе БВЕ были разработаны алгоритмы, с помощью которых можно быстро вычислить константу Апери, константу Каталана, дзета-функцию Римана, дзета-функцию Гурвица,£-ряды Дирихле, функции Бесселя, интеграл вероятности Гаусса, интегралы Френеля, интегральные синус и косинус и некоторые другие специальные интегралы математической физики [58]-[68], [72], [73].

Приведём точную формулировку основных результатов диссертации. Перечень этих результатов состоит из шести пунктов, соответствующих главам, в которых эти результаты изложены. Главы объединены по тематике в двух частях диссертации, которая состоит из "Введения", первой части из трёх глав: "Проблемы приближения некоторых классических функций и констант"; второй части из введения и трёх глав: "Метод БВЕ и быстрое вычисление специальных функций математической физики" , раздела "О тестировании и внедрении метода БВЕ" и "Заключения."

Первая часть диссертации посвящена аппроксимации и установлению новых соотношений для некоторых специальных функций и констант.

1. Пусть 7 есть постоянная Эйлера:

Получена оценка скорости сходимости к постоянной 7 последовательностей

1>„ = 1 + А + А+ ••• + --1оеп, 71 = 1,2,3,.,

Лп = 1 + л + I + • • • + л - log + 0 , п = 1,2,3,., и доказана справедливость соотношений:

11 1 1 . „ .11 1

2n 12п2 120п4 12бгаб - - 2п 12п2 120п4'

1.1 1 . „ .1 1 . 23

24п2 24713 + 1207^14 12б7гб - 24.пА 2А.пл Л Шлл'

71 = 1,2,3,.

Доказана теорема (гипотеза Вуоринена) о поведении функции

Я(7г) = 7г2(Д„-7).

Теорема . Функция Н(п) монотонно возрастает от Я(1) = —74-l-log3/2 = 0.0173. (?о 1/24 = 0.0416. 7гр«тг л ос, тг = 1,2,3,.

Обсуждается вопрос о вычислении постоянной 7 с помощью метода БВЕ по формуле, представляющей постоянную Эйлера в виде суммы двух быстро сходящихся рядов: 12Л{-'1Уг/л'Л4Л л 12п (-l)'-7i'-+i л,„„,

Результат опубликован в [70]. 2. Пусть Г(а;) есть гамма-функция Эйлера. Пусть и где

Доказана теорема о монотонности функции /»(»), из которой следует гипотеза Рамануджана, сформулированная им в 1915 году [92]: Если ж > О, то выполняются неравенства

1)' + + ' +155)' <г(1 +

Теорема. Функция к{х) возрастает монотонно на промежутке (1 ,оо) от/1(1)= 13 = 0.0111976. до Л(оо) = А = 0.0333.

Доказательство теоремы основано на доказательстве трёх лемм. Лемма 1. При х > хо = 2.4 функция Н{х) удовлетворяет неравенствам < Цх) < Л; « Цх) л при X -лоо. Лемма 2. При ж > Ж! = 4.21 функция Цх) монотонно возрастает. Лемма 3. При 1 < х < 4.21 функция к{х) монотонно возрастает.

При доказательстве используются асимптотические формулы Стир-линга для функций у = 1о§Г(а;) и ф{х) = а 1о§Г(ж) , а также компьютерные вычисления при 1 < ж < 4.21.

В ходе доказательства получено новое асимптотическое представление для гамма-функции Эйлера:

Т{х + 1) = ЛЛ{ЛУ (8.а + 4жА + ж + 1 - +

3539 9511 10051 47474887

201600ЖЗ 403200ж4 716800ж5 1277337600жб"*'

-ьлл-.+ л-л-д„,х(.))л где Д„+1(ж) = О ( а ) .

При этом доказана равномерная по ж и п оценка значения остаточного члена Дп(ж) : при ж > 2п,

Результат опубликован в [71].

3. Пусть а,п)!"Ь,п) z"

F{а, Ь; с; 2) = 2Л"! (а, 6; с; г,) = А '/ ' , с, п) п!

П = 0 4 у есть гипергеометрическая функция Гаусса. Для функции

L(a, Ь, с, г) = Г{а - 1, Ь; с; г)Г(а, 6; с; 1 - г) +

F(a - 1, Ь; с; 1 - г^?(а, Ь; с; г) - Л(а, Ь; с; г)л(а, Ь; с; 1 - г), при а > 0,6> 0,с> 0, 1>г> О доказана теорема, частным случаем которой является теорема Эллиотта [42], следствием которой, в свою очередь, являются классические соотношения Лежандра для полных эллиптических интегралов [82], [34], [8] .

Теорема. (1) Для с + 1 > аЬ/{а + Ь+1) справедливы утверждения: a) если с>Ь,а + Ь>1 или с < Ь,а + Ь < 1, то L{a, Ь, с, г) строго выпукла. b) если с>Ь,а + Ь<1 или с < Ь, а + 6 > 1, то L(a, 6, с, г) строго вогнута.

2) a) L(a, 6, с, г) > О для с > 6, b) L(a, Ь, с, г) < О для с< Ь, c) L(a, Ь, Ь, г) — Ща, с, с, т") = 0.

3) L(a, Ь, с, г) есть константа для а + Ь = 1.

4) L(a,6,с, 1/2) есть единственный экстремум функции Ь(а,Ь,с,г). Следствиями доказанной теоремы являются новые соотношения для гипергеометрической функции, полученные в предположении, что параметры а, 6 и с — положительные.

Следствие 1. Для О < а < 1, гЕ{а, 1 - а, с -I- 1,г)Е{а, 1 - а, с, 1 - г) +

1 - г)Г{а, 1 - а, с 1 , 1 - г)Г{а, 1-а,с,г) = Г(с)Г(с-Ц) Г(с + а)Г(с-а + 1)'

Следствие 2.

F{a,Ь;c;r)*F{a,b;c+í;r) / 1\

F{a,Ь;c;l-r) " 1'(а,6;с + 1; 1 -г)' ^ 2/

Г{а,Ъ;с;г) Е{а,Ъ;с+1;г) П \

Па,Ъ;с;1-г) л Г(а,Ъ;с + 1;1 -г)'л и' Т'

Следствие 3. При г О (0,1) \ {§}: если с> Ъ,а + Ъ> 1; а + Ъ < с, то (а, 6; с + 1; 0 ^ (а, Ъ; с; < гЕ(а, Ъ; с + 1; г)Е(а, 6; с; 1 - г) +

1 - г)Е(а, 6; с + 1; 1 - г)Е(а, Ъ; с; г) < ¥{а, 6; с + 1; 1). если с> Ъ,а + Ъ<1,а+Ъ<с,то а, 6; с + 1; 1) < гЕ{а, 6; с + 1; г)Е{а, 6; с; 1 - г-)+

1 - г)Г[а, Ь; с + 1; 1 - г)Р(а, Ь; с; г) < Б [а, Ь; с + 1; 0 (Ла, Ь; с; 1) . Следствие 4. Для с > аЬ/(о + Ь + 1) - 1

40. Ь, с; г)Г(а + 1.Ъ+1.е+2;1-г) + ЛЧа.Ь, е; 1 - г)л(о + 1.6+1.е + 27) F(a,b,c+ 1;г)л(а+1,Ь+1,с+1;1-г) + л(а,Ь,с + 1;1 -,|-Жа+ 1,Ь+1,с+1;]-)

1 + 1. с

Следствие 5. Для а + Ь< с, 0<» -< 1,

1'(а, Ь; с; гЩа, Ь; с+ 1; 1 - г) - Б(а, Ь; с; 1 - г-)Б(а, Ь; с + 1; г)| < <Ыа,Ь;с + 1;1)-1Л(а,Ь;с;1)| = с-а)(с-Ь)л ' ' Г ( с - а + 1)Г(с-Ь+1)'

Представлены новые соотношения для других специальных функций, родственных гипергеометрической функции, среди которых

• Для присоединённых функций Лежандра первого рода Р1л(х), при -1<г/<0, 0</л<1, 0 < г < 1 ,

РГЧ1 - 2г)рл'{2г - 1) + РГЧлг - 1)рл*(1 - 2г) =

1 У"1 г(1 -г)/ Г( 1 -/. -г. )Г(2

• Для присоединённых функций Лежандра второго рода Q(л{x), где цжи — действительные числа и г/ > -1/2, для г/ + > -1

•I).

• Для неполных бэта-функций: при х е (0,1/2), р> О, О < д < 1:

Вх{р,ч) > {2ху-"+л-В1{р,д), если р> 1 -д,р>д;

Вх{р,д)<{2ху-л+лВ.(р,д), если р> 1 - д,р< д. Результат опубликован в совместной работе с М.Вуориненом [69].

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

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

4. Для дзета-функции Римана, определяемой рядом Дирихле при Еез = сг >1, 8 = сг 4- й, п=1 и на всей плоскости формулой

7г-л/2г(в/2)СМ = л л л л + 1л (х-"л + жЫ) со{х)ах, где ы{х) = Х)л1ехр(—жтгпл). получены следующие результаты:

• Доказано, что значения С(2то) и С(—2т + 1),т=: 1,2,., можно вычислить с помощью БВЕ со сложностью

0{М(п)\оёЛп).

• Дано описание БВЕ-алгоритма для быстрого вычисления постоянной Апери С(3). При этом использована формула Апери, представляющая константу Апери в виде быстро сходящегося ряда что позволяет вычислить его посредством БВЕ с оценкой сложности вычисления, близкой к оптимальной. Доказана

Теорема. вл(3)(п) = 0(M(n)log2n).

Доказаны новые соотношения для дзета-функции Римана С(*)) представляющие её для любого натурального аргумента 5 = к , к > 2, в виде конечной комбинации быстро суммируемых методом БВЕ рядов. Доказана лемма:

Лемма 1. Пусть к — натуральное число, к > 2, ш, пг,., — целые неотрицательные числа и л .па Й оо где роо

Л] = / е-* tdt. Зо

Тогда справедливо тождество

• Доказана лемма об оценке сложности вычисления интеграла

ЛЗО е-* 1оЛ tdt. Зо

Лемма 2. Для любого фиксированного натурального числа к и любого натурального параметра ], 1 < ]< к, справедлива оценка я]{п) = ОгМ(п) ¡о^Лп).

• Представлен алгоритм быстрого вычисления интеграла 3] = f,^e-4og^tdt.

• С использованием результатов двух лемм доказана основная теорема о сложности вычисления л = Л(В:) при любом натуральном к,к>2.

Теорема. Справедлива оценка

8Л(п) = 0(п1о§лп1о§1о§п).

Результаты опубликованы в [59], [60], [63]-[66].

5. Представлены два алгоритма быстрого вычисления дзета-функции Гур-вица

1/=0 основанные на методе БВЕ: для целого аргумента и алгебраического параметра и для целого аргумента и рационального параметра.

• Доказаны две вспомогательные леммы: Лемма 1. Пусть пх,пг,.,п« — целые неотрицательные числа

Ч + Г»2 + . + «»,= » лоо

Jj = Г e-f-Ho^idt.

Jo

Тогда справедливо тождество eis а) (-1Глул(-1Т-Мг-ВД 1

Лемма 2. sj(n) = 0{M{n)log2n).

• Доказана основная теорема:

Теорема. Для сложности вычисления значения дзета-функции Гурвица л = любом натуральном s = к,к>2, и любом вещественном алгебраическом а, справедлива оценка

8л{п) = 0{М{п) logA п).

• Представлено описание алгоритма и доказана теорема о быстром вычислении £-ряда Дирихле L{s, х) при любом натуральном s = к,к>2.

Пусть m — целое число, m >2; х(0 — произвольный характер Дирихле по модулю т. Тогда при Дез > 1 :

Доказана теорема:

Теорема. Для сложности вычисления значения Ь - ряда Дирихле Ь{8,х) щи любом натуральном з = к,к >2 и любом характере

Дирихле х{1) по модулю т,т> 2, т — целое число,справедлива оценка

БЦп) = 0{М{п)1а^п). Результаты опубликованы в [67].

6. Представлены алгоритмы быстрого вычисления функций Бесселя (при алгебраических значениях аргумента и параметров), некоторых специальных интегралов математической физики , константы Каталана и некоторых других интегралов и констант. Все алгоритмы основаны на методе БВЕ и допускают распараллеливание. Применение этих алгоритмов впервые позволило вычислить вышеупомянутые функции, константы и интегралы быстро, с оценкой сложности вычисления, близкой к наилучшей возможной.

• Для функций (ж есть вещественное число): интеграл вероятности: ег/(ж) = -р / е~* |а;| < ос; ю интегральная экспоненциальная функция:

Ж, х^;

•оо Л интегральные синус и косинус:

Б1{х) = / — Л , Сг{х) = - [ ж >0;

1о I Ух t интегральные гиперболические синус и косинус: г,, , г, , ,, ТСОБЫ-КА Ьпг{х) = I -Ш, С т{х) =-у + 1а§х+---ш;

1о г 1о А интегралы Френеля:

5(.) = 1 г' Ых) = 4= f^dt. доказана теорема:

Теорема. Пусть /(ж) является одной из функций ег/(ш), Ег{х), Бг{х), Сг{х), БМ{х), СЫ{х), С{х), Б{х). Сложность вычисления функции /(ж) в алгебраической точке х = хо с точностью до п знаков есть

Б/{п) = О {М{п)\оА п) .

• представлен алгоритм быстрого вычисление значения полилогарифма и доказано, что сложность вычисления специального интеграла

1к= [Чо^-Ч + у)л , Ге = 2,3,.,г, ^ у есть вКп) = 0(М(п)^Лп).

• Рассматриваются формулы Рамануджана, приближающие постоянную Кат алан а,

О = 1 - -ь 5-2 - + ., и показано, что сложность вычисления постоянной Каталана по этим формулам есть О {М{п) 1одЛ п) операций.

• Представлены основанные на БВЕ алгоритмы быстрого вычисления функции Бесселя для разных значений аргумента и порядка. Доказана основная теорема о сложности вычисления функции Бесселя:

Теорема. Пусть у = Зу (7) есть функция Бесселя V- ого порядка, пусть 2 ии — алгебраические числа. Тогда $){н) = О {М(п) log2 п). Результаты опубликованы в [61]-[62], [72]-[73].

Вышеизложенные результаты диссертации полностью опубликованы в работах автора [51]-[73].

Часть I

Проблемы приближения некоторых классических функций и констант

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Карацуба, Екатерина Анатольевна

Заключение

Изучение широко распространённых в разных областях науки и техники классических функций, интегралов и констант помогает в определении способа их вычисления и выбора наиболее эффективного метода такого вычисления.

Быстрые методы и алгоритмы оптимизируют вычисление какой-либо функции с заданной точностью по количеству затрачиваемых на это вычисление битовых операций электронно-вычислительной машины.

Несмотря на то, что в развитии области быстрых вычислений заинтересован самый широкий круг пользователей и создателей software (а в будущем и hardware), следует отметить, что в настоящее время найдено лишь несколько быстрых методов. Среди этих методов лишь два — АГС и БВЕ дают возможность быстро вычислять простейшие трансцендентные функции и некоторые классические константы, и лишь один — метод БВЕ даёт возможность быстро вычислять функции из широкого класса высших трансцендентных функций (при алгебраических значениях аргумента и параметров), а также специальные интегралы и классические константы.

Алгоритмы, основанные на БВЕ, имеют оценку сложности вычисления, близкую к оптимальной. Дополнительным преимуществом БВЕ-алгоритмов является возможность их распараллеливания.

Обобщая приведённые в диссертации БВЕ-алгоритмы вычисления функций, интегралов и констант, нужно отметить, что схема подхода к каждой задаче может быть представлена следующим образом:

1. Сначала решается проблема представления вычисляемого значения функции, интеграла или константы в виде некоторого "подходящего" ряда. Этот ряд должен

• достаточно быстро сходиться (для того чтобы, для приближения вычисляемого значения с точностью до п знаков требовалось бы не очень много — порядка п — членов ряда) ;

• кроме того, коэффициенты этого ряда должны расти с ростом п не слишком быстро и иметь специальный вид, например, быть целыми числами.

Такими рядами, как было отмечено выше, являются, например, ряды Е

2 / 2 л Е = о при условии, что а{з), Ьл) — целые числа, |а(Я1 + |60')1 < (Сз)л; \г\ < 1\К и С есть константы, и 0 есть алгебраическое число. Такими рядами являются и ряды, представляющие константу Каталана (6.34), (6.35) и вообще все суммируемые во второй части диссертации ряды.

2. Затем оценивается остаток ряда и решается вопрос о том, сколько членов ряда достаточно сложить, или какую сумму 5 достаточно вычислить, чтобы получить вычисляемое значение с заданной точностью.

3. Затем к вычислению суммы 5 применяется одна из двух разработанных модификаций БВЕ метода,

• для рационального аргумента: т.е. комбинируя на каждом шаге слагаемые 5 последовательно попарно и вынося за скобки "очевидный" общий множитель, мы вычисляем на каждом шаге целые значения выражений в скобках, и лишь на последнем шаге производится одно деление с точностью до п знаков целого числителя на целый знаменатель получившейся дроби;

• для алгебраического аргумента ж = а, (считаем, что число а задано как в явной форме, так и некоторым многочленом Л (а) с целыми коэффициентами, корнем которого оно является (зная такой многочлен можно быстро найти значение его корня, например, методом Ньютона). Объединяя слагаемые суммы 5, как и для случая рационального аргумента, мы вычисляем на каждом шаге только целые коэффициенты при степенях ж в многочленах, стоящих в числителе и знаменателе складываемых дробей. Так происходит до некоторого шага (определяемого тем, что на этом шаге степени многочленов числителя и знаменателя превосходят степень многочлена к{а)). Начиная с этого шага, мы редуцируем многочлены числителя и знаменателя по модулю многочлена к{а), не давая степени этих многочленов расти. Вычисления с алгебраическим значением производится лишь на последнем шаге. Поскольку коэффициенты вк{х) являются абсолютными константами и степень /г(ж) есть абсолютная константа, при таких редукциях разрядность чисел, участвующих в вычислениях, может вырасти лишь в постоянное число раз, поэтому сложность вычисления остаётся такой же, как и в случае рационального аргумента.

4. Наконец, проводится оценка сложности вычисления заданного значения с заданной точностью, для того, чтобы

• убедиться, что представленный алгоритм является быстрым; и

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

Таким модифицированным под-алгоритмом является, например, алгоритм вычисления произведения {т- 2'+V)(m - 2'+V - 1). (m - 2'+V -24 1), j = 0, l,.,mj+i — 1, (CM. Введение к части II), который позволяет несколько уменьшить общую сложность вычисления.

Надо отметить, что сложности проводимых вычислений

8f,{n) = 0{M{n)log'n),

SfAn)=0{M{n)\ogn) оценивались для случая последовательного вычисления по методу БВЕ. Распараллеливание алгоритмов, основанных на БВЕ, позволит в будущем уменьшить время работы БВЕ-программ, и это значительно увеличит их эффективность.

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

О {М{п) log" п), где с есть константа, для сложности вычисления высших трансцендентных функций при любом, в том числе иррациональном, аргументе.

Список литературы диссертационного исследования доктор физико-математических наук Карацуба, Екатерина Анатольевна, 2002 год

1. A. V.Aho, J.E.Hopscroft, J.D.Uilman, The design and analysis of computer algorithms. Addison-Wesley Publ. Co., Reading (1974).

2. B. Б. Алексеев, От метода Карацубы для быстрого умножения чисел к быстрым алгоритмам для дискретных функций. Труды Математического Института им. В.А.Стеклова, т. 218, с.20-27 (1997).

3. В.Б.Алексеев, С.А.Ложкин, Элементы теории графов, схем и автоматов. Изд. ВМиК МГУ, Москва (2000).

4. G. Alefeld, J.Herzberger, Introduction to Interval Computations. Academic Press, New York (1983).

5. H. Alzer, Inequalitiesfor the Gamma and Poly gamma Functions. Abh. Math. Se. Univ. Hamburg ,v. 68, pp.363-372 (1998).

6. G.D.Anderson,S.-L.Qiu, M.K. Vamanamurthy and M.Vuorinen, Generalized elliptic integrals and modular equations. Pacific J. Math., v. 192, pp. 1-37 (2000).

7. G.D.Anderson,M.K. Vamanamurthy and M.Vuorinen,

8. Conformal Invariants,Inequalities,and Quasiconformal Maps. Can. Math. Soc, Series of Mon. Adv. Txt., Wiley, New York (1997).

9. G.Andrews, R.Askey, R.Roy, Special Functions, Encyclopedia of Mathematics and it's Application. Vol.71, Cambridge U. Press, Cambridge (1999).

10. E.Bach, The complexity of number-theoretic constants. Info.Proc.Letters, N 62, pp.145-152 (1997).

11. D.H.Bailey, P.B.Borwein and S.PloufFe, On the rapid computation ofvariouspolylogarithmic constants. Math. Comp.,v. 66, pp.903-913 (1997).

12. D.H.Bailey, H.R.P.Ferguson, Numerical Results on Relations Between Fundamental Constants Using a New Algorithm. Math. Comp.,v.53, pp.649-656 (1989).

13. Л.А.Бассалыго, Замечание о быстром умножении многочленов над полями Талу а. Проблемы Передачи Информации, N 1, с. 101102 (1978).

14. Bateman Manuscript Project, Higher Transcendental Functions. (A.Erdelyi, W.Magnus, F.Oberhettinger, F.G.Tricomi, eds.) McGraw-Hill, New York (1953).

15. Н.С.Бахвалов, Численные методы. Изд. Наука, Москва (1975).

16. Ю.В.Бендерский, Быстрые вычисления. Доклады Академии Наук СССР, Т.223, N 5, с.1041-1043 (1975).

17. B.C.Berndt Ramanujan'sNotebook, Parti. Springer-Verlag (1985).

18. B.C.Berndt,Y-S.Choi,and S-Y.Kang, The Problems Submitted by Ramanujan to the Journal of the Indian Mathematical Society. Contemporary Mathematics, v.236, pp.15-56 (1999).

19. A.Borodin, On the number of arithmetics required to compute certain functions circa May 1973. Complexity of Seq. and Par. Numer. Algorithms, Academic Press, New York, pp. 149-180 (1973).

20. A.Borodin and I.Munro, The Computational Complexity of Algebraic and Numeric Problems. American Elsevier, New York (1975).

21. J.M.Borwein and P.B.Borwein, Pi and theAGM. Wiley, New York (1987).

22. J.M.Borwein, D.M.Bradley and R.E.Crandall, Computational strategies for the Riemann zeta function. J. of Comput. Appl. Math., V. 121 ,N 1-2 , pp.247-296 (2000).

23. J.M.Borwein and D.M.Bradley, Empirically Determined AperyLike Formulae for C(4n -f 3). Experimental Mathematics, v. 6 , N 3, pp.181-194 (1996).

24. D.M.Bradley, On a claim of Ramanujan about certain hypergeometric series. Proc. of AMS, vol.121, N 4, pp.1145-1149 (1994).

25. D.M.Bradley, A Class of Series Acceleration Formulae for Catalan's Constant. The Ramanujan Journal, N 3, pp.159-173 (1999).

26. R.P.Brent, Fast Multiple-Precision Evaluation of Elementary Functions. ACM, V.23, N 2, pp.242-251 (1976).

27. R.P.Brent, Multiple-precision zero-Gnding methods and the complexity of elementary function eveduation. Proc.Symp. on Analytic Сотр.Complexity , New York, pp.151-176 (1976).

28. R.P.Brent, Computation ofthe regular continuedfraction for Euler's constant. Math. Сотр., vol.31, pp.771-777 (1977).

29. R.P.Brent and E.M.McMillan, Some new algorithms for high-precision computation of Euler's constant. Math. Сотр., vol.34, pp.305-312 (1980).

30. Ш.Ж. де ла Валле-Пуссен, Курс анализа бесконечно малых. ГТТИ, Москва (1933).

31. И.М. Виноградов, Основы теории чисел.9-е издание. Изд. Наука, Москва (1981).

32. A . Г.Витушкин, Оденка сложности задачи табулирования. Изд. Физматгиз, Москва (1959).

33. B. C.Carlson, Algorithms involving arithmetic and geometric means. Amer. Math. Monthly, v.78, pp.496-505 (1971).

34. B.C.Carlson, An algorithm for computing logarithms and arctangents. Math.Comp., v.26, pp.543-549 (1972).

35. B.C.Carlson, Special Functions of Applied Mathematics. Academic Press, New York (1977).

36. S.A.Cook, On the minimum computation time of functions. Thesis, Harvard University (1966).

37. D.Coppersmith and S.Winograd, On the asymptotic complexity of matrix multiplication. SIAM Journal on Computing, v. 11, N 3, pp.472-492 (1982).

38. D.Coppersmith and S.Winograd, Matrix multiplication via Arithmetic Progressions. J. ACM , v.221, N 7, pp.1-6 (1987).

39. R.E.Crandall, On the quantum zeta function. J. Phys. A. Math. Gen, V. 29, pp.6795-6816 (2000).

40. R.E.Crandall and J.P.Buhler, On the evaluation of Euler sums. Experimental Mathematics, v.3, N 4, pp.275-285 (1995).

41. D. W.DeTemple, A Quicker Convergence to Euler's constant. The American Math. Monthly 100(5), pp.468-470 (1993).

42. P.L.Duren, The Legendre relation for elliptic integrals, in Paul Halmos: Celebrating 50 years of Mathematics. J.H.Ewing and F.W.Gehring,eds., Springer-Verl.,New York, pp.305-315 (1991).

43. E. B.Elliott, A formu.ainciudingLegendre's£;iiL4iiC£;'-iiLiiC' = §7Г. Messenger of Math. 33 (1904), 31-40.

44. G.M.Fichtenholz, Differential- und Integralrechnung, vol. 2, VEB Deutscher Verlag der Wissenschaften, Berlin (1964).

45. С.Б.ГашКОВ, О сложности интегрирования рациональных дробей. Труды Математического Института им. В.А.Стеклова, т. 218, с.122-133, (1997).

46. K.F.Gauss, WerJre. Bd 1-3, Göttingen, (1876).

47. K.F.Gauss, Arithmetische-Geometrische Mittel. Werke, Bd 3, Reprinted by Olms, Hildescheim, pp.361-432, (1987).

48. А.Карацуба и Ю.Офман, Умножение многозначны1х чисел на автоматах. Доклады Академии Наук СССР т. 145, N 2, с.293-294(1962).

49. A.Karacuba, Berechnungen und die Kompliziertheit von Beziehungen. EIK, N 11, s.10-12 (1975).

50. A.A.Karatsuba and S.M.Voronin, Tie Riemann Zeta-Function. W. de Gruyter, Berlin (1992).

51. A. А.Карацуба, Сложность вычислений. Труды Математического института им. В.А.Стеклова, т.211, с. 169-183 (1995).

52. Е.А.Карацуба, Арифметическо-геометрического среднего (АГС) методы для быстрого вычисления констант типа тт. Проблемы передачи информации , Т.25, N3, с.11, Хроника-16ая Всесоюзнгья школа по теории информации и её приложениям (1989).

53. Е.А.Карацуба, Быстрое вычисление ехр{х). Проблемы передачи информации, Т.26, N 3, с.109, Хроника-17ая Всесоюзная школа по теории информации и её приложениям (1990).

54. Е.А.Карацуба, О новом методе быстрого вычисления трансцендентных функций. Успехи Математических Наук, т.46, N 2 (278), с.219-220 (1991).

55. Е.А.Карацуба, О быстром вычислении трансцендентных функций. Доклады Академии Наук СССР , т.319, N 2, с.278-279 (1991).

56. Е.А.Карацуба, Быстрое вычисление трансцендентных функций.

57. Проблемы передачи информации, т.27, N 4, с.87-110 (1991).

58. Е.А.Карацуба, Оценка эффективности быстрых алгоритмов для вычисления некоторых классов трансцендентных функций. Автореферат диссертации, Москва, 10 с. (1991).

59. Е.А.Карацуба, Оценка эффективности быстрых алгоритмов для вычисления некоторых классов трансцендентных функций. Диссертация, Москва, 95 с. (1991).

60. Е.А.Карацуба, Сложность вычисления трансцендентных функций . Доклады Зей Всесоюзной Конференции по Суперкомпьютерам, Москва (1992).

61. Е.А.Карацуба,Быстрое вычисление значения (А(Ъ),((ф) дзета-функция Римана). Проблемы передачи информации , т.28, N 3, С.112, Хроника-19ая Всероссийская школа по теории информации и её приложениям (1992).

62. Е.А.Карацуба,Быстрое вычисление С(З). Проблемы передачи информации , T.29, N 1, с.68-73 (1993).

63. Catherine A.Karatsuba, Fast evaluation of Bessel functions. Integral Transforms and Special Functions, v. l, N4, pp. 269-276 (1993).

64. Е.А.Карацуба, Метод БВЕ. Доклады второй международной конференции "Математические Алгоритмы", Нижний Новгород, (1995).

65. E.A.Karatsuba, On the FEE-Method Method for Fast Evaluating the Functions Like E-Functions. Abstracts of the International Conference "Symbolic Calculations and Their Application in Fundamental Reseachers", ITA RAS, St.Petersburg, p.26 (1995).

66. Е.А.Карацуба, Быстрое вычисление дзета-функции Римана C(s) для целых значений аргумента s. Проблемы передачи информации, Т.31, N 4, с.69-80 (1995).

67. Е.А.Карацуба, О быстром вычислении дзета-функции Римана для целых значений аргумента. Доклады Академии Наук СССР, Т.349, N 4, С.463 (1996).

68. Е.А.Карацуба, Быстрое вычисление дзета-функции Гурвица и L-рядов Дирихле. Проблемы передачи информации, т. 34, N 4, с. 342-353 (1998).

69. Ekatharine А. Karatsuba, Fast evaluation of hypergeometric function by FEE. Computational Methods and Function Theory (CMFT'97), N.Papamichael, St.Ruscheweyh and E.B.Saff, eds. World ScPub., pp. 303-314 (1999).

70. E.A.Karatsuba, M.Vuorinen, On hypergeometric functions and generalization of Legendre'srelation. University of Helsinki preprint, 16 pp. (1998); J. of Math.Anal.a.Appl., v. 260, pp.623-640, (2001).

71. E.A.Karatsuba, On the computation of the Euler constant gamma. University of Helsinki preprint, 21 pp. (1999); J. of Numerical Algorithms, V. 24, pp.83-97, (2000).

72. E.A.Karatsuba, On the asymptotic representation of the Euler gamma function by Ramanujan. University of Helsinki preprint, 22 pp. (1999); J. of Comput.a.Appl. Mathematics, v. 135, N 2, pp.225240 (2001).

73. E.A.Karatsuba, Fast computation of C(3) and of some special integrals ,using the polylogaiithms, the Ramanujan formula and it's generalization. 3. ofNumerical Mathematics BIT, v. 41, N 4, pp.722730 (2001).

74. E.A.Karatsuba, Fast computation of some special integrals of mathematical physics. Scientific Computing, Validated Numerics, Interval Methods, W.Kramer, J.W.von Gudenberg, eds., pp.29-41, (2001).

75. Р.Клатте, У.Кулиш, М.Неага, Д.Рау, Х.Ульрих, PASCAL-XSC. Язык численного программирования. Изд. ДМК Пресс, Москва (2000).

76. Д.Е.Кнут, Искусство программирования на ЭВМ. т.2. Изд. Мир, Москва (1977).

77. А.Н.Колмогоров, О некоторых асимптотических характеристиках вполне ограниченных метрических пространств. Доклады Академии Наук СССР, т. 108, N 3, с.385-388 (1956).

78. А.Н.Колмогоров, Различные подходы к оценке трудности приближённого задания и вычисления функций. Proc.Intern.Congr.Math.Stokholm, с.369-376 (1963).

79. A. Н.Колмогоров, Теория информации и теория алгоритмов. Изд. Наука, Москва (1987).

80. Kronsjo,Algorithms. Their ComplexityemdEiEciency. Wiley, New York (1987).

81. J.Landen, An investigation of a general theorem for finding the length ofany arc of any conic hyperbola, by means of two elliptic arcs, with some other new and useful theorems deduced therefrom. Philos.Trans.Royal Soc. London v.65 ,pp.283-289 (1775).

82. B. И.Левин, Об одной задаче Рамапуджана. Успехи Мат. Наук, Т.5, N 3(37), с. 161-166 (1950).

83. A.M.Legendre, Exercices de calculintegral, v. l ,Paris (1811).

84. P.Lindqvist and J.Peetre, On the Remainder in a Series of JWertens. Expo.Math., N 15, pp.467-478 (1997).

85. D.W.Lozier and F.W.J.01ver, Numerical Evaluation of Special Functions. Mathematics of Computation 1943-1993: A Half-Century of Computational Mathematics, W.Gautschi,eds., Proc. Sympos. Applied Mathematics, AMS, v.48, pp.79-125 (1994).

86. D.W.Lozier, Software Needs in Special Functions. J. of Comp.a.Applied Mathematics, v.66, pp.345-358 (1996).

87. W. Magnus und F. Oberhettinger , Formeln und Sätze für diespeziellen Funktionen der mathematischen Physik. Springer-Verlag, Berlin, (1948).

88. R.E. Moore, Methods and Applications of Interval Analysis. SIAM, Philadelphia, (1979).

89. N.Nielsen, Theorie des Integrallogarithmus und verwandter Transcendenten. Teubner , Leipzig (1906).

90. V.Ya.Pan, Strassen 's algorithm is not optimal. Proc. ACM Symp. on the Found, of Comp.Science, pp.166-176 (1978).

91. A. van der Poorten, A Proof that Euler missed . Apery's proof of the irrationality of Math.Intelligencer, v.l ,pp.l95-204 (1979).

92. S.Ramanujan Question 754. J. of Indian Math.Soc, vol. 8, p.80 (1915).

93. S.Ramanujan Collected papers of SrinivasaRamanujan. Cambridge University Press, Cambridge (1927).

94. S.Ramanujan, The lost notebook and other unpublished papers. Intr. by G.E.Andrews, Narosa Publ.H.-Springer Verl.,New Delhi-Berlin (1988).

95. E. Salamin, Computation of тг using arithmetic-geometric mean. Math. Сотр., vol.30, N 135, pp.565-570 (1976).

96. A. S chönhage, Schnelle Multiplikation grosser Zahlen. Computing, v.l, pp.182-196 (1966).

97. A.Schönhage und V.Strassen, Schnelle Multiplikation grosser Zahlen. Computing, v.7, pp.281-292 (1971).

98. A.Schonhage, A.P.W.Grotefeld and E.Vetter, Fast Algorithms. Bl-Wiss.-Verl., Zürich. (1994).

99. C.L.Siegel, Haascendental numbers. Princeton University Press ,Princeton (1949).

100. V.Strassen, Gaussian elimination is not optimal. J. Numer. Math., N 13, pp.354-356 (1969).

101. V.Strassen, The asymptotic Spectrum of Tensors and the Exponent of Matrix Multiplication. J.FOGS, pp.49-54 (1986).

102. N.M.Temme, Special functions: an introduction to the classical functions of mathematical physics. A Wiley-Interscience Publ., John Wiley and Sons Inc., New-York (1996).

103. S.R.Tims and J.A.Tyrell, Approximate evaluation of Euler's constant. Math.Gaz., N 55, pp.65-67 (1971).

104. А.Л.Т00М, О сложности схемы из функциональных элементов, реализующей умножение целых чисел. Доклады Академии Наук СССР, т. 150, N 2, с.496-498 (1963).

105. G.N.Watson, А Treatise on the Theory of Bessel Functions. Cambridge Univ. Press, Cambridge (1944).

106. E.T.Whittaker and G.N.Watson, A Course ofModernAnalysis. Cambridge Univ. Press, Cambridge (1958).

107. R.M.Young, Buler's Constant. Math.Gaz., N 75 (472), pp.187-190 (1991).