Анализ ошибок

46. Очень детальный анализ ошибок такого приведения к трехдиагональному виду был проведен Уилкинсоном (1962а). Здесь ограничимся суммированием результатов. В таком анализе есть некоторая трудность. В § 14 мы видели, что даже при приведении матрицы общего вида к верхней форме Хессенберга, при которой перестановки разрешены, невозможно безусловно гарантировать устойчивость. То же самое происходит при приведении верхних матриц Хессенберга к трехдиагональному виду даже в наиболее благоприятных случаях, когда все множители порядка единицы. Однако не это будет предметом изучения сейчас. В основном займемся теми ошибками, которые возникают из-за появления малых ведущих элементов и связанного с этим появления больших множителей. В анализе Уилкинсона (1962а) мы поэтому пренебрегли всеми усиливающими эффектами, которые могут быть вызваны умножениями нормальных ошибок округления слева и справа на последовательность и с элементами порядка единицы. При таких условиях результаты состоят в следующем.

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

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

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

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

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

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

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

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

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

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