ГЛАВА III. ВСПОМОГАТЕЛЬНЫЕ АЛГЕБРАИЧЕСКИЕ ОПЕРАЦИИ

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

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

§ 18. Преобразование вращения

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

Если через обозначим матрицу второго порядка

то соотношения (18.1) в матричной записи означают, что

Матрица (18.2) называется матрицей вращения, а преобразования вида (18.3) — преобразованиями вращения; угол а называется углом поворота.

Рис. 18.1.

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

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

Таким образом, в реальных условиях вместо выражений (18.1) придется вычислять выражения

Этот процесс реализуется на ЭВМ вполне устойчиво. Обозначив

и пусть координаты вектора Имеем

Предположим сначала, что среди величин нет равных —1, т. е. справедливы оценки для всех Тогда получаем

откуда следует, что

Если среди есть равные —1, то это означает, что соответствующие вычисляемые величины по модулю не превосходят минимального положительного числа , которое можно представить в ЭВМ. Чисел равных —1, может быть в (18.7) не более четырех. Поэтому окончательно оценка для будет такой:

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

где Принимая во внимание вид матрицы и оценку (18.8), находим, что

Итак, вектор, реально вычисленный по формулам (18.5), совпадает с вектором, точно вычисленным по тем же формулам, но исходя из возмущенного вектора а где эквивалентное возмущение удовлетворяет условию (18.10).

Рис. 18.2.

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

полученный вектор оказался лежащим на координатной оси Согласно (18.1) это означает, что для угла а должно выполняться соотношение Поэтому можно, например, считать, что

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

Прямое вычисление а по формулам (18.11) невозможно, если вектор нулевой, и заведомо неустойчиво, если вектор достаточно мал. Поэтому реальные вычисления будем выполнять по измененным формулам. Обозначим Если то положим

Если, же то вычисляем и далее

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

при этом очевидно, что . Имеем

вычисляя тем самым элементы матрицы (18.4),

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

Если обозначить

то для получаем оценку

Если же то для всех

Легко проверить, что теперь

С учетом (4.7), эта оценка включает в себя оценку (18.16), поэтому соотношение (18.17) имеет место всегда, если, конечно, матрица вращения вычисляется согласно (18.12), (18.13).

Если все вычисления осуществляются точно, то образом вектора является вектор, имеющий координаты и 0. В качестве первой координаты вычисленного вектора мы возьмем

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

при точном линейном преобразовании с матрицей, вычисленной согласно (18.14). Как уже отмечалось выше, величины не равны — 1, величина же не равна — 1, так как Если то вектор (18.19) отличается от исходного вектора на вектор где

Если же то это означает, что и поэтому, с учетом (4.7), теперь имеем

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

Подведем итоги выполненных исследований. Итак, пусть заданы два вектора , и по вектору вычисляется матрица вращения согласно формулам (18.12), (18.13). Если вычисления выполняются по алгорифму (18.12), (18.14), то реально полученная матрица имеет вид (18.4) и будет отличаться от ортогональной матрицы множителем где для справедлива оценка (18.17). Преобразование вектора а с помощью матрицы согласно формулам (18.5) по алгорифму (18.7) или преобразование вектора по тем же формулам с вычислением единственной ненулевой координаты согласно (18.18) эквивалентно точному преобразованию по формулам (18.5) возмущенных ректоров. Эквивалентное возмущение для вектора а удовлетворяет неравенству (18.10), для вектора неравенству (18.20) и, следовательно, для любого вектора с, включая тот, по которому строилась матрица неравенству

Аналогичные результаты могут быть получены и для комплексных векторов. В этом I случае вместо матрицы вращения в преобразовании (18.3) берется унитарная матрица вида

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

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

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

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)