Loading [MathJax]/jax/output/CommonHTML/jax.js
가우스 소거법(Gaussian elimination)::::수학과 사는 이야기

가우스 소거법(Gaussian elimination)

수학이야기 2015. 4. 29. 15:16
반응형

미지수가 같은 1차 연립방정식은 하나의 체계를 이룬다. 1차 연립방정식이 이루고 있는 체계를 연구하는 것이 선형대수(Linear Algebra)다.

먼저 연립방정식을 쉽게 풀어보자.

x+3y2z=53x+5y+6z=72x+4y+3z=8

첫째 식에서 x=5+2z3y을 나머지 식에 대입한다.

4y+12z=82y+7z=2

다시 정리하여 y=2+3z를 대입하여 z=2를 구한다.

x=5+2z3yy=2+3zz=2

연립방정식은 다음과 같은 방법으로 푼다.

1. 방정식의 순서를 바꾼다.

2. 양변에 0이 아닌 상수를 곱한다.

3. 양변에 상수를 곱한 방정식을 더한다.

위 연립방정식을 행렬로 나타내면 아래와 같다.

(132356243)(xyz)=(578)

풀이 과정을 확장된 행렬로 나타내면 왼쪽 행렬을 단위행렬로 만드는 것과 같다.

아래와 같은 행 연산으로 해가 달라지지 않는다. 이 방법이 가우스 소거법이다.

1. 행렬의 두 행을 바꾼다.                                             Eiji행과 j행을 바꾼다.          

2. 한 행의 모든 성분에 0이 아닌 상수를 곱한다.             Ei(c) : i행에 상수 c를 곱한다. (단, c0)

3. 상수를 곱한 행을 다른 행에 더한다.                          Eij(d) : j행에 상수 d를 곱해서 i행에 더한다.  (단, d0)

이제 가우스 소거법으로 문제를 풀어보자. 미지수 x,y,z는 별다른 역할을 하지 않고 자리만 차지하고 있다.

[132535672438]

[132535672438]E21(3)[1325041282438]E31(2)[1325041280272]E2(14)[132501320272]E32(2)[132501320012]E23(3)[132501080012]E13(2)[130901080012]E12(3)[1001501080012]

마지막을 정리하여 아래와 같은 해를 구할 수 있다.

x=15, y=8, z=2

이 가우스 소거법을 이용하여 역행렬을 구한다.

A=(210121012)

의 역행렬을 A1라고 하면 아래와 같이 곱해서 단위행렬 I가 되는 행렬이다.

AA1=A1A=I

AA1=(210121012)(a11a12a13a21a22a23a31a32a33)=(100010001)

[A|I]=[210100121010012001]

[I|A1]=[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|

=(a11a22a12a21)(a11a33a13a31)(a11a32a31a12)(a11a23a13a21)

=a11a22a11a33a11a22a13a31a12a21a11a33+a12a21a13a31

(a11a32a11a23a11a32a13a21a31a12a11a23+a31a12a13a21)

=a11[a11(a22a33a32a23)a12(a21a33a31a23)+a13(a22a31+a32a21)]

=a11(a11|M11|a12|M12|+a13|M13|)

여기서 det(A)=a11|M11|a12|M12|+a13|M13|로 놓기로 하자. 한편

a31|M33|+a21|M23|

=a31(a11a22a12a21)+a21(a11a32a12a31)

=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|0a21|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으로 만들어 보자. 지저분하지만 마무리하면 아래와 같이 역행렬을 구할 수 있다.

A1=(a11a12a13a21a22a23a31a32a33)1=1det(A)(A11A12A13A21A22A23A31A32A33)T=1det(A)(A11A21A31A12A22A32A13A23A33)

성분은 아래와 같은 행렬을 나머지 인자(cofactor) 행렬이라고 하고 이 행렬을 행과 열을 바꾼 전치(Transpose) 행렬을 수반(Adjugate or Adjoint) 행렬로 부른다.

Aij=(1)i+j|Mij|

cofactormatrixofA=(A11A12A13A21A22A23A31A32A33)

adj(A)=(A11A21A31A12A22A32A13A23A33)

다시 적으면 A1=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+a13a21a32a13a22a31a11a23a32a12a21a33인데 아래 그림에서 실선은 + 점선은 로 기억하면 된다.

 

n차 행렬에서 행렬식을 더욱 엄밀하게 정의한다면 아래와 같다.

det(A)=σSnsgn(σ)ni=1aiσi

sgn(σ)=(1)N(σ)이다. 여기서 σ{1,2,3,,n}으로 이루어진 순열(permutation)이고 N(σ)σ에 따라 차례가 바뀌는 i<j 일 때, σ(i)>σ(j)인 순서쌍 (i,j)의 개수다.  

연립방정식의 해를 쉽게 계산할 수 있는 크래머 공식(Cramer's rule)을 기억해 두자.

x+3y2z=53x+5y+6z=72x+4y+3z=8

x=|532756843||132356243|,y=|152376283||132356243|,z=|135357248||132356243|

Applications_of_linear_algebra.pdf
다운로드
Applied_Linear_Algebra_And_Matrix_Analysis_-_Thomas_S._Shor.pdf
다운로드

 

 

 

반응형

수학이야기님의
글이 좋았다면 응원을 보내주세요!