Часть II. Очерки по теории обыкновенных дифференциальных уравнений

Назад § О34. Приближенные методы решения краевых задач Вперед

...В сердце он попадает, — Коровьев вытянул свой длинный палец по направлению Азазелло, — по выбору, в любое предсердие сердца или в любой из его желудочков.

Маргарита не сразу поняла, а поняв, воскликнула с удивлением:

— Да ведь они же закрыты!

Дорогая, — дребезжал Коровьев, — в том-то и штука, что закрыты! В этом-то вся и соль! А в открытый предмет может попасть каждый!

М. Булгаков. Мастер и Маргарита

— Кажется, я начинаю понимать, — сказал Дортмундер. — Компьютер — это машина, которая ничего не знает, пока я что-нибудь ей не скажу, и которая поверит мне, если я совру.

Д. Уэстлейк. Утонувшие надежды

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

x′′ = f(t, x, x′),    t ∈ [0, T], (1)

x(0) = x0,    x(T) = x1; (2)

здесь, как обычно, f: [0, TR×RR — непрерывная функция.

Основные методы приближенного решения краевых задач можно разбить на три большие группы.

Первую группу составляют так называемые методы стрельбы. В идейном плане эти методы аналогичны методу стрельбы доказательства разрешимости краевых задач. Для приближенного нахождения решения краевой задачи (1)(2) рассматривается вспомогательная задача Коши, например, такая:

x′′ = f(t, x, x′),    t ∈ [0, T], (3)

x(0) = x0,    x′(0) = α, (4)

в которой α — подлежащий определению параметр. Предположим мы можем при каждом α указать решение x(t, α) задачи (3)(4). Тогда, решив относительно α уравнение

x(T, α) = x1, (5)

мы найдем искомое решение x(t, α0), где α0 — решение уравнения (5). В общем случае, разумеется, функцию x(t, α) обозримой формулой указать нельзя. Поэтому для решения задачи Коши (3)(4) используют один из приближенных методов. Уравнение (5)тоже решают каким-либо приближенным численным методом, например, в скалярном случае методом деления отрезка пополам. В общем случае используют итерационный метод Ньютона, метод секущих и т. п. (см. любой курс методов вычислений). Таким образом, приближенное решение краевой задачи (1)(2) свелось к приближенному решению задачи Коши (3)(4) и приближенному решению уравнения (5).

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

x′′ + a1(t)x′ + a0(t)x = φ(t),    t ∈ [0, T], (6)

c0x(0) + c1x′(0) = 0, (7)

d0x(T) + d1x′(T) = 0, (8)

Пусть x1 — решение задачи Коши для неоднородного уравнения (6), определяемой начальными условиями

x(0) = –c1,    x′(0) = c0, (9)

а x2 — решение выделяемой этими же начальными условиями задачи Коши для соответствующего однородного уравнения. Очевидно функция x(t, α) = x1(t) + αx2(t) является решением уравнения (6) и, в силу (9), удовлетворяет первому краевому условию (7). Остается теперь подобрать α так, чтобы в точке t = T выполнялось второе краевое условие:

α =   d0x1(T) + d1x1(T)
d0x1(T) + d1x2(T)
.

Основным недостатком методов стрельбы является следующее обстоятельство: если исходное уравнение содержит быстро растущие решения, например, типа eλt с λ >> 1, то вычисление функции α → x(T, α), необходимой для решения уравнения (5), происходит с большой потерей точности (ошибка тоже нарастает как eλt), что ведет к потере точности и в решении уравнения (5). Не спасает здесь и замена начальной точки t = 0 в задаче (3)(4) на точку t = T, поскольку уравнение (1) может одновременно иметь как решения, растущие как eλ1t 1 >> 1), так и решения, убывающие как eλ2t 2 << –1) (т. е. растущие влево с большой экспоненциальной скоростью).

Задача О34.1. Продемонстрируйте последнее утверждение на примере краевой задачи

x′′ = 106x,    t ∈ [0,1];    x(0) = 1, x(1) = 1.

Вторую группу составляют конечно-разностные или сеточные методы приближенного решения краевых задач. Так же, как и в случае задачи Коши, краевая задача сводится к разностной схеме

Fτ(y) = 0, (10)

решением которой является сеточная функция yτ приближенное решение краевой задачи. Так же, как и в предыдущем очерке, вводятся понятия сходимости, аппроксимации и устойчивости разностной схемы. И, наконец, наиболее распространенный способ доказательства сходимости разностной схемы дает та же теорема Лакса о сходимости разностной схемы.

Мы рассмотрим в качестве иллюстрации простейшую линейную краевую задачу

x′′ + a0(t)x = φ(t),    t ∈ [0, T], (11)

x(0) = x0,    x(T) = x1; (12)

и простейшую разностную схему ее решения. При этом мы будем предполагать, что a0(t) < 0 при всех t. Пусть Mτ равномерная сетка на [0, T]: Mτ = {ti = iτ: i = 0, ..., k} (будем считать, не ограничивая общности, что tk = T). Рассмотрим следующую разностную схему

{
yi+1 – 2yi + yi – 1
τ2
 + a0(ti) yi – φ(ti),    i = 1, ..., k – 1
yix0,    если i = 0
yix1,    если i = k
} = 0,
(13)

Очевидно, y0 = x0, yk = x1. Исключая из (13) неизвестные y0 и y1, после очевидных преобразований и обозначений получим следующую линейную систему уравнений относительно y1, ..., yk–1:

Ay =
|
|
|
|
|
|
|
|
|
|
|
λ11 00...000
1 λ210... 000
01 λ31...0 00
001 λ4...00 0
:::: ···:::
0000... λk–3 10
0000... 1λk–2 1
0000... 01λk–1

|
|
|
|
|
|
|
|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
y1
y2
y3
:
yk–2
yk–1

|
|
|
|
|
|
|
|
|
|
|
  =  
|
|
|
|
|
|
|
|
|
|
|
φ1
φ2
φ3
:
φk–2
φk–1

|
|
|
|
|
|
|
|
|
|
|
= 0.
(14)

в которой λi = τ2a0(ti ) – 2.

Задача О34.2. Проведите указанные преобразования.

Матрица A имеет специальную структуру — она трехдиагональна, т. е. лишь на главной и двух соседних ее диагоналях стоят ненулевые элементы. Кроме того, λi = τ2a0(ti) – 2 < –2. Такая структура матрицы позволяет модифицировать стандартный алгоритм Гаусса решения линейных систем алгебраических уравнений (требующий, как известно, O(k3) арифметических операций). Описываемая ниже модификация метода исключения называется методом прогонки и требует O(k) операций.

Введем неизвестные ξi и ηi (i = 1, ..., k – 1) (они называются прогоночными коэффициентами) и потребуем, чтобы они удовлетворяли уравнениям

yi–1 = ξiyi + ηi. (15)

Выразим, пользуясь (15), yi–1 и yi через yi+1 и подставим получившиеся выражения в i-ое уравнение системы (14). После несложных преобразований получим

[(ξi + λii+1 + 1]yi+1 + [(ξi + λii+1 + ηi] = αi.

Последнее равенство будет выполнено, например, если будут выполнены равенства

 ξi+1 = – 1
ξi + λi
,   ηi = αi – ηi
ξi + λi
.
(16)

Алгоритм прогонки выглядит так. Положим ξ1 = 0, η1 = y0. Пользуясь соотношениями (16) рекуррентно вычислим прогоночные коэффициенты ξi и ηi (i = 2, ..., k – 1) (этот этап называется прямой прогонкой). Подставляя (15) при i = k – 1 в последнее уравнение системы (14), находим yk–1 = k–2 – ηk–2) · k–1 + λk–1)–1 и, наконец, пользуясь (15), рекуррентно находим yk–2, ..., y1 (обратная прогонка).

Задача О34.3. Индукцией по i покажите, что xi ∈ [0,1) и поэтому все знаменатели в алгоритме прогонки отличны от нуля (напомним, что λi < –2).

Задача О34.4. Восстановите все детали алгоритма и его обоснования.

Таким образом, разностная схема (13) всегда разрешима.

Задача О34.5. Докажите, что если функции a0 и φ в (11) дважды непрерывно дифференцируема на [0, T], то схема (13) имеет второй порядок аппроксимации на решении.

Задача О34.6. Покажите, что схема (13) устойчива.

Поэтому в силу теоремы о сходимости разностной схемы схема (13) сходится со вторым порядком точности.

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

В случае общей нелинейной задачи (1)(2) разностные схемы представляют собой нелинейную систему алгебраических уравнений. Их решают каким-либо приближенным методом. Или, чаще, нелинейную краевую задачу сводят так называемым итерационным методом Ньютона (или каким-либо другим) к последовательности линейных краевых задач. Суть этого метода такова. Выбрав удовлетворяющее краевым условиям (2) начальное приближение x0 решения, определим последовательность {xk} приближенных решений задачи (1)(2) рекуррентным соотношением

xk+1 = xk + yk,

где yk — решение линейной краевой задачи

y′′ = a1(t)y′ + a0y + φ(t), (17)

y(0) = 0,   y(T) = 0. (18)

В ней

a1(t) =  f(t, x, y)
y
|

x = xk(t), y = xk′(t)
,

a0(t) =  f(t, x, y)
x
|

x = xk(t), y = xk′(t)
,

φ(t) = f[t, xk(t), xk(t)]x′′k(t).

Уравнение (17) получается подстановкой функции x = xk + y в уравнение (1) и отбрасыванием в равенстве f(t, x, x′) = f[t, xk(t), xk(t)]+ a0(t)y + a1(t)y′ + O(|y|2 + |y′|2) остаточного члена. Линейную краевую задачу (17)(18) решают каким-либо приближенным методом или, если удается, аналитически. При достаточно общих предположениях последовательность {xk} сходится к точному решению задачи (1)(2) со скоростью геометрической прогрессии.

И, наконец, третью группу приближенных методов решения краевых задач образуют так называемые методы разложения или проекционные методы. Их суть проста: неизвестную функцию раскладывают в функциональный ряд по выбранной из тех или иных соображений системе базисных функций Z = {zi}i=0:

x(t) =

i = 0
αi zi(t). 
(19)

Например, часто в качестве базисных функций берут степенные функции Z = {ti}i=0 или тригонометрические Z = {cos ix, sin ix}i=0. Приближенным решением задачи (1)(2) считают конечную сумму ряда (19) xk(t) = ki=0αizi(t), в которой коэффициенты αi подобраны так, чтобы функция xk была в том или ином смысле приближенным решением краевой задачи (1)(2).

Например, в методе коллокаций αi подбираются так, чтобы функция xk удовлетворяла краевым условиям (2) (это дает два уравнения на αi) и в k – 2 заранее выбранных фиксированных точках отрезка [0, T], называемых точками коллокации, удовлетворяла уравнению (1) (это дает еще k – 2 уравнения).

А в методе Галеркина эти k – 2 уравнения получают из следующих соображений. В пространстве функций, которому принадлежат решения краевой задачи, выбирают ортогональный базис и требуют, чтобы невязка x′′k(t) – f[t, xk(t), xk(t)] была ортогональна первым k – 2 функциям базиса (если бы невязка была ортогональна всем элементам базиса, то она равнялась бы нулю, т. е. функция xk была бы точным решением задачи (1)(2)).

Литературные указания. Приближенные методы решения краевых задач описаны во многих учебниках и монографиях по методам вычислений, напр., [Бахвалов, Годунов — Рябенький, Марчук, Самарский, Современные численные методы...].

Задачи. О34.7. Допустим решение x(t, α) в методе стрельбы для задачи (11)(12) строится методом Эйлера, а уравнение (5) решается методом деления пополам с точностью Cτ. Предположим, что задача (11)(12) однозначно разрешима при любой непрерывной функции φ. Исследуйте сходимость метода стрельбы в этих условиях.

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

[p(t)x′]′ – q(t)x = φ(t),    t ∈ [0, T]

с краевыми условиями (7)(8).

О34.9. Для краевой задачи

x′′ + a1(t)x′ + a0(t)x = φ(t),

x(0) = x0,    x(T) = x1

рассмотрим разностную схему

{
yi+1 – 2yi + yi – 1
τ2
  + a1 yi+1yi
  + a0(ti) yi – φ(ti),   если i = 1, ..., k
yix0,   если i = 0
yix1,   если i = k
} = 0.
(20)

Пусть a0, a1 и φ дважды непрерывно дифференцируемы. Покажите, что (20) аппроксимирует данную краевую задачу на решении со вторым порядком точности.

О34.10. Найдите решение разностной схемы (13) при a0(t) ≡ a0 = const, φ(t) ≡ 0. Исследуйте его поведение при τ → 0. Сравните с решением соответствующей дифференциальной задачи.

О34.11. Аналогичные вопросы для схемы (20) (в предположении постоянства коэффициентов).

О34.12. Взяв в качестве базисных функций набор {sin(πit/T)}i=1, а в качестве точек коллокации точки {iτ}ki=1 (τ = T/(k+1)), выпишите уравнения метода коллокации для задачи (11)(12) с однородными граничными условиями (x0 = x1 = 0).

О34.13. Исследуйте разрешимость полученной системы уравнений (для простоты, на первом этапе можно считать, что a0(t) ≡ a0 = const, а k = 2 или k = 3).

О34.14. Аналогичные задачам О34.12 и О34.13 вопросы в случае, когда {zi}i=1= {ti(Tt)}i=1.

О34.15. Пусть {zi}i=1= {sin(2πit/T)}i=1. Рассмотрим метод Галеркина для краевой задачи (11)(12) с однородными краевыми условиями. Под ортогональностью функций φ и ψ будем понимать равенство нулю скалярного произведения (x, y) = 0Tφ(s)ψ(s) ds. Выпишите уравнения на коэффициенты αi метода Галеркина.

О34.16. Исследуйте разрешимость полученной системы уравнений.


File based on translation from TEX by TTH, version 2.32.
Created 25 Mar 2000, 18:07.
Last modified 3 May 2002.