Линейный многошаговый метод
Эта статья включает список литературы , связанную литературу или внешние ссылки , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . ( июнь 2017 г. ) |
Линейные многошаговые методы применяются для численного решения обыкновенных дифференциальных уравнений . Концептуально численный метод начинается с начальной точки, а затем делает небольшой шаг вперед во времени, чтобы найти следующую точку решения. Процесс продолжается последующими шагами для определения решения. Одношаговые методы (такие как метод Эйлера ) обращаются только к одной предыдущей точке и ее производной для определения текущего значения. Такие методы, как Рунге-Кутта, выполняют некоторые промежуточные шаги (например, полшага) для получения метода более высокого порядка, но затем отбрасывают всю предыдущую информацию, прежде чем сделать второй шаг. Многошаговые методы пытаются повысить эффективность за счет сохранения и использования информации, полученной на предыдущих этапах, а не ее отбрасывания. Следовательно, многошаговые методы ссылаются на несколько предыдущих точек и производных значений. В случае линейных многошаговых методов используется линейная комбинация предыдущих точек и значений производных.
Определения
[ редактировать ]Численные методы для обыкновенных дифференциальных уравнений аппроксимируют решения начальных задач вида
Результатом являются аппроксимации значения в дискретные моменты времени : где - это временной шаг (иногда называемый ) и является целым числом.
Многошаговые методы используют информацию из предыдущего шаги для расчета следующего значения. В частности, линейный многошаговый метод использует линейную комбинацию и рассчитать стоимость для желаемого текущего шага. Таким образом, линейный многошаговый метод – это метод вида с . Коэффициенты и определить метод. Разработчик метода выбирает коэффициенты, балансируя между необходимостью получить хорошее приближение к истинному решению и желанием получить метод, который легко применить. Часто многие коэффициенты равны нулю для упрощения метода.
Можно различать явные и неявные методы . Если , то метод называется «явным», поскольку по формуле можно напрямую вычислить . Если то метод называется «неявным», поскольку значение зависит от стоимости , и уравнение необходимо решить относительно . итерационные методы, такие как метод Ньютона Для решения неявной формулы часто используются .
Иногда для «предсказания» значения используется явный многошаговый метод. . Это значение затем используется в неявной формуле для «исправления» значения. Результатом является метод предиктора-корректора .
Примеры
[ редактировать ]Рассмотрим для примера задачу Точное решение .
Одношаговый Эйлер
[ редактировать ]Простым численным методом является метод Эйлера: Метод Эйлера можно рассматривать как явный многошаговый метод для вырожденного случая одного шага.
Этот метод применяется с размером шага по проблеме , дает следующие результаты:
Двухшаговый Адамс – Башфорт
[ редактировать ]Метод Эйлера является одношаговым. Простым многошаговым методом является двухэтапный метод Адамса – Башфорта. Этому методу нужны два значения: и , чтобы вычислить следующее значение, . Однако проблема начального значения дает только одно значение: . Одним из вариантов решения этой проблемы является использование вычисляется методом Эйлера как второе значение. При таком выборе метод Адамса – Башфорта дает (округляется до четырех цифр): Точное решение на является , поэтому двухшаговый метод Адамса – Башфорта более точен, чем метод Эйлера. Это всегда так, если размер шага достаточно мал.
Семейства многошаговых методов
[ редактировать ]Обычно используются три семейства линейных многошаговых методов: методы Адамса – Башфорта, методы Адамса – Моултона и формулы обратного дифференцирования (BDF).
Методы Адамса – Башфорта
[ редактировать ]Методы Адамса – Башфорта являются явными методами. Коэффициенты и , в то время как выбираются так, чтобы методы имели порядок s (это определяет методы однозначно).
Методы Адамса-Башфорта с s = 1, 2, 3, 4, 5 таковы ( Hairer, Nørsett & Wanner 1993 , §III.1; Butcher 2003 , стр. 103):
Коэффициенты можно определить следующим образом. Используйте полиномиальную интерполяцию , чтобы найти полином p степени такой, что Формула Лагранжа для полиномиальной интерполяции дает Полином p является локально хорошим приближением правой части дифференциального уравнения которую необходимо решить, поэтому рассмотрим уравнение вместо. Это уравнение можно решить точно; решение — это просто интеграл от p . Это предполагает принятие формулы для p Метод Адамса – Башфорта возникает при замене . Коэффициенты оказываются предоставленными Замена своим интерполянтом p приводит к ошибке порядка h с , и отсюда следует, что s -шаговый метод Адамса–Бэшфорта действительно имеет порядок s ( Iserles 1996 , §2.1)
Методы Адамса-Бэшфорта были разработаны Джоном Каучем Адамсом для решения дифференциального уравнения, моделирующего капиллярное действие, предложенного Фрэнсисом Башфортом . Башфорт (1883) опубликовал свою теорию и численный метод Адамса ( Goldstine 1977 ).
Методы Адамса – Моултона
[ редактировать ]Методы Адамса-Моултона аналогичны методам Адамса-Бэшфорта тем, что они также имеют и . Опять же, коэффициенты b выбираются так, чтобы получить максимально возможный порядок. Однако методы Адамса – Моултона являются неявными методами. Убрав ограничение, которое , s -шаговый метод Адамса – Моултона может достичь порядка , а s -шаг методов Адамса–Бэшфорта имеет только порядок s .
Перечислены методы Адамса-Моултона с s = 0, 1, 2, 3, 4 ( Hairer, Nørsett & Wanner 1993 , §III.1; Quarteroni, Sacco & Saleri 2000 ), где первые два метода представляют собой обратный метод Эйлера. и правило трапеций соответственно:
Вывод методов Адамса-Моултона аналогичен выводу метода Адамса-Бэшфорта; однако интерполирующий полином использует не только точки , как указано выше, но также . Коэффициенты имеют вид
Методы Адамса-Моултона созданы исключительно Джоном Каучем Адамсом , как и методы Адамса-Бэшфорта. Имя Фореста Рэя Моултона стало ассоциироваться с этими методами, потому что он понял, что их можно использовать в тандеме с методами Адамса-Бэшфорта в качестве пары предиктор-корректор ( Moulton 1926 ); Милн (1926) придерживался той же идеи. Адамс использовал метод Ньютона для решения неявного уравнения ( Hairer, Nørsett & Wanner 1993 , §III.1).
Формулы обратного дифференцирования (BDF)
[ редактировать ]Методы BDF являются неявными методами с а остальные коэффициенты выбраны так, чтобы метод достиг порядка s (максимально возможного). Эти методы особенно используются для решения жестких дифференциальных уравнений .
Анализ
[ редактировать ]Центральными понятиями анализа линейных многошаговых методов, да и любого численного метода дифференциальных уравнений, являются сходимость, порядок и устойчивость .
Последовательность и порядок
[ редактировать ]Первый вопрос заключается в том, является ли метод последовательным: является ли разностное уравнение хорошее приближение дифференциального уравнения ? Точнее, многошаговый метод является последовательным, если локальная ошибка усечения стремится к нулю быстрее, чем размер шага h, когда h стремится к нулю, где локальная ошибка усечения определяется как разница между результатом метода, предполагая, что все предыдущие значения точны, а точное решение уравнения в момент времени . Вычисление с использованием рядов Тейлора показывает, что линейный многошаговый метод непротиворечив тогда и только тогда, когда Все упомянутые выше методы последовательны ( Hairer, Nørsett & Wanner 1993 , §III.2).
Если метод непротиворечив, то следующий вопрос заключается в том, насколько хорошо разностное уравнение, определяющее численный метод, аппроксимирует дифференциальное уравнение. Говорят, что многошаговый метод имеет порядок p, если локальная ошибка имеет порядок когда h стремится к нулю. Это эквивалентно следующему условию на коэффициенты методов: s - шаговый метод Адамса-Бэшфорта имеет порядок s , а s -шаговый метод Адамса-Моултона имеет порядок ( Хайрер, Норсетт и Ваннер 1993 , §III.2).
Эти условия часто формулируются с использованием характеристических полиномов В терминах этих полиномов приведенное выше условие того, чтобы метод имел порядок p, становится В частности, метод непротиворечив, если он имеет порядок хотя бы один, что имеет место, если и .
Стабильность и конвергенция
[ редактировать ]Численное решение одношагового метода зависит от начального условия , но численное решение метода s -шага зависит от всех начальных значений s , . Таким образом, представляет интерес, устойчиво ли численное решение по отношению к возмущениям начальных значений. Линейный многошаговый метод является нуль-устойчивым для некоторого дифференциального уравнения на заданном интервале времени, если возмущение начальных значений размера ε приводит к изменению численного решения на этом интервале времени не более чем на K ε для некоторого значения K который не зависит от размера шага h . Это называется «нулевой устойчивостью», поскольку достаточно проверить условие дифференциального уравнения ( Сюли и Майерс 2003 , стр. 332).
Если все корни характеристического многочлена ρ имеют модуль меньше или равный 1, а корни модуля 1 имеют кратность 1, мы говорим, что условие корня удовлетворено. Линейный многошаговый метод устойчив к нулю тогда и только тогда, когда выполняется условие корня ( Süli & Mayers 2003 , стр. 335).
Теперь предположим, что к достаточно гладкому дифференциальному уравнению применяется последовательный линейный многошаговый метод и что начальные значения все сходится к начальному значению как . Тогда численное решение сходится к точному решению как тогда и только тогда, когда метод устойчив к нулю. Этот результат известен как теорема эквивалентности Далквиста , названная в честь Гермунда Далквиста ; по духу эта теорема аналогична теореме Лакса об эквивалентности для методов конечных разностей . Более того, если метод имеет порядок p , то глобальная ошибка (разница между численным решением и точным решением в фиксированный момент времени) равна ( Сюли и Майерс 2003 , стр. 340).
Кроме того, если метод сходится, его называют сильно устойчивым, если — единственный корень по модулю 1. Если он сходится и все корни по модулю 1 не повторяются, но таких корней более одного, то его называют относительно устойчивым . Обратите внимание, что для сходимости метода 1 должна быть корнем; таким образом, конвергентные методы всегда являются одним из этих двух.
Чтобы оценить производительность линейных многошаговых методов для жестких уравнений , рассмотрим линейное тестовое уравнение y' = λ y . Многошаговый метод, примененный к этому дифференциальному уравнению с размером шага h, дает линейное рекуррентное соотношение с характеристическим полиномом Этот полином называется полиномом устойчивости многошагового метода. Если все его корни имеют модуль меньше единицы, то численное решение многошагового метода будет сходиться к нулю и многошаговый метод называется абсолютно устойчивым для этого значения h λ. Метод называется A-стабильным , если он абсолютно устойчив для всех h λ с отрицательной вещественной частью. Область абсолютной устойчивости — это набор всех h λ, для которых многошаговый метод абсолютно устойчив ( Süli & Mayers 2003 , стр. 347 и 348). Подробнее см. в разделе о жестких уравнениях и многошаговых методах .
Пример
[ редактировать ]Рассмотрим трехшаговый метод Адамса – Башфорта. Таким образом, один характеристический многочлен у которого есть корни , и указанные выше условия выполняются. Как является единственным корнем по модулю 1, метод сильно устойчив.
Другой характеристический полином
Первый и второй барьеры Далквиста
[ редактировать ]Эти два результата были доказаны Гермундом Далквистом и представляют собой важную оценку порядка сходимости и A-устойчивости линейного многошагового метода. Первый барьер Далквиста был доказан Далквистом (1956) , а второй — Далквистом (1963) .
Первый барьер Далквиста
[ редактировать ]Первый барьер Далквиста гласит, что нулевой устойчивый и линейный q -шаговый многошаговый метод не может достичь порядка сходимости выше q + 1, если q нечетно, и больше q + 2, если q четно. Если метод также является явным, то он не может достичь порядка выше q ( Hairer, Nørsett & Wanner 1993 , Thm III.3.5).
Второй барьер Далквиста
[ редактировать ]Второй барьер Далквиста утверждает, что ни один явный линейный многошаговый метод не является A-стабильным . Кроме того, максимальный порядок (неявного) A-стабильного линейного многошагового метода равен 2. Среди A-стабильных линейных многошаговых методов порядка 2 правило трапеций имеет наименьшую константу ошибки ( Dahlkist 1963 , Thm 2.1 и 2.2).
См. также
[ редактировать ]Ссылки
[ редактировать ]- Башфорт, Фрэнсис (1883), Попытка проверить теории капиллярного действия путем сравнения теоретических и измеренных форм капель жидкости. С объяснением метода интегрирования, используемого при построении таблиц, дающих теоретические формы таких капель, Дж. К. Адамс , Кембридж.
{{citation}}
: CS1 maint: отсутствует местоположение издателя ( ссылка ) . - Батчер, Джон К. (2003), Численные методы для обыкновенных дифференциальных уравнений , Джон Уайли, ISBN 978-0-471-96758-3 .
- Далквист, Гермунд (1956), «Сходимость и устойчивость при численном интегрировании обыкновенных дифференциальных уравнений», Mathematica Scandinavica , 4 : 33–53, doi : 10.7146/math.scand.a-10454 .
- Далквист, Гермунд (1963), «Специальная проблема устойчивости линейных многошаговых методов», BIT , 3 : 27–43, doi : 10.1007/BF01963532 , ISSN 0006-3835 , S2CID 120241743 .
- Голдстайн, Герман Х. (1977), История численного анализа с 16 по 19 века , Нью-Йорк: Springer-Verlag, ISBN 978-0-387-90277-7 .
- Хайрер, Эрнст; Норсетт, Сиверт Пол; Ваннер, Герхард (1993), Решение обыкновенных дифференциальных уравнений I: Нежесткие задачи (2-е изд.), Берлин: Springer Verlag, ISBN 978-3-540-56670-0 .
- Хайрер, Эрнст; Ваннер, Герхард (1996), Решение обыкновенных дифференциальных уравнений II: жесткие и дифференциально-алгебраические задачи (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-3-540-60452-5 .
- Изерлес, Арье (1996), Первый курс численного анализа дифференциальных уравнений , Cambridge University Press, ISBN 978-0-521-55655-2 .
- Милн, МЫ (1926), «Численное интегрирование обыкновенных дифференциальных уравнений», American Mathematical Monthly , 33 (9), Mathematical Association of America: 455–460, doi : 10.2307/2299609 , JSTOR 2299609 .
- Моултон, Форест Р. (1926), Новые методы внешней баллистики , University of Chicago Press .
- Квартерони, Альфио ; Сакко, Риккардо; Салери, Фаусто (2000), Численная математика , Springer Verlag, ISBN 978-88-470-0077-3 .
- Сюли, Эндре; Майерс, Дэвид (2003), Введение в численный анализ , издательство Кембриджского университета , ISBN 0-521-00794-1 .