Практика_3 Кожин Численные
.doc
Практика №3
LU разложение матрицы.
Если есть матрица
|
а11 |
а12 |
... |
а1n |
|
а21 |
а22 |
... |
... |
|
... |
... |
... |
... |
|
аn1 |
аn2 |
... |
аnn |
Для которой det(A) ≠0 , то существует единственная матрица L нижнее треугольная и верхне треугольная U такие что
LU=А
1 0 ... 0 L21 1 ... ... ... ... ... ... Ln1 Ln2 ... 1
U11 U12 ... U1n 0 U22 ... ... ... ... ... ... 0 0 ... Unn
а11 а12 ... а1n а21 а22 ... ... ... ... ... ... аn1 аn2 ... аnn
× =
Алгоритм разложения с помощью вспомогательной матрицы
-
Строим матрицу М1
по диагонали 1
первый столбец - аi1/ а11
все остальные элементы матрицы равны 0
1 0 ... 0 -
а21/
а11 1 ... ... ... ... ... ... -
аn1/
а11 0 ... 1
-
строим матрицу А1 = М1 × А
1 0 ... 0 m21 1 ... ... ... ... ... ... mn1 0 ... 1
а11 а12 ... а1n а21 а22 ... ... ... ... ... ... аn1 аn2 ... аnn
а111 а112 ... а11n 0 а122 ... ... ... ... ... ... 0 а1n2 ... а1nn
× =
По матрице А1 строим новую матрицу М2 в которой
по диагонали 1
второй столбец ниже диагонали - а1i2/ а122
все остальные элементы матрицы равны 0
1 0
... 0 0 1
... ... 0 -
а132/
а122 1 ... ... … …
1 0 0 -
а1n2/
а122 0 0 1
-
строим матрицу А2 = М2 ×А1
-
Продолжаем строить матрицы Мi для очередного столбца и получать новые матрицы Аi. После построения матрицы Мn-1 для предпоследнего столбца и получения матрицы Аn-1 матрица будет иметь верхнетреугольный вид - U матрица. Матрица L строится из Мi
1 0 ... 0 -m12 1 ... ... ... ... ... ... -mn1 -mn2 ... 1
U11 U12 ... U1n 0 U22 ... ... ... ... ... ... 0 0 ... Unn
Второй метод построения матриц L и U
-
первая строка матрицы переписывается из матрицы A
a11 a12 ... a1n 0 0 ... ... ... ... ... ... 0 0 ... 0
-
первый столбец ниже диагонали заполняется значениями аi1/ а11
a11 a12
a1n а21/
а11 0 ... ... ... ... ... ... аn1/
а11 0 ... 0
-
Заполняем вторую строку справа от диагонали
a11 u12
u1n l21 0 ... ... ... ... ... ... ln1 0 ... 0
значениями a2j-u1j*l21 при этом a2j берется из исходной таблицы,
-
Заполняем второй столбец ниже диагонали
a11 a12
a1n l21 u22 ... u2n... ... ... ... ... ... ... ... ... ln1 0 ... 0
значениями (aj2-a12*lj1)/u22 при этом a2j берется из исходной таблицы
5) Действуем аналогично для следующей строки и столбца, заполняя их справа и ниже диагонали в соответствии с пунктами 3 и 4. При заполнении строки из соответствующего элемента матрицы А вычитаем сумму произведений элементов выше данного на соответствующие элементы справа от начала
u11 u12
u14
u1n l21 u22
u24
u2n l31 l32
u34
u3n l41 l42
l51 l52
... ...
... ln1 ln2
0
При заполнении столбца из соответствующего элемента матрицы А вычитаем сумму произведений элементов слева на соответствующие элементы выше от начала и делим на диагональный элемент
u11 u12 u13 u14
u1n l21 u22 u23 u24
u2n l31 l32 u33 u34
u3n l41 l42
l51 l52 u53
... ...
... ln1 ln2
0
Определитель матрицы А будет равен определителю матрицы U и равен произведению диагональных элементов матрицы U
При вычислении матрицы М осуществляется деление на диагональный элемент. Если очередной диагональный элемент равен 0, можно переставить строки местами так, что бы диагональный элемент был отличен он 0. В этом случае определитель исходной матрицы будет равен
det(A)=(-1)k det(U)=∏uii i=1..n
где k количество перестановок строк и столбцов
Пример ( через вспомательную матрицу)
|
|
|
A |
|
|
|
|
M1 |
|
|
|
|
M1*A |
|
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
1 |
0 |
0 |
0 |
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
-0,4 |
-1 |
-0,8 |
-0,2 |
|
-0,4 |
1 |
0 |
0 |
|
0 |
-0,84 |
-0,56 |
0,12 |
|
-0,6 |
-0,6 |
-1 |
-0,4 |
|
-0,6 |
0 |
1 |
0 |
|
0 |
-0,36 |
-0,64 |
0,08 |
|
-0,2 |
-0,4 |
-0,4 |
-1 |
|
-0,2 |
0 |
0 |
1 |
|
0 |
-0,32 |
-0,28 |
-0,84 |
|
|
|
|
|
|
|
|
M2 |
|
|
|
|
M2*A |
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
|
|
|
|
|
0 |
1 |
0 |
0 |
|
0 |
-0,84 |
-0,56 |
0,12 |
|
|
|
|
|
|
0 |
-0,43 |
1 |
0 |
|
0 |
0 |
-0,4 |
0,029 |
|
|
|
|
|
|
0 |
-0,38 |
0 |
1 |
|
0 |
0 |
-0,07 |
-0,89 |
|
|
|
|
|
|
|
|
M3 |
|
|
|
U |
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
|
|
|
|
|
0 |
1 |
0 |
0 |
|
0 |
-0,84 |
-0,56 |
0,12 |
|
|
|
|
|
|
0 |
0 |
1 |
0 |
|
0 |
0 |
-0,4 |
0,029 |
|
|
|
|
|
|
0 |
0 |
-0,17 |
1 |
|
0 |
0 |
0 |
-0,89 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
L |
|
|
|
LU |
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
|
|
|
|
|
0,4 |
1 |
0 |
0 |
|
0,4 |
-0,84 |
-0,56 |
0,12 |
|
|
|
|
|
|
0,6 |
0,429 |
1 |
0 |
|
0,6 |
0,429 |
-0,4 |
0,029 |
|
|
|
|
|
|
0,2 |
0,381 |
0,167 |
1 |
|
0,2 |
0,381 |
0,167 |
-0,89 |
Второй метод построения матриц L и U
Для матрицы
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
-0,4 |
-1 |
-0,8 |
-0,2 |
|
-0,6 |
-0,6 |
-1 |
-0,4 |
|
-0,2 |
-0,4 |
-0,4 |
-1 |
|
|
|
|
|
|
- |
-0,4 |
-0,6 |
-0,8 |
|
0,4 |
|
|
|
|
0,6 |
|
|
|
|
0,2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
0,4 |
-0,84 |
-0,56 |
0,12 |
|
0,6 |
|
|
|
|
0,2 |
|
|
|
|
|
|
|
|
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
0,4 |
-0,84 |
-0,56 |
0,12 |
|
0,6 |
0,428571 |
|
|
|
0,2 |
0,380952 |
|
|
|
|
|
|
|
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
0,4 |
-0,84 |
-0,56 |
0,12 |
|
0,6 |
0,428571 |
-0,4 |
0,028571 |
|
0,2 |
0,380952 |
0,166667 |
|
|
|
|
|
|
|
-1 |
-0,4 |
-0,6 |
-0,8 |
|
0,4 |
-0,84 |
-0,56 |
0,12 |
|
0,6 |
0,428571 |
- |
0,028571 |
|
0,2 |
0,380952 |
0 |
- |
1
0,4
,166667
0,89048