§ 5.10. QR-разложение матрицы. Методы вращений и отражений

Метод Гаусса не является единственным методом исключения, используемым для решения систем линейных уравнений и приведения матриц к треугольному виду. Рассмотрим два метода исключения, обладающих в отличие от метода Гаусса гарантированной хорошей обусловленностью — метод вращений и метод отражений. Оба этих метода позволяют получить представление исходной матрицы А в виде произведения ортогональной матрицы Q на верхнюю треугольную матрицу R:

Представление (5.79) — это QR-разложение матрицы на множители.

1. Метод вращений.

Опишем прямой ход метода. На 1-м шаге неизвестное исключают из всех уравнений, кроме первого. Для исключения из второго уравнения вычисляют числа

обладающие следующими свойствами:

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

в которой

Заметим, что в силу специального выбора чисел (см. равенства (5.81)).

Естественно, что в случае исходная система уже имеет вид (5.82) и в исключении неизвестного из второго уравнения нет необходимости. В этом случае полагают

Как нетрудно видеть, преобразование исходной системы (5.1) к виду (5.82) эквивалентно умножению слева матрицы А и правой части 6 на матрицу имеющую вид

Для исключения неизвестного из третьего уравнения вычисляют числа

такие, что Затем первое уравнение системы (5.82) заменяют линейной комбинацией первого и третьего уравнений с коэффициентами и , а третье уравнение — аналогичной комбинацией с коэффициентами — Это преобразование системы эквивалентно умножению слева на матрицу

и приводит к тому, что коэффициент при в преобразованном третьем уравнении обращается в нуль.

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

В матричной записи получаем

где

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

элемент с индексами равен а элемент с индексами равен причем выполнено условие

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

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

В матричной форме записи получаем

где

После завершения шага система принимает вид

или в матричной форме записи

где

Введем обозначение для полученной верхней треугольной матрицы Она связана с исходной матрицей А равенством

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

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

Метод вращений обладает замечательной численной устойчивостью. Для него оценка (5.43) справедлива с коэффициентом Однако этот метод существенно более трудоемок по сравнению с методом Гаусса. Получение -разложения для квадратной матрицы А общего вида требует примерно арифметических операций.

Пример 5.18. Используя метод вращений, решим на 6-разрядной десятичной ЭВМ систему уравнений

Прямой ход. 1-й шаг. Исключим из второго уравнения. Для этого вычислим по формулам (5.80):

Преобразуя коэффициенты первого и второго уравнений по формулам (5.83), приходим к системе

Далее вычислим коэффициенты по формулам (5.84):

Заменяя первое и третье уравнения их линейными комбинациями с коэффициентами соответственно, получим систему

2-й шаг. В полученной системе имеем Поэтому

Заменяя второе и третье уравнения системы их линейными комбинациями с коэффициентами соответственно, приходим к системе

Обратный ход дает последовательно значения

2. Метод отражений.

Матрицами Хаусхолдера (или отражений) называются квадратные матрицы вида

Здесь вектор-столбец в имеющий единичную длину. Матрица

V является ортогональной и симметричной. Умножение на нее называют преобразованием Хаусхолдера (или отражением). Действие матрицы

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

Как и вращения, отражения используются для обращения в нуль элементов преобразуемой матрицы. Однако здесь с помощью одного отражения можно обратить в нуль не один элемент матрицы, а целую группу элементов некоторого столбца или строки. Поэтому, являясь почти столь же устойчивым, как и метод вращений, метод отражений позволяет получить QR-разложение квадратной матрицы общего вида примерно за арифметических операций, т.е. в полтора раза быстрее. Изложение самого метода можно найти, например, в [9].