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

Предположим, что нам удалось привести данную матрицу A к виду

A=LU , (1)

где L – матрица вида , U – матрица вида .

Подставляя полученное разложение в исходную систему Ax=b, получим:

LUx=b. (2)

Пусть

Ux=y, (3)

тогда, подставляя (3) в (2), получаем:

Ly=b. (4)

Таким образом, решение данной системы сводится к трем этапам /2/:

1. 
   нахождение элементов матриц L и U из матрицы A;
   
2. 
   решение системы (4) с матрицей L;
   
3. 
   решение системы (3) с матрицей U.
   

Учитывая равенство (1) и умножая последовательно столбцы матрицы L на строки матрицы U получаем систему из 9 уравнений и 9 неизвестных (элементы матриц L и U):

a₁₁=l₁₁;

a₂₁=l₂₁;a₂₂=l₂₂+l₂₁*u₁₂;a₁₂=l₁₁*u₁₂;



a₁₃=l₁₁*u₁₃;a₂₃=l₂₁*u₁₃+l₂₂*u₂₃.

Находим элементы матриц L и U:

Решим систему (4). Ее решение сводится к решению следующей системы уравнений:

b₁=l₁₁*y₁

b₂=l₂₁*y₁+ l₂₂*y₂

b₃=l₃₁*y₁+ l₃₂*y₂+ l₃₃*y₃

Вектор y будет выглядеть следующим образом:y=

Следующий этап – решение системы Ux=y. Решение сводится к решению следующей системы:

x₁+u₁₂*x₂+u₁₃*x₃=y₁

x₂+u₂₃*x₃=y₂

x₃=y₃

Находим вектор решения данной системы.x=

Чтобы найти определитель матрицы A, перемножим числа, стоящие на главной диагонали матрицы L.

detA=a₁₁*a₂₂*a₃₃

Получение обратной матрицы

Имеем матрицу A=LU,

где L – матрица вида , U – матрица вида .

Решим систему LU=E, где E – единичная матрица.

Представим единичную матрицу как набор вектор-столбцов:

e₁=, e₂=, e₃=.

Решим последовательно системы Ly=e₁, Ly=e₂, Ly=e₃ на основе формул, полученных в п. 2.2.

Теперь решаем последовательно системы Ux=y₁, Ux=y₂, Ux=y₃ .

СПИСОК ЛИТЕРАТУРЫ

1. 
   Демидович Б.П., Марон И.А. Основы вычислительной математики. — М.: Наука, 1970.
   
2. 
   Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения). — М.: Высшая школа, 2000.
   

1. ПРИМЕР РАБОТЫ ПРОГРАММЫ

Рис. 1. Результат работы программы. Вычисление корней

2. ВЫВОДЫ

Метод Гаусса решения систем линейных алгебраических уравнений позволяет с заданной точностью отыскать решение системы. К его преимуществам можно отнести простоту реализации на ЭВМ.

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