§ 1.7. Устойчивость разностных схем

В отличие от схем Рунге — Кутты, многошаговые схемы устойчивы не всегда. В этом параграфе исследуются свойства устойчивости многошаговых схем.

1.7.1. Пример.

Рассмотрим явный линейный двухшаговый метод

xi - 3xi-1 + 2xi-2 = t[f(ti-1, xi-1) - 2f(ti-2, xi-2)].

(1)

в применении к задаче Коши

xў = 2t,   x(0) = 0.

Очевидно ее решением является функция j(t) = t².

Задача 1.7.1. С помощью теоремы 1.6.9 покажите, что схема (1) является схемой первого порядка аппроксимации.

Начальный запуск схемы определим, положив

x0 = 0,   x1 = t2

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

(jt)i = (2i + i2 - i -1)t2 при i і 2.

(2)

Задача 1.7.2. Проверьте.

Заметим теперь, что при достаточно малом t

||jt - Ptj||t =  max 2ЈiЈn |(jt)i - j(ti)| =

= max 2ЈiЈn |(2i + i2 -i - 1 - i2)t2| = max 2ЈiЈn |2i - i – 1|t2 =

= (2n - n - 1)t2 =  ж и 2T/t -  T t  – 1 ц ш t2 ® Ґ при t ® 0.

Таким образом, схема (1) хотя и является аппроксимирующей, не является сходящейся. Дело здесь, разумеется, в ее неустойчивости. Попробуем понять это явление подробнее. Ответственным за несходимость решения (2) к точному решению является первое слагаемое. А источник его появления таков. Решение уравнения (1) по аналогии с линейным обыкновенным дифференциальным уравнением (а также с системой линейных алгебраических уравнений, каковой она собственно и является) можно искать в виде "общее решение линейного однородного уравнения + частное решение неоднородного", а первое из них в виде z ⁱ (ср. с нахождением решений линейных однородных дифференциальных уравнений с постоянными коэффициентами в виде e^lt = z ^t (здесь z = e^l). Тогда для того чтобы сеточная функция z ⁱ была решением однородной схемы (1), нужно, чтобы

z i - 3z i-1 + 2z i-2 є 0,

или, что эквивалентно,

z2 - 3z+ 2 = 0.

(3)

Таким образом, сеточная функция i ® z ⁱ является решением однородной схемы (1), если и только если z — корень уравнения (3). Наличие у этого уравнения корня z = 2 и дает слагаемое, пропорциональное 2ⁱ, растущее при t ® 0.

1.7.2. Устойчивость. Наводящие соображения.

Рассмотрим линейный p-шаговый метод

p е s = 0 asxi-s = t p е s = 0 bs f(ti-s, xi-s).

(4)

Можно надеяться, поскольку нас интересует поведение решений при t ® 0, что это поведение характеризует однородная разностная схема

p е s = 0 asxi-s = 0,

(5)

получающаяся из (4) при t ® 0. Кроме того, эту надежду подтверждает аналогия с обыкновенными дифференциальными уравнениями. Будем искать решение уравнения (5) в виде экспоненциальной функции. Подставив x_i = z ⁱ в (5):

p е s = 0 asz i-s =  ж и p е s = 0 asz p-s ц ш z i-p = 0,

получим, что сеточная функция i®z ⁱ является решением (5) в том и только том случае, если число z является корнем полинома

r(z) =  p е s = 0 asz p-s.

Этот полином называется производящим полиномом метода (4). Более того, если z — корень характеристического полинома кратности l, то решениями (5) являются также сеточные функции i ® i^jz ⁱ с j = 0, 1,..., l - 1.

Задача 1.7.3. Докажите!

Очевидно, что i ® i^jz ⁱ ограничена по i в том и только в том случае, если либо |z| < 1, либо |z| = 1 и j = 0. Поэтому для для того чтобы однородная схема (5) не имела растущих при i ® Ґ решений, нужно, чтобы корни производящего полинома лежали в (замкнутом) единичном круге комплексной плоскости C, причем те из них, которые лежат на границе круга, были простыми. Схемы, производящие полиномы которых удовлетворяют указанному свойству, называются схемами, удовлетворяющими корневому условию.

Отметим здесь же, что в силу теоремы 1.6.9 (см. условие (1.6.9)), если метод (4) является аппроксимирующим, то его производящий полином с необходимостью имеет единичный корень: r(+1) = еps=0 as = 0.

1.7.3. Теорема об устойчивости линейных многошаговых методов.

Для того чтобы схема (4) была устойчивой, необходимо и достаточно, чтобы соответствующая однородная схема (5) удовлетворяла корневому условию.

Д о к а з а т е л ь с т в о  необходимости нами, по существу, уже проведено. В самом деле, применение метода (4) к дифференциальному уравнению xў = 0 приводит к однородной схеме (1). Поэтому, если она не удовлетворяет корневому условию (скажем, для определенности, имеет корень z такой, что |z| > 1), то у нее есть решение вида z ⁱ. Поэтому при произвольных малых z решение y_t разностной схемы F_tx = z будет содержать слагаемое вида cz ⁱ, а поэтому ||y_t - j_t||_t будет стремиться к бесконечности при i ® Ґ.

Доказательство достаточности сложнее, и мы его опускаем.

Задача 1.7.4. Восстановите детали доказательства.

Задача 1.7.5. Рассмотрите случай кратного равного по модулю единице корня.

Производящий полином p-шаговых методов Адамса (как явных, так и неявных) имеет вид r(z) = z ^p - z ^p-1. Поэтому они, очевидно, устойчивы.

1.7.4. Сходимость линейных многошаговых методов.

В силу теоремы 1.6.9 для того, чтобы линейный p-шаговый метод (4) обладал k-м порядком аппроксимации, нужно удовлетворить k + 1 условие (1.6.9) на коэффициенты метода. Свободных же параметров в методе (4) ровно 2p + 1 (напомним, что мы считаем a₀ = 1). Поэтому теоретически достижимый порядок аппроксимации линейного p-шагового метода равен 2p. Однако, оказывается, методы (4) высокого порядка обязательно оказываются неустойчивыми и, следовательно, несходящимися. Более точно, имеет место следующая

Теорема Далквиста. Пусть k — порядок сходимости линейного p-шагового метода. Тогда k Ј p + 2, если k четно, k Ј p + 1, если k нечетно, k Ј p, если b₀ = 0 (т. е. если метод явный).

Эта теорема (доказательство которой мы опускаем) задает ограничение на порядок сходимости многошаговых методов. Линейные устойчивые p-шаговые методы (p+2)-го порядка аппроксимации (и, следовательно, сходимости) называются оптимальными.

1.7.5. Абсолютная устойчивость.

Обсуждавшееся выше понятие устойчивости гарантирует, что устойчивый метод хорошо работает лишь при t ® 0. При этом в конкретной ситуации при конкретном (даже весьма малом) t погрешность может сильно возрастать с ростом i. В реальности же нам нужно знать поведение при данном конкретном t. Поскольку трудно выяснить, заключается ли причина роста погрешности в неустойчивости метода или в неустойчивости самогó дифференциального уравнения, важно выделить свойства устойчивости метода, безотносительные к свойствам дифференциального уравнения. Здесь обычно поступают так. Вместо произвольного дифференциального уравнения рассматривают так называемое модельное уравнение

xў = lx

(6)

с комплексным параметром l. Мотивировка выбора уравнения (6) в качестве модельного такова. Во-первых, его предельная простота. Во-вторых, это уравнение "представляет" локальное поведение решение общего дифференциального уравнения (E) в следующем смысле. Решения уравнения (E) локально (в окрестности любой точки (t₀, x₀)) ведут себя как решения линеаризованного уравнения

xў = fx(t0, x0)x

(7)

в окрестности нуля. В случае, когда жордановы клетки линейного оператора f_x(t₀, x₀) простые (т. е. имеют размерность 1×1) уравнение (7) невырожденной заменой переменных приводится к уравнениею с диагональной матрицей, на диагонали которой стоят собственные значения f_x(t₀, x₀), а получившееся уравнение распадается на систему уравнений вида (6) (случай не простых жордановых клеток не является случаем общего положения). Поэтому есть надежда, что по поведению решений разностного метода на уравнениях вида (6) можно с той или иной степенью достоверности предсказать их поведение на произвольных дифференциальных уравнениях.

Будем говорить, что метод (4) абсолютно устойчив при данном t и данном l О C, если его глобальная погрешность E_n(t) при применении его к уравнению (6) с данным l при t ® 0 остается ограниченной.

1.7.6. Область абсолютной устойчивости.

Применение метода (4) к уравнению (6) приводит к разностной схеме

p е s = 0 asxi-s = t p е s = 0 bslxi-s,

или

p е s = 0 (as – tlbs)xi-s = 0.

(8)

Соответствующее возмущенное уравнение имеет вид

p е s = 0 (as – tlbs)xi-s = tzi.

(9)

Как и в п. 1.7.2, общее решение неоднородного уравнения (9) складывается из общего решения однородного уравнения (8) и частного решения неоднородного уравнения (9). Частное решение можно считать малым. Поэтому поведение (9) определяется поведением решений однородного уравнения (8). Так же, как и выше, тривиально показывается, что функция z ⁱ является решением уравнения (8) в том и только том случае, если z является корнем полинома

ptl(z) =  p е s = 0 (as - tlbs)z p-s,

называемого обычно полиномом устойчивости метода (4). Таким образом, если корни полинома лежат в единичном круге, то у уравнения (7) нет растущих решений (предоставляем читателю возможность произнести все нужные слова, относящиеся к корням, лежащим на границе круга).

По существу, мы показали, что если при данном t и l О C все корни полинома устойчивости p_tl лежат в единичном круге, то метод абсолютно устойчив при данных t и l. Множество S тех z О C, при которых корни полинома устойчивости p_z лежат в единичном круге, называется областью абсолютной устойчивости метода (4). Другими словами, для того чтобы метод (4) был абсолютно устойчив при данных t и l, нужно, чтобы tl О S.

1.7.7. Пример: область устойчивости неявного метода Эйлера.

Полином устойчивости неявного метода Эйлера, очевидно, имеет вид

pz(z) = (1 - z)z- 1.

Его единственный корень — z = (1 - z)^-1. Он не превосходит по модулю единицы в том и только в том случае, если |z - 1| і 1. Таким образом, S = {z О C: |z - 1| і 1} (рис. 9,а).

Рис. 9.

Задача 1.7.6. Докажите, что для явного метода Эйлера S = {z О C: |z + 1| Ј 1} (рис. 9,б), а для неявного одношагового метода Адамса S = {z О C: Re z Ј 0} (рис. 9,в).

1.7.8. Зачем нужно знать область устойчивости метода?

Тривиальный пример применения неявного метода Эйлера для нахождения нулевого решения задачи Коши

xў = x,   x(0) = 0

показывает, что погрешность e₀ в определении начального условия распространяется по закону

ei = (1 - t)-ie0.

Очевидно, если шаг t О (0, 2), то погрешность растет по экспоненциальному закону с ростом i. Это происходит из-за того, что агрегат tl (в данном случае равный t) не лежит в области устойчивости метода.

Поэтому для контроля шага (особенно при применении одношаговых методов к системам малой размерности) иногда поступают так. Через некоторое число шагов находят матрицу Якоби f_x и все ее собственные значения, а затем корректируют шаг так, чтобы произведение шага на каждое собственное значение лежало в области устойчивости используемого метода. Эта процедура достаточно дорогостояща. Поэтому в случае больших размерностей ее обычно не применяют.

Кроме того, форма и размеры области абсолютной устойчивости важны при сравнении различных методов.

Несколько слов о нахождении области абсолютной устойчивости метода. Для простых случаев область может быть указана аналитически. В более сложных ситуациях применяют следующее рассуждение. Если точка z лежит на границе ¶S области S, то при этом z полином устойчивости p_zимеет корень z, равный по модулю единице: z = e^ia (здесь i — мнимая единица), т. е.

pz(eia) = 0.

(10)

Решим при каждом a О [0, 2p] уравнение (10) относительно z и обозначим его решение через z(a). С известными оговорками z(a) представляет собой параметризацию границы ¶S области устойчивости S или ее части.

File based on translation from T_EX by T_TH, version 3.05.
Created On 29 May 2002, 8: 37.