§ 24. Неунитарные преобразования

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

Рассмотрим простейшие неунитарные матрицы. Пусть a и b — векторы размерности По аналогии с матрицей отражения можно построить матрицы вида

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

координатным. Второй из векторов обычно определяется условиями задачи.

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

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

при этом

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

Конечно, по такому же принципу строится и произведение матриц

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

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

Здесь — вектор ошибок, возникающий из-за неточного вычисления произведений Принимая во внимание (8.4), (8.5), можно записать, что

где

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

откуда вытекает, что

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

Вычисление матриц по формулам (24.2) возможно лишь при условии Однако иногда оно может не выполняться. Существует значительное число алгорифмов,

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

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

Итак, утверждение доказано. По-прежнему первые элементов вектора ошибок являются нулевыми. Следовательно, для любого

Окончательно заключаем, что теперь

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

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

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

при этом

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

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

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

Однако у вектора при любых будет отлична от нуля лишь одна координата. Конечно, снова

где

Произведение простым способом связано со своими сомножителями. Легко проверить, что аналогично (24.4) будем иметь

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

поэтому

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)