Pivot element

Original article: w:Pivot element

This article is about pivots in matrices. For the pivot in the quicksort algorithm, see Quicksort.

피벗(pivot) 또는 피벗 원소(pivot element)는 특정 계산을 수행하기 위해 알고리듬 (예를 들어, 가우스 소거법(Gaussian elimination), 심플렉스 알고리듬(simplex algorithm), 등)에 의해 첫 번째로 선택된 행렬(matrix), 또는 배열(array)의 원소입니다. 행렬 알고리듬의 경우에서, 피벗 엔트리는 보통 적어도 영과 구별되는 것이 요구되고, 종종 그것에서 멀리 떨어져 있습니다; 이 경우에서, 이 원소를 찾는 것은 피벗팅(pivoting)이라고 불립니다. 피벗팅은 행 또는 열의 교환에 의해 피벗을 고정된 위치로 가져오고 알고리듬이 연속적으로 진행될 수 있고, 아마도 반-올림 오차를 줄일 수 있습니다. 그것은 종종 행 사다리꼴 형식(row echelon form)을 확인하기 위해 사용됩니다.

피벗팅은 행렬에서 행 또는 열을 교환 또는 정렬하는 것으로 생각될 수 있고, 따라서 순열 행렬(permutation matrices)에 의한 곱셈(multiplication)으로 나타낼 수 있습니다. 어쨌든, 알고리듬은 행렬 원소를 거의 이동하지 않는데 왜냐하면 이것은 시간이 오래 걸리기 때문입니다; 대신에, 그것들은 단지 순열의 선로를 유지합니다.

전반적으로, 피벗팅은 알고리듬의 계산 비용에 더 많은 연산을 추가합니다. 이들 추가적 연산은 때때로 알고리듬이 작동하기 위해 필요합니다. 다른 시간에 이들 추가 연산은 그것들이 최종 결과에 수치적 안정성(numerical stability)을 추가하기 때문에 가치가 있습니다.

Examples of systems that require pivoting

가우스 소거법의 경우에서, 알고리듬은 피벗 원소가 영이 아니어야 합니다. 영 피벗 원소의 경우에서 행 또는 열을 교환해야 합니다. 아래 시스템은 소거를 수행하기 위해 행 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]$

게다가, 가우스 소거법에서, 절댓값(absolute value)이 큰 피벗 원소를 선택하는 것이 일반적으로 바람직합니다. 이것은 수치적 안정성(numerical stability)을 향상시킵니다. 다음 시스템은 가우스 소거법과 역 대입을 수행할 때 반올림 오차에 의해 크게 영향을 받습니다.

$\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의 정확한 해를 가지지만, 소거 알고리듬과 네-자릿수 산술을 사용하여 역 대입을 수행할 때 a₁₁의 작은 값으로 인해 작은 반올림 오차가 전파됩니다. 피벗 없이 알고리듬은 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].$

이 시스템을 고려하면, 소거 알고리듬과 네-자릿수 산술을 사용한 역 대입은 올바른 값 x₁ = 10.00와 x₂ = 1.000을 산출합니다.

Partial, rook, and complete pivoting

부분 피벗팅(partial pivoting)에서, 알고리듬은 현재 피벗 원소로 고려되는 행렬의 열에서 절댓값이 가장 큰 엔트리를 선택합니다. 보다 구체적으로, 행렬을 행 사다리꼴 형식으로 축소할 때, 부분 피벗팅은 열의 행 축소 전에 행을 교체하여 피벗 원소가 같은 열의 아래 원소에 비해 가장 큰 절댓값을 갖도록 합니다. 부분 피벗팅은 일반적으로 반올림 오차를 적절히 줄이기 위해 충분합니다.

어쨌든, 특정 시스템과 알고리듬에 대해, 완전한 피벗팅(complete pivoting 또는 최대 피벗팅(maximal pivoting))이 허용-가능한 정확도에 대해 요구될 수 있습니다. 완전한 피벗팅은 피벗으로 행렬에서 가장 큰 (절댓값 기준) 원소를 사용하기 위해 행과 열을 모두 교환합니다. 완전한 피벗팅은 보통 수치적 안정성을 보장하기 위해 필요하지 않고, 최대 원소를 검색하는 추가 비용으로 인해, 그것이 제공하는 수치적 안정성의 개선은 전형적으로 가장 작은 행렬을 제외한 모든 행렬에 대한 효율성 감소보다 더 큽니다. 따라서, 그것은 거의 사용되지 않습니다.

루크 피벗팅(rook pivoting)으로 알려진 또 다른 전략은 행과 열을 모두 교환하지만 선택된 피벗이 전체 남아있는 부분행렬에서 가능한 가장 큰 것과는 반대로 행에서 가장 큰 가능한 엔트리와 열에서 가장 큰 가능한 엔트리임을 동시에 보장합니다. 직렬 컴퓨터에서 구현될 때 이 전략은 부분 피벗팅의 약 3배 정도의 비용만 예상되고 따라서 완전한 피벗팅보다 저렴합니다. 루크 피벗팅은 이론적으로나 실제적으로 부분 피벗팅보다 더 안정적인 것으로 입증되었습니다.

Scaled pivoting

부분 피벗팅 전략의 변형은 스케일된 피벗팅입니다. 이 접근 방식에서, 알고리듬은 해당 행에서 엔트리에 비해 가장 큰 엔터리를 피벗 원소로 선택합니다. 이 전략은 엔트리의 크기 차이가 커서 반올림 오차가 전파될 때 바람직합니다. 스케일된 피벗팅은 행 엔트리의 크기가 크게 다른 아래와 같은 시스템에서 사용되어야 합니다. 아래 예제에서, 현재 피벗 원소 30은 5.291보다 크지만 해당 행의 다른 엔트리에 비해 상대적으로 작기 때문에 두 행을 교환하는 것이 바람직합니다. 이 경우에서 행 교환 없이, 이전 예제에서와 같이 반올림 오차가 전파됩니다:

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

Pivot position

행렬, A의 피벗 위치는 A의 감소된 행 사다리꼴 형식(reduced row echelon form)에서 행-선행되는 1에 해당하는 행렬의 위치입니다. A의 감소된 행 사다리꼴 형식은 고유하므로, 피벗 위치는 고유하게 결정되고 축소 프로세스에서 행 교환이 수행되는지 여부에 의존하지 않습니다. 역시, 행의 피벗은 행 사다리꼴 형식(row echelon form)으로 위 행의 피벗 오른쪽에 나타나야 합니다.

References

This article incorporates material from Pivoting on PlanetMath, which is licensed under the Creative Commons Attribution/Share-Alike License.

• R. L. Burden, J. D. Faires, Numerical Analysis, 8th edition, Thomson Brooks/Cole, 2005. ISBN 0-534-39200-8
• G. H. Golub, C. F. Loan, Matrix Computations, 3rd edition, Johns Hopkins, 1996. ISBN 0-8018-5414-8.
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming, Series B. Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997. 79 (1–3): 369–395. CiteSeerX 10.1.1.36.9373. doi:10.1007/BF02614325. MR 1464775. S2CID 2794181. Postscript preprint.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. Degeneracy in optimization problems. 46–47 (1): 203–233. CiteSeerX 10.1.1.36.7658. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. S2CID 6058077.