28. Matrix Operations

이 장에서는 행렬 연산을 알아본다. 실제로는 수치적 안정성이 중요하다. 부동 소수점 표현의 한계로 인해 수치적 불안정성이 일어나기 때문이다.

28.1. Solving systems of linear equations

선형 방정식의 계인 Ax = b의 를 이 방정식들을 동시에 만족하는 x의 집합으로 정의한다. 미지수가 n개 있을 때 A의 랭크가 n보다 작으면 이 계는 결정불충분적이고, 해가 무한히 많거나 아예 없을 수 있다. A의 랭크가 n보다 크면 이 계는 결정과충분적이 되어 해가 아예 없을 수 있다. 선형 방정식을 풀 때는 LUP 분해가 빠르고 수치적으로 안정적이다.

Overview of LUP decomposition

LUP 분해는 PA = LU인 행렬 P, L, U를 찾는 것이다. P는 순열 행렬, L은 단위 하삼각 행렬, U은 상삼각 행렬이다.

Forward and back substitution

전방 대입은 Ly = Pb를 \Theta(n^2) 시간에 풀 수 있게 한다. y를 구했을 때 후방 대입은 Ux = y를 \Theta(n^2) 시간에 풀 수 있게 한다. 알고리즘은 다음과 같다.

LUP-SOLVE(L, U, π, b)
n = L.rows
let x be a new vector of length n
for i = 1 to n
    y_i = b_(π[i]) - ∑_(j=1)^(i-1) l_(ij) y_j
for i = n downto 1
    x_i = (y_i - ∑_(j=i+1)^(n) u_(ij) x_j)/u_(ii)
return x

Computing an LU decomposition

P가 단위 행렬인 경우 A = LU로 나타내는 LU 분해를 생각할 수 있다. 이는 슈르 보행렬을 사용하는 가우시안 소거법으로 이루어진다. 이 과정에서 중심 원소들을 활용하는 피보팅이 쓰인다. 알고리즘은 다음과 같다.

LU-DECOMPOSITION(A)
n = A.rows
let L and U be new n x n matrices
initialize U with 0s below the diagonal
initialize L with 1s on the diagonal and 0s above the diagonal
for k = 1 to n
    u_(kk) = a_(kk)
    for i = k + 1 to n
        l_(ik) = a_(ik) / u_(kk)
        u_(ki) = a_(ki)
    for i = k + 1 to n
        for j = k + 1 to n
            a_(ij) = a_(ij) - l_(ik)u_(kj)
return L and U

이는 \Theta(n^{3}) 시간이 걸린다.

Computing and LUP decomposition

LUP 분해는 다음과 같다.

LUP-DECOMPOSITION(A)
n = A.rows
let π[1, ..., n] be a new array
for i = 1 to n
    π[i] = i
for k = 1 to n
    p = 0
    for i = k to n
        if |a_(ik)| > p
            p = |a_(ik)|
            k' = i
    if p == 0
        error "singular matrix"
    exchange π[k] with π[k']
    for i = 1 to n
        exchange a_(ki) with a_(k'i)
    for i = k + 1 to n
        a_(ik) = a_(ik) / a_(kk)
        for j = k + 1 to n
            a_(ij) = a_(ij) - a_(ik)a_(kj)

이도 \Theta(n^{3}) 시간이 걸린다.

28.2. Inverting matrices

역행렬은 어떻게 구할까?

Computing a matrix inverse from an LUP decomposition

LUP 분해를 구할 수 있다면 AX = I_{n}을 구하는 것은 AX_{i} = e_{i}을 i 각각에 대해 푸는 것과 같다. 그러므로 LUP 분해를 구할 수 있다면 역행렬은 \Theta(n^{3})에 구해진다.

Matrix multiplication and matrix inversion

행렬 곱과 역행렬 구하기는 다음의 관계가 있다.

Theorem. (Multiplication is no harder than inversion) n x n 행렬을 I(n) = \Omega(n^{2}) 시간에 역행렬을 구할 수 있고 I(3n) = O(I(n))이 성립한다면 두 행렬의 곱은 O(I(n)) 시간에 구할 수 있다.

Theorem. (Inversion is no harder than multiplication) n x n 행렬을 M(n) = \Omega(n^{2}) 시간에 곱할 수 있고 어떤 0 \leq k \leq n에 대해 M(n+k) = O(M(n)), 어떤 c < \frac{1}{2}에 대해 M(\frac{n}{2}) \leq c M(n)이 성립한다면 역행렬이 존재하는 n x n 실수 행렬은 그 역행렬을 O(M(n)) 시간에 구할 수 있다.

28.3. Symmetric positive-definite matrices and least-squares approximation

대칭이고 양의 정칙인 행렬은 여러 좋은 특성을 갖는다.

Lemma. 양의 정칙인 행렬은 역행렬이 존재한다.

k번째 선두 부분행렬을 첫 k 행과 첫 k 열의 교집합으로 정의하자.

Lemma. 대칭이고 양의 정칙인 행렬의 모든 선두 부분행렬은 대칭이고 양의 정칙이다.

k번째 선두 부분행렬 A_{k}에 대해 슈르 보행렬S = C - B A_{k}^{-1} B^{T}로 일반화하면 다음이 성립한다.

Lemma. (Schur complement lemma) 대칭이고 양의 정칙인 행렬의 선두 부분행렬에 대한 슈르 보행렬은 대칭이고 양의 정칙이다.

Collorary. 대칭이고 양의 정칙인 행렬에 대한 LU 분해는 0에 의한 나누기를 하지 않는다.

Least-squares approximation

대칭 양정칙 행렬의 중요한 적용은 데이터에 대한 곡선 맞춤이다. 이 곡선은 기저 함수의 가중치합으로 나타내어진다. 널리 쓰이는 선택은 f_{j}(x) = x^{j-1}이다. 이 경우 다항식 곡선 맞춤이 된다. 이 때 기저 함수를 데이터값에 대해 구한 값으로 만든 행렬을 A, 곡선을 가중치합으로 나타냈을 때 가중치 벡터를 c라 하면 \eta = Ac - y근사 오차라 한다. 근사 오차를 최소화시키는 해를 최소 제곱해라 한다. 이는 A^{T}A c  = A^{T} y을 만족하며, 이를 표준방정식이라 한다. 이 해는 c = ((A^{T}A)^{-1}A^{T})y = A^{+}y이 되며, 이 때 A^{+} = (A^{T}A)^{-1}A^{T}유사역행렬이라 한다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중