8장. 가우스 소거

요약

소거의 아이디어와 피벗·승수, 3×3 예제, 첨가행렬과 기본 행 연산, 행 교환과 특이한 경우, 소거행렬과 치환행렬, 계산량과 피벗으로 구하는 행렬식

미지수가 수백 개인 연립방정식을 사람이나 컴퓨터가 실제로 어떻게 풀까요? 답은 고등학교에서 배운 소거법을 체계적으로 하는 가우스 소거입니다. 이 장에서는 소거를 행렬로 정리해, 어떤 순서로 무엇을 빼는지, 언제 행을 바꿔야 하는지, 계산이 얼마나 드는지 봅니다. 컴퓨터의 연립방정식 풀이와 9장의 LU 분해의 바탕입니다.

8.1 큰 연립방정식의 풀이

질문. 미지수 3개, 식 3개짜리 연립방정식은 손으로 풀 수 있습니다. 미지수 1000개짜리라면? 컴퓨터는 어떤 순서로 계산할까요? 그리고 해가 없거나 무수히 많은 경우를 계산 도중에 어떻게 알아챌까요?

1부에서는 연립방정식 $A\mathbf{x} = \mathbf{b}$ 를 그림으로 보았습니다. 2부는 계산으로 시작합니다. 이 장의 방법인 가우스 소거(Gaussian elimination)는 중학교에서 배운 “한 식에서 다른 식의 배수를 빼서 미지수를 없애기”를 체계화한 것입니다. 체계화하면 두 가지를 얻습니다.

몇 개의 미지수든 똑같은 절차로 풀립니다. 그래서 컴퓨터가 쓸 수 있습니다.
절차가 어디서 멈추는지를 보면 해가 하나인지, 없는지, 무수히 많은지가 드러납니다.

8.2 소거의 아이디어

예제 8.1.

\begin{cases} x - 2y = 1 \\ 3x + 2y = 11 \end{cases}

둘째 식에서 첫째 식의 3배를 빼면 $x$ 가 사라집니다.

\begin{cases} x - 2y = 1 \\ \phantom{3x + {}} 8y = 8 \end{cases}

이제 아래에서부터 풉니다. 둘째 식에서 $y = 1$ , 첫째 식에 넣어 $x = 3$ 입니다.

이 계산에 쓰인 말을 정해 둡시다.

첫째 식의 $x$ 계수 1을 피벗(pivot)이라 합니다. 피벗은 아래쪽 식에서 그 미지수를 없애는 데 쓰는 기준입니다.
둘째 식에서 첫째 식을 몇 배 뺐는지( $\ell_{21} = 3$ )를 승수(multiplier)라 합니다. 승수 = (없앨 계수) ÷ (피벗)입니다.
소거 후 둘째 식의 $y$ 계수 8이 둘째 피벗입니다.
소거가 끝나면 계수가 계단 모양(위삼각)이 됩니다. 아래에서부터 차례로 푸는 것을 후진대입(back substitution)이라 합니다.

$두 그림. (a) 소거 전: 직선 x − 2y = 1과 3x + 2y = 11이 점 (3, 1)에서 만납니다. (b) 소거 후: 둘째 직선이 수평선 8y = 8로 바뀌었고, 두 직선은 여전히 (3, 1)에서 만납니다.$

그림 8.1. 소거하면 둘째 직선이 수평선으로 바뀝니다. 직선은 달라졌지만 교점은 그대로입니다.

그림 8.1처럼 소거는 방정식(직선)을 바꿉니다. 그러나 교점, 즉 해는 바꾸지 않습니다. 이것이 소거가 정당한 이유이며 8.4절에서 증명합니다.

8.3 3 × 3 예제

예제 8.2.

\begin{aligned} 2x + 4y - 2z &= 2 \\ 4x + 9y - 3z &= 8 \\ -2x - 3y + 7z &= 10 \end{aligned}

1단계 (첫째 열 소거). 피벗은 2. 승수 $\ell_{21} = 4/2 = 2$ , $\ell_{31} = -2/2 = -1$ .

식2 $- 2\times$ 식1: $y + z = 4$
식3 $- (-1)\times$ 식1 (즉 식3 + 식1): $y + 5z = 12$

2단계 (둘째 열 소거). 새 식2의 $y$ 계수 1이 둘째 피벗. 승수 $\ell_{32} = 1/1 = 1$ .

식3 $- 1\times$ 식2: $4z = 8$

결과는 위삼각 꼴입니다.

\begin{aligned} 2x + 4y - 2z &= 2 \\ y + z &= 4 \\ 4z &= 8 \end{aligned}

피벗은 2, 1, 4입니다. 후진대입: $z = 2$ , $y = 4 - 2 = 2$ , $2x = 2 - 8 + 4 = -2$ 에서 $x = -1$ .

검산: 원래 둘째 식 $-4 + 18 - 6 = 8$ , 셋째 식 $2 - 6 + 14 = 10$ . 해는 $(x, y, z) = (-1, 2, 2)$ 입니다.

검산은 반드시 원래 식에 대해 합니다. 소거 중에 실수했다면 소거 후의 식은 이미 틀려 있으므로, 거기에 넣어 맞아도 의미가 없습니다.

8.4 첨가행렬과 행 연산

식을 매번 $x, y, z$ 와 함께 쓰는 것은 번거롭습니다. 계수와 우변만 적으면 충분합니다.

정의 8.3 (첨가행렬). 연립방정식 $A\mathbf{x} = \mathbf{b}$ 에 대해 $A$ 의 오른쪽에 $\mathbf{b}$ 를 붙인 행렬 $\left[\, A \mid \mathbf{b} \,\right]$ 를 첨가행렬(augmented matrix)이라 합니다.

예제 8.2의 소거를 첨가행렬로 쓰면

\left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 4 & 9 & -3 & 8 \\ -2 & -3 & 7 & 10 \end{array}\right] \to \left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ 0 & 1 & 5 & 12 \end{array}\right] \to \left[\begin{array}{ccc|c} 2 & 4 & -2 & 2 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 4 & 8 \end{array}\right].

정의 8.4 (기본 행 연산). 행렬에 대한 다음 세 연산을 기본 행 연산(elementary row operations)이라 합니다.

(교체) 한 행에서 다른 행의 상수배를 뺍니다.
(교환) 두 행을 맞바꿉니다.
(스케일) 한 행에 0이 아닌 상수를 곱합니다.

정리 8.5 (행 연산은 해를 바꾸지 않습니다). 첨가행렬에 기본 행 연산을 하여 얻은 연립방정식은 원래 연립방정식과 해집합이 같습니다.

증명. 교체를 봅시다. 식 $i$ 를 “식 $i - \ell\times$ 식 $j$ ”로 바꾼다고 합시다. $\mathbf{x}$ 가 원래 연립방정식의 해이면 식 $i$ 와 식 $j$ 를 모두 만족하므로 새 식 $i$ 도 만족합니다. 따라서 원래 해는 새 연립방정식의 해입니다.

거꾸로, 새 연립방정식에 “새 식 $i + \ell\times$ 식 $j$ ”를 하면 원래 식 $i$ 가 돌아옵니다. 이것도 교체 연산이므로, 같은 논리로 새 해는 원래 연립방정식의 해입니다. 두 방향의 포함으로 해집합이 같습니다.

교환은 식의 순서만 바꾸므로 당연합니다. 스케일은 $c \ne 0$ 으로 나누면 되돌릴 수 있으므로 같은 논리가 적용됩니다. ■

증명의 핵심은 세 연산이 모두 되돌릴 수 있다는 것입니다. 스케일에서 $c \ne 0$ 을 요구하는 이유도 이것입니다. 0을 곱하면 식이 $0 = 0$ 이 되어 정보가 사라지고 되돌릴 수 없습니다.

▶ 문제 8.1–8.4

8.5 소거가 멈출 때

정의 8.6 (피벗). 소거 과정에서 각 단계의 기준이 되는, 그 열의 (현재 행 이하에서) 0이 아닌 첫 성분을 피벗(pivot)이라 합니다.

피벗 자리에 0이 오면 그 수로 나눌 수 없어 소거가 멈춥니다. 두 가지 경우가 있습니다.

8.5.1 일시적인 멈춤: 행 교환으로 해결

예제 8.7.

\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 2 & 4 & 1 & 5 \\ 0 & 1 & 3 & 4 \end{array}\right] \xrightarrow{\text{식2} - 2\,\text{식1}} \left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 0 & -1 & -1 \\ 0 & 1 & 3 & 4 \end{array}\right].

둘째 피벗 자리가 0입니다. 그러나 그 아래 셋째 행에 0이 아닌 수 1이 있습니다. 두 행을 바꾸면 소거가 계속됩니다.

\xrightarrow{\text{행2} \leftrightarrow \text{행3}} \left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 1 & 3 & 4 \\ 0 & 0 & -1 & -1 \end{array}\right].

피벗은 $1, 1, -1$ 이고 후진대입으로 $z = 1$ , $y = 1$ , $x = 0$ 입니다.

8.5.2 완전한 멈춤: 특이한 경우

예제 8.8.

\left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 1 & 2 & 3 & 5 \\ 2 & 3 & 4 & b_3 \end{array}\right] \to \left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & 1 & 2 & 3 \\ 0 & 1 & 2 & b_3 - 4 \end{array}\right] \to \left[\begin{array}{ccc|c} 1 & 1 & 1 & 2 \\ 0 & 1 & 2 & 3 \\ 0 & 0 & 0 & b_3 - 7 \end{array}\right].

셋째 피벗 자리가 0이고, 아래에 바꿀 행도 없습니다. 마지막 식은 $0x + 0y + 0z = b_3 - 7$ 입니다.

$b_3 \ne 7$ 이면 $0 =$ (0이 아닌 수)가 되어 해가 없습니다.
$b_3 = 7$ 이면 마지막 식은 $0 = 0$ 으로 아무 정보가 없습니다. $z$ 를 자유롭게 $t$ 로 정하면 $y = 3 - 2t$ , $x = 2 - y - z = -1 + t$ 이므로 해가 무수히 많습니다: $(x, y, z) = (-1 + t, 3 - 2t, t)$ .

이 예의 행렬은 셋째 행이 (첫째 행) + (둘째 행)입니다. 셋째 식이 새로운 정보를 주지 못하고, 앞의 두 식과 모순되거나( $b_3 \ne 7$ ) 그냥 반복될 뿐입니다( $b_3 = 7$ ). 그림으로는 세 평면이 한 점에서 만나지 않습니다. 6장의 말로는 행렬식이 0이고, 3장의 말로는 세 열이 한 평면 위에 있어 span이 $\mathbb{R}^3$ 이 되지 못합니다.

직관. $n \times n$ 행렬 $A$ 의 소거 결과는 두 가지 중 하나입니다.

정칙(nonsingular): 행 교환을 허용하면 피벗이 $n$ 개 모두 나옵니다. 모든 $\mathbf{b}$ 에 대해 해가 정확히 하나입니다.
특이(singular): 피벗이 $n$ 개보다 적습니다. $\mathbf{b}$ 에 따라 해가 없거나 무수히 많습니다.

피벗이 몇 개 나오는지가 행렬의 본질적인 정보입니다. 이 개수를 랭크라 하며 11장의 주제입니다.

▶ 문제 8.5–8.8

8.6 소거를 행렬곱으로 쓰기

소거의 각 단계는 행렬을 왼쪽에서 곱하는 것으로 쓸 수 있습니다. 5장에서 왼쪽에 곱하는 행렬은 행들의 일차결합을 만든다고 했습니다(정리 5.5의 (3)).

정의 8.9 (소거행렬). $i \ne j$ 에 대해 단위행렬의 $(i, j)$ 성분을 $-\ell$ 로 바꾼 행렬을 $E_{ij}$ 라 합시다. $E_{ij}A$ 는 $A$ 의 제 $i$ 행에서 제 $j$ 행의 $\ell$ 배를 뺀 행렬입니다. 이런 행렬을 소거행렬(elimination matrix)이라 합니다.

예제 8.10. $E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$ 이면

E_{21}\begin{bmatrix} 2 & 4 & -2 \\ 4 & 9 & -3 \\ -2 & -3 & 7 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ -2 & -3 & 7 \end{bmatrix}.

$E_{21}$ 의 제2행 $(-2, 1, 0)$ 은 “행1의 $-2$ 배 + 행2”를 뜻합니다.

예제 8.2의 소거 전체는

E_{32}E_{31}E_{21}A = U = \begin{bmatrix} 2 & 4 & -2 \\ 0 & 1 & 1 \\ 0 & 0 & 4 \end{bmatrix}

입니다. 여기서 $E_{31}$ 은 $(3, 1)$ 성분이 $+1$ , $E_{32}$ 는 $(3, 2)$ 성분이 $-1$ 입니다. 행렬 순서에 주의합시다. 가장 먼저 한 $E_{21}$ 이 $A$ 에 가장 가깝습니다.

정의 8.11 (치환행렬). 단위행렬의 행 순서를 바꾼 행렬을 치환행렬(permutation matrix)이라 합니다. $PA$ 는 $A$ 의 행 순서를 같은 방식으로 바꾼 행렬입니다.

예를 들어 $P_{23} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$ 은 행2와 행3을 바꿉니다(문제 5.3에서 $2 \times 2$ 경우를 보았습니다).

소거행렬과 치환행렬은 모두 되돌릴 수 있습니다. $E_{ij}$ 가 한 일(행 $j$ 의 $\ell$ 배 빼기)은 행 $j$ 의 $\ell$ 배를 다시 더하면 되돌아갑니다. 이 관찰이 9장에서 $A = LU$ 분해로 이어집니다.

▶ 문제 8.9–8.10

8.7 계산량과 행렬식

8.7.1 소거의 계산량

$n \times n$ 행렬에서 첫째 열을 소거하려면 아래 $n - 1$ 개 행 각각에서 $n$ 개쯤의 성분을 고쳐야 하므로 약 $n^2$ 번의 곱셈이 필요합니다. 둘째 열은 약 $(n - 1)^2$ 번, $\ldots$ . 합하면

n^2 + (n - 1)^2 + \cdots + 1^2 = \frac{n(n + 1)(2n + 1)}{6} \approx \frac{n^3}{3}.

(문제 1.8의 공식입니다.) 후진대입은 약 $\frac{n^2}{2}$ 번으로 훨씬 적습니다.

$n = 1000$ 이면 약 $3.3 \times 10^8$ 번의 곱셈입니다. 오늘날 컴퓨터는 1초 안에 끝냅니다. 한편 15장에서 볼 크래머 공식을 그대로 쓰면 $n!$ 에 비례하는 계산이 필요한데, $1000!$ 은 $10^{2567}$ 보다 큽니다. 이론적으로 아름다운 공식과 실제로 쓸 수 있는 알고리즘은 다를 수 있습니다.

8.7.2 소거로 행렬식 구하기

6장에서 층밀림은 넓이와 부피를 바꾸지 않는다고 했습니다. 교체 연산(한 행에서 다른 행의 배수를 빼기)은 층밀림입니다. 그러므로 교체 연산만으로 $A$ 를 $U$ 로 만들었다면 $\det A = \det U$ 이고, 위삼각행렬의 행렬식은 대각성분의 곱이므로

\det A = (\text{피벗들의 곱}).

행 교환이 있었다면 교환할 때마다 부호가 바뀝니다. 예제 8.2에서 $\det A = 2 \cdot 1 \cdot 4 = 8$ 입니다.

이 사실은 15장에서 행렬식의 성질로부터 증명합니다. 컴퓨터가 행렬식을 계산하는 방법도 바로 이것입니다.

▶ 문제 8.11–8.12

쓰이는 곳. 회로 해석, 구조물의 힘 계산, 유한요소법처럼 큰 연립방정식이 나오는 곳에서 컴퓨터가 쓰는 기본 알고리즘입니다. 계산량이 약 $\frac{2}{3}n^3$ 이라는 것은 '변수가 두 배면 시간은 여덟 배'라는 감각으로 쓰입니다.

이 장의 요약

가우스 소거: 피벗 아래 성분을 (승수 = 성분/피벗)×피벗 행을 빼서 없앱니다. 위삼각 꼴이 되면 후진대입합니다.
기본 행 연산(교체, 교환, 0이 아닌 수의 스케일)은 되돌릴 수 있으므로 해를 바꾸지 않습니다.
피벗 자리가 0이면 아래 행과 교환합니다. 교환할 행이 없으면 특이 행렬이고, 해가 없거나 무수히 많습니다.
소거는 왼쪽에서 소거행렬 $E_{ij}$ 와 치환행렬 $P$ 를 곱하는 것입니다.
계산량은 약 $n^3/3$ . $\det A$ 는 피벗의 곱(행 교환마다 부호 변경).

문제

8.1 [계산] · 확인 문제

가우스 소거와 후진대입으로 풉니다. 피벗과 승수를 모두 적고, 원래 식에 대입해 검산합니다. (a) $2x + 3y = 8$ , $4x + 7y = 18$ (b) $x + y + z = 6$ , $2x + 3y + z = 11$ , $x - y + 2z = 5$

	$x$	$y$	$z$
(a)	[?]	[?]	없음
(b)	[?]	[?]	[?]

정답

풀이

(a) $\ell_{21} = 2$ . 식2 $- 2\times$ 식1: $y = 2$ . 피벗 2, 1. 후진대입 $x = (8 - 6)/2 = 1$ . 검산: $4 + 14 = 18$ .

(b) $\ell_{21} = 2$ , $\ell_{31} = 1$ : $y - z = -1$ , $-2y + z = -1$ . $\ell_{32} = -2$ : 식3 $+ 2\times$ 식2: $-z = -3$ . 피벗 $1, 1, -1$ . $z = 3$ , $y = 2$ , $x = 1$ . 검산: $2 + 6 + 3 = 11$ , $1 - 2 + 6 = 5$ .

8.2 [계산] · 확인 문제

다음 첨가행렬이 나타내는 연립방정식을 소거로 풉니다.

\left[\begin{array}{ccc|c} 1 & -1 & 0 & 1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & 1 \end{array}\right]

$x$	$y$	$z$
[?]	[?]	[?]

정답

4
3
2

풀이

행2 + 행1: $(0, 1, -1 \mid 1)$ . 행3 + 행2: $(0, 0, 1 \mid 2)$ . $z = 2$ , $y = 1 + 2 = 3$ , $x = 1 + 3 = 4$ . 검산: $-4 + 6 - 2 = 0$ , $-3 + 4 = 1$ .

8.3 [계산] · 확인 문제

$A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 2 \\ 1 & 2 & 3 \end{bmatrix}$ 을 위삼각행렬 $U$ 로 소거합니다. 승수 $\ell_{21}, \ell_{31}, \ell_{32}$ 와 피벗을 모두 적습니다.

$\ell_{21}$	$\ell_{31}$	$\ell_{32}$	첫째 피벗	둘째 피벗	셋째 피벗
[?]	[?]	[?]	[?]	[?]	[?]

정답

풀이

$\ell_{21} = 1$ , $\ell_{31} = 1$ : 행2 → $(0, 1, 1)$ , 행3 → $(0, 1, 2)$ . $\ell_{32} = 1$ : 행3 → $(0, 0, 1)$ . $U = \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$ , 피벗 1, 1, 1.

8.4 [증명]

식 하나에 상수 $c \ne 0$ 을 곱해도 해집합이 바뀌지 않음을 보입니다. $c = 0$ 을 허용하면 해집합이 바뀔 수 있음을 예를 들어 보입니다.

풀이

$\mathbf{x}$ 가 식 $\mathbf{r} \cdot \mathbf{x} = b$ 를 만족하면 $c\mathbf{r} \cdot \mathbf{x} = cb$ 도 만족합니다. 역으로 $c\mathbf{r} \cdot \mathbf{x} = cb$ 이면 양변을 $c \ne 0$ 으로 나누어 원래 식이 나옵니다. $c = 0$ 이면: $x = 1$ 의 해집합은 $\{1\}$ 인데 0을 곱한 $0x = 0$ 의 해집합은 $\mathbb{R}$ 입니다.

8.5 [계산] · 확인 문제

행 교환이 필요한 연립방정식입니다. 소거로 풉니다.

\left[\begin{array}{ccc|c} 0 & 1 & 2 & 3 \\ 1 & 1 & 1 & 2 \\ 2 & 1 & 3 & 4 \end{array}\right]

$x$	$y$	$z$
[?]	[?]	[?]

정답

0
1
1

풀이

행1 ↔ 행2: $(1, 1, 1 \mid 2)$ ; $(0, 1, 2 \mid 3)$ ; $(2, 1, 3 \mid 4)$ . 행3 $- 2$ 행1: $(0, -1, 1 \mid 0)$ . 행3 + 행2: $(0, 0, 3 \mid 3)$ . $z = 1$ , $y = 1$ , $x = 0$ . 검산: $0 + 1 + 2 = 3$ , $0 + 1 + 3 = 4$ .

8.6 [계산] · 확인 문제

$A = \begin{bmatrix} a & 2 \\ a & a \end{bmatrix}$ 의 소거가 실패하는(피벗이 2개 나오지 않는) $a$ 를 모두 구합니다.

작은 $a$	큰 $a$
[?]	[?]

정답

0
2

풀이

첫째 피벗 $a$ . $a \ne 0$ 이면 행2 $-$ 행1 $= (0, a - 2)$ 이므로 둘째 피벗 $a - 2$ . 실패: $a = 0$ (첫째 열이 모두 0) 또는 $a = 2$ . 확인: $\det = a^2 - 2a = a(a - 2)$ .

8.7 [계산]

$x + 2y = b_1$ , $2x + 4y = b_2$ 가 해를 갖기 위한 $b_1, b_2$ 의 조건을 구합니다. 해가 있을 때 해는 몇 개일까요? 그림으로 설명합니다.

풀이

식2 $- 2\times$ 식1: $0 = b_2 - 2b_1$ . 조건: $b_2 = 2b_1$ . 이때 해는 직선 $x + 2y = b_1$ 위의 모든 점으로 무수히 많습니다. 그림: 두 직선이 평행하며, $b_2 = 2b_1$ 이면 겹치고 아니면 만나지 않습니다.

8.8 [계산]

(a) $x + y + z = 1$ , $x + 2y + 3z = 2$ , $2x + 3y + 4z = 3$ 의 해를 모두 구합니다. (b) 셋째 식의 우변 3을 4로 바꾸면 어떻게 될까요?

풀이

(a) 행2 $-$ 행1: $(0, 1, 2 \mid 1)$ . 행3 $- 2$ 행1: $(0, 1, 2 \mid 1)$ . 행3 $-$ 행2: $(0, 0, 0 \mid 0)$ . $z = t$ , $y = 1 - 2t$ , $x = 1 - y - z = t$ . 해: $(t, 1 - 2t, t)$ .

(b) 마지막 행이 $(0, 0, 0 \mid 1)$ , 즉 $0 = 1$ 이 되어 해가 없습니다.

8.9 [계산]

문제 8.3의 소거에 쓰인 $E_{21}, E_{31}, E_{32}$ 를 씁니다. $E_{32}E_{31}E_{21}A = U$ 임을 확인합니다.

풀이

E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}, \quad E_{31} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}, \quad E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix}.

차례로 곱하면 문제 8.3의 $U$ 가 나옵니다.

8.10 [도전]

문제 8.9의 행렬들에 대해 (a) $E = E_{32}E_{31}E_{21}$ 을 계산합니다. $E$ 의 성분에 승수들이 그대로 나타날까요? (b) 각 $E_{ij}$ 의 역행렬(한 일을 되돌리는 행렬)을 쓰고, $L = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}$ 을 계산합니다. $L$ 의 성분은 승수들과 어떤 관계일까요? (이 관찰이 9장의 $A = LU$ 분해입니다.)

풀이

(a) $E_{31}E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}$ . 여기에 $E_{32}$ 를 곱하면 셋째 행이 $(-1, 0, 1) - (-1, 1, 0) = (0, -1, 1)$ 이 되어 $E = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & -1 & 1 \end{bmatrix}$ . $(3, 1)$ 자리에 승수 $\ell_{31} = 1$ 의 흔적이 없습니다. 승수가 섞입니다.

(b) $E_{ij}^{-1}$ 은 $-\ell$ 을 $+\ell$ 로 바꾼 것. $L = E_{21}^{-1}E_{31}^{-1}E_{32}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{bmatrix}$ . 승수 $\ell_{21} = 1$ , $\ell_{31} = 1$ , $\ell_{32} = 1$ 이 정확히 제자리에 있습니다.

8.11 [계산] · 확인 문제

문제 8.1(b)의 계수행렬의 행렬식을 피벗의 곱으로 구하고, 6.7절의 첫째 행 전개 공식으로 구한 값과 비교합니다.

정답

-1

풀이

피벗 $1, 1, -1$ 이므로 $\det = -1$ . 전개: $1(6 + 1) - 1(4 - 1) + 1(-2 - 3) = 7 - 3 - 5 = -1$ . 같습니다.

8.12 [도전]

대각선과 그 바로 위아래 대각선에만 0이 아닌 성분이 있는 $n \times n$ 행렬을 삼중대각행렬이라 합니다(문제 8.2의 행렬이 그 예). 삼중대각행렬을 소거할 때(행 교환이 필요 없다고 합시다) 필요한 곱셈·나눗셈의 횟수가 $n$ 에 비례함을 설명합니다. 일반 행렬의 $n^3/3$ 과 비교합니다.

풀이

각 단계에서 피벗 아래에 0이 아닌 성분은 하나뿐이므로 고칠 행은 하나입니다. 그 행에서도 바뀌는 성분은 피벗 열의 성분(0이 됨)과 바로 오른쪽 성분, 그리고 우변뿐입니다. 그래서 한 단계에 나눗셈 1번, 곱셈 2번 정도이고, $n - 1$ 단계이므로 전체가 $n$ 에 비례합니다. 후진대입도 각 행에서 미지수가 둘뿐이라 $n$ 에 비례합니다. $n = 1000$ 이면 몇천 번 대 $3 \times 10^8$ 번입니다. 행렬에 0이 많다는 구조를 이용하면 계산이 극적으로 줄어듭니다(30장).