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

Цель работы:

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

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

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

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

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

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

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

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

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

Доказано, что если главные миноры матрицы A отличны от нуля, то разложение всегда возможно и единственно.

При наличии LU-разложения решение системы сводится к решению двух систем с треугольной матрицей: .Первая система имеет вид:

 

Из первого уравнения находим , из второго – , и т.д. Запишем общую формулу:

.

Затем составляется система :

Из последнего уравнения этой системы найдем , из предпоследнего – , и т.д. Получим формулу для решения системы :

.

Для построения LU-разложения матрицы A создаются последовательно матрицы , где

и вычисляются матрицы . Легко проверить, что умножение произвольной матрицы М порядка n на слева означает, что к строке с номером k, , прибавляется строка с номером j, умноженная на . Умножая матрицу на мы добиваемся, чтобы в j- ом столбце матрицы под диагональю стояли нули. Для этого берем

.

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

Основное преимущество метода LU-разложение заключается в том, что столбец свободных членов при решении системы линейных алгебраических уравнений используется только на заключительном этапе, а наиболее трудоемкие операции по вычислению матриц L и U не требует знания вектора свободных членов b. Таким образом, если решается серия СЛАУ с одной и той же матрицей коэффициентов A, но разными правыми частями b, то очень выгодно один раз вычислить LU-разложение матрицы A, а уже за тем решать конкретные системы, меняя столбец свободных членов.

Если матрица A СЛАУ содержит много нулей, то использование LU-разложения может существенно сократить объем вычислений. Можно проверить, что если какая-то строка матрицы A до первого ненулевого элемента содержит m нулей, то та же строка в матрице L будет содержать в начале m нулей. Если какой-то столбец в матрице A содержит до первого ненулевого элемента p нулей, то в матрице U этот столбец в своем начале будет иметь p нулей.

Но наряду с достоинствами метод LU-разложения имеет и недостатки. Алгоритм LU-разложения может остановиться даже при невырожденной матрице A из-за деления на нуль при . Кроме того при ненулевом, но малом значении ошибки округлений в результате деления на могут сильно возрастать и искажать получаемое решение.

 

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

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

2. Последовательно создать матрицы и вычислить матрицы . Элементы матриц находятся по формулам: ; ; …; , где верхний индекс j элемента – индекс матрицы , а нижние индексы i, k – номер строки и номер столбца соответственно.

3. Нашли .

4. Найти матрицу . Заметим, что в действительности обратную матрицу вычислять не приходится. По правилу обращения произведения получим

.

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

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

6. Найти решение системы , записать решение исходной системы линейных уравнений.

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

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

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

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

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

 

Пример:

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

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

Создаем единичную матрицу : Задаем цикл («..» ставится при нажатии «;»): Находим коэффициенты , :

Находим матрицу (произведение матриц требует порядка n 3 действий. Оптимальнее, вместо вычисления произведения, присвоить элементам матрицы те, которые не изменяются. Или же новую матрицу можно не создавать, а изменять изначальную), она имеет вид . Выполнили всего порядка n 2 действий:

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

Создаем матрицу L:

Получили матрицу U: Разложение найдено верно:

Находим решение системы :

Находим решение системы :

Решение найдено верно:

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

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

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

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

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

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

· Преимущество метода LU-разложения по сравнению с правилом Крамера и использованием обратной матрицы;

· В чем заключается различие между методом Гауса и LU-разложением?

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

 

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

1 вариант:

2 вариант:

3 вариант:

4 вариант:

5 вариант:

6 вариант:

7 вариант:

8 вариант:

9 вариант:

10 вариант:

11 вариант:

12 вариант:

13 вариант:

14 вариант:

15 вариант: