Алгоритм Ленца

В математике алгоритм Ленца — это алгоритм вычисления цепных дробей и вычисления таблиц сферических функций Бесселя . ^{[ 1 ]}^{[ 2 ]}

Версия, обычно используемая сейчас, принадлежит Томпсону и Барнетту. ^{[ 3 ]}

История

Идея была предложена в 1973 году Уильямом Дж. Ленцем. ^{[ 1 ]} и был упрощен им в 1982 году. ^{[ 4 ]} Ленц предположил, что вычисление отношений сферических функций Бесселя от комплексных аргументов может быть затруднено. Он разработал новую технику цепной дроби для вычисления отношений сферических функций Бесселя последовательного порядка. Этот метод был улучшением по сравнению с другими методами, поскольку он начинался с начала цепной дроби, а не с хвоста, имел встроенную проверку сходимости и был численно стабильным. Исходный алгоритм использует алгебру для обхода нуля либо в числителе, либо в знаменателе. ^{[ 5 ]} Более простые улучшения для устранения нежелательных нулевых членов включают измененное рекуррентное соотношение. ^{[ 6 ]} предложенный Яаскелайненом и Руусканеном в 1981 году, или простой сдвиг знаменателя на очень небольшое число, как предложили Томпсон и Барнетт в 1986 году. ^{[ 3 ]}

Начальная работа

Первоначально эта теория была мотивирована необходимостью Ленца точно вычислить отношения сферической функции Бесселя, необходимые для рассеяния Ми . Он создал новый алгоритм цепной дроби, который начинается с начала цепной дроби, а не с ее конца. Это позволяет не гадать, сколько членов цепной дроби необходимо для сходимости. Кроме того, с помощью алгоритма Ленца можно вычислить представления цепных дробей как для отношений функций Бесселя, так и для сферических функций Бесселя последовательного порядка. ^{[ 5 ]} Алгоритм предполагал, что можно прекратить вычисление цепных дробей, когда $|f_{j}-f_{j-1}|$ сравнительно невелик. ^{[ 7 ]}

Алгоритм

Алгоритм Ленца основан на соотношениях Уоллиса-Эйлера . Если

{f}_{0}={b}_{0}

{f}_{1}={b}_{0}+{\frac {{a}_{1}}{{b}_{1}}}

{f}_{2}={b}_{0}+{\frac {{a}_{1}}{{b}_{1}+{\frac {{a}_{2}}{{b}_{2}}}}}

{f}_{3}={b}_{0}+{\frac {{a}_{1}}{{b}_{1}+{\frac {{a}_{2}}{{b}_{2}+{\frac {{a}_{3}}{{b}_{3}}}}}}}

и т. д., или используя обозначение big-K , если

{f}_{n}={b}_{0}+{\underset {j=1}{\overset {n}{\operatorname {K} }}}{\frac {{a}_{j}}{{b}_{j}+}}

это $n$ сходящийся к $f$ затем

{f}_{n}={\frac {{A}_{n}}{{B}_{n}}}

где ${A}_{n}$ и ${B}_{n}$ задаются рекуррентными соотношениями Уоллиса-Эйлера

{A}_{-1}=1

{B}_{-1}=0

{A}_{0}={b}_{0}

{B}_{0}=1

{A}_{n}={b}_{n}{A}_{n-1}+{a}_{n}{A}_{n-2}

{B}_{n}={b}_{n}{B}_{n-1}+{a}_{n}{B}_{n-2}

Метод Ленца определяет

{C}_{n}={\frac {{A}_{n}}{{A}_{n-1}}}

{D}_{n}={\frac {{B}_{n-1}}{{B}_{n}}}

так что $n$ конвергента

{f}_{n}={C}_{n}{D}_{n}{f}_{n-1}

и использует рекуррентные соотношения

{C}_{0}={\frac {{A}_{0}}{{A}_{-1}}}={b}_{0}

{D}_{0}={\frac {{B}_{-1}}{{B}_{0}}}=0

{f}_{0}={b}_{0}

{C}_{n}={b}_{n}+{\frac {{a}_{n}}{{C}_{n-1}}}

{D}_{n}={\frac {1}{{b}_{n}+{a}_{n}{D}_{n-1}}}

Когда продукт ${C}_{n}{D}_{n}$ приближается к единству с увеличением $n$ , есть надежда, что ${f}_{n}$ сошелся к $f$ . ^{[ 8 ]}

Приложения

Алгоритм Ленца широко использовался в конце двадцатого века. Было высказано предположение, что в нем нет строгого анализа распространения ошибок. Однако несколько эмпирических тестов показывают, что он по крайней мере не хуже других методов. ^{[ 9 ]} В качестве примера он был применен для вычисления экспоненциальных интегральных функций. Это приложение тогда называлось модифицированным алгоритмом Ленца. ^{[ 10 ]} Также утверждается, что алгоритм Ленца применим не для всех вычислений, и сходимость может быть довольно быстрой для некоторых цепных дробей и наоборот для других. ^{[ 11 ]}

Ссылки

^ Jump up to: ^а ^б Ленц, WJ (сентябрь 1973 г.). Метод вычисления сферических функций Бесселя комплексного аргумента с помощью таблиц (PDF) (Технический отчет по исследованиям и разработкам ECOM-5509). Ракетный полигон Уайт-Сэндс, Нью-Мексико: Лаборатория атмосферных наук, Командование электроники армии США.
^ Числовые рецепты на C++ . стр. 177–179. ISBN 0 521 75033 4 .
^ Jump up to: ^а ^б Томпсон, Ай-Джей; Барнетт, Арканзас (1986). «Функции Кулона и Бесселя комплексного аргумента и порядка» . Журнал вычислительной физики . 64 (2): 490–509. Бибкод : 1986JCoPh..64..490T . дои : 10.1016/0021-9991(86)90046-x . ISSN 0021-9991 .
^ Дж., Ленц, В. (август 1982 г.). Упрощение алгоритма Ленца . Центр оборонной технической информации. OCLC 227549426 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ Jump up to: ^а ^б Ленц, Уильям Дж. (1 марта 1976 г.). «Построение функций Бесселя в расчетах рассеяния Ми с использованием цепных дробей» . Прикладная оптика . 15 (3): 668–671. Бибкод : 1976ApOpt..15..668L . дои : 10.1364/ao.15.000668 . ISSN 0003-6935 . ПМИД 20165036 .
^ Яаскелайнен, Т.; Руусканен, Дж. (1 октября 1981 г.). «Заметка об алгоритме Ленца» . Прикладная оптика . 20 (19): 3289–3290. Бибкод : 1981ApOpt..20.3289J . дои : 10.1364/ao.20.003289 . ISSN 0003-6935 . ПМИД 20333144 .
^ Масмуди, Атеф; Бухель, Мед Салим; Пуэх, Уильям (март 2012 г.). «Шифрование изображения с использованием хаотической стандартной карты и карты непрерывных дробей» . 2012 6-я Международная конференция по электронике, информационным технологиям и телекоммуникациям (SETIT) . IEEE. стр. 474–480. дои : 10.1109/setit.2012.6481959 . ISBN 978-1-4673-1658-3 . S2CID 15380706 .
^ Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). Численные рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета. стр. 207–208.
^ Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (1992). Числовые рецепты на Фортране, Искусство научных вычислений (2-е изд.). Издательство Кембриджского университета. п. 165.
^ Пресс, Уильям Х.; Теукольский, Саул А. (1988). «Оценка цепных дробей и вычисление экспоненциальных интегралов» . Компьютеры в физике . 2 (5): 88. Бибкод : 1988ComPh...2...88P . дои : 10.1063/1.4822777 . ISSN 0894-1866 .
^ Ванд, Мэтт П.; Ормерод, Джон Т. (18 сентября 2012 г.). «Продолжение дробного улучшения байесовских вычислений» . Стат . 1 (1): 31–41. дои : 10.1002/sta4.4 . ISSN 2049-1573 . ПМИД 22533111 . S2CID 119636237 .

[:0-1] Jump up to: ^а ^б Ленц, WJ (сентябрь 1973 г.). Метод вычисления сферических функций Бесселя комплексного аргумента с помощью таблиц (PDF) (Технический отчет по исследованиям и разработкам ECOM-5509). Ракетный полигон Уайт-Сэндс, Нью-Мексико: Лаборатория атмосферных наук, Командование электроники армии США.

[2] Числовые рецепты на C++ . стр. 177–179. ISBN 0 521 75033 4 .

[:1-3] Jump up to: ^а ^б Томпсон, Ай-Джей; Барнетт, Арканзас (1986). «Функции Кулона и Бесселя комплексного аргумента и порядка» . Журнал вычислительной физики . 64 (2): 490–509. Бибкод : 1986JCoPh..64..490T . дои : 10.1016/0021-9991(86)90046-x . ISSN 0021-9991 .

[4] Дж., Ленц, В. (август 1982 г.). Упрощение алгоритма Ленца . Центр оборонной технической информации. OCLC 227549426 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[Lentz_668–671-5] Jump up to: ^а ^б Ленц, Уильям Дж. (1 марта 1976 г.). «Построение функций Бесселя в расчетах рассеяния Ми с использованием цепных дробей» . Прикладная оптика . 15 (3): 668–671. Бибкод : 1976ApOpt..15..668L . дои : 10.1364/ao.15.000668 . ISSN 0003-6935 . ПМИД 20165036 .

[6] Яаскелайнен, Т.; Руусканен, Дж. (1 октября 1981 г.). «Заметка об алгоритме Ленца» . Прикладная оптика . 20 (19): 3289–3290. Бибкод : 1981ApOpt..20.3289J . дои : 10.1364/ao.20.003289 . ISSN 0003-6935 . ПМИД 20333144 .

[7] Масмуди, Атеф; Бухель, Мед Салим; Пуэх, Уильям (март 2012 г.). «Шифрование изображения с использованием хаотической стандартной карты и карты непрерывных дробей» . 2012 6-я Международная конференция по электронике, информационным технологиям и телекоммуникациям (SETIT) . IEEE. стр. 474–480. дои : 10.1109/setit.2012.6481959 . ISBN 978-1-4673-1658-3 . S2CID 15380706 .

[8] Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). Численные рецепты: искусство научных вычислений (3-е изд.). Издательство Кембриджского университета. стр. 207–208.

[9] Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (1992). Числовые рецепты на Фортране, Искусство научных вычислений (2-е изд.). Издательство Кембриджского университета. п. 165.

[10] Пресс, Уильям Х.; Теукольский, Саул А. (1988). «Оценка цепных дробей и вычисление экспоненциальных интегралов» . Компьютеры в физике . 2 (5): 88. Бибкод : 1988ComPh...2...88P . дои : 10.1063/1.4822777 . ISSN 0894-1866 .

[11] Ванд, Мэтт П.; Ормерод, Джон Т. (18 сентября 2012 г.). «Продолжение дробного улучшения байесовских вычислений» . Стат . 1 (1): 31–41. дои : 10.1002/sta4.4 . ISSN 2049-1573 . ПМИД 22533111 . S2CID 119636237 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]