ПК для ТЕБЯ

Теоретическая часть

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

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

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

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

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

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

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

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

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

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

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

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

1.     Ly=b

2.     Ux=y

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

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

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

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

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

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

Алгоритм:

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

2.     n:=1

3.     Если n<=str, тогда п.4, иначе п.11

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

5.     Если i<=str тогда п.6, иначе п.10

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

7.     Если j<=str тогда п.8, иначе п.9

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

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

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

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

12.     Считаем y₁:=A[1,stlb]/L[1,1]; далее y по формуле (5)

13.     Выводим y;

14.     Считаем последний x[str]:=y[str]; далее по формуле (6)

15.     Выводим x;

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

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

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

Ссылки для скачивания:LU-разложение

Вернуться назад