Ортогонализация Шмидта

54. Если мы приравняем соответствующие столбцы в уравнениях (53.2), то имеем

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

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

55. При точном вычислении процесс Шмидта дает матрицы которые совпадают (с точностью до знаков) с матрицами, полученными как по процессу Гивенса, так и по процессу Хаусхолдера. Однако матрица полученная на практике, с использованием уравнений (54.1) —

(54.3), и матрица, которая могла бы быть получена перемножением транспонированных матриц преобразований процесса Гивенса или Хаусхолдера, могут почти полностью отличаться друг от друга. Вообще говоря, обе последние матрицы могут также отличаться полностью. Из анализа ошибок главы 3 мы знаем, что эти матрицы очень близки к ортогональным для любого приемлемого значения хотя на практике их полный вид нам нужен редко. Однако векторы полученные из применения формул (54.1)-(54.3), могут отклоняться от ортогональных на почти произвольные величины.

На первый взгляд это кажется неожиданным, так как процесс Шмидта вроде бы и построен специально для того, чтобы получать ортогональные векторы. Однако рассмотрим такую матрицу 2-го порядка:

Первый шаг в процессе Шмидта дает

второй шаг дает Поэтому мы имеем

При вычислении правой части (55.3) имеет место значительное сокращение, и полученные компоненты имеют большую относительную ошибку. (Это верно независимо от того, используется ли фиксированная или плавающая запятая.) Следовательно, когда вектор справа нормируется, чтобы получить он даже приближенно неортогонален Это вполне убедительно показывает, что данное явление не связано с большим порядком матриц и не может быть отнесено к «совокупному влиянию большого числа ошибок округления».

Естественно спросить, действительно ли «близка» вычисленная ортогональная матрица, полученная по процессу Гивенса или по процессу Хаусхолдера, к той единственной ортогональной матрице, которая соответствует точному вычислению во всех трех методах. В общем случае мы не можем гарантировать, что это действительно так. Наш анализ ошибок из главы 3 гарантирует то, что матрицы будут «почти ортогональны», а не то, что они будут «близки» к матрице, соответствующей точному вычислению. (В гл. 5, § 28 дадим иллюстрацию сказанного в связи с ортогональными подобными преобразованиями.) В некоторых вычислениях ортогональность очень важна. Например, в -алгорифме для симметричных матриц после получения разложения матрицы А в произведение вычисляется матрица Так как мы имеем то эта полученная матрица есть подобное преобразование А, но она будет симметричной только тогда, когда ортогональная. Явление, которое мы только что рассмотрели в связи с процессом Шмидта, будет снова интересовать нас, когда мы рассмотрим метод Арнольди для решения проблемы собственных значений (гл. 6, § 32).

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

Хаусхолдера требует дополнительно умножений, так что, даже если ортогональная матрица требуется в явном виде, метод Хаусхолдера вполне экономичен. Более того, если мы хотим получить матрицу, «близкую к ортогональной», используя процесс Шмидта, то векторы должны переортогонализироваться на каждом этапе, а это требует дополнительно умножений (см. гл. 6).