Алгоритм повторения Миллера

Рекуррентный алгоритм Миллера — это процедура вычисления быстро убывающего решения линейного рекуррентного соотношения , разработанная JCP Miller . ^{[ 1 ]} Первоначально он был разработан для вычисления таблиц модифицированной функции Бесселя. ^{[ 2 ]} но также применяется к функциям Бесселя первого рода и имеет другие приложения, такие как вычисление коэффициентов разложений Чебышева других специальных функций. ^{[ 3 ]}

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

Модифицированные функции Бесселя первого рода $I_{n}(x)$ удовлетворить рекуррентное соотношение

I_{n-1}(x)={\frac {2n}{x}}I_{n}(x)+I_{n+1}(x)

.

Однако модифицированные функции Бесселя второго рода $K_{n}(x)$ также удовлетворяют тому же рекуррентному соотношению

K_{n-1}(x)={\frac {2n}{x}}K_{n}(x)+K_{n+1}(x)

.

Первое решение быстро убывает с ростом $n$ . Второе решение быстро возрастает с ростом $n$ . Алгоритм Миллера обеспечивает численно устойчивую процедуру получения убывающего решения.

Чтобы вычислить условия повторения $a_{0}$ через $a_{N}$ согласно алгоритму Миллера сначала выбирают значение $M$ намного больше, чем $N$ и вычисляет пробное решение, принимая начальные условия $a_{M}$ произвольному ненулевому значению (например, 1) и приняв $a_{M+1}$ и более поздние члены равны нулю. Затем рекуррентное соотношение используется для последовательного вычисления пробных значений для $a_{M-1}$ , $a_{M-2}$ вплоть до $a_{0}$ . Учитывая, что вторая последовательность, полученная из пробной последовательности путем умножения на постоянный нормировочный коэффициент, по-прежнему будет удовлетворять тому же рекуррентному соотношению, можно затем применить отдельное нормализующее соотношение для определения нормализующего коэффициента, который дает фактическое решение.

В примере модифицированных функций Бесселя подходящим нормализующим соотношением является суммирование, включающее четные члены рекуррентности:

I_{0}(x)+2\sum _{m=1}^{\infty }(-1)^{m}I_{2m}(x)=1

где бесконечное суммирование становится конечным из-за приближения, что $a_{M+1}$ и более поздние члены равны нулю.

Наконец, подтверждается, что ошибка аппроксимации процедуры приемлема путем повторения процедуры со вторым выбором $M$ больше, чем первоначальный выбор, и подтверждая, что второй набор результатов для $a_{0}$ через $a_{N}$ согласовать в пределах первого набора в пределах желаемого допуска. Обратите внимание, что для получения этого соглашения значение $M$ должно быть достаточно большим, чтобы член $a_{M}$ мал по сравнению с желаемым допуском.

В отличие от алгоритма Миллера, попытки применить рекуррентное соотношение в прямом направлении, начиная с известных значений $I_{0}(x)$ и $I_{1}(x)$ полученные другими методами, не будут иметь успеха, поскольку ошибки округления вносят компоненты быстро растущего решения. ^{[ 4 ]}

Олвер ^{[ 2 ]} и Гаучи ^{[ 5 ]} подробно анализирует распространение ошибок алгоритма.

Для функций Бесселя первого рода эквивалентные рекуррентное соотношение и нормализующее соотношение имеют вид: ^{[ 6 ]}

J_{n-1}(x)={\frac {2n}{x}}J_{n}(x)-J_{n+1}(x)

J_{0}(x)+2\sum _{m=1}^{\infty }J_{2m}(x)=1

.

Алгоритм особенно эффективен в приложениях, которым требуются значения функций Бесселя для всех порядков. $0\cdots N$ за каждое значение $x$ по сравнению с прямыми независимыми вычислениями $N+1$ отдельные функции.

Ссылки

^ Бикли, В.Г.; Комри, LJ; Сэдлер, Д.Х.; Миллер, JCP; Томпсон, Эй Джей (1952). Британская ассоциация содействия развитию науки, Mathematical Tables, vol. X, Функции Бесселя, часть II, Функции целого положительного порядка . Издательство Кембриджского университета. ISBN 978-0521043212 . , цитируется в Олвере (1964).
^ Перейти обратно: ^а ^б Олвер, FWJ (1964). «Анализ ошибок алгоритма повторения Миллера». Математика. Комп . 18 (85): 65–74. дои : 10.2307/2003406 . JSTOR 2003406 .
^ Немет, Г. (1965). «Разложения Чебышева для интегралов Френеля». Число. Математика . 7 (4): 310–312. дои : 10.1007/BF01436524 .
^ Харт, Дж. Ф. (1978). Компьютерные приближения (переиздание). Малабар, Флорида: Роберт Э. Кригер. стр. 25–26. ISBN 978-0-88275-642-4 .
^ Гаучи, Уолтер (1967). «Вычислительные аспекты трехчленных рекуррентных отношений» (PDF) . Обзор СИАМ . 9 : 24–82. дои : 10.1137/1009002 .
^ Арфкен, Джордж (1985). Математические методы для физиков (3-е изд.). Академическая пресса. п. 576 . ISBN 978-0-12-059820-5 .

[Miller-1] Бикли, В.Г.; Комри, LJ; Сэдлер, Д.Х.; Миллер, JCP; Томпсон, Эй Джей (1952). Британская ассоциация содействия развитию науки, Mathematical Tables, vol. X, Функции Бесселя, часть II, Функции целого положительного порядка . Издательство Кембриджского университета. ISBN 978-0521043212 . , цитируется в Олвере (1964).

[Olver-2] Перейти обратно: ^а ^б Олвер, FWJ (1964). «Анализ ошибок алгоритма повторения Миллера». Математика. Комп . 18 (85): 65–74. дои : 10.2307/2003406 . JSTOR 2003406 .

[Nemeth-3] Немет, Г. (1965). «Разложения Чебышева для интегралов Френеля». Число. Математика . 7 (4): 310–312. дои : 10.1007/BF01436524 .

[Hart-4] Харт, Дж. Ф. (1978). Компьютерные приближения (переиздание). Малабар, Флорида: Роберт Э. Кригер. стр. 25–26. ISBN 978-0-88275-642-4 .

[Gautschi-5] Гаучи, Уолтер (1967). «Вычислительные аспекты трехчленных рекуррентных отношений» (PDF) . Обзор СИАМ . 9 : 24–82. дои : 10.1137/1009002 .

[Arkfen-6] Арфкен, Джордж (1985). Математические методы для физиков (3-е изд.). Академическая пресса. п. 576 . ISBN 978-0-12-059820-5 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]