§ 23. Двухсторонние унитарные преобразования

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

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

вычислены эти матрицы. Важно лишь, чтобы выполнялись полученные ранее оценки ошибок округления.

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

при этом согласно уже проведенным исследованиям

где Величина а зависит от выбранной последовательности преобразований но не зависит от элементов матрицы А. Далее находим матрицу при этом аналогично (23.1)

где Снова величина зависит от выбранной последовательности преобразований но не зависит от элементов матрицы В. Согласно предположению все преобразования асимптотически близки к унитарным. Теперь, принимая во внимание инвариантность евклидовой нормы к унитарным преобразованиям, заключаем из (23.1), (23.2), что

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

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

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

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

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

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

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

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

Реально полученные матрицы уже не будут унитарными. Поэтому, строго говоря, мы должны были бы вычислять матрицу

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

Во всех рассмотренных преобразованиях

для некоторого эквивалентного возмущения Теперь покажем, что

и дадим оценку нормы .

Умножим обе части равенства (23.3) справа на матрицу Это дает соотношение

Так как матрицы преобразования близки к унитарным, то

Поэтому оценка нормы сводится, по существу, к оценке нормы первого слагаемого из (23.4).

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

Принимая во внимание (18.15), (18.17), заключаем, что

Следовательно, если обозначить

то будем иметь

Предположим теперь, что есть вычисленная последовательность матриц вращения, индексы

которых меняются, например, в циклическом порядке. Рассмотрим более внимательно выражение Согласно (23.5) последовательное умножение матрицы А слева на матрицы можно трактовать как умножение на матрицы с внесением некоторых ошибок. Но эти ошибки с точностью до числовых коэффициентов образуются по тому же закону, что и ошибки округления при умножении на последовательность Поэтому, воспользовавшись анализом ошибок, выполненным в § 19, находим, что

где согласно (19.12) с заменой (18.21) на (23.6) имеем

Но это означает, что также

Аналогично получаются оценки для других последовательностей матриц вращения.

Исследование преобразований отражения осуществляется по той же схеме. Если вычисленная матрица отражения, вектор, то . Принимая во внимание (20.9), заключаем, что

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

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

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

И, наконец, если в качестве матриц подобного преобразования берется последовательность из я— 1 матриц отражения, то в этом случае

УПРАЖНЕНИЯ

(см. скан)