선형 연립일차방정식 2) 피벗과 소거법(Pivots and Elimination method)

연립방정식에 해와 이들을 행렬표현으로 나타냈을 때 수많은 논의들은 행렬의 피벗과 관련성이 있습니다. 피벗이 무엇인지 다루어 보도록 합시다.

---

1. 소거법과 피벗(pivot)

​

피벗이 무엇이다, 라고 말하는 방법은 굉장히 많습니다. 처음 공부하시는 분들은 이런 말을 들으면 당황하시겠지만 보통 수학 개념 용어들을 배울 때 정의를 깔고 시작하는 것과 다르게, 피벗과 랭크는 무작정 정의를 들으면 이해가 까다로울 뿐만 아니라 제 의미를 파악하지도 못할 겁니다.

​

저번 포스팅에서 예로 들었던, 중학교 수준에서 배우는 아래의 연립방정식을 봅시다.

 

$$ \left\{\begin{matrix}
x-2y=1\\ 
3x+2y=11
\end{matrix}\right.$$

 

이것을 소거법으로 풀 것입니다. 헌데 단순히 소거법으로 풀라고 한다면 사람에 따라 여러가지 방법을 쓸 것 같습니다. 위에 식에 3을 곱해 밑에 식을 뺄 수도 있고, 위에 식에 3을 곱해 밑에 식에서 뺄 수도 있고, 위에 식에 -3을 곱해 둘을 더할 수도 있고, 밑에 식에 1/3을 곱해 뺄 수도 있고, 밑에 식에 -1/3을 곱해 더할 수도 있고... 소거를 할 때는 결국 미지수 앞의 계수의 절댓값만 맞추어 주면 빼거나 더해 소거가 가능하다는 특징이 있습니다.

​

그런데 앞으로, 소거법을 적용하여 연립방정식을 풀 때 피벗(pivot)이란 녀석을 찾으려면 이렇게 막무가내로 숫자를 곱하는 것이 아니라, 정해진 숫자를 곱해 더하거나 빼기로 약속합니다. 이렇게 복잡하게 하는 이유는 다 랭크와 가역성, 대각화, LU분해 등등... 때문이라 지금 다 설명할 수는 없습니다. 먼저, 피벗의 딱딱한 정의는 아래와 같습니다. 

 

한 행에서 일차방정식의 첫번째 미지수 앞의 계수 or 기본행연산을 적용하여 행사다리꼴(REF)로 변형하였을 때 대각성분을 피벗(pivot)이라고 한다.

단, 다음의 주의사항에 주목한다.
​
① 피벗은 계수를 바꿔 미지수를 제거할 방정식의 미지수의 계수이다.
​
② 한 미지수에 대한 피벗은 1개이다. 즉 $n$개의 미지수를 포함한 연립방정식에서 피벗의 최대 개수는 $n$개이다.
​
③ 0은 피벗으로 취급하지 않는다. 피벗은 0이 될 수 없다.

 

기본행연산과 행사다리꼴(REF)에 대한 포스팅은 차후에 할 것이라 써 놓기만 했는데, 지금 다룰 내용은 아닙니다. 첫번째 pivot 의 정의에 주목해 주시기 바랍니다. 그런데 이걸 보면 이게 왜 어려울까 하는 생각이 들겁니다. 한 행에서 일차방정식의 첫번째 미지수 앞의 계수라고 했으니

 

$$ \left\{\begin{matrix}  
x-2y=1 \cdots \;(1)\\  
3x+2y=11 \cdots \;(2)  
\end{matrix}\right. $$

 

에서 1행의 첫번째 미지수의 계수는 1이고 2행의 첫번째 미지수 계수는 3이니 pivot 은 1,3 아닌가? 할 수 있는데, 그렇지 않습니다. ②를 보면, 미지수 하나에 대한 pivot 은 1개라고 했습니다. 결론부터 말하지만 1행에 대해서 미지수 x에 대한 pivot 은 1이 맞습니다. 그런데 pivot의 정의에 의하면 이 형태에서는 $y$의 pivot을 찾을 수 없고 $x$의 pivot만 2개인 것처럼 보입니다. 이러한 모순은 ①을 해석하면 되는데, $y$의 pivot 을 구하려면 소거를 한 번 해야 합니다. 여러분들은 아마 그냥 다이렉트로 (1)+(2)를 해서 $x$값을 구하겠지만 지금은 방정식의 해를 구하는 것이 아니라 pivot을 찾아야 하니 다른 방안 - 후술하겠지만 상삼각행렬을 구해야 함 - 을 고려할 것입니다.

(1)에 3을 곱하고 (2)에서 (1)을 뺀 것으로 (2)를 대체해 봅시다. $3x+2y=11$ 에서 $3x-6y=3$ 을 빼면 $8y=8$이니

 

$$ \left\{\begin{matrix} 
x-2y=1 \cdots \;(1)\\ 
8y=8 \cdots \;(3) 
\end{matrix}\right. $$

 

으로 연립방정식의 형태가 바뀝니다. 즉, (2)가 (3)으로 대체되고 미지수 $x$ part가 소거되어 $y$만 남게 되었고 이제 두번째 pivot을 말할 수 있습니다. 2행의 $y$에 대한 pivot 은 8입니다.

이 과정을 보면 굉장히 생소하고 까다롭게 느껴질 것입니다. 첫번째 pivot 은 그냥 1행에서 $x$의 계수를 읽으면 되지만 두번째 pivot 을 구하는 과정이 낯설죠. 익숙해지기 위해서 우선적으로 필요한 것은 소거를 어떻게 해야 하는지 명확한 기준을 세우는 것입니다. 앞으로 pivot 을 구하기 위한 소거는 다음과 같은 방법으로 합니다.

 

① 미지수를 소거할 방정식(pivot 을 찾을 방정식)을 고른다.
​
② 그 방정식의 소거할 미지수의 계수를 바로 위 방정식의 pivot 으로 나눈다. 이 값을 '승수(multiplier)'라 한다.
​
③ 위 방정식 양변에 '$-$승수' 를 곱하고 두 방정식을 더하여 대체한다. 그 때 소거된 방정식의 첫 미지수 계수가 구한 pivot 이다.
​
이 과정을 '소거(Elimination)', 방법을 '소거법(Elimination method)'라고 한다.

 

①에서 말하는 미지수를 소거할 방정식은 식 (2)를 가리키는 것으로, 식 (3)으로 만들어 $x$를 소거시키겠다는 뜻입니다.  그 다음 ②에서, 소거할 미지수의 계수는 3이기 때문에 3을 위 방정식 (1)의 pivot = 1로 나눕니다. 이 값 3/1=3이 승수(multiplier)입니다. 마지막으로 ③의 내용은 승수에 음의 기호를 붙인 -3을 (1)양변에 곱한 뒤 (2)와 더해, (3)을 만드라는 것입니다. 그러면 모든 과정이 끝납니다.

 

$$ \left\{\begin{matrix}
-3x+6y=-3 \cdots \;(1)\times (-3)\\
3x+2y=11 \cdots \;(2)\;\;\;\;\;\;\;\;
\end{matrix}\right. $$

$$ \mathrm{Substitute}\;(1)\times (-3)+(2)\;\;\rightarrow\;\;(3)
$$

$$ \left\{\begin{matrix}
x-2y=1 \cdots \;(1)\\
8y=8 \cdots \;(3)
\end{matrix}\right.$$

 

x항이 소거된 식 (3)에서 등장하는 첫 미지수 y의 계수를 8입니다. 이 8이 두번째 피벗(pivot)인 것입니다. 이 형태의 연립방정식을 이제 행렬로 바꿔보면, 특징이 있습니다. 바로 계수행렬 A가 상삼각행렬 U로 바뀝니다!

 

$$\left\{\begin{matrix}
x-2y=1 \cdots \;(1)\\
8y=8 \cdots \;(3)
\end{matrix}\right. \;\; \Rightarrow  \;\; \begin{pmatrix}
1 & -2\\ 
0 & 8
\end{pmatrix}\begin{pmatrix}
x\\ 
y
\end{pmatrix}\begin{pmatrix}
1\\ 
8
\end{pmatrix}\;\;\Leftrightarrow   \;\;U\mathbf{x}=\mathbf{b'}$$

 

이 예시 뿐만 아니라, 일반적으로 한 쌍의 해를 가지는 연립방정식의 행렬표현에서 소거법(Elimination)을 진행하면 $n$행 $n$열, 즉 대각성분의 위치에 pivot 들이 놓이며, 대각성분들 아래는 모두 0으로 채워진 상삼각행렬이 만들어집니다.

 

$$\mathrm{Elimination\;makes\;}A\mathbf{x}=\mathbf{b}\;\;\Rightarrow \;\;U\mathbf{x}=\mathbf{b'}$$

---

2. 0은 피벗이 될 수 없다.

 

1) 해가 존재하지 않는 경우(불능)

 

종종 연립방정식에서 한 쌍의 해를 얻는데 실패하는 경우가 발생합니다.

 

$$ \left\{\begin{matrix}
x-4y=5 \cdots \;(4)\\
3x-12y=10 \cdots \;(5)
\end{matrix}\right. \;\; \rightarrow \;\;\frac{1}{3}=\frac{-4}{-12}\neq \frac{5}{10}\;,\;\mathrm{No\;solution} $$

 

적어두었듯이 이 연립방정식은 중학생 수준에서 풀면 해가 존재하지 않습니다. 행관점에서 보았을 때 두 직선은 평행하고 y절편이 달라 만나는 교점이 단 한개도 없기 때문입니다. 이것을 행렬꼴로 보고 이 방정식에 대한 소거법을 진행하면 pivot 을 구할 수 없게 됩니다. 소거법을 적용하면 승수는 3/1=3이고 -3을 (4)에 곱한 뒤 (5)에 더해 (5)를 (6)으로 대체합니다.

 

$$ \left\{\begin{matrix}
x-4y=5\\ 
0y=-5 \cdots \;(6)
\end{matrix}\right. $$

 

이를 만족하는 해는 당연 존재하지 않으며, (6)에서 $y$의 계수는 0입니다. 그러나 pivot 은 0이 될 수 없다고 정의했으므로 이 행렬의 pivot 은 1개입니다.

 

 

2) 무수히 많은 해를 가지는 경우 (부정)

​

반면 두 직선이 $y$절편과 기울기가 모두 같다면 일치하는 관계를 가지고, 연립방정식의 해는 무수히 많아집니다.

$$ \left\{\begin{matrix}
x-4y=5 \cdots \;(4)\\
3x-12y=15 \cdots \;(7)
\end{matrix}\right. \;\; \rightarrow \;\;\frac{1}{3}=\frac{-4}{-12}= \frac{5}{15}\;,\;\mathrm{Infinitely\;many\;solution} $$

소거법을 적용하면, 해는 무수히 많지만 $y$의 계수가 0이니 두번째 pivot 은 값을 찾을 수 없습니다. 이 때도 pivot 의 개수는 1개입니다.

 

$$ \left\{\begin{matrix}
x-4y=5 \;\cdots \;(4)\\
0y=0 \;\;\;\;\cdots \;\;(8)
\end{matrix}\right. $$

---

3. 여러가지 사각행렬에 대한 pivot

 

위에서 설명한 방법은 정사각행렬이 아닌 행렬의 pivot 을 구할 때 난관에 봉착합니다. 열벡터나 행벡터 같은 하나의 행, 열을 가진 행렬이나 정사각행렬이 아닌 사각행렬에 대한 pivot 및 pivot 의 개수는 어떻게 구할까요? 정사각행렬이 아니라는 뜻은 다시 말하면 연립방정식에서 방정식의 개수(=행의 개수=$m$)이 미지수의 개수(=열의 개수=$n$)보다 작은 $m < n$ 과 같은 뜻입니다. 이는 중학교 수준의 연립방정식 단원에서도 다루지 않는 내용입니다. 이때부터는 결론적으로 말하면 행렬의 랭크와 기본행연산, 사다리꼴 행렬에 대한 기초 지식을 쌓은 다음 진행하는 것이 좋습니다. 간단하게 몇가지 특징만 보고 갑시다. 완전한 설명은 이후에 하겠습니다.

 

1) 행벡터, 열벡터 즉 1개의 행이나 열로 이루어진 행렬의 pivot 은 1개입니다. 1행의 첫 성분이 pivot 에 해당합니다.

 

$$ A=\begin{pmatrix}
3 & 4 & 2
\end{pmatrix}\;,\;\mathrm{(1st\;pivot)}=3 $$

 

2) 성분이 1개뿐인 행렬도 pivot 은 1개로 취급하고, 그 성분이 pivot 입니다.

 

$$ A=\left ( 4 \right )\;,\;\mathrm{(1st\;pivot)}=4 $$

 

3) $m \times n$ 행렬의 경우, 최대 $n$개의 pivot 을 가질 수 있고, pivot 을 구하려면 행사다리꼴 형태로 바꾸는 소거법을 진행하는 것이 좋습니다. 최대 $n$개라고 했지 항상 $n$개를 가지지 않아서 pivot 의 개수는 직접 구하기보다 행렬의 랭크와 같으므로 랭크를 먼저 구하는 것이 pivot 을 찾는데도 수월한 편입니다. 

$$ R=\begin{bmatrix}
3 & 2 &5 \\ 
0 & 0 & 0
\end{bmatrix}\;\;\mathrm{(Number\;of\;pivot)}=1\;,\;\;\mathrm{(first\;pivot)}=3 $$

 

이제 pivot 에 대한 이해는 어느 정도 감을 잡았을 것이라 믿습니다. 그러나 여전히 남아있는 질문이 있습니다. 

아직 일반적인 $m \times n$ 행렬의 pivot 구하기는 설명을 하지 않았는데, 이것은 랭크(rank)를 알아야 하므로 이 뒤로 논의를 넘기겠습니다.

 

pivot 을 배우는 보다 구체적인 이유는 연립방정식의 방정식 개수 $m$과 미지수 개수 $n$을 확장했을 때는 소거법의 계산 횟수가 급증하기 때문입니다. 이원연립일차방정식까지는 소거법으로 푸는 속도가 월등히 빠른데, $3\times 3$ 계수행렬을 포함한 연립방정식만 되더라도 기존의 방식이 점점 귀찮아지게 될 겁니다. 실은 pivot 을 포함한 상삼각행렬로 바꾸어 소거하는 방법을 '가우스 소거법(Gaussian Elimination)'이라 하고 행사다리꼴과 같은 행렬의 다른 주제와 연결되게 됩니다. 다음 시간부터 이들을 살펴보겠습니다.

 

[참고서적]

Introduction to Linear Algebra, Gilbert Strang, 5e