Gaussian elimination

수학(mathematics)에서, 가우스 소거법(Gaussian elimination)은, 역시 행 감소법(row reduction)으로 알려져 있으며, 선형 방정식의 시스템을 풀기 위한 알고리듬(algorithm)입니다. 그것은 계수의 대응하는 행렬(matrix)에 대해 수행되는 연산의 열로 구성됩니다. 이 방법은 역시 행렬의 랭크(rank), 정사각 행렬(square matrix)의 행렬식(determinant)과 역-가능 행렬의 역을 계산하기 위해 사용될 수 있습니다. 그 방법은 카를 프리드리히 가우스(Carl Friedrich Gauss) (1777–1855)의 이름을 따서 지어졌지만, 그 방법의 일부 특수한 경우는—증명 없이 제시되었지만—이르면 기원전 179년경 중국 수학자에게 알려져 있었습니다.^[1]

행렬에 행 감소법을 수행하기 위해, 우리는 행렬의 아래쪽 왼쪽 구석에 가능한 많은 영을 채울 때까지 행렬을 수정하기 위해 기본 행 연산(elementary row operations)의 열을 사용합니다. 기본 행 연산의 다음과 같은 세 가지 유형이 있습니다:

두 행을 교환하는 것,
행에 비-영 숫자를 곱하는 것,
한 행의 배수를 또 다른 행에 더하는 것. (뺄셈은 한 행에 -1을 곱하고 그 결과를 또 다른 행에 더함으로써 얻을 수 있습니다)

이들 연산을 사용하여, 행렬은 항상 위쪽 삼각 행렬(upper triangular matrix)로 변환될 수 있고, 사실 그것은 행 사다리꼴 형식(row echelon form)입니다. 일단 모든 선행 계수 (각 행에서 가장 왼쪽의 비-영 엔트리)가 1이고, 선행 계수를 포함하는 모든 각 열이 어떤 딴 곳에서 영들을 가지면, 그 행렬은 감소된 행 사다리꼴 형식(reduced row echelon form)이라고 말합니다. 이러한 최종 형식은 고유합니다; 다른 말로, 그것은 사용된 행 연산의 순서에 독립적입니다. 예를 들어, 행 연산의 다음의 순서에서 (여기서 다른 행에 두 개의 기본 기본 연산이 처음과 세 번째 단계에서 수행됩니다), 세 번째 행렬과 네 번째 행렬은 행 사다리꼴의 행식에 있고, 마지막 행렬은 고유한 감소된 행 사다리꼴 형식입니다.

{\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}}

행렬을 감소된 행 사다리꼴 형식으로 변환하기 위해 행 연산을 사용하는 것은 때때로 가우스-요르단 소거법(Gauss–Jordan elimination)이라고 불립니다. 이 경우에서, 그 용어 가우스 소거법은 위쪽 삼각 형식, 또는 (비-기약) 행 사다리꼴 형식에 도달할 때까지의 과정을 참조합니다. 계산상의 이유로, 선형 방정식 시스템을 풀 때, 행렬이 완전하게 축소되기 전에 행 연산을 중지하는 것이 때때로 바람직합니다.

Definitions and example of algorithm

행 축소의 과정은 기본 행 연산(elementary row operations)을 사용하고, 두 부분으로 나눌 수 있습니다. 첫 번째 부분 (때때로 순방향 소거법이라고 불림)은 주어진 시스템을 행 사다리꼴 형식으로 축소하며, 이것으로부터 우리는 해 없음, 고유한 해, 또는 무한하게 많은 해가 있는지 알 수 있습니다. 두 번째 부분 (때때로 역방향 대입(back substitution)라고도 불림)은 해를 찾을 때까지 행 연산을 계속 사용합니다; 다시 말해서, 그것은 행렬을 기약 행 사다리꼴 형식으로 만듭니다.

알고리듬을 분석하는 데 매우 유용한 것으로 밝혀진 또 다른 관점은 행 축소법이 원래 행렬의 행렬 분해(matrix decomposition)를 생성한다는 것입니다. 기본 행 연산은 원래 행렬의 왼쪽에 기본 행렬(elementary matrices)을 곱한 것으로 볼 수 있습니다. 대안적으로, 단일 행을 줄이는 기본 연산의 열은 프로베니우스 행렬(Frobenius matrix)에 의한 곱셈으로 볼 수 있습니다. 그런-다음 알고리듬의 첫 번째 부분은 LU 분해를 계산하고, 반면에 두 번째 부분은 원래 행렬을 고유하게 결정된 역-가능 행렬과 고유하게 결정된 감소된 행 사다리꼴 행렬의 곱으로 작성합니다.

Row operations

행렬의 행에 대해 수행될 수 있는 기본 행 연산(elementary row operations)에는 세 가지 유형이 있습니다:

두 행을 교환하는 것,
행에 비-영 스칼라(scalar)를 곱하는 것,
한 행의 스칼라 배수를 또 다른 행에 더하는 것.

만약 행렬이 선형 방정식의 시스템과 결합되어 있으면, 이들 연산은 해 집합을 변경하지 않습니다. 그러므로, 목표가 선형 방정식의 시스템을 푸는 것이면, 이들 행 연산을 사용하는 것은 문제를 더 쉽게 만들 수 있습니다.

Echelon form

행렬의 각 행에 대해, 만약 행이 0으로만 구성되지 않으면, 가장 왼쪽의 비-영 엔트리가 해당 행의 선행 계수 (또는 피벗)라고 불립니다. 따라서 두 개의 선행 계수가 같은 열에 있으면, 유형 3의 행 연산이 그들 계수 중 하나를 영으로 만들기 위해 사용될 수 있습니다. 그런-다음 행 교환 연산을 사용함으로써, 모든 각 비-영 행에 대해, 선행 계수가 위의 행의 선행 계수의 오른쪽에 있도록 항상 행을 정렬할 수 있습니다. 만약 이것은 그 경우이면, 행렬은 행 사다리꼴 형식이라고 말합니다. 따라서 행렬의 아래쪽 왼쪽 부분은 0만 포함하고, 모든 영 행은 비-영 행 아래에 있습니다. 여기에서 "사다리꼴"이라는 단어가 사용된 이유는 크기에 따라 순위가 매겨진 행을 대략적으로 생각할 수 있기 때문이며, 이때 가장 큰 것이 맨 위에 있고 가장 작은 것이 맨 아래에 있습니다.

예를 들어, 다음 행렬은 행 사다리꼴 형식이고, 그것의 선행 계수는 빨간색으로 표시됩니다:

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

그것은 영 행이 바닥에 있고, 두 번째 행 (세 번째 열)의 선행 계수가 첫 번째 행 (두 번째 열)의 선행 계수 오른쪽에 있기 때문에 사다리꼴 형식입니다.

역시 모든 선행 계수가 1과 같고 (이는 유형 2의 기본 행 연산을 사용함으로써 달성할 수 있음), 선행 계수를 포함하는 모든 각 열에서, 해당 열에서 모든 다른 엔트리가 0이면 (이는 유형 3의 기본 행 연산을 사용함으로써 달성할 수 있음) 행렬은 감소된 행 사다리꼴 형식이라고 말합니다.

Example of the algorithm

목표가 다음 선형 방정식의 시스템(system of linear equations)에 대한 해 집합을 찾고 설명하는 것이라고 가정합니다:

{\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}

아래의 테이블은 방정식의 시스템과 그것의 결합된 증가된 행렬(augmented matrix)에 동시에 적용되는 행 축소 과정입니다. 실제로는, 보통 방정식의 측면에서 시스템을 다루지 않고, 대신 컴퓨터 조작에 더 적합한 증가된 행렬을 사용합니다. 행 축소 절차는 다음과 같이 요약될 수 있습니다: $L 1$ 아래의 모든 방정식에서 $x$ 를 제거하고, 그런-다음 $L 2$ 아래의 모든 방정식에서 $y$ 를 제거합니다. 이것은 시스템을 삼각형 형식(triangular form)으로 만들 것입니다. 그런-다음, 역방향-대입을 사용하여, 각각의 미지수를 해결할 수 있습니다.

System of equations	Row operations	Augmented matrix
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\end{alignedat}}$		$\left[{\begin{array}{rrr\|r}2&1&-1&8\\-3&-1&2&-11\\-2&1&2&-3\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&2y&{}+{}&z&{}={}&5&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2}\\L_{3}+L_{1}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&2&1&5\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\\&&{\tfrac {1}{2}}y&{}+{}&{\tfrac {1}{2}}z&{}={}&1&\\&&&&-z&{}={}&1&\end{alignedat}}$	$L_{3}+-4L_{2}\to L_{3}$	$\left[{\begin{array}{rrr\|r}2&1&-1&8\\0&{\frac {1}{2}}&{\frac {1}{2}}&1\\0&0&-1&1\end{array}}\right]$
The matrix is now in echelon form (also called triangular form)
${\begin{alignedat}{4}2x&{}+{}&y&&&{}={}7&\\&&{\tfrac {1}{2}}y&&&{}={}{\tfrac {3}{2}}&\\&&&{}-{}&z&{}={}1&\end{alignedat}}$	${\begin{aligned}L_{2}+{\tfrac {1}{2}}L_{3}&\to L_{2}\\L_{1}-L_{3}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}2&1&0&7\\0&{\frac {1}{2}}&0&{\frac {3}{2}}\\0&0&-1&1\end{array}}\right]$
${\begin{alignedat}{4}2x&{}+{}&y&\quad &&{}={}&7&\\&&y&\quad &&{}={}&3&\\&&&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}2L_{2}&\to L_{2}\\-L_{3}&\to L_{3}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}2&1&0&7\\0&1&0&3\\0&0&1&-1\end{array}}\right]$
${\begin{alignedat}{4}x&\quad &&\quad &&{}={}&2&\\&\quad &y&\quad &&{}={}&3&\\&\quad &&\quad &z&{}={}&-1&\end{alignedat}}$	${\begin{aligned}L_{1}-L_{2}&\to L_{1}\\{\tfrac {1}{2}}L_{1}&\to L_{1}\end{aligned}}$	$\left[{\begin{array}{rrr\|r}1&0&0&2\\0&1&0&3\\0&0&1&-1\end{array}}\right]$

두 번째 열은 방금 수행된 행 연산을 설명합니다. 따라서 첫 번째 단계에 대해, $L 2$ 에 $3 / 2 L 1$ 을 더함으로써 $x$ 를 $L 2$ 에서 제거합니다. 다음으로, $L 3$ 에 $L 1$ 을 더함으로써 $x$ 를 $L 3$ 에서 제거합니다. 이들 행 연산은 테이블에서 다음과 같이 레이블이 지정됩니다:

{\begin{aligned}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$ 임을 알 수 있습니다. 따라서 원래 방정식의 시스템에 대한 고유한 해가 있습니다.

일단 행렬이 사다리꼴 형식이 되면 멈추는 대신, 테이블에서 처럼, 행렬이 기약 행 사다리꼴 형식이 될 때까지 계속할 수 있습니다. 행렬이 축소될 때까지 행을 축소하는 과정은 사다리꼴 형식에 도달한 후 멈추는 것과 구별하기 위해 때때로 가우스-요르단 소거법으로 참조됩니다.

History

가우스 소거의 방법은 – 증명 없음에도 불구하고 – 중국 수학 텍스트 The Nine Chapters on the Mathematical Art의 Chapter Eight: Rectangular Arrays에 나타납니다. 그것의 사용법은 2에서 5의 방정식을 갖는 18 개의 문제에서 설명되어 있습니다. 이 제목으로 책에 대한 첫 번째 참조는 기원후 179년으로 거슬러 올라가지만, 그것의 일부는 빠르면 기원전 150년경에 쓰였습니다.^[2]^[3]^[4] 그것은 3세기에 유 휘(Liu Hui)에 의해 논평되었습니다.

유럽에서 그 방법은 아이작 뉴턴(Isaac Newton)의 노트에서 비롯되었습니다.^[5]^[6] 1670년에, 그는 자신이 알고 있는 모든 대수학 책에는 당시 뉴턴이 제공했던 연립 방정식을 푸는 수업이 부족하다고 썼습니다. 케임브리지 대학교는 결국 뉴턴이 학업을 중단한 지 오랜 후인 1707년에 이 노트를 Arithmetica Universalis로 출판했습니다. 그 노트는 광범위하게 모방되어, 18세기 말까지 대수학 교과서의 표준 수업 (지금 부르게 되는) 가우스 소거법이 되었습니다. 1810년 카를 프리드리히 가우스(Carl Friedrich Gauss)는 최소-제곱 문제의 정규 방정식을 풀기 위해 19세기에 전문 핸드 컴퓨터(hand computers)에 의해 채택된 대칭 제거에 대한 표기법을 고안했습니다.^[7] 고등학교에서 가르치는 알고리듬은 1950년대에 와서야 가우스의 이름을 따서 이름을 붙였습니다.^[8]

일부 저자는 행렬이 사다리꼴 형식이 될 때까지의 절차만을 지칭하기 위해 가우스 소거법이라는 용어를 사용하고, 기약 사다리꼴 형식으로 끝나는 절차를 지칭하기 위해 가우스-요르단 소거법이라는 용어를 사용합니다. 그 이름은 1888년 빌헬름 요르단(Wilhelm Jordan)에 의해 설명된 가우스 소거법의 변형이기 때문에 사용됩니다. 어쨌든, 그 방법은 역시 같은 해에 출판된 클라센(Clasen)의 기사에도 나타납니다. 요르단과 클라센은 아마도 독립적으로 가우스-요르단 소거법을 발견했을 것입니다.^[9]

Applications

역사적으로. 행 축소 방법의 첫 번째 응용은 선형 방정식의 시스템(systems of linear equations)을 푸는 것입니다. 다음은 알고리듬의 일부 다른 중요한 응용입니다.

Computing determinants

가우스 소거법이 정사각 행렬의 행렬식의 계산을 허용하는 방법을 설명하기 위해, 우리는 기본 행 연산이 행렬식을 어떻게 변경하는지 기억해야 합니다:

두 행을 바꾸면 행렬식에 −1을 곱합니다.
행에 비-영 스칼라를 곱하면 행렬식에 같은 스칼라를 곱합니다.
한 행에 또 다른 행의 스칼라 배수를 더해도 행렬식은 변경되지 않습니다.

만약 정사각 행렬 $A$ 에 적용된 가우스 소거법이 행 사다리꼴 행렬 $B$ 를 생성하면, 위의 규칙을 사용하여 행렬식이 곱해진 스칼라의 곱을 $d$ 라고 놓습니다. 그런-다음 $A$ 의 행렬식은 $B$ 의 대각선 원소의 곱의 $d$ 에 의한 몫입니다:

\det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.

계산적으로, $n \times n$ 행렬에 대해, 이 방법은 $O(n 3)$ 산술 연산만 필요하고, 반면에 행렬식에 대한 라이프니츠 공식(Leibniz formula for determinants)을 사용하면 $O(n!)$ 연산 (공식의 피합수의 개수)이 필요하고, 재귀적 라플라스 전개(Laplace expansion)는 $O(2 n)$ 연산 (아무것도 두 번 계산되지 않으면, 계산하기 위해 부분-행렬식의 개수)이 필요합니다. 심지어 가장 빠른 컴퓨터에서도, 이들 두 가지 방법은 20보다 큰 $n$ 에 대해 비실용적이거나 거의 불가능합니다.

Finding the inverse of a matrix

가우스–요르단 소거법이라고 불리는 가우스 소거법의 변형은 행렬의 역행렬을, 만약 존재한다면, 찾는 데 사용될 수 있습니다. 만약 $A$ 가 $n \times n$ 정사각 행렬이면, 행 축소를 그것의 역 행렬(inverse matrix)을, 만약 존재한다면, 계산하기 위해 사용할 수 있습니다. 먼저, $n \times n$ 항등 행렬이 $A$ 의 오른쪽에 증가되어, $n \times 2 n$ 블록 행렬(block matrix) $[A | I]$ 를 형성합니다. 이제 기본 행 연산 적용을 통해, 이 $n \times 2 n$ 행렬의 기약 사다리꼴 형식을 찾습니다. 행렬 $A$ 가 역-가능인 것과 왼쪽 블록이 항등 행렬 $I$ 로 축소될 수 있는 것은 필요충분 조건입니다; 이 경우에서, 최종 행렬의 오른쪽 블록은 $A -1$ 입니다. 만약 그 알고리듬이 왼쪽 블록을 $I$ 로 줄일 수 없으면, $A$ 는 역-가능이 아닙니다.

예를 들어, 다음 행렬을 생각해 보십시오:

A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.

이 행렬의 역을 찾기 위해, 항등 행렬로 증가된 다음 행렬을 취하고 그것을 3 × 6 행렬로 행-축소합니다:

[A|I]=\left[{\begin{array}{ccc|ccc}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right].

행 연산을 수행함으로써, 이 증가된 행렬의 감소된 행 사다리꼴 형식이 다음과 같은지 확인할 수 있습니다:

[I|B]=\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right].

각 행 연산을 기본 행렬(elementary matrix)의 왼쪽 곱으로 생각할 수 있습니다. 이들 기본 행렬의 곱을 $B$ 로 표시하면, 왼쪽에 $BA = I$ 이고, 따라서 $B = A -1$ 임을 알 수 있습니다. 오른쪽에는, $BI = B$ 라는 기록을 보관하며, 이는 우리가 원했던 역임을 알고 있습니다. 역 행렬을 찾는 이 절차는 임의의 크기의 정사각 행렬에 대해 동작합니다.

Computing ranks and bases

가우스 소거 알고리듬은 임의의 $m \times n$ 행렬 $A$ 에 적용될 수 있습니다. 이러한 방법에서, 예를 들어, 일부 6 × 9 행렬은 다음과 같은 행 사다리꼴 형식을 가지는 행렬로 변환될 수 있습니다:

T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\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$ 에 대한 풍부한 정보를 포함합니다: $A$ 의 랭크(rank)는 5인데, 왜냐하면 $T$ 에 5 개의 비-영 행이 있기 때문입니다; $A$ 의 열에 의해 스팬된 벡터 공간(vector space)은 열 1, 3, 4, 7, 및 9 ( $T$ 에서 $a, b, c, d, e$ 를 갖는 열)로 구성된 기저를 가지고, 별은 $A$ 의 다른 열이 기저 열의 선형 조합으로 쓰이는 방법을 보여줍니다. 이것은 선형 맵을 행렬로 표현한 점 곱(dot product)의 분배성에 따른 결과입니다.

이 모든 것은 특정 행 사다리꼴 형식인 감소된 행 사다리꼴 형식에도 적용됩니다.

Computational efficiency

행 축소를 수행하기 위해 요구된 산술 연산의 개수는 알고리듬의 계산 효율성을 측정하는 한 가지 방법입니다. 예를 들어, 행렬이 사다리꼴 형식이 될 때까지 행렬에 행 연산을 수행하고, 그런-다음 각 미지수를 역순으로 풀어서 $n$ 미지수에 대한 $n$ 방정식의 시스템을 풀기 위해, 근사적으로 총 $2 n 3 /3$ 연산에 대해, $n (n + 1)/2$ 나눗셈, $(2 n 3 + 3 n 2 - 5 n)/6$ 곱셈, 및 $(2 n 3 + 3 n 2 - 5 n)/6$ 뺄셈을 요구합니다.^[10] 따라서 그것은 $O(n 3)$ 의 산술 복잡도를 가집니다; 큰 O 표기법(Big O notation)을 참조하십시오.

이 산술 복잡도는 각 산술 연산에 대한 시간이 근사적으로 상수일 때 전체 계산에 필요한 시간의 좋은 측정입니다. 이것은 계수가 부동-점 숫자(floating-point numbers)에 의해 표시될 때 또는 그것들이 유한 필드(finite field)에 속할 때의 경우입니다. 만약 계수가 정수 또는 정확하게 표현된 유리수이면, 중간 엔트리가 기하급수적으로 커질 수 있으므로, 비트 복잡도(bit complexity)가 기하급수적입니다.^[11] 어쨌든, 버라이스 알고리듬(Bareiss algorithm)이라고 불리는 가우스 소거법의 변형이 있으며, 그 알고리듬은 중간 엔트리의 기하급수적인 증가를 피하고, $O(n 3)$ 의 같은 산술 복잡도와 함께, $O(n 5)$ 의 비트 복잡도를 가집니다.

이 알고리듬은 수천 개의 방정식과 미지수를 갖는 시스템에 대해 컴퓨터에서 사용될 수 있습니다. 어쨌든, 수백만 개의 방정식을 갖는 시스템에 대해 비용이 엄청나게 듭니다. 이들 대규모 시스템은 일반적으로 반복적인 방법(iterative methods)을 사용하여 해결됩니다. 계수가 규칙적인 패턴을 따르는 시스템에 대한 특정 방법이 존재합니다 (선형 방정식의 시스템을 참조하십시오).

행 연산에 의해 $n \times n$ 행렬을 기약 사다리꼴 형식으로 만들기 위해, 근사적으로 50% 더 많은 계산 단계인 $n 3$ 산술 연산이 필요합니다.^[12]

한 가지 가능한 문제는 매우 작은 수로 나눌 가능성으로 인해 발생하는 수치적 불안정성(numerical instability)입니다. 만약, 예를 들어, 행 중 하나의 선행 계수가 영에 매우 가까우면, 행렬을 행-축소하기 위해, 해당 숫자로 나누어야 합니다. 이것은 영에 가까운 숫자에 대해 존재하는 임의의 오차가 증폭됨을 의미합니다. 가우스 소거법은 대각선으로 지배적(diagonally dominant) 행렬 또는 양의-한정(positive-definite) 행렬에 대해 수치적으로 안정적입니다. 일반 행렬에 대해, 비록 가우스 소거법이 불안정한 안정적인 행렬의 예제가 있더라도, 부분 피벗팅을 사용할 때, 가우시안 소거법은 보통 안정적인 것으로 고려됩니다.^[13]

Generalizations

가우스 소거법은 실수뿐만 아니라 임의의 필드(field)에 대해 수행될 수 있습니다.

부흐베르거의 알고리듬(Buchberger's algorithm)은 가우스 소거법을 다항 방정식의 시스템(systems of polynomial equations)으로 일반화한 것입니다. 이 일반화는 단항식 순서(monomial order)의 개념에 크게 의존합니다. 변수에 대한 순서화의 선택은 이미 가우스 소거법에 내포되어 있으며, 피벗 위치를 선택할 때 왼쪽에서 오른쪽으로 작업하는 선택으로 나타납니다.

2보다 큰 차수 텐서의 랭크를 계산하는 것은 NP-hard입니다.^[14] 그러므로, $P \neq NP$ 이면, 고차 텐서 (행렬은 차수 2 텐서의 배열 표현임)에 대해 가우스 소거법의 다항식 시간 아날로그가 있을 수 없습니다.

Pseudocode

위에서 설명한 것처럼, 가우스 소거법은 주어진 $m \times n$ 행렬 $A$ 를 행 사다리꼴 형식(row-echelon form)에서 행렬로 변환합니다.

다음 유사-코드(pseudocode)에서, A[i, j]는 인덱스가 1부터 시작하는 행 $i$ 와 열 $j$ 에 있는 행렬 $A$ 의 엔트리를 나타냅니다. 변환은 제자리에서 수행되며, 원래 행렬은 결국 그것의 행 사다리꼴 형식으로 대체되기 때문에 없어짐을 의미합니다.

h := 1 /* Initialization of the pivot row */
k := 1 /* Initialization of the pivot column */

while h ≤ m and k ≤ n
    /* Find the k-th pivot: */
    i_max := argmax (i = h ... m, abs(A[i, k]))
    if A[i_max, k] = 0
        /* No pivot in this column, pass to next column */
        k := k + 1
    else
         swap rows(h, i_max)
         /* Do for all rows below pivot: */
         for i = h + 1 ... m:
             f := A[i, k] / A[h, k]
             /* Fill with zeros the lower part of pivot column: */
             A[i, k] := 0
             /* Do for all remaining elements in current row: */
             for j = k + 1 ... n:
                 A[i, j] := A[i, j] - A[h, j] * f
         /* Increase pivot row and column */
         h := h + 1
         k := k + 1

이 알고리듬은 가장 큰 절댓값(absolute value)을 갖는 피벗을 선택함으로써 앞에서 설명한 것과 약간 다릅니다. 만약 피벗 위치에서, 행렬의 엔트리가 영이면, 그러한 부분 피벗팅이 필요할 수 있습니다. 임의의 경우에서, 부동 점(floating point)이 숫자를 나타내는 데 사용될 때, 피벗의 가장 큰 가능한 절댓값을 선택하면 알고리듬의 수치적 안정성(numerical stability)이 향상됩니다.

이 절차가 완료되면, 그 행렬은 행 사다리꼴 형식(row echelon form)에 있을 것이고 해당 시스템은 역방향 대입(back substitution)에 의해 풀 수 있습니다.

References

^ Grcar, Joseph F. (2011-05-01). "How ordinary elimination became Gaussian elimination". Historia Mathematica. 38 (2): 163–218. doi:10.1016/j.hm.2010.06.003. ISSN 0315-0860. S2CID 14259511.
^ "DOCUMENTA MATHEMATICA, Vol. Extra Volume: Optimization Stories (2012), 9-14". www.emis.de. Retrieved 2022-12-02.
^ Calinger (1999), pp. 234–236
^ Timothy Gowers; June Barrow-Green; Imre Leader (8 September 2008). The Princeton Companion to Mathematics. Princeton University Press. p. 607. ISBN 978-0-691-11880-2.
^ Grcar (2011a), pp. 169-172
^ Grcar (2011b), pp. 783–785
^ Lauritzen, p. 3
^ Grcar (2011b), p. 789
^ Althoen, Steven C.; McLaughlin, Renate (1987), "Gauss–Jordan reduction: a brief history", The American Mathematical Monthly, 94 (2), Mathematical Association of America: 130–142, doi:10.2307/2322413, ISSN 0002-9890, JSTOR 2322413
^ Farebrother (1988), p. 12.
^ Fang, Xin Gui; Havas, George (1997). "On the worst-case complexity of integer Gaussian elimination" (PDF). Proceedings of the 1997 international symposium on Symbolic and algebraic computation. ISSAC '97. Kihei, Maui, Hawaii, United States: ACM. pp. 28–31. doi:10.1145/258726.258740. ISBN 0-89791-875-4.^{[permanent dead link]}
^ J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, Chapter 10.
^ Golub & Van Loan (1996), §3.4.6.
^ Hillar, Christopher; Lim, Lek-Heng (2009-11-07). "Most tensor problems are NP-hard". arXiv:0911.1393 [cs.CC].

Works cited

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. Archived (PDF) from the original on 2012-09-07.
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

External links

Interactive didactic tool

[1] Grcar, Joseph F. (2011-05-01). "How ordinary elimination became Gaussian elimination". Historia Mathematica. 38 (2): 163–218. doi:10.1016/j.hm.2010.06.003. ISSN 0315-0860. S2CID 14259511.

[2] "DOCUMENTA MATHEMATICA, Vol. Extra Volume: Optimization Stories (2012), 9-14". www.emis.de. Retrieved 2022-12-02.

[3] Calinger (1999), pp. 234–236

[princeton-4] Timothy Gowers; June Barrow-Green; Imre Leader (8 September 2008). The Princeton Companion to Mathematics. Princeton University Press. p. 607. ISBN 978-0-691-11880-2.

[5] Grcar (2011a), pp. 169-172

[6] Grcar (2011b), pp. 783–785

[7] Lauritzen, p. 3

[8] Grcar (2011b), p. 789

[9] Althoen, Steven C.; McLaughlin, Renate (1987), "Gauss–Jordan reduction: a brief history", The American Mathematical Monthly, 94 (2), Mathematical Association of America: 130–142, doi:10.2307/2322413, ISSN 0002-9890, JSTOR 2322413

[10] Farebrother (1988), p. 12.

[11] Fang, Xin Gui; Havas, George (1997). "On the worst-case complexity of integer Gaussian elimination" (PDF). Proceedings of the 1997 international symposium on Symbolic and algebraic computation. ISSAC '97. Kihei, Maui, Hawaii, United States: ACM. pp. 28–31. doi:10.1145/258726.258740. ISBN 0-89791-875-4.^{[permanent dead link]}

[12] J. B. Fraleigh and R. A. Beauregard, Linear Algebra. Addison-Wesley Publishing Company, 1995, Chapter 10.

[13] Golub & Van Loan (1996), §3.4.6.

[14] Hillar, Christopher; Lim, Lek-Heng (2009-11-07). "Most tensor problems are NP-hard". arXiv:0911.1393 [cs.CC].

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]