LU 분해

수치 분석과 선형 대수에서, 하위-상위(LU) 분해 또는 인수 분해는 하위 삼각 행렬과 상위 삼각 행렬의 곱으로 행렬을 인수 분해한다. (행렬 분해 참조).제품에는 치환 매트릭스도 포함되어 있는 경우가 있습니다.LU 분해는 가우스 제거의 매트릭스 형태로 볼 수 있다.컴퓨터는 보통 LU 분해를 사용하여 선형 방정식의 제곱계를 풀고 행렬을 반전시키거나 행렬의 행렬식을 계산할 때 중요한 단계이기도 합니다.LU 분해는 1938년 ^[1]폴란드 수학자 타데우시 바나치에비치에 의해 도입되었다.

정의들

월시 행렬의 LDU 분해

A를 정사각형 행렬이라고 하자.LU 인수분해는 행 및/또는 열의 순서 또는 순열을 적절히 사용하여 A를 아래쪽 삼각형 행렬 L과 위쪽 삼각형 행렬 U의 두 인자로 분해하는 것을 의미합니다.

(\displaystyle A=LU)

아래쪽 삼각행렬에서는 대각선 위의 모든 요소가 0이고 위쪽 삼각행렬에서는 대각선 아래의 모든 요소가 0입니다.예를 들어 3 × 3 행렬A의 경우 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}\ell _{11}&, 0&, 0\\\ell _{21}&, \ell _{22}&, 0\\\ell _{31일}&, \ell _{32}&, \ell _{33}\end{bmatrix}}{\begin{bmatrix}u_{11}&, u_{12}&, u_{13}\\0&, u_{22}&, u_{23}\\0&, 0&, u_{33}.\end{bmatrix}}.}

행렬에서 올바른 순서 또는 순열이 없으면 인수분해가 실현되지 않을 수 있습니다. ${\textstyle a_{11}=\ell _{11}u_{11}}$ 를 들어 행렬 곱셈을 확장하면 ${\textstyle a_{11}=\ell _{11}u_{11}}$ ${\textstyle a_{11}=\ell _{11}u_{11}}$ ${\textstyle a_{11}=\ell _{11}u_{11}}$ ${\textstyle a_{11}=\ell _{11}u_{11}}$ 11 { $textstyle$ a $_$ { $11$ } = \ $ell$ ${\textstyle a_{11}=\ell _{11}u_{11}}$ _ { $11$ } $u _$ { 11 } ${\textstyle a_{11}=\ell _{11}u_{11}}$ ${\textstyle a_{11}=0}$ $0$ 인 $,$ ${\textstyle u_{11}}$ ${\textstyle \ell _{11}}$ 11 {\ {\ {\ {\ ${\$ 11 ${\textstyle u_{11}}$ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ for for for for for for {\ {\ {\ {\ $11$ u_{ $textstyle$ ${\textstyle \ell _{11}}$ $a_{$ $11}$ _ a for for for for for for a a a a a { textstyle_{11 ${\textstyle \ell _{11}}$ } } u_{11} $11$ ${\textstyle u_{11}}$ for for for for또는 U는 단수입니다.이것은, A가 비표준(반전 불가)인 경우는 불가능합니다.이것은 절차상의 문제입니다.변환된 행렬의 첫 번째 요소가 0이 아니도록 A의 행을 정렬하는 것만으로 제거할 수 있습니다.이후의 인수분해 순서에서도 같은 문제를 해결할 수 있습니다.다음의 기본적인 순서를 참조해 주세요.

부분 피벗을 사용한 LU 인수분해

LU 인수 분해에는 행(또는 열)의 적절한 순열이 충분한 것으로 나타났습니다.부분 피벗(LUP)을 사용한 LU 인수분할은 행 순열만을 사용한 LU 인수분할을 말합니다.

PA=LU,

여기서 L과 U는 다시 아래쪽 및 위쪽 삼각 행렬이고 P는 A로 왼쪽 곱하면 A의 행을 정렬하는 치환 행렬입니다.모든 제곱 행렬은 이 ^[2]형태로 인수분해될 수 있으며 인수분해는 실제로 ^[3]수치적으로 안정적입니다.이것은 LUP 분해를 실제로 유용한 기술로 만든다.

풀 피벗을 사용한 LU 인수분해

완전 피벗을 사용하는 LU 인수분해에는 행과 열의 순열이 모두 포함됩니다.

PAQ=LU,

여기서 L, U 및 P는 이전과 같이 정의되며 Q는 ^[4]A의 열을 정렬하는 순열 행렬입니다.

Lower-Diagnal-Upper(LDU; 하부대각상부) 분해

Lower-Dangular-Upper(LDU; 하부 대각선 상부) 분해는 다음 형식의 분해입니다.

A=LDU,

여기서 D는 대각행렬이고 L과 U는 단위각행렬이며, 이는 L과 U의 대각선 상의 모든 엔트리가 하나임을 의미합니다.

직사각형 행렬

앞에서 우리는 A가 정사각형 행렬이어야 한다고 요구했지만,^[5] 이러한 분해는 모두 직사각형 행렬로도 일반화될 수 있다.이 경우, L과 D는 모두 A와 행 수가 같고 U는 A와 치수가 정확히 같은 정사각형 행렬이다.위쪽 삼각형의 경우 왼쪽 상단 모서리에서 시작하는 주 대각선 아래에 0개의 항목만 있는 것으로 해석해야 합니다.마찬가지로 U에 대한 보다 정확한 용어는 행렬 A의 "행 에켈론 형식"이라는 것입니다.

예

다음 2x2 행렬을 인수분해합니다.

{bmatrix}4&3\end {bmatrix}=cisco {bmatrix}\ell _{11}&0\\ell _{22}\end {bmatrix}u_{11}&u_{12}\0&{bmatrix}.

이 단순한 행렬의 LU 분해를 찾는 한 가지 방법은 검사로 간단히 선형 방정식을 푸는 것입니다.행렬 곱셈을 확장하면

{syslog {aligned}\ell _{11}+0\cdot 0&=4\ell _{11}+0\cdot u_{12}+0\cdot u_{22}&=3\ell _cdot u_{11}+\cdot 0=6\ell\end { aligned}

이 방정식의 체계는 충분히 결정되지 않았다.이 경우 L 행렬과 U 행렬의 0이 아닌 두 요소는 솔루션의 매개 변수이며 임의의 0이 아닌 값으로 임의로 설정할 수 있습니다.따라서 고유한 LU 분해를 찾으려면 L과 U 행렬에 약간의 제한을 둘 필요가 있습니다.예를 들어 삼각행렬 L을 단위삼각행렬로 하는 것이 편리하다(즉, 주대각의 모든 엔트리를 1로 설정한다).그리고 방정식 시스템은 다음과 같은 해답을 가지고 있습니다.

{\displaystyle}\ell _{11}=\ell _{22}&=1\ell _{21}&=1.5\\u_{11}&=4\u_{12}&=3\u_{22}&=-1.5\end{aligned}}

이러한 값을 수율 이상의 LU 분해로 대체

(\displaystyle {bmatrix}4&3&3\end{bmatrix}=bmatrix1&0\1).5&1\end{bmatrix}{\color{bmatrix}4&3\0&-1.5\end {bmatrix}.}

존재와 고유성

정사각형 행렬

모든 정사각형 ${\textstyle A}$ A $(텍스트$ 스타일 A $)$ 는 LUP와 PLU ^[2]인수분해를 허용합니다.A $(\textstyle$ A $)$ 가 ${\textstyle A}$ 반전 가능한 ${\textstyle A}$ 주요 마이너가 모두 0이^[6] 아닌 경우에만 LU(또는 LDU) 인수분해를 허용합니다(예를 들어 ${\begin{bmatrix}0&1\\1&0\end{bmatrix}}$ ${\begin{bmatrix}0&1\\1&0\end{bmatrix}}$ 0 $](\$ end ${brix}).$ A $(\textstyle$ A $)$ 가 ${\textstyle A}$ ${\textstyle k}$ k(\ $textstyle$ k ${\textstyle k}$ 의 단수 매트릭스인 ${\textstyle A}$ 첫 ${\textstyle k}$ k $(\textstyle$ k $)$ 가 ${\textstyle k}$ 0이 아닌 경우 LU 인수분해를 허용하지만 그 반대가 사실이 ^[7]아닙니다.

정사각형 역행렬에 LDU(L과 U의 모든 대각 엔트리가 1인 인수분해)가 있는 경우 인수분해는 ^[6]고유합니다.이 경우 L $\textstyle$ L $($ ${\textstyle U}$ U $\textstyle$ U ${\textstyle U}$ 의 대각선이 1로 구성되어야 하는 경우에도 LU 인수분해는 고유합니다.

일반적으로 정사각형 $A_{n\times n}$ $A_{n\times n}$ n $A_{n\times n}$ × $A_{n\times n}$ $(\$ A_ ${n\times$ n})은 $A_{n\times n}$ 다음 중 하나를 가질 수 있습니다.

고유한 LU 인수분해(위에서 설명한 바와 같이)
두 개 이상의 첫 번째(n-1) 열이 선형 종속적이거나 첫 번째(n-1) 열 중 하나가 0이면 A에는 LU 인수 분해가 무한히 많습니다.
첫 번째 (n-1) 열이 0이 아니고 선형 독립적이며 하나 이상의 선행 주소수가 0이면 LU 인수 분해가 없습니다.

케이스 3에서는 대각선 $a_{jj}$ $(\$ 를 $a_{jj}\pm \varepsilon$ ± ${\(\displaystyle a_{jj}\pm \varepsilon)$ 로 $a_{jj}\pm \varepsilon$ 변경하여 ^[8]LU 인수분해를 근사화할 수 있습니다.

대칭 정의 행렬

A가 대칭(또는 에르미트, A가 복소수) 정의 행렬이라면 U가 L의 공역 전치 행렬이 되도록 사물을 배열할 수 있다.즉, A를 다음과 같이 쓸 수 있습니다.

(\displaystyle A=)LL^{*},

이 분해는 콜레스키 분해라고 불립니다.촐레스키 분해는 항상 존재하며 행렬이 양의 유한일 경우 고유합니다.또한 콜레스키 분해를 계산하는 것이 다른 LU 분해를 계산하는 것보다 더 효율적이고 수치적으로 안정적입니다.

일반행렬

(반전가능하지 않은) 모든 필드의 행렬에 대해 LU 인수분해를 갖는 정확한 필요충분조건이 알려져 있습니다.조건은 특정 하위 행렬의 등급으로 표시됩니다.LU 분해를 얻기 위한 가우스 제거 알고리즘도 이 가장 일반적인 경우로 ^[9]확장되었습니다.

알고리즘

닫힌 공식

LDU 인수분해가 존재하며 고유할 경우, 원래 행렬 ^[10]A의 특정 하위 행렬의 결정인자 비율에 관해 L, D 및 U의 요소에 대해 닫힌(명시적인) 공식이 있습니다. ${\textstyle D_{1}=A_{1,1}}$ ${\textstyle D_{1}=A_{1,1}}$ $=$ ${\textstyle D_{1}=A_{1,1}}$ 1 ${\textstyle D_{1}=A_{1,1}}$ { $textstyle D_{1$ }= $A_{1,1$ i ${\textstyle i=2,\ldots ,n}$ , $…,$ { $textstyle i=2,\ldots,$ ${\textstyle D_{i}}$ ${\textstyle i=2,\ldots ,n}$ ${\textstyle D_{i}}$ { $textstyle D_{$ i ${\textstyle D_{i}}$ }는 ${\textstyle (i-1)}$ i $(\textstyle$ i $)$ 에 ${\textstyle i}$ 대한 주요 행렬의 비율이다 $.$ 결정 요인의 계산은 계산 비용이 많이 들기 때문에, 이 명시적 공식은 실제로 사용되지 않는다.

가우스 제거 사용

다음 알고리즘은 본질적으로 수정된 형태의 가우스 제거입니다.이 알고리즘을 사용하여 LU 분해를 계산하려면 하위 항을 무시하고 ${\tfrac {2}{3}}n^{3}$ ${\tfrac {2}{3}}n^{3}$ ${\tfrac {2}{3}}n^{3}$ 3 \ $displaystyle$ \ $tfrac {2} {$ 3} n $^{3}}$ 개의 ${\tfrac {2}{3}}n^{3}$ 부동 소수점 연산이 ${\tfrac {2}{3}}n^{3}$ 합니다.부분 피벗은 2차 항만 추가합니다. 전체 ^[11]피벗의 경우는 그렇지 않습니다.

N × N $A=(a_{i,j})_{1\leq i,j\leq N}$ A $A=(a_{i,j})_{1\leq i,j\leq N}$ ( $A=(a_{i,j})_{1\leq i,j\leq N}$ , $A=(a_{i,j})_{1\leq i,j\leq N}$ ) $A=(a_{i,j})_{1\leq i,j\leq N}$ $A=(a_{i,j})_{1\leq i,j\leq N}$ , $A=(a_{i,j})_{1\leq i,j\leq N}$ N { $display$ $style$ A $A^{(0)}:=A$ $=$ ( $a$ $_$ { $i$ , $j$ ) $_ { 1$ \ $leq$ i , $j$ \ $leq$ N $A=(a_{i,j})_{1\leq i,j\leq N}$ } $A^{(0)}:=A$ an 、 $A^{(0)}:=A$ ( $A^{(0)}:=A$ ) : $= A$ 를 $정의$ 합니다.

이 행렬의 i번째 행에 n번째 행에 다음을 곱한 행렬 요소를 추가하여⁽ⁿ⁻¹⁾ A의 n번째 열에서 주 대각선 아래의 행렬 요소를 제거한다.

{\displaystyle -\ell _{i,n}^{(n-1)}{a_{n,n}^{(n-1)}}},\display i=n+1,\dotsc,N}.

이것은 A를 왼쪽 아래에 삼각행렬을 곱함으로써^{(n − 1)} 할 수 있다.

({display style L_{n}=pmatrix}1&&\dots &\&\&\\&\&\dots &\&\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\pmatrix\&\\\\\\\\\&\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\

즉, n번째 열이 벡터 ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ 0 ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ - ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ n + ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ , ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ - ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ N , ${\begin{pmatrix}0&\dotsm &0&1&-\ell _{n+1,n}&\dotsm &-\ell _{N,n}\end{pmatrix}}^{\textsf {T}}.$ )로 대체되는 N × N ID 매트릭스. $(\display$ { $begin {pmatrix} 0&\dotsm$ & $0&1&\ell$ _{ $n+$ 1,n}&\ $dots$ & $pm-ell {N},$ $}$

설정했습니다.

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

N - 1 단계 후, 우리는 주 대각선 아래의 모든 행렬 요소를 제거하였으므로, 우리는 상부 삼각^{(N − 1)} 행렬 A를 얻는다.우리는 부패를 발견한다.

{{displaystyle A=L_{1}^{{1}A^{(0)}=L_{1}^{(1)=L_{1}^{-1}L_{1}L_{2}A^{(1)=L_{2}A^{{1}{1}L_{1}^{1}L_{1}L_{1}L_{{1}L_{1}L_{{1}L_{{1}L_{{{(1)}^{{{{{{{{{{1}}^{{{{{1}}^{{{{{{{{{}}}}}}^{{{{}

그 뒤 Denote의 위쪽에 삼각 행렬 A(N1−)U에 의해 및 L)L1− 1⋯ 나는 N1− 1{\textstyle L=L_{1}^{)}\dotsm − L_{N-1}^{)}}. 왜냐하면 낮은 삼각 행렬은 때때로의 역은 다시 낮은 삼각 행렬, 그리고 두개 하단의 삼각형의 매트릭스의 곱셈은 다시 낮은 삼각 행렬은 L은 l.트라이ower각행렬게다가, 라는 것을 알 수 있다.

({display style L=begin{pmatrix}1&&\ell_{2,1}&\dots&\\dots&\cdots&\ell_{n+1,n}&\vots&\dots&\ell_{n}&\ddots&\ell_{n})}

A $A=LU.$ $A=LU.$ . $A=LU.$ { $displaystyle$ A = $LU$ }를 구합니다 $.$

이 알고리즘이 기능하려면 각 단계에서 $a_{n,n}^{(n-1)}\neq 0$ ( $a_{n,n}^{(n-1)}\neq 0$ $a_{n,n}^{(n-1)}\neq 0$ $a_{n,n}^{(n-1)}\neq 0$ ) $a_{n,n}^{(n-1)}\neq 0$ ${$ $display$ style $a_{n,n}^{(n-1)}\neq$ 0 $}$ 이 $a_{n,n}^{(n-1)}\neq 0$ $a_{n,n}^{(n-1)}\neq 0$ 합니다( 「 $\ell _{i,n}$ $\$ _ ${i,n}$ 의 정의를 참조).이 가정이 어느 시점에서 실패했을 경우는, 속행하기 전에, n번째 행을 그 아래의 다른 행과 교환할 필요가 있습니다.따라서 일반적으로 LU 분해는 $P^{-1}A=LU$ P - $P^{-1}A=LU$ A $P^{-1}A=LU$ $P^{-1}A=LU$ $P^{-1}A=LU$ (\ $displaystyle$ P $^{-1}A=LU$ 처럼 보인다.

이 절차를 통해 얻은 분해는 둘리틀 분해이며, L의 주 대각선은 1s로만 구성되어 있습니다.열의 배수를 추가하여 대각선 위의 요소를 제거함으로써 진행한다면(행의 배수를 추가하여 대각선 아래의 요소를 제거하는 대신), U의 대각선이 1인 Crout 분해를 얻을 수 있다.

주어진 행렬 A의 Crout 분해를 생성하는 또 다른 (등가) 방법은 A의 전치 둘리틀 분해를 얻는 것이다.실제로 A ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ 0 ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ {\ $textstyle$ A $^{\textsf {T$ }} = $L_{0}$ 인 ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ $U_{0}$ 은 ${\textstyle A^{\textsf {T}}=L_{0}U_{0}}$ 이 절에서 설명하는 알고리즘을 통해 얻은 LU 분해이며, L ${\textstyle L=U_{0}^{\textsf {T}}}$ ${\textstyle L=U_{0}^{\textsf {T}}}$ ${\textstyle L=U_{0}^{\textsf {T}}}$ T {\ $textstyle$ L $=U_{0}^{T}}$ 및 ${\textstyle L=U_{0}^{\textsf {T}}}$ ${\textstyle U=L_{0}^{\textsf {T}}}$ $A=LU$ ${\textstyle U=L_{0}^{\textsf {T}}}$ ${\textstyle U=L_{0}^{\textsf {T}}}$ T {\ $textstyle$ U= $L_{0}^{T$ 를 ${\textstyle L=U_{0}^{\textsf {T}}}$ 으로써 얻을 수 $A=LU$ L은 $A=LU$ 과 같다.LU $}$ 는 $A=LU$ Crout 분해입니다.

재귀에 의한

Cormen ^[12]등은 LUP 분해에 대한 재귀 알고리즘을 설명한다.

행렬 A가 주어졌을 때, P를 다음과 같이 치환 행렬로 하자₁.

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

A'&\&\end {array}\right

${\textstyle a\neq 0}$ 서 a ${\textstyle a\neq 0}$ 0 \ $textstyle$ a \ $neq$ 0 ${\textstyle a\neq 0}$ text 。A의 첫 번째 열에 0 이외의 엔트리가 있는 경우는 P를 ID₁ 매트릭스로 합니다.c ${\textstyle c=1/a}$ / ${\textstyle c=1/a}$ { $textstyle$ c= 1 / a ${\textstyle c=1/a}$ $（ textstyle$ a \ $neq$ 0 ${\textstyle a\neq 0}$ ${\textstyle c=0}$ 、 ${\textstyle c=0}$ 0 { $textstyle$ c= $0$ ${\textstyle c=0}$ ）。우리는 가지고 있다.

P_{1}A=\left({\begin{array}{ccc}1&0&\hline&\displays&\displays&}I_{n-1}&\&end{array}\right({\begin{array}{c}a&w^{T}}\hline&\0&A'-cvw^{T}}\textf {T}\&\end{array}}\right)

LUP ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ P ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ ( ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ - ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ v ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ $′$ \ $textstyle$ P' \ $left$ ( $A$ ' - $cvw$ ^ { T } \ $textsf$ { $T$ } \ ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ )를 재귀적으로 찾을 수 있습니다.= $L'$ U ${\textstyle P'\left(A'-cvw^{\textsf {T}}\right)=L'U'}$ . ${\textstyle v'=P'v}$ v ${\textstyle v'=P'v}$ ′ ${\textstyle v'=P'v}$ = ${\textstyle v'=P'v}$ $′$ v \ $textstyle$ v' ${\textstyle v'=P'v}$ P $'v$ $.$

\displaystyle \left({\begin{array}{ccc}1&\hline&\0&P'&\&end{array}}\오른쪽)P_{1}A=\left({\begin{array}{ccc}1&0&\hline&\cv'&L'&\&\end{array}\right)\left({\begin{array}{ccc}a&w^{t}\h}&h}\line)\lineU'&\&\end {array}\right})}

A의 LUP 분해입니다.

랜덤화 알고리즘

랜덤화 알고리즘을 사용하여 LU 분해에 대한 낮은 순위 근사치를 찾을 수 있습니다.입력 ${\textstyle A}$ A $(\textstyle$ A $)$ 와 ${\textstyle A}$ 원하는 ${\textstyle k}$ 순위 ${\textstyle k}$ k(\ $textstyle k)$ 가 주어지면 랜덤화된 LU는 각각 m ${\textstyle k\times n}$ ${\textstyle m\times k}$ × ${\textstyle m\times k}$ (\ $textstyle$ m $\times$ k) ${\textstyle k\times n}$ 의 ${\textstyle P,Q}$ ${\textstyle m\times k}$ ${\textstyle m\times k}$ $/$ 상위 사다리꼴 ${\textstyle L,U}$ ${\textstyle P,Q}$ L ${\textstyle L,U}$ $(\textstyle$ L $,U)$ 와 ${\textstyle L,U}$ ${\textstyle k\times n}$ k $textstyle$ k $)$ 를 반환합니다 $.$ ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ A ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ - ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ U ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ 2 ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ C ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ k + ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ \ $textstyle$ $\ PAQ$ - $LU$ \ $right$ \ ${$ 2 $}$ \ $leq$ C \ $sigma _$ { k + ${\textstyle \left\|PAQ-LU\right\|_{2}\leq C\sigma _{k+1}}$ 1 ${\textstyle \sigma _{k+1}}$ } 。 ${\textstyle C}$ { $textstyle$ C $}$ 는 ${\textstyle C}$ ${\textstyle \sigma _{k+1}}$ 의 파라미터에 따라 $달라지는 상수입니다.$ ut ${\textstyle A}$ A(\ $textstyle$ A ${\textstyle A}$ ^[13]

이론상의 복잡성

순서 n의 2개의 행렬을 시간 M(n)에 곱할 수 있는 경우(여기서 M(n) for^a n은 일부 n > 2에 대해), LU 분해는 시간 O(M(n)^[14]에 계산할 수 있다.이는 예를 들어 Coppersmith-Winograd 알고리즘을 기반으로 O(n^2.376) 알고리즘이 존재함을 의미합니다.

스파스 매트릭스 분해

큰 스파스 행렬을 인수분해하기 위한 특수 알고리즘이 개발되었습니다.이러한 알고리즘은 희박한 요인 L과 U를 찾으려고 합니다.이상적으로 계산 비용은 행렬의 크기가 아니라 0이 아닌 엔트리의 수에 의해 결정됩니다.

이러한 알고리즘은 행과 열을 자유롭게 교환하여 채우기(알고리즘 실행 중에 초기 0에서 0이 아닌 값으로 변경되는 항목)를 최소화합니다.

채우기를 최소화하는 순서의 일반적인 처리는 그래프 이론을 사용하여 해결할 수 있습니다.

적용들

선형 방정식 풀기

행렬 형식의 선형 방정식 시스템이 주어진 경우

A\mathbf {x} =\mathbf {b} ,

A와 b가 주어졌을 때 x에 대한 방정식을 풀려고 합니다. ${\textstyle PA=LU}$ $=$ $(텍스트 스타일$ PA=)인 A의 LUP 분해를 이미 얻었다고 가정합니다.LU ${\textstyle PA=LU}$ ${\textstyle LU\mathbf {x} =P\mathbf {b} }$ ${\textstyle LU\mathbf {x} =P\mathbf {b} }$ U ${\textstyle LU\mathbf {x} =P\mathbf {b} }$ ${\textstyle LU\mathbf {x} =P\mathbf {b} }$ ${\textstyle LU\mathbf {x} =P\mathbf {b} }$ b {\ $textstyle$ LU\ $mathbf {x}$ = $P\mathbf {b$ 입니다 $.$

이 경우 솔루션은 다음 두 가지 논리적 단계로 수행됩니다.

먼저 방정식 ${\textstyle L\mathbf {y} =P\mathbf {b} }$ y ${\textstyle L\mathbf {y} =P\mathbf {b} }$ ${\textstyle L\mathbf {y} =P\mathbf {b} }$ b { $textstyle$ L $\mathbf {y}$ = $P\mathbf {b} }$ 를 ${\textstyle L\mathbf {y} =P\mathbf {b} }$ y에 대해 푼다.
둘째, x에 대해 U ${\textstyle U\mathbf {x} =\mathbf {y} }$ $=$ ${\textstyle U\mathbf {x} =\mathbf {y} }$ {\ $textstyle$ U $\mathbf {x}$ =\ $mathbf {y} }$ ${\textstyle U\mathbf {x} =\mathbf {y} }$ 을 ${\textstyle U\mathbf {x} =\mathbf {y} }$ 푼다.

두 경우 모두 가우스 제거 프로세스를 사용하지 않고 정방향 및 역방향 치환으로 직접 해결할 수 있는 삼각 행렬(L과 U)을 다루고 있습니다(다만 LU 분해 자체를 계산하려면 이 프로세스 또는 동등한 프로세스가 필요합니다).

위의 절차를 반복하여 다른 b에 대해 방정식을 여러 번 풀 수 있습니다.이 경우 행렬 A의 LU 분해를 한 번 수행한 후 다른 b의 삼각 행렬을 푸는 것이 매번 가우스 제거를 사용하는 것보다 더 빠르고 편리합니다.행렬 L과 U는 가우스 제거 과정을 "인코딩"한 것으로 간주될 수 있습니다.

선형 방정식 시스템을 푸는 데 드는 비용은 $A$ 의 ${\textstyle A}$ ${\textstyle n}$ 가 n $(\textstyle$ n ${\textstyle n}$ 인 경우 ${\textstyle {\frac {2}{3}}n^{3}}$ ${\textstyle {\frac {2}{3}}n^{3}}$ . $(\$ 부동소수점 ${\textstyle {\frac {2}{3}}n^{3}}$ 연산입니다.따라서 QR 분해에 기반한 알고리즘보다 2배 빨라집니다. QR 분해에는 Houseer reflection을 사용할 경우 부동 소수점 연산 비용이 약 $43n3({frac$ { $4}{$ 3}} $n$ ^{3 $}})$ 소요됩니다.따라서 보통 LU 분해가 선호됩니다.^[15]

행렬 반전

방정식의 시스템을 풀 때, b는 보통 행렬 A의 높이와 같은 길이를 가진 벡터로 취급된다.그러나 행렬 반전에서는 벡터 b 대신 행렬 B가 있습니다.여기서 B는 n-by-p 행렬이므로 행렬 X(n-by-p 행렬도 있음)를 찾으려고 합니다.

(\displaystyle AX=)LUX=B.}

앞에서 설명한 것과 동일한 알고리즘을 사용하여 행렬 X의 각 열을 풀 수 있습니다.이제 B가 크기 n의 항등 행렬이라고 가정합니다.따라서 결과 X는 ^[16]A의 역수여야 합니다.

행렬식 계산

정사각형 매트릭스 A의 LUP ${\textstyle A=P^{-1}LU}$ ${\textstyle A=P^{-1}LU}$ ${\textstyle A=P^{-1}LU}$ ${\textstyle A=P^{-1}LU}$ - ${\textstyle A=P^{-1}LU}$ LU { $textstyle$ A = $P^$ { $- 1$ LU }가 ${\textstyle A=P^{-1}LU}$ 주어졌을 때 A의 행렬식은 다음과 같이 쉽게 계산할 수 있다.

(\displaystyle \det(A)=\det \left(P^{-1}\right)\det(L)\det(U)=param1)^{S}\left(\prod _{i=1}^{n}l_{i}\right)\left(\d _i=1}^{nu_{i}\right}\right)}

두 번째 방정식은 삼각행렬의 행렬식은 단순히 대각행렬의 산물이며, 순열행렬의 행렬식은 (-1)^S과 같으며, 여기서 S는 분해에서의 행 교환의 수이다.

풀 피벗을 사용한 LU 분해의 경우 ${\textstyle \det(A)}$ S를 행 및 열 교환의 총수로 하면 det ( ${\textstyle \det(A)}$ $)\textstyle \det (A)$ 도 ${\textstyle \det(A)}$ 위의 방정식의 오른쪽과 같습니다.

P를 항등행렬과 동일하게 설정함으로써 LU 분해에도 같은 방법이 쉽게 적용됩니다.

코드 예시

C 코드 예시

/* INPUT: 차원 N을 가진 정사각형 행렬의 행에 대한 포인터 배열 * Tol - 행렬이 축퇴에 가까울 때 고장을 탐지하기 위한 작은 공차 수 * 출력: 행렬 A가 변경되어 행렬 L-E와 U의 양쪽 복사본을 P*A=L*U가 되도록 A=(L-E)+U로 포함합니다. * 치환행렬은 행렬로 저장되지 않고 N+1 크기의 정수 벡터 P에 저장됩니다. * 순열 행렬에 "1"이 있는 열 인덱스를 포함합니다.마지막 요소 P[N]=S+N, * 여기서 S는 결정식 계산에 필요한 행 교환의 수, det(P)=solid1)^S */ 인트 LUPDecompose(이중으로 하다 **A, 인트 N, 이중으로 하다 톨, 인트 *P) {      인트 i, j, k, 아이맥스;      이중으로 하다 최대 A, *ptr, absA;      위해서 (i = 0; i <=> N; i++)         P[i] = i; //단위 치환 행렬, P[N]가 N으로 초기화됨      위해서 (i = 0; i < > N; i++) {         최대 A = 0.0;         아이맥스 = i;          위해서 (k = i; k < > N; k++)             한다면 ((absA = 팹(A[k][i])) > 최대 A) {                  최대 A = absA;                 아이맥스 = k;             }          한다면 (최대 A < > 톨) 돌아가다 0; //장애, 매트릭스가 퇴화됨          한다면 (아이맥스 != i) {             //P를 기동하다             j = P[i];             P[i] = P[아이맥스];             P[아이맥스] = j;              //A의 행 이동             ptr = A[i];             A[i] = A[아이맥스];             A[아이맥스] = 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;  //재조합 완료 }  /* 입력: LUPDecompose에 채워진 A, P, b - rhs 벡터, N - 차원 * 출력: x - A*x=b의 솔루션 벡터 */ 무효 LUPSolve(이중으로 하다 **A, 인트 *P, 이중으로 하다 *b, 인트 N, 이중으로 하다 *x) {      위해서 (인트 i = 0; i < > N; i++) {         x[i] = b[P[i]];          위해서 (인트 k = 0; k < > i; k++)             x[i] -= A[i][k] * x[k];     }      위해서 (인트 i = N - 1; i >= 0; i--) {         위해서 (인트 k = i + 1; k < > N; k++)             x[i] -= A[i][k] * x[k];          x[i] /= A[i][i];     } }  /* 입력: A, P에 LUPDecompose를 입력, N차원 * 출력: IA는 초기 행렬의 역행렬입니다. */ 무효 루핀버트(이중으로 하다 **A, 인트 *P, 인트 N, 이중으로 하다 **IA) {        위해서 (인트 j = 0; j < > N; j++) {         위해서 (인트 i = 0; i < > N; i++) {             IA[i][j] = P[i] == j ? 1.0 : 0.0;              위해서 (인트 k = 0; k < > i; k++)                 IA[i][j] -= A[i][k] * IA[k][j];         }          위해서 (인트 i = N - 1; i >= 0; i--) {             위해서 (인트 k = i + 1; k < > N; k++)                 IA[i][j] -= A[i][k] * IA[k][j];              IA[i][j] /= A[i][i];         }     } }  /* 입력: A, P가 LUPDecompose로 채워지고 N차원.  * OUTPUT: 함수는 초기 행렬의 행렬식을 반환합니다. */ 이중으로 하다 LUPDerminant(루프 터미널)(이중으로 하다 **A, 인트 *P, 인트 N) {      이중으로 하다 멈추다 = A[0][0];      위해서 (인트 i = 1; i < > N; i++)         멈추다 *= A[i][i];      돌아가다 (P[N] - N) % 2 == 0 ? 멈추다 : -멈추다; }

C# 코드 예시

일반의 학급 System Of Linear Equiations(시스템 Of 선형 등식) {     일반의 이중으로 하다[] 해결 사용LU(이중으로 하다[,] 매트릭스, 이중으로 하다[] 오른쪽 부품, 인트 n)     {         // 행렬 분해         이중으로 하다[,] 루 = 신규 이중으로 하다[n, n];         이중으로 하다 합 = 0;         위해서 (인트 i = 0; i < > n; i++)         {             위해서 (인트 j = i; j < > n; j++)             {                 합 = 0;                 위해서 (인트 k = 0; k < > i; k++)                     합 += 루[i, k] * 루[k, j];                 루[i, j] = 매트릭스[i, j] - 합;             }             위해서 (인트 j = i + 1; j < > n; j++)             {                 합 = 0;                 위해서 (인트 k = 0; k < > i; k++)                     합 += 루[j, k] * 루[k, i];                 루[j, i] = (1 / 루[i, i]) * (매트릭스[j, i] - 합);             }         }          // lu = L+U-I         // Ly = b의 솔루션을 찾습니다.         이중으로 하다[] y = 신규 이중으로 하다[n];         위해서 (인트 i = 0; i < > n; i++)         {             합 = 0;             위해서 (인트 k = 0; k < > i; k++)                 합 += 루[i, k] * y[k];             y[i] = 오른쪽 부품[i] - 합;         }         // Ux = y의 솔루션을 찾습니다.         이중으로 하다[] x = 신규 이중으로 하다[n];         위해서 (인트 i = n - 1; i >= 0; i--)         {             합 = 0;             위해서 (인트 k = i + 1; k < > n; k++)                 합 += 루[i, k] * x[k];             x[i] = (1 / 루[i, i]) * (y[i] - 합);         }         돌아가다 x;     } }

MATLAB 코드 예시

함수 LU = LUdecompDoolittle(A) n = 길이(A), LU = A, 행렬의 % 분해, j = 1:1:(i - 1) LU(i,j) = LU(i,j) - LU(i,j) - 1:(j)LU(1:(j - 1,j), LU(j,j), 끝 j = i:n; LU(i,j) = LU(i,j) - LU(i,1:(i - 1)*LU(1:(i - 1),j), 말단 %LU = L+U-I 말단 함수 x = SolveLinearSystem(LU, B) n = 길이(LU), y = 0(사이즈(B)), i = 1:n(i, B)에 대한 Ly = B의 솔루션을 % 구합니다.6 3 3 ; 3 4 3 ] LU = LUdecomp Doolittle (A) B = [ 1 2 3 ; 4 5 6 ; 7 8 9 ; 10 11 12 ]' x' = Solve Linearinear System (LU, B) A * x

「」를 참조해 주세요.

메모들

^ Schwarzenberg-Czerny, A. (1995). "On matrix factorization and efficient least squares solution". Astronomy and Astrophysics Supplement Series. 110: 405. Bibcode:1995A&AS..110..405S.
^ ^a ^b Okunev & Johnson(1997), Collollary 3.
^ Trefeten & Bau(1997), 페이지 166.
^ Trefeten & Bau(1997), 페이지 161.
^ Lay, David C. (2016). Linear algebra and its applications. Steven R. Lay, Judith McDonald (Fifth ed.). Harlow. p. 142. ISBN 1-292-09223-8. OCLC 920463015.
^ ^a ^b Horn & Johnson (1985), Collollary 3.5.5
^ Horn & Johnson (1985), 정리 3.5.2
^ Nhiayi, Ly; Phan-Yamada, Tuyetdong (2021). "Examining Possible LU Decomposition". North American GeoGebra Journal. 9 (1).
^ 오쿠네브 & 존슨 (1997년)
^ 세대주(1975년)
^ 골럽앤반론(1996), 페이지 112, 119.
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.
^ Shabat, Gil; Shmueli, Yaniv; Aizenbud, Yariv; Averbuch, Amir (2016). "Randomized LU Decomposition". Applied and Computational Harmonic Analysis. 44 (2): 246–272. arXiv:1310.7202. doi:10.1016/j.acha.2016.04.006. S2CID 1900701.
^ 번치 & 홉크로프트(1974년)
^ Trefeten & Bau(1997), 페이지 152.
^ 골럽앤반론(1996), 페이지 121

레퍼런스

를 클릭합니다Bunch, James R.; Hopcroft, John (1974), "Triangular factorization and inversion by fast matrix multiplication", Mathematics of Computation, 28 (125): 231–236, doi:10.2307/2005828, ISSN 0025-5718, JSTOR 2005828.
를 클릭합니다Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms, MIT Press and McGraw-Hill, ISBN 978-0-262-03293-3.
를 클릭합니다Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Baltimore: Johns Hopkins, ISBN 978-0-8018-5414-9.
섹션 3.5를 참조하십시오Horn, Roger A.; Johnson, Charles R. (1985), Matrix Analysis, Cambridge University Press, ISBN 978-0-521-38632-6.N − 1
를 클릭합니다Householder, Alston S. (1975), The Theory of Matrices in Numerical Analysis, New York: Dover Publications, MR 0378371.
를 클릭합니다Okunev, Pavel; Johnson, Charles R. (1997), Necessary And Sufficient Conditions For Existence of the LU Factorization of an Arbitrary Matrix, arXiv:math.NA/0506382.
를 클릭합니다Poole, David (2006), Linear Algebra: A Modern Introduction (2nd ed.), Canada: Thomson Brooks/Cole, ISBN 978-0-534-99845-5.
를 클릭합니다Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.3", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8.
를 클릭합니다Trefethen, Lloyd N.; Bau, David (1997), Numerical linear algebra, Philadelphia: Society for Industrial and Applied Mathematics, ISBN 978-0-89871-361-9.

외부 링크

레퍼런스

MathWorld에서의 LU 분해.
Math-Linux에서의 LU 분해.
총체적 수치법 연구소의 LU 분해
LU 행렬 인수분해MATLAB 참조.

컴퓨터 코드

LAPACK은 고밀도 선형 대수 문제를 해결하기 위한 FORTRAN 서브루틴의 집합입니다.
ALGLIB에는 C++, C#, Delphi 등에 대한 LAPACK의 일부 포트가 포함되어 있습니다.
C++ 코드입니다, 교수님.데이턴 대학교 루미스
C 코드, 수학 소스 라이브러리
X10의 LU

온라인 자원

[Schwarzenberg-1] Schwarzenberg-Czerny, A. (1995). "On matrix factorization and efficient least squares solution". Astronomy and Astrophysics Supplement Series. 110: 405. Bibcode:1995A&AS..110..405S.

[okunev-cor3-2] Okunev & Johnson(1997), Collollary 3.

[3] Trefeten & Bau(1997), 페이지 166.

[4] Trefeten & Bau(1997), 페이지 161.

[5] Lay, David C. (2016). Linear algebra and its applications. Steven R. Lay, Judith McDonald (Fifth ed.). Harlow. p. 142. ISBN 1-292-09223-8. OCLC 920463015.

[horn-cor355-6] Horn & Johnson (1985), Collollary 3.5.5

[7] Horn & Johnson (1985), 정리 3.5.2

[8] Nhiayi, Ly; Phan-Yamada, Tuyetdong (2021). "Examining Possible LU Decomposition". North American GeoGebra Journal. 9 (1).

[9] 오쿠네브 & 존슨 (1997년)

[10] 세대주(1975년)

[11] 골럽앤반론(1996), 페이지 112, 119.

[12] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3.

[13] Shabat, Gil; Shmueli, Yaniv; Aizenbud, Yariv; Averbuch, Amir (2016). "Randomized LU Decomposition". Applied and Computational Harmonic Analysis. 44 (2): 246–272. arXiv:1310.7202. doi:10.1016/j.acha.2016.04.006. S2CID 1900701.

[14] 번치 & 홉크로프트(1974년)

[15] Trefeten & Bau(1997), 페이지 152.

[16] 골럽앤반론(1996), 페이지 121

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

v t 수치 선형 대수
주요 개념	부동 소수점 수치 안정성
문제	선형 방정식 체계 행렬 분해 행렬 곱셈(알고리즘) 행렬 분할 희박한 문제
하드웨어	CPU 캐시 TLB 캐시 오비어스 알고리즘 SIMD 멀티프로세서
소프트웨어	매트랩 기본 선형 대수 서브 프로그램(BLAS) 랩 전문 라이브러리 범용 소프트웨어

Search

LU 분해

네임스페이스

더

목차

정의들

부분 피벗을 사용한 LU 인수분해

풀 피벗을 사용한 LU 인수분해

Lower-Diagnal-Upper(LDU; 하부대각상부) 분해

직사각형 행렬

예

존재와 고유성

정사각형 행렬

대칭 정의 행렬

일반행렬

알고리즘

닫힌 공식

가우스 제거 사용

재귀에 의한

랜덤화 알고리즘

이론상의 복잡성

스파스 매트릭스 분해

적용들

선형 방정식 풀기

행렬 반전

행렬식 계산

코드 예시

C 코드 예시

C# 코드 예시

MATLAB 코드 예시

「」를 참조해 주세요.

메모들

레퍼런스

외부 링크

Search

LU 분해

정의들

부분 피벗을 사용한 LU 인수분해

풀 피벗을 사용한 LU 인수분해

Lower-Diagnal-Upper(LDU; 하부대각상부) 분해

직사각형 행렬

예

존재와 고유성

정사각형 행렬

대칭 정의 행렬

일반행렬

알고리즘

닫힌 공식

가우스 제거 사용

재귀에 의한

랜덤화 알고리즘

이론상의 복잡성

스파스 매트릭스 분해

적용들

선형 방정식 풀기

행렬 반전

행렬식 계산

코드 예시

C 코드 예시

C# 코드 예시

MATLAB 코드 예시

「 」를 참조해 주세요.

메모들

레퍼런스

외부 링크

「」를 참조해 주세요.