Значение переортогонализации

33. Для того чтобы получить который действительно ортогонален мы применяли процесс ортогонализации Шмидта к . Важно понять, что поправка к полученная таким путем, не единственная, дающая удовлетворительные результаты. Все, что нам нужно, — это получить такую поправку, которая была бы порядка не больше и делала бы почти ортогональным Например, вектор

дает такие же хорошие результаты, как и полученный при помощи переортогонализации. После нормировки он дает такой что (32.8) выполнено. Эффект взаимного уничтожения дает некоторую степень свободы в выборе вектора . В работе Уилкинсона (1963b, стр. 86—91) показано, что если происходит взаимное уничтожение, даже при использовании переортогонализации окончательные матрицы очень сильно зависят от точности вычислений.

Простейшая процедура, вообще говоря, состоит в следующем. Вычисляем вектор вида

Затем вычисляем такой, что

где

Тогда будем иметь

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

Необходимость переортогонализации возникает из-за взаимного уничтожения, а не из-за накопления ошибок округления. Для того чтобы подчеркнуть это, мы использовали матрицу второго порядка. Если на всех этапах не происходит взаимного уничтожения, то переортогонализацию можно опустить, но, к сожалению, такие случаи редки. Включение переортогонализации делает метод Арнольди значительно менее экономичным, чем метод Хаусхолдера; в нем умножений без переортогонализации и с переортогонализацией. (В этой связи смотрите сравнение процесса ортогонализации Шмидта и процесса приведения к треугольному виду Хаусхолдера в гл. 4, § 55). Без переортогонализации метод Арнольди может давать произвольно плохие результаты даже для хорошо обусловленных матриц. Однако если переортогонализация включена, то метод Арнольди сравним по точности с методом Хаусхолдера; эта точность

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

Снова имеем ситуацию, когда при точных вычислениях, если равен нулю, имеется полная свобода в выборе «всех знаков» при условии лишь, что он ортогонален к предыдущим При вычислениях же с ограниченной точностью, когда к цифр исчезают в результате взаимного уничтожения, можем выбирать к знаков произвольно. Заметим, что в методе Арнольди мы не можем иметь срыва второго типа, описанного в § 27, так как

34. В связи с переортогонализацией весьма естественно возникают два вопроса:

(i) Почему в методе Хессенберга нет ничего соответствующего этой переортогонализации?

(ii) Что занимает место переортогонализации в приведениях Гивенса и Хаусхолдера, которые, как мы знаем, математически эквивалентны приведению Арнольди?

Необходимо, чтобы читателю все стало ясно в этих вопросах, и мы детально обсудим их. Обсудим сначала первый вопрос. Заметим, что если мы определим уравнениями

то, предполагая только, что получим

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

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

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

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