피벗

3. 피벗팅의 종류

행렬 알고리즘에서 피벗 성분은 일반적으로 0이 아니어야 하며, 1이 사용되는 경우가 많지만 1이 아닌 값도 가능하다. 이러한 성분을 찾는 것을 피벗팅(pivoting)이라고 한다. 피벗팅은 선택된 성분을 나눗셈 등의 연산에 사용하여 피벗을 고정된 위치에 놓고(재정렬), 알고리즘이 성공적으로 진행될 수 있도록 행이나 열을 교환(스와핑)하여 반올림 오류를 줄일 수 있다.^[3] 피벗팅은 에셜론행렬을 확인하는 데에도 종종 사용된다.

피벗은 행렬의 행 또는 열을 스와핑하거나 재정렬하는 것으로 볼 수 있으며, 순열 행렬을 이용한 행렬곱셈으로 나타낼 수 있다. 그러나 행렬 성분을 거의 이동하지 않는 알고리즘에서는 이 과정이 시간을 지체시킬 수 있다.

전반적으로 피벗팅은 알고리즘의 시간복잡도에 더 많은 연산을 추가한다. 이러한 추가 작업은 알고리즘이 작동하기 위해 때때로 필요하며, 최종 결과의 수치 안정성을 높이기 때문에 시간상으로도 가치가 있다.

부분 피벗팅 전략의 변형으로 스케일링 피벗팅이 있다. 이 방식에서는 행 내 항목들에 비해 상대적으로 가장 큰 항목을 피벗 요소로 선택한다. 이 전략은 항목의 크기가 크게 다를 때 반올림 오류가 전파되는 것을 막는 데 유용하다. 스케일링 피벗팅은 아래와 같이 행의 항목 크기가 크게 변동하는 시스템에서 사용해야 한다.

:$$

\left[ \begin{array}{cc|c}

30 & 591400 & 591700 \\

5.291 & -6.130 & 46.78 \\

\end{array} \right]



위의 예시에서는 현재 피벗 요소 30이 5.291보다 크지만, 해당 행의 다른 항목에 비해 상대적으로 작기 때문에 두 행을 교환하는 것이 바람직하다. 이 경우 행을 교환하지 않으면 반올림 오류가 전파될 수 있다.

3. 1. 부분 피벗팅 (Partial Pivoting)

3. 2. 완전 피벗팅 (Complete Pivoting)

3. 3. 룩 피벗팅 (Rook Pivoting)

3. 4. 스케일링 피벗팅 (Scaled Pivoting)

4. 피벗 위치 (Pivot Position)

행렬 A에서 피벗 위치는 A의 기약행 사다리꼴에서 행의 선두 1에 해당하는 행렬 내 위치이다. A의 기약행 사다리꼴은 유일하므로, 피벗 위치는 고유하게 결정되며, 행 감소 과정에서 행 교환을 수행했는지 여부와 관계없이 결정된다. 또한, 행 사다리꼴에서 행의 피벗은 위의 행의 피벗 오른쪽에 나타나야 한다.^[1]

5. 예제

가우스 소거법에서 피벗 요소는 0이 아니어야 한다. 만약 피벗 요소가 0이면 행이나 열을 교환해야 한다. 아래 예시는 소거를 위해 2행과 3행을 교환해야 하는 경우이다.

:$$

\left[ \begin{array}{ccc|c}

1 & -1 & 2 & 8 \\

0 & 0 & -1 & -11 \\

0 & 2 & -1 & -3

\end{array} \right]



피벗팅을 통해 다음과 같은 시스템을 얻을 수 있다. 이를 통해 소거 알고리즘과 후방 대입을 사용하여 해를 구할 수 있다.

:$$

\left[ \begin{array}{ccc|c}

1 & -1 & 2 & 8 \\

0 & 2 & -1 & -3 \\

0 & 0 & -1 & -11

\end{array} \right]



가우스 소거법에서는 일반적으로 절댓값이 큰 피벗 요소를 선택하는 것이 좋다. 이는 수치적 안정성을 높여준다. 다음 시스템은 반올림 오차에 큰 영향을 받는다.

:$$

\left[ \begin{array}{cc|c}

0.00300 & 59.14 & 59.17 \\

5.291 & -6.130 & 46.78 \\

\end{array} \right]



이 시스템의 정확한 해는 ''x''₁ = 10.00, ''x''₂ = 1.000이다. 하지만 4자리 산술을 사용하여 소거 알고리즘과 후방 대입을 수행하면 작은 반올림 오차가 전파된다. 피벗팅을 사용하지 않으면 ''x''₁ ≈ 9873.3, ''x''₂ ≈ 4와 같은 근사값을 얻게 된다. 따라서 두 행을 교환하여 ''a''₂₁이 피벗 위치에 오도록 하는 것이 좋다.

:$$

\left[ \begin{array}{cc|c}

5.291 & -6.130 & 46.78 \\

0.00300 & 59.14 & 59.17 \\

\end{array} \right]



이 시스템에 4자리 산술을 적용하면 정확한 해 ''x''₁ = 10.00, ''x''₂ = 1.000을 얻을 수 있다.

6. 시간 복잡도

행렬 알고리즘에서 피벗 엔트리(성분)는 일반적으로 적어도 0이 아니어야 하며, 종종 1이 사용되지만 1이 아닌 값도 가능하다. 이 경우 이러한 성분을 찾는 것을 피벗팅(pivoting)이라고 한다. 피벗팅은 선택된 성분이 나눗셈 등의 연산에 의해 피벗이 고정된 위치에 있게 하고(재정렬), 알고리즘이 성공적으로 진행될 수 있도록 행 또는 열을 교환(스와핑)함으로써 반올림 오류를 줄일 수도 있다.^[3] 이것은 종종 에셜론행렬을 확인하는 데 사용된다.

피벗은 행렬의 행 또는 열을 스와핑하거나 재정렬하는 것으로 생각할 수 있으며, 따라서 순열 행렬에 의한 행렬곱셈으로 나타낼 수 있다. 그러나 이러한 알고리즘은 행렬 성분을 거의 이동하지 않으므로 시간이 지체될 수 있다.

전반적으로 피벗팅은 알고리즘의 시간복잡도에 더 많은 연산을 추가하게 된다. 이러한 추가 작업은 알고리즘이 작동하기 위해 때로는 필요하다. 시간상에도 불구하고 이러한 추가 작업은 최종 결과에 수치 안정성을 높이기 때문에 가치가 있다.

참조

_[1] 논문 The Complete Pivoting Conjecture for Gaussian Elimination is False. http://www-math.mit.[...] 1992
_[2] 간행물 The Rook's Pivoting Strategy 2000-11
_[3] 서적 An Introduction to Numerical Methods A MATLAB Approach 학산미디어 2013