Умножение на последовательность плоских вращений

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

Комбинируя равенства (22.1) для последовательности значений получим

где

Так как по определению точно ортогональны, то также точно ортогональны. Следовательно,

для -нормы или евклидовой нормы.

На практике будем часто иметь дело с множеством вращений в последовательных плоскостях

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

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

Таблица 1 (см. скан)

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

Если мы запишем

то предыдущий анализ показывает, что

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

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

то, применяя неравенство

которое справедливо для всех положительных имеем для

где множитель 10 есть в общем случае.

Записывая для краткости соотношения (21.6), соответствующие для каждого из преобразований, будут таковы:

Мы хотим установить соотношение между Из соотношений в первом столбце (23.7) имеем

и, следовательно, определяя равенством

видим, что сумма в первой строке правой части (23.6) будет ограничена величиной

Точно так же оставшиеся три суммы в (23.6) ограничены величинами

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

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

и, следовательно, тем более

Аналогично для второго столбца (23.7)

где последняя строка заведомо следует из умножения (23.14) на k. Аналогично, используя (23.15) для третьего столбца (23.7), получим

Выражения в скобках левых частей (23.14), (23.15) и (23.16) являются второй, третьей и четвертой строками (23.12), и, следовательно,

а из способа доказательства ясно, что в общем случае коэффициенты будут Заменяя каждый из коэффициентов в (23.17) на максимальный имеем

и, следовательно, в общем случае

так как

Ссылаясь на (23.2) и (23.4), мы видим окончательно, что отсюда следует неравенство

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

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

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

Поэтому этот множитель совсем незначителен в своем влиянии на предел применимости.

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

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