Pivoting 전략 Partial Pivoting과 Complete Pivoting

LU 분해에서 수치적 안정성을 확보하기 위해 pivoting 전략은 매우 중요하다. Pivoting은 주어진 행렬에서 가장 큰 요소를 이용해 계산 과정에서 발생할 수 있는 수치적 오류를 최소화하는 기법이다. 여기에서는 Partial Pivoting과 Complete Pivoting의 개념과 이들이 어떻게 사용되는지 설명한다.

Pivoting의 필요성

LU 분해는 주어진 행렬을 하삼각행렬과 상삼각행렬로 분해하는 과정이다. 그러나, 일부 행렬에서는 직관적으로 분해를 수행하면 수치적 불안정성이 발생할 수 있다. 특히, 작은 피벗 요소로 인해 수치적 오차가 크게 발생하거나, 분해가 불가능해지는 경우가 있다. 이런 문제를 방지하기 위해, pivoting 전략을 적용하여 행렬의 요소들을 재배열함으로써 안정성을 확보한다.

Partial Pivoting

Partial Pivoting은 각 단계에서 현재 고려 중인 열(column)에서 가장 큰 절댓값을 가지는 요소를 찾아 해당 요소가 피벗 요소가 되도록 행을 교환하는 방법이다. 이 방법은 수치적 오차를 줄이고 분해의 성공 가능성을 높이는 데 효과적이다.

행렬에서 피벗 요소 찾기
주어진 행렬 $\mathbf{A}$ 에 대해, $k$ 번째 단계에서 아래의 과정을 수행한다.
행렬 $\mathbf{A}$ 의 $k$ 번째 열에서 $k$ 번째 행 이후의 행들 중 가장 큰 절댓값을 가지는 요소 $a_{ik}$ 를 찾는다.
이때, $i$ 는 $k \leq i \leq n$ 을 만족한다.
행 교환
$a_{kk}$ 가 가장 큰 절댓값을 가지지 않으면, $a_{ik}$ 와 $a_{kk}$ 를 교환한다. 이 과정은 행렬 $\mathbf{A}$ 에 행렬 $\mathbf{P}$ 를 곱하는 것과 같다. $\mathbf{P}$ 는 해당 행들을 교환하는 permutation 행렬이다.
LU 분해 수행
피벗팅이 적용된 행렬에 대해 LU 분해를 수행한다. 이때, $\mathbf{P}\mathbf{A} = \mathbf{L}\mathbf{U}$ 로 나타낼 수 있다.

Partial Pivoting은 다음과 같은 알고리즘으로 요약된다:

$\text{For } k = 1 \text{ to } n-1:$

$\begin{aligned} &\text{Step 1: Pivot 요소 선택} \\ &i = \text{argmax}_{k \leq i \leq n} |a_{ik}| \\ &\text{Step 2: } \mathbf{A} \text{에서 행 } k \text{와 행 } i \text{를 교환} \\ &\text{Step 3: } \text{Forward elimination을 통해 } \mathbf{A} \text{를 } \mathbf{L}\mathbf{U} \text{로 분해} \end{aligned}$

Complete Pivoting

Complete Pivoting은 Partial Pivoting보다 더 강력한 전략으로, 각 단계에서 전체 행렬에서 가장 큰 절댓값을 가지는 요소를 찾아 그 요소가 피벗이 되도록 행과 열을 모두 교환하는 방법이다. 이 방법은 매우 높은 수치적 안정성을 제공하지만, 그만큼 계산 비용이 증가한다.

피벗 요소 선택
주어진 행렬 $\mathbf{A}$ 에 대해, $k$ 번째 단계에서 전체 하위 행렬 $\mathbf{A}[k:n, k:n]$ 에서 가장 큰 절댓값을 가지는 요소 $a_{ij}$ 를 찾는다.
행 및 열 교환
$a_{kk}$ 가 가장 큰 절댓값을 가지지 않으면, $a_{ij}$ 와 $a_{kk}$ 를 교환한다. 이 과정은 행렬 $\mathbf{A}$ 에 행렬 $\mathbf{P}$ 와 $\mathbf{Q}$ 를 곱하는 것과 같다. $\mathbf{P}$ 는 행 교환, $\mathbf{Q}$ 는 열 교환을 나타내는 permutation 행렬이다.
LU 분해 수행
피벗팅이 적용된 행렬에 대해 LU 분해를 수행한다. 이때, $\mathbf{P}\mathbf{A}\mathbf{Q} = \mathbf{L}\mathbf{U}$ 로 나타낼 수 있다.

Complete Pivoting은 다음과 같은 알고리즘으로 요약된다:

$\text{For } k = 1 \text{ to } n-1:$

$\begin{aligned} &\text{Step 1: Pivot 요소 선택} \\ &(i, j) = \text{argmax}_{k \leq i, j \leq n} |a_{ij}| \\ &\text{Step 2: } \mathbf{A} \text{에서 행 } k \text{와 행 } i \text{를 교환} \\ &\text{Step 3: } \mathbf{A} \text{에서 열 } k \text{와 열 } j \text{를 교환} \\ &\text{Step 4: } \text{Forward elimination을 통해 } \mathbf{A} \text{를 } \mathbf{L}\mathbf{U} \text{로 분해} \end{aligned}$

Partial Pivoting과 Complete Pivoting 모두 LU 분해의 수치적 안정성을 크게 향상시킬 수 있지만, Complete Pivoting은 더 높은 비용을 동반한다. 따라서, 대부분의 실용적인 문제에서는 Partial Pivoting이 더 선호된다.

Pivoting 전략의 비교

Partial Pivoting과 Complete Pivoting은 모두 수치적 안정성을 개선하는 데 중요한 역할을 한다. 그러나 두 방법은 성능 및 계산 비용 측면에서 다르다.

계산 복잡도

Partial Pivoting: 각 단계에서 열에서 최대값을 찾고, 필요한 경우 행을 교환하는 연산만 수행하므로, 연산 복잡도가 상대적으로 낮다. 일반적으로 $O(n^2)$ 의 추가 연산이 필요하다.
Complete Pivoting: 각 단계에서 하위 행렬 전체에서 최대값을 찾고, 행과 열을 모두 교환해야 하므로, 연산 복잡도가 높다. 이 과정에서 $O(n^3)$ 의 연산이 필요할 수 있다.

수치적 안정성

Partial Pivoting: 대부분의 실용적인 문제에서 충분한 수치적 안정성을 제공한다. 일부 예외적인 경우에는 안정성이 부족할 수 있지만, 대부분의 경우 LU 분해를 수행하는 데 문제가 없다.
Complete Pivoting: 최고 수준의 수치적 안정성을 제공한다. 모든 가능한 교환을 고려하므로, 가장 안정적인 피벗을 선택할 수 있다. 그러나, 이 방법은 고비용으로 인해 드물게 사용된다.

구현의 복잡성

Partial Pivoting: 구현이 상대적으로 간단하며, 대부분의 LU 분해 알고리즘에서 기본적으로 사용된다. 이는 실용적이고 효율적이기 때문에, 널리 사용되는 방법이다.
Complete Pivoting: 구현이 복잡하고, 많은 연산을 필요로 한다. 따라서, 수치적 안정성이 극도로 중요한 경우를 제외하고는 잘 사용되지 않는다.

수치적 안정성의 중요성

행렬의 피벗팅 전략을 잘못 선택하면, LU 분해 과정에서 매우 큰 수치적 오류가 발생할 수 있다. 이는 특히, 행렬의 요소들이 매우 크거나 작은 값을 가질 때, 또는 행렬이 거의 특이행렬에 가까운 경우에 중요하다. 이러한 상황에서, 작은 수치적 오차가 전체 계산 결과에 큰 영향을 미칠 수 있다.

수치적 안정성을 위한 전략을 선택할 때, 다음과 같은 요소들을 고려해야 한다:

행렬의 구조: 특정한 구조를 가지는 행렬, 예를 들어 대칭 행렬이나 희소 행렬 등은 별도의 피벗팅 전략이 필요할 수 있다.
문제의 성격: 문제의 수치적 민감성, 즉 입력값의 작은 변화가 결과에 미치는 영향이 큰 경우, 더 강력한 피벗팅 전략이 필요할 수 있다.
계산 자원: 고성능 컴퓨팅 자원이나 병렬 처리가 가능한 경우, Complete Pivoting을 사용할 여지가 늘어날 수 있다.

Pivoting의 실제 응용

Pivoting 전략은 단순히 이론적인 개념이 아니라, 실질적인 응용에서도 중요한 역할을 한다. 예를 들어, 기계학습, 금융 모델링, 물리 시뮬레이션 등 다양한 분야에서 사용되는 연립 방정식의 해법에서 LU 분해가 자주 사용되며, 이때 수치적 안정성을 확보하기 위해 Pivoting이 필수적이다.

Pivoting의 구현

Pivoting 전략은 다양한 프로그래밍 언어에서 구현할 수 있다. 여기서는 Python을 이용해 Partial Pivoting과 Complete Pivoting을 구현하는 방법을 간단히 살펴보겠다.

Partial Pivoting의 Python 구현

Python에서는 NumPy 라이브러리를 사용하여 Partial Pivoting을 쉽게 구현할 수 있다. 다음은 Partial Pivoting을 적용한 LU 분해의 간단한 구현 예이다.

import numpy as np

def partial_pivoting_lu(A):
    n = A.shape[0]
    L = np.zeros_like(A)
    U = A.copy()
    P = np.eye(n)

    for k in range(n-1):
        # Pivoting: find the row with the largest element in the current column
        max_index = np.argmax(abs(U[k:, k])) + k
        if max_index != k:
            # Swap rows in U
            U[[k, max_index], :] = U[[max_index, k], :]
            # Swap rows in P
            P[[k, max_index], :] = P[[max_index, k], :]
            # Swap rows in L (but not the current column)
            if k > 0:
                L[[k, max_index], :k] = L[[max_index, k], :k]

        # LU decomposition
        L[k+1:, k] = U[k+1:, k] / U[k, k]
        U[k+1:, :] -= np.outer(L[k+1:, k], U[k, :])

    np.fill_diagonal(L, 1)  # Diagonal elements of L are 1
    return P, L, U

A = np.array([[0, 2, 1], [1, 2, 2], [2, 0, 2]], dtype=float)
P, L, U = partial_pivoting_lu(A)

print("P:")
print(P)
print("L:")
print(L)
print("U:")
print(U)

위의 코드에서 partial_pivoting_lu 함수는 입력 행렬 $\mathbf{A}$ 에 대해 LU 분해를 수행하며, 피벗팅 행렬 $\mathbf{P}$ , 하삼각행렬 $\mathbf{L}$ , 상삼각행렬 $\mathbf{U}$ 를 반환한다. 이 함수는 Partial Pivoting을 사용하여 $\mathbf{A}$ 를 분해한다.

Complete Pivoting의 Python 구현

Complete Pivoting의 경우는 좀 더 복잡하며, 행과 열을 모두 교환하는 과정이 추가된다. 다음은 Complete Pivoting을 포함한 LU 분해의 간단한 구현 예이다.

import numpy as np

def complete_pivoting_lu(A):
    n = A.shape[0]
    L = np.zeros_like(A)
    U = A.copy()
    P = np.eye(n)
    Q = np.eye(n)

    for k in range(n-1):
        # Pivoting: find the largest element in the submatrix U[k:, k:]
        max_index = np.unravel_index(np.argmax(abs(U[k:, k:])), U[k:, k:].shape)
        max_index = (max_index[0] + k, max_index[1] + k)

        if max_index[0] != k:
            # Swap rows in U
            U[[k, max_index[0]], :] = U[[max_index[0], k], :]
            # Swap rows in P
            P[[k, max_index[0]], :] = P[[max_index[0], k], :]
            # Swap rows in L (but not the current column)
            if k > 0:
                L[[k, max_index[0]], :k] = L[[max_index[0], k], :k]

        if max_index[1] != k:
            # Swap columns in U
            U[:, [k, max_index[1]]] = U[:, [max_index[1], k]]
            # Swap columns in Q
            Q[:, [k, max_index[1]]] = Q[:, [max_index[1], k]]

        # LU decomposition
        L[k+1:, k] = U[k+1:, k] / U[k, k]
        U[k+1:, :] -= np.outer(L[k+1:, k], U[k, :])

    np.fill_diagonal(L, 1)  # Diagonal elements of L are 1
    return P, L, U, Q

A = np.array([[0, 2, 1], [1, 2, 2], [2, 0, 2]], dtype=float)
P, L, U, Q = complete_pivoting_lu(A)

print("P:")
print(P)
print("L:")
print(L)
print("U:")
print(U)
print("Q:")
print(Q)

위의 코드에서 complete_pivoting_lu 함수는 Partial Pivoting과 유사하게 동작하지만, 피벗팅을 위해 행과 열을 모두 교환한다. 이 함수는 행렬 $\mathbf{A}$ 에 대해 Complete Pivoting을 사용하여 LU 분해를 수행하고, 피벗팅 행렬 $\mathbf{P}$ , $\mathbf{Q}$ , 하삼각행렬 $\mathbf{L}$ , 상삼각행렬 $\mathbf{U}$ 를 반환한다.

실용적 고려사항

실제 응용에서 Partial Pivoting은 대부분의 상황에서 충분히 안정적이므로 자주 사용된다. Complete Pivoting은 그만큼의 안정성이 요구되는 경우에만 사용되며, 주로 매우 민감한 계산을 수행할 때 선택된다.