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

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

Цель работы:

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

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

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

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

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

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

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

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

Метод LUP-разложения – это LU-разложение с выбором главного (ведущего) элемента. В этом методе ищутся три матрицы: P, L, U, где L – нижняя треугольная матрица с единицами на диагонали, U – верхняя треугольная матрица, P – матрица перестановок.

Определение. Матрицей перестановок называется матрица, у которой в каждом столбце и в каждой строке один элемент равен единице, остальные – нули.

Если в матрице перестановок P в строке с номером i единица стоит в столбце с номером j, то в матрице строкой с номером i будет строка с номером j матрицы А, а в матрице столбцом с номером j будет служить столбец с номером i матрицы А. Поэтому умножение на матрицу перестановок не требует выполнения арифметических операций. Кроме того матрица перестановок является ортогональной матрицей. Произведение двух матриц перестановок дает снова матрицу перестановок.

В основном метод LUP-разложения совпадает с LU-разложением.

Пусть к шагу с номером j, , построена матрица , имеющая вид

,

матрицы , имеющие вид

,

и матрицы перестановок , такие, что

,

если j= 1, то считаем . Среди элементов столбца с номером j матрицы , стоящих не выше диагонали, находим главный элемент, т.е. наибольший по модулю. Пусть это будет элемент с номером при . Пусть – матрица перестановок, отличающаяся от единичной только j -ой и k -ой строками, причем . Положим . Матрица получается из матрицы перестановкой строк с номерами j и k. В матрице элемент будет наибольшим по модулю среди элементов столбца с номером j, стоящих ниже. Если , то матрица А – вырожденная и решение системы невозможно.

Далее находим матрицу , у которой

, где .

В результате умножения получим нули в столбце с номером j столбце, ниже диагонали. Обозначим

.

Тогда в силу

.

Положим

,

.

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

,

и т.д. В результате получим

.

Пусть Тогда

,

требуемый вид получен. Шаг с номером j завершен.

После выполнения шага получаем

.

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

Чтобы применить полученное разложение к решению системы уравнений , умножим обе части равенства слева на матрицу . Получим . Используя разложение, имеем и далее решаем треугольные системы уравнений , . Метод LU-разложения с выбором главного элемента в точной арифметике позволяет решить любую систему уравнений с невырожденной матрицей. Точная арифметика подразумевает, что вычисления ведутся без округления, а конечная, что вычисления ведутся в десятичных дробях с округлением до какого-то знака. Компьютер считает всегда в конечной арифметике.

К недостаткам метода следует отнести возможность возникновения очень больших элементов в матрицах и по сравнению с элементам матрицы . Но этот недостаток играет существенную роль только при больших n. Частично проблему неоправданного увеличения элементов матриц можно решить, выбирая главный элемент не только по столбцу, но и по всем элементам матрицы, стоящим на шаге с номером j в строках и столбцах с номерами . В этом случае будет получено разложение , где и - матрицы перестановок. Систему уравнений тогда решаем так:

,

,

,

,

.

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