Методическое пособие для практических и лабораторных работ по курсу «Численные методы»

149
k
k
g
b
A
B
b
A
r r
r
+
=
−
−
1 1

Отсюда
b
C
b
A
B
E
g
k
k
k
r r
r
=
−
=
−
1
)
(
, где через
k
C обозначили матрицу
1
)
(
−
−
A
B
E
k
. Следовательно, линейный одношаговый итерационный метод для решения системы (7.1) имеет вид
b
C
x
B
x
k
k
k
k
r r
r
+
=
+
1
,
E
B
A
C
k
k
=
+
,
,...
1
,
0
=
k
(7.3)
Первый вопрос, который возникает при применении методов последовательного приближения, это вопрос сходимости.
Выразим матрицу
k
C из второго соотношения в (7.3)
1
)
(
−
−
=
A
B
E
C
k
k
и подставим в первое уравнение (7.3). Получаем
b
A
B
b
A
x
B
x
k
k
k
k
r r
r r
1 1
1
−
−
+
−
+
=

Вычитая из этого равенства почленно точное решение
b
A
x
r r
1
−
=
, имеем
)
(
1 1
b
A
x
B
x
x
k
k
k
r r
r r
−
+
−
=
−

Полагая здесь последовательно
m
k
,...,
1
,
0
=
, находим, что
)
(
1 0
0 1
1
b
A
x
B
B
B
x
x
m
m
k
r r
r r
−
−
+
−
=
−

Отсюда
b
A
x
B
x
x
m
i
i
k
r r
r r
1 0
0 1
−
=
+
−




≤
−
∏

Тем самым мы доказали теорему:

150
Теорема 1. Для сходимости нестационарного одношагового
итерационного метода (7.3) достаточно, чтобы нормы всех матриц
i
B были
меньше единицы:
1
<
i
B
,
m
i
,...,
1
,
0
=
.
Рассмотрим одношаговый стационарный метод
b
C
x
B
x
k
k
r r
r
+
=
+
1
,
E
B
CA
=
+
,
,...
1
,
0
=
k
(7.4)
В этом случае справедлива следующая теорема.
Теорема 2. Для сходимости стационарного метода (7.4) необходимо и
достаточно, чтобы все собственные числа матрицы B по модулю были
меньше единицы.
Доказательство. Последовательно полагая в (7.4)
m
k
,...,
1
,
0
=
, получаем
b
C
E
B
B
B
x
B
x
m
m
m
k
r r
r
)
(
1 0
1 1
+
+
+
+
+
=
+
+
+

Отсюда следует, что для сходимости метода (7.4) необходимо и достаточно, чтобы сходился матричный ряд
...
+
+
+
+
k
B
B
E
Известно, что для сходимости этого матричного ряда, необходимо и достаточно, чтобы все собственные числа матрицы B по модулю были меньше единицы. Теорема доказана.
Вспоминая свойства собственных чисел матрицы и Теорему 1, видим, что из Теоремы 2 вытекает следствие
Следствие 1. Для сходимости стационарного метода (7.4)
достаточно, чтобы какая-либо из норм матрицы B была меньше единицы.
Пусть имеем какой-либо сходящийся итерационный метод (7.4).
Матрица B зафиксирована, ее норма меньше единицы. Для организации расчетов нужно задать начальное приближение
0
xr , точность расчетов – малое
0
>
ε
и критерий окончания расчетов. Как видно их доказанных теорем, если метод сходится, то
0
xr выбирается произвольно. Что брать в качестве критерия окончания итерационного процесса? Пусть
b
C
x
B
x
k
k
r r
r
+
=
+
1

В пределе получаем
b
C
x
B
x
r r
r
+
=

Вычитая одно равенство из другого, имеем
)
(
)
(
)
(
1 1
1 1
+
+
+
+
−
+
−
=
±
−
=
−
k
k
k
k
k
k
x
x
B
x
x
B
x
B
x
x
B
x
x
r r
r s
r r
r r
r
,

151
откуда находим, что
k
k
k
x
x
B
B
x
x
r r
r r
−
−
≤
−
+
+
1 1
1

Следовательно, если требуется найти приближенное решение отстоящее от точного на малое
0
>
ε
, то в качестве критерия окончания расчетов нужно взять неравенство
ε
≤
−
−
+
k
k
x
x
B
B
r r
1 1

Для нестационарных итерационных методов условием окончания расчетов часто выбирают неравенство
ε
≤
−
+
k
k
x
x
r r
1

Выше мы получили, что
)
(
1
x
x
B
x
x
k
k
r r
r r
−
=
−
+
, отсюда
)
(
0 1
x
x
B
x
x
k
k
r r
r r
−
=
−
+
, следовательно, справедлива оценка
x
x
B
x
x
k
k
k
r r
r r
−
≤
−
+
0 1
(7.5)
Пусть
1
<
≤
q
B
. Из (7.5) получаем, что для того, чтобы начальная погрешность
x
x
r r
−
0
уменьшилась в
ε
1
необходимо провести
)
1
ln(
)
1
ln(
)
(
0
q
k
k
ε
ε ≥
>
итераций. Числом
)
(
0
ε
k
можно характеризовать скорость сходимости итерационного метода. Целая часть числа
)
(
0
ε
k
называют
минимальным числом итераций, необходимым для получения заданной точности
ε
. Выражение
)
1
ln( q называют скоростью сходимости
итерационного метода. Скорость сходимости целиком определяется

152
свойствами матрицы B – матрицы перехода от итерации к итерации и не зависит ни от начального приближения
0
xr , ни от задаваемой точности
ε
Чтобы построить итерационный метод, систему
b
x
A
r r
=
предварительно преобразовывают к виду
g
x
B
x
r r
r
+
=
(7.6)
Операция приведения системы к виду удобному для итераций (т.е. к виду (7.6)), вообще говоря, не простая и требует специальных знаний, а также существенного использования специфики системы. Один из способов перехода к виду (7.6) заключается в следующем. Исходную систему записывают в эквивалентном виде
)
(
b
x
A
C
x
x
r r
r r
−
−
=
. Выбор матрицы
C
конкретизирует итерационный метод.
Если в качестве матрицы C взять диагональную матрицу
1
−
D , где
















=
−
−
nn
n
n
a
a
a
a
D
0 0
0 0
0 0
0
...
0 0
0 0
0 0
0
)
1
)(
1
(
22 11
, то получаем метод Якоби
∑
∑
−
=
+
=
+
+
−
−
=
1 1
1
)
(
)
(
)
(
1
i
j
n
i
j
ii
i
j
k
ii
ij
j
k
ii
ij
i
k
a
b
x
a
a
x
a
a
x
,
n
i
,...,
1
=
,
,...
1
,
0
=
k
(7.7)
Матрица B в методе Якоби имеет вид


















−
−
−
−
−
−
−
−
−
=
0
...
...
...
0 0
3 2
1 22 2
22 31 22 21 11 1
11 13 11 12
nn
n
nn
n
nn
n
n
n
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
B
(7.8)
Отсюда и из Следствия 1. вытекает следующая теорема.
Теорема 3. Если A – матрица с диагональным преобладанием, то
метод Якоби сходится.

153
Небольшая модификация метода Якоби приводит к методу Гаусса-
Зейделя
∑
∑
−
=
+
=
+
+
+
−
−
=
1 1
1
)
(
)
(
1
)
(
1
i
j
n
i
j
ii
i
j
k
ii
ij
j
k
ii
ij
i
k
a
b
x
a
a
x
a
a
x
,
n
i
,...,
1
=
,
,...
1
,
0
=
k
(7.9)
Идея, заложенная в методе (7.9) понятна: только что насчитанную компоненту
)
(
1
j
k
x
+
(предполагается, что она ближе к точной
)
( j
x по сравнению с
)
( j
k
x ) сразу же включаем в расчеты для вычисления
)
1
(
1
+
+
j
k
x
компоненты.
Представим матрицу A в виде суммы трех матриц
2 1
A
D
A
A
+
+
=
, где
















=
0
...
.
.
0 0
0 0
0 0
0 0
0 3
2 1
32 31 21 1
n
n
n
a
a
a
a
a
a
A
,
















=
0 0
0 0
...
.
...
0 0
0 0
0 0
3 2
23 1
13 12 2
n
n
n
a
a
a
a
a
a
A
, матрицу D мы ввели ранее.
Введем обозначения
1 1
1
A
D
B
−
=
,
2 1
2
A
D
B
−
=
. Для метода Гаусса-Зейделя справедливы утверждения [4]:
Теорема 4. Пусть
1 1
1 2
<
≤
−
q
B
B
. Тогда метод Гаусса-Зейделя
сходится при любом начальном приближении
0
xr и справедлива оценка
0
x
x
q
x
x
k
k
r r
r r
−
≤
−
для любого
N
k
∈
.
Теорема 5. Пусть
1
<
B
, где B – матрица (7.8). Тогда для метода
Гаусса-Зейделя справедлива оценка
1 2
1
+
−
−
≤
−
k
k
k
x
x
B
B
x
x
r r
r r
для любого
N
k
∈
.
Замечание. Неверно, что если метод Якоби сходится, то метод Гаусса-
Зейделя сходится еще лучше. Существуют примеры, для которых метод
Якоби сходится, а метод Гаусса-Зейделя расходится и наоборот. Дело в том, что эти методы ориентированы на решение различных классов систем: метод
Якоби – на системы с матрицами, близкими к диагональным, а метод Гаусса-
Зейделя – на системы с матрицами, близкими к нижне-треугольным. Поэтому можно ожидать хорошую сходимость метода Гаусса-Зейделя для систем с

154
«почти» нижне-треугольными матрицами
A . Однако этот признак носит качественный характер и не является условием сходимости. Так, например, метод Гаусса-Зейделя не сходится в случае
8 2
1 10 4
1 50 25 2
A




= 





, несмотря на ее
«почти» нижне-треугольный вид.
Это объяснимо. Метод Гаусса-Зейделя можно переписать в виде
(
)
(
)
1 1
1 1
2 1
k
k
x
D
A
A x
D
A
b
−
−
+
= −
+
+
+
r r
r
Собственные числа матрицы
(
)
1 1
2
D
A
A
−
−
+
следующие
(
)
2.2853; 0.6845;0.0
−
−
, т.е. одно из них по модулю больше единицы.
Справедливо только утверждение [3]: если A – симметричная и
положительно определенная матрица с диагональным преобладанием, то
методы Якоби и Гаусса-Зейделя сходятся, причем второй не медленнее, чем
первый.
Определение 2. Канонической формой одношагового итерационного метода решения системы (3.1) называется его запись в виде
1 1
1
k
k
k
k
k
x
x
B
Ax
b
τ
+
+
+
−
+
=
r r
r r
,
0,1,...
k
=
(7.10)
Здесь
1
k
B
+
– матрица, задающая тот или иной итерационный метод,
1
k
τ
+
– итерационный параметр. Итерационный метод называется стационарным, если
1
k
B
B
+
=
и
1
k
τ
τ
+
=
не зависят от номера итерации и нестационарным в противном случае. Очевидно, что итерационный метод, записанный в канонической форме всегда можно переписать в виде (7.2).
Из канонической формы (7.10) видно, что если итерационных метод сходится, то он сходится к точному решению исходной системы.
Для итерационных методов (7.10) в случае симметричной и положительно определенной матрицы доказан ряд теорем сходимости, которые мы рассмотрим в следующей лекции.

155
Лекция 8. Метод простой итерации. Сходимость. Метод релаксации. Сходимость. Метод наискорейшего спуска. Метод минимальных невязок. Метод сопряженных градиентов.
Рассмотрим явный стационарный итерационный метод, записанный в канонической форме – метод простой итерации
1
k
k
k
x
x
Ax
b
τ
+
−
+
=
r r
r r
(8.1)
Вычитая из (8.1) почленно исходную систему Ax b
=
r r
, получаем, что вектор погрешности
k
k
z
x
x
=
−
r r r
удовлетворяет задаче
1 0
k
k
k
z
z
Az
τ
+
−
+
=
r r
r
(8.2)
Отсюда для метода простой итерации имеем
1
(
)
k
k
k
z
E
A z
Sz
τ
+
=
−
=
r r
r
,
(8.3) где через S
E
A
τ
= −
обозначили матрицу перехода от итерации к итерации.
Обозначим через
i
µ
собственные числа матрицы
S . Напомним, что для сходимости стационарного метода (8.2) (а тем самым и метода простой итерации (8.1)) достаточно, чтобы какая-либо из норм матрицы S была меньше единицы.
Пусть
0
T
A
A
=
>
и min max
E
A
E
λ
λ
≤ ≤
,
(8.4) где min
λ
– минимальное, а max
λ
– максимальное собственные числа матрицы
A . Так как
T
A
A
=
, то и
T
S
S
=
, поэтому
2
max max 1
i
i
i
i
S
µ
τλ
=
=
−
, где
i
λ
– собственные числа матрицы A . В силу (8.4) условие сходимости метода простой итерации
1
i
µ <
выполняется при

156
max
2 0
τ
λ
< <
(8.5)
Очевидно, что сходимость тем быстрее, чем меньше
2
S . Задача минимизации
2
S сводится к отысканию такого
0
τ >
, при котором достигается
0
min max 1
i
i
τ
τλ
>
−
(8.6)
Исследование функции 1
τλ
−
на отрезке
[
]
min max
,
λ
λ
показывает, что результат (8.6) достигается при min max
2
опт
τ τ
λ
λ
=
=
+
(8.7)
При этом наименьшее значение
2
S есть max min
2,min max min
1 1
S
λ
λ
ξ
λ
λ
ξ
−
−
=
=
+
+
, min max
λ
ξ
λ
=
(8.8)
Полученные результаты объединим в теореме.
Теорема 1. Пусть
0
T
A
A
=
>
,
min
λ
и
max
λ
– минимальное и
максимальное собственные числа матрицы A. Тогда метод простой
итерации (8.1) сходится при
max
2
τ
λ
<
и наибольшая скорость сходимости
достигается при
min max
2
опт
τ τ
λ
λ
=
=
+
.
Рассмотрим явный нестационарный итерационный метод
b
x
A
x
x
k
k
k
k
r r
r r
=
+
−
+
+
+
1 1
1
τ
(8.9)
Считаем, что A – симметричная, положительно определенная матрица.
Последовательность итерационных параметров будем выбирать, исходя из условий минимума функционалов, связанных с такими характеристиками, как вектор невязки
b
x
A
r
k
k
r r
r
−
=
+
+
1 1
или вектор погрешности
x
x
z
k
k
r r
r
−
=
+
+
1 1
. В частности рассмотрим функционал

157 2
2 2
2
)
,
(
)
(
r
b
x
A
b
x
A
b
x
A
x
Ф
r r
r r
r r
r
=
−
=
−
−
=

Определение 1. Методом минимальных невязок называется метод, в котором итерационный параметр
1
+
k
τ
выбирается из условий минимизации
1
+
k
rr
, при известной
k
rr .
Из (8.9) имеем
k
k
k
k
r
x
x
r r
r
1 1
+
+
−
=
τ
, отсюда
k
k
k
k
r
A
r
r
r r
r
1 1
+
+
−
=
τ

Поэтому
2 2
2 1
1 2
2 2
2 1
1
)
,
(
2
)
(
k
k
k
k
k
k
k
k
r
A
r
A
r
r
r
x
Ф
r r
r r
r r
+
+
+
+
+
−
=
=
τ
τ

Следовательно, минимум
1
+
k
rr достигается при
)
,
(
)
,
(
1
k
k
k
k
k
r
A
r
A
r
A
r
r r
r r
=
+
τ
(8.10)
Итак, алгоритм метода минимальных невязок следующий. Пусть
k
xr найдено, тогда очередное приближение
1
+
k
xr вычисляют по формулам
k
k
k
k
r
x
x
r r
r
1 1
+
+
−
=
τ
,
b
x
A
r
k
k
r r
r
−
=
,
(
)
(
)
k
k
k
k
k
r
A
r
A
r
A
r
r r
r r
,
,
1
=
+
τ
,
,...
2
,
1
,
0
=
k
(8.11)

Определение 2. Методом скорейшего спуска называется метод, в котором итерационный параметр
1
+
k
τ
выбирается из условий минимальности
A -нормы вектора погрешности
1
+
k
zr
Из (8.9)
0 1
1
=
+
−
+
+
k
k
k
k
z
A
z
z
r r
r
τ
,

158
отсюда
k
k
k
k
z
A
z
z
r r
r
1 1
+
+
−
=
τ

Поэтому
)
,
(
)
,
(
2 2
2 1
1 2
2 1
k
k
k
k
k
k
A
k
A
k
z
A
z
A
z
A
z
A
z
z
r r
r r
r r
+
+
+
+
−
=
τ
τ

Следовательно, минимум
2 1 A
k
z
+
r достигается при
)
,
(
)
,
(
2 1
k
k
k
k
k
z
A
z
A
z
A
z
A
r r
r r
=
+
τ

Поскольку
k
zr нам неизвестен, но
r
z
A
k
r r
=
, предыдущую формулу перепишем в виде
(
)
(
)
k
k
k
k
k
r
A
r
r
r
r r
r r
,
,
1
=
+
τ
Итак, расчетные формулы метода скорейшего спуска следующие.
Пусть
k
xr найдено, тогда очередное приближение
1
+
k
xr вычисляют по формулам
k
k
k
k
r
x
x
r r
r
1 1
+
+
−
=
τ
,
b
x
A
r
k
k
r r
r
−
=
,
(
)
(
)
k
k
k
k
k
r
A
r
r
r
r r
r r
,
,
1
=
+
τ
,
,...
2
,
1
,
0
=
k
(8.12)

Видим, что методы минимальных невязок и скорейшего спуска отличаются лишь выбором итерационных параметров.
Докажем сходимость этих методов. В методе минимальных невязок
2 2
1 2
2 1
1
)
(
)
(
k
k
k
k
r
A
E
r
x
Ф
r r
r
+
+
+
−
=
=
τ
(8.13)
И последовательность
1
+
k
τ
из (8.10) минимизирует правую часть в (8.13).
Поэтому при любом
1
+
≠
k
τ
τ
будем иметь
2 2
1
)
(
)
(
k
k
r
A
E
x
Ф
r r
τ
−
≤
+

Выберем в качестве
τ
оптимальный параметр в методе простой итерации

159
min max
2
опт
τ τ
λ
λ
=
=
+
.

Тогда
2 2
2 2
2 1
)
(
k
k
опт
k
опт
k
r
r
A
E
r
A
E
r
r r
r r
ρ
τ
τ
=
−
≤
−
≤
+
, где
)
(
)
(
)
(
)
(
min max min max
A
A
A
A
λ
λ
λ
λ
ρ
+
−
=
Тем самым доказана

Скачать 1.29 Mb.

Поделитесь с Вашими друзьями: