선형대수 02 - 연립선형방정식, 가우스 소거법, REF, 기본행연산

연립선형방정식(System of linear equations, SOLE)

  • Systems of linear equations, SOLE, 연립일차방정식, 연립선형방정식 ...

위 네가지는 모두 같은 뜻입니다.

선형대수의 가장 큰 목적 중 하나는 연립선형방정식을 푸는 것입니다.

a11x1+a12x2+...+a1nxn=b1a21x1+a22x2+...+a2nxn=b2am1x1+am2x2+...+amnxn=bma_{11} x_1 + a_{12} x_2 + ... + a_{1n} x_n = b_1 \\ a_{21} x_1 + a_{22} x_2 + ... + a_{2n} x_n = b_2 \\ \vdots \\ a_{m1} x_1 + a_{m2} x_2 + ... + a_{mn} x_n = b_m \\

n개의 미지수(n-unknown variables)m개의 방정식(m-equations)으로 이루어져있을 때, 우리는 방정식을 위와 같이 표시할 수 있습니다.

우리가 중학교 시절 배웠던 그 연립일차방정식과 같은겁니다!

이 경우에서 n개의 미지수와 m개의 방정식이 주어질 때,
방정식이라 함은, 미지수가 충족해야할 조건이라고 볼 수 있습니다.


그렇다면 이제 저 위의 연립방정식을 행렬의 형태로 바꾸어 줍시다.

행렬은 Ax=bAx=b의 형태로 나타납니다.

A=[a11a12a1na21a22a2nan1an2amn](mn)x=[x1x2xn](n1),b=[b1b2bn](m1)A = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{mn} \end{bmatrix} \in (m * n) \\ \\ x = \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} \in (n * 1), b = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix} \in (m * 1) \\ \\

여기서 A를 계수행렬(Coefficient Matrix)이라고 하고, b를 데이터 벡터(Data Vector)라고 합니다.

  • AAmm개의 행(m-row)과 nn개의 열(n-column)로 구성되어 있는 계수행렬이라고 부릅니다.
  • AA에서, (mn)(m * n)을 행렬의 차원(dimension)이라고 부릅니다.
  • xxnn개의 열(n-column)으로 이루어져 있고, 이는 열벡터(column vector)입니다.
  • bbmm개의 열(m-column)으로 이루어져 있고, 이는 열벡터(column vector)이고, 데이터 벡터(data vector)라고 부릅니다.

AA 행렬의 각 행별로, xx 행렬의 각 행에 대응되서 곱해집니다.
그 결과 아래와 같은 형태가 됩니다.

x1[a11a21am1]+x2[a12a22am2]++xn[a1na2namn]x_1 \begin{bmatrix} a_{11} \\ a_{21} \\ \vdots \\ a_{m1} \end{bmatrix} + x_2 \begin{bmatrix} a_{12} \\ a_{22} \\ \vdots \\ a_{m2} \end{bmatrix} + \cdots + x_n \begin{bmatrix} a_{1n} \\ a_{2n} \\ \vdots \\ a_{mn} \end{bmatrix}

결과적으로, 각각의 행은 방정식을 표시하고, 각각의 열은 미지변수에 대응한다고 생각하면 될 것 같습니다.


첨가행렬 (Augmented Matrix)

Augmented Matrix는 AA행렬과 bb행렬을 합쳐준 것이라고 보면됩니다. 즉, 연립일차방정식의 내용을 좌변 우변을 분리하지 않고 그대~로 행렬로 만들어 준 것이라고 생각하면 쉽습니다.

[A:b](m(n+1))[A:b] \in (m * (n + 1)) 라고 쓰고, A  partition  BA\;partition\;B 라고 읽는다. 한국어로는 첨가행렬이라고 하는 것 같습니다.

첨가행렬이 의미하는 것은 앞의 연립방정식과 같습니다. 단지 표현 방법의 차이입니다.

[A:b]=[a11a12a1nb1a21a22a2nb2b3an1an2amnbm](m(n+1))[A:b] = \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} & b_{1} \\ a_{21} & a_{22} & \cdots & a_{2n} & b_{2} \\ \vdots & \vdots & \ddots & \vdots & b_{3} \\ a_{n1} & a_{n2} & \cdots & a_{mn} & b_{m} \end{bmatrix} \in (m * (n + 1)) \\ \\

세 가지 경우에서 행렬을 구성해봅시다.

(a) x1=4,x2=2,x3=3x_1 = 4, x_2 = 2, x_3 = 3 (identity matrix, 단위 행렬) : 대각성분들이 모두 1을 가지고 있고, 나머지 성분이 모두 0인 경우 우리는 이를 단위 행렬이라고 부릅니다.

[100401020013]\begin{bmatrix} 1 & 0 & 0 & 4 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{bmatrix}

(b) 2x1=8,3x2=6,4x3=122x_1 = 8, 3x_2 = 6, 4x_3 = 12 (diagonal matrix, 대각 행렬) : 대각성분만이 0이 아니고, 나머지 성분이 모두 0인 경우 이를 대각 행렬이라고 부릅니다.

[2004030600412]\begin{bmatrix} 2 & 0 & 0 & 4 \\ 0 & 3 & 0 & 6 \\ 0 & 0 & 4 & 12 \end{bmatrix}

(c) x1+x2+x3=9,2x27x3=17,x3=3x_1 + x_2 + x_3 = 9, 2x_2 - 7x_3 = -17, x_3 = -3 (upper-triangular matrix, 상삼각행렬)

[1119027170013]\begin{bmatrix} 1 & 1 & 1 & 9 \\ 0 & 2 & -7 & -17 \\ 0 & 0 & 1 & -3 \end{bmatrix}

Upper-triangular-matrix는 해를 아래에서부터 위로 차례로 구해나갑니다. 이를 역대입(back-subtitution)해나간다고 합니다!

그래서, 우리는 Ax=bAx = b형태의 SOLE(연립일차방정식)을 Bx=cBx = c의 형태로 바꾸어줄 것입니다. 그리고 이 BB 행렬은 Upper-triangular-matrix(상삼각행렬)로 만드는 것입니다.

이 과정을 Gaussian Elimination (가우스 소거법)이라고 한다. 이제부터 살펴봅시다.


가우스 소거법 (Gauss Elimination)

  • Ax=bAx = b라는 연립방정식을 변형시켜서, Bx=cBx = c로 바꾼다.
  • Ax=bAx = bBx=cBx = c는 동치여야 한다.
  • BB라는 행렬이 upper-triangular-matrix여야 한다.

이를 가우스 소거법이라 합니다.

정방행렬(Square Matrix, 행과 열의 개수가 같은 행렬)과는 다른게 일반적인 사각행렬(Rectangle Matrix, 행과 열의 개수가 다른 행렬)에서는 Upper-triangular-matrix의 모습이 조금씩 달라질 수 있습니다.

[a11a12a13a21a22a23a31a32a33]\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \\ \end{bmatrix}

위와 같은 Square Matrix에서는 Upper-triangular-matrix가 예쁘게 잘 나옵니다.

[a11a12a13a14a15a21a22a23a24a25a31a32a33a34a35]\begin{bmatrix} a_{11} & a_{12} & a_{13} & a_{14} & a_{15} \\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25} \\ a_{31} & a_{32} & a_{33} & a_{34} & a_{35} \\ \end{bmatrix}

하지만 위와 같은 Rectangle Matrix에서는 Upper-triangular-matrix의 모양이 다양해집니다. (어떤 모양으로 대각선이 나올지 모르므로)

Upper-triangular-matrix의 모습을 조금 더 깔끔하게 정의하는 방법으로서 REF를 도입했습니다.


행사다리꼴행렬 (Row Echelon Form, REF)

REF를 굳이 번역하자면 행사다리꼴, 사다리꼴행렬 정도로 볼 수 있겠다. 하지만 번역하지 않고 REF로 적는 것이 일반적인 것 같습니다.

다음은 REF의 조건입니다.

  • 모든 행의 성분이 00(all-zero row)이 아닌 경우, 가장 첫 번째 나오는 11이라는 숫자를 leading1leading-1, leadingentryleading-entry, 선행성분선행 성분이라고 한다.
  • 어떤 임의의 행이 모두 00(all-zero row)일 때, 이 행은 항상 행렬의 가장 아래(bottom) 존재해야 한다.
  • 어떤 두 개 이상의 연속적인 행이 all-zero-row가 아니었을 때, 밑에 있는 행의 leading1leading-1은 위에 있는 행의 leading1leading-1보다 오른쪽에 와야한다.

두번째 조건과 세번째 조건은 upper-triangular의 모습을 갖추기 위한 조건이라고 볼 수 있습니다.

example.  [0000][100010001][1129013.5400130]example.\; \begin{bmatrix} 0 & 0 \\ 0 & 0 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 2 & 9 \\ 0 & 1 & -3.5 & -4 \\ 0 & 0 & 1 & 30 \end{bmatrix}

기본행연산 (Elmentary Row Operations, ERO)

가우스 소거법은 3가지의 행 연산으로 이루어져 있다. 이를 Elmentary Row Operations(기본 행연산)이라고 합니다.

  • 하나의 방정식의 Multiple 값을 다른 방정식에 더해준다.
  • 두 개의 행의 위치를 서로 교환해준다.
  • 방정식에 0이 아닌 상수값을 곱해준다.

위의 세가지 ERO로 가우스 소거법을 구현할 수 있습니다.

다음은 위의 세가지 연산을 그대로~ 행렬의 개념으로 표현해보면 다음과 같습니다. 참고만 해도 될 것 같습니다.

  • Add a multiple of row-ii to row-jj : (Rj+aRi)Rj(R_j + aR_i) \to R_j
  • Interchange rows-ii and jj : RiRjR_i \leftrightarrow R_j
  • Multiply row-jj by a non-zero constant a: aRjRiaR_j \to R_i

어떤 행렬 A와 B가 있을 때, A에 ERO를 적용해 B라는 행렬을 만들 수 있다면 이를 Row Equivalent(행 동치)라고 합니다.

A와 B가 Row Equivalent하다는 것은 A와 B가 동일한 REF로 변환될 수 있다는 것과 같습니다. (iff, 필요충분조건)

example.  x1+x2+2x3=9,2x1+4x23x3=1,3x1+6x25x3=0example.\; x_1 + x_2 + 2x_3 = 9, 2x_1 + 4x_2 - 3x_3 = 1, 3x_1 + 6x_2 - 5x_3 = 0 [A:b]=[112924313650][A:b] = \begin{bmatrix} 1 & 1 & 2 & 9 \\ 2 & 4 & -3 & 1 \\ 3 & 6 & 5 & 0 \end{bmatrix} E21:(2R1+R2R2)[1129027173650]E_{21} : (-2R_1 + R_2 \to R_2) \nRightarrow \begin{bmatrix} 1 & 1 & 2 & 9 \\ 0 & 2 & -7 & -17 \\ 3 & 6 & 5 & 0 \end{bmatrix} E31:(3R1+R3R3)[112902717031127]E_{31} : (-3R_1 + R_3 \to R_3) \nRightarrow \begin{bmatrix} 1 & 1 & 2 & 9 \\ 0 & 2 & -7 & -17 \\ 0 & 3 & -11 & -27 \end{bmatrix} E32:(3/2R2+R3R3)[112902717001/23/2]E_{32} : (-3/2 R_2 + R_3 \to R_3) \nRightarrow \begin{bmatrix} 1 & 1 & 2 & 9 \\ 0 & 2 & -7 & -17 \\ 0 & 0 & -1/2 & -3/2 \end{bmatrix}

이렇게 해서 Upper-triangular-matrix를 만들 수 있습니다.

다음 편에서는 가우스 소거법에 대해서 조금 더 알아보도록 합시다.

© 2020 leshleekor