Метод 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 в строках и столбцах с номерами . В этом случае будет получено разложение , где и - матрицы перестановок. Систему уравнений тогда решаем так: , , , , . Ход лабораторной работы:
|