Кубически сходящийся LR-процесс

57. Пусть матрица типа, который мы обсуждали в § 54. Кроме того, предположим, что она положительно определенная и что мы получили удовлетворяющую условиям (54.3), (54.4), используя LR-алгорифм Холецкого. Из (54.6) знаем, что на этой стадии все диагональные элементы отличаются от на величины порядка Предположим, что мы используем в качестве сдвига При этом факторизация должна сорваться, так как все диагональные элементы симметричной матрицы не меньше ее наименьшего собственного значения. Однако из (54.9) следует, что срыв не произойдет ранее стадии Матрица X на этой стадии имеет вид

и эта матрица порядка Если наименьшее собственное значение X, то (см. § 56) является подходящим сдвигом. Мы покаяем, что это очень близко к Положив получим

Так как обе матрицы в правой части имеют одну систему собственных векторов, то, используя (54.8), (54.9) и (54.4), имеем

Следовательно, так как (наименьшее собственное значение ), имеем

что дает

Для того чтобы показать, что после итерации с матрицей евклидова норма матрицы имеет порядок мы могли бы провести прямой анализ, аналогичный анализу § 54. Оставим это для упражнения. Общая теория показывает, что умножится на множитель порядка

т. е. порядка Так как. порядка результат установлен.

58. Мы рассмотрели случай, когда кратность наименьшего собственного значения произвольна, но на практике метод наиболее удовлетворителен, если равно 1 или 2, так как только тогда легко определяется наименьшее собственное значение

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

Определяем положительные сдвиги любым подходящим способом, например, как в § 55, до тех пор, пока не станет значительно меньше всех остальных диагональных элементов и внедиагональные элементы в последних столбце и строке не станут малыми. Затем в качестве следующего сдвига берем и разложение не проходит. Если при этом порядок матрицы, остающейся ниже точки срыва, больше двух, то мы сменили методы слишком рано. (Заметим, что если кратность собственного значения действительно больше двух, то срыв обязательно произойдет слишком рано.) Рутисхаузер и Шварц (1963) развили очень изобретательные стратегии для приложения этого процесса, и мы советуем читателю обратиться к их работе.

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

Отсюда следует результат. Заметим, что если недиагональные элементы последних строки и столбца достаточно малы, то мы можем произвести исчерпывание независимо от того, мал или нет Этот элемент будет на самом деле мал, если только сдвиг был выбран хорошо.