Программа для решения методом lu разложения. Решение матричного уравнения или системы линейных уравнений AX=B онлайн

Пусть дано уравнение Ax=b, тогда LU-разложением называется разложение вида: LUx=b, где Ux=y, а Ly=b. При этом: LU=A, этим равенством можно пользоваться для проверки на правильность разложения.

Этот метод лежит в основе метода Гаусса.

Матрица U верхнетреугольная, по диагонали единицы, поэтому ее определитель равен единице. Матрица L — нижнетреугольная, ее определитель равен произведению элементов, расположенных по диагонали.

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

Пусть A 0 =, тогда

каждый элемент матриц L и U можно выразить следующими формулами:

n — размерность матрицы A (nxn)

Элементы по диагонали:

где (k-1) — номер итерации, k=1…n, (2)

Остальные элементы:

Где k=1…n, i, j=k+1…n. (4)

Обратный ход метода предполагает вычисление двух уравнений:

Из последнего уравнения получаем ответ.

Разберем первое уравнение:

,, значит, общая формула для поиска элементов столбца y выглядит следующим образом:

эта формула нам потом понадобится для вычисления y в программе, поэтому я убрал из общей формулы нахождение первого элемента y 1 , так как будут производиться лишние вычисления.

Разберем второе уравнение:

Здесь x n =y n , поэтому нет смысла включать его в общую формулу, по которой будут вычисляться все x , кроме последнего:

Алгоритм:

1. Вводим str/stlb — количество строк/столбцов, A — элементы расширенной матрицы, копируем A в A0;

4. Формируем матрицы L:=A0, U:=1, сначала диагональные элементы, i:=n+1 (по формулам (1), (2))

6. Формируем остальные элементы: L:=A0 и U:=A0/A0 (по формулам (3),(4)), присваиваем t:=A0/A0, j:=n+1

8. A0:=A0-A0*t, увеличиваем j на единицу, переходим к п.7

9. i:=i+1 переходим к п.5

10. n:=n+1 переходим к п.3

11. Выводим матрицы L, U

13. Выводим y;

15. Выводим x;

16. Проверки на невязку, заканчиваем алгоритм.

Описание входной информации: Str (Stlb) — количество строк (столбцов) в расширенной матрице, A — матрица A (i — строки, j — столбцы).

Описание выходной информации: x — матрица-ответ.

Метод Гаусса предназначен для решения систем линейных алгебраических уравнений (СЛАУ). Его описание приводится в предположении, что число неизвестных равно числу уравнений и что определитель матрицы коэффициентов системы отличен от нуля (матрица невырожденная).

Пусть задана СЛАУ (запись в матричном виде) Ax = b , где

, ,.

Составляется расширенная матрица системы
. С элементами этой матрицы выполняются следующие операции, которые обычно называются элементарными:

можно менять местами строки;

к одной строке можно прибавлять другую, умноженную на любое число;

можно умножать строку на любое число, отличное от нуля (используется в основном при вычислениях вручную, на бумаге).

Цель выполнения элементарных операций – получить под главной диагональю матрицы A нули. Этой цели добиваемся последовательными переходами от одной матрицы к другой после выполнения определенного цикла элементарных операций.

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

К третьей строке прибавляем первую строку, умноженную на число
, т.е.
,
,
, при этом окажется, что
. Таким же образом преобразуем все строки, т.е. к строке с номеромi прибавляется первая строка, умноженная на число
,
,
,
,
. В результате этих вычислений получим матрицу

Первый шаг прямого хода метода Гаусса на этом закончен.

Далее переходим к матрице
, добиваясь нулей во втором столбце, начиная с третьей строки. Строки 1,2 оставим без изменений. Полагаем
,
. К строке с номеромматрицы
прибавляем вторую строку, умноженную на число
,
,
,
,
. В действительностиj меняется от 2 до n , так как первый столбец в результате этих действий останется без изменений. Получим матрицу

На этом закончен второй шаг прямого хода метода Гаусса.

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

у которой под главной диагональю стоят одни нули. Прямой ход метода Гаусса закончен.

Матрице
соответствует система уравнений

равносильная исходной. Ее решения легко найти по формулам
,
(значениеуже найдено) и так далее. Общая формула:

Метод Гаусса требует выполнения порядка арифметических операций. Это один из самых экономичных методов.

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

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

Элементы этих матриц находятся по формулам в том порядке, в котором здесь эти формулы выписаны:

Такое разложение дает следующий результат:

Положим
, тогда
. Получили треугольную систему уравнений

Из этой системы последовательно находим
,
. Знаяy , находим x из треугольной системы

Откуда
,
.

И в методе Гаусса при решении систем линейных уравнений, и в LU-разложении матрицы приходится выполнять деление на элемент матрицы. Если этот элемент нуль, то процесс остановится, хотя матрица А не вырождена, и решение системы существует. Проблемы возникают и в том случае, когда элемент, на который приходится делить, очень маленький. В этой ситуации предыдущие ошибки, возникающие неизбежно при округлении чисел компьютером, резко увеличиваются и могут стать недопустимо большими. Если действия выполняются на бумаге, то вы просто меняете строки матрицы местами. Аналогично поступают и при программировании метода Гаусса и LU-разложения. При этом обычно выбирают такую строку, где элемент, на который нужно делить, является наибольшим по модулю.

При таком алгоритме при LU-разложении уже получается три матрицы P , L , U . Матрицы L , U – нижняя и верхняя треугольные соответственно,
,
,P – матрица перестановок, т.е. квадратная матрица порядка n , в каждой строке и в каждом столбце которой только один элемент равен 1, а все остальные элементы – нули. Эти матрицы связаны соотношением
. Такое разложение всегда возможно, если
.

Если мы получим такое разложение, то для решения системы
обе части умножим слева на матрицуP ,
, и заменимPA на LU ,
. Далее действия такие же, как описано выше. ИменноLU-разложение используется в системе MATHCAD для решения систем линейных уравнений.

Или ступенчатая матрица.

Процедура LU - разложения

Пусть A m×n А приписываем единичную матрицу E порядка n×n . Применяем к матрице A|E метод исключения Гаусса . Если на каком то этапе Гауссово исключения ведущий элемент равен нулю, и существует ненулевой элемент, расположенный ниже ведущего элемента, то LU - разложение данной матрицы невозможно. Если же элементы ниже ведущего элемента нулевые, то выбираем новый ведущий элемент той же строки и следующего столбца.

Приводим матрицу A|E к треугольному или ступенчатому виду. Получим матрицу U|L 0 , где U - верхняя треугольная или ступенчатая матрица, а L 0 - нижняя треугольная матрица. Заметим, что полученная матрица L 0 приводит A к треугольному или ступенчатому виду:

(3)

Как мы отметили, не всегда можно проводить LU -разложение матрицы. Но LUP - разложение всегда возможно.

LUP-разложение матрицы A - это представление матрицы A в виде произведения

где L -нижняя треугольная матрица, U - верхняя треугольная или ступенчатая матрица, P - матрица перестановок (матрица перестановок - эта матрица, полученная из единичной матрицы перестановкой некоторых строк или столбцов).

Процедура LUP - разложения

Пусть A прямоугольная матрица порядка m×n любого ранга. С правой стороны матрицы А приписываем единичную матрицу E порядка n×n . Применяем к матрице A|E матод исключения Гаусса c выбором наибольшего по модулю ведущего элемента. Если на каком то этапе исключения ведущий элемент равен нулю, то процедуру останавливаем. Получим матрицу U|L 0 . Тогда имеют место равенства (1) и (2). Но в общем случае L 0 и, следовательно, не являются нижними треугольными матрицами, если при применении Гауссово исключения строки переставлялись.

Далее допустим, что мы знаем, как построить матрицу A 1 из матрицы A переставляя строки так, что при применении Гауссово исключения c выбором максимального по модулю ведущего элемента относительно матрицы A 1 не понадобилась переставление строк. Выбираем матрицу перестановок так, что

Строим матрицу A 1 |E и применяем Гауссово исключение. Получим матрицу U|L 1 . Тогда

где L 1 и нижние треугольные матрицы т.к. при применении Гауссово исключения строки матрицы A 1 не переставлялись.

Из (4) и (5) имеем:

Обозначим.

Наша задача найти L и U , без построения A 1 .

Из (2) и (4) имеем:

Тогда, учитывая второе равенство (5), получим:

Следовательно

Получили, что для LUP-разложения нужно применить Гауссово исключение c выбором максимального по модулю ведущего элемента относительно матрицы A|E . Получим матрицу . Вычисляем обратную матрицу . Вычисляем L из выражения (9).

С помощью матричного онлайн калькулятора вы можете сложить , вычитать , умножить , транспонировать матрицы, вычислить обратную матрицу, псевдообратную матрицу, ранг матрицы, определитель матрицы, m-норму и l-норму матрицы, возвести матрицу в степень , умножить матрицу на число , сделать скелетное разложение матрицы, удалить из матрицы линейно зависимые строки или линейно зависимые столбцы , проводить исключение Гаусса , решить матричное уравнение AX=B , сделать LU разложение матрицы , вычислить ядро (нуль пространство) матрицы , сделать ортогонализацию Грамма-Шмидта и ортонормализацию Грамма-Шмидта .

Матричный онлайн калькулятор работает не только с десятичными числами, но и с дробями. Для ввода дроби нужно в исходные матрицы и вводить числа в виде a или a /b , где a и b целые или десятичные числа (b положительное число). Например 12/67, -67.78/7.54, 327.6, -565.

Кнопка в верхем левом углу матрицы открывает меню (Рис.1) для преобразования исходной матрицы (создание единичной матрицы , нулевой матрицы или очищать содержимое ячеек ).

При вычислениях пустая ячейка воспринимается как нуль.

Для операций с одной матрицей (т.е. транспонирование, обратное, псевдообратное, скелетное разложение и т.д.) сначала выбирается конкретная матрица с помощью радиокнопки .

Кнопки Fn1, Fn2 и Fn3 переключают разные группы функциий.

Нажимая на вычисленных матрицах открывается меню (Рис.2), что позволяет записать данную матрицу в исходные матрицы и , а также преобразовать на месте элементы матрицы в обыкновенную дробь, смешанную дробь или в десятичное число.

Вычисление суммы, разности, произведения матриц онлайн

сумму , разность или произведение матриц . Для вычисления суммы или разности матриц, необходимо, чтобы они были одинаковой размерности, а для вычисления произведения матриц, количество столбцов первой матрицы должен быть равным количеству строк второй матрицы.

Для вычисления суммы, разности или произведения матриц:

Вычисление обратной матрицы онлайн

Матричным онлайн калькулятором можно вычислить обратную матрицу . Для того, чтобы существовала обратная матрица, исходная матрица должна быть невырожденной квадратной матрицей.

Для вычисления обратной матрицы:

Для подробного вычисления обратной матрицы по шагам, пользуйтесь этим калькулятором для вычисления обратной матрицы . Теорию вычисления обратной матрицы смотрите .

Вычисление определителя матрицы онлайн

Матричным онлайн калькулятором можно вычислить определитель матрицы . Для того, чтобы существовал определитель матрицы, исходная матрица должна быть невырожденной квадратной матрицей.

Для вычисления определителя матрицы:

Для подробного вычисления определителя матрицы по шагам, пользуйтесь этим калькулятором для вычисления определителя матрицы . Теорию вычисления определителя матрицы смотрите .

Вычисление ранга матрицы онлайн

Матричным онлайн калькулятором можно вычислить ранг матрицы .

Для вычисления ранга матрицы:

Для подробного вычисления ранга матрицы по шагам, пользуйтесь этим калькулятором для вычисления ранга матрицы . Теорию вычисления ранга матрицы смотрите .

Вычисление псевдообратной матрицы онлайн

Матричным онлайн калькулятором можно вычислить псевдообратную матрицу . Псевдообратная к данной матрице всегда существует.

Для вычисления псевдообратной матрицы:

Удаление линейно зависимых строк или столбцов матрицы онлайн

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

Для удаления линейно зависимых строк или столбцов матрицы:

Скелетное разложение матрицы онлайн

Для проведения скелетного разложения матрицы онлайн

Решение матричного уравнения или системы линейных уравнений AX=B онлайн

Матричным онлайн калькулятором можно решить матричное уравнение AX=B по отношению матрицы X. В частном случае, если матрица B является вектор-столбцом, то X , будет решением системы линейных уравнений AX=B.

Для решения матричного уравнения:

Учтите, что матрицы и должны иметь равное количество строк.

Исключение Гаусса или приведение матрицы к треугольному (ступенчатому) виду онлайн

Матричный онлайн калькулятор проводит исключение Гаусса как для квадратных матриц, так и прямоугольных матриц любого ранга. Сначала проводится обычный метод Гаусса. Если на каком то этапе ведущий элемент равен нулю, то выбирается другой вариант исключения Гаусса с выбором наибольшего ведущего элемента в столбце.

Для исключения Гаусса или приведения матрицы к треугольному виду

LU-разложение или LUP-разложение матрицы онлайн

Данный матричный калькулятор позволяет проводить LU-разложение матрицы (A=LU) или LUP-разложение матрицы (PA=LU) , где L нижняя треугольная матрица, U-верхняя треугольная (трапециевидная) матрица, P- матрица перестановок. Сначала программа проводит LU разложение, т.е. такое разложение, при котором P=E, где E-единичная матрица (т.е. PA=EA=A). Если это невозможно, то проводится LUP-разложение. Матрица A может быть как квадратной, так и прямоугольной матрицей любого ранга.

Для LU(LUP)-разложения: