Вычислительная математика и программирование - Боглаев Ю.П.
ISBN 5-06-00623-9
Скачать (прямая ссылка):
8.3.4. Метод Зейделя. Отличие метода Зейделя от простой итерации состоит лишь в том, что при вычислении (к Л- 1)-го приближения полученные х(к+1) компоненты вектора х(к+1) сразу же используются в вычислениях. В координатной записи итерационный процесс Зейделя имеет вид
начальный вектор х(0) = (л^0), ..., х?,0)) задается; к=0, 1, 2, ... . В матричной записи (8.3.13) можно представить так:
х(к+1)=их(к) + Ьх(к+1) + (1,
где матрицы и, Ь получены разложением В в сумму:
В=и+Ь;
матрица и—верхняя треугольная часть В, включая диагональ; Е—нижняя поддиагональная часть В;
Таким образом, метод Зейделя можно записать в форме (8.3.3), если принять С=(Е—Ь), В=и. Имеем
Заметим, что построение матрицы, обратной (Е— Ь) х, не представ* ляет труда, так как это нижняя треугольная матрица.
0.
.0
(Е-Е)х{к + 1)=их{к) + с1, к=0, 1, 2, ... . (8.3.14)
326
\
(8.3.15)
тогда последовательные приближения {х{к)}, полученные из (8.3.14), сходятся к точному решению системы
при любом начальном векторе л;(0).
Доказательство. Заметим, что метод Зейделя (8.3.14) — это метод простой итерации для системы
которая эквивалентна исходной х = Вх + (1. Обозначая (Е— Ь) 1и= = Ви [Е—Ь)~1 <1=(1и запишем (8.3.14) следующим образом:
Теперь утверждение теоремы следует из теоремы 8.6.
Заметим, что оценка погрешности к-то приближения метода Зейделя в случае выполнения (8.3.15) вытекает из (8.3.9), (8.3.11) при условии замены В на 2?х:
Выше приводились достаточные условия сходимости последовательных приближений (|| В || <1, || || < 1). Заметим, что области сходи-
мости метода простой итерации и Зейделя лишь пересекаются: существуют матрицы В, для которых метод Зейделя сходится, а метод простой итерации расходится, и наоборот.
Для иллюстрации итерационного процесса Зейделя рассмотрим систему
х = Вх+с1
х = (Е-Ь)~1 их + (Е-Ь)~1(1,
х{к + 1) = В1х(к) + с11.
х1=0,\х1—0,2х2 + \, х2 = 0,5^! + 0,1 х2 — 1.
Здесь
В=и+Ь;
Итерационный процесс
х?+1) = 0,1х?> -0,2x^+1,
х<$+=0,05*?+1(+0, 1х?> -1
327
с начальным вектором лг5.О) = 0, лс:^0) = 0 дает следующие приближения: х[г) = 1,00; х[2) = 1,2900; х{3) = ...
лг^)= —0,95; *?>=-1,0305; л^3) = ...
# 8.4. Вычисление собственных значений и векторов
8.4.1. Введение. Большинство алгоритмов определения собственных значений и векторов матрицы А основаны на приведении А с помощью невырожденных преобразований к такой матрице А*, для которой проблема собственных значений является простой. Например, есдЬ А—вещественная матрица с различными вещественными собственными значениями Х1? ..., ХЛ, то матрица преобразования Т, которая приводит А к диагональному виду, полностью решает проблему. Действительно,
Столбцы матрицы Т образуют полную систему собственных векторов матрицы А, а диагональные элементы А* суть собственные значения А.
Чтобы- определить собственные значения матрицы (при тех же предположениях относительно X,*), не обязательно приводить ее к диагональному виду. Достаточно привести ее к треугольному виду, поскольку на диагонали будут расположены собственные значения матрицы А:
откуда следует, что собственные значения А*
ЦА*) = {а\л, а*2Л, а*п,п}.
Остается показать, что X (А)=X (А'). Это вытекает из равенств
ае1(Л’-Х?)=ёе1(7’-1^Г-Х.?)=ёе1(Г-1 (А-ХЕ) Т)=
=ае1 Т~1 скН (А - ХЕ) а# Т= ск* (А - ХЕ).
Определение собственных векторов е* треугольной матрицы А* является простой задачей, так как она эквивалентна решению
А* =
= Т~1АТ.
. 0
Действительно, характеристическое уравнение А*
Аа(А*-ХЕ) = 0
представляется в форме
(яід — Х)(а*2,2 — X) ... (а*п,п — X) — 0,
328
\
ч
\
I
системы однородных уравнений А*е{ = а*цеь 1 с треугольной
матрицей и каким-либо дополнительным условием, однозначно выделяющим собственные векторы, например <?*,* = Ь Зная
собственные векторы матрицы А*, можно получить собственные векторы А с помощью матрицы преобразования Т
поскольку из равенства
е{=Те1
Т-'АТе^аЪе]
следует соотношение
А(Те1) = а1(Те1).
Заметим, что вещественная матрица, если она имеет комплексные собственные значения, не может быть приведена к треугольной матрице А* с помощью вещественного преобразования. Матрицей, к которой можно привести любую матрицу А с помощью вещественного и даже ортогонального преобразования, является почти треугольная матрица А*:
А* =
«1,1
«2,1
• «1,п «2,и
(8.4.1)
0
В задаче определения собственных значений и собственных векторов первым шагом является приведение матрицы А к форме (8.4.1). Эту процедуру целесообразно выполнить для того, чтобы дальнейшие вычисления вести с ненулевыми элементами А*, которых при больших п почти вдвое меньше, чем у исходной матрицы А. Для симметричных матриц А форма (8.4.1) принимает вид
А* =
«1,1 «1,2 «2,1 «2,2«2,3
О
«и 1 ,** О «и,и — 1 ап,п
(8.4.2)
А* называется трехдиагональной матрицей; для нее а(]=0, если |/-у|>1.
8.4.2. Приведение матрицы к почти треугольному виду. Приведение матрицы А к виду (8.4.1) будем осуществлять с помощью ортогональных преобразований Г, которые, как известно, сохраняют длину векторов, т. е.
II Тх II2= II X II2 ИЛИ (Тх, Тх) = (х, х).
