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

 

Пусть  - данная n´ n матрица, - соответственно нижняя и верхняя треугольные матрицы порядка n. Главными минорами матрицы называются миноры элементов главной диагонали матрицы, т.е. миноры Mii, где i=1,2,..n. Справедлива теорема.

Теорема 4.1.  Если все главные миноры квадратной матрицы A отличны от нуля, то существуют нижняя треугольная матрицаL  и верхняя треугольная матрицаU, что A = LU. Если диагонали одной из матриц фиксированы и (ненулевые), то такое разложение единственно.

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

 .                     (4.1)

После умножения приравниваем соответствующие элементы матриц и получим следующую систему nn уравнений:

          (4.2)

относительно nn неизвестных

,                                                      (4.3)

которую решаем следующим образом.

Из первой строки системы уравнений (4.1) находим .

Из оставшейся части первого столбца уравнений (4.1) находим .

Из оставшейся части второй строки уравнений (4.1) находим .

Из оставшейся части второго столбца уравнений (4.1) находим .

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

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

         .                        (4.5)

Замечания. 1. При организации вычислений необходимо предусматривать чередование вычислений по первым и вторым формулам (4.5).

2. При вычислении необходимо, чтобы диагональные элементы были не равны нулю, так как на них приходится делить. Это требование будет выполнятся, если главные миноры матрицы отличны от нуля. Лучше их сравнивать с малой константой (допуском). Отметим, что для матриц с диагональным преобладанием, т.е. таких, для которых

,                                          (4.6)

требование разложения выполняется. 

Алгоритм  LU- разложения матрицы:

Ввод: матрица A[i,j] порядка n.

Вывод: Матрицы L[i,j] и U[i,j] для матрицы A.

Цикл по i: =1, 2, …,n выполнять Цикл по j: =1, 2, …,n выполнять L[i,j]:=0;U[i,j]:=0; конец цикла по j; конец цикла по i;

Цикл по i: =1, 2, …,n выполнять L[i,i]:=1; конец цикла по i;

Цикл по l: =1, 2, …,n выполнять

      Цикл по j: =l, …,n выполнять

              U[l,j]:= A[l,j]; k:=1;

              1. Если k<l, то U[l,j]:= U[l,j]-L[l,k]*U[k,j]; k:= k+1; идти к 1;

     конец цикла по j;

     Если l<n , то

          Цикл по i: =l, …,n выполнять

                   L[i,l]:= A[i,l]; k:=1;

                       2. Если k<l, то L[i,l]:= L[i,l]-L[i,k]*U[k,l]; k:= k+1; идти к 2;

                        Если U[l,l] = 0, то LU-разложение матрицы не существует. Конец.

                       Иначе L[i,l]:= L[i,l]/U[l,l];

          конец цикла по i;

Конец цикла по l;

Конец.