Pivoting

Motivation of Pivoting

가우스 소거법과, 가우스-조르당 방법에서 대각행렬을 기준으로 수행한다는 것은 명백하다.

우리는 그래서 이 대각 행렬의 요소를 Pivot 이라 부른다. Pivoting 이란, 행렬이 있을때, 이 Pivot을 기준으로 행을 판단해서 두 행을 바꿔 계산하는 방법을 말한다.

그렇다면 이 Pivoting은 왜 필요한 것일까?

우리는 행렬을 계산하는데 있어 Computing Method를 사용하는데, 현실의 값을 근사해서 매핑하는 컴퓨터의 한계 때문에,

우리는 Round Off Error 를 필연적으로 가질 수 밖에 없다. 이 에러를 줄이기 위해 우리는 Pivoting을 한다.

예제를 살펴보자.

$$\left[\begin{array}{cc}0.003& 59.14\\ 5.291& -6.130\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}59.17\\ 46.78\end{array}\right]$$

이 식의 정확한 값은,

$$\begin{gathered} ExactSolution \\ \left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}10.00\\ 1.0\end{array}\right] \end{gathered}$$

가우스 소거법을 사용해서 위 식을 계산해보자. 우리는 대각 요소를 1로 만드는 것에 관심이 있기 때문에, 1행 1열의 값을, 2행 1열의 값과 같게 만든뒤 빼줘야 한다.

그러기 위해서

$$\frac{a_{11}}{a_{21}}=\frac{0.003}{5.291}=1763.66\cdots$$

이 값을 1행에 곱하고 2행을 더한 행을 2행과 바꿔주자. 결과 식은,

$$\left[\begin{array}{cc}0.003& 59.14\\ 0& -104300\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}59.17\\ -104400\end{array}\right]$$

이 때 계산된 해는,

$$\begin{gathered} ApproximatedSolution \\ \left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}-10.00\\ 1.001\end{array}\right] \end{gathered}$$

다음과 같이 현저히 다른 해가 도출된다. 결국 우리는 대각 요소의 값과 밑의 행이 비율이 큰 것을 피하면 된다!

$$m_{jk}=\frac{a_{jk}}{a_{kk}}>>1$$

j는 행의 번호를 말하고, k는 대각 요소의 행번호를 의미한다.

우리는 이 값이 1보다 클경우 Round Off 에러가 발생한다는 것을 알았으므로 이것을 막으면 된다.

Remedy

1. Partial Pivoting
2. Scaled Pivoting

Partial Pivoting

가장 간단한 방법은, 저 값이 1보다 훨씬 클경우 아래 행과 위의 행을 바꾸는 것이다!

$$|a_{pk}|=Loop(k\le i\le n)max|a_{ik}|$$

k는 현재 있는 행을 의미한다. n은 마지막 행을 의미한다.

그 사이에 있는 i 라는 값을 가지면서 각 행의 요소들을 조사하면서 가장 큰 값을 리턴한다. 이때, 행의 index를 저장하고, 만약 해당 행의 대각 요소의 값이 가장 크다면 p = k 가 될 것이다.

만약 그렇지 않다면 p != k 일 것이다. 이 경우 p 행과 k 행을 Pivoting 한다.

그렇게 되면 필연적으로 m_jk 값은 1보다 작아지므로 Round Off Error 를 피할 수 있다.

적용

$$\left[\begin{array}{cc}5.291& -6.130\\ 0.003& 59.14\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}46.78\\ 59.17\end{array}\right]$$ $$m_{jk}=m_{21}=\frac{a_{21}}{a_{11}}=\frac{5.291}{0.003}=0.000567$$ $$\left[\begin{array}{cc}5.291& -6.130\\ 0& 59.14\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}46.78\\ 59.14\end{array}\right]$$ $$\begin{gathered} ApproximatedSolution \\ \left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}10.00\\ 1\end{array}\right] \end{gathered}$$

Scaled Pivoting

만약 m 값이 1에서 크게 차이가 없다면 이 방법은 사실의미가 없다.

따라서 이 경우에는 각 행에 특정 같은 값을 곱한뒤, 답을 구하는 방법을 사용해야 한다.

가우스 소거법의 특성상, 밑의 값부터 올라오기 때문에, 특정 행의 계수들의 크기가 균등하다면 값의 변화가 크다.

따라서 우리는 행의 계수들의 비율이 큰 행을 아래로 피보팅 해야한다.

$$\left[\begin{array}{cc}30& 591400\\ 5.291& -6.130\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}591700\\ 46.78\end{array}\right]$$ $$\begin{gathered} S_1=max[|30|,|591400|]=591400 \\ {S}_2=max[|5.291|,|-6.130|]=6.130 \end{gathered}$$ $$\begin{gathered} \frac{|a_{11}|}{S_1}=\frac{30}{591400}=0.5073\times 10^{-4} \\ \frac{|a_{21}|}{S_2}=\frac{5.291}{6.130}=0.8631 \end{gathered}$$

따라서 1행과 2행을 피보팅한다.

$$\left[\begin{array}{cc}5.291& -6.130\\ 30& 591400\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{c}46.78\\ 591700\end{array}\right]$$