Методы Адамса. Вывод расчетных формул

Методы Адамса. Вывод расчетных формул Методы Адамса относятся к многошаговым методам решения задачи Коши 𝑦 ′ (𝑥) = 𝑓(𝑥, 𝑦(𝑥)), 𝑦(𝑎) = 𝑦0 , 𝑥 ∈ [𝑎, 𝑏] (1 − 2) Методы Рунге-Кутта относятся к одношаговым методам, так как строится решение для 𝑦(𝑥 + ℎ) в предположении, что известно решение 𝑦(𝑥). Принцип построения формул методов Адамса заключается в замене функции 𝑓(𝑥, 𝑦(𝑥)) интерполяционным многочленом, построенным по известным значениям решения в нескольких точках 𝑥, 𝑥 − ℎ, 𝑥 − 2ℎ, … Разобьем отрезок [𝑎, 𝑏] на отрезки длины ℎ = 𝑏−𝑎 𝑛 , обозначим 𝑥𝑖 = 𝑎 + 𝑖 ℎ, 𝑖 = 0, … 𝑛 Проинтегрируем дифференциальное уравнение (1) 𝑥𝑖+1 𝑦(𝑥𝑖+1 ) = 𝑦(𝑥𝑖 ) + ∫ 𝑓(𝑥, 𝑦(𝑥))𝑑𝑥 (3) 𝑥𝑖 Заменим 𝑓(𝑥, 𝑦(𝑥))~ 𝑁𝑘 (𝑥), 𝑘 − степень многочлена и получим выражение для приближенного значения 𝑦𝑖+1 ≈ 𝑦(𝑥𝑖+1 ) 𝑥𝑖+1 𝑦𝑖+1 = 𝑦𝑖 + ∫ 𝑁𝑘 (𝑥)𝑑𝑥 (4) 𝑥𝑖 Для функции 𝑓(𝑥, 𝑦(𝑥)) известны дискретные значения для 𝑥 = 𝑥𝑖 , 𝑥 = 𝑥𝑖−1 , …, поэтому построение ИМ возможно. Обозначим для краткости 𝑓(𝑥𝑗 , 𝑦𝑗 ) = 𝑓𝑗 , 𝑗 = 0,1,2, … 𝑖 Если для построения интерполяционного многочлена использовать таблицу значений, построенную по (𝑘 + 1)-му значению функции 𝑓(𝑥, 𝑦(𝑥)), начиная с 𝑥𝑖 : 𝑥𝑖 𝑥𝑖−1 𝑥𝑖−2 …… 𝑥𝑖−𝑘 𝑓𝑖 𝑓𝑖−1 𝑓𝑖−2 𝑓𝑖−𝑘 ….. то в результате интегрирования получаются расчетные формулы интерполяционного метода Адамса. Если же для построения интерполяционного многочлена использовать таблицу значений, построенную по (𝑘 + 1)-му значению функции 𝑓(𝑥, 𝑦(𝑥)), начиная с 𝑥𝑖+1 : 𝑥𝑖+1 𝑥𝑖 𝑥𝑖−1 …… 𝑥𝑖−𝑘+1 𝑓𝑖+1 𝑓𝑖 𝑓𝑖−1 ….. 𝑓𝑖−𝑘+1 то в результате интегрирования получаются расчетные формулы экстраполяционного метода Адамса. Семейство интерполяционных методов Адамса Будем использовать интерполяционный многочлен в форме Ньютона для интерполирования назад. Ранее мы использовали ИМ Ньютона для интерполирования вперед из точки 𝑥0 , который записывался в следующем виде 𝑁𝑘 (𝑥) = 𝑓𝑜 + 𝑓(𝑥0 ; 𝑥1 )(𝑥 − 𝑥0 ) + 𝑓(𝑥0 ; 𝑥1 ; 𝑥2 )(𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) + ⋯ 𝑓(𝑥0 ; 𝑥1 ; … 𝑥𝑘 )(𝑥 − 𝑥0 )(𝑥 − 𝑥1 ) … (𝑥 − 𝑥𝑘−1 ) Теперь запишем ИМ в форме Ньютона для интерполирования назад из точки 𝑥𝑖 𝑁𝑘 (𝑥) = 𝑓𝑖 + 𝑓(𝑥𝑖 ; 𝑥𝑖−1 )(𝑥 − 𝑥𝑖 ) + 𝑓(𝑥𝑖 ; 𝑥𝑖−1 ; 𝑥𝑖−2 )(𝑥 − 𝑥𝑖 )(𝑥 − 𝑥𝑖−1 ) + ⋯ 𝑓(𝑥𝑖 ; 𝑥𝑖−1 ; … 𝑥𝑖−𝑘 )(𝑥 − 𝑥𝑖 )(𝑥 − 𝑥𝑖−1 ) … (𝑥 − 𝑥𝑖−𝑘+1 ) (5) В случае равноотстоящих узлов разделенные разности заменяются на конечные 𝑓(𝑥𝑖 ; 𝑥𝑖−1 ) = 𝒇𝒊 − 𝒇𝒊−𝟏 ∆𝑓𝑖−1 = ; ∆𝑓𝑖−1 − конечная разность 1 порядка 𝑥𝑖 − 𝑥𝑖−1 ℎ 𝑓(𝑥𝑖 ; 𝑥𝑖−1 ; 𝑥𝑖−2 ) = 𝑓(𝑥𝑖 ; 𝑥𝑖−1 ) − 𝑓(𝑥𝑖−1 ; 𝑥𝑖−2 ) ∆𝑓𝑖−1 − ∆𝑓𝑖−2 1 = = ∆(∆𝑓𝑖−2 ) 𝑥𝑖 − 𝑥𝑖−2 2! ℎ2 2! ℎ2 1 2 ∆ 𝑓𝑖−2 2! ℎ2 1 1 𝑁𝑘 (𝑥) = 𝑓𝑖 + ∆ 𝑓𝑖−1 (𝑥 − 𝑥𝑖 ) + ∆2 𝑓𝑖−2 (𝑥 − 𝑥𝑖 )(𝑥 − 𝑥𝑖−1 ) ℎ 2! ℎ2 1 +⋯ ∆𝑘 𝑓𝑖−𝑘 (𝑥 − 𝑥𝑖 )(𝑥 − 𝑥𝑖−1 ) … (𝑥 − 𝑥𝑖−(𝑘−1) ) (6) 𝑘! ℎ𝑘 = Выполним замену переменных 𝑥 = 𝑥𝑖 + 𝑞ℎ; 𝑥 − 𝑥𝑖 = 𝑞ℎ; 𝑥 − 𝑥𝑖−1 = 𝑥 − (𝑥𝑖 − ℎ) = 𝑞ℎ + ℎ = ℎ(𝑞 + 1) 𝑥 − 𝑥𝑖−2 = 𝑥 − (𝑥𝑖 − 2ℎ) = 𝑞ℎ + 2ℎ = ℎ(𝑞 + 2) получим ИМ Ньютона в виде 𝑁𝑘 (𝑥) = 𝑁𝑘 (𝑥𝑖 + 𝑞ℎ) 1 1 = 𝑓𝑖 + ∆ 𝑓𝑖−1 (𝑞ℎ) + ∆2 𝑓𝑖−2 (𝑞ℎ)(𝑞 + 1)ℎ 2 ℎ 2! ℎ 1 +⋯ ∆𝑘 𝑓𝑖−𝑘 (𝑞ℎ)(𝑞 + 1)ℎ … (𝑞 + 𝑘 − 1)ℎ (7) 𝑘! ℎ𝑘 𝑁𝑘 (𝑥) = 𝑁𝑘 (𝑥𝑖 + 𝑞ℎ) = 𝑓𝑖 + ∆ 𝑓𝑖−1 (𝑞) + +⋯ 1 2 ∆ 𝑓𝑖−2 (𝑞)(𝑞 + 1) 2! 1 𝑘 ∆ 𝑓𝑖−𝑘 (𝑞)(𝑞 + 1) … (𝑞 + 𝑘 − 1) (8) 𝑘! Многочлен в форме (8) – это ИМ Ньютона для интерполирования назад в случае равноотстоящих узлов. Таким образом, выбрав число узлов для построения многочлена, подставим многочлен (7) вместо подинтегральной функции и получим многошаговый интерполяционный метод Адамса. Заметим, что основой для построения ИМ в форме Ньютона служит таблица разностей, в данном случае, конечных разностей: 𝒙𝒋 𝑥𝑖−𝑘 𝑥𝑖−𝑘+1 𝑥𝑖−𝑘+2 …. 𝑥𝑖−1 𝑥𝑖 𝒇𝒋 𝑓𝑖−𝑘 𝑓𝑖−𝑘+1 𝑓𝑖−𝑘+2 … 𝑓𝑖−1 𝑓𝑖 ∆𝒇𝒋 ∆𝑓𝑖−𝑘 ∆𝑓𝑖−𝑘+1 ∆ 𝟐 𝒇𝒋 ∆2 𝑓𝑖−𝑘 … ∆ 𝒌 𝒇𝒋 ∆𝑘 𝑓𝑖−𝑘 ∆2 𝑓𝑖−2 ∆ 𝑓𝑖−1 Подставим ИМ в форме Ньютона, проинтегрируем и получим расчетные формулы метода Адамса 𝑥𝑖+1 𝑦𝑖+1 = 𝑦𝑖 + ∫ 𝑁𝑘 (𝑥)𝑑𝑥 𝑥𝑖 Приведем примеры интерполяционных методов Адамса 1) Пусть 𝑘 = 0, тогда для построения ИМ 0-й степени следует взять одно значение функции 𝑓(𝑥, 𝑦) для 𝑥 = 𝑥𝑖 𝑓(𝑥𝑖 , 𝑦𝑖 ) = 𝑓𝑖 𝑥𝑖+1 𝑦𝑖+1 = 𝑦𝑖 + ∫ 𝑓𝑖 𝑑𝑥 = 𝑦𝑖 + 𝑓𝑖 (𝑥𝑖+1 − 𝑥𝑖 ) 𝑥𝑖 𝒚𝒊+𝟏 = 𝒚𝒊 + 𝒉 𝒇(𝒙𝒊 , 𝒚𝒊 ), 𝒊 = 𝟎, 𝟏, 𝟐, … (8) Это одношаговый интерполяционный метод Адамса, который совпал с явным методом Эйлера. 2) Пусть 𝑘 = 1, тогда для построения ИМ 1-й степени следует взять два узла и построить таблицу для подинтегральной функции 𝑥𝑖 𝑥𝑖−1 𝑓𝑖 = 𝑓(𝑥𝑖 , 𝑦𝑖 ) 𝑓𝑖−1 = 𝑓(𝑥𝑖−1 , 𝑦𝑖−1 ) Теперь построим ИМ в форме Ньютона и проинтегрируем по формуле Ньютона-Лейбница 𝑥𝑖+1 𝑥𝑖+1 1 𝑦𝑖+1 = 𝑦𝑖 + ∫ 𝑁1 (𝑥)𝑑𝑥 = 𝑦𝑖 + ∫ (𝑓𝑖 + ∆ 𝑓𝑖−1 (𝑥 − 𝑥𝑖 )) 𝑑𝑥 ℎ 𝑥𝑖 𝑥𝑖 𝑥𝑖+1 1 (𝑥 ) = 𝑦𝑖 + 𝑓𝑖 𝑖+1 − 𝑥𝑖 + ∆ 𝑓𝑖−1 ∫ (𝑥 − 𝑥𝑖 )𝑑𝑥 ℎ 𝑥𝑖 Выполним замену переменных 𝑥 − 𝑥𝑖 = 𝑞ℎ, 𝑥 = 𝑥𝑖 + 𝑞ℎ, 𝑑𝑥 = ℎ 𝑑𝑞 1 𝑦𝑖+1 = 𝑦𝑖 + ℎ 𝑓𝑖 + ℎ ∆ 𝑓𝑖−1 ∫ 𝑞 𝑑𝑞 = 𝑦𝑖 + ℎ 𝑓𝑖 + ℎ ∆𝑓𝑖−1 𝒚𝒊+𝟏 = 𝒚𝒊 + 𝒉 𝟐 (𝟑 𝒇(𝒙𝒊 , 𝒚𝒊 ) − 𝒇(𝒙𝒊−𝟏 , 𝒚𝒊−𝟏 )) 1 2 (9) Это двушаговый интерполяционный метод Адамса. Семейство экстраполяционных методов Адамса. Запишем интерполяционный многочлен в форме Ньютона для интерполирования назад из узла 𝑥𝑖+1 . 1 1 𝑁𝑘 (𝑥) = 𝑓𝑖+1 + ∆ 𝑓𝑖 (𝑥 − 𝑥𝑖+1 ) + ∆2 𝑓𝑖−1 (𝑥 − 𝑥𝑖+1 )(𝑥 − 𝑥𝑖 ) 2 ℎ 2! ℎ 1 +⋯ ∆𝑘 𝑓𝑖−𝑘+1 (𝑥 − 𝑥𝑖+1 )(𝑥 − 𝑥𝑖 ) … (𝑥 − 𝑥𝑖−𝑘+2 ) (10) 𝑘! ℎ𝑘 Выполним замену переменных 𝑥 = 𝑥𝑖+1 + 𝑞ℎ; 𝑥 − 𝑥𝑖+1 = 𝑞ℎ; 𝑥 − 𝑥𝑖 = 𝑥 − (𝑥𝑖+1 − ℎ) = 𝑞ℎ + ℎ = ℎ(𝑞 + 1) 𝑥 − 𝑥𝑖−1 = 𝑥 − (𝑥𝑖+1 − 2ℎ) = 𝑞ℎ + 2ℎ = ℎ(𝑞 + 2) получим ИМ Ньютона в виде 𝑁𝑘 (𝑥) = 𝑁𝑘 (𝑥𝑖+1 + 𝑞ℎ) 1 1 = 𝑓𝑖+1 + ∆ 𝑓𝑖 (𝑞ℎ) + ∆2 𝑓𝑖−1 (𝑞ℎ)(𝑞 + 1)ℎ 2 ℎ 2! ℎ 1 +⋯ ∆𝑘 𝑓𝑖−𝑘+1 (𝑞ℎ) (𝑞 + 1) ℎ … (𝑞 + 𝑘 − 2) ℎ ) (11) 𝑘! ℎ𝑘 𝑁𝑘 (𝑥) = 𝑁𝑘 (𝑥𝑖+1 + 𝑞ℎ) = 𝑓𝑖+1 + ∆ 𝑓𝑖 (𝑞) + +⋯ 1 2 ∆ 𝑓𝑖−1 (𝑞)(𝑞 + 1) 2! 1 𝑘 ∆ 𝑓𝑖−𝑘+1 (𝑞) (𝑞 + 1) … (𝑞 + 𝑘 − 2) ) (12) 𝑘! Подставим ИМ в форме Ньютона, проинтегрируем и получим расчетные формулы метода Адамса 𝑥𝑖+1 𝑦𝑖+1 = 𝑦𝑖 + ∫ 𝑁𝑘 (𝑥)𝑑𝑥 𝑥𝑖 Приведем примеры экстраполяционных методов Адамса 3) Пусть 𝑘 = 0, тогда для построения ИМ 0-й степени следует взять одно значение функции 𝑓(𝑥, 𝑦) для 𝑥 = 𝑥𝑖+1 𝑓(𝑥𝑖+1 , 𝑦𝑖+1 ) = 𝑓𝑖+1 𝑥𝑖+1 𝑦𝑖+1 = 𝑦𝑖 + ∫ 𝑓𝑖+1 𝑑𝑥 = 𝑦𝑖 + 𝑓𝑖+1 (𝑥𝑖+1 − 𝑥𝑖 ) 𝑥𝑖 𝒚𝒊+𝟏 = 𝒚𝒊 + 𝒉 𝒇(𝒙𝒊+𝟏 , 𝒚𝒊+𝟏 ), 𝒊 = 𝟎, 𝟏, 𝟐, … Это одношаговый экстраполяционный метод Адамса, который совпал с неявным методом Эйлера. 4) Пусть 𝑘 = 1, тогда для построения ИМ 1-й степени следует взять два узла и построить таблицу для подинтегральной функции 𝑥𝑖+1 𝑥𝑖 𝑓𝑖+1 = 𝑓(𝑥𝑖+1 , 𝑦𝑖+1 ) 𝑓𝑖 = 𝑓(𝑥𝑖 , 𝑦𝑖 ) Теперь построим ИМ в форме Ньютона и проинтегрируем по формуле Ньютона-Лейбница 𝑥𝑖+1 𝑥𝑖+1 1 𝑦𝑖+1 = 𝑦𝑖 + ∫ 𝑁1 (𝑥)𝑑𝑥 = 𝑦𝑖 + ∫ (𝑓𝑖+1 + ∆ 𝑓𝑖 (𝑥 − 𝑥𝑖+1 )) 𝑑𝑥 ℎ 𝑥𝑖 𝑥𝑖 𝑥𝑖+1 1 = 𝑦𝑖 + 𝑓𝑖+1 (𝑥𝑖+1 − 𝑥𝑖 ) + ∆ 𝑓𝑖 ∫ (𝑥 − 𝑥𝑖+1 )𝑑𝑥 ℎ 𝑥𝑖 Выполним замену переменных 𝑥 − 𝑥𝑖+1 = 𝑞ℎ, 𝑥 = 𝑥𝑖+1 + 𝑞ℎ, 𝑑𝑥 = ℎ 𝑑𝑞 𝑦𝑖+1 = 𝑦𝑖 + ℎ 𝑓𝑖+1 + ℎ ∆ 𝑓𝑖 ∫ 𝑞 𝑑𝑞 = 𝑦𝑖 + ℎ 𝑓𝑖+1 + ℎ ∆𝑓𝑖 −1 𝒚𝒊+𝟏 −1 2 𝒉 = 𝒚𝒊 + (𝒇(𝒙𝒊+𝟏 , 𝒚𝒊+𝟏 ) + 𝒇(𝒙𝒊 , 𝒚𝒊 )) 𝟐 Это двушаговый экстраполяционный метод Адамса. Погрешность на шаге (локальная) и глобальная погрешность метода Адамса Для непрерывно дифференцируемой функции 𝑓(𝑥, 𝑦) вопрос о погрешности метода Адамса может быть решен с помощью погрешности интерполяционного многочлена max|𝑓 𝑘+1 (𝑥, 𝑦(𝑥))| |𝑓(𝑥, 𝑦) − 𝑁𝑘 (𝑥)| ≤ |𝑞(𝑞 + 1)(𝑞 + 2) … (𝑞 + 𝑘)| ℎ𝑘+1 (𝑘 + 1)! Домашнее задание 1) Трехшаговый интерполяционный метод Адамса 2) Трехшаговый экстраполяционный метод Адамса