§ 1.2. Разностные схемы. Сходимость, аппроксимация, устойчивость

После такой подготовки приступит он к судебным делам и прежде всего установит, какого рода эти дела.

Цицерон. Оратор

В данном параграфе на примере явного метода Эйлера даются основные понятия теории разностных схем — понятия сходимости, аппроксимации и устойчивости. Доказывается теорема Лакса. Описываются основные приемы построения разностных схем.

Напомним, что метод ломаных Эйлера – это метод нахождения аппроксимирующей интегральную кривую ломаной, который в образах парка со стрелками-указателями может быть представлен так (рис. 2). Из точки (t₀, x₀) = (t₀, x⁰) расширенного фазового пространства движемся t "секунд", сообразуясь со стрелкой, помещенной в этой точке, и не обращая внимания на остальные стрелки. Придя (через время t) в точку (t₁, x₁), меняем направление, пользуясь указанием, задаваемым стрелкой в точке (t₁, x₁); через t секунд приходим в точку (t₂, x₂), опять меняем направление и т. д. Полученная траектория и является ломаной Эйлера, аппроксимирующей решение задачи (E) – (C).

Легко видеть, что координаты i-й вершины (i = 1,..., n) ломаной Эйлера определяются формулами

Запишем метод ломаных Эйлера в общем виде, в котором могут быть записаны другие разностные методы и который позволяет укладывать исследование таких методов в общую схему. Для этого сначала запишем задачу (E) – (C) в операторной форме. Начальное условие (C) можно записать в виде

где функция g имеет вид g(x) = x(t₀) - x⁰. Тогда начальную задачу (E) – (C) можно записать в операторной форме

F(x) = 0,

(O)

где F(x) = (xў(·) - f(·, x), g(x)). Не будем обсуждать подробно вопрос об областях определения и значений оператора F. В случае задачи (E) – (C) можно считать, например, что областью определения D(F) оператора F служит пространство C¹([t₀, t₀ + T], R^m) непрерывно дифференцируемых на отрезке [t₀, t₀ + T] функций со значениями в R^m, а областью значений R(F) — декартово произведение C¹([t₀, t₀ + T], R^m)×R^m. Заметим, что решение j задачи (E) – (C) есть прообраз нуля для оператора F: j = F^-1(0).

1.2.3. Операторная форма метода ломаных Эйлера.

Пусть x — сеточная функция из S_t. Определим на S_t оператор F_t равенством

[F_t(x)]_i =

м
п
н
п
о

x_i – x_i–1

– f(t_i–1, x_i–1), если i = 1, ..., n,

x_i – x⁰, если i = 0;

(2)

(Здесь [F_t(x)]_i обозначает значение сеточной функции [F_t(x)] в точке t_i.)

Задача о нахождении ломаной Эйлера, очевидно, эквивалентна задаче о нахождении решения j_t уравнения

F_t(x) = 0

(S)

в пространстве S_t сеточных функций в следующем смысле: значения (j_t)_i решения уравнения (S) в узлах сетки и только они являются ординатами вершин ломаной Эйлера в точках t_i (см. формулу (1)). Таким образом, вместо точного решения j = F^-1(0) мы ищем приближенное решение j_t = F_t^–1(0).

Любое уравнение вида (S) для нахождения сеточной функции x будем называть разностной схемой, а его (уравнения) решение, которое мы всегда будем обозначать j_t, — разностным или сеточным решением (уравнения (S)). Оператор F_t будем называть разностным оператором. Разумеется, в таком общем виде определение разностной схемы никак не связано с исходной задачей Коши (E) – (C) (уравнением (O)). В то же время, если в (S) оператор F_t определен формулой (2), то разностная схема (S) имеет к задаче (E) – (C) самое непосредственное отношение (объяснить, что означают эти слова, и есть цель остальной части параграфа).

В последнем случае разностная схема (S) называется явной (разностной) схемой Эйлера. Явной она называется потому, что ее решение может быть выписано в явном виде с помощью рекуррентных соотношений:

Единственное отличие метода ломаных Эйлера от явной схемы Эйлера заключается в том, что в первом ищется функция, заданная на отрезке [t₀, t₀ + T] (ломаная Эйлера), а во втором — на сетке G_t (вершины этой ломаной).

1.2.5. Пример. Сходимость явной разностной схемы Эйлера.

В условиях задачи 1.2.1 разностное решение j_t аппроксимирует решение j(t) = x⁰e^at интересующей нас исходной (дифференциальной) задачи в следующем смысле: при всех t О [0, T]

(j_t)_i® x⁰e^at при t® 0,

(3)

где i = [t/t] (здесь [t/t] — целая часть числа t/t; ниже мы наряду с обозначением [a] для целой части числа a используем обозначение {a} для его дробной части: a = [a]+ {a}). Действительно,

Сомножитель lim_t®0(1 + ta)^-{t/t} равен единице, поскольку {t/t} О (0, 1). Второй сомножитель также вычисляется тривиально:

lim
t®0

(1 + ta)^t/t =

lim
t®0

(1 + ta)^{[1/(ta)] ·at} =

й
л

lim
t®0

(1+ ta)^1/ta

щ
ы

^at

= e^at

Задача 1.2.2. Докажите более сильное, чем (3) утверждение

означающее, что предельное соотношение (3) выполнено равномерно по i О {1, ..., n).

Будем говорить, что разностная схема (S) сходится (к решению j задачи (E) – (C)), если

||j_t - P_tj||_t® 0 при t®0.

(4)

Сходимость разностной схемы означает, что при достаточно малом t значения сеточного (приближенного) решения j_t и точного решения j мало отличаются. Соотношение (4) на практике оказывается мало полезным, поскольку на основании его нельзя судить о том насколько малым мы должны выбрать шаг t, чтобы в узлах сетки точное и приближенное решения отличались друг от друга не более, чем на e (заранее заданную точность). Если удается доказать, что при достаточно малых t > 0

||j_t - P_tj||_t Ј Ct^k,

(5)

где C — не зависящая от t константа, то говорят, что схема (S) сходится с порядком k (или является схемой k-го порядка (сходимости)). Оценка (5), если в ней известна (для конкретной задачи (E) – (C)) константа C, позволяет по заранее выбранной точности e a priori выбрать шаг так, чтобы приближенное решение аппроксимировало решение данной (дифференциальной) задачи Коши с точностью e:

Явная схема Эйлера обладает двумя важными свойствами, из которых, как будет показано ниже, последует ее сходимость с первым порядком. Во-первых, при достаточно малых t

где C_a — константа, не зависящая от t, а j — как обычно, точное решение задачи (E) – (C). В этом случае говорят, что схема (S) имеет первый порядок аппроксимации на решении. (Если в правой части неравенства (6) стоит C_at^k, то, соответственно, говорят о схеме k-го порядка аппроксимации (на решении).) Другими словами, неравенство (6) эквивалентно тому, что ||F_t(P_tj)||_t = O(t) (в случае схемы k-го порядка аппроксимации — O(t^k)). Тот факт, что разностная схема обладает аппроксимацией на решении, означает, грубо говоря, что при подстановке точного решения дифференциальной задачи в разностную схему мы получаем невязку соответствующего порядка малости по t. (Было бы идеально, если бы после такой подстановки мы получали в левой части нуль, однако в общем случае конструктивно такие схемы выписать нельзя.)

Обычно требуется, чтобы схема обладала свойством аппроксимации на множестве функций из некоторого класса гладкости. Очевидно, если решения дифференциального уравнения (E) m раз непрерывно дифференцируемы, а разностная схема обладает k-м порядком аппроксимации (согласованности) на m раз непрерывно дифференцируемых функциях, то она обладает k-м порядком аппроксимации на решении.

Поскольку f дифференцируема по t и x, решение j дважды непрерывно дифференцируемо (см. утверждение о гладкости решений). В частности, найдется M такое, что ||jўў(t)|| Ј M при всех t О [t₀, t₀ + T]. Кроме того, в силу гладкости j для любых t = 1, ..., n

- f[t_i-1, j(t_i-1)] = jў(t_i-1) +

t²

jўў(t_i-1 + J_it) - f[t_i-1, j(t_i-1)]=

(Если i = 0, то очевидно, [F_t(P_tj)]_i = 0.) Из сказанного следует, что

Второе важное свойство, которым обладает явная схема Эйлера, называется устойчивостью и определяется так: если z О S_t и, кроме того, ||z||_t и t достаточно малы, то уравнение

F_t(y) = z

(7)

однозначно разрешимо и существует такая не зависящая от t и ||z||_t константа C_s, что

||y - j_t||_t = ||F_t^-1(z)- j_t||_t Ј C_s||z||_t.

(8)

Устойчивость разностной схемы означает, что малые возмущения z в начальных данных и правой части разностной схемы приводят к равномерно малому по t изменению решения (напомним, что j_t — решение невозмущенной системы, а F_t^-1(z) — возмущенной). Поскольку j_t = F_t^-1(z),неравенство (8), переписанное в виде ||F_t^-1(z)- F_t^-1(0)||_t Ј C_s||z|| _t, означает, в частности, непрерывность обратного к разностному оператору оператора F_t^-1в нуле.

Устойчивость — очень важное в приложениях свойство разностных схем. При практической реализации на ЭВМ разностных методов возникают, в частности, проблемы, связанные с невозможностью представления точных чисел в компьютере. В результате мы решаем не разностную схему (S), а несколько отличающееся от (S) уравнение. Все такие возмущения в разностной схеме, грубо говоря, можно "перенести в правую часть" и, таким образом, считать, что в ЭВМ ищется решение не разностной схемы (S), но решение возмущенного уравнения (7). Свойство устойчивости разностной схемы гарантирует близость при достаточно малых t между точным (теоретическим) решением j_t разностной схемы и его практической реализацией F_t^-1(z)(где z — суммарный вектор возмущений). Источником возмущений служит не только невозможность точного представления данных в ЭВМ, но и неточность определения физических параметров модели, погрешность измерений и т.п.

1.2.10. Пример. Устойчивость явной схемы Эйлера.

Докажем, что явная схема Эйлера устойчива.

Разрешимость уравнения (7) для любых t и z очевидным образом следует из того, что явная схема Эйлера является явной: значения y_i решения y = F_t^-1(z) этого уравнения определяются рекуррентными формулами

Ј ||x_i-1|| + tL||y_i-1 - (j_t)_i-1|| + t||z|| _t = (1 + tL)||x_i-1|| + t||z|| _t.

Воспользуемся теперь известным неравенством (1 + a)^1/a < e (напомним также, что t = T/n):

(1 + tL)ⁱ Ј (1 + tL)ⁿ = (1 + tL)^[(TL)/(tL)] Ј [(1 + tL)^[ 1/(tL)]]^TL < e^TL.

max
0ЈiЈn

e^TL·

L + 1

||z|| _t = e^TL·

L + 1

||z||_t =def C_s|| z|| _t.

Любая устойчивая разностная схема k-го порядка аппроксимации на решении является схемой k-го порядка сходимости.

Д о к а з а т е л ь с т в о. Действительно, если разностная схема имеет k-й порядок аппроксимации на решении, то ||F_t(P_tj)||_t Ј C_at^k и поэтому, в частности, при малых t мала и ||F_t(P_tj)||_t. Следовательно, в силу устойчивости, F_t^-1[F_t(P_tj)] существует и ||F_t^-1[F_t(P_tj)]- j_t||_t Ј C_s||F_t(P_tj)||_t. Но тогда, очевидно,

Эта теорема описывает наиболее распространенный способ доказательства сходимости разностных схем.

1.2.12. Немного о методах построения разностных схем.

Явная схема Эйлера может быть построена, исходя из различных соображений. Каждый из описываемых ниже приемов порождает ряд обобщений явной схемы Эйлера и может иллюстрировать основные методы построения разностных схем. В дальнейшем эти методы будут рассматриваться подробнее.

Попытаемся, отталкиваясь от уравнения (E), заменить его приближенным в том или ином смысле уравнением так, чтобы в результате получилась разностная схема. Первая идея выглядит так. Заменим в уравнении

xў(t) = f[t, x(t)]

(9)

производную xў(t) в точке t_i-1 ее приближенным значением [x(t_i) - x(t_i-1]/t, а правую часть — ее значением в этой точке. В результате получим приближенное уравнение

для отыскания значений точного решения уравнения (E) в точках сетки G_t. Переход к сеточным функциям и замена приближенного равенства точным приводит к точному уравнению для приближенных значений решения, а именно, к явной схеме Эйлера. Использование других аппроксимаций производной в (9) (например, xў(t_i-1) » [x(t_i+1) - x(t_i-1)]/2t, а также других аппроксимаций правой части (например, f[t_i, x(t_i)]) взамен f[t_i-1, x(t_i-1)] позволяет получать другие разностные схемы.

Вторая идея основывается на замене дифференциального уравнения (9) интегральным

x(t + t) = x(t) +

t+t

t

f[s, x(s)]ds,

(10)

Если заменить в (10) t на t_i-1, а интеграл — приближенной квадратурной формулой (в данном случае прямоугольников), то мы получим приближенное уравнение

которое так же, как и выше приводит к явной схеме Эйлера. Если использовать другие квадратурные формулы (заменяя, например, интеграл на tf[t_i, x(t_i)] или t[f(t_i-1, x(t_i-1)) + f(t_i, x(t_i))]/2), то будут получаться другие разностные схемы.

Третья возможность построения разностных схем связана с разложением решения в ряд Тейлора:

"Обрежем" этот ряд до второго члена и выразим производную xў(t_i-1) из (9). В результате получим все то же приближенное уравнение

приводящее к явной схеме Эйлера. Удлинение отрезка ряда и другие аппроксимации коэффициентов приводят к другим разностным схемам.

Наконец, четвертая возможность связана с поиском решения в виде полинома. Допустим, мы ищем решение в виде полинома первого порядка:

с неизвестным коэффициентом a. Потребуем, чтобы этот полином точно удовлетворял уравнению (9) в некоторой точке t_i-1 + a:

Переходя к сеточным функциям, как и выше, получаем разностную схему:

При a = 0 это явная схема Эйлера. Если выбирать отличные от нуля a, а также брать полиномы более высоких порядков, то получается класс различных разностных схем.

File based on translation from T_EX by T_TH, version 3.05.
Created 23 May 2002, 20:10.