Формально при 1 = 0 итерации сходятся к следующему собственному значению. Однако из-за ошибок округления li не может быть точно нулем, а при малом 1 процесс по-прежнему сходится к первому собственному значению, только за большее число итераций.

Если наибольшее собственное значение кратное, но соответствующий элементарный делитель матрицы линеен, то итерации сходятся обычным образом. Но если КхФХ, а их модули равны или если элементарный делитель матрицы нелинеен (жорданова клетка), то процесс не сходится.

Если I Ях I я« I 21, то сходимость очень медленная; этот случай нередко встречается в простейших итерационных методах решения разностных схем для эллиптических уравнений (глава ХП). Тогда сходимость можно ускорить процессом Эйткена (см. главу IV, § I).

Одна итерация для матрицы общего вида требует 2п арифметических действий, а для ленточной матрицы-2тл действий. Из-за медленной сходимости степенной метод применяют только к матрицам, содержащим очень много нулевых элементов (и даже к ним-довольно редко).

В математической литературе описана вариация степенного метода, имеющая квадратичную сходимость: x>=AsX"", где As = Asi А 1 и Аа = А. Однако если матрица А имеет много нулевых элементов, то ее степени уже такими не будут. Поэтому этот вариант обычно не экономичен.

4. Обратные итерации со сдвигом. Напишем итерационный процесс, обратный по отношению к степенному процессу:

л:1+1) = Л-1л;(). (73)

Очевидно, он сходится в указанном в п. 3 смысле к наибольшему по модулю собственному значению матрицы А, т. е. к наименьшему по модулю собственному значению матрицы А (ибо собственные значения матриц А и А обратны друг Другу). Все, что говорилось в предыдущем пункте о характере сходимости, разумеется, справедливо и в этом случае; сходимость будет довольно медленной.

Однако здесь положение можно существенно улучшить методом сдвига, который заключается в следующем. Пусть нам приближенно известно некоторое, не обязательно наименьшее, собственное значение Я,-. Тогда так называемая сдвинутая матрица (A-kiE) будет иметь собственные значения Я -Я/. У этой матрицы интересующее нас собственное значение Я; -Я/ будет намного меньше по модулю, чем остальные. Поэтому обратные итерации со сдвинутой матрицей (которые мы запишем в несколько иной форме)

{A-%iE)x+>=x>, (74а)

будут быстро сходиться и определят требуемое нам собственное значение Я/ -Я;. Напомним, что после каждой итерации надо нормировать вектор, чтобы избежать переполнений. С учетом этого вместо (74а) получим последовательность формул

~ 1х\ vsi (746)

Здесь индекс k относится к компонентам векторов, а скобки (...) означают некоторое усреднение по всем компонентам: например, среднеарифметическое.

Если исходное приближение было хорошим, то иногда процесс сходится за несколько итераций; тогда выгодно непосредственно решать линейную систему (73). Если же требуемое число итераций велико, то лучше обратить матрицу (Л - XiE). Выгодней всего при решении линейной системы (74) методом исключения Гаусса использовать полученные на первой же итерации вспомогательные коэффициенты Стк (см. главу V, § 1, п. 1) на каждой последующей итерации; но это не предусмотрено в обычных стандартных программах.

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

(Л-Я£)У) = д:(,

Для матриц, имеющих ортогональную систему собственных век-, торов (например, эрмитовых матриц), сходимость вблизи корня будет даже кубической. Заметим, что допускать слишком точное совпадение Я,- с собственным значением нельзя, ибо матрица системы (75) становится плохо обусловленной; об этом уже говорилось в § 1, п. 6 в связи с нахождением собственных векторов. Поэтому, когда в ходе итераций у величины Я* устанавливаются (т. е. перестают меняться) 5-7 знаков, то итерации следует прекращать.

Замечание 1. Переменный сдвиг собственного значения (75) нельзя включать с первой итераций; сначала надо получить грубую сходимость итераций с постоянным сдвигом.

Замечание 2. Обратные итерации особенно удобны, если матрица заранее приведена преобразованием подобия к почти треугольной форме. Тогда одна обратная итерация выполняется

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

Выводы. Обратные итерации с постоянным и особенно с переменным сдвигом - очень эффективный метод расчета. Для нахождения собственных векторов этот метод считается наиболее

точным. Сходимость при хорошем подборе К настолько быстрая, что метод пригоден и для близких или случайно равных по модулю собственных значений (ибо после сдвига они хорошо различаются), и даже при наличии у матрицы нелинейного элементарного делителя.

ЗАДАЧИ

1. Доказать, что если матрица п-го порядка имеет п собственных векторов ei={&ir\\, Iskin, то она диагснальна.

2. Найти собственные векторы треугольной матрицы, считая все собственные значения простыми.

3. Доказать, что нормальная матрица при унитарном преобразовании подобия остается нормальной.

4. Показать, что если матрица А ленточная, то преобразование подобия матрицами отражения (30) не сохраняет ее структуры.

5. Какие элементы необходимо вычислять в формулах (43) -(44) при преобразовании подобия матрицами вращения для эрмитовой матрицы А?

6. Доказать, что сферическая норма произвольной матрицы не меняется при умножении с любой стороны на унитарную матрицу.

7. В итерационном методе вращений вывести для определения параметров поворота комплексных матриц формулу, аналогичную (51).

8. Показать, что в итерационном методе вращений формулы (54) определяют собственные векторы с точностью О (е), где е -максимум модулей вне-диагональных элементов; если же в этих формулах положить yi - a, то точность ухудшается до О (е).

9. Получить все формулы расчета матричных элементов для второго хода метода элементарных преобразований.

10. Написать формулы восстановления собственных векторов исходной матрицы по собственным векторам трехдиагональной матрицы в методе элементарных преобразований.

11. Показать, что если матрица А ленточная, то элементарное преобразование подобия (57) разрушает ее структуру.

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

У] дг;2=1? б) Как построить экономичный алгоритм решения полученной 1 = 1

при этом, линейной системы, если матрица А является трехдиагональной?

13. Доказать, что метод обратных итераций с переменным сдвигом (75) сходится квадратично вблизи простого собственного значения.