§ 22. Сравнение точности преобразований вращения и отражения

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

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

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

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

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

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

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

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

и мы имеем

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

Каковы бы ни были числа на классе векторов с заданной величиной евклидовой нормы справедливо неравенство

Очевидно, что правая часть имеет минимум в том случае, тогда для всех Так как неравенство (22.2) достигается, то оценки ошибок при различных порядках преобразования элементов не могут быть лучше, чем оценка

где а — некоторая константа.

Если оценка для какой-либо последовательности преобразований вращения отличается от (22.3), то это означает, что или она завышена, или в значительной мере зависит от углов доворота.

Рассмотрим с этой точки зрения результаты исследования влияния ошибок округления, полученные в § 19. Оценка (19.9) не является оценкой вида (22.3) и хуже ее примерно в раз. Но как мы уже отмечали, эта оценка почти достигается для некоторых сильно связанных последовательностей. Следовательно, для таких последовательностей суммарное эквивалентное возмущение должно в значительной мере зависеть от углов поворота. С другой стороны, оценки (19.11), (19.12) для циклических последовательностей являются оценками вида (22.3) и поэтому исключительно эффективны.

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

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

где

для всех Отсюда вытекает, что

Следовательно, оценки (21.6), (21.7) по существу неулучшаемы.

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

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

УПРАЖНЕНИЯ

(см. скан)