LU разложение - LU decomposition

В числовой анализ и линейная алгебра, нижний – верхний (LU) разложение или же факторизация факторы а матрица как продукт низшего треугольная матрица и верхнетреугольная матрица. Продукт иногда включает матрица перестановок также. LU-разложение можно рассматривать как матричную форму Гауссово исключение. Компьютеры обычно решают квадрат системы линейных уравнений используя разложение LU, и это также ключевой шаг при обращении матрицы или вычислении детерминант матрицы. LU-разложение было введено польским математиком Тадеуш Банахевич в 1938 г.^[1]

Определения

LDU-разложение Матрица Уолша

Позволять А - квадратная матрица. An LU факторизация относится к факторизации Ас правильным порядком строк и / или столбцов или перестановками на два фактора - нижнюю треугольную матрицу L и верхнетреугольная матрица U:

${displaystyle A=LU.}$

В нижней треугольной матрице все элементы над диагональю равны нулю, в верхней треугольной матрице все элементы ниже диагонали равны нулю. Например, для матрицы 3 × 3 А, его LU-разложение выглядит так:

${displaystyle {egin{bmatrix}a_{11}&a_{12}&a_{13}a_{21}&a_{22}&a_{23}a_{31}&a_{32}&a_{33}end{bmatrix}}={egin{bmatrix}l_{11}&0&0l_{21}&l_{22}&0l_{31}&l_{32}&l_{33}end{bmatrix}}{egin{bmatrix}u_{11}&u_{12}&u_{13}�&u_{22}&u_{23}�&0&u_{33}end{bmatrix}}.}$

Без надлежащего упорядочивания или перестановок в матрице факторизация может не осуществиться. Например, легко проверить (раскрывая матричное умножение), что ${ extstyle a_{11}=l_{11}u_{11}}$. Если ${ extstyle a_{11}=0}$, то хотя бы один из ${ extstyle l_{11}}$ и ${ extstyle u_{11}}$ должно быть нулем, что означает, что либо L или же U является единственное число. Это невозможно, если А неособо (обратимо). Это процедурная проблема. Его можно удалить, просто изменив порядок строк А так что первый элемент переставленной матрицы отличен от нуля. Та же проблема на последующих этапах факторизации может быть устранена таким же образом; см. основную процедуру ниже.

Факторизация LU с частичным разворотом

Оказывается, что правильной перестановки в строках (или столбцах) достаточно для факторизации LU. Факторизация LU с частичным разворотом (LUP) часто относится к факторизации LU только с перестановками строк:

${displaystyle PA=LU,}$

куда L и U - снова нижняя и верхняя треугольные матрицы, и п это матрица перестановок, которая при умножении слева на А, меняет порядок строк А. Оказывается, все квадратные матрицы можно разложить на множители в таком виде:^[2] и факторизация численно стабильна на практике.^[3] Это делает разложение LUP полезным методом на практике.

Факторизация LU с полным поворотом

An Факторизация LU с полным поворотом включает в себя перестановки как строк, так и столбцов:

${displaystyle PAQ=LU,}$

куда L, U и п определены, как и раньше, и Q матрица перестановки, которая переупорядочивает столбцы А.^[4]

Разложение LDU

An Разложение LDU является разложением вида

${displaystyle A=LDU,}$

куда D это диагональная матрица, и L и U находятся унитреугольный матриц, что означает, что все записи на диагоналях L и U едины.

Выше мы требовали, чтобы А - квадратная матрица, но все эти разложения можно обобщить и на прямоугольные матрицы. В таком случае, L и D квадратные матрицы, каждая из которых имеет то же количество строк, что и А, и U имеет точно такие же размеры, как А. Верхний треугольный следует интерпретировать как имеющий только ноль записей ниже главной диагонали, которая начинается в верхнем левом углу.

Пример

Факторизуем следующую матрицу 2 на 2:

${displaystyle {egin{bmatrix}4&36&3end{bmatrix}}={egin{bmatrix}l_{11}&0l_{21}&l_{22}end{bmatrix}}{egin{bmatrix}u_{11}&u_{12}�&u_{22}end{bmatrix}}.}$

Один из способов найти LU-разложение этой простой матрицы - просто решить линейные уравнения путем проверки. Расширение матричного умножения дает

${displaystyle {egin{aligned}l_{11}cdot u_{11}+0cdot 0&=4l_{11}cdot u_{12}+0cdot u_{22}&=3l_{21}cdot u_{11}+l_{22}cdot 0&=6l_{21}cdot u_{12}+l_{22}cdot u_{22}&=3.end{aligned}}}$

Эта система уравнений имеет вид недоопределенный. В этом случае любые два ненулевых элемента L и U матрицы являются параметрами решения и могут быть установлены произвольно на любое ненулевое значение. Следовательно, чтобы найти единственное разложение LU, необходимо наложить некоторые ограничения на L и U матрицы. Например, нам удобно потребовать нижнюю треугольную матрицу L быть единичной треугольной матрицей (т.е. установить все элементы ее главной диагонали в единицы). Тогда система уравнений имеет следующее решение:

${displaystyle {egin{aligned}l_{11}&=l_{22}=1l_{21}&=1.5u_{11}&=4u_{12}&=3u_{22}&=-1.5end{aligned}}}$

Подставляя эти значения в разложение LU выше, получаем

${displaystyle {egin{bmatrix}4&36&3end{bmatrix}}={egin{bmatrix}1&01.5&1end{bmatrix}}{egin{bmatrix}4&3�&-1.5end{bmatrix}}.}$

Существование и уникальность

Квадратные матрицы

Любая квадратная матрица ${ extstyle A}$ признает LUP и PLU факторизации.^[2] Если ${ extstyle A}$ является обратимый, то допускает LU (или же LDU) факторизация если и только если весь его ведущий руководитель несовершеннолетние ненулевые.^[5] Если ${ extstyle A}$ особая матрица ранга ${ extstyle k}$, то допускает LU факторизация, если первая ${ extstyle k}$ ведущие главные миноры отличны от нуля, хотя обратное неверно.^[6]

Если квадратная обратимая матрица имеет LDU (факторизация со всеми диагональными элементами L и U равным 1), то факторизация однозначна.^[5] В этом случае LU факторизация также уникальна, если мы потребуем, чтобы диагональ ${ extstyle L}$ (или же ${ extstyle U}$) состоит из единиц.

Симметричные положительно определенные матрицы

Если А является симметричным (или Эрмитский, если А сложно) положительно определенный матрицу, мы можем организовать дела так, чтобы U это сопряженный транспонировать из L. То есть мы можем написать А в качестве

${displaystyle A=LL^{*}.,}$

Это разложение называется Разложение Холецкого. Разложение Холецкого всегда существует и уникально - при условии, что матрица положительно определена. Кроме того, вычисление разложения Холецкого более эффективно и численно более стабильный чем вычисление некоторых других разложений LU.

Общие матрицы

Для (не обязательно обратимой) матрицы над любым полем известны точные необходимые и достаточные условия, при которых она имеет LU-факторизацию. Условия выражаются в виде рангов определенных подматриц. Алгоритм исключения Гаусса для получения LU-разложения также был расширен на этот наиболее общий случай.^[7]

Алгоритмы

Закрытая формула

Когда факторизация LDU существует и уникальна, существует замкнутая (явная) формула для элементов L, D, и U через отношения определителей некоторых подматриц исходной матрицы А.^[8] Особенно, ${ extstyle D_{1}=A_{1,1}}$, и для ${ extstyle i=2,ldots ,n}$, ${ extstyle D_{i}}$ это соотношение ${ extstyle i}$-я главная подматрица ${ extstyle (i-1)}$-я главная подматрица. Вычисление определителей вычислительно дорогой, поэтому эта явная формула на практике не используется.

Использование исключения Гаусса

Следующий алгоритм представляет собой модифицированную форму Гауссово исключение. Для вычисления разложения LU с использованием этого алгоритма требуется ${displaystyle { frac {2}{3}}n^{3}}$ операции с плавающей запятой, игнорируя младшие члены. Частичное поворот добавляет только квадратичный член; это не относится к полному повороту.^[9]

Учитывая N × N матрица ${displaystyle A=(a_{i,j})_{1leq i,jleq N}}$, определять ${displaystyle A^{(0)}:=A}$.

Мы исключаем элементы матрицы ниже главной диагонали в п-й столбец А^(п − 1) добавив к я-й строке этой матрицы п-я строка умноженная на

${displaystyle -l_{i,n}:=-{frac {a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}},quad i=n+1,ldots ,N.}$

Это можно сделать, умножив А^(п − 1) слева с нижней треугольной матрицей

${displaystyle L_{n}={egin{pmatrix}1&&&&&&ddots &&&&&&1&&&&&-l_{n+1,n}&&&&&vdots &&ddots &&&-l_{N,n}&&&1end{pmatrix}},}$

это N Икс N единичная матрица с ее п-й столбец заменен вектором ${displaystyle {egin{pmatrix}0&cdots &0&1&-l_{n+1,n}&cdots &-l_{N,n}end{pmatrix}}^{T}.}$

Мы установили

${displaystyle A^{(n)}:=L_{n}A^{(n-1)}.}$

После N - 1 шаг, мы удалили все элементы матрицы ниже главной диагонали, так что мы получили верхнюю треугольную матрицу А^(N − 1). Находим разложение

${displaystyle A=L_{1}^{-1}L_{1}A^{(0)}=L_{1}^{-1}A^{(1)}=L_{1}^{-1}L_{2}^{-1}L_{2}A^{(1)}=L_{1}^{-1}L_{2}^{-1}A^{(2)}=dotsb =L_{1}^{-1}ldots L_{N-1}^{-1}A^{(N-1)}.}$

Обозначим верхнетреугольную матрицу А^(N − 1) к U, и ${ extstyle L=L_{1}^{-1}ldots L_{N-1}^{-1}}$. Поскольку обратная нижнетреугольная матрица L_п снова является нижнетреугольной матрицей, а умножение двух нижнетреугольных матриц снова является нижнетреугольной матрицей, из этого следует, что L - нижнетреугольная матрица. Более того, видно, что

${displaystyle L={egin{pmatrix}1&&&&&l_{2,1}&ddots &&&&&ddots &1&&&vdots &dots &l_{n+1,n}&1&&&&vdots &ddots &ddots &l_{N,1}&dots &l_{N,n}&dots &l_{N,N-1}&1end{pmatrix}}.}$

Мы получаем ${displaystyle A=LU.}$

Понятно, что для того, чтобы этот алгоритм работал, необходимо иметь ${displaystyle a_{n,n}^{(n-1)}eq 0}$ на каждом шаге (см. определение ${displaystyle l_{i,n}}$). Если это предположение в какой-то момент не сработает, нужно поменять местами п-й ряд с другим рядом под ним перед продолжением. Вот почему LU-разложение в целом выглядит как ${displaystyle P^{-1}A=LU}$.

Обратите внимание, что разложение, полученное с помощью этой процедуры, является Разложение Дулитла: главная диагональ L состоит исключительно из 1с. Если продолжить удаление элементов над главной диагонали, добавляя кратные столбцы (вместо удаления элементов ниже диагонали, добавляя кратные ряды), мы получили бы Разложение гренок, где главная диагональ U имеет 1с.

Другой (эквивалентный) способ получения разложения Краута заданной матрицы А состоит в том, чтобы получить разложение Дулитла транспонированной А. Действительно, если ${ extstyle A^{T}=L_{0}U_{0}}$ - LU-разложение, полученное с помощью алгоритма, представленного в этом разделе, тогда, взяв ${ extstyle L=U_{0}^{T}}$ и ${ extstyle U=L_{0}^{T}}$у нас есть это ${displaystyle A=LU}$ является разложением Краута.

Через рекурсию

Cormen et al.^[10] описать рекурсивный алгоритм разложения LUP.

Учитывая матрицу А, позволять п₁ матрица перестановок такая, что

${displaystyle P_{1}A=left({egin{array}{c|ccc}a&&w^{T}&hline &&&v&&A'&&&&end{array}}ight)}$,

куда ${ extstyle aeq 0}$, если в первом столбце А; или взять п₁ в качестве единичной матрицы в противном случае. Теперь позвольте ${ extstyle c=1/a}$, если ${ extstyle aeq 0}$; или же ${ extstyle c=0}$ иначе. У нас есть

${displaystyle P_{1}A=left({egin{array}{c|ccc}1&&0&hline &&&cv&&I_{n-1}&&&&end{array}}ight)left({egin{array}{c|c}a&w^{T}hline &�&A'-cvw^{T}&end{array}}ight)}$.

Теперь мы можем рекурсивно найти LUP-разложение ${ extstyle P'(A'-cvw^{T})=L'U'}$. Позволять ${ extstyle v'=P'v}$. Следовательно

${displaystyle left({egin{array}{c|ccc}1&&0&hline &&&�&&P'&&&&end{array}}ight)P_{1}A=left({egin{array}{c|ccc}1&&0&hline &&&cv'&&L'&&&&end{array}}ight)left({egin{array}{c|ccc}a&&w^{T}&hline &&&�&&U'&&&&end{array}}ight)}$,

который является LUP-разложением А.

Рандомизированный алгоритм

Можно найти приближение низкого ранга к разложению LU, используя рандомизированный алгоритм. Учитывая входную матрицу ${ extstyle A}$ и желаемый низкий ранг ${ extstyle k}$, рандомизированный LU возвращает матрицы перестановок ${ extstyle P,Q}$ и нижняя / верхняя трапециевидные матрицы ${ extstyle L,U}$ размера ${ extstyle m imes k}$ и ${ extstyle k imes n}$ соответственно такие, что с большой вероятностью ${ extstyle Vert PAQ-LUVert _{2}leq Csigma _{k+1}}$, куда ${ extstyle C}$ - константа, зависящая от параметров алгоритма и ${ extstyle sigma _{k+1}}$ это ${ extstyle (k+1)}$-е сингулярное значение входной матрицы ${ extstyle A}$.^[11]

Теоретическая сложность

Если две матрицы порядка п можно умножить во времени M(п), куда M(п) ≥ п^а для некоторых а > 2, то LU-разложение может быть вычислено за время O (M(п)).^[12] Это означает, например, что O (п^2.376) существует алгоритм, основанный на Алгоритм Копперсмита – Винограда.

Разложение по разреженной матрице

Были разработаны специальные алгоритмы факторизации больших разреженные матрицы. Эти алгоритмы пытаются найти редкие факторы L и U. В идеале стоимость вычислений определяется количеством ненулевых элементов, а не размером матрицы.

Эти алгоритмы используют свободу обмена строками и столбцами для минимизации заполнения (записи, которые изменяются с начального нуля на ненулевое значение во время выполнения алгоритма).

Общая обработка заказов, минимизирующая заполнение, может быть решена с помощью теория графов.

Приложения

Решение линейных уравнений

Для системы линейных уравнений в матричной форме

${displaystyle Ax=b,}$

мы хотим решить уравнение для Икс, данный А и б. Предположим, мы уже получили LUP-разложение А такой, что ${ extstyle PA=LU}$, так ${ extstyle LUx=Pb}$.

В этом случае решение осуществляется в два логических шага:

1. Сначала решаем уравнение ${ extstyle Ly=Pb}$ за у.
2. Во-вторых, решаем уравнение ${ extstyle Ux=y}$ за Икс.

В обоих случаях мы имеем дело с треугольными матрицами (L и U), которую можно решить напрямую прямая и обратная замена без использования Гауссово исключение процесс (однако нам нужен этот процесс или его эквивалент для вычисления LU само разложение).

Вышеупомянутую процедуру можно многократно применять для решения уравнения несколько раз для разных б. В этом случае быстрее (и удобнее) выполнить LU-разложение матрицы А один раз, а затем решите треугольные матрицы для различных б, а не каждый раз использовать исключение Гаусса. Матрицы L и U можно было подумать, что они «закодировали» процесс исключения Гаусса.

Стоимость решения системы линейных уравнений составляет примерно ${ extstyle {frac {2}{3}}n^{3}}$ операции с плавающей запятой, если матрица ${ extstyle A}$ имеет размер ${ extstyle n}$. Это делает его вдвое быстрее, чем алгоритмы, основанные на QR-разложение, что стоит около ${ extstyle {frac {4}{3}}n^{3}}$ операции с плавающей запятой, когда Размышления домохозяина используются. По этой причине обычно предпочтительнее разложение LU.^[13]

Инвертирование матрицы

При решении систем уравнений б обычно рассматривается как вектор с длиной, равной высоте матрицы А. Однако при обращении матрицы вместо вектора б, имеем матрицу B, куда B является п-к-п матрица, так что мы пытаемся найти матрицу Икс (также п-к-п матрица):

${displaystyle AX=LUX=B.}$

Мы можем использовать тот же алгоритм, представленный ранее, чтобы решить для каждого столбца матрицы Икс. Теперь предположим, что B это единичная матрица размера п. Из этого следует, что результат Икс должно быть обратным А.^[14]

Вычисление определителя

Учитывая разложение LUP ${ extstyle A=P^{-1}LU}$ квадратной матрицы А, определитель А можно просто вычислить как

${displaystyle det(A)=det(P^{-1})det(L)det(U)=(-1)^{S}left(prod _{i=1}^{n}l_{ii}ight)left(prod _{i=1}^{n}u_{ii}ight).}$

Второе уравнение следует из того факта, что определитель треугольной матрицы - это просто произведение ее диагональных элементов, и что определитель матрицы перестановок равен (−1)^S куда S количество замен строк в разложении.

В случае разложения ЛУ с полным поворотом ${ extstyle det(A)}$ также равна правой части приведенного выше уравнения, если мы положим S быть общим количеством обменов строк и столбцов.

Тот же метод легко применим к разложению LU, задав п равняется единичной матрице.

Примеры кода C

/ * INPUT: A - массив указателей на строки квадратной матрицы размерности N * Tol - небольшое число допуска для обнаружения отказа, когда матрица близка к вырожденной * ВЫХОД: Матрица A изменена, она содержит копию обеих матриц L-E и U как A = (L-E) + U, так что P * A = L * U. * Матрица перестановок хранится не как матрица, а в целочисленном векторе P размера N + 1  * содержащий индексы столбцов, в которых матрица перестановок имеет "1". Последний элемент P [N] = S + N,  * где S - количество обменов строк, необходимых для вычисления определителя, det (P) = (- 1) ^ S  */int LUPDecompose(двойной **А, int N, двойной Тол, int *п) {    int я, j, k, imax;     двойной maxA, *ptr, абсА;    за (я = 0; я <= N; я++)        п[я] = я; // Матрица единичной перестановки, P [N] инициализирована N    за (я = 0; я < N; я++) {        maxA = 0.0;        imax = я;        за (k = я; k < N; k++)            если ((абсА = фабрики(А[k][я])) > maxA) {                 maxA = абсА;                imax = k;            }        если (maxA < Тол) возвращаться 0; // сбой, матрица вырожденная        если (imax != я) {            // поворот P            j = п[я];            п[я] = п[imax];            п[imax] = j;            // поворот строк A            ptr = А[я];            А[я] = А[imax];            А[imax] = ptr;            // подсчет опорных точек, начиная с N (для определителя)            п[N]++;        }        за (j = я + 1; j < N; j++) {            А[j][я] /= А[я][я];            за (k = я + 1; k < N; k++)                А[j][k] -= А[j][я] * А[я][k];        }    }    возвращаться 1;  // разложение выполнено }/ * INPUT: A, P заполнены LUPDecompose; b - вектор rhs; N - размер * ВЫХОД: x - вектор решения A * x = b */пустота LUPSolve(двойной **А, int *п, двойной *б, int N, двойной *Икс) {    за (int я = 0; я < N; я++) {        Икс[я] = б[п[я]];        за (int k = 0; k < я; k++)            Икс[я] -= А[я][k] * Икс[k];    }    за (int я = N - 1; я >= 0; я--) {        за (int k = я + 1; k < N; k++)            Икс[я] -= А[я][k] * Икс[k];        Икс[я] /= А[я][я];    }}/ * INPUT: A, P заполнены LUPDecompose; N - размер * ВЫХОД: IA - это обратная исходная матрица */пустота LUPInvert(двойной **А, int *п, int N, двойной **Я) {      за (int j = 0; j < N; j++) {        за (int я = 0; я < N; я++) {            Я[я][j] = п[я] == j ? 1.0 : 0.0            за (int k = 0; k < я; k++)                Я[я][j] -= А[я][k] * Я[k][j];        }        за (int я = N - 1; я >= 0; я--) {            за (int k = я + 1; k < N; k++)                Я[я][j] -= А[я][k] * Я[k][j];            Я[я][j] /= А[я][я];        }    }}/ * INPUT: A, P заполнено LUPDecompose; N - размерность.  * ВЫХОД: функция возвращает определитель исходной матрицы */двойной LUP Детерминант(двойной **А, int *п, int N) {    двойной Det = А[0][0];    за (int я = 1; я < N; я++)        Det *= А[я][я];    возвращаться (п[N] - N) % 2 == 0 ? Det : -Det}

Примеры кода C #

    общественный учебный класс SystemOfLinearEquations    {        общественный двойной[] РешитьUsingLU(двойной[,] матрица, двойной[] rightPart, int п)        {            // разложение матрицы            двойной[,] Лу = новый двойной[п, п];            двойной сумма = 0;            за (int я = 0; я < п; я++)            {                за (int j = я; j < п; j++)                {                    сумма = 0;                    за (int k = 0; k < я; k++)                        сумма += Лу[я, k] * Лу[k, j];                    Лу[я, j] = матрица[я, j] - сумма;                }                за (int j = я + 1; j < п; j++)                {                    сумма = 0;                    за (int k = 0; k < я; k++)                        сумма += Лу[j, k] * Лу[k, я];                    Лу[j, я] = (1 / Лу[я, я]) * (матрица[j, я] - сумма);                }            }                        // lu = L + U-I            // находим решение Ly = b            двойной[] у = новый двойной[п];            за (int я = 0; я < п; я++)            {                сумма = 0;                за (int k = 0; k < я; k++)                    сумма += Лу[я, k] * у[k];                у[я] = rightPart[я] - сумма;            }            // находим решение Ux = y            двойной[] Икс = новый двойной[п];            за (int я = п - 1; я >= 0; я--)            {                сумма = 0;                за (int k = я + 1; k < п; k++)                    сумма += Лу[я, k] * Икс[k];                Икс[я] = (1 / Лу[я, я]) * (у[я] - сумма);            }            возвращаться Икс;        }    }

Примеры кода MATLAB

функцияИкс =SolveLinearSystem(А, б)п = длина(б);    Икс = нули(п, 1);    у = нули(п, 1);    % разложения матрицы, метод Дулиттла    за я = 1: 1: п        за j = 1: 1: (я - 1)            альфа = А(я,j);            за к = 1: 1: (j - 1)                альфа = альфа - А(я,k)*А(k,j);            конецA (i, j) = альфа / A (j, j);        конецдля j = i: 1: n            альфа = А(я,j);            за к = 1: 1: (я - 1)                альфа = альфа - А(я,k)*А(k,j);            конецA (i, j) = альфа;        конецконец    % A = L + U-I    % найти решение Ly = b    за я = 1: 1: п        альфа = 0;        за к = 1: 1: я            альфа = альфа + А(я,k)*у(k);        конецy (i) = b (i) - альфа;    конец% найти решение Ux = y    за я = п: (- 1): 1        альфа = 0;        за к = (я + 1): 1: п            альфа = альфа + А(я,k)*Икс(k);        конецх (я) = (у (я) - альфа) / А (я, я);    конец конец

Смотрите также

• Блочная декомпозиция LU
• Разложение Брюа
• Разложение Холецкого
• Неполная факторизация LU
• LU сокращение
• Разложение матрицы
• QR-разложение

Примечания

1. Шварценберг-Черни, А. (1995). «О матричной факторизации и эффективном решении методом наименьших квадратов». Серия дополнений по астрономии и астрофизике. 110: 405. Bibcode:1995A и AS..110..405S.
2. Окунев и Джонсон (1997), Следствие 3.
3. Trefethen & Bau (1997), п. 166.
4. Trefethen & Bau (1997), п. 161.
5. Хорн и Джонсон (1985), Следствие 3.5.5
6. Хорн и Джонсон (1985), Теорема 3.5.2
7. Окунев и Джонсон (1997)
8. Домохозяин (1975)
9. Голуб и Ван Лоан (1996), п. 112, 119.
10. Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001). Введение в алгоритмы. MIT Press и McGraw-Hill. ISBN  978-0-262-03293-3.
11. Шабат, Гиль; Шмуэли, Янив; Айзенбуд, Ярив; Авербух, Амир (2016). «Рандомизированное разложение LU». Прикладной и вычислительный гармонический анализ. 44 (2): 246–272. arXiv:1310.7202. Дои:10.1016 / j.acha.2016.04.006.
12. Банч и Хопкрофт (1974)
13. Trefethen & Bau (1997), п. 152.
14. Голуб и Ван Лоан (1996), п. 121

Рекомендации

• Связка, Джеймс Р .; Хопкрофт, Джон (1974), "Треугольная факторизация и обращение быстрым матричным умножением", Математика вычислений, 28 (125): 231–236, Дои:10.2307/2005828, ISSN  0025-5718, JSTOR  2005828.
• Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), Введение в алгоритмы, MIT Press и McGraw-Hill, ISBN  978-0-262-03293-3.
• Голуб, Джин Х.; Ван Лоан, Чарльз Ф. (1996), Матричные вычисления (3-е изд.), Балтимор: Джонс Хопкинс, ISBN  978-0-8018-5414-9.
• Хорн, Роджер А .; Джонсон, Чарльз Р. (1985), Матричный анализ, Издательство Кембриджского университета, ISBN  978-0-521-38632-6. См. Раздел 3.5. N − 1
• Домохозяин, Олстон С. (1975), Теория матриц в численном анализе, Нью-Йорк: Dover Publications, МИСТЕР  0378371.
• Окунев, Павел; Джонсон, Чарльз Р. (1997), Необходимые и достаточные условия существования ЛУ-факторизации произвольной матрицы, arXiv:math.NA/0506382.
• Пул, Дэвид (2006), Линейная алгебра: современное введение (2-е изд.), Канада: Томсон Брукс / Коул, ISBN  978-0-534-99845-5.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, BP (2007), «Раздел 2.3», Числовые рецепты: искусство научных вычислений (3-е изд.), Нью-Йорк: Издательство Кембриджского университета, ISBN  978-0-521-88068-8.
• Trefethen, Ллойд Н.; Бау, Дэвид (1997), Числовая линейная алгебра, Филадельфия: Общество промышленной и прикладной математики, ISBN  978-0-89871-361-9.

внешняя ссылка

Рекомендации

• LU разложение на MathWorld.
• LU разложение на Математика-Linux.
• LU разложение в Институт целостных численных методов
• Факторизация матрицы LU. Ссылка на MATLAB.

Компьютерный код

• ЛАПАК представляет собой набор подпрограмм FORTRAN для решения задач плотной линейной алгебры
• АЛГЛИБ включает частичный перенос LAPACK на C ++, C #, Delphi и т. д.
• Код C ++, Профессор Дж. Лумис, Дейтонский университет
• Код C, Библиотека исходников по математике
• LU в X10
• [1] Лу в C ++ Анил Педгаонкар
• Рандомизированный код LU MATLAB

Интернет-ресурсы

• WebApp описательно решает системы линейных уравнений с LU Decomposition
• Матричный калькулятор, bluebit.gr
• Инструмент разложения LU, uni-bonn.de
• LU разложение к Эд Пегг младший, Демонстрационный проект Wolfram, 2007.