ldl

에르미트 부정부호 행렬(Hermitian Indefinite Matrix)의 블록 LDL 분해

구문

[L,D] = ldl(A)

[L,D] = ldl(A,triangle)

[L,D,P] = ldl(___)

[L,D,P] = ldl(___,outputForm)

[L,D,P] = ldl(S)

[L,D,P,C] = ldl(S)

[L,D,P,C] = ldl(S,tol)

[___] = ldl(___,triangle)

[___] = ldl(___,outputForm)

설명

비희소 형식 데이터

[L,D] = ldl(A)는 비희소 행렬 A를 치환된 하부 삼각 행렬 L과 블록 대각 행렬 D로 행렬 분해하여 A = L*D*L'이 성립되도록 합니다.

[L,D] = ldl(A,triangle)은 triangle이 "upper"인 경우 A의 상부 삼각을 사용하여 행렬 분해합니다. 기본적으로는 triangle의 디폴트 값이 "lower"이므로 A의 하부 삼각을 사용하여 행렬 분해합니다.

[L,D,P] = ldl(___)은 P'*A*P = L*D*L'을 성립시키는 치환 행렬도 반환합니다. 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다.

[L,D,P] = ldl(___,outputForm)은 outputForm으로 지정된 형식으로 치환 정보를 반환합니다. outputForm을 "vector"로 지정하여 치환 정보를 벡터로 반환할 수 있습니다.

희소 형식 데이터

[L,D,P] = ldl(S)는 실수 희소 행렬 S에 대해 P'*S*P = L*D*L'을 성립시키는 하부 삼각 인수, 블록 대각선 인수, 치환 정보를 반환합니다.

[L,D,P,C] = ldl(S)는 P'*C*S*C*P = L*D*L'을 성립시키는 스케일링 행렬을 반환합니다. 이 구문은 희소 행렬 입력값에만 사용할 수 있습니다.

[L,D,P,C] = ldl(S,tol)은 S를 행렬 분해하는 알고리즘의 피벗 허용오차를 지정합니다.

[___] = ldl(___,triangle)은 triangle이 "upper"인 경우 실수 희소 행렬 S의 상부 삼각을 사용하여 행렬 분해합니다. 기본적으로는 triangle의 디폴트 값이 "lower"이므로 S의 하부 삼각을 사용하여 행렬 분해합니다. 희소 행렬에 대해 위에 열거된 구문에 나와 있는 입력 인수와 출력 인수를 원하는 대로 조합하여 사용할 수 있습니다.

[___] = ldl(___,outputForm)은 outputForm으로 지정된 형식으로 치환 정보를 반환합니다. outputForm을 "vector"로 지정하여 치환 정보를 벡터로 반환할 수 있습니다.

예제

LDL 분해

세 개의 출력 인수를 갖는 ldl 함수를 사용하여 3×3 행렬의 비희소 LDL 분해를 계산합니다.

A = [2 -1 0; -1 2 -1; 0 -1 1];
[L1,D1,P1] = ldl(A)

L1 = 3×3

    1.0000         0         0
   -0.5000    1.0000         0
         0   -0.6667    1.0000

D1 = 3×3

    2.0000         0         0
         0    1.5000         0
         0         0    0.3333

P1 = 3×3

     1     0     0
     0     1     0
     0     0     1

두 개의 출력 인수를 지정하여 치환 행렬 P를 L 인자에 통합합니다. 여기서 L2는 P1*L1과 같습니다.

[L2,D2] = ldl(A)

L2 = 3×3

    1.0000         0         0
   -0.5000    1.0000         0
         0   -0.6667    1.0000

D2 = 3×3

    2.0000         0         0
         0    1.5000         0
         0         0    0.3333

P1*L1

ans = 3×3

    1.0000         0         0
   -0.5000    1.0000         0
         0   -0.6667    1.0000

LDL 분해를 사용하여 선형 시스템 풀기

LDL 분해를 수행하고 인수를 사용하여 문제를 단순화하여 선형 시스템을 풉니다. 백슬래시 연산자, ldl 함수, decomposition 객체를 사용하여 얻은 해를 비교해 봅니다.

3×3 행렬과 3×1 벡터를 만들고 백슬래시 연산자를 사용하여 선형 시스템 A*x = b를 풉니다.

A = [2 -3 4; -3 2 -3; 4 -3 1];
b = [1; 0; 0];
x1 = A\b

x1 = 3×1

   -0.4118
   -0.5294
    0.0588

A의 LDL 분해를 계산합니다. 인수를 사용하여 시스템을 풉니다. P'*A*P = L*D*L'이기 때문에 선형 시스템 A*x = b를 inv(P')*L*D*L'*inv(P)*x = b로 다시 작성할 수 있습니다. x에 대해 풀 경우 선형 시스템을 x = P*inv(L')*inv(D)*inv(L)*P'*b 또는 x = P*(L'\(D\(L\(P'*b))))로 다시 작성할 수 있습니다.

선형 시스템의 해를 구하기 전에 행렬 인수를 먼저 계산하면 행렬 분해가 한 번만 발생하고 반복이 필요하지 않기 때문에 여러 다양한 b의 값으로 선형 시스템을 풀어야 할 때 성능이 높아질 수 있습니다.

[L,D,P] = ldl(A)

L = 3×3

    1.0000         0         0
         0    1.0000         0
   -0.6429   -0.4286    1.0000

D = 3×3

    2.0000    4.0000         0
    4.0000    1.0000         0
         0         0   -1.2143

P = 3×3

     1     0     0
     0     0     1
     0     1     0

x2 = P*(L'\(D\(L\(P'*b))))

x2 = 3×1

   -0.4118
   -0.5294
    0.0588

decomposition 객체도 행렬 인수를 먼저 계산하는 접근 방식의 이점을 얻으면서도 인수를 어떻게 사용하는지 알 필요가 없기 때문에 특화된 행렬 분해를 사용하여 선형 시스템을 풀 때 유용합니다. decomposition 객체를 "ldl" 유형과 함께 사용하여 동일한 결과를 다시 만듭니다.

dA = decomposition(A,"ldl");
x3 = dA\b

x3 = 3×1

   -0.4118
   -0.5294
    0.0588

LDL 분해의 치환 벡터

분해할 행렬의 크기가 클수록 치환 벡터를 사용했을 때의 효율이 높아집니다. 치환 벡터를 사용하면 이후의 연산에서의 실행 시간도 단축할 수 있습니다.

1000×1000 대칭 확률 행렬(난수 행렬)을 만들고 행렬의 LDL 분해를 계산합니다. ldl 함수에 세 개의 출력 인수를 지정하여 치환 정보를 반환합니다. 행렬과 벡터로 저장된 치환 정보의 크기를 비교합니다.

A = rand(1000);
A = A + A';
[L,D,P] = ldl(A);
[Lv,Dv,v] = ldl(A,"vector");
whos P v

  Name         Size                Bytes  Class     Attributes

  P         1000x1000            8000000  double              
  v            1x1000               8000  double              

치환 행렬의 인자들은 항등식 P'*A*P = L*D*L'을 성립시킵니다. 치환 벡터의 인자들은 항등식 A(v,v) = Lv*Dv*Lv'를 대신 성립시킵니다.

상부 삼각을 사용한 LDL 분해

하부 삼각을 사용하여 3×3 행렬의 LDL 분해를 계산합니다.

A = [2 -1 0; -3 2 -1; 0 -3 1];
[L,D] = ldl(A)

L = 3×3

    1.0000         0         0
   -1.5000    1.0000         0
         0    1.2000    1.0000

D = 3×3

    2.0000         0         0
         0   -2.5000         0
         0         0    4.6000

triangle을 "upper"로 지정해 상부 삼각을 사용하여 동일한 행렬의 LDL 분해를 계산합니다.

[Lu,Du] = ldl(A,"upper")

Lu = 3×3

    1.0000   -0.5000         0
         0    1.0000   -0.6667
         0         0    1.0000

Du = 3×3

    2.0000         0         0
         0    1.5000         0
         0         0    0.3333

희소 LDL 분해를 위한 스케일링 행렬

확률(난수) 에르미트 행렬의 LDL 분해를 계산합니다. ldl 함수에 대해 네 개의 출력 인수를 지정하여 스케일링 행렬을 반환합니다. 스케일링 행렬 C1의 값은 서로 다른 스케일을 갖는데 반해, 블록 대각 행렬 D1은 더 균형이 잡혀 있습니다.

A = randn(7);
A = A + A';
d = logspace(0,-20,7);
A = A.*d.*d';
[L1,D1,P1,C1] = ldl(sparse(A));
full(C1)

ans = 7×7
1019 ×

    0.0000         0         0         0         0         0         0
         0    0.0000         0         0         0         0         0
         0         0    0.0000         0         0         0         0
         0         0         0    0.0000         0         0         0
         0         0         0         0    0.0000         0         0
         0         0         0         0         0    0.0046         0
         0         0         0         0         0         0    6.7627

full(D1)

ans = 7×7

    1.0000         0         0         0         0         0         0
         0   -0.2722         0         0         0         0         0
         0         0    1.2133         0         0         0         0
         0         0         0   -3.6488         0         0         0
         0         0         0         0    0.2950         0         0
         0         0         0         0         0   -0.7251         0
         0         0         0         0         0         0   13.1577

세 개의 출력 인수와 함께 ldl을 사용하여 LDL 분해를 계산합니다. 스케일링 행렬 출력을 지정하지 않을 경우 행렬 L2와 D2의 스케일이 다를 수 있습니다.

[L2,D2,P2] = ldl(sparse(A));
full(D2)

ans = 7×7

    0.0000    0.0010         0         0         0         0         0
    0.0010    1.0753         0         0         0         0         0
         0         0    0.0000    0.0000         0         0         0
         0         0    0.0000   -0.0000         0         0         0
         0         0         0         0         0         0         0
         0         0         0         0         0         0         0
         0         0         0         0         0         0         0

입력 인수

A — 입력 행렬

실수 또는 복소수 정사각 행렬

입력 행렬로, 실수 또는 복소수 정사각 행렬로 지정됩니다. ldl은 A를 대칭 행렬(복소수인 경우 에르미트 행렬)로 간주하고 기본적으로 A의 하부 삼각만 사용합니다. ishermitian(A)를 사용하여 A가 에르미트 행렬인지 확인할 수 있습니다.

데이터형: single | double
복소수 지원 여부: 예

S — 희소 입력 행렬

실수 희소 행렬

희소 입력 행렬로, 실수 희소 행렬로 지정됩니다. ldl은 S를 대칭 행렬로 간주합니다.

데이터형: double

triangle — 입력 행렬의 삼각 인수

"lower" (디폴트 값) | "upper"

입력 행렬의 삼각 인수로, "lower" 또는 "upper"로 지정됩니다. 이 옵션을 사용하여 ldl이 행렬 분해를 계산할 때 입력 행렬의 하부 삼각을 사용할지 아니면 상부 삼각을 사용할지 지정합니다. ldl은 입력 행렬이 대칭(복소수인 경우 에르미트)이라고 간주하고 하부 삼각 또는 상부 삼각만 사용하여 계산을 수행합니다.

세 개의 출력 인수를 지정한 경우 triangle이 "lower"이면 행렬 분해는 P'*A*P = L*D*L'을 성립시키고 L은 하부 삼각입니다. triangle이 "upper"이면 행렬 분해는 P'*A*P = L'*D*L을 성립시키고 L은 상부 삼각입니다.

outputForm — 치환 출력값의 형태

"matrix" (디폴트 값) | "vector"

치환 출력값의 형태로, "matrix" 또는 "vector"로 지정됩니다. outputForm이 "matrix"이고 하부 삼각을 사용하는 경우 치환 행렬은 P'*A*P = L*D*L'을 성립시킵니다. outputForm이 "vector"이고 하부 삼각을 사용하는 경우 치환 벡터는 A(P,P) = L*D*L'을 성립시킵니다.

tol — 실수 희소 행렬에 대한 피벗 허용오차

0.01 (디폴트 값) | 범위 [0,0.5] 내의 스칼라

실수 희소 행렬에 대한 피벗 허용오차로, 범위 [0,0.5] 내의 스칼라로 지정됩니다. 기본적으로 tol은 0.01입니다. 더 작은 값을 사용하면 행렬 분해의 시간이 빨라지고 인수가 더 희소해질 수 있지만, 행렬 분해의 안정성이 저하될 수 있습니다.

데이터형: double

출력 인수

L — 하부 삼각 인수

정사각 행렬

하부 삼각 인수로, 정사각 행렬로 반환됩니다. 기본적으로 L은 하부 단위 삼각 행렬, 즉 대각선상의 요소가 1인 하부 삼각 행렬입니다. triangle이 "upper"인 경우 L은 상부 단위 삼각 행렬입니다.

D — 블록 대각선 인수

정사각 행렬

블록 대각선 인수로, 정사각 행렬로 반환됩니다. D는 대각선에 1×1 블록과 2×2 블록을 포함합니다.

P — 치환 정보

행렬 | 벡터

치환 정보로, 행렬로 반환되거나 outputForm이 "vector"인 경우 벡터로 반환됩니다.

C — 스케일링 인자

정사각 행렬

스케일링 인자로, 정사각 행렬로 반환됩니다. C는 실수 희소 행렬 S에 대해 P'*C*S*C*P = L*D*L'을 성립시키는 양의 희소 대각 행렬입니다.

세부 정보

에르미트(Hermitian) 행렬

• 정사각 행렬 A는 켤레 복소수 전치와 같을 경우(A = A') 에르미트입니다.

  이를 행렬 요소로 표현하자면 다음과 같습니다.

  $$a_{i,j}={\overline{a}}_{j,i}.$$

• 에르미트(Hermitian) 행렬의 대각선에 있는 요소는 항상 실수입니다. 실수 행렬은 복소 켤레화의 영향을 받지 않으므로 대칭인 실수 행렬은 에르미트 행렬이기도 합니다. 예를 들어 이 행렬은 대칭이자 에르미트 행렬입니다.

  $$A=\left[\begin{array}{cc}\begin{array}{c}1\\ 0\end{array}& \begin{array}{cc}\begin{array}{c}0\\ 2\end{array}& \begin{array}{c}1\\ 0\end{array}\end{array}\\ 1& \begin{array}{cc}0& 1\end{array}\end{array}\right]$$

• 에르미트(Hermitian) 행렬의 고유값은 실수입니다.

참고 문헌

[1] Ashcraft, Cleve, Roger G. Grimes, and John G. Lewis. “Accurate Symmetric Indefinite Linear Equation Solvers.” SIAM Journal on Matrix Analysis and Applications 20, no. 2 (January 1998): 513–61. https://doi.org/10.1137/S0895479896296921.

[2] Anderson, E., Z. Bai, C. Bischof, L. S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenny, and D. Sorensen. LAPACK Users’ Guide. Philadelphia: Society for Industrial and Applied Mathematics, 1999. https://doi.org/10.1137/1.9780898719604.

[3] Duff, Iain S. “MA57---a Code for the Solution of Sparse Symmetric Definite and Indefinite Systems.” ACM Transactions on Mathematical Software 30, no. 2 (June 2004): 118–44. https://doi.org/10.1145/992200.992202.

확장 기능

C/C++ 코드 생성

MATLAB® Coder™를 사용하여 C 코드나 C++ 코드를 생성할 수 있습니다.

사용법 관련 참고 및 제한 사항:

• 입력 행렬에 nonfinite 값이 포함되어 있는 경우 생성된 코드 출력값에는 NaN 값만 포함됩니다.

• 코드 생성 시 이 함수에 대해 희소 행렬 입력값은 지원되지 않습니다.

스레드 기반 환경

MATLAB®의 backgroundPool을 사용해 백그라운드에서 코드를 실행하거나 Parallel Computing Toolbox™의 ThreadPool을 사용해 코드 실행 속도를 높일 수 있습니다.

이 함수는 스레드 기반 환경을 완전히 지원합니다. 자세한 내용은 스레드 기반 환경에서 MATLAB 함수 실행하기 항목을 참조하십시오.

버전 내역

R2006a 이전에 개발됨

참고 항목

chol | lu | qr | decomposition