Главная > Математика > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

4. Обратные итерации со сдвигом.

Напишем итерационный процесс, обратный по отношению к степенному процессу:

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

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

будут быстро сходиться и определят требуемое нам собственное значение

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

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

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

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

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

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

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

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление