LU-розклад матриці

${\displaystyle A={\begin{pmatrix}a_{11}&a_{12}&\dots &a_{1n}&\\a_{21}&a_{22}&\dots &a_{2n}&\\\vdots &\vdots &\ddots &\vdots &\\a_{n1}&a_{n2}&\dots &a_{nn}&\\\end{pmatrix}}={\begin{pmatrix}a_{11}&w^{t}&\\v&A'&\\\end{pmatrix}}={\begin{pmatrix}1&0&\\v/a_{11}&I_{n-1}&\\\end{pmatrix}}{\begin{pmatrix}a_{11}&w^{T}&\\0&A'-{\frac {v\times w^{t}}{a_{11}}}&\\\end{pmatrix}}={\begin{pmatrix}1&0&\\v/a_{11}&I_{n-1}&\\\end{pmatrix}}{\begin{pmatrix}a_{11}&w^{T}&\\0&L'U'&\\\end{pmatrix}}={\begin{pmatrix}1&0&\\v/a_{11}&L'&\\\end{pmatrix}}{\begin{pmatrix}a_{11}&w^{T}&\\0&U'&\\\end{pmatrix}}=LU}$

Матриця ${\displaystyle A'-v\times w^{t}/a_{11}}$ називається доповненням Шура для ${\displaystyle A}$ щодо ${\displaystyle a_{11}.}$

Метод не працює якщо один з ${\displaystyle a_{ii}=0,}$ тому що відбувається ділення на нуль. Елементи, на які ми ділимо впродовж ${\displaystyle LU}$-розкладу, називаються опорними і перебувають на головній діагоналі матриці ${\displaystyle U.}$ Ми використовуємо матрицю перестановки ${\displaystyle P}$ у ${\displaystyle LUP}$-розкладі задля уникнення ділення на нуль. Оскільки представлення чисел з рухомою комою на цифровій машині має обмеження[1], ми також не хочемо ділити на надто маленьке число. Використовують два підходи для вибору опорного елементу на ${\displaystyle i}$-му кроці ${\displaystyle LUP}$-розкладу. Перший — вибрати найбільший елемент в ${\displaystyle i}$-му рядку, що дає значний виграш у числовій стійкості. Другий — вибрати найбільший елемент у доповненні Щура на отриманому ${\displaystyle i}$-му кроці. Цей підхід дає дуже маленький приріст числової стабільності порівняно з попереднім підходом, натомість вимагає значних затрат часу.[2]

Є модифікованим методом Гауса і потребує 2n³ / 3 арифметичних операцій.

Позначимо як l_ij, u_ij, a_ij елементи матриць L,U та A відповідно. З означення LU-розбиття l_ij=0 (j>i), u_ij=0 (j<i), u_ii=1. Очевидно, що

${\displaystyle a_{ij}=\sum _{k=0}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{i-1}l_{ik}u_{kj}+l_{ii}u_{ij}+\sum _{k=i+1}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{i-1}l_{ik}u_{kj}+l_{ii}u_{ij}}$

${\displaystyle a_{ij}=\sum _{k=0}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{j-1}l_{ik}u_{kj}+l_{ij}u_{jj}+\sum _{k=j+1}^{n-1}l_{ik}u_{kj}=\sum _{k=0}^{j-1}l_{ik}u_{kj}+l_{ij}u_{jj}}$,

(тут n — розмір матриці А)

Звідки легко в явній формі отримати вирази для елементів матриць L та U:

${\displaystyle l_{ij}=a_{ij}-\sum _{k=0}^{j-1}l_{ik}u_{kj}\ (i\geq \ j)}$

${\displaystyle u_{ij}={1 \over l_{ii}}\left[a_{ij}-\sum _{k=0}^{i-1}l_{ik}u_{kj}\right]\ (i<j)}$

• Теорія матриць

• Гантмахер Ф. Р. Теория матриц. — 2 изд. — Москва : Наука, 1967. — 576 с. — ISBN 5-9221-0524-8.(рос.)