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

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

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

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

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

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

• 소거법

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

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 의 개수

$\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 = 2$ → $sin$은 곡선형태

  $3x + y^3 = 2$

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

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

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

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

선형시스템의 대수적 표현

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

👉 Ax = b로 표현하기

1. 선형시스템의 unknowns(미지수)를 모아 column vector(열벡터) x 로 표현한다.
2. 선형시스템의 linear equation(선형방정식)에 대해 다음을 수행한다.
   • coefficients(계수)를 모아 A의 row vector(행벡터)로 표현한다.
   • constant(상수)를 모아 b에 표현한다.

[ 연습문제 ]

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

  1. 2 x 3 linear system

     $3x_1+x_2+x_3 = 4$

     $x_1-2x_2-x_3 = 1$

     👇

     $\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

     $-x_1+2x_2-x_3=3$

     $-x_2+2x_3-x_4=2$

     $-x3+2x_4-x_5=5$

     👇

     $\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. $\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}$

     👇

     $3x_1+x_2+x_3 = 4$

     $x_1-2x_2-x_3 = 1$

     ---

  2. $\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}$

     👇

     $\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}$

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

내용 정리

• 선형시스템

  $3x_1+x_2=2$

  $x_1-2x_2=3$

  $2x_1-4x_2=6$

  • 식은 행이고, 행은 식이다 (linear equation ↔ row)
  • $m$ 은 linear equation(선형방정식)의 개수이다.
  • $n$ 은 unknowns(미지수)의 개수이다.

• $Ax = b$

  $\begin{bmatrix} 3 & 1 \\ 1 & -2 \\ 2 & -4 \end{bmatrix}$$\begin{bmatrix} x \\ y \end{bmatrix}$ = $\begin{bmatrix} 2 \\ 3 \\ 6 \end{bmatrix}$

  • $A$ 는 $m$ x n 행렬이다.
  • $x$ 는 $n$-벡터이다.
  • $b$ 는 $m$-벡터이다.

2강: 선형시스템 - 실습

$\begin{bmatrix} 3 & 1 & 1 \\ 1 & -2 & -1\\ 1 & 1 & 1 \end{bmatrix}$$\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}$ = $\begin{bmatrix} 4 \\ 1 \\ 2 \end{bmatrix}$

행렬과 벡터의 코딩 및 연산

$Ax = b$

• 행렬 코딩과 벡터 코딩

  ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fa8d2a813-a43f-4f41-a0f9-da402cdd4064%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fa8d2a813-a43f-4f41-a0f9-da402cdd4064%2Fimage.png)

역행렬

$(A^{-1})A x=b(A^{-1})$

$x=A^{-1}b$

• 역행렬 구하기

  ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Fc9251db5-e225-4319-8f4e-d4d41d765542%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Fc9251db5-e225-4319-8f4e-d4d41d765542%2Fimage.png)

• 역행렬을 이용한 선형시스템 Ax=b의 해 구하기

  ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2F5f684e35-984c-4a8e-935e-0e963f420760%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2F5f684e35-984c-4a8e-935e-0e963f420760%2Fimage.png)

• 결과 검증

  ![https://velog.velcdn.com/images%2Fleeyongjoo%2Fpost%2Febf30441-0aec-4e35-b824-2f23b821e5b3%2Fimage.png%5D(https%3A%2F%2Fimages.velog.io%2Fimages%2Fleeyongjoo%2Fpost%2Febf30441-0aec-4e35-b824-2f23b821e5b3%2Fimage.png)

  b 와 bb 의 차이가 작은 지($10^{-3}$) 검사

2강: 가우스 소거법

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

선형시스템의 해

1. 해가 하나인 경우

   $3x = 6$

   $\begin{bmatrix} 1 & 3 \\ -2 & 1 \end{bmatrix}$$\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ = $\begin{bmatrix} 2 \\ 3 \end{bmatrix}$

2. 해가 없는 경우

   $0x = 6$

   $\begin{bmatrix} 1 & 3 \\ 2 & 6 \end{bmatrix}$$\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ = $\begin{bmatrix} 2 \\ 5 \end{bmatrix}$

3. 해가 여러개인 경우

   $0x = 0$

   $\begin{bmatrix} 1 & 3 \\ 2 & 6 \end{bmatrix}$$\begin{bmatrix} x_1 \\ x_2 \end{bmatrix}$ = $\begin{bmatrix} 2 \\ 4 \end{bmatrix}$

• $a=0$ 이면 특이하다. #2, 3 경우
  • $ax=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)

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

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

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

2) 후방대입법

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

1. $E_3$ 에서 $x_3$ 를 구하고, $x_3$ 이용하여
2. $E_2$ 에서 $x_2$ 를 구하고, $x_3$ 과 $x_2$ 를 이용하여
3. $E_1$ 에서 $x_1$ 을 구한다.

🔥 가우스소거법 해보기

$\begin{bmatrix} 1 & 2 & 1 \\ 1 & 2 & 3\\ 2 & 3 & -1 \end{bmatrix}$$\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}$ = $\begin{bmatrix} 1 \\ 3 \\ -3 \end{bmatrix}$

$E_1: x_1+2x_2+x_3=1$

$E_2:x_1+2x_2+3x_3=3$

$E_3:2x_1+3x_2+-x_3=-3$

전방소거법

1. $E_2\leftarrow E_2-E_1$
2. $E_3\leftarrow E_3-2E_1$
3. $E_2\leftrightarrow E_3$
4. $E_2\leftarrow -E_2$
5. $E_3\leftarrow -\frac{1}{2} E_3$

$\begin{bmatrix} 1 & 2 & 1 \\ 0 & 1 & 3\\ 0 & 0 & 1 \end{bmatrix}$$\begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix}$ = $\begin{bmatrix} 1 \\ 5 \\ 1 \end{bmatrix}$

기본행연산(EROs)

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

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

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

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

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

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

  랭크: 의미있는 식의 개수

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

  $\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개$\;\;(E_2는\;의미없는\;식)$

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

  $\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}$

  $E_2: 0x_1 + 0x_2 = 1 → 해가\;없음$