LU разложение

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

Определения [ править ]

Разложение по LDU матрицы Уолша

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

${\ displaystyle A = LU.}$

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

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

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

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

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

${\displaystyle PA=LU,}$

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

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

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

${\displaystyle PAQ=LU,}$

где L , U и Р имеют значения , определенные выше, а Q представляет собой матрицу перестановок , что сортирует столбцы A . ^[4]

Разложение по нижнему диагонали и верхнему (LDU) [ править ]

Нижний диагональное-верхний (LDU) разложение является разложением вида

${\displaystyle A=LDU,}$

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

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

Пример [ править ]

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

${\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}l_{11}&0\\l_{21}&l_{22}\end{bmatrix}}{\begin{bmatrix}u_{11}&u_{12}\\0&u_{22}\end{bmatrix}}.}$

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

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

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

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

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

${\displaystyle {\begin{bmatrix}4&3\\6&3\end{bmatrix}}={\begin{bmatrix}1&0\\1.5&1\end{bmatrix}}{\begin{bmatrix}4&3\\0&-1.5\end{bmatrix}}.}$

Существование и уникальность [ править ]

Квадратные матрицы [ править ]

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

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

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

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

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

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

Общие матрицы [ править ]

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

Алгоритмы [ править ]

Закрытая формула [ править ]

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

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

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

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

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

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

Это можно сделать, умножив A ^{( n  - 1)} слева на нижнюю треугольную матрицу

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

то есть единичная матрица N x N, в которой ее n -й столбец заменен вектором${\displaystyle {\begin{pmatrix}0&\dotsm &0&1&-l_{n+1,n}&\dotsm &-l_{N,n}\end{pmatrix}}^{\textsf {T}}.}$

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

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

После N  - 1 шагов мы удалили все матричные элементы ниже главной диагонали, так что мы получили верхнюю треугольную матрицу A ^{( 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)}=\dotsm =L_{1}^{-1}\dotsm L_{N-1}^{-1}A^{(N-1)}.}$

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

${\displaystyle L={\begin{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}&1\end{pmatrix}}.}$

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

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

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

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

Через рекурсию [ править ]

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

Для данной матрицы A пусть P ₁ - матрица перестановок такая, что

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

где , если в первом столбце A есть ненулевая запись ; или в противном случае возьмем P ₁ как единичную матрицу. Теперь пусть , если ; или иначе. У нас есть${\textstyle a\neq 0}$${\textstyle c=1/a}$${\textstyle a\neq 0}$${\textstyle c=0}$

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

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

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

которая представляет собой разложение LUP из A .

Рандомизированный алгоритм [ править ]

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

Теоретическая сложность [ править ]

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

Разложение по разреженной матрице [ править ]

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

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

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

Приложения [ править ]

Решение линейных уравнений [ править ]

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

${\displaystyle Ax=b,}$

мы хотим решить уравнение относительно x , учитывая A и b . Предположим, мы уже получили LUP-разложение A такое, что , so .${\textstyle PA=LU}$${\textstyle LUx=Pb}$

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

1. Сначала мы решаем уравнение относительно y .${\textstyle Ly=Pb}$
2. Во-вторых, мы решаем уравнение относительно x .${\textstyle Ux=y}$

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

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

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

Инвертирование матрицы [ править ]

При решении системы уравнений, б , как правило , рассматривается как вектор с длиной , равной высоте матрицы A . В матричной инверсии , однако, вместо вектора Ь , мы имеем матрицу B , где B является в н матрице с размерностью р матрицей, так что мы пытаемся найти матрицу X (также н матрицы с размерностью р матрица):

${\displaystyle AX=LUX=B.}$

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

Вычисление определителя [ править ]

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

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

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

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

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

Примеры кода [ править ]

Пример кода C [ править ]

/ * INPUT: A - массив указателей на строки квадратной матрицы, имеющей размерность N * Tol - малое число допуска для обнаружения отказа, когда матрица близка к вырожденной * OUTPUT: матрица A изменена, она содержит копию обеих матриц LE и U как A = (LE) + U, такое что P * A = L * U. * Матрица перестановок сохраняется не как матрица, а в целочисленном векторе P размера N + 1 *, содержащем индексы столбцов, где матрица перестановок имеет «1». Последний элемент P [N] = S + N, * где S - количество обменов строк, необходимых для вычисления определителя, det (P) = (- 1) ^ S * / int  LUPDecompose ( double  ** A ,  int  N ,  двойной Tol ,  int  * P )  { int  i ,  j ,  k ,  imax ;  двойной  maxA ,  * ptr ,  absA ; для  ( i  =  0 ;  i  <=  N ;  i ++ )  P [ i ]  =  i ;  // Матрица единичной перестановки, P [N] инициализирована N для  ( я  =  0 ;  я  <  N ;  я ++ )  {  maxA  =  0,0 ;  imax  =  i ; для  ( K  =  я ;  K  <  N ;  K ++ ) ,  если  (( Абс  =  FABS ( [ к ] [ я ])) > MAXA ) { MAXA = Абс ; imax = k ; }           если  ( maxA  <  Tol )  вернуть  0 ;  // сбой, матрица вырожденная if  ( imax  ! =  i )  {  // поворот P  j  =  P [ i ];  P [ i ]  =  P [ imax ];  P [ imax ]  =  j ; // поворот строк A  ptr  =  A [ i ];  A [ i ]  =  A [ imax ];  A [ imax ]  =  ptr ; // подсчет опорных точек, начиная с N (для определителя)  P [ N ] ++ ;  } для  ( j  =  i  +  1 ;  j  <  N ;  j ++ )  {  A [ j ] [ i ]  / =  A [ i ] [ i ]; для  ( k  =  i  +  1 ;  k  <  N ;  k ++ )  A [ j ] [ k ]  - =  A [ j ] [ i ]  *  A [ i ] [ k ];  }  } возврат  1 ;  // декомпозиция завершена }/ * INPUT: A, P заполнены LUPDecompose; b - вектор rhs; N - размерность * ВЫХОД: x - вектор решения A * x = b * / void  LUPSolve ( double  ** A ,  int  * P ,  double  * b ,  int  N ,  double  * x )  { для  ( int  я  =  0 ;  я  <  N ;  я ++ )  {  х [ я ]  =  б [ P [ я ]]; для  ( int  k  =  0 ;  k  <  i ;  k ++ )  x [ i ]  - =  A [ i ] [ k ]  *  x [ k ];  } for  ( int  i  =  N  -  1 ;  i  > =  0 ;  i - )  {  for  ( int  k  =  i  +  1 ;  k  <  N ;  k ++ )  x [ i ]  - =  A [ i ] [ k ]  *  х [ к ]; х [ я ]  / =  А [ я ] [ я ];  } }/ * INPUT: A, P заполнены LUPDecompose; N - размерность * OUTPUT: IA - это обратная исходная матрица * / void  LUPInvert ( double  ** A ,  int  * P ,  int  N ,  double  ** IA )  {  for  ( int  j  =  0 ;  j  <  N ;  j ++ )  {  for  ( int  i  =  0 ;  i  <  N ;  i ++ )  {  IA [ i ] [ j ]  =  P [ i ]  ==  j  ?  1,0  :  0,0 для  ( int  k  =  0 ;  k  <  i ;  k ++ )  IA [ i ] [ j ]  - =  A [ i ] [ k ]  *  IA [ k ] [ j ];  } for  ( int  i  =  N  -  1 ;  i  > =  0 ;  i - )  {  for  ( int  k  =  i  +  1 ;  k  <  N ;  k ++ )  IA [ i ] [ j ]  - =  A [ i ] [ k ]  *  IA [ k ] [ j ]; IA [ i ] [ j ]  / =  A [ i ] [ i ];  }  } }/ * INPUT: A, P заполнены LUPDecompose; N - размерность. * OUTPUT: функция возвращает определитель исходной матрицы * / double  LUPDeterminant ( double  ** A ,  int  * P ,  int  N )  { двойной  det  =  A [ 0 ] [ 0 ]; для  ( int  i  =  1 ;  i  <  N ;  i ++ )  det  * =  A [ i ] [ i ]; return  ( P [ N ]  -  N )  %  2  ==  0  ?  det  :  - det }

Пример кода C # [ править ]

открытый  класс  SystemOfLinearEquations {  public  double []  SolveUsingLU ( double [,]  matrix ,  double []  rightPart ,  int  n )  {  // разложение матрицы  double [,]  lu  =  new  double [ n ,  n ];  двойная  сумма  =  0 ;  для  ( int  i  =  0 ;  i  <  n ;  i ++) {  для  ( int  j  =  i ;  j  <  n ;  j ++)  {  сумма  =  0 ;  для  ( int  k  =  0 ;  k  <  i ;  k ++)  sum  + =  lu [ i ,  k ]  *  lu [ k ,  j ];  lu [ i ,  j ]  =  матрица [ i ,  j]  -  сумма ;  }  для  ( int  j  =  i  +  1 ;  j  <  n ;  j ++)  {  sum  =  0 ;  для  ( int  k  =  0 ;  k  <  i ;  k ++)  sum  + =  lu [ j ,  k ]  *  lu [ k ,  i ];  lu [ j ,  i ] =  ( 1  /  lu [ i ,  i ])  *  ( матрица [ j ,  i ]  -  сумма );  }  } // lu = L + UI  // найти решение Ly = b  double []  y  =  new  double [ n ];  для  ( int  я  =  0 ;  я  <  п ;  я ++)  {  сумма  =  0 ;  для  ( int  k  =  0 ;  k  <  i ;  k ++)  sum  + =  lu [ i ,  k ]  *  y [ k ];  у[ i ]  =  rightPart [ i ]  -  сумма ;  }  // находим решение Ux = y  double []  x  =  new  double [ n ];  для  ( int  я  =  п  -  1 ;  я  > =  0 ;  я -)  {  сумма  =  0 ;  для  ( int  k  =  i  +  1 ;  k  <  n ;  k++)  сумма  + =  lu [ i ,  k ]  *  x [ k ];  x [ i ]  =  ( 1  /  lu [ i ,  i ])  *  ( y [ i ]  -  сумма );  }  return  x ;  } }

Пример кода MATLAB [ править ]

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

См. Также [ править ]

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

Примечания [ править ]

Ссылки [ править ]

• Связка, Джеймс Р .; Hopcroft, Джон (1974), "Треугольная факторизационная и инверсия быстрого умножения матриц", Математика вычислений , 28 (125): 231-236, DOI : 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), Матричный анализ , Cambridge University Press, ISBN 978-0-521-38632-6. См. Раздел 3.5. N  - 1
• Хаусхолдер, Алстон С. (1975), Теория матриц в численном анализе , Нью-Йорк: Dover Publications , MR  0378371.
• Окунев, Павел; Джонсон, Чарльз Р. (1997), Необходимые и достаточные условия для существования LU-факторизации произвольной матрицы , arXiv : math.NA/0506382.
• Пул, Дэвид (2006), Линейная алгебра: современное введение (2-е изд.), Канада: Томсон Брукс / Коул, ISBN 978-0-534-99845-5.
• Нажмите, WH; Теукольский С.А.; Феттерлинг, штат Вашингтон; Фланнери, Б. П. (2007), «Раздел 2.3» , Численные рецепты: Искусство научных вычислений (3-е изд.), Нью-Йорк: Cambridge University Press, ISBN 978-0-521-88068-8.
• Trefethen, Lloyd N .; Бау, Дэвид (1997), Численная линейная алгебра , Филадельфия: Общество промышленной и прикладной математики, ISBN 978-0-89871-361-9.

Внешние ссылки [ править ]

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

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

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

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

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

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