(2-1) 선형시스템 / 가우스 소거법

Yongjoo Lee·2020년 12월 7일
0
post-thumbnail

1강: 선형시스템(Linear System)

선형시스템에서는 다음과 같은 내용을 배운다.

  • 선형시스템 복습: 초등/중등 교과과정
  • 선형시스템: Ax=bAx = b, 연립일차방정식의 대수적 표현
  • 가우스 소거법: 선형시스템을 푸는 방법
  • LU 분해: 가우스 소거법 과정을 행렬로 표현
  • 프로그래밍 실습

👶선형시스템 복습: 초등 교과과정

간단한 형태의 선형시스템(linear system) 문제는 다음과 같다.

3x=6313x=316x=2\begin{aligned}3x &= 6 \\3^{-1} * 3x &= 3^{-1} * 6 \\ x &= 2\end{aligned}

연립일차방정식 == 선형시스템

  • 소거법

    식과 식을 더하거나 식에 숫자를 곱하여 변수를 소거

3x + y = 2 # --> * 2
x - 2y = 3

⇒

6x + 2y = 4
x - 2y = 3

⇒

7x = 7
x = 1, y = -1

소거법을 정형화한 것이 가우스 소거법

소거법을 적용하여 변수를 소거하였는데 소거한 변수가 다시 튀어 나오는 경우가 발생.

이런 경우 가우스 소거법을 이용

  • 가우스 소거법

    이미 소거한 변수가 나오지 않도록 하는 방법

선형대수(linear algebra)의 목표는 어떤 선형시스템(연립일차방정식) 문제라도 정형적인 방법으로 표현하고 해결하는 방법을 배우는 것이다.

선형시스템 구성요소

  • Linear Equations (선형방정식)

    3차원 공간에 방정식을 그렸을 때 직선, 평면이 나오면 선형방정식이다.

  • Unknowns (미지수)

    알아내려는 변수 x, y, ...를 Unknown (혹은 variable) 이라고 한다.

m x n Linear System

m: linear equation 의 개수

n: unknown 의 개수

3x+y+z=4x2yz=1x+y+z=2\begin{alignedat}{5}3x&+&y&+&z=4 \\ x&-2&y&-&z=1\\x&+&y&+&z=2\end{alignedat}

3개의 linear equations, 3개의 unknowns로 구성된 연립일차방정식을

3 x 3 linear system 이라고 한다.

non-linear equation (비선형방정식)

  • 비선형방정식 예시

    sinx+y=2sinx + y = 2sinsin은 곡선형태

    3x+y3=23x + y^3 = 2

💡선형방정식인지 비선형방정식인지 구분하는 방법

미지수의 승수가 1로만 구성되어 있는 경우는 선형방정식이다!

그렇다면 xy+z=3xy + z = 3 의 경우는?

⇒ x의 승수 1 + y의 승수 1 = 2 이므로 비선형방정식이다!

선형시스템의 대수적 표현

Ax=bAx = b (연립일차방정식의 대수적 표현)

👉 Ax = b로 표현하기

[311224][xy]=[236]\begin{bmatrix}3 & 1 \\1 & -2 \\2 & -4\end{bmatrix}\begin{bmatrix}x \\y \end{bmatrix}=\begin{bmatrix}2 \\3 \\6\end{bmatrix}
  1. 선형시스템의 unknowns(미지수)를 모아 column vector(열벡터) x 로 표현한다.
  2. 선형시스템의 linear equation(선형방정식)에 대해 다음을 수행한다.
    • coefficients(계수)를 모아 A의 row vector(행벡터)로 표현한다.
    • constant(상수)를 모아 b에 표현한다.

[ 연습문제 ]

  • 다음 선형시스템을 Ax=bAx = b 로 표현해보자!

    1. 2 x 3 linear system

      3x1+x2+x3=43x_1+x_2+x_3 = 4

      x12x2x3=1x_1-2x_2-x_3 = 1

      👇

      [311121][x1x2x3]=[41]\begin{bmatrix}3 & 1 & 1 \\1 & -2 & -1 \\\end{bmatrix}\begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix}=\begin{bmatrix}4 \\1\end{bmatrix}


    2. 3 x 5 linear system

      x1+2x2x3=3-x_1+2x_2-x_3=3

      x2+2x3x4=2-x_2+2x_3-x_4=2

      x3+2x4x5=5-x3+2x_4-x_5=5

      👇

      [121000121000121][x1x2x3x4x5]=[325]\begin{bmatrix}-1 & 2 & -1 & 0 & 0 \\0 & -1 & 2 & -1 & 0 \\0 & 0 & -1 & 2 & -1\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\x_3 \\x_4 \\x_5\end{bmatrix}=\begin{bmatrix}3 \\2 \\5\end{bmatrix}

  • 다음 Ax=b 로부터 연립일차방정식 형태의 선형시스템을 표현해보자!

    1. [311121][x1x2x3]=[41]\begin{bmatrix}3 & 1 & 1 \\1 & -2 & -1 \\\end{bmatrix}\begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix}=\begin{bmatrix}4 \\1\end{bmatrix}

      👇

      3x1+x2+x3=43x_1+x_2+x_3 = 4

      x12x2x3=1x_1-2x_2-x_3 = 1


    2. [121000121000121][x1x2x3x4x5]=[325]\begin{bmatrix}-1 & 2 & -1 & 0 & 0 \\0 & -1 & 2 & -1 & 0 \\0 & 0 & -1 & 2 & -1\end{bmatrix}\begin{bmatrix}x_1 \\ x_2 \\x_3 \\x_4 \\x_5\end{bmatrix}=\begin{bmatrix}3 \\2 \\5\end{bmatrix}

      👇

      x1+2x2x3=3x2+2x3x4=2x3+2x4x5=5\begin{aligned}-x_1+2x_2-x_3\hspace{5.2em}&=3 \\-x_2+2x_3-x_4\hspace{2.5em}&=2\\-x_3+2x_4-x_5\hspace{0em}&=5\end{aligned}

빠져있는 변수를 비워두고 적으면 구조적으로 파악하기 더 좋음!

내용 정리

  • 선형시스템

    3x1+x2=23x_1+x_2=2

    x12x2=3x_1-2x_2=3

    2x14x2=62x_1-4x_2=6

    • 식은 행이고, 행은 식이다 (linear equation ↔ row)
    • mm 은 linear equation(선형방정식)의 개수이다.
    • nn 은 unknowns(미지수)의 개수이다.
  • Ax=bAx = b

    [311224]\begin{bmatrix} 3 & 1 \\ 1 & -2 \\ 2 & -4 \end{bmatrix}[xy]\begin{bmatrix} x \\ y \end{bmatrix} = [236]\begin{bmatrix} 2 \\ 3 \\ 6 \end{bmatrix}

    • AAmm x n 행렬이다.
    • xxnn-벡터이다.
    • bbmm-벡터이다.

2강: 선형시스템 - 실습

[311121111]\begin{bmatrix} 3 & 1 & 1 \\ 1 & -2 & -1\\ 1 & 1 & 1 \end{bmatrix}[x1x2x3]\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = [412]\begin{bmatrix} 4 \\ 1 \\ 2 \end{bmatrix}

행렬과 벡터의 코딩 및 연산

Ax=bAx = b

역행렬

(A1)Ax=b(A1)(A^{-1})A x=b(A^{-1})

x=A1bx=A^{-1}b

2강: 가우스 소거법

역행렬을 구하기 위한 알고리즘

선형시스템의 해

  1. 해가 하나인 경우

    3x=63x = 6

    [1321]\begin{bmatrix} 1 & 3 \\ -2 & 1 \end{bmatrix}[x1x2]\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = [23]\begin{bmatrix} 2 \\ 3 \end{bmatrix}

  2. 해가 없는 경우

    0x=60x = 6

    [1326]\begin{bmatrix} 1 & 3 \\ 2 & 6 \end{bmatrix}[x1x2]\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = [25]\begin{bmatrix} 2 \\ 5 \end{bmatrix}

  3. 해가 여러개인 경우

    0x=00x = 0

    [1326]\begin{bmatrix} 1 & 3 \\ 2 & 6 \end{bmatrix}[x1x2]\begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = [24]\begin{bmatrix} 2 \\ 4 \end{bmatrix}

  • a=0a=0 이면 특이하다. #2, 3 경우
    • ax=bax=b의 해가 곧장 나오지 않는다 → a의 역수가 존재하지 않는다. (0으로 나눌 수 없기 때문)
    • a의 역수가 존재하지 않는 경우, a가 특이(singular)하다고 한다.
  • 해가 있으면 선형시스템이 consistent 하다고 한다. # 1, 3 경우
  • 해가 없으면 선형시스템이 inconsistent 하다고 한다. # 2 경우

가우스 소거법 (Gauss elimination)

가우스 소거법은 임의의 m x n 선형 시스템의 해를 구하는 가장 대표적인 방법이다.

가우스 소거법은 다음의 두 단계로 수행된다.

  1. 전방소거법(Forward Elimination)
  2. 후방대입법(back-substitution)

1) 전방소거법(Forward Elimination)

주어진 선형시스템을 아래로 갈수록 더 단순한 형태의 선형방정식을 가지도록 변형하는 절차

[][x1x2x3]=[][000][x1x2x3][]\begin{bmatrix}* & * & * \\* & * & *\\* & * & *\end{bmatrix}\begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix}=\begin{bmatrix}* \\* \\*\end{bmatrix}→\begin{bmatrix}* & * & * \\0 & * & *\\0 & 0 & *\end{bmatrix}\begin{bmatrix}x_1 \\x_2 \\x_3\end{bmatrix}\begin{bmatrix}* \\* \\*\end{bmatrix}

대부분 0이 아닌 A에 대하여 전방소거법을 수행 후 많은 부분이 0으로 바뀌게 됨

(마지막 행은 가장 단순한 선형방정식이 나오게 됨)

2) 후방대입법

아래에서부터 위로 미지수를 실제값으로 대체

  1. E3E_3 에서 x3x_3 를 구하고, x3x_3 이용하여
  2. E2E_2 에서 x2x_2 를 구하고, x3x_3x2x_2 를 이용하여
  3. E1E_1 에서 x1x_1 을 구한다.

🔥 가우스소거법 해보기

[121123231]\begin{bmatrix} 1 & 2 & 1 \\ 1 & 2 & 3\\ 2 & 3 & -1 \end{bmatrix}[x1x2x3]\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = [133]\begin{bmatrix} 1 \\ 3 \\ -3 \end{bmatrix}

E1:x1+2x2+x3=1E_1: x_1+2x_2+x_3=1

E2:x1+2x2+3x3=3E_2:x_1+2x_2+3x_3=3

E3:2x1+3x2+x3=3E_3:2x_1+3x_2+-x_3=-3

전방소거법

  1. E2E2E1E_2\leftarrow E_2-E_1
  2. E3E32E1E_3\leftarrow E_3-2E_1
  3. E2E3E_2\leftrightarrow E_3
  4. E2E2E_2\leftarrow -E_2
  5. E312E3E_3\leftarrow -\frac{1}{2} E_3

[121013001]\begin{bmatrix} 1 & 2 & 1 \\ 0 & 1 & 3\\ 0 & 0 & 1 \end{bmatrix}[x1x2x3]\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = [151]\begin{bmatrix} 1 \\ 5 \\ 1 \end{bmatrix}

기본행연산(EROs)

소거법에 활용된 세가지 기본행연산(elementary row operations, EROs)

  • 치환(Replacement): rjrjmrir_j\leftarrow r_j-mr_i
  • 교환(interchange): rjrir_j\leftrightarrow r_i
  • 스케일링(Scaling): rjsrir_j\leftarrow sr_i

⭐전방소거법(Forward Elimination)의 가치

  • 주어진 선형시스템을 가장 풀기 쉬운 꼴로 변형해준다.

    상삼각형태(Upper triangular form)로 만들어줌

  • 주어진 선형시스템의 랭크(rank)를 알려준다.

    랭크: 의미있는 식의 개수

    예시) rank = 1 인 선형시스템

    [1326][x1x2]=[24]            [1300][x1x2]=[20]\begin{bmatrix}1 & 3 \\2 & 6\end{bmatrix}\begin{bmatrix}x_1 \\x_2\end{bmatrix} = \begin{bmatrix}2 \\4\end{bmatrix}\;\;\;\rightarrow\;\;\;\begin{bmatrix}1 & 3 \\0 & 0\end{bmatrix}\begin{bmatrix}x_1 \\x_2\end{bmatrix} = \begin{bmatrix}2 \\0\end{bmatrix}

    식은 2개이지만 의미있는 식은 1개    (E2  의미없는  )\;\;(E_2는\;의미없는\;식)

  • 선형시스템이 해가 있는지(consistent) 아니면 해가 없는지(inconsistent) 알려준다.

    [1326][x1x2]=[25]            [1300][x1x2]=[21]\begin{bmatrix}1 & 3 \\2 & 6\end{bmatrix}\begin{bmatrix}x_1 \\x_2\end{bmatrix} = \begin{bmatrix}2 \\5\end{bmatrix}\;\;\;\rightarrow\;\;\; \begin{bmatrix}1 & 3 \\0 & 0\end{bmatrix}\begin{bmatrix}x_1 \\x_2\end{bmatrix} = \begin{bmatrix}2 \\1\end{bmatrix}

    E2:0x1+0x2=1해가  없음E_2: 0x_1 + 0x_2 = 1 → 해가\;없음

profile
하나씩 정리하는 개발공부로그입니다.

0개의 댓글