Разложение матриц As

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

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

для матрицы

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

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

38. Второй способ основан на обобщении вышеизложенной идеи Френсиса (1961). Рассмотрим матрицу Хессенберга А, имеющую малые элементы в позициях Это иллюстрируется случае матрицей, имеющей вид

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

Действительно, так как особенная, найдется отличный от нуля вектор х, для которого

Первые две компоненты х удовлетворяют соотношению

которое дает

Уравнения (38.2) и (38.4) вместе означают, что последние строк модифицированной матрицы линейно зависимы, и следовательно, является собственным значением А. Если достаточно мало, то можно считать собственным значением А. Если предположить, что не мало, то малость позволяет отделить от остальной части матрицы.