Анализ ошибок метода Хаусхолдера

35. Был дан целый ряд различных анализов ошибок метода Хаусхолдера. Наш общий анализ ошибок из гл. 3, §45 нуждается лишь в небольшом изменении для того, чтобы охватить симметричный случай. Уравнение (45.5) гл. 3 показывает, что если С есть вычисленная трехдиагональная матрица, полученная с использованием накопления с плавающей запятой, и есть точное произведение ортогональных матриц, соответствующих вычисленным то

для некоторой константы К. Для операций с плавающей запятой, использующихся на мы показали, что меньше 40. Следовательно, в обозначениях § 26 имеем

и, как обычно, последний множитель в правой части (35.2) не имеет значения в приемлемых пределах этой оценки. Первый результат такого вида был получен Ортега (1963), причем его доказательство несущественно отличается от нашего. Как мы отмечали в гл. 3, § 45, множитель едва ли может быть улучшен, так как он получается даже тогда, когда мы предполагаем, что каждое преобразование выполняется точно, и только перед переходом к следующему шагу полученная матрица округляется до двоичных разрядов.

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

Константы зависят от особенностей рассматриваемой арифметики, и тщательный их учет в анализе может несколько уменьшить полученные значения. Но, сравнивая (26.2) и (35.3), мы видим, что в пределах использования имеем оценки порядка соответственно для методов Гивенса и Хаусхолдера, выполненных в обычной арифметике с плавающей запятой. Поэтому при больших оценка для процесса Гивенса лучше. Несомненно оценка (35.3) слабее, чем большинство оценок, которые мы получили, но это еще не показывает, какой процесс дает более точные результаты на практике. Трудность заключается в том, что вследствие статистического распределения ошибок округления собственные значения, полученные на практике, очень точны. Поэтому для получения важной информации об относительной точности обоих методов нужно исследовать очень большое число матриц высокого порядка.

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

а это очень хоровшй результат. Но полная матрица порядка 104 имеет 108 элементов, и ее преобразование требует около 2/31012 умножений. Даже со скоростью выполнения умножений в 1 мксек время счета составило бы более 200 часов.

Детальный анализ ошибок метода Хаусхолдера в арифметике с фиксированной запятой и накоплением был дан Уилкинсоном Этот анализ показал, что

при таком условии нормировки

Эта оценка была получена для формул, имеющих два квадратных корня на каждом основном шаге, но при условии, что накапливаются скалярные произведения; несколько других формул дают результаты типа (35.5),

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

Для вычислений с фиксированной запятой без накопления оценка вида

является самой лучшей среди тех, которые до сих пор были получены.