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

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

Цель работы:

· Знакомство с алгоритмом 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. На первом шаге .

3. Пусть .

4. Создать матрицу .

5. Создать векторы .

6. Найти число .

7. Найти единичный вектор .

8. Найти матрицы и . Увеличить j на 1: . Если перейти к шагу 9, иначе к шагу 4.

9. Ввести обозначение , создать матрицу .

10. Найти решение системы .

11. Найти решение системы .

12. Выполнить проверку.

1) Для проверки разложения:

Вычислить произведение матриц QR, сравнить с матрицей A.

2) Для проверки решения:

Посмотреть выполняется ли равенство ?

 

Пример:

Найти решение системы линейных уравнений , где

Получим QR-разложение матрицы коэффициентов:

На первом шаге :

Создаем векторы , :

Находим число . Функция определяет знак элемента :

Найдем единичный вектор :

, - ортогональная матрица:

Составляем матрицу следующего вида . На первом шаге :

Найдем матрицу . Заметим, что матрица единичная, следовательно :

Увеличиваем j на 1. Составляем матрицу . Воспользуемся функцией Mathcad submatrix:

Найдем матрицу : Матрица (см. описание метода):

Аналогично находим матрицы и :

Составим матрицу :

Решим систему уравнений :

Решив вторую систему , получим:

Проверка:

 

Требования к отчету:

1. Отчет должен быть представлен в электронном или бумажном виде;

2. Отчет должен содержать:

· Расчеты и проверку.

3. Ответы на вопросы:

· Какова точность найденного решения;

· Преимущество метода QR-разложения по сравнению с

LU-разложением;

· Недостатки метода.

 

Задания для самостоятельной работы:

1 вариант:

2 вариант:

3 вариант:

4 вариант:

5 вариант:

6 вариант:

7 вариант:

8 вариант:

9 вариант:

10 вариант:

11 вариант:

12 вариант:

13 вариант:

14 вариант:

15 вариант: