Алгоритм Булирша – Стоера

В численном анализе алгоритм Булирша-Стоера представляет собой метод численного решения обыкновенных дифференциальных уравнений , который сочетает в себе три мощные идеи: экстраполяцию Ричардсона , использование экстраполяции рациональных функций в приложениях типа Ричардсона и модифицированный метод средней точки. получать численные решения обыкновенных дифференциальных уравнений (ОДУ) с высокой точностью и сравнительно небольшими вычислительными затратами. Он назван в честь Роланда Булирша и Йозефа Стоера . Его иногда называют алгоритмом Грэгга-Булирша-Стоера (GBS) из-за важности результата о функции ошибок модифицированного метода средней точки, полученного Уильямом Б. Грэггом .

Основные идеи

Идея экстраполяции Ричардсона состоит в том, чтобы рассматривать численный расчет, точность которого зависит от используемого размера шага h, как (неизвестную) аналитическую функцию размера шага h , выполнять численный расчет с различными значениями h , подгонять (выбранную) аналитическую функцию к полученные точки, а затем оцениваем аппроксимирующую функцию для h = 0, пытаясь таким образом аппроксимировать результат расчета бесконечно мелкими шагами.

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

Модифицированный метод средней точки сам по себе является методом второго порядка и, следовательно, обычно уступает методам четвертого порядка, таким как метод Рунге-Кутты четвертого порядка . Однако у него есть то преимущество, что требуется только одна оценка производной на каждый подшаг (асимптотически для большого числа подшагов), и, кроме того, как обнаружил Грэгг, ошибка модифицированного шага средней точки размера H , состоящего из n подшагов размер h = H / n каждый и выраженный в виде степенного ряда по h , содержит только четные степени h . результаты отдельных попыток пересечь интервал H Это делает модифицированный метод средней точки чрезвычайно полезным для метода Булирша – Стоера, поскольку точность увеличивается на два порядка за раз, когда объединяются с увеличением числа подшагов.

Хайрер, Норсетт и Ваннер (1993 , стр. 228) при обсуждении метода говорят, что рациональная экстраполяция в этом случае почти никогда не является улучшением по сравнению с полиномиальной интерполяцией ( Deuflhard 1983 ). Более того, модифицированный метод средней точки является модификацией обычного метода средней точки, чтобы сделать его более стабильным, но из-за экстраполяции это не имеет большого значения ( Shampine & Baca 1983 ).

Ссылки

• Дефлхард, Питер (1983), «Управление порядком и размером шага в методах экстраполяции», Numerische Mathematics , 41 (3): 399–422, doi : 10.1007/BF01418332 , ISSN   0029-599X , S2CID   121911947 .
• Хайрер, Эрнст; Норсетт, Сиверт Пол; Ваннер, Герхард (1993), Решение обыкновенных дифференциальных уравнений I: Нежесткие задачи , Берлин, Нью-Йорк: Springer-Verlag , ISBN  978-3-540-56670-0 .
• Пресс, WH; Теукольский, С.А.; Феттерлинг, WT; Фланнери, BP (2007). «Раздел 17.3. Экстраполяция Ричардсона и метод Булирша-Стоера» . Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк: Издательство Кембриджского университета. ISBN  978-0-521-88068-8 . Архивировано из оригинала 11 августа 2011 г. Проверено 17 августа 2011 г.
• Шампин, Лоуренс Ф.; Бака, Лоррейн С. (1983), «Сглаживание экстраполированного правила средней точки», Numerische Mathematik , 41 (2): 165–175, doi : 10.1007/BF01390211 , ISSN   0029-599X , S2CID   121097742 .

Внешние ссылки

• ODEX.F , реализация алгоритма Булирша-Стоера Эрнста Хайрера и Герхарда Ваннера (другие процедуры и условия лицензии см. на их странице кодов Fortran и Matlab ).
• Библиотека BOOST , реализация на C++.
• Apache Commons Math , реализация на Java.