ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 02.08.2019
Просмотров: 4708
Скачиваний: 6
Лекция 9
81
границы спектра матрицы
A (минимальное и максимальное собственные
значения). При этих предположениях мы не только определим диапазон
значений
τ , гарантирующих сходимость, но и найдем оптимальное τ , при
котором величина погрешности приближений убывает с номером прибли-
жения наиболее быстро.
Итак, замечая, что
x
∗
= P x
∗
+ g,
(9.11)
x
∗
— точное решение
Ax = f , и вводя в рассмотрение вектор ошибки k-го
приближения r
(k)
= x
(k)
− x
∗
, получим, вычитая (9.11) из (9.10):
r
(k)
= P r
(k
−1)
.
(9.12)
Собственные значения матрицы
A обозначим через λ
i
, а собственные
значения
P — через µ
i
. Очевидно, что
µ
i
= 1
− τλ.
Найдём Евклидову норму
P . Так как E = E
>
и
A = A
>
, то
P =
E
−τA = E
>
−τA
>
= P
>
. Если
µ
i
— собственное значение матрицы
P , то
µ
2
i
— будет собственным значением матрицы
P
>
P = P
2
. Действительно
из
P x = µx следует, что P
2
x
= µP x = µ
2
x. Для подчинённой нормы
2
справедливо
kP k
2
=
q
max
i
µ
2
i
= max
i
|µ
i
|.
По теореме 9.2 для сходимости итерационного процесса требуется, чтобы
выполнялось
kP k
2
= max
i
|µ
i
|
6
q < 1. Из этой же теоремы следует, что
kr
(k)
k
2
2
6
max
i
µ
2
i
· kr
(k
−1)
k
2
2
.
(9.13)
Таким образом, если
max
i
|µ
i
|
6
q < 1, то погрешность будет убывать с
номером приближения как член геометрической прогрессии со знаменате-
лем
q.
Оптимизация параметра.
В силу (9.13) для быстрого убывания нор-
мы ошибки
kr
(k)
k нужно, чтобы величина max
i
|µ
i
| была как можно мень-
ше. Кроме того для сходимости итерационного процесса необходимо, что-
бы
max
i
|µ
i
|
6
q < 1.
Лекция 9
82
Рис. 9.1: Выбор оптимального значения параметра
τ .
Для удобства введём следующие обозначения
¯
λ = min
i
λ
i
,
Λ = max
i
λ
i
.
На рис. 9.1 в системе координат
λ и µ прямая
µ = 1
− τλ
(9.14)
проходит через точку
(λ, µ) = (0, 1). Так как max
i
|µ
i
| < 1, то параметр τ
может меняться в пределах
0 < τ < 2/Λ. Следовательно, прямая (9.14)
при различных
τ описывает заштрихованную на рис. 9.1 область. Наиболь-
шие отклонения прямой
µ = 1
− τλ от нуля на отрезке ¯λ
6
λ
6
Λ будут
при
λ = ¯
λ или при λ = Λ. Из геометрических соображений очевидно, что
значение
max
i
|µ
i
| = max
i
|1 − τλ
i
| будет достигнуто либо при λ = ¯λ, либо
при
λ = Λ.
Вспомним, что наша цель — это подобрать такое значение
τ , чтобы
число
max
i
|µ
i
| было как можно меньше. Глядя на рисунок, несложно за-
метить, что при искомом оптимальном значении
τ прямая µ = 1
− τλ
должна пересечь с е р е д и н у отрезка
[¯
λ, Λ], то есть
µ = 0 = 1
− τ ·
¯
λ + Λ
2
|
{z
}
сер. отр.
[¯
λ, Λ]
,
откуда
τ
опт
=
2
¯
λ + Λ
.
Имеем
q = max
i
|µ
i
| = |1 − τ
опт
¯
λ
| = |1 − τ
опт
Λ
| = 1 −
2¯
λ
¯
λ + Λ
=
¯
λ
− Λ
¯
λ + Λ
.
(9.15)
Лекция 9
83
Именно величина
q определяет реальный темп убывания погрешности с
номером приближения в рамках оптимального однопараметрического ите-
рационного процесса. Имеет место оценка
kr
(k)
k
6
q
k
kr
(0)
k.
(9.16)
Откуда, получаем априорную оценку числа приближений, гарантирую-
щих достижение заданной точности
ε:
k
>
k
0
=
ln
ε
kr
(0)
k
ln q
0
Найдем
µ
A
, используя норму
2. По условию матрица A — симметрич-
ная, то есть
A
>
= A. Тогда A
>
A = A
2
. Если
λ
i
— собственное значение
матрицы
A, то λ
2
i
— собственное значение матрицы
A
2
= A
>
A. Для нормы
A получим
kAk
2
=
q
max
i
|λ
2
i
| = max
i
|λ
i
|
A>0
= max
i
λ
i
= Λ.
Аналогично для обратной матрицы с помощью леммы 9.1
kA
−1
k
2
=
s
max
i
1
|λ
2
i
|
= max
i
1
|λ
i
|
A>0
= max
i
1
λ
i
=
1
¯
λ
.
В результате
µ
A
= Λ/¯
λ.
Теперь можно в (9.15) выразить
q через µ
A
q =
µ
A
− 1
µ
A
+ 1
.
Если
µ
A
1 (число обусловленности велико), то
ln q
0
= ln
µ
A
− 1
µ
A
+ 1
= ln(µ
A
− 1) − ln(µ
A
+ 1)
≈ −2/µ
A
и
k
0
≈
µ
A
2
ln
ε
kr
(0)
k
.
(9.17)
3 а м е ч а н и е . Здесь приводятся некоторые оценки для систем с боль-
шим числом обусловленности. Это не случайно. Дело в том, что с такими
Лекция 9
84
системами приходится иметь дело довольно часто при численном решении
уравнений с частными производными.
П р и м е р . Пусть надо решить систему из
n = 10
4
линейных уравне-
ний с симметричной положительно определенной матрицей. Метод Гаусса
требует в этом случае выполнения порядка
n
3
∼ 10
12
элементарных опе-
раций. В итерационных методах для перехода от одного приближения к
следующему необходимо выполнить порядка
n
2
операций. Таким образом,
объем вычислений, который сопряжен с методом итераций с одним опти-
мальным параметром (
k
0
n
2
), согласно (9.17) порядка
µ
A
·ln
1
ε
·10
8
, и при не
слишком больших числах обусловленности этот метод эффективнее мето-
да Гаусса.
Каноническая форма записи итерационных методов
Многообразие итерационных схем, созданных для решения различных ли-
нейных систем, можно представить в канонической форме записи:
B
k+1
X
(k+1)
− X
(k)
τ
k+1
+ AX
(k)
= f .
Принята следующая классификация:
• B
k
= E — явные итерационные процессы,
• B
k
6= E — неявные итерационные процессы,
• B
k
= B, τ
k
= τ — стационарные итерационные процессы.
Нами были рассмотрены следующие частные случаи:
1.
B
k
= E, τ
k
= τ — однопараметрический метод;
2.
B
k
= D, τ
k
= 1 — метод Якоби;
3.
B
k
= D + A
−
,
τ
k
= 1 — метод Зейделя.
Метод Прогонки.
85
1.10
Метод Прогонки.
В общем случае системы с трёхдиагональной матрицей имеют вид
(
a
j
y
j
−1
− c
j
y
j
+ b
j
y
j+1
=
−f
j
,
j = 1, 2, . . . , n
− 1,
y
0
=
κ
1
y
1
+ µ
1
,
y
n
=
κ
2
y
n
−1
+ µ
2
.
(10.1)
Или в матричном виде
Ay = f :
−1
κ
1
0
a
1
−c
1
b
1
a
2
−c
2
b
2
. . .
. . .
. . .
a
n
−1
−c
n
−1
b
n
−1
0
κ
2
−1
|
{z
}
A
y
0
y
1
y
2
...
y
n
−1
y
n
|
{z
}
y
=
−µ
1
−f
1
−f
2
...
−f
n
−1
−µ
2
|
{z
}
f
В матрице
A на главной диагонали и в векторе f стоят элементы со зна-
ком «минус». Это объясняется применением метода прогонки для решения
разностных схем для дифференциальных уравнений второго порядка.
Будем искать решение в виде
y
j
= α
j+1
y
j+1
+ β
j+1
,
j = 0, 1, . . . , n
− 1,
(10.2)
где
α
j+1
,
β
j+1
— неизвестные пока коэффициенты. Отсюда найдём
y
j
−1
= α
j
y
j
+ β
j
= α
j
(α
j+1
y
j+1
+ β
j+1
)
|
{z
}
y
j
+β
j
= α
j
α
j+1
y
j+1
+ (α
j
β
j+1
+ β
j
),
где
j = 1, 2, . . . , n
− 1. Подставляя полученные коэффициенты для y
j
и
y
j
−1
в уравнение (10.1) и объединяя слагаемые с
y
j+1
, приходим при
j =
1, 2, . . . , n
− 1 к уравнению
[α
j+1
(a
j
α
j
− c
j
) + b
j
]
|
{z
}
приравняем к нулю
y
j+1
+ [β
j+1
(a
j
α
j
− c
j
) + a
j
β
j
+ f
j
]
|
{z
}
приравняем к нулю
= 0.
Последнее уравнение будет выполнено, если коэффициенты
α
j+1
,
β
j+1
выбрать такими, чтобы выражения в квадратных скобках обращались в
6
Например, вторая производная в точке
x
k
аппроксимируется разделённой разно-
стью
1
h
2
(y
k−1
− 2y
k
+ y
k+1
), где коэффициент при y
k
отрицательный.