Лабораторная работа №3. Метод QR-разложения

Тема:Численные методы решения систем линейных уравнений.

Лабораторная работа №3

Метод QR-разложения

Цель работы:

· Знакомство с алгоритмом QR-разложения матрицы коэффициентов;

· Применение метода QR-разложения к решению систем линейных уравнений;

· Использование возможностей системы MATHCAD для выполнения QR-разложения.

Постановка задачи:

Найти решение системы линейных уравнений с помощью метода QR-разложения, где

– матрица коэффициентов размера ,

, - столбец неизвестных и столбец свободных членов соответственно.

Описание метода:

Метод QR- разложения заключается в представлении матрицы коэффициентов в виде произведения ортогональной матрицы на верхнюю треугольную , .

Пусть к шагу с номером найдены матрицы и , такие, что матрица имеет вид ,

- ортогональная матрица и . На первом шаге . Составим квадратную матрицу

, где .

Пусть

, , .

Возьмем число таким, что ( ), а знак числа противоположен знаку числа . Если , то возьмем положительным. Пусть . Очевидно, что – единичный вектор. Положим , - ортогональная матрица (это легко проверить). Преобразование с матрицей будет преобразованием отражения относительно плоскости с нормальным вектором и будет вектор переводить в вектор .

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

Образуем матрицу следующего вида

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

В этой матрице и под главной диагональю в столбцах стоят нули. Учитывая, что , получим . Положим . Так как произведение ортогональных матриц является матрицей ортогональной, то матрица – ортогональная. Итак, . Шаг с номером завершен. Выполнив таких шагов, получим, что , где – верхняя треугольная. Отсюда . Обратная к ортогональной матрице, т.е. транспонированная матрица, является ортогональной. Поэтому, обозначив , получим требуемое QR-разложение.

Преимуществом QR-разложения является то, что элементы матрицы R не могут сильно превышать по модулю элементы матрицы A. Действительно, , т.е. каждый столбец матрицы R получается умножением ортогональной матрицы на соответствующей столбец матрицы A. Так как при умножении ортогональной матрицы на столбец вторая норма столбца не меняется, то нормы столбцов матрицы R совпадают с нормами соответствующих столбцов матрицы A. Норма каждого столбца ортогональной матрицы равна 1. Поэтому все элементы матрицы Q по модулю не больше 1.

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

С помощью QR-разложения можно найти разложение прямоугольной матрицы коэффициентов. Если матрица А размера m×n, где , то матрица будет иметь размер , а матрица .

Недостатком метода служит то, что его реализация требует в два раза больше операций, чем LU-разложение. Кроме того QR-разложение требует дополнительную память для хранения матрицы Q, в то время, как в LU-разложении матрицы L и U могут формироваться в памяти компьютера на месте, занимаемом матрицей A. Впрочем, недостатки, как и преимущества, сказываются только при больших значениях n.

Ход лабораторной работы:

1. Ввести матрицу коэффициентов A (n×n) и столбец свободных членов b.

2. На первом шаге .