가우스 소거

수학에서, 행 감소라고도 알려진 가우스 제거는 선형 방정식의 시스템을 풀기 위한 알고리즘입니다.이는 해당 계수 행렬에 대해 수행되는 일련의 연산으로 구성됩니다.이 방법은 행렬의 순위, 정사각형 행렬의 행렬식 및 역행렬의 역행렬을 계산하는 데도 사용할 수 있습니다.이 방법은 비록 증거 없이 제시되었지만, 중국의 수학자들에게는 ^[1]179년 경에 이미 알려져 있었지만, 칼 프리드리히 가우스(1777–1855)의 이름을 따서 명명되었다.

행렬에서 행 축소를 수행하려면 행렬의 왼쪽 하단 모서리가 가능한 한 0으로 채워질 때까지 일련의 기본 행 연산을 사용하여 행렬을 수정합니다.기본 행 연산에는 다음 세 가지 유형이 있습니다.

• 두 행을 바꿉니다.
• 행에 0이 아닌 숫자를 곱하면
• 한 행의 배수를 다른 행에 추가(한 행에 -1을 곱한 후 결과를 다른 행에 추가하면 감산 가능)

이러한 연산을 사용하면 행렬은 항상 위쪽 삼각 행렬로 변환될 수 있으며, 실제로는 행 형태로 변환됩니다.모든 선행 계수(각 행에서 가장 왼쪽이 0이 아닌 항목)가 1이고 선행 계수가 들어 있는 모든 열에 0이 있으면 행렬이 축소된 행 형식이라고 합니다.이 최종 형식은 고유합니다.즉, 사용되는 행 연산 순서와는 무관합니다.예를 들어 다음 행 연산 시퀀스(다른 행의 두 기본 연산이 첫 번째 및 세 번째 단계에서 수행됨)에서 세 번째 및 네 번째 행렬은 행 echelon 형식의 행렬이며, 마지막 행렬은 고유한 축소 행 echelon 형식입니다.

${\displaystyle{\begin{bmatrix}1&, 3&, 1&, 9\\1&, 1&, -1&, 1\\3&, 11&, 5&, 35\end{bmatrix}}\to{\begin{bmatrix}1&, 3&, 1&, 9\\0&, -2&, -2&, -8\\0&, 2&, 2&, 8\end{bmatrix}}\to{\begin{bmatrix}1&, 3&, 1&, 9\\0&, -2&, -2&, -8\\0&, 0&, 0&, 0\end{bmatrix}}\to{\begin{bmatrix}1&, 0&, -2&, -3\\0&.앰프, 1&, 1&, 4\\0&, 0&, 0&, 0\end{bmatrix}}}$

행 연산을 사용하여 행렬을 축소행 echelon 형식으로 변환하는 것을 가우스-요르단 제거라고 부르기도 합니다.이 경우, 가우스 제거라는 용어는 상부 삼각형 또는 (감소되지 않은) 행 에켈론 형태에 도달할 때까지의 프로세스를 말합니다.계산상의 이유로 선형 방정식의 시스템을 풀 때 행렬이 완전히 감소하기 전에 행 연산을 중지하는 것이 더 바람직할 수 있습니다.

알고리즘의 정의와 예시

행 축소 프로세스는 기본 행 연산을 사용하며 두 부분으로 나눌 수 있습니다.첫 번째 부분(전진 제거라고도 함)은 주어진 시스템을 로우 echelon 형식으로 축소하여 솔루션이 없는지, 고유한 솔루션이 없는지, 무한히 많은지 구분할 수 있습니다.두 번째 부분(백 치환이라고도 함)은 솔루션을 찾을 때까지 행 연산을 계속 사용합니다. 즉, 행렬을 축소된 행 echelon 형식으로 만듭니다.

알고리즘 분석에 매우 유용한 또 다른 관점은 행 축소가 원래 행렬의 행렬 분해를 발생시킨다는 것입니다.기본행 연산은 기본행렬에 의한 원래 행렬의 왼쪽에 있는 곱셈으로 볼 수 있습니다.또는 단일 행을 감소시키는 일련의 기본 연산은 프로베니우스 행렬에 의해 곱셈으로 간주될 수 있다.다음으로 알고리즘의 첫 번째 부분은 LU 분해를 계산하고 두 번째 부분은 고유하게 결정된 가역행렬과 고유하게 결정된 환원행렬 행렬의 곱으로 원래의 행렬을 쓴다.

행 조작

행렬의 행에 대해 수행할 수 있는 세 가지 유형의 기본 행 연산이 있습니다.

1. 두 줄의 위치를 바꿉니다.
2. 행에 0이 아닌 스칼라를 곱합니다.
3. 한 행에 다른 행의 스칼라 배수를 추가합니다.

행렬이 선형 방정식 시스템에 연결되어 있는 경우 이러한 연산을 수행해도 솔루션 집합은 변경되지 않습니다.따라서 선형 방정식의 시스템을 푸는 것이 목표라면 이러한 행 연산을 사용하면 문제를 더 쉽게 만들 수 있습니다.

에셜론 형식

행렬의 각 행에 대해 행이 0으로만 구성되어 있지 않은 경우 맨 왼쪽에 있는 비제로 엔트리를 해당 행의 선행 계수(또는 피벗)라고 합니다.따라서 두 선행 계수가 동일한 열에 있으면 유형 3의 행 연산을 사용하여 계수 중 하나를 0으로 만들 수 있습니다.그런 다음 행 스왑 작업을 사용하면 0이 아닌 모든 행에 대해 선행 계수가 위의 행의 선행 계수의 오른쪽에 오도록 항상 행 순서를 지정할 수 있습니다.이 경우 행렬은 행 형식이라고 합니다.따라서 행렬의 왼쪽 하단에는 0만 포함되며 모든 0 행은 0이 아닌 행 아래에 있습니다.여기서 "에셜론"이라는 단어를 사용하는 이유는 가장 큰 행은 맨 위에 있고 가장 작은 행은 맨 아래에 있는 행의 크기에 따라 순위가 매겨진다고 대략적으로 생각할 수 있기 때문입니다.

예를 들어, 다음 행렬은 행 echelon 형식이며 선행 계수는 빨간색으로 표시됩니다.

${\displaystyle {bmatrix} 0&\color {red} {\mathbf {2}&1&-1\0&0&\color {red} {\mathbf {3}}&1&0&0&\end {bmatrix}}.}$

이 값은 0 행이 맨 아래에 있고 두 번째 행(세 번째 열)의 선행 계수가 첫 번째 행(두 번째 열)의 선행 계수의 오른쪽에 있으므로 echelon 형식입니다.

행렬은 더 나아가 모든 선행 계수가 1과 같고(타입 2의 초등 행 연산을 사용하여 달성될 수 있음), 그리고 선행 계수를 포함하는 모든 열에서, 그 열의 다른 모든 엔트리는 0이다(이것은 다음의 초등 행 연산을 사용하여 달성될 수 있음).타입 3)을 선택합니다.

알고리즘의 예

다음과 같은 선형 방정식 시스템에 대한 해 집합을 찾아 설명하는 것이 목표라고 가정합니다.

$({displaystyle {arginedat} {4} 2x&{} + {} - {} - {} - {} - {} & \ qquad ( L_ {1} ) \ 3x & { { } - { } + 2z & { } = { } & 11 & { \ qad ( L _ 2 } )$

아래 표는 방정식 체계와 그와 관련된 증강 행렬에 동시에 적용되는 행 축소 공정이다.실제로는 방정식의 관점에서 시스템을 다루는 것이 아니라 컴퓨터 조작에 더 적합한 증강 행렬을 사용합니다.행 축소 절차는 다음과 같이 요약할 수 있습니다. L 아래의₁ 모든 방정식에서 x를 제거하고 L 아래의₂ 모든 방정식에서 y를 제거합니다.이렇게 하면 시스템이 삼각형 형태가 됩니다.그 후, 백 치환을 사용하면, 불명확한 각각의 문제를 해결할 수 있습니다.

방정식 체계	행 조작	증강 매트릭스
${\displaystyle {negratedat} {4x&{} + {} & y&{} - {} = {8} &\ 3x & {} - {} & y& {} + {} = {} - 11 & \ 2x & {} + { } & { { } & { = { } & { } & { {\ {\&& {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ {\ 、 { \ \ \ \ \ \ \ \ \ \ \ \ \ 2x & { { { }$		$\displaystyle \left[{\display{array}{rrr r}2&1&8\-3&1&11\-2&3\end{array}\right]$
${\displaystyle {arginedat} {4} 2x&{}&{}&{}-{}-{}={}&\\\tfrac {1}+{2}&{\tfrac {1}+{2}&{}z&{}&{}&{\tfrac {1}&{1&{}&{\tfrac {}&{}&{}&{}&{}&{}&{}&{}&{}&{}&{\f}&{}$	$디스플레이 스타일L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end {aligned}}$	$\displaystyle \left[{\display {rr r}2&1&8\0&{\frac {1}{2}}&{\frac {1}{{1}}&1&5\end {array}}\right}}$
${\displaystyle {negratedat} {4} 2x&{}&{}&{}-{}-{}={}&\\\tfrac {1}+{2}&{}&{\tfrac {1}+{1}&{1}={1}&{1}&{}&{}&\tfrac {1}&{}&{}&{}&{}&{}&{}&{}}&{}}}&{\\\\\\cl}}}}}&\\\\\clashyledisterfrac{\\$	${\displaystyle L_{3}+-4L_{2}\to L_{3}}$	$\displaystyle \left[{\display {rr r}2&1&8\0&{\frac {1}{2}}&{\frac {1}{1}}&1&1&1\end {array}\right}$
행렬이 이제 에켈론 형식(삼각형 형식이라고도 함)입니다.
${\displaystyle {\tfrac {1} {2} {\displaystyle {4}2x&{}+{}={y&{\tfrac {1}{2}}{\tfrac {3}{2}}&\&{}-{1}={1\end}}} 정렬$	$디스플레이 스타일L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\\L_{1}-L_{3}&\to L_{1}\end {aligned}}$	$\displaystyle \left[{\display{rr r}2&0&7\0&{\frac {1}{2}}&{\frac {3}{\0&1&1\end {array}}\right}}$
$({displaystyle {arginedat} {4} 2x&{} + {} = {} & \ \ \ \ \ y & \ pargined & { } = { } & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ exampled { alignedat } = { } & 1 & \ \ }$	$\displaystyleL_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end {aligned}}$	$\displaystyle \left[{\display{array}{rr r}2&0&7\\0&1&3\0&1&1\end{array}\right]}$
${\displaystyle {4}x&\display &\display &\display &\display &\display &\display &\display &\display &\display &\y&{}={}&\display &\display &\d {aligned at}$	$디스플레이 스타일L_{1}-L_{2}&\to L_{1}\{\tfrac {1}{2}}L_{1}&\to L_{1}\end {aligned}}$	$\displaystyle \left[{\display{array}{rr r}1&0&2\\0&1&3\0&1&1\end{array}}\right]}$

두 번째 열에는 방금 수행된 행 작업이 설명되어 있습니다.그래서 첫번째 단계에서, xL2에서.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .den{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-를 첨가하여 제거된다.L2에 Parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}3/2L1.다음으로,)L3에서 L3에 L1를 추가함으로써 제거된다.이러한 행 조작은 표에서 다음과 같이 라벨이 붙어 있습니다.

$디스플레이 스타일L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\L_{3}+L_{1}&\to L_{3}.\end { aligned}}$

세 번째 행에서 y를 제거하면 삼각형 형태의 선형 방정식 시스템이 생성되므로 알고리즘의 첫 번째 부분이 완성됩니다.계산의 관점에서 보면 역순으로 변수를 해결하는 것이 더 빠릅니다. 역치환이라고 하는 프로세스입니다.해답은 z = -1, y = 3, x = 2입니다.그래서 원래의 방정식 체계에 대한 독특한 해법이 있습니다.

행렬이 일단 echelon 형식이 되면 중단하는 대신 행렬이 표에서와 같이 축소된 행 echelon 형식이 될 때까지 계속할 수 있습니다.행렬이 축소될 때까지 행이 축소되는 과정을 가우스-요르단 제거라고 부르기도 하는데, 이는 행렬이 에켈론 형태에 도달한 후 멈추는 것과 구별하기 위해서이다.

역사

가우스 제거 방법은 비록 증거는 없지만 중국 수학 텍스트 8장: 수학 예술에 관한 9장의 직사각형 배열에 나타난다.18개의 문제에서 2-5개의 방정식을 사용하여 이 방법의 용도를 설명하고 있습니다.이 제목으로 이 책에 대한 첫 번째 언급은 서기 179년으로 거슬러 올라가지만, 그것의 일부는 기원전 ^[2][3]150년경에 쓰여졌다.그것은 3세기에 유희에 의해 언급되었다.

유럽에서의 방법은 아이작 ^[4][5]뉴턴의 주석에서 유래했다.1670년, 그는 그에게 알려진 모든 대수학 책에는 연립 방정식을 푸는 교훈이 부족하다고 썼고, 뉴튼은 그것을 제공했다.캠브리지 대학교는 결국 뉴턴이 학업을 떠난 지 한참 지난 1707년에 이 노트를 산술적 유니버설리스로 출판했다.음표들은 널리 모방되었고, 이것은 18세기 말까지 가우스 제거를 대수 교과서에서 표준 수업으로 만들었다.1810년 칼 프리드리히 가우스는 최소 제곱 ^[6]문제의 정규 방정식을 풀기 위해 19세기에 전문적인 핸드 컴퓨터에 의해 채택된 대칭 제거 표기법을 고안했다.고등학교에서 가르치는 알고리즘은 1950년대에만 ^[7]과목의 역사에 대한 혼란의 결과로 가우스를 위해 명명되었다.

일부 저자는 행렬이 에켈론 형식이 될 때까지 절차만을 참조하기 위해 가우스 제거라는 용어를 사용하고, 환원된 에켈론 형식으로 끝나는 절차를 참조하기 위해 가우스-요르단 제거라는 용어를 사용한다.이 이름은 1888년 빌헬름 조던에 의해 기술된 가우스 제거의 변형이기 때문에 사용됩니다.그러나 이 방법은 같은 해에 발표된 Clasen의 기사에도 나와 있다.요르단과 클라센은 ^[8]아마도 독립적으로 가우스-요르단 소거를 발견했을 것이다.

적용들

역사적으로 행 축소법의 첫 번째 적용은 선형 방정식의 시스템을 푸는 것이다.다음은 알고리즘의 기타 중요한 응용 프로그램입니다.

컴퓨팅 결정 요인

가우스 제거가 정사각형 행렬의 행렬식 계산을 가능하게 하는 방법을 설명하기 위해, 우리는 초등 행 연산이 행렬식을 어떻게 변화시키는지 기억해야 한다.

• 두 행을 바꾸면 행렬식에 -1을 곱합니다.
• 행에 0이 아닌 스칼라를 곱하면 행렬식에 동일한 스칼라가 곱됩니다.
• 한 행에 다른 행의 스칼라 배수를 추가해도 행렬식은 변경되지 않습니다.

정사각형 행렬 A에 가우스 소거가 행 에켈론 행렬 B를 생성하는 경우 위의 규칙을 사용하여 d를 행렬식에 곱한 스칼라의 곱으로 하자.A의 행렬식은 B의 대각선 원소의 곱에 대한 d의 몫이다.

${\displaystyle\det(A)=sysfrac {display\operatorname {diag}(B)}{d.}$

계산적으로, n × n 행렬의 경우, 이 방법은³ O(n) 산술 연산만 필요로 하는 반면, 라이프니츠 공식을 행렬에 사용하는 데는 O(n!) 연산(공식에서의 총합 수)이 필요하며, 재귀적 라플라스 확장은ⁿ O(2) 연산(두 번 계산하지 않는 경우)이 필요하다.가장 빠른 컴퓨터에서도 이 두 가지 방법은 n이 20보다 크면 실용적이지 않거나 거의 실용적이지 않습니다.${\displaystyle}$

행렬의 역행렬 찾기

가우스-요르단 제거라고 불리는 가우스 제거의 변형은 행렬의 역행렬이 존재한다면 그것을 찾기 위해 사용될 수 있다.A가 n × n 정사각형 행렬인 경우 행 축소를 사용하여 역행렬을 계산할 수 있습니다.우선, n×n의 항등 행렬을 A의 오른쪽으로 증강해, n×2n의 블록 행렬[AI]을 형성한다.이제 기본 행 연산을 적용하여 이 n x 2n 행렬의 축소된 echelon 형식을 찾습니다.행렬 A는 왼쪽 블록을 항등 행렬 I로 줄일 수 있는 경우에만 반전할 수 있습니다. 이 경우 최종 행렬의 오른쪽 블록은 A입니다⁻¹.알고리즘이 왼쪽 블록을 I로 줄일 수 없는 경우 A는 반전할 수 없습니다.

예를 들어 다음 매트릭스를 생각해 보겠습니다.

$({displaystyle A=bgin{bmatrix}2&1&0\-1&2\\0&1&2\end{bmatrix})}$

이 행렬의 역행렬을 구하려면 항등식에 의해 증가된 다음 행렬을 3 × 6 행렬로 행 축소합니다.

$\displaystyle [ A I ] = \left [ { \ begin { array } { ccc ccc } 2 & 1 & 0 \ 1 & 0 & 1 & 0 \ 0 & 0 \ 0 & 0 & 0 & 0 \ \ end {array } \ right ]}$

행 연산을 수행함으로써 이 증강 매트릭스의 축소 행 echelon 형식이

${\displaystyle [ I B ] = \left [ \ begin { rrr } 1 & 0 & 0 & { \ frac {3} { 4 } } & { \ frac { { 1 } { 4 } } \ 0 & 0 & { \ frac { 1 } { 1 } { \ frac 1 } }}$

각 행 연산은 기본 행렬의 왼쪽 곱이라고 생각할 수 있습니다.B는 이들 기본행렬의 곱을 B로 나타내어 왼쪽에는 BA = I, 즉 B⁻¹ = A로 표시했다.오른쪽에는 BI = B의 기록을 유지했는데, 이는 우리가 원하는 역수이다.이 절차에서는 모든 크기의 정사각형 행렬에 대해 역행렬을 찾습니다.

랭크와 베이스 계산

가우스 제거 알고리즘은 모든 m × n 행렬 A에 적용할 수 있습니다.예를 들어, 일부 6 × 9 행렬은 다음과 같은 행 형식을 가진 행렬로 변환할 수 있습니다.

${\displaystyle T={\begin{bmatrix}a&, *&, *&, *&, *&, *&, *&, *&, *\\0&, 0&, b&, *&, *&, *&, *&, *&, *\\0&, 0&, 0&, c&, *&, *&, *&, *&, *\\0&, 0&, 0&, 0&, 0&, 0&, 기운, *&, *\\0&, 0&, 0&, 0&, 0&, 0&, 0&, 0&, e\\0&, 0&, 0&, 0&, 0&, 0&, 0&, 0&, 0\end{bmatrix}},}$

여기서 별은 임의의 엔트리, a, b, c, d, e는 제로 이외의 엔트리입니다.이 에셜론 행렬 T는 A에 대한 풍부한 정보를 포함하고 있다: T에는 0이 아닌 행이 5개 있기 때문에 A의 순위는 5이다. A의 열에 의해 스팬된 벡터 공간은 1, 3, 4, 7 및 9(a, b, c, d, E가 T에 있는 열)로 구성되며, 별들은 A의 다른 조합이 어떻게 선형으로 기록될 수 있는지를 보여준다.e basis 열.이것은 행렬로서의 선형 맵의 표현에서 점곱의 분포성의 결과입니다.

이 모든 것은 특정 행 echelon 형식인 축소 행 echelon 형식에도 적용됩니다.

계산 효율

행 축소를 실행하는 데 필요한 산술 연산의 수는 알고리즘의 계산 효율을 측정하는 한 가지 방법입니다.예를 들어 행렬에서 행 연산을 실행해 n개의 미지 방정식을 echelon 형식으로 한 후 역순으로 풀려면 n(n + 1)/2의 나눗셈, (2n³²³ + 3n - 5n)/6의 곱셈, (2n² + 3n - 5n)/6의 ^[9]곱셈이 필요하며, 총 2³/3n의 연산이 필요하다.따라서 O(n³)의 산술 복잡도를 갖습니다. 빅 O 표기법을 참조하십시오.

이 산술 복잡도는 각 산술 연산의 시간이 거의 일정할 때 전체 계산에 필요한 시간을 측정하는 좋은 척도입니다.이는 계수가 부동소수점 숫자로 표현되거나 계수가 유한 필드에 속하는 경우입니다.계수가 정확히 표현되는 정수 또는 유리수일 경우 중간 엔트리가 기하급수적으로 커질 수 있으므로 비트 복잡도는 ^[10]기하급수적으로 증가합니다.단, 중간 엔트리의 지수 증가를 피하고 O³(n)의 산술 복잡도와 동일한 O(n⁵)의 비트 복잡도를 갖는 Bareiss 알고리즘이라고 불리는 가우스 제거의 변형이 있습니다.

이 알고리즘은 수천 개의 방정식과 미지수가 있는 시스템에 사용할 수 있습니다.그러나 수백만 개의 방정식이 있는 시스템에서는 비용이 만만치 않습니다.이러한 대규모 시스템은 일반적으로 반복적인 방법을 사용하여 해결됩니다.계수가 규칙 패턴을 따르는 시스템에 대한 구체적인 방법이 있습니다(선형 방정식 시스템 참조).

n × n 행렬을 행 연산에 의해 감소된 echelon 형태로 만들려면 n개의 산술 연산이 필요하며³, 이는 계산 단계가 ^[11]약 50% 더 많은 것입니다.

한 가지 가능한 문제는 아주 작은 숫자로 나눌 수 있는 가능성으로 인한 수치 불안정이다.예를 들어 행 중 하나의 선행 계수가 0에 매우 가깝다면 행렬을 행 감소시키려면 해당 수로 나누어야 합니다.즉, 0에 가까운 숫자에 존재하는 오차는 증폭됩니다.가우스 제거는 대각선 우세 행렬 또는 양의 정의 행렬에 대해 수치적으로 안정적입니다.일반 행렬의 경우 ^[12]가우스 제거는 불안정한 안정적인 행렬의 예가 있음에도 불구하고 부분 피벗을 사용할 때 일반적으로 안정적인 것으로 간주됩니다.

일반화

가우스 소거는 실수뿐만 아니라 모든 필드에 걸쳐 수행할 수 있습니다.

Buckberger의 알고리즘은 다항식 시스템에 대한 가우스 제거의 일반화이다.이 일반화는 단항 순서의 개념에 크게 의존한다.변수에 대한 순서 선택은 이미 가우스 제거에 내포되어 있으며, 피벗 위치를 선택할 때 왼쪽에서 오른쪽으로 작업하는 선택으로 나타납니다.

2보다 큰 순서의 텐서의 순위를 계산하는 것은 ^[13]NP-hard이다.따라서 P np NP일 경우 고차 텐서의 가우스 소거 다항식 시간 아날로그가 존재할 수 없습니다(행렬은 2차 텐서의 배열 표현입니다).

유사 코드

위에서 설명한 바와 같이, 가우스 제거는 주어진 m × n 행렬 A를 행-에켈론 형태의 행렬로 변환합니다.

다음 의사 코드에서는A[i, j]행렬 A가 i행과 j열의 1부터 시작하는 인덱스를 포함하는 엔트리를 나타냅니다.변환이 제자리걸음으로 수행됩니다.즉, 원래의 행렬이 행-에켈론 형식으로 대체되기 때문에 손실됩니다.

h : = 1 /* 피벗 행 초기화 * / k : = 1 /* 피벗 열 초기화 */ 동안 피벗 열 초기화 * / i _ max : = argmax ( i = h ... m , abs ( A [ i , k ) = 0 /* 이 피벗 열에 통과하지 않는 경우피벗 아래의 ws: */ i = h + 1 ... m : f : = A [ i , k ] /* 피벗 열의 아래쪽을 0으로 채웁니다. * / A [ i , k ] : = 0 / * 현재 행의 나머지 모든 요소에 대해: */ j = k + 1...n: A[i, j] := A[i, j] - A[h, j] * f /* 피벗 행 및 열 증가 */h := h + 1 k := k + 1

이 알고리즘은 절대값이 가장 큰 피벗을 선택한다는 점에서 앞에서 설명한 알고리즘과는 약간 다릅니다.이러한 부분 피벗은 피벗 위치에서 행렬의 엔트리가 0인 경우 필요할 수 있습니다.어떤 경우에도 피벗의 가능한 가장 큰 절대값을 선택하면 부동 소수점이 숫자 표현에 사용될 때 알고리즘의 수치 안정성이 향상됩니다.

이 절차를 완료하면 매트릭스가 열 형태로 되며, 대응하는 시스템은 백 치환으로 해결할 수 있습니다.

「 」를 참조해 주세요.

• 팡청(수학)

레퍼런스

인용된 작품

• 를 클릭합니다Atkinson, Kendall A. (1989), An Introduction to Numerical Analysis (2nd ed.), New York: John Wiley & Sons, ISBN 978-0471624899.
• 를 클릭합니다Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2nd ed.), Wiley-Interscience, ISBN 978-0-471-79156-0.
• 를 클릭합니다Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3.
• 를 클릭합니다Farebrother, R.W. (1988), Linear Least Squares Computations, STATISTICS: Textbooks and Monographs, Marcel Dekker, ISBN 978-0-8247-7661-9.
• 를 클릭합니다Lauritzen, Niels, Undergraduate Convexity: From Fourier and Motzkin to Kuhn and Tucker.
• 를 클릭합니다Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9.
• Grcar, Joseph F. (2011a), "How ordinary elimination became Gaussian elimination", Historia Mathematica, 38 (2): 163–218, arXiv:0907.2397, doi:10.1016/j.hm.2010.06.003, S2CID 14259511
• Grcar, Joseph F. (2011b), "Mathematicians of Gaussian elimination" (PDF), Notices of the American Mathematical Society, 58 (6): 782–792
• 를 클릭합니다Higham, Nicholas (2002), Accuracy and Stability of Numerical Algorithms (2nd ed.), SIAM, ISBN 978-0-89871-521-7.
• 를 클릭합니다Katz, Victor J. (2004), A History of Mathematics, Brief Version, Addison-Wesley, ISBN 978-0-321-16193-2.
• Kaw, Autar; Kalu, Egwu (2010). "Numerical Methods with Applications: Chapter 04.06 Gaussian Elimination" (PDF) (1st ed.). University of South Florida.
• 를 클릭합니다Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra, New York: McGraw-Hill, pp. 69–80, ISBN 978-0-07-136200-9.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Section 2.2", Numerical Recipes: The Art of Scientific Computing (3rd ed.), New York: Cambridge University Press, ISBN 978-0-521-88068-8

외부 링크

• 인터랙티브한 지도 도구