Розклад Холецького

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Розклад Холецького — представлення симетричної додатноозначеної матриці у вигляді \ A = LL^T, де \ L — нижня трикутна матриця з додатніми елементами на діагоналі.

Для симетричних матриць розклад Холецького завжди існує і, для додатноозначених матриць, він єдиний. Для невід'ємновизначених матриць розклад не єдиний.

Для матриць з комплексними елементами: якщо \ A — додатноозначена ермітова матриця, то існує розклад \ A = LL^*.

Розклад названий в честь французького математика Андре-Луї Холецького (1875-1918).

Алгоритм[ред.ред. код]

Елементи матриці \ L можна обчислити, починаючи з верхнього лівого кута, за формулами:

L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2}
L_{ij} = \frac{1}{L_{jj}} \left(A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} \right), якщо \ j < i.

Вираз під коренем завжди додатній, якщо A — дійсна додатновизначена матриця.

Для комплекснозначних ермітових матриць використовуються формули:

L_{ii} = \sqrt{ A_{ii} - \sum_{k=1}^{i-1} L_{ik}L_{i,k}^* }
L_{ij} = \frac{1}{L_{jj}} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk}^* \right), якщо \ j < i.

LDL розклад[ред.ред. код]

Пов'язаним із розкладом Холецького є LDL-розклад:

\ A = LDL^T

де \ L — одинична нижня трикутна матриця; \ Dдіагональна матриця.

 D_j = A_{jj} - \sum_{k=1}^{j-1} L_{jk}^2 D_k
 L_{ij} = \frac{1}{D_j} \left( A_{ij} - \sum_{k=1}^{j-1} L_{ik} L_{jk} D_k \right), якщо \ j < i.

Застосування[ред.ред. код]

Розклад Холецького може застосовуватись для розв'язку системи лінійних рівнянь Ax = b з симетричною додатноозначеною матрицею. Такі матриці часто виникають, наприклад, при використанні методу найменших квадратів чи числовому розв'язуванні диференціальних рівнянь.

Виконавши розклад A = LL^T, розв'язок x отримаємо послідовно розв'язавши дві трикутні СЛАР: Ly = b та L^T x = y. Такий спосіб розв'язку називають методом квадратних коренів. Порівняно з загальнішими методами: метод Гауса чи LU розклад матриці, він стійкіший і потребує вдвічі менше арифметичних операцій.