Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Метод 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-разложение матрицы коэффициентов.

Создаем единичную матрицу : Задаем цикл («..» ставится при нажатии «;»): Находим коэффициенты , :
Находим матрицу (произведение матриц требует порядка n3 действий. Оптимальнее, вместо вычисления произведения, присвоить элементам матрицы те, которые не изменяются. Или же новую матрицу можно не создавать, а изменять изначальную), она имеет вид . Выполнили всего порядка n2 действий:
Аналогично находим матрицы L2 и A2:
Создаем матрицу L:
Получили матрицу U: Разложение найдено верно:
Находим решение системы :
Находим решение системы :
Решение найдено верно:

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

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

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

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

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

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

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

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

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

 

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

1 вариант:

2 вариант:

3 вариант:

4 вариант:

5 вариант:

6 вариант:

7 вариант:

8 вариант:

9 вариант:

10 вариант:

11 вариант:

12 вариант:

13 вариант:

14 вариант:

15 вариант:

 

 







Дата добавления: 2015-08-12; просмотров: 7540. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2020 год . (0.009 сек.) русская версия | украинская версия