ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4690
Скачиваний: 6
Лекция 9
76
арифметических операций (для числа с плавающей запятой одинарной
точности
t = 26, для двойной: t = 52) g(A) = max
k
max
i,j
|a
(k)
ij
|
max
i,j
|a
ij
|
, где
k —
номер шага на этапе прямого хода метода исключений. (Таким образом,
величина
g(A) показывает, насколько могут возрасти пересчитываемые
элементы матрицы на стадии приведения её к треугольному виду. Отсюда
её название — коэффициент роста.)
Привлекая далее (9.5), получаем оценку ошибок решения системы (9.2)
за счёт погрешностей вычислений:
kδxk
kxk
≈ µ
A
ng(A)p
−t
.
(9.6)
Если, например, решается система из
10
3
уравнений и
µ
A
≈ 1, g(A) ≈ 1,
то при счёте c двойной точностью (
p = 2, t = 52) нельзя рассчитывать на
точность лучшую, нежели
kδxk
kxk
∼ n · 2
−52
∼ n · 10
−15
|
n=10
3
∼ 10
−12
. Если
при этом
µ
A
≈ 10
12
, то может произойти полная потеря точности.
З а м е ч а н и е . Плохо обусловленные СЛАУ вызывают определённые
трудности при решении. Из (9.5) следует, что решение их сильно зависит
от ошибок входных данных, а из (9.6) вытекает, что даже при отсутствии
ошибок во входных величинах может произойти значительная (если не
полная) потеря точности на стадии вычислений по методу Гаусса за счёт
погрешностей округлений.
1.9.5
Итерационные методы решения СЛАУ
По-прежнему будем рассматривать системы вида
Ax = f . Различные ва-
рианты итерационных методов связаны с переходом к эквивалентной си-
стеме
Ax = f
⇔
x
= P x + g.
Берём некоторое начальное приближение x
(0)
и очевидным образом
строим итерационный процесс x
(k)
= P x
(k
−1)
+ g. Здесь x
(k)
обозначает
k-е по счёту приближение к искомому вектору x.
Лекция 9
77
Условия сходимости метода последовательных приближений формули-
руются в следующих теоремах.
Теорема 9.2. Для сходимости итераций
x
(k)
= P x
(k
−1)
+ g, где x
(0)
задано
(9.7)
к решению системы
x
= P x + g
(9.8)
достаточно, чтобы в какой-либо норме выполнялось условие
||P ||
6
q < 1.
Тогда независимо от выбора x
(0)
||x
(k)
− x
∗
||
6
q
k
||x
(0)
− x
∗
||,
где x
∗
— точное решение.
Доказательство. Подстановка точного решения в (9.8) обращает послед-
нее в тождество
x
∗
= P x
∗
+ g.
Вычитая его из (9.7), получим
x
(k)
− x
∗
= P (x
(k
−1)
− x
∗
),
где
(x
(k)
− x) — вектор погрешности (или просто погрешность k-го реше-
ния).
Оценивая погрешность по какой-либо норме (с которой согласована нор-
ма матрицы, фигурирующая в условии теоремы), получаем
||x
(k)
− x
∗
||
6
||P || · ||x
(k
−1)
− x
∗
||
6
6
q
||x
(k
−1)
− x
∗
||
6
. . .
6
q
k
||x
(0)
− x
∗
||.
Очевидно, что при
q < 1 lim
k
→∞
x
(k)
= x
∗
.
Теорема 9.3. (без доказательства) Для сходимости итераций (9.7) к
решению системы (9.8) необходимо и достаточно, чтобы все собствен-
ные значения матрицы
P по абсолютной величине были меньше едини-
цы.
Лекция 9
78
Выбор метода
Теперь самое время осознать, зачем, собственно, нуж-
ны итерационные методы, если мы умеем вычислять решение, пользуясь,
например, какой-либо модификацией метода Гаусса. Вопрос становится
ясным, если оценить эффективность различных подходов с точки зрения
вычислительных затрат.
Метод Гаусса (в простейшей интерпретации), как мы видели, при
n
1
требует выполнения приблизительно
2
3
n
3
арифметических операций. Ме-
тод итераций x
(k)
= P x
(k
−1)
+ g реализуется приблизительно за (2n
2
)K
операций (
2n
2
умножений и сложений связано с умножением матрицы
P
на вектор x
(k
−1)
,
K — число приближений). Если допустимая погрешность
достигается при
K < n/3, то метод итераций становится предпочтитель-
ней. В задачах, с которыми практически приходится иметь дело, зачастую
K
n.
Кроме того, итерационные методы могут оказаться предпочтительней с
точки зрения устойчивости вычислений, в смысле влияния вычислитель-
ных погрешностей на результаты расчетов.
Метод Якоби.
Запишем каждое уравнение системы
Ax = f в виде, раз-
решённом относительно неизвестного с коэффициентом на главной диаго-
нали матрицы
A:
x
m
=
1
a
mm
(f
m
− a
m1
x
1
− a
m,m
−1
x
m
−1
− a
m,m+1
x
m+1
− . . . − a
mn
x
n
),
m = 1, 2, . . . , n.
То есть мы переписали
Ax = f в виде x = P x + g с матрицей
P =
−
0
a
12
a
11
a
13
a
11
· · ·
a
1n
a
11
a
21
a
22
0
a
23
a
22
· · ·
a
2n
a
22
...
...
a
n1
a
nn
a
n2
a
nn
a
n3
a
nn
· · ·
0
.
Лекция 9
79
Если ввести в рассмотрение диагональную матрицу
D =
a
11
0
a
22
. . .
0
a
nn
,
то
P =
−D
−1
(A
− D), g = D
−1
f .
Итерационный процесс (9.7) с определённой таким образом матрицей
P
называется методом Якоби. Фактически вычисления проводятся по фор-
мулам
x
(k)
m
=
1
a
mm
(f
m
− a
m1
x
(k
−1)
1
− . . . − a
m,m
−1
x
(k
−1)
m
−1
−
− a
m,m+1
x
(k
−1)
m+1
− . . . − a
mn
x
(k
−1)
n
), m = 1, 2, . . . , n. (9.9)
Для сходимости метода Якоби достаточно, чтобы для исходной матри-
цы
A имело место диагональное преобладание, т.е. чтобы коэффициенты
исходных уравнений удовлетворяли условиям
|a
ii
| >
X
j
6=i
|a
ij
| для всех i.
В самом деле, тогда условие теоремы 9.2 выполнено для нормы
||P ||
∞
:
||P ||
∞
= max
i
X
j
6=i
|a
ij
|
|a
ii
|
= max
i
P
j
6=i
|a
ji
|
|a
ii
|
< 1.
Метод Зейделя.
Этот метод отличается от метода Якоби только тем, что при вычислении
k-го приближения m-й компоненты используются уже вычисленные k-е
Лекция 9
80
приближения предыдущих (1-й, 2-й, . . . ,
(m
− 1)-й) компонент:
x
(k)
1
=
1
a
11
f
1
− a
12
x
(k
−1)
2
− a
13
x
(k
−1)
3
− . . . − a
1n
x
(k
−1)
n
,
x
(k)
2
=
1
a
22
f
2
− a
21
x
(k)
1
− a
23
x
(k
−1)
3
− . . . − a
2n
x
(k
−1)
n
,
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
x
(k)
m
=
1
a
mm
f
m
− a
m1
x
(k)
1
− a
m2
x
(k)
2
− . . . − a
mm
−1
x
(k)
m
−1
−
−a
mm+1
x
(k
−1)
m+1
− . . . − a
mn
x
(k
−1)
n
,
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Если представить матрицу
A в виде суммы A = A
−
+ D + A
+
(
A
−
—
нижняя треугольная,
A
+
— верхняя треугольная и
D — диагональная
матрицы с элементами исходной матрицы
A), то методу Зейделя соответ-
ствует матрица
P =
−(A − A
+
)
−1
A
−
=
−(A
−
+ D)
−1
A
−
.
Можно доказать, что метод Зейделя гарантировано сходится, если:
• выполнено условие диагонального преобладания матрицы A; или
• матрица A является симметричной и положительно определенной.
В одинаковых условиях (при наличии диагонального преобладания) ме-
тод Зейделя сходится примерно в два раза быстрее метода Якоби.
Однопараметрический метод итераций
Перепишем
Ax = f в виде x = x
− τ(Ax − f) = (E − τA)x + τf, где τ —
пока неопределенный параметр.
Мы фактически привели
Ax = f к форме x = P x + g, где P = E
− τA
и g
= τ f . Итерационная последовательность имеет вид
x
(k)
= P x
(k
−1)
+ g,
(9.10)
Далее будем предполагать, что матрица исходной системы симметрич-
на и положительно определена (т.е.
A
>
= A и A > 0) и что известны