Ускорение сходимости

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

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

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

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