행렬 분해
행렬 분해 (Matrix Factorizations)
행렬을 몇 개의 성질 좋은 행렬의 곱으로 쪼개는 것을 행렬 분해라고 해요. 선형 방정식을 풀거나 최소자승 문제를 다룰 때, 또 고유값을 구할 때 분해는 핵심 도구로 쓰여요. 이 문서에서는 Octave가 제공하는 대표적인 행렬 분해 함수들, 곧 콜레스키(chol)·LU·QR·QZ·슈어(schur)·SVD 분해를 정리해요.
출처: 문서
본문
콜레스키 분해 — chol
R = chol (A)
[R, p] = chol (A)
[R, p, Q] = chol (A)
[R, p, Q] = chol (A, "vector")
[L, …] = chol (…, "lower")
[R, …] = chol (…, "upper")
실대칭 또는 복소에르미트 양정부호(positive definite) 행렬 A의 위 콜레스키 인자 R을 계산해요. 위 콜레스키 인자 R은 행렬 A의 위 삼각 부분을 사용해 계산하며, R' * R = A로 정의돼요. 선택적인 "upper" 플래그로 호출해도 동일하게 동작해요. 반대로 "lower" 플래그로 호출하면 L * L' = A가 되도록 아래 삼각 분해를 돌려줘요. 이때는 행렬 A의 아래 삼각 부분을 사용해요.
출력 인자가 하나일 때 chol은 행렬 A가 양정부호가 아니면 실패해요. A가 실대칭이나 복소에르미트가 아니면, "lower" 플래그 여부에 따라 아래 삼각 부분이 위 삼각 부분의 (복소 켤레) 전치로 간주되거나 그 반대로 간주된다는 점에 주의하세요.
출력 인자가 두 개 이상일 때 p는 행렬 A가 양정부호였는지를 알려주고 chol은 실패하지 않아요. p가 0이면 A가 양정부호이고 R이 분해를 준다는 뜻이에요. 그렇지 않으면 p는 양수 값을 가져요.
출력 인자가 세 개로 호출하면 행렬 A는 희소(sparse)여야 하며, 분해 전에 희소성을 보존하는 행/열 순열이 A에 적용돼요. 즉 R은 R' * R = Q' * A * Q가 되도록 하는 A(Q,Q)의 분해예요. 희소성 보존 순열은 일반적으로 행렬로 돌려줘요. 하지만 선택적인 "vector" 플래그를 주면 Q를 R' * R = A(Q, Q)가 되도록 벡터로 돌려줘요.
일반적으로 희소 행렬에서는 아래 삼각 분해가 훨씬 빠르게 동작해요. 함께 보면 좋은 함수: hess, lu, qr, qz, schur, svd, ichol, cholinv, chol2inv, cholupdate, cholinsert, choldelete, cholshift.
cholinv — 콜레스키 분해로 역행렬
Ainv = cholinv (A)
콜레스키 분해를 사용해 대칭 양정부호 행렬 A의 역행렬을 계산해요. 함께 보면 좋은 함수: chol, chol2inv, inv.
chol2inv — 분해로부터 역행렬
Ainv = chol2inv (R)
콜레스키 분해 R로부터 대칭 양정부호 정방행렬을 역행렬로 바꿔요. R은 양의 대각 원소를 가진 위 삼각 행렬이어야 해요. chol2inv (U)는 inv (R'*R)을 제공하지만 inv를 쓰는 것보다 훨씬 빨라요. 함께 보면 좋은 함수: chol, cholinv, inv.
cholupdate — 콜레스키 분해 갱신
[R1, info] = cholupdate (R, u, op)
콜레스키 분해를 갱신(update)하거나 다운데이트(downdate)해요. 위 삼각 행렬 R과 열 벡터 u가 주어지면, op가 "+"일 때 R1'*R1 = R'*R + u*u', op가 "-"일 때 R1'*R1 = R'*R - u*u'를 만족하는 또 다른 위 삼각 행렬 R1을 구하려 시도해요. op가 "-"일 때 info는 다음과 같이 설정돼요.
- 0 — 다운데이트 성공
- 1 —
R'*R - u*u'가 양정부호가 아님 - 2 — R이 특이(singular)
info가 없으면 경우 1, 2에서 오류 메시지를 출력해요. 함께 보면 좋은 함수: chol, cholinsert, choldelete, cholshift.
cholinsert — 행/열 삽입 갱신
R1 = cholinsert (R, j, u)
[R1, info] = cholinsert (R, j, u)
원래 분해된 행렬에 삽입할 행이나 열이 주어졌을 때 콜레스키 분해를 갱신해요. 실대칭 또는 복소에르미트 양정부호 행렬 A = R'*R, R 위 삼각의 콜레스키 분해가 주어지면, A1(p,p) = A, A1(:,j) = A1(j,:)' = u, p = [1:j-1,j+1:n+1]인 A1의 콜레스키 분해를 돌려줘요. u(j)는 양수여야 해요. 반환 시 info는 다음과 같이 설정돼요.
- 0 — 삽입 성공
- 1 — A1이 양정부호가 아님
- 2 — R이 특이
info가 없으면 경우 1, 2에서 오류 메시지를 출력해요. 함께 보면 좋은 함수: chol, cholupdate, choldelete, cholshift.
choldelete — 행/열 삭제 갱신
R1 = choldelete (R, j)
원래 분해된 행렬에서 삭제할 행이나 열이 주어졌을 때 콜레스키 분해를 갱신해요. 실대칭 또는 복소에르미트 양정부호 행렬 A = R'*R, R 위 삼각의 콜레스키 분해가 주어지면, p = [1:j-1,j+1:n+1]인 A(p,p)의 콜레스키 분해를 돌려줘요. 함께 보면 좋은 함수: chol, cholupdate, cholinsert, cholshift.
cholshift — 열 구간 이동 갱신
R1 = cholshift (R, i, j)
원래 분해된 행렬에서 이동시킬 열 구간이 주어졌을 때 콜레스키 분해를 갱신해요. 실대칭 또는 복소에르미트 양정부호 행렬 A = R'*R, R 위 삼각의 콜레스키 분해가 주어지면, p가 순열인 A(p,p)의 콜레스키 분해를 돌려줘요.
p = [1:i-1, circshift(i:j, 1), j+1:n]if i < j- 또는
p = [1:j-1, circshift(j:i,-1), i+1:n]if j < i
함께 보면 좋은 함수: chol, cholupdate, cholinsert, choldelete.
헤센베르크 분해 — hess
H = hess (A)
[P, H] = hess (A)
행렬 A의 헤센베르크(Hessenberg) 분해를 계산해요. 헤센베르크 분해는 P * H * P' = A인데, P는 정방 유니타리 행렬(P' * P = I, 복소 켤레 전치 사용)이고 H는 상부 헤센베르크(H(i, j) = 0 forall i > j+1)예요. 헤센베르크 분해는 보통 고유값 계산의 첫 단계로 쓰이지만 다른 응용도 있어요(참고: Golub, Nash, Van Loan, IEEE Transactions on Automatic Control, 1979). 함께 보면 좋은 함수: eig, chol, lu, qr, qz, schur, svd.
LU 분해 — lu
[L, U] = lu (A)
[L, U, P] = lu (A)
[L, U, P, Q] = lu (S)
[L, U, P, Q, R] = lu (S)
[…] = lu (S, thresh)
y = lu (…)
[…] = lu (…, "vector")
A의 LU 분해를 계산해요. A가 밀집(full)이면 LAPACK의 서브루틴을, A가 희소면 UMFPACK을 사용해요. 결과는 선택적인 반환값 P에 따라 순열된 형태로 돌려줘요.
예를 들어 A = [1, 2; 3, 4]일 때 [L, U, P] = lu (A)는 다음을 돌려줘요.
L =
1.00000 0.00000
0.33333 1.00000
U =
3.00000 4.00000
0.00000 0.66667
P =
0 1
1 0
행렬은 정방일 필요가 없어요.
두세 개의 출력 인자와 희소 입력 행렬로 호출하면 lu는 희소성 보존 열 순열을 시도하지 않아요. 네 번째 출력 인자로 호출하면 희소성 보존 열 변환 Q를 돌려주며 P * A * Q = L * U예요. 희소 입력 행렬과 함께 lu를 호출하는 선호 방식이에요. 다섯 번째 출력 인자와 희소 입력 행렬로 호출하면 P * (R \ A) * Q = L * U가 되도록 입력 행렬에 스케일 인자 R을 사용하려 해요. 이는 보통 더 희소하고 안정적인 분해를 이끌어요.
피벗 임계값을 정의하는 추가 입력 인자 thresh를 줄 수 있어요. thresh가 스칼라이면 대칭·비대칭 양 경우 모두에 UMFPACK 피벗 허용 오차를 정의해요. thresh가 2-원소 벡터면 첫 원소는 비대칭 UMFPACK 피벗 전략의 허용 오차를, 둘째 원소는 대칭 전략의 허용 오차를 정의해요. 기본적으로 spparms가 정의한 값([0.1, 0.001])을 사용해요.
문자열 인자 "vector"를 주면 lu는 P와 Q의 값을 벡터로 돌려줘요. 밀집 행렬의 경우 A(P,:) = L * U, R(P,:) * A(:,Q) = L * U예요. 출력 인자가 두 개면 위·아래 삼각 행렬의 순열된 형태를 돌려줘서 A = L * U예요. 출력 인자가 하나 y면 LAPACK 루틴이 돌려주는 행렬을 돌려줘요. 입력 행렬이 희소면 L을 U에 끼워 넣어 밀집 경우와 비슷한 반환값을 만들어요. 밀집·희소 모두에서 lu는 순열 정보를 잃어요.
함께 보면 좋은 함수: luupdate, ilu, chol, hess, qr, qz, schur, svd.
luupdate — LU 분해 갱신
[L, U] = luupdate (L, U, x, y)
[L, U, P] = luupdate (L, U, P, x, y)
실수 또는 복소수 행렬 A = LU(L 아래 단위 사다리꼴, U 위 사다리꼴)의 LU 분해가 주어지면, A + xy.'의 LU 분해를 돌려줘요. 여기서 x와 y는 열 벡터(rank-1 갱신)이거나 열 수가 같은 행렬(rank-k 갱신)이에요.
선택적으로 행 순열(피벗) 행렬 P를 제공하면 행 피벗 갱신을 쓸 수 있고, 이 경우 갱신된 순열 행렬을 돌려줘요. lu로 얻은 것처럼 L, U, P가 피벗 LU 분해라면:
[L, U, P] = lu (A);
A+x*y.'의 분해는 다음 두 가지 중 하나로 얻을 수 있어요.
[L1, U1] = lu (L, U, P*x, y)
또는
[L1, U1, P1] = lu (L, U, P, x, y)
첫 번째 형태는 피벗 없는 알고리즘을 쓰는데 더 빠르지만 덜 안정적이에요. 두 번째 형태는 더 느리지만 더 안정적인 피벗 알고리즘을 써요. 행렬 경우는 rank-1 갱신의 연속으로 처리돼요. 그래서 k가 충분히 크면, 처음부터 분해를 다시 계산하는 편이 더 빠르고 정확해요. 함께 보면 좋은 함수: lu, cholupdate, qrupdate.
QR 분해 — qr
[Q, R] = qr (A)
[Q, R, P] = qr (A)
R = qr (A)
[C, R] = qr (A, B)
[C, R, P] = qr (A, B)
X = qr (A, B) # sparse only
[…] = qr (…, "econ")
[…] = qr (…, "vector")
[…] = qr (…, "matrix")
[…] = qr (…, 0)
A의 QR 분해를 계산해요. QR 분해는 Q * R = A인데, Q는 직교 행렬이고 R은 위 삼각 행렬이에요. 예를 들어 A = [1, 2; 3, 4]일 때 [Q, R] = qr (A)는 다음을 돌려줘요.
Q =
-0.31623 -0.94868
-0.94868 0.31623
R =
-3.16228 -4.42719
0.00000 -0.63246
둘을 곱하면 원래 행렬이 돌아와요.
Q * R
⇒
1.0000 2.0000
3.0000 4.0000
반환 값을 하나만 요청하면 그것은 R이에요. (참고: 대부분의 명령과 달리, 단일 반환 값은 여러 값을 요청했을 때의 첫 반환 값이 아니에요.)
세 번째 출력 P를 요청하면 qr은 순열 QR 분해 Q * R = A * P를 계산해요. Q는 직교 행렬, R은 위 삼각, P는 순열 행렬이에요.
A가 밀집이면 표준 LAPACK 서브루틴으로 QR 분해를 계산해요. 이 경우 순열 분해는 R의 대각 원소가 크기 순으로 정렬되는 추가 속성을 가져요. 즉 abs (diag (R))이 큰 값부터 작은 값까지 정렬돼요. A가 희소면 P는 A 열의 채움 감소(fill-reducing) 순서예요. 이 경우 R의 대각 원소는 크기 순으로 정렬되지 않아요.
예를 들어 A = [1, 2; 3, 4]에서 [Q, R, P] = qr (A)는 다음을 돌려줘요.
Q =
-0.44721 -0.89443
-0.89443 0.44721
R =
-4.47214 -3.13050
0.00000 0.44721
P =
0 1
1 0
입력 행렬 A가 희소면 희소 QR 분해는 SPQR 또는 CXSPARSE(예: SPQR을 쓸 수 없을 때)로 계산해요. Q 행렬은 일반적으로 밀집 행렬이므로, 반환 값 하나 R만 요청하는 걸 권장해요. 그 경우 Q의 구성 없이 R = chol (A' * A)가 되도록 희소 R을 돌려주는 계산을 해요.
A가 밀집이고 추가 입력 행렬 B가 주어지고 반환 값 두 개를 요청하면 qr은 C = Q' * B인 C를 돌려줘요. 이렇게 하면 A \ B의 최소자승 근사를 다음처럼 계산할 수 있어요.
[C, R] = qr (A, B)
X = R \ C
A가 희소 MxN 행렬이고 추가 행렬 B가 주어지면 반환 값은 하나나 둘이 될 수 있어요. 반환 값 하나 X를 요청하고 M < N이면 X는 A \ B의 최소 2-놈(minimum 2-norm) 해예요. M >= N이면 X는 A \ B의 최소자승 근사예요. 반환 값 둘을 요청하면 C와 R은 밀집 경우와 같은 의미를 가져요(C는 밀집, R은 희소). 반환 값 하나 버전이 메모리를 덜 쓰고 랭크 결핍 행렬을 더 잘 처리하므로 선호돼요.
마지막 인자가 문자열 "vector"면 P는 (A의 열의) 순열 벡터이지 순열 행렬이 아니에요. 이 경우 정의 관계는 Q * R = A(:, P)예요. 하지만 기본값은 순열 행렬을 돌려주는 것이고, 마지막 인자 "matrix"로 명시적으로 지정할 수 있어요.
선택 인자가 문자열 "econ"이면 경제(economy) 분해를 돌려줘요. 원래 행렬 A가 MxN이고 M > N이면, 경제 분해는 R에서 N개 행과 Q에서 N개 열만 계산하고 R에서 0을 생략해요. M ≤ N이면 경제 분해와 표준 분해 사이에 차이가 없어요.
선택 인자가 숫자 0이면 qr은 "econ"과 "vector" 인자가 모두 주어진 것처럼 행동해요. 경고: 이 문법은 받아들여지지만 더 이상 권장되지 않고 향후 제거될 수 있어요. "econ"을 쓰세요.
배경 설명: QR 분해는 과결정(overdetermined) 연립방정식(즉 A가 키가 크고 가는 행렬)에서 최소자승 문제 min norm (A*x - b)를 푸는 데 응용돼요. 순열 QR 분해 [Q, R, P] = qr (A)는 span (A)의 직교 기저 구성을 가능하게 해요. 함께 보면 좋은 함수: chol, hess, lu, qz, schur, svd, qrupdate, qrinsert, qrdelete, qrshift.
qrupdate — QR 분해 갱신
[Q1, R1] = qrupdate (Q, R, u, v)
갱신 벡터나 행렬이 주어졌을 때 QR 분해를 갱신해요. 실수 또는 복소수 행렬 A = QR(Q 유니타리, R 위 사다리꼴)의 QR 분해가 주어지면, A + uv'의 QR 분해를 돌려줘요. u와 v는 열 벡터(rank-1 갱신)이거나 열 수가 같은 행렬(rank-k 갱신)이에요. 후자의 경우 rank-1 갱신의 연속으로 처리되므로, k가 충분히 크면 처음부터 분해를 다시 계산하는 편이 더 빠르고 정확해요. 제공되는 QR 분해는 완전(Q 정방)이거나 경제형(R 정방)일 수 있어요. 함께 보면 좋은 함수: qr, qrinsert, qrdelete, qrshift.
qrinsert — 행/열 삽입 갱신
[Q1, R1] = qrinsert (Q, R, j, x, orient)
원래 분해된 행렬에 삽입할 행이나 열이 주어졌을 때 QR 분해를 갱신해요. 실수 또는 복소수 행렬 A = Q*R(Q 유니타리, R 위 사다리꼴)의 QR 분해가 주어지면, [A(:,1:j-1) x A(:,j:n)]의 QR 분해를 돌려줘요. 여기서 u는 (orient가 "col"일 때) A에 삽입할 열 벡터예요. 또는 [A(1:j-1,:);x;A(:,j:n)]의 QR 분해인데, x는 (orient가 "row"일 때) A에 삽입할 행 벡터예요. orient의 기본값은 "col"이에요.
orient가 "col"이면 u는 행렬일 수 있고 j는 인덱스 벡터일 수 있어서, B(:,j)가 u를 주고 B(:,j) = []가 A를 주는 행렬 B의 QR 분해를 만들어요. 후자의 경우 k번 삽입의 연속으로 처리되므로, k가 충분히 크면 처음부터 다시 계산하는 편이 낫고 정확해요. orient가 "col"이면 제공되는 QR 분해는 완전(Q 정방)이거나 경제형(R 정방)일 수 있어요. orient가 "row"면 완전 분해가 필요해요. 함께 보면 좋은 함수: qr, qrupdate, qrdelete, qrshift.
qrdelete — 행/열 삭제 갱신
[Q1, R1] = qrdelete (Q, R, j, orient)
원래 분해된 행렬에서 삭제할 행이나 열이 주어졌을 때 QR 분해를 갱신해요. 실수 또는 복소수 행렬 A = Q*R(Q 유니타리, R 위 사다리꼴)의 QR 분해가 주어지면, [A(:,1:j-1), U, A(:,j:n)]의 QR 분해를 돌려줘요. 여기서 u는 (orient가 "col"일 때) A에 삽입할 열 벡터예요. 또는 [A(1:j-1,:);X;A(:,j:n)]의 QR 분해인데, x는 (orient가 "row"일 때) 행 벡터예요. orient의 기본값은 "col"이에요.
orient가 "col"이면 j는 인덱스 벡터일 수 있어서, A(:,j) = []가 B를 주는 행렬 B의 QR 분해를 만들어요. 후자의 경우 k번 삭제의 연속으로 처리되므로, k가 충분히 크면 처음부터 다시 계산하는 편이 낫고 정확해요. orient가 "col"이면 제공되는 QR 분해는 완전(Q 정방)이거나 경제형(R 정방)일 수 있어요. orient가 "row"면 완전 분해가 필요해요. 함께 보면 좋은 함수: qr, qrupdate, qrinsert, qrshift.
qrshift — 열 구간 이동 갱신
[Q1, R1] = qrshift (Q, R, i, j)
원래 분해된 행렬에서 이동시킬 열 구간이 주어졌을 때 QR 분해를 갱신해요. 실수 또는 복소수 행렬 A = Q*R(Q 유니타리, R 위 사다리꼴)의 QR 분해가 주어지면, p가 순열인 A(:,p)의 QR 분해를 돌려줘요.
p = [1:i-1, circshift(i:j, 1), j+1:n]if i < j- 또는
p = [1:j-1, circshift(j:i,-1), i+1:n]if j < i
함께 보면 좋은 함수: qr, qrupdate, qrinsert, qrdelete.
QZ 분해 — qz
[AA, BB, Q, Z, V, W] = qz (A, B)
[AA, BB, Q, Z, V, W] = qz (A, B, opt)
일반화 고유값 문제의 QZ 분해를 계산해요. 일반화 고유값 문제는 A x = lambda B x로 정의돼요. 이 함수에는 두 가지 호출 형태가 있어요.
[AA, BB, Q, Z, V, W] = qz (A, B)— 복소 QZ 분해, 일반화 고유벡터, 일반화 고유값을 계산해요.
AA = Q * A * Z, BB = Q * B * Z
A * V * diag (diag (BB)) = B * V * diag (diag (AA))
diag (diag (BB)) * W' * A = diag (diag (AA)) * W' * B
AA와 BB는 위 삼각이고 Q와 Z는 유니타리예요. 행렬 V와 W는 각각 오른쪽·왼쪽 일반화 고유벡터를 담아요.
[AA, BB, Q, Z, V, W] = qz (A, B, opt)— opt 인자는"real"또는"complex"여야 해요."complex"면 이 호출 형태는 입력 인자 두 개만 있는 첫 번째 형태와 동일해요."real"이면 실수 QZ 분해를 계산해요. 특히 AA는 대각에 1×1·2×2 블록을 가진 준위삼각(quasi-upper triangular)임이 보장되고 Q와 Z는 직교예요. 위에서 언급한 오른쪽·왼쪽 일반화 고유벡터 항등식은 AA가 위 삼각일 때만 검증돼요(즉 모든 일반화 고유값이 실수인 경우, 그때 실수·복소 QZ가 일치해요).
참고: qz는 순열 균형(permutation balancing)을 수행하지만 스케일링은 하지 않아요(참고: balance). 그래서 eig보다 덜 정확한 결과를 낼 수 있어요. 출력 인자의 순서는 MATLAB과의 호환을 위해 선택됐어요. 고유값은 결과 AA, BB 행렬을 바탕으로 ordeig 함수로 계산해요. 함께 보면 좋은 함수: eig, gsvd, balance, chol, hess, lu, qr, qzhess, schur, ordeig.
qzhess — 헤센베르크-삼각 분해
[aa, bb, q, z] = qzhess (A, B)
행렬 펜실 (A, B)의 헤센베르크-삼각 분해를 계산해요. aa = q * A * z, bb = q * B * z를 돌려주며 q와 z는 직교예요. 예를 들어 보죠.
[aa, bb, q, z] = qzhess ([1, 2; 3, 4], [5, 6; 7, 8])
⇒ aa =
-3.02244 -4.41741
0.92998 0.69749
⇒ bb =
-8.60233 -9.99730
0.00000 -0.23250
⇒ q =
-0.58124 -0.81373
-0.81373 0.58124
⇒ z =
Diagonal Matrix
1 0
0 1
헤센베르크-삼각 분해는 Moler와 Stewart의 QZ 분해 알고리즘의 첫 단계예요. 알고리즘은 Golub와 Van Loan, Matrix Computations, 2nd edition에서 가져왔어요. 함께 보면 좋은 함수: lu, chol, hess, qr, qz, schur, svd.
슈어 분해 — schur
S = schur (A)
S = schur (A, "real")
S = schur (A, "complex")
S = schur (A, opt)
[U, S] = schur (…)
A의 슈어(Schur) 분해를 계산해요. 정방행렬 A의 슈어 분해는 S = U' * A * U로 정의돼요. 여기서 U는 유니타리 행렬(U'* U는 항등행렬)이고 S는 위 삼각이에요. A(그리고 S)의 고유값은 S의 대각 원소예요. 행렬 A가 실수면 실수 슈어 분해를 계산하는데, 이때 U는 직교 행렬이고 S는 대각을 따라 크기가 최대 2 x 2인 블록을 가진 블록 위 삼각 행렬이에요.
실수 행렬의 기본값은 실수 슈어 분해예요. "complex" 플래그를 넘기면 복소 분해를 강제할 수 있어요. 고유값은 opt 값에 따라 대각을 따라 선택적으로 정렬돼요.
opt = "a"— 음의 실수부를 가진 고유값을 S의 앞 블록으로 이동해요. 기억법: 대수 리카티 방정식(Algebraic Riccati Equations)의"a"로, 이 정렬이 유용한 곳이에요.opt = "d"— 크기가 1보다 작은 고유값을 S의 앞 블록으로 이동해요. 기억법: 이산 대수 리카티 방정식(Discrete Algebraic Riccati Equations)의"d".opt = "u"— 정렬 없음. 고유값을 특별히 정렬하지 않아요(기본).
U의 앞 k개 열은 항상 S의 앞 k개 고유값에 대응하는 A-불변 부분공간을 펼쳐요. 함께 보면 좋은 함수: rsf2csf, ordschur, trexc, ordeig, lu, chol, hess, qr, qz, svd, eig.
rsf2csf — 실수 슈어 폼을 복소로 변환
[U, T] = rsf2csf (UR, TR)
실수 준위삼각 슈어 폼 TR을 복소 위삼각 슈어 폼 T로 변환해요. 다음 관계가 성립함에 주의하세요: UR * TR * UR' = U * T * U', 그리고 U' * U는 항등 행렬 I예요. U와 T는 유일하지 않다는 점에도 주의하세요. 함께 보면 좋은 함수: schur, ordschur, trexc.
ordschur — 실수 슈어 분해 재정렬
[UR, SR] = ordschur (U, S, select)
schur 함수로 얻은 실수 슈어 분해 (U,S)를, 선택된 고유값이 준삼각 슈어 행렬의 왼쪽 위 대각 블록에 나타나도록 재정렬해요. 논리 벡터 select가 S의 대각을 따라 나타나는 선택 고유값을 지정해요.
예를 들어 A = [1, 2; 3, 4]와 그 슈어 분해 [U, S] = schur (A)가 다음을 돌려줬다고 해보죠.
U =
-0.82456 -0.56577
0.56577 -0.82456
S =
-0.37228 -1.00000
0.00000 5.37228
다음처럼 하면 양의 고유값이 왼쪽 위 모서리에 오도록 분해를 재정렬할 수 있어요.
[U, S] = ordschur (U, S, [0,1])
함께 보면 좋은 함수: schur, trexc, ordeig, ordqz.
trexc — 슈어 분해 재정렬(LAPACK ZTREXC)
[U, T] = trexc (U, T, M)
LAPACK 함수 ZTREXC를 사용해 슈어 분해를 재정렬해요. 슈어 분해 A = U*T*U'의 유니타리 행렬 U와 위삼각 슈어 폼 T가 주어지면, 이 함수는 M의 교환 사양에 따라 T의 대각 원소를 재정렬해요. M의 각 행은 [IFST, ILST] 두 인덱스를 담는데, 위치 IFST의 대각 원소를 위치 ILST로 옮기라는 뜻이에요. 교환은 순차적으로 수행돼요. 함께 보면 좋은 함수: schur, ordschur.
ordqz — QZ 분해 재정렬
[AR, BR, QR, ZR] = ordqz (AA, BB, Q, Z, keyword)
[AR, BR, QR, ZR] = ordqz (AA, BB, Q, Z, select)
일반화 고유값 문제의 QZ 분해를 재정렬해요. 일반화 고유값 문제는 A x = lambda B x로 정의되며, 그 일반화 슈어 분해는 qz 알고리즘을 사용해 [AA, BB, Q, Z] = qz (A, B)로 계산해요. 여기서 AA, BB, Q, Z는 다음을 만족해요.
AA = Q * A * Z, BB = Q * B * Z
ordqz 함수는 AA와 BB의 대각에 있는 고유값의 순서가 바뀌도록 유니타리 변환 QR과 ZR을 계산해요. 결과적으로 재정렬된 행렬 AR과 BR은 다음을 만족해요.
AR = QR * A * ZR, BR = QR * B * ZR
이 함수는 키워드 인자로 호출하거나 논리 벡터 select로 호출할 수 있어요. 키워드는 AR과 BR의 왼쪽 위 블록에서 고유값을 다음처럼 선택해요.
"S","udi"— 작음(small): 앞 블록이 모두 |lambda| < 1"B","udo"— 큼(big): 앞 블록이 모두 |lambda| ≥ 1"-","lhp"— 음의 실수부: 앞 블록이 모두 열린 왼쪽 반평면의 고유값"+","rhp"— 음이 아닌 실수부: 앞 블록이 모두 닫힌 오른쪽 반평면의 고유값
키워드 대신 논리 벡터 select를 주면 ordqz는 select(k)가 true인 모든 고유값 k를 왼쪽 블록으로 재정렬해요. 참고: 키워드는 qr의 것과 호환돼요. 함께 보면 좋은 함수: eig, ordeig, qz, schur, ordschur.
ordeig — 준삼각 행렬의 고유값
lambda = ordeig (A)
lambda = ordeig (A, B)
준삼각(quasi-triangular) 행렬의 고유값을 행렬 A에 나타나는 순서대로 돌려줘요. 준삼각 행렬 A는 보통 슈어 분해의 결과예요. 두 번째 입력 B와 함께 호출하면 쌍 A, B의 일반화 고유값을 행렬 A-lambda*B에 나타나는 순서대로 돌려줘요. 쌍 A, B는 보통 QZ 분해의 결과예요. 함께 보면 좋은 함수: ordschur, ordqz, eig, schur, qz.
subspace — 부분공간 사이의 각도
angle = subspace (A, B)
행렬 A와 B의 열이 펼치는 두 부분공간 사이의 가장 큰 주각(principal angle)을 구해요. 참고 문헌: Andrew V. Knyazev, Merico E. Argentati, "Principal Angles between Subspaces in an A-Based Scalar Product: Algorithms and Perturbation Estimates", SIAM Journal on Scientific Computing, Vol. 23, No. 6, pp. 2008–2040.
특이값 분해 — svd
s = svd (A)
[U, S, V] = svd (A)
[U, S, V] = svd (A, "econ")
[U, S, V] = svd (A, 0)
A의 특이값 분해(SVD)를 계산해요. 특이값 분해는 A = U*S*V' 관계로 정의돼요. svd 함수는 보통 특이값 벡터만 돌려줘요. 반환 값 세 개로 호출하면 U, S, V를 계산해요. 예를 들어 보죠.
svd (hilb (3))
는 다음을 돌려줘요.
ans =
1.4083189
0.1223271
0.0026873
그리고
[u, s, v] = svd (hilb (3))
는 다음을 돌려줘요.
u =
-0.82704 0.54745 0.12766
-0.45986 -0.52829 -0.71375
-0.32330 -0.64901 0.68867
s =
1.40832 0.00000 0.00000
0.00000 0.12233 0.00000
0.00000 0.00000 0.00269
v =
-0.82704 0.54745 0.12766
-0.45986 -0.52829 -0.71375
-0.32330 -0.64901 0.68867
두 번째 인자가 0이 아닐 때 svd는 U나 V의 불필요한 행·열을 제거한 경제 크기(economy-sized) 분해를 돌려줘요. 두 번째 인자가 정확히 0이면 행렬 A에 따라 분해를 고르는데, A가 열보다 행이 많으면 경제 크기 분해를, 그렇지 않으면 일반 분해를 계산해요.
알고리즘 참고: 완전 분해(특이값 외에 왼쪽·오른쪽 특이 행렬)를 계산할 때 LAPACK에 두 가지 루틴 선택지가 있어요. Octave가 기본으로 쓰는 루틴은 gesvd예요. 대안은 gesdd인데 5배 더 빠르지만 메모리를 더 쓰고 일부 입력 행렬에 대해 부정확할 수 있어요. 극단적인 규모에서 더 나은 정확도에 적합한 세 번째 루틴 gejsv도 있어요. 드라이버 선택에 대한 자세한 내용은 svd_driver 문서를 참고하세요.
함께 보면 좋은 함수: svd_driver, svds, eig, lu, chol, hess, qr, qz.
svd_driver — SVD 드라이버 설정
val = svd_driver ()
old_val = svd_driver (new_val)
old_val = svd_driver (new_val, "local")
svd가 사용하는 기본 LAPACK 드라이버를 조회하거나 설정해요. 현재 인식되는 값은 "gesdd", "gesvd", "gejsv"예요. 기본값은 "gesvd"예요. 함수 안에서 "local" 옵션으로 호출하면 변수가 그 함수와 호출하는 서브루틴에 대해 로컬로 바뀌고, 함수를 빠져나오면 원래 변수 값으로 복원돼요.
알고리즘 참고: LAPACK 라이브러리 루틴 gesvd와 gesdd는 완전 특이값 분해(왼쪽·오른쪽 특이 행렬과 특이값)를 계산할 때만 달라요. 특이값만 계산할 때는 아래 논의가 관련 없어요. 더 새로운 gesdd 루틴은 QR 분해 기반인 대안 gesvd보다 5배 빠른 Divide-and-Conquer 알고리즘을 기반으로 해요. 하지만 새 알고리즘은 메모리를 훨씬 더 쓸 수 있어요. MxN 입력 행렬에 대해 메모리 사용이 O(min(M,N)^2)인 반면, 대안은 O(max(M,N))이에요.
gejsv 루틴은 전처리된 자코비(Jacobi) SVD 알고리즘을 사용해요. gesvd와 gesdd와 달리 gejsv에는 일부 극단적 경우에서 정확도를 오염시킬 수 있는 2중 대각화 단계가 없어요. 또 gejsv는 어떤 의미에서 최적으로 정확한 것으로 알려져 있어요. 하지만 속도가 더 느리고(핵은 단일 스레드) 메모리를 더 써요(O(min(M,N)^2 + M + N)).
속도와 메모리 문제 외에도, 어떤 입력 행렬은 gesdd로 정확히 분해되지 않은 사례가 있었어요. 현재 진행 중인 버그 https://savannah.gnu.org/bugs/?55564 참고. 이 정확도 문제가 LAPACK 라이브러리의 새 버전에서 해결될 때까지, Octave의 기본 드라이버는 "gesvd"로 설정되어 있어요. 함께 보면 좋은 함수: svd.
기타 — housh, krylov
housh — 하우스홀더 반사 벡터
[housv, beta, zer] = housh (x, j, z)
x를 항등행렬의 j번째 열로 반사하도록 하우스홀더 반사 벡터 housv를 계산해요. 즉 다음과 같아요.
(I - beta*housv*housv')x = norm (x)*e(j) if x(j) < 0,
(I - beta*housv*housv')x = -norm (x)*e(j) if x(j) >= 0
입력:
- x — 벡터
- j — 벡터 안의 인덱스
- z — 0에 대한 임계값(보통 0이어야 함)
출력(참고: Golub and Van Loan):
- beta — beta = 0이면 반사를 적용할 필요가 없음(zer는 0으로 설정)
- housv — 하우스홀더 벡터
krylov — 블록 크릴로프 부분공간
[u, h, nu] = krylov (A, V, k, eps1, pflg)
블록 크릴로프(Krylov) 부분공간의 직교 기저 u를 구성해요. 블록 크릴로프 부분공간은 다음 형태예요.
[v a*v a^2*v ... a^(k+1)*v]
직교성 상실을 막기 위해 하우스홀더 반사를 사용해 구성해요. V가 벡터이면 h는 a*u == u*h+rk*ek'가 되도록 하는 헤센베르크 행렬을 담아요. 여기서 rk = a*u(:,k)-u*h(:,k)이고 ek'는 길이 k의 벡터 [0, 0, …, 1]이에요. 그렇지 않으면 h는 의미가 없어요. V가 벡터이고 k가 length (A) - 1보다 크면 h는 a*u == u*h가 되도록 하는 헤센베르크 행렬을 담아요. nu의 값은 (eps1에 기반한) 크릴로프 부분공간의 스팬 차원이에요. b가 벡터이고 k가 m-1보다 크면 h는 A의 헤센베르크 분해를 담아요.
선택 매개변수 eps1은 0에 대한 임계값이에요. 기본값은 1e-12예요. 선택 매개변수 pflg가 0이 아니면 수치 거동을 개선하기 위해 행 피벗을 사용해요. 기본값은 0이에요. 참고 문헌: A. Hodel, P. Misra, "Partial Pivoting in the Computation of Krylov Subspaces of Large Sparse Systems", Proceedings of the 42nd IEEE Conference on Decision and Control, December 2003.
더 알아보기
- 분해를 활용하는 선형 대수 전반은 Linear Algebra(선형 대수) 장에서 다뤄요.
- 각 분해의 응용(고유값, 최소자승, 역행렬)도 함께 살펴보세요.