Разложение матриц As
37. Первый способ основан на том, что хотя мы и предполагаем, что имеет отличные от нуля поддиагональные элементы, мы знаем, что, вообще говоря, некоторые из поддиагональных элементов
стремятся к нулю.
Может случиться, что в процессе итераций у матрицы
окажется один или более очень малых поддиагональных элементов. Если какой-либо из таких элементов достаточно мал, то мы можем рассматривать его как нуль и иметь дело с меньшими матрицами Хессенберга. Так,
для матрицы
при достаточно малом
мы можем найти собственные значения матриц
Заметим, что элементы С в дальнейшем не играют роли. Заметим также, что исходная матрица Хессенберга была сама получена в результате предыдущих вычислений, и следовательно, если
меньше, чем ошибки в элементах то мы мало теряем при замене
на нуль. Число порядка величины
является хорошим допуском.
Итак, на каждой стадии итераций мы можем проверять величины
поддиагональных элементов, и если последний из этих элементов, которым можно пренебречь, находится в позиции
то мы можем продолжать итерации с матрицей порядка
расположенной в нижнем правом углу, возвращаясь к верхней матрице, когда все собственные значения нижней уже найдены. Если
нижняя матрица будет первого порядка, и ее собственное значение известно. На этом этапе мы можем выполнить исчерпывание, опустив последние строку в столбец. Если
нижняя матрица второго порядка и мы можем найти ее собственные значения, решая квадратное уравнение. Снова можно выполнить исчерпывание, опустив последние две строки и два столбца.
38. Второй способ основан на обобщении вышеизложенной идеи Френсиса (1961). Рассмотрим матрицу Хессенберга А, имеющую малые элементы
в позициях
Это иллюстрируется
случае
матрицей, имеющей вид
Пусть А разделена по отношению к этим элементам способом, показанным в (38.1), где
нулевая матрица с точностью до элемента
Покажем, что любое собственное значение
матрицы
является также собственным значением матрицы А, которая отличается от А только элементом
в позиции
.
Действительно, так как
особенная, найдется отличный от нуля вектор х, для которого
Первые две компоненты х удовлетворяют соотношению