Solving Systems of Linear Equations

식 (2.3)에서 일반적인 연립선형방정식의 형태를 다음과 같이 작성했습니다.

\[a_{11}x_1 + \cdots + a_{1n}x_n = b_1 \\ \vdots \\ a_{m1}x_1 + \cdots + a_{mn}x_n = b_{mn} \tag{2.37}\]

여기서 $a_{ij} \in \mathbb{R}$ 과 $b_i \in \mathbb{R}$ 은 알고 있는 상수이며, $x_j$ 는 미지수입니다($i = 1, \cdots, m, j = 1, \cdots, n$).

아래에서는 연립선형방정식의 풀이에 초점을 맞추고 행렬의 역행렬을 찾는 알고리즘에 대해 살펴보도록 하겠습니다.

Particular and General Solution

연립선형방정식의 해를 찾는 일반적인 방법을 살펴보기 전에, 아래의 연립방정식에 대한 예제를 살펴보도록 하겠습니다.

\[\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} 42 \\ 8 \end{bmatrix} \tag{2.38}\]

이 시스템에는 두 개의 방정식과 4개의 미지수가 있습니다. 따라서, 우리는 무한히 많은 해가 존재한다는 것을 예상할 수 있습니다(방정식의 갯수보다 미지수가 더 많으므로). 이 연립방정식에서 처음 두 열은 0과 1로만 구성된 아주 쉬운 형태입니다. $\sum_{i=1}^4 x_i\boldsymbol{c}_i = \boldsymbol{b}$ 에서 $\boldsymbol{c}_i$ 를 행렬의 i번째 열이고, $\boldsymbol{b}$ 를 식 (2.38)의 우항이라고 정의했을 때, 우리의 목적은 $x_1, \dotsc, x_4$ 의 스칼라 값을 구하는 것입니다. 식 (2.38)의 해는 첫 번째 열에 42를 곱하고 두 번째 열에 8을 곱하면 쉽게 구할 수 있습니다.

\[\boldsymbol{b} = \begin{bmatrix} 42 \\ 8 \end{bmatrix} = 42 \begin{bmatrix} 1 \\ 0 \end{bmatrix} + 8 \begin{bmatrix} 0 \\ 1 \end{bmatrix} \tag{2.39}\]

따라서, 해는 $\lbrack 42, 8, 0, 0 \rbrack^\top$ 이 됩니다. 이러한 해는 특수해(particular solution or special solution) 이라고 합니다. 그러나, 연립선형방정식의 해는 하나가 아닙니다. 다른 해들을 찾으려면 0-벡터를 만드는 여러 방법을 찾아야 하는데, 0-벡터를 다른 특수해에 더해도 특수해는 변하지 않습니다.

처음 두 열을 사용해서 세 번째 열을 다음과 같이 표현할 수 있습니다.

\[\begin{bmatrix} 8 \\ 2 \end{bmatrix} = 8\begin{bmatrix} 1 \\ 0 \end{bmatrix} + 2 \begin{bmatrix} 0 \\ 1 \end{bmatrix} \tag{2.40}\]

따라서, $\boldsymbol{0} = 8\boldsymbol{c}_1 + 2\boldsymbol{c}_2 -\boldsymbol{c}_3 + 0\boldsymbol{c}_4$ 이고, 해는 $(x_1, x_2, x_3, x_4) = (8, 2, -1, 0)$ 입니다. 어떠한 스칼라 값을 곱해도 0이므로 이 해에 $\lambda_1 \in \mathbb{R}$ 이 곱해져도 무관합니다.

\[\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \left( \lambda_1 \begin{bmatrix} 8 \\ 2 \\ -1 \\ 0 \end{bmatrix} \right) = \lambda_1(8\boldsymbol{c}_1 + 2\boldsymbol{c}_2 -\boldsymbol{c}_3) = \boldsymbol{0} \tag{2.41}\]

동일한 방식으로 (2.38)의 행렬의 네 번째 열을 처음 두 번째 열을 사용하여 표현할 수 있습니다.

\[\begin{bmatrix} 1 & 0 & 8 & -4 \\ 0 & 1 & 2 & 12 \end{bmatrix} \left( \lambda_2 \begin{bmatrix} -4 \\ 12 \\ 0 \\ -1 \end{bmatrix} \right) = \lambda_1(-4\boldsymbol{c}_1 + 12\boldsymbol{c}_2 -\boldsymbol{c}_4) = \boldsymbol{0} \tag{2.42}\]

이제 앞서 구한 특수해와 방금 구한 것들을 합치면, (2.38)의 연립방정식의 모든 해를 구할 수 있습니다. 이러한 해를 일반해(general solution)이라고 합니다.

\[\left\lbrace \boldsymbol{x} \in \mathbb{R}^4 : \boldsymbol{x} = \begin{bmatrix} 42 \\ 8 \\ 0 \\ 0 \end{bmatrix} + \lambda_1 \begin{bmatrix} 8 \\ 2 \\ -1 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} -4 \\ 12 \\ 0 \\ -1 \end{bmatrix}, \lambda_1, \lambda_2 \in \mathbb{R} \right\rbrace \tag{2.43}\]

(2.38)의 연립선형방정식은 쉬운 형태의 행렬이기 때문에 위와 같이 풀기 쉬웠고, 특수해와 일반해를 찾을 수 있었습니다. 하지만, 일반적인 연립선형방정식은 이렇게 단순한 형태가 아닙니다. 다행히 모든 연립선형방정식을 간단한 형태로 변환하는 가우스 소거법(Gaussian elimination)이라는 알고리즘이 있습니다. 가우스 소거법의 핵심은 연립선형방정식을 간단한 형태로 변환하는 연립선형방정식의 elementary transformations 입니다. 이 알고리즘으로 복잡한 형태의 연립선형방정식을 간단한 형태로 변환한 후, 위의 세 단계를 적용할 수 있습니다.

Elementary Transformations

위에서 언급했듯이 연립선형방정식을 푸는데 핵심은 elementary transformations 입니다. 이 변환을 수행해도 해는 변하지 않으며, 단지 연립방정식을 간단한 형태로 변환하기만 합니다. 이 변환의 과정은 다음과 같습니다.

• 두 방정식을 교환한다. (연립선형방정식을 표현하는 행렬의 행을 교환)
• 0이 아닌 상수 $\lambda \in \mathbb{R}$ 을 한 방정식에 곱한다.
• 두 방정식을 더한다.

다음의 예제를 통해서 변환 방법을 살펴보도록 하겠습니다.

\[\begin{matrix} -2x_1 &+ &4x_2 &- &2x_3 &- &x_4 &+ &4x_5 &= &-3 \\ 4x_1 &- &8x_2 &+ &3x_3 &- &3x_4 &+ &x_5 &= &2 \\ x_1 &- &2x_2 &+ &x_3 &- &x_4 &+ &x_5 &= &0 \\ x_1 &- &2x_2 & & &- &3x_4 &+ &4x_5 &= &a \end{matrix} \tag{2.44}\]

먼저 위의 연립선형방정식을 $\boldsymbol{Ax} = \boldsymbol{b}$ 의 형태로 변환하는데, 변수 $\boldsymbol{x}$ 를 생략하고 augmented matrix(in the form $\lbrack \boldsymbol{A} | \boldsymbol{b} \rbrack$ )로 표현하도록 하겠습니다.

augmented matrix를 첨가 행렬이라고 칭합니다. 계수 행렬과 상수 행렬을 붙인 것을 의미하며, 수직선을 통해 이 둘을 구분합니다.

\[\left\lbrack \left.\begin{matrix} -2 & 4 & -2 & -1 & 4 \\ 4 & -8 & 3 & -3 & 1 \\ 1 & -2 & 1 & -1 & 1 \\ 1 & -2 & 0 & -3 & 4 \end{matrix}\right| \begin{matrix} -3 \\ 2 \\ 0 \\ a \end{matrix} \right\rbrack\]

먼저 첫 번째 행과 세 번째 행을 서로 교환합니다.

\[\left\lbrack \left.\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 4 & -8 & 3 & -3 & 1 \\ -2 & 4 & -2 & -1 & 4 \\ 1 & -2 & 0 & -3 & 4 \end{matrix}\right| \begin{matrix} 0 \\ 2 \\ -3 \\ a \end{matrix} \right\rbrack \begin{align*} \\ -4R_1 \\ +2R_1 \\ -R_1 \end{align*}\]

그리고 두 번째 행은 첫 번째 행에 4배한 결과를 빼주고, 세 번째 행은 첫 번째 행에 2배한 결과를 더하고, 네 번째 행은 첫 번째 행을 빼줍니다. 이러한 방식으로 아래의 연산들을 수행합니다.

\[\begin{align*} &\left\lbrack \left.\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & -1 & 1 & -3 \\ 0 & 0 & 0 & -3 & 6 \\ 0 & 0 & -1 & -2 & 3 \end{matrix}\right| \begin{matrix} 0 \\ 2 \\ -3 \\ a \end{matrix} \right\rbrack \begin{matrix} \\ \\ \\ -R_2 - R_3 \end{matrix} \\ \rightsquigarrow & \left\lbrack \left.\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & -1 & 1 & 3 \\ 0 & 0 & 0 & -3 & 6 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}\right| \begin{matrix} 0 \\ 2 \\ -3 \\ a + 1 \end{matrix} \right\rbrack \begin{matrix} \\ \cdot (-1) \\ \cdot(-1/3) \\ \; \end{matrix} \\ \rightsquigarrow & \left\lbrack \left.\begin{matrix} 1 & -2 & 1 & -1 & 1 \\ 0 & 0 & 1 & -1 & -3 \\ 0 & 0 & 0 & 1 & -2 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}\right| \begin{matrix} 0 \\ -2 \\ 1 \\ a + 1 \end{matrix} \right\rbrack \begin{matrix} \\ \\ \\ \end{matrix} \end{align*}\]

위의 결과로 다음의 연립방정식을 얻을 수 있습니다.

\[\begin{matrix} x_1 &- &2x_2 &+ &x_3 &- &x_4 &+ &x_5 &= &0 \\ & & & &x_3 &- &x_4 &+ &3x_5 &= &-2 \\ & & & & & &x_4 &- &2x_5 &= &1 \\ & & & & & & & &0 &= &a + 1 \end{matrix} \tag{2.45}\]

오직 $a = -1$ 일 때, 이 시스템은 해가 존재합니다. 특수해(particular solution)은 다음과 같습니다.

\[\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} \tag{2.46}\]

일반해(general solution)은 다음과 같습니다.

\[\left\lbrace \boldsymbol{x} \in \mathbb{R}^5 : \boldsymbol{x} = \begin{bmatrix} 2 \\ 0 \\ -1 \\ 1 \\ 0 \end{bmatrix} + \lambda_1 \begin{bmatrix} 2 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 2 \\ 0 \\ -1 \\ 2 \\ 1 \end{bmatrix}, \lambda_1, \lambda_2 \in \mathbb{R} \right\rbrace \tag{2.47}\]

Definition 2.6 (Row-Echelon Form)

• 0으로만 구성된 행이 행렬의 가장 아랫쪽에 위치한다. (0이 아닌 요소를 하나 이상 가지고 있는 행은 0으로만 구성된 행 위에 존재)
• 0이 아닌 행만 봤을 때, 왼쪽에서부터 처음으로 0이 아닌 숫자(pivot or leading coefficient)가 항상 그 행의 윗 행의 피벗의 오른쪽에 위치한다.

위 조건들을 만족하는 행렬은 사다리꼴 모앙(row-echelon form) 입니다.

Example 2.7 (Reduced Row Echelon Form)
아래의 행렬은 reduced row-echelon form 이며, 피벗은 굵은 글자로 표시되었습니다.

\[\boldsymbol{A} = \begin{bmatrix} \boldsymbol{1} & 3 & 0 & 0 & 3 \\ 0 & 0 & \boldsymbol{1} & 0 & 9 \\ 0 & 0 & 0 & \boldsymbol{1} & -4 \end{bmatrix} \tag{2.49}\]

$\boldsymbol{Ax} = \boldsymbol{0}$ 의 해를 찾는데 핵심은 non-pivot columns를 찾는 것입니다. 그리고, 피벗이 있는 열의 선형 조합으로 식을 표현합니다. reduced row-echelon form은 이를 비교적 쉽게 만들 수 있고, 피벗이 없는 열을 해당 열의 왼쪽에 있는 피벗 열의 합과 조합으로 표현할 수 있습니다. (2.49)를 예로 들면, 두 번째 열은 첫 번째 열을 3배한 것과 같습니다. 따라서, $\boldsymbol{0}$ 을 구하기 위해서, 두 번째 열을 첫 번째 열에 3을 곱한 것을 빼면 됩니다.
다섯 번째 열은 (첫 번째 피벗 열 x 3), (두 번째 피벗 열 x 9), (세 번째 피벗열 x -4)의 조합으로 표현할 수 있습니다. 따라서, 다섯 번째 열을 3개의 피벗 열로 표현할 수 있으며, 결과적으로 homogeneous equation system($\boldsymbol{Ax} = \boldsymbol{0}$ 꼴의 연립방정식)의 해를 구할 수 있습니다.
따라서, $\boldsymbol{Ax} = \boldsymbol{0}$ 의 해는 다음과 같습니다.

\[\left\lbrace \boldsymbol{x} \in \mathbb{R}^5 : \boldsymbol{x} = \lambda_1 \begin{bmatrix} 3 \\ -1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 3 \\ 0 \\ 9 \\ -4 \\ -1 \end{bmatrix}, \quad \lambda_1, \lambda_2 \in \mathbb{R} \right\rbrace \tag{2.50}\]

The Minus-1 Trick

이번에는 homogeneous system of linear equations $\boldsymbol{Ax} = \boldsymbol{0}$ 의 해를 구하는 트릭에 대해서 살펴보도록 하겠습니다.

시작하기에 앞서, 행렬 $\boldsymbol{A} \in \mathbb{R}^{k \times n}$ 는 reduce row-echelon form이고 다음과 같은 행렬이라고 가정해봅시다 ($\boldsymbol{x} \in \mathbb{R}^n$ ).

\[\boldsymbol{A} = \begin{bmatrix} 0 & \cdots & 0 & \boldsymbol{1} & \ast & \cdots & \ast & 0 & \ast & \cdots & \ast & 0 & \ast & \cdots & \ast \\ \vdots & & \vdots & 0 & 0 & \cdots & 0 & \boldsymbol{1} & \ast & \cdots & \ast & \vdots & \vdots & & \vdots \\ \vdots & & \vdots & \vdots & \vdots & & \vdots & 0 & \vdots & & \vdots & \vdots & \vdots & & \vdots \\ 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & 0 & \cdots & 0 & \boldsymbol{1} & \ast & \cdots & \ast \end{bmatrix} \tag{2.51}\]

여기서 $\ast$ 는 임의의 실수이며, 위 행렬의 어느 행에서든지 첫 번째로 0이 아닌 요소의 값은 1이며 그 행에서 나머지 요소들은 모두 0이라고 가정합니다. 볼드체로 표시된 피벗을 가진 열 $j_1, j_2, \dotsc, j_k$ 는 표준 단위 벡터 $\boldsymbol{e}_1, \cdots, \boldsymbol{e}_k \in \mathbb{R}^k$ 입니다. 위 행렬은 다음 형태의 n - k 행을 더하여

\[\begin{bmatrix} 0 & \cdots & 0 & -1 & 0 & \cdots & 0 \end{bmatrix} \tag{2.52}\]

$n \times n$ 행렬 $\tilde{\boldsymbol{A}}$ 행렬로 확장할 수 있습니다. 따라서, augmented matrix $\tilde{\boldsymbol{A}}$ 의 대각 요소들은 1 또는 -1을 포함합니다. 그러면, 피벗으로 -1을 포함하는 행렬 $\tilde{\boldsymbol{A}}$ 의 열은 homogeneous equation system $\boldsymbol{Ax} = \boldsymbol{0}$ 의 해입니다. 조금 더 정확하게 말하자면, -1을 피벗으로 하는 열들은 $\boldsymbol{Ax} = \boldsymbol{0}$ 의 solution space의 basis(기저)를 형성하며, 이를 kernel 또는 null space라고 부릅니다 (2.7.3절 참조).

Example 2.8 (Minus-1 Trick)
식 (2.49)의 행렬을 다시 살펴보도록 하겠습니다.

\[\boldsymbol{A} = \begin{bmatrix} \boldsymbol{1} & 3 & 0 & 0 & 3 \\ 0 & 0 & \boldsymbol{1} & 0 & 9 \\ 0 & 0 & 0 & \boldsymbol{1} & -4 \end{bmatrix} \tag{2.53}\]

위 행렬에 (2.52) 형태의 행을 추가하여 아래와 같은 $5 \times 5$ 행렬로 변환합니다.

\[\tilde{\boldsymbol{A}} = \begin{bmatrix} \boldsymbol{1} & 3 & 0 & 0 & 3 \\ \color{Blue}0 & \color{Blue}-\boldsymbol{\color{Blue}1} & \color{Blue}0 & \color{Blue}0 & \color{Blue}0 \\ 0 & 0 & \boldsymbol{1} & 0 & 9 \\ 0 & 0 & 0 & \boldsymbol{1} & -4 \\ \color{Blue}0 & \color{Blue}0 & \color{Blue}0 & \color{Blue}0 & \color{Blue}-\boldsymbol{\color{Blue}1} \end{bmatrix} \tag{2.54}\]

위 행렬로부터 대각 요소에 -1을 포함하는 열을 가지고, 바로 $\boldsymbol{Ax} = \boldsymbol{0}$ 의 해를 얻을 수 있습니다.

\[\left\lbrace \boldsymbol{x} \in \mathbb{R}^5 : \boldsymbol{x} = \lambda_1 \begin{bmatrix} 3 \\ -1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 3 \\ 0 \\ 9 \\ -4 \\ -1 \end{bmatrix}, \quad \lambda_1, \lambda_2 \in \mathbb{R} \right\rbrace \tag{2.55}\]

이 결과는 (2.50)에서 얻은 결과와 완전 동일하다는 것을 알 수 있습니다.

참고로 가우스 소거법을 통해 역행렬을 구할 수 있습니다 (Example 2.9 참조).

Algorithm for Solving a System of Linear Equations

이번에는 $\boldsymbol{Ax} = \boldsymbol{b}$ 형태의 연립선형방정식의 해를 구하는 방법에 대해 간략하게 살펴보도록 하겠습니다. 해는 항상 존재한다고 가정하는데, 만약 해가 존재하지 않는다면, 해를 근사(approximate solution)해야 하며 챕터 2에서는 다루지 않습니다. 근사해를 구하는 한 가지 방법은 선형 회귀(linear regression)을 사용하는 것이며 이는 챕터 9에서 자세하게 살펴봅니다.

Special case로, 역행렬 $\boldsymbol{A}^{-1}$ 을 구할 수 있고, $\boldsymbol{x} = \boldsymbol{A}^{-1}\boldsymbol{b}$ 로 해를 구할 수 있습니다. 그러나, 이는 행렬 $\boldsymbol{A}$ 가 정사각 행렬(square matrix)이면서 역행렬이 존재(invertible)해야 합니다. 그렇지 않으면 $\boldsymbol{A}$ 는 ‘linear independent columns가 있다’라는 가정 하에 다음의 변환을 사용할 수 있습니다.

\[\boldsymbol{Ax} = \boldsymbol{b} \iff \boldsymbol{A}^\top \boldsymbol{Ax} = \boldsymbol{A}^\top \boldsymbol{b} \iff \boldsymbol{x} = (\boldsymbol{A}^\top\boldsymbol{A})^{-1}\boldsymbol{A}^\top\boldsymbol{b} \tag{2.59}\]

그리고 Moore-Penrose pseudo-inverse(무어-펜로즈 유사 역행렬) $(\boldsymbol{A}^\top\boldsymbol{A})^{-1}\boldsymbol{A}^\top$ 를 사용하여 해를 구할 수 있습니다. 이러한 접근 방법의 단점은 행렬-행렬 곱셈과 $\boldsymbol{A}^\top\boldsymbol{A}$ 의 역행렬을 구하는데 많은 연산이 필요하다는 것입니다. 게다가, 수치적 정밀도 때문에 일반적으로 역행렬이나 유사역행렬을 계산하는 것이 권장되지 않습니다.

가우스 소거법(gaussian elimination)은

• 행렬식(determinants)를 계산할 때 (4.1장)
• 벡터 집합이 선형 독립이라는 것을 확인할 때 (2.5장)
• 역행렬을 구할 때 (2.2.2장)
• 벡터 공간(vector space)의 기저(basis)를 결정할 때 (2.6.2장)

할 때 중요한 역할을 합니다. 가우스 소거법은 수천 개의 변수가 있는 연립선형방정식을 푸는데 직관적이고 유용한 방법이지만, 수백만 개의 변수가 있는 경우에는 필요한 연산의 수가 너무 많아지기 때문에 비효율적, 비현실적 입니다.

실제로 많은 선형연립방정식은 Richardson method, Jacobi method, Gauss-Seidel method, Successive over-relaxation method와 같은 반복법(stationary iterative methods), 또는 Conjugate gradients, Generalized minimal residual, Biconjugate gradient와 같은 Krylov subspace methods를 통해 간접적으로 해를 구합니다.

$\boldsymbol{x}_{\ast}$ 를 $\boldsymbol{Ax} = \boldsymbol{b}$ 의 해라고 할 때, 반복법의 핵심은 모든 반복에서 해에 수렴하도록 적절한 $\boldsymbol{C}$ 와 $\boldsymbol{d}$ 에 대해 아래와 같은 같은 형태의 반복을 설정하는 것입니다.

\[\boldsymbol{x}^{(k+1)} = \boldsymbol{Cx}^{(k)} + \boldsymbol{d} \tag{2.60}\]

3.1장에서는 벡터 간의 유사성을 계산할 수 있는 norm($\|\cdot\|$)에 대해 살펴봅니다.