§ 19. Последовательность преобразований вращения

Оценим теперь эквивалентное возмущение при выполнении последовательности преобразований вращения. Рассмотрим -мерный вектор с координатами и последовательность матриц вращения.

Пусть реально заданные матрицы. Мы не будем интересоваться способом их вычисления, но предположим, что все они удовлетворяют условию (18.17). Обозначим

для . Ясно, что

где — эквивалентное возмущение преобразования вращения с матрицей Последовательно используя соотношение (19.1), находим

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

Одна из оценок выводится совсем просто. Пусть

— координаты вектора Согласно (18.21) будем иметь

Так как матрицы близки к ортогональным, то

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

К тому же, следовательно,

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

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

если только все матрицы вращения близки к матрицам перестановок. Эти примеры показывают, что оценка (19.4) практически неулучшаема для всех последовательностей матриц вращения, у которых любые две соседние матрицы имеют хотя бы один общий индекс. Такие последовательности мы будем называть сильно связанными.

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

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

а вместо соотношения -неравенство

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

поэтому

В соответствии с неравенством Коши — Буняковского

и окончательно находим, что теперь

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

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

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

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

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

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

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

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

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

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

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

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

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

где каждая строка соответствует несвязанной последовательности.

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

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

Предположим, что последовательность матриц вращения состоит из несвязанных групп. Тогда из (19.6) получаем, что

Для обеих циклических последовательностей согласно (19,8) имеем

если и

если

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

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

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

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

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

с номерами Далее, умножая на матрицы исключим координаты с номерами Ясно, что внутри каждой такой группы матрицы вращения не имеют одинаковых индексов, а всего групп будет не более Согласно оценке (19.10), в этом случае будем иметь

Эта оценка существенно лучше оценки (19.14)

УПРАЖНЕНИЯ

(см. скан)