319 lines
10 KiB
Markdown
319 lines
10 KiB
Markdown
---
|
||
id: 5e6decd8ec8d7db960950d1c
|
||
title: LU-розклад матриці
|
||
challengeType: 5
|
||
forumTopicId: 385280
|
||
dashedName: lu-decomposition
|
||
---
|
||
|
||
# --description--
|
||
|
||
Кожну квадратну матрицю $A$ можна розкласти на добуток з нижньої трикутної матриці $L$ та верхньої трикутної матриці $U$, як описано у [LU decomposition](https://en.wikipedia.org/wiki/LU decomposition).
|
||
|
||
$A = LU$
|
||
|
||
Таке представлення матриці є модифікованим методом Гауса.
|
||
|
||
В той час як [розклад Холецького](http://rosettacode.org/wiki/Cholesky decomposition) тільки працює для симетричних, позитивно-визначених матриць, загальніший LU-розклад матриці працює для будь-якої квадратної матриці.
|
||
|
||
Існують декілька алгоритмів для розрахунку $L$ та $U$.
|
||
|
||
Для отримання *алгоритму Крота* для прикладу 3x3, нам необхідно розв'язати наступну систему:
|
||
|
||
\\begin{align}A = \\begin{pmatrix} a\_{11} & a\_{12} & a\_{13}\\\\ a\_{21} & a\_{22} & a\_{23}\\\\ a\_{31} & a\_{32} & a\_{33}\\\\ \\end{pmatrix}= \\begin{pmatrix} l\_{11} & 0 & 0 \\\\ l\_{21} & l\_{22} & 0 \\\\ l\_{31} & l\_{32} & l\_{33}\\\\ \\end{pmatrix} \\begin{pmatrix} u\_{11} & u\_{12} & u\_{13} \\\\ 0 & u\_{22} & u\_{23} \\\\ 0 & 0 & u\_{33} \\end{pmatrix} = LU\\end{align}
|
||
|
||
Зараз нам доведеться розв'язати 9 рівнянь з 12 невідомими. Щоб зробити систему унікальною в розв'язанні, зазвичай діагональні елементи $L$ встановлюються на 1
|
||
|
||
$l\_{11}=1$
|
||
|
||
$l\_{22}=1$
|
||
|
||
$l\_{33}=1$
|
||
|
||
тож ми отримали розв'язуючу систему з 9 невідомих та 9 рівнянь.
|
||
|
||
\\begin{align}A = \\begin{pmatrix} a\_{11} & a\_{12} & a\_{13}\\\\ a\_{21} & a\_{22} & a\_{23}\\\\ a\_{31} & a\_{32} & a\_{33}\\\\ \\end{pmatrix} = \\begin{pmatrix} 1 & 0 & 0 \\\\ l\_{21} & 1 & 0 \\\\ l\_{31} & l\_{32} & 1\\\\ \\end{pmatrix} \\begin{pmatrix} u\_{11} & u\_{12} & u\_{13} \\\\ 0 & u\_{22} & u\_{23} \\\\ 0 & 0 & u\_{33} \\end{pmatrix} = \\begin{pmatrix} u\_{11} & u\_{12} & u\_{13} \\\\ u\_{11}l\_{21} & u\_{12}l\_{21}+u\_{22} & u\_{13}l\_{21}+u\_{23} \\\\ u\_{11}l\_{31} & u\_{12}l\_{31}+u\_{22}l\_{32} & u\_{13}l\_{31} + u\_{23}l\_{32}+u\_{33} \\end{pmatrix} = LU\\end{align}
|
||
|
||
Розв'язуючи для інших $l$ і $u$, ми отримуємо наступні рівняння:
|
||
|
||
$u\_{11}=a\_{11}
|
||
|
||
$u\_{12}=a\_{12}
|
||
|
||
$u\_{13}=a\_{13}
|
||
|
||
$u\_{22}=a\_{22} - u\_{12}l\_{21}$
|
||
|
||
$u\_{23}=a\_{23} - u\_{13}l\_{21}$
|
||
|
||
$u\_{33}=a\_{33} - (u\_{13}l\_{31} + u\_{23}l\_{32})$
|
||
|
||
і для $l$:
|
||
|
||
$l\_{21}=\\frac{1}{u\_{11}} a\_{21}$
|
||
|
||
$l\_{31}=\\frac{1}{u\_{11}} a\_{31}$
|
||
|
||
$l\_{32}=\\frac{1}{u\_{22}} (a\_{32} - u\_{12}l\_{31})$
|
||
|
||
Як бачимо, існує шаблон обчислення, який можна виразити наступною формулою, спочатку за $U$
|
||
|
||
$u\_{ij} = a\_{ij} - \\sum\_{k=1}^{i-1} u\_{kj}l\_{ik}$
|
||
|
||
і потім для $L$
|
||
|
||
$l\_{ij} = \\frac{1}{u\_{jj}} (a\_{ij} - \\sum\_{k=1}^{j-1} u\_{kj}l\_{ik})$
|
||
|
||
Як бачимо, у другій формулі, щоб отримати $l\_{ij}$ нижче діагоналі, ми повинні поділити на діагональний елемент (значення) $u\_{jj}$, так виникає проблема, коли значення $u\_{jj}$ дорівнює 0 або є дуже малим, що призводить до числової нестабільності.
|
||
|
||
Розв'язок цього завдання є *вибір головного елемента матриці* $A$, що означає перегрупування рядків $A$, на розклад $LU$ таким чином, щоб найбільший елемент кожної колонки потрапляв на діагональ $A$. Переміщення рядків означає множення $A$ на матрицю перестановки $P$:
|
||
|
||
$PA \\Rightarrow A'$
|
||
|
||
Наприклад:
|
||
|
||
\\begin{align} \\begin{pmatrix} 0 & 1 \\\\ 1 & 0 \\end{pmatrix} \\begin{pmatrix} 1 & 4 \\\\ 2 & 3 \\end{pmatrix} \\Rightarrow \\begin{pmatrix} 2 & 3 \\\\ 1 & 4 \\end{pmatrix} \\end{align}
|
||
|
||
Алгоритм розкладки застосовується тоді до перерозміщеної матриці так, щоб
|
||
|
||
$PA = LU$
|
||
|
||
# --instructions--
|
||
|
||
Завдання полягає в тому, щоб реалізувати процедуру, яка знайде матрицю nxn $A$ і поверне нижчу трикутну матрицю $L$, верхню трикутну матрицю $U$ і матрицю перестановки $P$, так, щоб розв'язати вищезгадане рівняння. Повернене значення має бути у вигляді `[L, U, P]`.
|
||
|
||
# --hints--
|
||
|
||
`luDecomposition` повинне бути функцією.
|
||
|
||
```js
|
||
assert(typeof luDecomposition == 'function');
|
||
```
|
||
|
||
`luDecomposition([[1, 3, 5], [2, 4, 7], [1, 1, 0]])` повинен повернути масив.
|
||
|
||
```js
|
||
assert(
|
||
Array.isArray(
|
||
luDecomposition([
|
||
[1, 3, 5],
|
||
[2, 4, 7],
|
||
[1, 1, 0]
|
||
])
|
||
)
|
||
);
|
||
```
|
||
|
||
`luDecomposition([[1, 3, 5], [2, 4, 7], [1, 1, 0]])` повинен повернути `[[[1, 0, 0], [0.5, 1, 0], [0.5, -1, 1]], [[2, 4, 7], [0, 1, 1.5], [0, 0, -2]], [[0, 1, 0], [1, 0, 0], [0, 0, 1]]]`.
|
||
|
||
```js
|
||
assert.deepEqual(
|
||
luDecomposition([
|
||
[1, 3, 5],
|
||
[2, 4, 7],
|
||
[1, 1, 0]
|
||
]),
|
||
[
|
||
[
|
||
[1, 0, 0],
|
||
[0.5, 1, 0],
|
||
[0.5, -1, 1]
|
||
],
|
||
[
|
||
[2, 4, 7],
|
||
[0, 1, 1.5],
|
||
[0, 0, -2]
|
||
],
|
||
[
|
||
[0, 1, 0],
|
||
[1, 0, 0],
|
||
[0, 0, 1]
|
||
]
|
||
]
|
||
);
|
||
```
|
||
|
||
`luDecomposition([[11, 9, 24, 2], [1, 5, 2, 6], [3, 17, 18, 1], [2, 5, 7, 1]])` повинен повернути `[[[1, 0, 0, 0], [0.2727272727272727, 1, 0, 0], [0.09090909090909091, 0.2875, 1, 0], [0.18181818181818182, 0.23124999999999996, 0.0035971223021580693, 1]], [[11, 9, 24, 2], [0, 14.545454545454547, 11.454545454545455, 0.4545454545454546], [0, 0, -3.4749999999999996, 5.6875], [0, 0, 0, 0.510791366906476]], [[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]]]`.
|
||
|
||
```js
|
||
assert.deepEqual(
|
||
luDecomposition([
|
||
[11, 9, 24, 2],
|
||
[1, 5, 2, 6],
|
||
[3, 17, 18, 1],
|
||
[2, 5, 7, 1]
|
||
]),
|
||
[
|
||
[
|
||
[1, 0, 0, 0],
|
||
[0.2727272727272727, 1, 0, 0],
|
||
[0.09090909090909091, 0.2875, 1, 0],
|
||
[0.18181818181818182, 0.23124999999999996, 0.0035971223021580693, 1]
|
||
],
|
||
[
|
||
[11, 9, 24, 2],
|
||
[0, 14.545454545454547, 11.454545454545455, 0.4545454545454546],
|
||
[0, 0, -3.4749999999999996, 5.6875],
|
||
[0, 0, 0, 0.510791366906476]
|
||
],
|
||
[
|
||
[1, 0, 0, 0],
|
||
[0, 0, 1, 0],
|
||
[0, 1, 0, 0],
|
||
[0, 0, 0, 1]
|
||
]
|
||
]
|
||
);
|
||
```
|
||
|
||
`luDecomposition([[1, 1, 1], [4, 3, -1], [3, 5, 3]])` повинен повернути `[[[1, 0, 0], [0.75, 1, 0], [0.25, 0.09090909090909091, 1]], [[4, 3, -1], [0, 2.75, 3.75], [0, 0, 0.9090909090909091]], [[0, 1, 0], [0, 0, 1], [1, 0, 0]]]`.
|
||
|
||
```js
|
||
assert.deepEqual(
|
||
luDecomposition([
|
||
[1, 1, 1],
|
||
[4, 3, -1],
|
||
[3, 5, 3]
|
||
]),
|
||
[
|
||
[
|
||
[1, 0, 0],
|
||
[0.75, 1, 0],
|
||
[0.25, 0.09090909090909091, 1]
|
||
],
|
||
[
|
||
[4, 3, -1],
|
||
[0, 2.75, 3.75],
|
||
[0, 0, 0.9090909090909091]
|
||
],
|
||
[
|
||
[0, 1, 0],
|
||
[0, 0, 1],
|
||
[1, 0, 0]
|
||
]
|
||
]
|
||
);
|
||
```
|
||
|
||
`luDecomposition([[1, -2, 3], [2, -5, 12], [0, 2, -10]])` має повернути `[[[1, 0, 0], [0, 1, 0], [0.5, 0.25, 1]], [[2, -5, 12], [0, 2, -10], [0, 0, -0.5]], [[0, 1, 0], [0, 0, 1], [1, 0, 0]]]`.
|
||
|
||
```js
|
||
assert.deepEqual(
|
||
luDecomposition([
|
||
[1, -2, 3],
|
||
[2, -5, 12],
|
||
[0, 2, -10]
|
||
]),
|
||
[
|
||
[
|
||
[1, 0, 0],
|
||
[0, 1, 0],
|
||
[0.5, 0.25, 1]
|
||
],
|
||
[
|
||
[2, -5, 12],
|
||
[0, 2, -10],
|
||
[0, 0, -0.5]
|
||
],
|
||
[
|
||
[0, 1, 0],
|
||
[0, 0, 1],
|
||
[1, 0, 0]
|
||
]
|
||
]
|
||
);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function luDecomposition(A) {
|
||
|
||
}
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
function luDecomposition(A) {
|
||
|
||
function dotProduct(a, b) {
|
||
var sum = 0;
|
||
for (var i = 0; i < a.length; i++)
|
||
sum += a[i] * b[i]
|
||
return sum;
|
||
}
|
||
|
||
function matrixMul(A, B) {
|
||
var result = new Array(A.length);
|
||
for (var i = 0; i < A.length; i++)
|
||
result[i] = new Array(B[0].length)
|
||
var aux = new Array(B.length);
|
||
|
||
for (var j = 0; j < B[0].length; j++) {
|
||
|
||
for (var k = 0; k < B.length; k++)
|
||
aux[k] = B[k][j];
|
||
|
||
for (var i = 0; i < A.length; i++)
|
||
result[i][j] = dotProduct(A[i], aux);
|
||
}
|
||
return result;
|
||
}
|
||
|
||
function pivotize(m) {
|
||
var n = m.length;
|
||
var id = new Array(n);
|
||
for (var i = 0; i < n; i++) {
|
||
id[i] = new Array(n);
|
||
id[i].fill(0)
|
||
id[i][i] = 1;
|
||
}
|
||
|
||
for (var i = 0; i < n; i++) {
|
||
var maxm = m[i][i];
|
||
var row = i;
|
||
for (var j = i; j < n; j++)
|
||
if (m[j][i] > maxm) {
|
||
maxm = m[j][i];
|
||
row = j;
|
||
}
|
||
|
||
if (i != row) {
|
||
var tmp = id[i];
|
||
id[i] = id[row];
|
||
id[row] = tmp;
|
||
}
|
||
}
|
||
return id;
|
||
}
|
||
|
||
var n = A.length;
|
||
var L = new Array(n);
|
||
for (var i = 0; i < n; i++) { L[i] = new Array(n); L[i].fill(0) }
|
||
var U = new Array(n);
|
||
for (var i = 0; i < n; i++) { U[i] = new Array(n); U[i].fill(0) }
|
||
var P = pivotize(A);
|
||
var A2 = matrixMul(P, A);
|
||
|
||
for (var j = 0; j < n; j++) {
|
||
L[j][j] = 1;
|
||
for (var i = 0; i < j + 1; i++) {
|
||
var s1 = 0;
|
||
for (var k = 0; k < i; k++)
|
||
s1 += U[k][j] * L[i][k];
|
||
U[i][j] = A2[i][j] - s1;
|
||
}
|
||
for (var i = j; i < n; i++) {
|
||
var s2 = 0;
|
||
for (var k = 0; k < j; k++)
|
||
s2 += U[k][j] * L[i][k];
|
||
L[i][j] = (A2[i][j] - s2) / U[j][j];
|
||
}
|
||
}
|
||
return [L, U, P];
|
||
}
|
||
```
|