§ 25. Ортогонализация

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

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

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

Условие ортогональности вектора к ортогональным векторам или, что то же самое, векторам дает

поэтому окончательно находим

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

получаемой системы векторов Именно, эта система в точном смысле уже не будет эквивалентна системе и не будет ортонормированной.

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

Введем некоторые обозначения. Подпространства, натянутые на векторы будем обозначать через координаты векторов и других соответственно через

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

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

Предположим теперь, что вычислены векторы и получены оценки норм для при некотором Пусть вектор вычисляется согласно формулам (25.1), (25.4). Каким бы способом ни вычислялись коэффициенты из (25.3) и какие бы ошибки они ни содержали, вектор будет принадлежать сумме подпространства и подпространства, натянутого на если лишь суммирование в формуле (25.2) реализуется точно. Поэтому дополнительная неэквивалентность на этом этапе может возникнуть только за счет неточного вычисления суммы в правой части (25.2).

Будем определять координаты вектора используя операцию вычисления скалярного произведения в режиме накопления. Тогда для всех

где снова удовлетворяет обычным соотношениям. Эту формулу можно записать в таком виде:

Здесь Нормировка вектора вносит дополнительное возмущение в координаты которое оценивается так же, как при вычислении вектора Окончательно получаем, что вектор принадлежит сумме подпространства и подпространства, натянутого на вектор При этом

где есть точное значение евклидовой нормы вектора вычисленное в процессе нормировки.

Если вычисления выполняются точно, то евклидова норма вектора не превосходит евклидовой нормы вектора для всех так как из (25.1), (25.4) вытекает, что

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

Учитывая условие (4.7) и полученные выше оценки, можно сделать следующий вывод.

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

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

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

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

где достаточно малое число. С помощью несложных вычислений получаем

Здесь символ Кронекера и все суть величины порядка Пусть по векторам вектор вычисляется без ошибок. В силу (25.5), (25.8) имеем

Отсюда для следует, что

Введем в рассмотрение угол между вектором и подпространством согласно [1]. Несложные вычисления показывают, что

Если среди чисел есть большие по модулю, то большими по модулю будут и некоторые из отношений

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

Если мы проследим распространение ошибок на несколько последующих шагов, то положение окажется еще более серьезным, так как первоначальные ошибки будут умножаться на произведение отношений вида (25.10). Это означает, что для того, чтобы в значительной мере нарушилась ортогональность системы векторов совсем не обязательно, чтобы какое-либо из отношений (25.10) было большим. Достаточно, чтобы большим было произведение таких отношений из различных шагов.

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

Для устранения отмеченной Неустойчивости будем несколько иначе определять вектор Условие его ортогональности к вычисленным векторам дает для определения коэффициентов линейной комбинации (25.2) следующую систему линейных алгебраических уравнений:

Обозначим через В матрицу системы (25.11), а через вектор

Из рекуррентного соотношения (25.12) получаем, что векторы и связаны между собой равенством откуда вытекает, что

Если векторы близки к ортонормированным, то и последовательность векторов сходится к нулю. Следовательно, последовательность векторов сходится к такому вектору который ортогонален векторам По построению этот вектор является вектором вида (25.2).

Таким образом, при точной реализации итерационного процесса (25.12) ошибки от неортогональности системы

векторов не оказывают влияние на ортогональность к этим векторам всех последующих векторов.

При реальных вычислениях правые части соотношений (25.12) не могут быть определены точно, поэтому в действительности найденный вектор все же не будет ортогонален векторам Будем считать, что векторы не слишком сильно отличаются от ортонормированных и выполняется условие (25.6). В этом случае для всех

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

Здесь удовлетворяют обычным для ошибок соотношениям. Из (25.14) вытекает, что для

При этом координаты вектора связаны с величинами в (25.14) такими соотношениями:

Обозначим

Из (25.15) следует равенство

где координаты вектора таковы:

Принимая во внимание (25.6), (25.13), находим, что

Окончательно имеем

Полученное неравенство означает, что, начиная с некоторого вычисленный вектор будет почти ортогонален векторам Именно, евклидова норма его проекции на подпространство асимптотически не будет превосходить Снова мы получили замечательный результат в отношении точности метода ортогонализации. Ведь только округление мантисс координат вектора до знаков изменяет евклидову норму его проекции на подпространство на величину порядка Итерационный процесс (25.12) дает ошибку лишь вдвое больше.

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

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

УПРАЖНЕНИЯ

(см. скан)