ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4695
Скачиваний: 6
Метод Прогонки.
86
нуль. А именно, достаточно положить
α
j+1
=
b
j
c
j
− α
j
a
j
,
β
j+1
=
a
j
β
j
+ f
j
c
j
− α
j
a
j
,
j = 1, 2, . . . , n
− 1.
(10.3)
Для того, чтобы применять последние соотношения нужно задать началь-
ные значения
α
1
,
β
1
. С одной стороны
y
0
= α
1
y
1
+ β
1
, с другой стороны
по условию задано, что
y
0
=
κ
1
y
1
+ µ
1
. Таким образом, получаем
α
1
=
κ
1
,
β
1
= µ
1
.
(10.4)
Нахождение коэффициентов
α
j+1
,
β
j+1
по формулам (10.3) и (10.4) на-
зывается прямой прогонкой. После того как прогоночные коэффициенты
α
j+1
,
β
j+1
,
j = 0, 1, . . . n
− 1, найдены, решение системы (10.1) находится
по рекуррентной формуле (10.2), начиная с
j = n
− 1. Для начала счёта
по этой формуле требуется знать
y
n
, которое определяется из уравнений
y
n
=
κ
2
y
n
−1
+ µ
2
,
y
n
−1
= α
n
y
n
+ β
n
и равно
(
κ
2
β
n
+ µ
2
)/(1
−
κ
2
α
n
). Нахождение y
j
по формулам
y
j
= α
j+1
y
j+1
+ β
j+1
,
j = n
− 1, n − 2, . . . , 0,
y
n
=
κ
2
β
n
+ µ
2
1
−
κ
2
α
n
(10.5)
называется обратной прогонкой.
Метод прогонки можно применять, если знаменатели выражений (10.3),
(10.5) не обращаются в нуль. Достаточные для этого условия перечислены
в следующих двух теоремах.
Теорема 10.1 (достаточное условие применимости прогонки). Пусть
a
j
6= 0, b
j
6= 0,
|c
j
|
>
|a
j
| + |b
j
|, j = 1, 2, . . . , n − 1 (диагональное преобладание), (10.6)
|
κ
1
|
6
1,
|
κ
2
| < 1,
(10.7)
тогда метод прогонки применим.
Метод Прогонки.
87
Доказательство. Сначала докажем по индукции, что при условиях тео-
ремы
|α
j
|
6
1, j = 1, . . . , n
− 1. Базис индукции: α
1
=
κ
1
и
|
κ
1
|
6
1,
следовательно,
|α
1
|
6
1. Индуктивный переход: пусть
|α
j
|
6
1, докажем,
что
|α
j+1
|
6
1. Из оценок
|c
j
− α
j
a
j
|
>
| |c
j
| − |α
j
| |a
j
| |
|α
j
| 6 1
>
| |c
j
| − |a
j
| |
>
|b
j
| > 0,
т.е. знаменатели выражений (10.3) не обращается в нуль. Более того,
|α
j+1
| =
|b
j
|
|c
j
− α
j
a
j
|
6
1.
Следовательно,
|α
j
|
6
1, j = 1, 2, . . . , n. Далее, учитывая условие теоремы
|
κ
2
| < 1 и только что доказанное |α
n
|
6
1, имеем
|1 −
κ
2
α
n
|
>
1
− |
κ
2
| |α
n
|
>
1
− |
κ
2
| > 0,
т.е. не обращается в нуль и знаменатель в выражении для
y
n
.
Теорема 10.2 (альтернативный вариант). Пусть
a
j
6= 0, b
j
6= 0, |c
j
| >
|a
j
| + |b
j
|, j = 1, 2, . . . , n − 1, |
κ
1
|
6
1,
|
κ
2
|
6
1, тогда метод прогонки
применим.
Доказательство. Действуем аналогично предыдущему доказательству. В
данном случае из предположения
|α
j
|
6
1 следует
|c
j
− α
j
a
j
|
>
| |c
j
| − |a
j
| | > |b
j
|, |α
j+1
| < 1,
т.е. все прогоночные коэффициенты, начиная со второго, по модулю строго
меньше единицы. При этом
|1 −
κ
2
α
n
|
>
1
− |
κ
2
| |α
n
|
>
1
− |α
n
| > 0.
Количество арифметических операций
у метода прогонки оцени-
вается
∼ 8n. Это очень мало сравнительно с другими методами решения
СЛАУ. Причина кроется в том, что матрица
A содержит много нулевых
элементов.
7
Использованы неравенства «треугольника»: для любых
a, b
∈ R справедливо, что
|a| + |b| > |a + b| и |a − b| > | |a| − |b| |.
Метод Прогонки.
88
Устойчивость метода прогонки к погрешностям входных дан-
ных.
Если выполняются условия теоремы 10.1 или теоремы 10.2, то, как
было доказано,
|α
j
|
6
1, j = 1, 2, . . . , n. Пусть на каком-либо шаге вычис-
лений была внесена погрешность. Тогда эта погрешность не будет возрас-
тать при переходе к следующим шагам. Действительно, пусть в формулах
j = j
0
+ 1 вместо y
j
0
+1
вычислена величина
e
y
j
0
+1
=
y
j
0
+1
+ δ
j
0
+1
. Тогда на следующем шаге вычислений, т.е. при
j = j
0
, вместо
y
j
0
= α
j
0
+1
y
j
0
+1
+ β
j
0
+1
получим величину
e
y
j
0
= α
j
0
+1
(y
j
0
+1
+ δ
j
0
+1
) + β
j
0
+1
и погрешность окажется равной
δ
j
0
=
e
y
j
0
− y
j
0
= α
j
0
+1
δ
j
0
+1
.
Отсюда получим, что
|δ
j
0
|
6
|α
j
0
+1
| |δ
j
0
+1
|
6
|δ
j
0
+1
|, т.е. погрешность не
возрастает.
Численное решение дифференциальных уравнений
89
1.11
Численное решение дифференциальных уравнений
Будем рассматривать обыкновенные дифференциальные уравнения
F (x, u(x), u
0
(x), . . . , u
(n)
) = 0.
(11.1)
Как известно, в общем случае такие уравнения имеют бесконечно мно-
го решений. В приложениях требуется выделить одно из этих решений.
Поэтому, часто уравнение (11.1) рассматривают в сочетании с дополни-
тельными ограничивающими условиями. Рассмотрим основные типы до-
полнительных условий, с которыми мы будем дальше работать.
1. Задача Коши для дифференциального уравнения первого порядка
(
u
0
= f (x, u), x
∈ [a, b],
u(x
a
) = u
a
.
(11.2)
2. Краевая задача для линейного дифференциального уравнения второго
порядка
u
00
+ g(x)u
0
+ h(x)u = f (x), x
∈ [a, b],
α
1
u
0
(a) + β
1
u(a) = u
a
,
α
2
u
0
(b) + β
2
u(b) = u
b
.
(11.3)
Граничные условия принято разделять на следующие типы: (а) пер-
вого рода, если
α
i
= 0, i = 1, 2; (б) второго рода, если β
i
= 0, i = 1, 2;
(в) третьего рода, если
α
i
и
β
i
одновременно отличны от нуля.
При исследовании численных методов для каждой из перечисленных
задач будем заранее предполагать, что решение соответствующей задачи
существует, единственно и обладает необходимыми свойствами гладкости.
Многие методы решения дифференциальных задач сводятся к следу-
ющему. На интересующем нас отрезке
[a, b], на котором требуется найти
численное решение задачи для дифференциального уравнения, вводится
набор точек или сетка
ω =
{x
0
, x
1
, . . . , x
n
}.
В дальнейшем мы всегда будем считать, что расстояние между соседни-
ми узлами сетки
x
k
и
x
k+1
есть константа
h, называемая шагом сетки.
Численное решение дифференциальных уравнений
90
Кроме того полагаем
x
0
= a, x
n
= b. Теперь исходное дифференциальное
уравнение мы будем рассматривать только в узлах сетки
ω
F (x
k
, u(x
k
), u
0
(x
k
), u
00
(x
k
), . . . , u
(p)
(x
k
)) = 0, k = 0, 1, . . . , n.
(11.4)
Для краткости договоримся вместо
u(x
k
) писать u
k
. Теперь осталось пе-
рейти от дифференциального уравнения (11.4) к разностному. Для этого
заменим все вхождения символа
u
k
на
y
k
, а все вхождения символов про-
изводной на соответствующие разностные производные. Например,
u
0
k
→
1
h
(y
k+1
− y
k
) или u
0
k
→
1
2h
(y
k+1
− y
k
−1
),
u
00
k
→
1
h
2
(y
k
−1
− 2y
k
+ y
k+1
).
Переход от символов производной к разностным производным неоднозна-
чен. При выборе той или иной разностной формулы могут сыграть роль
порядок погрешности формулы (например,
O(h) или O(h
2
)), а также чис-
ло соседних узлов, задействованных в формуле (например, два узла
x
k
и
x
k+1
или три узла
x
k
−1
и
x
k+1
).
Решением разностного уравнения будет сеточная функция
y
k
= y(x
k
).
Термин «сеточная» говорит от том, что область определения функции
y(x) есть не весь отрезок [a, b], а только узлы сетки ω. Итак, u(x) и y(x)
есть различные функции, но при определённых условиях можно считать
u
k
≈ y
k
,
k = 0, 1, . . . , n.
При использовании приближённых методов основным является вопрос
о сходимости. Понятие сходимости приближённого метода можно сфор-
мулировать по-разному. Будем рассматривать понятие сходимости при
h
→ 0. Оно означает следующее. Фиксируем точку x и построим последо-
вательность сеток
ω
h
таких, что
h
→ 0 и x
n
= nh = x (при этом, очевидно,
n
→ ∞). Говорят, что численное решение сходится в точке x к точному
решению, если
|y
n
− u(x
n
)
| → 0 при h → 0, x
n
= x.
Численное решение сходится на отрезке
[a, b] к точному решению, если
оно сходится в каждой точке этого отрезка.
Погрешность решения — это числовая характеристика
δ
h
, показыва-
ющая, насколько истинное решение
u(x
k
) дифференциального уравнения