Main Content

이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

chol

촐레스키 분해(Cholesky Factorization)

설명

예제

R = chol(A)는 양의 정부호 대칭 행렬 AA = R'*R을 충족하는 상부 삼각 R로 분해합니다. A가 비대칭 행렬인 경우 chol은 이 행렬을 대칭 행렬로 취급하고 A의 대각선과 상부 삼각만 사용합니다.

예제

R = chol(A,triangle)은 행렬 분해 계산 시 사용할 A의 삼각 인수를 지정합니다. 예를 들어, triangle'lower'이면 cholA의 대각선과 하부 삼각 부분만 사용하여 A = R*R'을 충족하는 하부 삼각 행렬 R을 생성합니다. triangle의 디폴트 값은 'upper'입니다.

예제

[R,flag] = chol(___)A양의 정부호 대칭 행렬인지 여부를 나타내는 출력값 flag도 반환합니다. 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다. flag 출력값을 지정할 경우 chol은 입력 행렬이 양의 정부호 대칭 행렬이 아니더라도 오류를 생성하지 않습니다.

  • flag = 0이면 입력 행렬은 양의 정부호 대칭 행렬이고 행렬이 성공적으로 분해된 것입니다.

  • flag가 0이 아니면 입력 행렬은 양의 정부호 대칭 행렬이 아니고 flag는 행렬 분해가 실패한 피벗 위치의 인덱스를 나타내는 정수입니다.

예제

[R,flag,P] = chol(S)는 치환 행렬 P를 추가로 반환합니다. 이 행렬은 amd로 얻은 희소 행렬 S의 전위입니다. flag = 0이면 S는 양의 정부호 대칭 행렬이고 RR'*R = P'*S*P를 충족하는 상부 삼각 행렬입니다.

예제

[R,flag,P] = chol(___,outputForm)은 위에 열거된 구문에 나와 있는 입력 인수 조합 중 하나를 사용하여 치환 정보 P를 행렬과 벡터 중 어느 것으로 반환할 것인지 지정합니다. 이 옵션은 희소 행렬 입력값에서만 사용할 수 있습니다. 예를 들어, outputForm'vector'이고 flag = 0인 경우 S(p,p) = R'*R입니다. outputForm의 디폴트 값은 R'*R = P'*S*P가 되는 'matrix'입니다.

예제

모두 축소

chol을 사용하여 대칭 계수 행렬을 분해하고, 촐레스키 인수를 사용하여 선형 시스템을 풉니다.

대각선에 양의 값이 있는 대칭 행렬을 만듭니다.

A = [1 0 1; 0 2 0; 1 0 3]
A = 3×3

     1     0     1
     0     2     0
     1     0     3

행렬의 촐레스키 인수를 계산합니다.

R = chol(A)
R = 3×3

    1.0000         0    1.0000
         0    1.4142         0
         0         0    1.4142

방정식 Ax=b의 우변에 해당하는 벡터를 만듭니다.

b = sum(A,2);

촐레스키 분해를 사용했을 때 A=RTR이므로, 선형 방정식은 RTR x=b가 됩니다. 백슬래시 연산자를 사용하여 x를 구합니다.

x = R\(R'\b)
x = 3×1

    1.0000
    1.0000
    1.0000

행렬의 상부 및 하부 촐레스키 분해를 계산하고 결과를 확인합니다.

gallery 함수를 사용하여 6×6 양의 정부호 대칭 테스트 행렬을 만듭니다.

A = gallery('lehmer',6);

A의 상부 삼각을 사용하여 촐레스키 인수를 계산합니다.

R = chol(A)
R = 6×6

    1.0000    0.5000    0.3333    0.2500    0.2000    0.1667
         0    0.8660    0.5774    0.4330    0.3464    0.2887
         0         0    0.7454    0.5590    0.4472    0.3727
         0         0         0    0.6614    0.5292    0.4410
         0         0         0         0    0.6000    0.5000
         0         0         0         0         0    0.5528

상부 삼각 인수가 반올림 오차 내에서 R'*R - A = 0을 충족하는지 확인합니다.

norm(R'*R - A)
ans = 2.8779e-16

이번에는 'lower' 옵션을 지정하여 A의 하부 삼각을 사용하여 촐레스키 인수를 계산합니다.

L = chol(A,'lower')
L = 6×6

    1.0000         0         0         0         0         0
    0.5000    0.8660         0         0         0         0
    0.3333    0.5774    0.7454         0         0         0
    0.2500    0.4330    0.5590    0.6614         0         0
    0.2000    0.3464    0.4472    0.5292    0.6000         0
    0.1667    0.2887    0.3727    0.4410    0.5000    0.5528

하부 삼각 인수가 반올림 오차 내에서 L*L' - A = 0을 충족하는지 확인합니다.

norm(L*L' - A)
ans = 3.2914e-16

입력 행렬이 양의 정부호 대칭 행렬이 아닌 경우 오류를 표시하지 않으려면 chol을 두 개의 출력값과 함께 사용합니다.

이항 계수로 구성된 5×5 행렬을 만듭니다. 이 행렬은 양의 정부호 대칭 행렬이므로, 더 이상 양의 정부호가 되지 않도록 마지막 요소에서 1을 뺍니다.

A = pascal(5);
A(end) = A(end) - 1
A = 5×5

     1     1     1     1     1
     1     2     3     4     5
     1     3     6    10    15
     1     4    10    20    35
     1     5    15    35    69

A에 대해 촐레스키 인수를 계산합니다. A가 양의 정부호 대칭 행렬이 아닌 경우 오류가 생성되지 않도록 두 개의 출력값을 지정합니다.

[R,flag] = chol(A)
R = 4×4

     1     1     1     1
     0     1     2     3
     0     0     1     3
     0     0     0     1

flag = 5

flag가 0이 아니므로 행렬 분해가 실패한 위치의 피벗 인덱스를 제공합니다. chol은 행렬에서 변경된 부분에 도달하여 실패가 발생하기 직전까지인 q = flag-1 = 4개의 행과 열을 올바르게 계산할 수 있습니다.

R'*RA(1:q,1:q)와 일치하는 4개의 행과 열을 반환하는 것을 확인합니다.

q = flag-1;
R'*R
ans = 4×4

     1     1     1     1
     1     2     3     4
     1     3     6    10
     1     4    10    20

A(1:q,1:q)
ans = 4×4

     1     1     1     1
     1     2     3     4
     1     3     6    10
     1     4    10    20

희소 행렬의 촐레스키 인수를 계산하고, 치환 출력값을 사용하여 0이 아닌 요소가 더 적은 촐레스키 인수를 만듭니다.

west0479 행렬을 기반으로 양의 정부호 희소 행렬을 만듭니다.

load west0479
A = west0479;
S = A'*A;

두 가지 방법을 사용하여 이 행렬의 촐레스키 인수를 계산합니다. 한 번은 두 개의 출력값을 지정하고, 다른 한 번은 행과 열이 재정렬되도록 세 개의 출력값을 지정합니다.

[R,flag] = chol(S);
[RP,flagP,P] = chol(S);

각 계산에 대해 flag = 0인지 확인하여 계산이 성공했음을 확인합니다.

if ~flag && ~flagP
    disp('Factorizations successful.')
else
    disp('Factorizations failed.')
end
Factorizations successful.

chol(S)에 들어 있는 0이 아닌 요소의 개수와 재정렬된 행렬 chol(P'*S*P)에 들어 있는 0이 아닌 요소의 개수를 비교합니다. 행과 열을 재정렬하면 촐레스키 인수의 0이 아닌 요소의 개수가 대폭 줄어들므로 chol의 세 개 출력값 구문은 희소 행렬과 함께 사용하는 것이 가장 좋습니다.

subplot(1,2,1)
spy(R)
title('Nonzeros in chol(S)')
subplot(1,2,2)
spy(RP)
title('Nonzeros in chol(P''*S*P)')

Figure contains 2 axes objects. axes object 1 with title Nonzeros in chol(S), xlabel nz = 59887 contains a line object which displays its values using only markers. axes object 2 with title Nonzeros in chol(P'*S*P), xlabel nz = 7637 contains a line object which displays its values using only markers.

chol'vector' 옵션을 사용하여 치환 정보를 행렬이 아닌 벡터로 반환합니다.

희소 유한 요소 행렬을 만듭니다.

S = gallery('wathen',10,10);
spy(S)

Figure contains an axes object. The axes object with xlabel nz = 4861 contains a line object which displays its values using only markers.

이 행렬에 대해 촐레스키 인수를 계산합니다. 이때 치환 벡터 p를 반환하도록 'vector' 옵션을 지정합니다.

[R,flag,p] = chol(S,'vector');

flag = 0인지 확인하여 계산이 성공했음을 확인합니다.

if ~flag
    disp('Factorization successful.')
else
    disp('Factorization failed.')
end
Factorization successful.

반올림 오차 내에서 S(p,p) = R'*R인지 확인합니다.

norm(S(p,p) - R'*R,'fro')
ans = 2.1039e-13

입력 인수

모두 축소

입력 행렬입니다. 인수 A는 비희소 형식이나 희소 형식을 사용할 수 있지만 반드시 양의 정부호 정사각 대칭 행렬이어야 합니다.

chol은 실수 행렬의 경우 A를 대칭 행렬로 간주하고 복소수 행렬의 경우 에르미트 행렬로 간주합니다. choltriangle의 값에 따라 A의 상부 삼각 또는 하부 삼각만 사용하여 계산을 수행합니다.

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

희소 입력 행렬입니다. S는 양의 정부호 정사각 대칭 행렬이어야 합니다.

chol은 실수 행렬의 경우 S를 대칭 행렬로 간주하고 복소수 행렬의 경우 에르미트 행렬로 간주합니다. choltriangle의 값에 따라 S의 상부 삼각 또는 하부 삼각만 사용하여 계산을 수행합니다.

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

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

'lower' 옵션을 사용하는 것은 'upper' 옵션과 입력 행렬의 전치를 사용하여 chol을 호출한 다음 출력값 R을 전치하는 것과 동일합니다.

예: R = chol(A,'lower')

치환 출력값의 형태로, 'matrix' 또는 'vector'로 지정됩니다. 이 플래그는 치환 출력값 P가 치환 행렬과 치환 벡터 중 어느 것으로 반환되는지 제어합니다.

  • flag = 0이면 S는 양의 정부호 대칭 행렬이고 P'*S*P = R'*R(P가 행렬인 경우) 또는 S(p,p) = R'*R(p가 벡터인 경우)입니다.

  • flag가 0이 아니면 S는 양의 정부호 대칭 행렬이 아닙니다. R은 크기가 q×n인 상부 삼각 행렬이며, 이때 q = flag-1입니다. R'*R의 처음 q개 행과 처음 q개 열로 이루어진 L 모양 영역은 P'*S*P(P가 행렬인 경우) 또는 S(p,p)(p가 벡터인 경우)의 영역과 일치합니다.

  • 'lower' 옵션을 지정하면 R은 하부 삼각 행렬이고, 위에 나온 항등식에서 R'*RR*R'로 바꿀 수 있습니다.

P'*S*P(P가 행렬인 경우) 또는 S(p,p)(p가 벡터인 경우)의 촐레스키 인수는 S의 촐레스키 인수보다 희소성이 큰 경향이 있습니다.

예: [R,flag,p] = chol(S,'vector')

출력 인수

모두 축소

촐레스키 인수로, 행렬로 반환됩니다.

  • R이 상부 삼각 행렬이면 A = R'*R입니다. 희소 행렬에 대해 P 출력값을 지정하면 outputForm의 값에 따라 P'*S*P = R'*R 또는 S(p,p) = R'*R이 됩니다.

  • R이 하부 삼각 행렬이면 A = R*R'입니다. 희소 행렬에 대해 P 출력값을 지정하면 outputForm의 값에 따라 P'*S*P = R*R' 또는 S(p,p) = R*R'이 됩니다.

  • flag가 0이 아니면 R은 항상 부분 결과만 포함합니다. flag는 행렬 분해가 실패한 피벗 위치를 나타내고, R은 부분 완료된 행렬 분해를 포함합니다.

양의 정부호 대칭 플래그로, 스칼라로 반환됩니다.

  • flag = 0이면 입력 행렬은 양의 정부호 대칭 행렬입니다. RR'*R = A를 충족하는 상부 삼각 행렬입니다.

  • A가 양의 정부호 대칭 행렬이 아니면 flag는 행렬 분해가 실패한 피벗 위치를 나타내는 양의 정수이고 MATLAB®은 오류를 생성하지 않습니다. RR'*R = A(1:q,1:q)를 충족하면서 크기가 q = flag-1인 상부 삼각 행렬입니다.

  • A가 희소 행렬이면 RR'*R의 처음 q개 행과 처음 q개 열로 이루어진 L 모양 영역이 A 또는 S의 영역과 일치하면서 크기가 q×n인 상부 삼각 행렬입니다.

  • 'lower' 옵션을 지정하면 R은 하부 삼각 행렬이고, 위에 나온 항등식에서 R'*RR*R'로 바꿀 수 있습니다.

희소 행렬에 대한 치환으로, outputForm의 값에 따라 행렬 또는 벡터로 반환됩니다. 이 출력값이 충족하는 항등식에 대한 설명은 outputForm을 참조하십시오.

이 치환 행렬은 amd에 의해 계산되는 AMD(Approximate Minimum Degree) 정렬을 기반으로 합니다. 그러나 chol은 성능 향상을 위해 순서를 약간 바꾸므로 이 전위는 amd로 직접 얻은 것과 다를 수 있습니다.

세부 정보

모두 축소

양의 정부호 대칭 행렬

양의 정부호 대칭 행렬은 모든 값이 양의 고유값인 대칭 행렬입니다.

임의의 실수 가역 행렬 A에 대해 곱 B = A'*A를 사용하여 양의 정부호 대칭 행렬을 생성할 수 있습니다. 촐레스키 분해는 임의의 양의 정부호 대칭 행렬 B가 곱 R'*R로 분해될 수 있다고 함으로써 이 수식을 반전시킵니다.

양의 준정부호 대칭 행렬도 비슷한 방식으로 정의되나, 여기서는 고유값이 모두 양수이거나 모두 0이어야 합니다.

수치 계산에서는 양의 정부호 행렬과 양의 준정부호 행렬 사이의 구분이 뚜렷하지 않습니다. 고유값이 정확히 0이 되는 경우는 드물지만, (기계 정밀도 측면에서 보면) 수치적으로 0이 될 수 있습니다. 이러한 이유로 chol은 어느 한 양의 준정부호 행렬을 분해하는 데 성공하더라도 이와 매우 비슷한 고유값을 갖는 또다른 행렬을 분해하는 데는 실패할 수 있습니다.

참고 문헌

[1] Anderson, E., ed. LAPACK Users’ Guide. 3rd ed. Software, Environments, Tools. Philadelphia: Society for Industrial and Applied Mathematics, 1999. https://doi.org/10.1137/1.9780898719604.

[2] Chen, Yanqing, Timothy A. Davis, William W. Hager, and Sivasankaran Rajamanickam. “Algorithm 887: CHOLMOD, Supernodal Sparse Cholesky Factorization and Update/Downdate.” ACM Transactions on Mathematical Software 35, no. 3 (October 2008): 1–14. https://doi.org/10.1145/1391989.1391995.

확장 기능

버전 내역

R2006a 이전에 개발됨

참고 항목

| | |

도움말 항목