Main Content

행렬 분해

소개

이 섹션에서 다루는 세 가지 행렬 분해에는 모두 삼각 행렬이 사용됩니다. 참고로, 삼각 행렬은 대각선 위 또는 대각선 아래에 있는 요소가 모두 0인 행렬입니다. 삼각 행렬이 포함된 선형 연립방정식은 전진대입이나 역대입을 사용하여 쉽고 빠르게 풀 수 있습니다.

촐레스키 분해(Cholesky Factorization)

촐레스키 분해는 삼각 행렬과 삼각 행렬의 전치를 곱해 대칭 행렬을 표현합니다.

A = R′R,

여기서 R은 상부 삼각 행렬입니다.

하지만 일부 대칭 행렬은 이러한 방법으로 분해될 수 없습니다. 촐레스키 분해가 가능한 행렬은 양의 정부호 행렬로 간주됩니다. 따라서, A의 모든 대각선 요소는 양의 요소이며 비대각선 요소는 "그렇게 크지 않음"을 알 수 있습니다. 파스칼 행렬은 흥미로운 예를 보여줍니다. 이 장 전반에 걸쳐 예로 든 행렬 A는 3×3 파스칼 행렬이었습니다. 이를 잠시 6×6 행렬로 전환해 보겠습니다.

A = pascal(6)

A =
       1     1     1     1     1     1
       1     2     3     4     5     6
       1     3     6    10    15    21
       1     4    10    20    35    56
       1     5    15    35    70   126
       1     6    21    56   126   252

A의 요소는 이항 계수입니다. 각 요소는 인접한 윗 요소와 왼쪽 요소의 합입니다. 촐레스키 분해를 수행하면 다음과 같습니다.

R = chol(A)

R =
     1     1     1     1     1     1
     0     1     2     3     4     5
     0     0     1     3     6    10
     0     0     0     1     4    10
     0     0     0     0     1     5
     0     0     0     0     0     1

요소가 다시 이항 계수인 것을 볼 수 있습니다. R'*RA와 같다는 사실로 이항 계수 간 곱의 합을 수반하는 단위 행렬이라는 것이 입증됩니다.

참고

촐레스키 분해는 복소수 행렬에도 적용됩니다. 촐레스키 분해가 가능한 복소수 행렬은

A′ = A

를 충족하며 에르미트 양의 정부호 행렬로 간주됩니다.

촐레스키 분해를 수행하면 다음 선형 시스템을

Ax = b

다음 선형 시스템으로 변환할 수 있습니다.

R′Rx = b.

백슬래시 연산자가 삼각 행렬을 인식하기 때문에 이는 MATLAB® 환경에서 다음을 통해 신속하게 풀 수 있습니다.

x = R\(R'\b)

A가 n×n인 경우 chol(A)의 계산 복잡도는 O(n3)이지만 이후에 나오는 백슬래시 해의 복잡도는 O(n2)에 불과합니다.

LU 분해

LU 분해, 즉 가우스 소거법(Gaussian Elimination)은 임의의 정사각 행렬 A를 하부 삼각 행렬 치환과 상부 삼각 행렬의 곱으로 표현합니다.

A = LU,

여기서 L은 해당 대각선에 1이 포함된 하부 삼각 행렬의 치환이고 U는 상부 삼각 행렬입니다.

치환은 이론상으로는 물론 계산상의 이유로도 꼭 필요합니다. 다음 행렬은

[0110]

두 행을 서로 교환하지 않고서는 삼각 행렬의 곱으로 표현할 수 없습니다. 다음 행렬은

[ε110]

삼각 행렬의 곱으로 표현할 수 있지만 ε이 작을 경우 인수의 요소가 크고 이로 인해 오차가 확대되므로 반드시 필요하지 않더라도 치환을 사용하는 것이 바람직합니다. 부분 피벗 연산을 수행하면 L의 요소가 계산 차수 1로 바인딩되고 U의 요소 크기는 A의 요소 크기와 큰 차이가 나지 않게 됩니다.

예를 들면 다음과 같습니다.

[L,U] = lu(B)

L =
    1.0000         0         0
    0.3750    0.5441    1.0000
    0.5000    1.0000         0

U =
    8.0000    1.0000    6.0000
         0    8.5000   -1.0000
         0         0    5.2941

A의 LU 분해를 실행하면 다음 선형 시스템을

A*x = b

다음 선형 시스템으로 변환해 빠르게 풀 수 있습니다.

x = U\(L\b)

다음과 같은 LU 분해로 행렬식과 역행렬을 계산합니다.

det(A) = det(L)*det(U)

inv(A) = inv(U)*inv(L)

det(A) = prod(diag(U))를 사용하여 행렬식을 계산할 수도 있지만 이 경우 행렬식의 부호가 뒤바뀔 수도 있습니다.

QR 분해

직교 행렬, 즉 정규 직교 열이 포함되어 있는 행렬은 해당 열에 모두 단위 길이가 지정되어 있고 서로 직각을 이루는 실수 행렬입니다. Q가 직교 행렬인 경우 다음이 성립합니다.

QTQ = I,

여기서 I는 단위 행렬입니다.

가장 단순한 형태의 직교 행렬은 2차원 좌표 회전 행렬입니다.

[cos(θ)sin(θ)sin(θ)cos(θ)].

복소수 행렬의 경우에는 유니타리(Unitary) 행렬이라는 용어를 씁니다. 직교 행렬과 유니타리 행렬은 길이와 각도를 보존하고 오차를 확대하지 않기 때문에 수치 계산에 바람직합니다.

직교, 즉 QR 분해는 임의의 사각 행렬을 직교 행렬 또는 유니타리 행렬과 상부 삼각 행렬 간의 곱으로 표현합니다. 다음과 같은 경우에는 열 치환이 필요할 수 있습니다.

A = QR

또는

AP = QR,

여기서 Q는 직교 행렬 또는 유니타리 행렬이고, R은 상부 삼각 행렬이며, P는 치환 행렬입니다.

QR 분해에는 전체 크기로 행렬 분해하는 경우, 효율적인 크기로 분해하는 경우, 열 치환을 사용하는 경우, 열 치환을 사용하지 않는 경우와 같은 네 가지 변형이 존재합니다.

과결정 선형 시스템은 열 개수보다 행 개수가 더 많은 사각 행렬(즉, m×n, m > n)을 다룹니다. 전체 크기 QR 분해를 수행하면 정사각 m×m 직교 행렬 Q와 사각 m×n 상부 삼각 행렬 R이 생성됩니다.

C=gallery('uniformdata',[5 4], 0);
[Q,R] = qr(C)

Q =

    0.6191    0.1406   -0.1899   -0.5058    0.5522
    0.1506    0.4084    0.5034    0.5974    0.4475
    0.3954   -0.5564    0.6869   -0.1478   -0.2008
    0.3167    0.6676    0.1351   -0.1729   -0.6370
    0.5808   -0.2410   -0.4695    0.5792   -0.2207


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648
         0         0         0         0

많은 경우 Q의 마지막 m – n 열은 R의 맨 아래 부분에 있는 0과 곱해지므로 필요하지 않습니다. 따라서 효율적인 크기의 QR 분해는 정규 직교 열이 포함된 m×n 사각 행렬 Q와 정사각 n×n 상부 삼각 행렬 R을 생성합니다. 5×4 예제의 경우 이는 상당한 절감 효과로 볼 수 없지만 이보다 크고 직사각형 특성이 뚜렷한 행렬의 경우에는 시간과 메모리를 모두 절감하는 효과가 매우 중요하게 작용할 수 있습니다.

[Q,R] = qr(C,0)	
Q =

    0.6191    0.1406   -0.1899   -0.5058
    0.1506    0.4084    0.5034    0.5974
    0.3954   -0.5564    0.6869   -0.1478
    0.3167    0.6676    0.1351   -0.1729
    0.5808   -0.2410   -0.4695    0.5792


R =

    1.5346    1.0663    1.2010    1.4036
         0    0.7245    0.3474   -0.0126
         0         0    0.9320    0.6596
         0         0         0    0.6648

LU 분해와 대조적으로 QR 분해에는 피벗 연산이나 치환을 수행할 필요가 없습니다. 하지만 세 번째 출력 인수의 존재로 인해 작동되는 열 치환 선택 사항은 특이점 또는 랭크 부족을 감지하는 데 유용합니다. 각 분해 단계에서 노름이 가장 큰, 나머지 분해되지 않는 행렬의 열은 해당 단계의 기저로 사용됩니다. 이에 따라 R의 대각선 요소가 내림차순으로 나타나고 이 요소들을 검토하면 열 간의 선형 종속성이 거의 확실하게 드러나게 됩니다. 여기에 제시된 작은 예제의 경우 C의 두 번째 열은 첫 번째 열보다 노름이 크므로 두 열의 위치가 서로 바뀝니다.

[Q,R,P] = qr(C)

Q =
   -0.3522    0.8398   -0.4131
   -0.7044   -0.5285   -0.4739
   -0.6163    0.1241    0.7777

R =
  -11.3578   -8.2762
         0    7.2460
         0         0

P =
     0     1
     1     0

효율적인 크기로의 분해와 열 치환을 모두 사용하면 세 번째 출력 인수는 치환 행렬이 아니라 치환 벡터가 됩니다.

[Q,R,p] = qr(C,0)

Q =
   -0.3522    0.8398
   -0.7044   -0.5285
   -0.6163    0.1241

R =
  -11.3578   -8.2762
         0    7.2460


p =
     2     1

QR 분해는 과결정 선형 시스템을 등가의 삼각 시스템으로 변환합니다. 다음 표현식은

norm(A*x - b)

다음 표현식과 같습니다.

norm(Q*R*x - b)

직교 행렬로 곱셈을 수행하면 유클리드 노름(Euclidean Norm)이 보존되므로 이 표현식은 다음 표현식과도 같습니다.

norm(R*x - y)

여기서 y = Q'*b입니다. R의 마지막 m-n 행이 0이므로 이 표현식은 두 부분으로 분할됩니다.

norm(R(1:n,1:n)*x - y(1:n))

norm(y(n+1:m))

A에 완전 랭크가 있으면 위의 처음 표현식이 0이 되는 x를 구할 수 있습니다. 그러면 두 번째 표현식에서 잔차의 노름이 구해집니다. A에 완전 랭크가 없다면 R의 삼각 구조체로 최소제곱 문제에 대한 기저해를 구할 수 있습니다.

행렬 분해에 멀티스레드 계산 사용하기

MATLAB에서는 다수의 선형 대수 함수와 요소별 숫자형 함수의 멀티스레드 계산을 지원합니다. 이 함수들은 여러 스레드에서 자동으로 실행됩니다. 여러 개의 CPU를 기반으로 보다 빠른 속도로 실행해야 하는 함수 또는 표현식의 경우 다음과 같은 다양한 조건을 충족해야 합니다.

  1. 함수가 동시에 실행 가능한 여러 부분으로 쉽게 분할할 수 있는 연산을 수행해야 합니다. 이 부분들은 프로세스 간에 거의 교신이 이루어지지 않는 상태로 실행될 수 있어야 하며, 순차적 연산이 거의 필요하지 않아야 합니다.

  2. 데이터를 나누고 개별 실행 스레드를 관리하는 데 소요되는 시간보다 동시 실행으로 얻게 되는 이점이 더 클 정도로 데이터 크기가 충분히 커야 합니다. 예를 들어, 대부분의 함수는 배열에 수천 개 이상의 요소가 포함되어 있는 경우에만 실행 속도가 빨라집니다.

  3. 연산이 메모리에 바인딩되지 않아야 합니다. 처리 시간에서 메모리 액세스 시간이 많은 비중을 차지해서는 안 되기 때문입니다. 일반적으로 단순한 함수보다 복잡한 함수의 경우에 더 높은 속도 향상이 이루어집니다.

luqr은 대규모 배정밀도 배열(약 1만 개 요소)의 경우 속도를 크게 향상시킵니다.

참고 항목

| |

관련 항목