피벗 요소

피벗 또는 피벗 요소는 행렬의 요소 또는 배열로, 특정 계산을 위해 알고리즘(예: 가우스 제거, 심플렉스 알고리즘 등)에 의해 먼저 선택된다.매트릭스 알고리즘의 경우, 피벗 항목은 적어도 0과 구별되어야 하며 종종 그것으로부터 멀어야 한다. 이 경우 이 요소를 찾는 것을 피벗이라고 한다.피벗을 고정된 위치로 가져오고 알고리즘이 성공적으로 진행되도록 하기 위해, 그리고 반올림 오류를 줄이기 위해 피벗을 행 또는 열의 교환이 뒤따를 수 있다.이것은 종종 행 에셀론 형태를 확인하는 데 사용된다.

피벗은 행렬의 행이나 열을 스와핑하거나 정렬하는 것으로 생각할 수 있으며, 따라서 순열 매트릭스에 의해 곱셈으로 나타낼 수 있다.그러나 알고리즘은 매트릭스 요소를 거의 움직이지 않는다. 왜냐하면 이것은 너무 많은 시간이 소요되기 때문이다. 대신, 그들은 순열만 추적한다.

전체적으로 피벗은 알고리즘의 계산 비용에 더 많은 연산을 추가한다.이러한 추가 연산은 알고리즘이 전혀 작동하기 위해 필요한 경우가 있다.다른 경우에 이러한 추가 연산은 최종 결과에 수치적 안정성을 더하기 때문에 가치가 있다.

피벗이 필요한 시스템의 예

가우스 소거의 경우, 알고리즘은 피벗 요소가 0이 아니어야 한다.제로 피벗 요소의 경우 행 또는 열을 상호 교환해야 한다.아래 시스템은 제거를 수행하기 위해 2열과 3열의 교체가 필요하다.

${\displaystyle \left[{\put{array}{ccc c}1&-1&2&8\\0&#1&-11\\0&#1&#3\end{array}\오른쪽]}$

선회 결과 발생하는 시스템은 다음과 같으며, 제거 알고리즘과 역방향 치환을 통해 시스템에 솔루션을 출력할 수 있다.

${\displaystyle \left[{\put{array}{ccc c}1&-1&2&8\\0&-1&#3\0&#1&-11\end{array}\오른쪽]}$

나아가 가우스 제거에서는 일반적으로 절대값이 큰 피벗 요소를 선택하는 것이 바람직하다.이것은 수학적 안정성을 향상시킨다.다음 시스템은 가우스 제거 및 후방 치환 수행 시 반올림 오류의 영향을 크게 받는다.

${\displaystyle \left[{\put{array}{cc c}0.00300&59.14&59.17\\5.291&-6.130&46.78\\\end{array}\오른쪽]}$

이 시스템은 x₁ = 10.00, x₂ = 1.000의 정확한 용액을 가지고 있지만, 제거 알고리즘과 역방향 치환법을 네 자리 산술로 수행할 때 a의₁₁ 작은 값이 작은 반올림 오차를 전파한다.선회하지 않은 알고리즘은 x₁ ≈ 9873.3 및₂ x ≈ 4의 근사치를 산출한다.이 경우 a가₂₁ 피벗 위치에 있도록 두 행을 교환하는 것이 바람직하다.

${\displaystyle \left[{\put{array}{cc c}5.291&-6.130&46.78\\0.00300&59.14&59.17\\\end{array}\오른쪽).}$

이 시스템을 고려할 때 네 자리 산수를 사용한 소거 알고리즘과 후방 치환에서는 정확한 값이₁ x = 10.00, x = 1.000이다₂.

부분, 루크 및 전체 피벗

부분 피벗에서 알고리즘은 현재 피벗 요소로 간주되고 있는 매트릭스 컬럼에서 가장 큰 절대값을 가진 항목을 선택한다.부분 회전은 일반적으로 반올림 오차를 적절히 줄이기에 충분하다.그러나 특정 시스템과 알고리즘의 경우 허용 가능한 정확도를 위해 완전한 선회(또는 최대 선회)가 필요할 수 있다.전체 피벗은 행렬에서 가장 큰(절대값 기준) 요소를 피벗으로 사용하기 위해 행과 열의 상호 교환을 모두 수행한다.완전한 선회란 일반적으로 수학적 안정성을 보장하기 위해 필요하지 않으며, 최대 요소 검색의 추가 비용 때문에, 그것이 제공하는 수학적 안정성의 개선은 일반적으로 가장 작은 행렬을 제외한 모든 행렬에 대한 감소된 효율보다 더 크다.따라서 거의 사용되지 않는다.^[1]루크 피벗으로 알려진 또 다른 전략은 행과 열을 모두 바꾸지만, 선택한 피벗이 전체 하위 계층에서 가능한 최대 항목과 컬럼에서 가능한 최대 항목이라는 것만을 보장한다.^[2]직렬 컴퓨터에 구현될 때 이 전략은 부분 선회 비용의 약 3배만 예상했으며 따라서 완전한 선회보다 비용이 저렴하다.루크 피벗은 이론적으로나 실제적으로나 부분 피벗보다 더 안정적이라는 것이 증명되었다.

축척 피벗

부분 선회 전략의 변화는 선회한다.이 접근법에서 알고리즘은 피벗 요소로 행의 항목과 관련하여 가장 큰 항목을 선택한다.이 전략은 항목의 크기 차이가 반올림 오류의 전파를 초래할 때 바람직하다.축척 피벗은 행의 입력이 크기가 큰 아래 시스템과 같은 시스템에 사용해야 한다.아래 예에서 현재 피벗 요소 30은 5.291보다 크지만 행의 다른 항목과 비교하여 상대적으로 작기 때문에 두 행을 교환하는 것이 바람직하다.이 경우 행 교환이 없으면 이전 예와 같이 반올림 오류가 전파된다.

${\displaystyle \left[{\put}{array}{cc c}30&591400&591700\\5.291&-6.130&46.78\\end{array}\오른쪽]}$

피벗 위치

행렬의 피벗 위치 A는 A의 축소된 행 에셀론 형태의 행 선도 1에 해당하는 행렬의 위치다.A의 축소된 행 에셀론 형태가 고유하기 때문에 피벗 위치가 고유하게 결정되며, 축소 과정에서 행 상호 교환이 수행되는지 여부에 따라 달라지지 않는다.또한 행의 피벗은 위 행의 피벗 오른쪽에 행 에셀론 형식으로 나타나야 한다.

참조

이 글에는 Creative Commons Attribution/Share-Alike License에 따라 라이센스가 부여된 Pivoting on PlanetMath의 자료가 통합되어 있다.

• R. L. 짐, J. D.Fagers, 수치 분석, 제8판 Thomson Brooks/Cole, 2005.ISBN 0-534-39200-8
• G. H. Golub, C. F. Loan, Matrix Computations, 제3판, 존스 홉킨스, 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.