Явная схема Адамса.

Рассмотренные выше методы являются явными одношаговыми (для нахождения последующего приближения используется лишь одно предыдущее). Приведённый ниже метод является многошаговым.

Пусть задана задача Коши:

Для точного решения (которое нам не известно) выполнено:

Предположим, нам известны приближенные значения функции u(x) в k точках (стартовые k точек, в частности, можно найти методом Эйлера или методом Рунге-Кутта того или иного порядка), тогда функцию f (x, u(x)) в (2.4.2) для приближенного вычисления интеграла можно заменить на интерполяционный полином порядка k-1, построенный по k точкам, интеграл от которого считается явно и представляет собой линейную комбинацию значений c некоторыми множителями. Таким образом, мы получаем следующую рекуррентную процедуру вычисления приближенных значений функции u(x) (являющимся точным решением задачи Коши) в точках:

Описанная схема является k-шаговой явной формулой Адамса.

Неявная схема Адамса.

Пусть - интерполяционный полином порядка k, построенный по k+1 значению б одно из которых, именно, мы будем считать неизвестным. Модифицируем (2.4.3), заменив в нём на полином более высокой степени, интеграл от которого выражается в виде линейной комбинации значений с некоторыми новыми коэффициентами:

Формула (2.4.4) представляет собой неявную схему Адамса и является уравнением на, которое можно решать методом последовательных приближений. Естественно, что начальное приближение, должно быть разумно выбрано. Для этого удобно объединить явную и неявную схемы Адамса в одну, называемую «методом коррекции». Именно с помощью явной схемы определяется начальное приближение (прогноз), а затем по неявной схеме оно необходимое число раз (обычно один или два) корректируется методом последовательных приближений до достижения заданной точности (коррекция).

Другой путь построения разностных схем основан на том, что для вычисления значения используются результаты не одного, a k предыдущих шагов, т.е. значения yi .В этом случае получается k -шаговый метод.

Многошаговые методы могут быть построены следующим образом. Запишем исходное уравнение (1.9) в виде

(1.28)

Проинтегрируем обе части этого уравнения по х на отрезке . Интеграл от левой части

(1.29)

Для вычисления интеграла от правой части уравнения (1.28) строят сначала интерполяционный многочлен Pk -1степени k - 1 для аппроксимации функции на отрезке по значениям . После этого можно записать

(1.30)

Приравнивая выражения, полученные в (1.29) и (1.30), получим формулу для определения неизвестного значения сеточной функции в узле :

На основе этой формулы можно строить различные многошаговые методы любого порядка точности. Порядок точности зависит от степени интерполяционного многочлена , для построения которого используют значения сеточной функции , вычисленные на k предыдущих шагах.

Широко распространенным семейством многошаговых методов являются методы Адамса. Простейший из них, получающийся при k = 1, совпадает с рассмотренным ранее методом Эйлера первого порядка точности. В практических расчетах чаще всего применяют вариант метода Адамса, имеющий четвертый порядок точности и использующий на каждом шаге результаты предыдущих четырех. Именно его и называют обычно методом Адамса. Рассмотрим этот метод.

Пусть найдены значения в четырех последовательных узлах (k = 4). При этом имеются также вычисленные ранее значения правой части где . В качестве интерполяционного многочлена Р 3(х) можно взять многочлен Ньютона (см. разд. 2.3). В случае постоянного шага h конечные разности для правой части в узле х i имеют вид

Тогда разностную схему четвертого порядка метода Адамса можно записать после необходимых преобразований в виде

Сравнивая метод Адамса с методом Рунге – Кутта той же точности, отмечаем его экономичность, поскольку он требует вычисления лишь одного значения правой части на каждом шаге (в методе Рунге – Кутта - четырех). Но метод Адамса неудобен тем, что невозможно начать счет по одному лишь известному значению y 0 . Расчет может быть начат только с узла х 3, а не x 0.. Значения y 1, y 2, y 3,необходимые для вычисления y 4, нужно получить каким-либо другим способом (например, методом Рунге – Кутта), что существенно усложняет алгоритм. Кроме того, метод Адамса не позволяет (без усложнения формул) изменить шаг h в процессе счета; этого недостатка лишены одношаговые методы.

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

Один из вариантов метода прогноза и коррекции может быть получен на основе метода Адамса четвертого порядка. Приведем окончательный вид разностных соотношений, на этапе предиктора:

на этапе корректора:

(1.33)

Явную схему (1.32) используют на каждом шаге один раз, а с помощью неявной схемы (1.33) строят итерационный процесс вычисления yi +1, поскольку это значение входит в правую часть выражения

Заметим, что в этих формулах, как и в случае метода Адамса, при вычислении yi +1 необходимы значения сеточной функции в четырех предыдущих узлах: yi , yi -1, yi -2, yi -3. Следовательно, расчет по этому методу может быть начат только со значения y 4. Необходимые при этом y 1, y 2, y 3находят по методу Рунге – Кутта, у0 задается начальным условием. Это характерная особенность многошаговых методов. Алгоритм решения задачи Коши с помощью рассмотренного метода прогноза и коррекции представлен в укрупненном виде на рис. 1.4.

Рис. 1.4. Метод «предиктор-корректор»

В настоящее время методы Адамса являются одними из перспективных численных методов интегрирования для решения задачи Коши. Доказано, что при применении многошаговых численных методов Адамса для решения задачи Коши до 12 порядка область устойчивости уменьшается. При дальнейшем увеличении порядка область устойчивости, а также точность метода возрастает. Кроме того, при одинаковой точности для многошаговых методов на одном шаге интегрирования требуется меньше вычислений правых частей дифференциальных уравнений, чем в методах Рунге-Кутты. К достоинствам методов Адамса относится и то обстоятельство, что в них легко меняется шаг интегрирования и порядок метода.

На практике широко используются два типа методов Адамса - явные и неявные. Явные методы известны как методы Адамса-Бэшфорта, неявные - как методы Адамса-Мултона.

Рассмотрим применение численных методов для решения задачи Коши

При решении задачи (2. 1) с помощью одношаговых методов значение yn+1 зависит только от информации в предыдущей точке xn. Можно предположить, что можно добиться большей точности, если использовать информацию о нескольких предыдущих точках xn, xn-1... xn-k. На этой идее основаны многошаговые методы.

Большинство многошаговых методов возникает на основе следующего подхода. Если подставить в уравнение (2. 1) точное решение y (x) и проинтегрировать уравнение на отрезке , то получим:

Заменяя в формуле (2. 2) функцию f (x, y (x)) интерполяционным полиномом P (x), получим приближенный метод

Для того, чтобы построить полином P (x), предположим, что yn, yn-1... yn-k - приближения к решению в точках xn, xn-1... xn-k. Полагаем, что узлы xi расположены равномерно с шагом h. Тогда fi=f (xi, yi), (i=n, n-1.. n-k) - есть приближения к f (x, y (x)) в точках xn, xn-1... xn-k.

В качестве P (x) возьмем интерполяционный полином степени, k удовлетворяющий условиям

Если проинтегрировать этот полином явно, то получим следующий метод:

При k=0 полином P (x) - есть константа, равная fn, и формула (2. 4) превращается в обычный метод Эйлера.

При k=1 полином P (x) является линейной функцией, проходящей через точки (xn-1, fn-1) и (xn, fn), т. е.

Интегрируя этот полином от xn до xn+1, получим двухшаговый метод

который использует информацию в двух точках xn и xn+1.

Если k=2, то P (x) представляет собой квадратичный полином, интерполирующий данные (xn-2, fn-2), (xn-1, fn-1) и (xn, fn). Можно показать, что соответствующий метод имеет вид

Если k=3, то соответствующий метод определяется формулой

При k=4 имеем

Отметим, что метод (2. 7) является трехшаговым, (2. 8) - четырехшаговым и (2. 9) - пятишаговым. Формулы (2. 6) - (2. 9) известны как методы Адамса-Бэшфорта. Метод (2. 6) имеет второй порядок точности, поэтому его называют методом Адамса-Бэшфорта второго порядка. Аналогично, методы (2. 7), (2. 8) и (2. 9) называются соответственно методами Адамса-Бэшфорта третьего, четвертого и пятого порядков.

Продолжая этот процесс, используя все большее число предыдущих точек, а также интерполяционный полином более высокой степени, получим методы Адамса-Бэшфорта сколь угодно высокого порядка.

Многошаговые методы порождают трудности, которых не возникает при использовании одношаговых методов. Эти трудности становятся понятными, если, например, обратиться к методам Адамса-Бэшфорта пятого порядка (2. 9).

В задаче (2. 1) задано начальное значение y0 но при n=0 для счета по формуле (2. 9) необходима информация в точках x-1, x-2, x-3, x-4, которая естественно отсутствует. Обычный выход из данной ситуации заключается в использовании какого-либо одношагового метода того же порядка точности, например метода Рунге-Кутты, до тех пор, пока не будет получено достаточно значений для работы многошагового метода. Или же можно на первом шаге использовать одношаговый метод, на втором - двухшаговый и так далее, пока не будут получены все стартовые значения. При этом существенно, чтобы эти стартовые значения были вычислены с той же степенью точности, с какой будет работать окончательный метод. Поскольку стартовые методы имеют более низкий порядок точности, вначале приходится считать с меньшим шагом и использовать больше промежуточных точек.

Вывод методов (2. 6) - (2. 9) основан на замене функции f (x, y) интерполяционным полиномом P (x). Известно, что имеет место теорема, доказывающая существование и единственность интерполяцион ного полинома. Если узлы x0, x1… xn различны, то для любых f0, f1… fn существует единственный полином P (x) степени не выше n такой, что P (xi) =fi, i=0, 1,.. n.

Хотя интерполяционный полином является единственным, имеется несколько способов представления этого полинома. Чаще всего используются полиномы Лагранжа, но и они оказываются неудобными, если к набору данных нужно добавить (или удалить из него) какой-либо узел. В этом случае имеется другое представление интерполяционного полинома. Это представление Ньютона

Полином Pn+1 (x) можно записать в виде

Представление интерполяционного полинома в виде (2. 11) в ряде случаев бывает особенно полезным для практики.

Методы Адамса-Бэшфорта используют уже известные значения в точках xn, xn-1... xn-k. При построении интерполяционного полинома можно использовать и точки xn, xn, xn-1... xn-k. При этом возникает класс неявных m -шаговых методов, известных как методы Адамса-Мултона.

Если k=0, то P (x) - линейная функция, проходящая через точки (xn, fn) и (xn+1, fn+1), и соответствующий метод

является методом Адамса-Мултона второго порядка.

При k=1, 2, 3 получаем соответствующие методы

третьего, четвертого и пятого порядков аппроксимации. Соотношения (2. 12) - (2. 15) содержат искомые значения yn+1 неявно, поэтому для их реализации необходимо применять итерационные методы.

На практике обычно не решают непосредственно уравнений (2. 12) - (2. 15), а используют совместно явную и неявную формы, что приводит к методу прогноза и коррекции.

Например, для метода Адамса второго порядка, используя обозначения, где г - номер итерации, имеем для г=1 следующую схему вычислений:

Этот процесс называют методом PECE (P означает применение предсказывающей формулы, С - применение исправляющей формулы, Е - вычисление функции f). Можно сократить процесс вычисления, отбросив последнюю формулу. Это приводит к так называемому методу PEC.

Рассмотрим второй метод решения уравнений (2. 12) - (2. 15). Формулы (2. 12) - (2. 15) можно переписать в виде

где gn содержит известные величины. Доказано, что если, где L - константа Липшица, то существует единственное решение уравнения (2. 17), которое можно получить с помощью итерационного процесса

где - произвольно.

Итерации в выражении (2. 18) продолжаются до тех пор, пока не будет достигнута сходимость. При этом число вычислений функции f меняется от точки к точке и может быть достаточно велико.

С другой стороны, если уменьшить величину h, то сходимость может быть достигнута за фиксированное число итераций. Этот метод называется исправлением до сходимости.

На первый взгляд может показаться, что явный многошаговый метод является самым простым методом с точки зрения вычислений. Однако на практике явные методы используются очень редко. Неявный метод Адамса-Мултона является более точным, чем явный метод Адамса-Бэшфорта. Например, вычислительная схема для метода Адамса-Мултона 5-го порядка имеет следующий вид:

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

Как и в случае с методом Адамса-Бэшфорта, при использовании метода Адамса-Мултона важным вопросом является вопрос выбора оптимального соотношения шага интегрирования и порядка метода. Следует отметить, что при создании эффективных алгоритмов и программ увеличение порядка метода является более предпочтительным по сравнению с уменьшением шага интегрирования.

Для решения более сложных задач необходимо применять методы Адамса более высокого порядка. В таблице 2. 1 приведены значения коэффициентов для методов Адамса. В первой строке указан порядок метода; во второй - значения коэффициентов Ck для соответствующего порядка k; в последующих строках - пары коэффициентов Bkj и Mkj для методов Адамса-Бэшфорта и Адамса-Мултона соответственно. Тогда, с учетом данных таблицы 2. 14, коэффициенты вj в выражении

для метода Адамса-Бэшфорта k-гo порядка могут быть найдены из cоотношения

а для метода Адамса-Мултона k-гo порядка по аналогичной формуле

Формулы для предикторно-корректорных методов Адамса с 6-го по по 14-ый порядок имеют следующий вид:

• 6 порядок:
• 7 порядок:
• 8 порядок:
• 9 порядок:
• 10 порядок:
• 11 порядок:
• 12 порядок:
• 13 порядок:
• 14 порядок:
• 15 порядок:
• 16 порядок:

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

При S = 1 формула (6.16) примет вид

Если Q = 2, получим следующее вычислительное правило:

Обычно на практике используют экстраполяционную формулу (6.18), а затем корректируют полученное значение по формуле (6.23). И если результат уточненного значения не превышает допустимую погрешность расчета, то шаг H считается допустимым .

Для расчетов на компьютере формулы (6.18) и (6.23) в конечно-разностном виде неудобны. С учетом (6.21) их можно представить в виде

(6.24)

Приведенные формулы имеют достаточно большую точность. Они дают погрешность порядка ~ О (H4 ), но сами формулы оценки погрешности достаточно сложны. Приближенно погрешность можно оценить по правилу Рунге.

Пример 6.2. Решить дифференциальное уравнение на отрезке c начальным условием Y (X = 0) = 1. Найти методом Адамса (с коррекцией) в точке X 4 , в трех первых точках найти методом Рунге- Кутта, приняв шаг .

Решение. Значения функции в четырех первых точках возьмем из табл. 6.1 (см. пример в предыдущем разделе). Теперь стало понятно, зачем мы сохраняли значения первой производной в этих точках (см. формулы (6.24)).

X4 = X3 + H = 0.15 + 0.05 = 0.2;

Для того чтобы скорректировать полученный результат, необходимо вычислить значение производной в этой точке:

Теперь уточним значение по интерполяционной формуле (а можно этого и не делать, тогда погрешность метода будет больше):

Так как в качестве нового значения функции принято скорректированное, то Обязательно Следует пересчитать значение производной. В нашем случае модуль разности экстраполяционной и интерполяционной формул меньше ε, Что позволяет продолжить вычисления с тем же шагом.

Вопросы для самопроверки

· Сформулируйте задачу Коши для обыкновенных дифференциальных уравнений первого порядка.

· Что является решением дифференциального уравнения: а) в высшей математике, б) в прикладной математике?

· Какие методы дифференциальных уравнений называются одношаговыми, многошаговыми? Приведите примеры.

· Сравните , полученные на первом, втором шаге методами Эйлера, Рунге-Кутта и разложением в ряд Тейлора (трудоемкость, погрешность…).

· Как оценить погрешность применяемого метода? Как ее уменьшить?

· Сравните одношаговые и многошаговые методы решения дифференциальных уравнений, указав достоинства и недостатки первых и вторых.

· Что такое экстраполяционные и интерполяционные методы (формулы) Адамса?

· Можно ли применять: а) только экстраполяционные методы Адамса,
б) только интерполяционные?

· Можно ли использовать: а) многошаговые методы без одношаговых;
б) одношаговые методы без многошаговых?

· При решении дифференциального уравнения методом Адамса на 27-м шаге необходимо сменить шаг. Как это сделать?