Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
§ 5.10. QR-разложение матрицы. Методы вращений и отражений
Метод Гаусса не является единственным методом исключения, используемым для решения систем линейных уравнений и приведения матриц к треугольному виду. Рассмотрим два метода исключения, обладающих в отличие от метода Гаусса гарантированной хорошей обусловленностью — метод вращений и метод отражений. Оба этих метода позволяют получить представление исходной матрицы А в виде произведения ортогональной матрицы Q на верхнюю треугольную матрицу R:
Представление (5.79) — это QR-разложение матрицы на множители.
1. Метод вращений.
Опишем прямой ход метода. На 1-м шаге неизвестное
исключают из всех уравнений, кроме первого. Для исключения
из второго уравнения вычисляют числа
обладающие следующими свойствами:
Затем первое уравнение системы заменяют линейной комбинацией первого и второго уравнений с коэффициентами
и
, а второе уравнение — аналогичной линейной комбинацией с коэффициентами
. В результате получают систему
в которой
Заметим, что
в силу специального выбора чисел
(см. равенства (5.81)).
Естественно, что в случае
исходная система уже имеет вид (5.82) и в исключении неизвестного
из второго уравнения нет необходимости. В этом случае полагают
Как нетрудно видеть, преобразование исходной системы (5.1) к виду (5.82) эквивалентно умножению слева матрицы А и правой части 6 на матрицу
имеющую вид
где
Введем обозначение
для полученной верхней треугольной матрицы
Она связана с исходной матрицей А равенством
где
матрица результирующего вращения. Заметим, что матрица
ортогональна как произведение ортогональных матриц. Обозначая
получаем
-разложение матрицы А.
Обратный ход метода вращений проводится точно так же, как и для метода Гаусса.
Метод вращений обладает замечательной численной устойчивостью. Для него оценка (5.43) справедлива с коэффициентом
Однако этот метод существенно более трудоемок по сравнению с методом Гаусса. Получение
-разложения для квадратной матрицы А общего вида требует примерно
арифметических операций.
Пример 5.18. Используя метод вращений, решим на 6-разрядной десятичной ЭВМ систему уравнений
Прямой ход. 1-й шаг. Исключим
из второго уравнения. Для этого вычислим
по формулам (5.80):
Преобразуя коэффициенты первого и второго уравнений по формулам (5.83), приходим к системе
Далее вычислим коэффициенты
по формулам (5.84):
Заменяя первое и третье уравнения их линейными комбинациями с коэффициентами
соответственно, получим систему
2-й шаг. В полученной системе имеем
Поэтому
Заменяя второе и третье уравнения системы их линейными комбинациями с коэффициентами
соответственно, приходим к системе
Обратный ход дает последовательно значения
2. Метод отражений.
Матрицами Хаусхолдера (или отражений) называются квадратные матрицы вида
Здесь
вектор-столбец в
имеющий единичную длину. Матрица
V является ортогональной и симметричной. Умножение на нее называют преобразованием Хаусхолдера (или отражением). Действие матрицы
V на вектор можно интерпретировать как ортогональное отражение вектора в
относительно гиперплоскости, проходящей через начало координат и имеющей нормальный вектор, равный 10.
Как и вращения, отражения используются для обращения в нуль элементов преобразуемой матрицы. Однако здесь с помощью одного отражения можно обратить в нуль не один элемент матрицы, а целую группу элементов некоторого столбца или строки. Поэтому, являясь почти столь же устойчивым, как и метод вращений, метод отражений позволяет получить QR-разложение квадратной матрицы общего вида примерно за
арифметических операций, т.е. в полтора раза быстрее. Изложение самого метода можно найти, например, в [9].