book chis_met

Метод обратных итераций предназначен для вычисления наименьшего по модулю собственного значения λn и отвечающего ему собственного вектора u(n) и состоит в следующем. Выберем произвольный вектор x(0) и построим последовательность векторов x(k), каждый из

которых является решением системы уравнений

На практике вычисления продолжают до тех пор, пока не будет выполнено неравенство

|1/αk − 1/αk−1| < ε,

где ε - заданная точность вычисления собственного значения λn. При этом 1/αk принимают за приближенное значение λn, а x(k) - за приближение к u(n). Если за K итераций (K -

предельно допустимое число итераций, задаваемое программистом), заданная точность не достигается, вычисления прекращаются.

Для решения систем уравнений Ax(k) = x(k−1)/αk−1 на каждом шаге можно восполь-

зоваться методом Гаусса. Поскольку матрица у всех систем одна и та же, то ее треугольное разложение U + M A следует выполнить только один раз. Решение каждой системы Ax(k) = x(k−1)/αk−1 сводится, следовательно, к получению преобразованной правой части g(k) = M (x(k−1) /αk−1) и последующему решению системы с треугольной матрицей

U x(k) = g(k).

2.3Полная проблема собственных значений

2.3.1Метод вращения с преградами

Метод вращения предназначен для решения полной проблемы собственных значений невырожденной симметричной матрицы , т. е. для нахождения собственных значений и собственных векторов исходной матрицы. Эта проблема решается с помощью сходящихся итерационных процессов. Для симметричных матриц эти процессы состоят в цепочке преобразований подобия, в результате которых в пределе получается диагональная матрица так, что ее собственные значения определяются непосредственно. Впервые этот процесс был предложен Якоби в 1976 г., однако практическое применение стало возможным лишь с развитием быстродействующих счетных устройств. В настоящее время имеется целый ряд модификаций метода Якоби. Одной из модификаций является метод вращений с преградами.

Элементарный шаг каждого эрмитова процесса заключается в преобразовании подобия посредством матрицы вращения

31

где c2 + s2 = 1. Эти матрицы принадлежат к классу ортогональных матриц, т.е. Tij · Tij = E. Процесс состоит в построении последовательности матриц Ao = A, A1, ..., каждая из ко-

торых получается из предыдущей с помощью элементарного шага. Эти элементарные шаги должны быть подобраны так, чтобы An+1 безгранично приближалась к диагональной мат-

Матрица вращения выбирается на (m + 1) шаге так, чтобы элемент aij стал нулем. При этом пара индексов (ij) выбирается так, чтобы аннулировался наибольший по модулю внедиагональный элемент матрицы A(m) , а именно |a(ijm)| ≥ σk , где σ1, σ2, ... монотонно убываю-

щая к нулю последовательность чисел, называемых "преградами". Один из способов зада-

q

ния "преград"состоит в нахождении σk по формуле σk = max|a(iim) | · 10−k , где k = 1, 2, ..., p. Число p зависит от разрядности машины и требуемой точности решения поставленной задачи. После того как все внедиагональные элементы станут по модулю не больше σk , то "преграда"σk заменяется на σk+1 и т.д. k = 1, 2, ...p. Процесс заканчивается, когда все внедиагональные элементы станут меньше по модулю σp. Известно, что процесс с "преграда-

ми"сходится.

Так как характеристические полиномы подобных матриц совпадают, следовательно,

det(A − λE) = det(D − λE) = (d11 − λ)(d22 − λ)...(dnn − λ) = 0,

где D - есть диагональная матрица, полученная в результате выполнения описанного выше

итерационного процесса.

Скажем несколько слов о нахождении собственных векторов матрицы A. Пусть итераци-

m

32

W ′, получим A = W DW ′. Из этого равенства получаем, что AW = W D. Если расписать это равенство по столбцам, то окажется, что каждый i-ый столбец матрицы W является собственным вектором, соответствующим собственном значению λi.

В отличие от прямых методов, алгоритмы которых состоят из разнородных частей: преобразования исходной матрицы, вычисления корней многочлена, нахождения собственных векторов, метод вращения позволяет в результате выполнения итерационного процесса найти собственные значения и собственные вектора.

Хотя количество умножений в этом методе весьма значительно, ошибки округления накапливаются медленно, так как умножения происходит на коэффициенты c и s по модулю

меньше единицы.

Пример. Решить полную проблему собственных значений методом вращения с преграда-

33

x¯1 = (0, 846727; −0, 495220; −0, 194385)

x¯2 = (0, 482795; 0, 561790; 0, 671789)

x¯3 = (−0, 223458; −0, 662646; 0, 714802)

2.4Задания

1. Раскрыть вековые определители методами Леверье и Фадеева, найти собственные значения следующих матриц.

2.Решить частную проблему нахождения собственных значений методом прямой или обратной итерации.

3.Найти методом вращения собственные значения и собственные вектора матриц с точностью 10−3.

34

В следующих вариантах матрица A = D + kC, где C, D - матрицы, а k - параметр.

Список литературы

1.Бахвалов Н.C.Жидков Н.П., Кобельков Г.М. Чиcленные методы. -М.: Наука,1987.

2.Березин И.С., Жидков Н.П. Методы вычислений. Том II. -М.: Физматгиз, 1962. 640 с.

3.Волков Е.А. Чиcленные методы.-М.: Наука, 1987. 248 с.

4.Демидович Б.П., Марон И.А. Основы вычислительной математики. -М.: Наука, 1966.

35

5.Калиткин Н.Н. Чиcленные методы.-М.: Наука, 1978. 512 с.

6.Крылов В.И., Бобков В.В., Монаcтырный П.И. Вычиcлительные методы: В 2-х т. -М.: Наука, 1976-1977.

7.Митченко А.Д. Численные методы линейной алгебры. -Владивосток, ДВГУ, 1991.

142с.

8.Митченко А.Д., Хайрутдинова Г.З. Алгоритмы линейной алгебры. Методические указания (для студентов математического факультета). Владивосток, ДВГУ, 1993. 32 с.

9.Положий Г.Н., Пахарева Н.А. и др. Математический практикум. -М.: ГИФМЛ, 1960.

512с.

10.Cамарcкий А.А., Гулин А.В. Чиcленные методы.-М.: Наука,1989. 432 с.

11.Фадеев Д.К., Фадеев В.Н. Вычислительные методы линейной алгебры. -М.-Л.: ГИФМЛ, 1963. 735 с.

36