가우스 소거법(Gaussian elimination)
수학이야기 2015. 4. 29. 15:16미지수가 같은 1차 연립방정식은 하나의 체계를 이룬다. 1차 연립방정식이 이루고 있는 체계를 연구하는 것이 선형대수(Linear Algebra)다.
먼저 연립방정식을 쉽게 풀어보자.
x+3y−2z=53x+5y+6z=72x+4y+3z=8
첫째 식에서 x=5+2z−3y을 나머지 식에 대입한다.
−4y+12z=−8−2y+7z=−2
다시 정리하여 y=2+3z를 대입하여 z=2를 구한다.
x=5+2z−3yy=2+3zz=2
연립방정식은 다음과 같은 방법으로 푼다.1. 방정식의 순서를 바꾼다.
2. 양변에 0이 아닌 상수를 곱한다.
3. 양변에 상수를 곱한 방정식을 더한다.
위 연립방정식을 행렬로 나타내면 아래와 같다.
(13−2356243)(xyz)=(578)
풀이 과정을 확장된 행렬로 나타내면 왼쪽 행렬을 단위행렬로 만드는 것과 같다.
아래와 같은 행 연산으로 해가 달라지지 않는다. 이 방법이 가우스 소거법이다.1. 행렬의 두 행을 바꾼다. Eij : i행과 j행을 바꾼다.
2. 한 행의 모든 성분에 0이 아닌 상수를 곱한다. Ei(c) : i행에 상수 c를 곱한다. (단, c≠0)
3. 상수를 곱한 행을 다른 행에 더한다. Eij(d) : j행에 상수 d를 곱해서 i행에 더한다. (단, d≠0)
이제 가우스 소거법으로 문제를 풀어보자. 미지수 x,y,z는 별다른 역할을 하지 않고 자리만 차지하고 있다.
[13−2535672438]
[13−2535672438]E21(−3)∼[13−250−412−82438]E31(−2)∼[13−250−412−80−27−2]E2(−14)∼[13−2501−320−27−2]E32(2)∼[13−2501−320012]E23(3)∼[13−2501080012]E13(2)∼[130901080012]E12(−3)∼[100−1501080012]
마지막을 정리하여 아래와 같은 해를 구할 수 있다.
x=−15, y=8, z=2
이 가우스 소거법을 이용하여 역행렬을 구한다.
A=(2−10−12−10−12)
의 역행렬을 A−1라고 하면 아래와 같이 곱해서 단위행렬 I가 되는 행렬이다.
AA−1=A−1A=I
AA−1=(2−10−12−10−12)(a11a12a13a21a22a23a31a32a33)=(100010001)
[A|I]=[2−10100−12−10100−12001]
[I|A−1]=[10034121401012112001141234]
번거롭지만 아래를 가우스 소거법으로 정리하면 3차 행렬의 역행렬을 구할 수 있다.
[A|I]=[a11a12a13100a21a22a23010a31a32a33001]
편의를 위해 행렬 A에서 i행, j열을 지운 행렬을 Mij라고 하자. 참고 작은(minor) 행렬
∼[a11a12a131000|M33||M32|−a21a1100|M23||M22|−a310a11]
∼[a11a12a131000|M33||M32|−a21a11000|M33||M22|−|M23||M32|−a31|M33|+a21|M23|−a11|M23|a11|M33|]
여기서 잠깐 숨을 고르며 아래를 계산해보자.
|M33||M22|−|M23||M32|
=(a11a22−a12a21)(a11a33−a13a31)−(a11a32−a31a12)(a11a23−a13a21)
=a11a22a11a33−a11a22a13a31−a12a21a11a33+a12a21a13a31
−(a11a32a11a23−a11a32a13a21−a31a12a11a23+a31a12a13a21)
=a11[a11(a22a33−a32a23)−a12(a21a33−a31a23)+a13(−a22a31+a32a21)]
=a11(a11|M11|−a12|M12|+a13|M13|)
여기서 det(A)=a11|M11|−a12|M12|+a13|M13|로 놓기로 하자. 한편
−a31|M33|+a21|M23|
=−a31(a11a22−a12a21)+a21(a11a32−a12a31)
=a11|M13|이다.
∼[a11a12a131000|M33||M32|−a21a11000a11det(A)a11|M13|−a11|M23|a11|M33|]
∼[a11a12a131000|M33||M32|−a21a110001|M13|det(A)−|M23|det(A)|M33|det(A)]
∼[a11a12a131000|M33|0−a21−|M32||M13|det(A)a11+|M32||M23|det(A)−|M32||M33|det(A)001|M13|det(A)−|M23|det(A)|M33|det(A)]
위에서
|M33||M22|−|M23||M32|=a11det(A)
임을 활용하면 마무리 할 수 있다.
대각선(trace) 위 쪽 성분을 모두 0으로 만들어 보자. 지저분하지만 마무리하면 아래와 같이 역행렬을 구할 수 있다.
A−1=(a11a12a13a21a22a23a31a32a33)−1=1det(A)(A11A12A13A21A22A23A31A32A33)T=1det(A)(A11A21A31A12A22A32A13A23A33)
성분은 아래와 같은 행렬을 나머지 인자(cofactor) 행렬이라고 하고 이 행렬을 행과 열을 바꾼 전치(Transpose) 행렬을 수반(Adjugate or Adjoint) 행렬로 부른다.
Aij=(−1)i+j|Mij|
cofactormatrixofA=(A11A12A13A21A22A23A31A32A33)
adj(A)=(A11A21A31A12A22A32A13A23A33)
다시 적으면 A−1=1det(A)adj(A)
더 깔끔한 방법이 있으나 설명하자면 너무 길어서 생략. 궁금하면 선형대수를 공부하기를....
det(A)=|a11a12a13a21a22a23a31a32a33|=a11|a22a23a32a33|−a12|a21a23a31a33|+a13|a21a22a31a32|
위 행렬식은 묶는 방법을 달리하면 아래와 같이 여러 가지로 적을 수 있다. 행렬식을 쉽게 기억하기 위한 Rule of Sarrus이 있다.
det(A)=a11|M11|−a12|M12|+a13|M13|=a11|M11|−a21|M21|+a31|M31|=⋮=a31|M31|−a32|M32|+a33|M33|
행렬식을 다시 정리하면 a11a22a33+a12a23a31+a13a21a32−a13a22a31−a11a23a32−a12a21a33인데 아래 그림에서 실선은 + 점선은 −로 기억하면 된다.
n차 행렬에서 행렬식을 더욱 엄밀하게 정의한다면 아래와 같다.
det(A)=∑σ∈Snsgn(σ)n∏i=1aiσi
sgn(σ)=(−1)N(σ)이다. 여기서 σ는 {1,2,3,⋯,n}으로 이루어진 순열(permutation)이고 N(σ)는 σ에 따라 차례가 바뀌는 i<j 일 때, σ(i)>σ(j)인 순서쌍 (i,j)의 개수다.
연립방정식의 해를 쉽게 계산할 수 있는 크래머 공식(Cramer's rule)을 기억해 두자.
x+3y−2z=53x+5y+6z=72x+4y+3z=8
x=|53−2756843||13−2356243|,y=|15−2376283||13−2356243|,z=|135357248||13−2356243|
수학이야기님의
글이 좋았다면 응원을 보내주세요!