Дополнительные замечания

Предположение о том, что методы, аналогичные методу Якоби, могли бы быть использованы для приведения матриц общего вида к треугольному виду, делалось фон Нейманом и Козеем (1958); Гринштадт (1955) и Лоткнн (1956) описали методы такого типа. На конференции по теории матриц в Гетлинбурге в 1961 г. Гринштадт дал обзор методов этой группы, предложенных к тому времени, и сделал вывод, что еще не развито ни одной удовлетворительной процедуры. Эберлейн (1962) описала модификацию метода Якоби, основанную на замечании, что для любой матрицы А существует преобразование подобия которое сколь угодно близко к нормальной матрице. В алгорифме Эберлейн строится в виде произведения последовательности матриц, которые являются обобщениями плоских вращений, но уже не являются унитарными. Итерации продолжаются до тех пор, пока В не

станет с рабочей точностью нормальной, и основная черта метода состоит в том, что, вообще говоря, предельная матрица В является прямой суммой некоторого числа матриц 1-го и 2-го порядков, так что можно определить все собственные значения.

Эберлейп также рассматривала приведение матриц общего вида к нормальному виду, используя комбинации плоских вращений и диагональных преобразований подобия, и подобные идеи независимо развивались Рутисхаузером. Обычно ведущей стратегией на каждой стадии является уменьшение отклонения Хенричи (гл. 3, § 50). Развитие этой линии может привести к методам, которые превзойдут те методы, которые я описал, и, может быть, это будет наиболее перспективной линией развития.

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

Первое упоминание -алгорифма было сделано Рутисхаузером в 1955 г. С тех пор он постоянно развивал и расширял свою теорию в серии работ. Я попытался здесь обобщить наиболее позднюю информацию, полученпую из работ Рутисхаузера и моего собственного опыта работы в Национальной физической лаборатории. Я включил доказательства сходимости, данные Рутисхаузером в его работах, так как они являются типичными. -алгорифм со сдвигом и перестановками в применении к матрицам Хессенберга был впервые использован автором в 1959 г. в основном для матриц с комплексными элементами.

Работы Френсиса по -алгорифму помечены 1959 г., но не опубликованы вплоть до 1961 г. Одновременно и независимо тот же алгорифм был открыт Кублановской (1961). В свете нашего параллельного изучения ортогональных и неортогональных преобразований он является естественной аналогией -алгорифма, но работа Френсиса содержит значительно больше, чем простое описание -алгорифма. Обе техники — для комбинирования комплексно сопряженных сдвигов и описанная в § 38» техника, имеющая дело с последовательными малыми поддиагональными элементами, являются важным вкладом в эффективность QR-алгорифма.

Доказательство сходимости -алгорифма, данное в §§ 29—32, было найдена автором во время написания настоящей главы. Доказательства, основанные на более трудоемкой теории определителей, даны Кублановской (1961) и Хаусхолдером (1964).

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