Particular solution에서 General solution으로 확장하기

[108−401212][x1x2x3x4]=[428]\begin{bmatrix} 1 & 0 & 8 & -4\\ 0 & 1 & 2 & 12\\ \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ x_3\\ x_4\\ \end{bmatrix} = \begin{bmatrix} 42 \\8 \end{bmatrix}

위와 같은 linear equation이 있다고 생각해보겠습니다.

우선 particular solution을 구해보겠습니다. 우선 column의 linear combination으로 다음과 같이 해를 구할 수 있습니다.

b=[428]=42[10]+8[01]b =\begin{bmatrix} 42 \\ 8 \end{bmatrix} = 42 \begin{bmatrix} 1\\ 0 \end{bmatrix} + 8\begin{bmatrix} 0 \\1 \end{bmatrix} [x1,x2,x3,x4]T=[42,8,0,0]T[x_1, x_2, x_3, x_4] ^T = [42, 8, 0, 0] ^T

그리고, 위의 matrix를 잘 살펴보면, 일부 column의 linear combination을 통해서 다른 column vector를 표현할 수 있음을 알 수 있습니다.

[82]=8[10]+2[01]\begin{bmatrix} 8 \\ 2 \end{bmatrix} = 8 \begin{bmatrix} 1\\ 0 \end{bmatrix} + 2\begin{bmatrix} 0 \\1 \end{bmatrix} [−412]=−4[10]+12[01]\begin{bmatrix} -4 \\ 12 \end{bmatrix} = -4 \begin{bmatrix} 1\\ 0 \end{bmatrix} + 12\begin{bmatrix} 0 \\1 \end{bmatrix}

이것을 바탕으로 $Ax=0$인 해와 $Ax = b$의 해를 결합한 general solution을 구할 수 있습니다.

[42,8,0,0]T+λ1[8,2,−1,0]T+λ2[−4,12,0,−1]T[42, 8, 0, 0] ^T + \lambda_1 [8, 2, -1, 0] ^T + \lambda_2[-4, 12, 0, -1]^T

Elementary Transformation

2x1+4x2−2x3− x4+4x5=−34x1+8x2+3x3−3x4+x5=2x1−2x2+x3−x4+x5=0x1−2x2−3x4+4x5=a2x_1 + 4x_2 - 2x_3 - \ x_4 + 4x_5 = -3 \\ 4x_1 + 8x_2 + 3x_3 - 3x_4 + x_5 =2 \\ x_1 -2x_2 + x_3 - x_4 + x_5 = 0 \\ x_1 - 2x_2 - 3x_4 +4x_5 = a [A∣b]=[24−2−14∣−3483−31∣21−21−11∣01−20−34∣a][A \mid b] = \begin{bmatrix} 2 & 4 & -2 & -1 & 4 \mid & -3\\ 4 & 8 & 3 & -3 & 1 \mid &2\\ 1 & -2 & 1 & -1 & 1 \mid & 0\\ 1 & -2 & 0 & -3 & 4 \mid & a\\ \end{bmatrix}

Row echelon form

Matrix는 row chelon form이라고 정의할 수 있다.

  • 모든 요소가 zero인 row들은 matrix 하단에 위치한다. 동시에, 모든 요소가 zero가 아닌 row는 모든 요소가 zero인 row보다 위에 있다.

  • 모든 요소가 zero가 아닌 row에서 첫 번째로 zero가 아닌 요소는 pivot이라고 부른다.

  • basic variable: pivot variable

  • Free variable: 나머지

Row echelon form은 particular solution을 구하는데 유용하다.

λ1[1000]+λ2[1100]+λ3[−1−110]=[0−210]\lambda_1 \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 1 \\ 1 \\ 0 \\ 0 \end{bmatrix} + \lambda_3 \begin{bmatrix} -1 \\ -1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ -2 \\ 1 \\ 0 \end{bmatrix}

먼저, $\lambda_3$을 쉽게 구할 수 있으며, 연쇄적으로 $\lambda_2, \lambda_1$을 계산할 수 있다.

Reduced row echelon form

  • Row echelon form
  • every pivot = 1
  • Pivot 은 한 column에서 유일한 non-zero element이다.

Minus -1 trick

A=[13003001090001−4]A = \begin{bmatrix} 1 & 3 & 0 &0 & 3 \\ 0 & 0 & 1 & 0 & 9 \\ 0 & 0 & 0 & 1 & -4 \\ \end{bmatrix} A~=[130030−1000001090001−40000−1]\tilde{A} = \begin{bmatrix} 1 & 3 & 0 &0 & 3 \\ 0 & -1 & 0 &0 & 0 \\ 0 & 0 & 1 & 0 & 9 \\ 0 & 0 & 0 & 1 & -4 \\ 0 & 0 & 0 & 0 & -1 \\ \end{bmatrix}

$Ax=0$의 해는 아래와 같습니다. x=λ1[3−1000]+λ2[309−4−1],λ1,λ2∈Rx = \lambda_1 \begin{bmatrix} 3 \\ -1 \\ 0 \\ 0 \\ 0 \end{bmatrix} + \lambda_2 \begin{bmatrix} 3 \\ 0 \\ 9 \\ -4 \\ -1 \end{bmatrix} , \lambda_1, \lambda_2 \in R

Calculating an Inverse Matrix by Gaussian Elimination

A=[1020110012011111]A = \begin{bmatrix} 1 & 0 & 2 &0 \\ 1 & 1 & 0 & 0 \\ 1 & 2 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{bmatrix} [A∣I]=[1020∣10001100∣01001201∣00101111∣0001][A \mid I] = \begin{bmatrix} 1 & 0 & 2 &0 \mid 1 & 0 & 0 & 0\\ 1 & 1 & 0 & 0 \mid 0 & 1 & 0 & 0\\ 1 & 2 & 0 & 1 \mid 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 1 \mid 0 & 0 & 0 & 1\\ \end{bmatrix}

위의 matrix를 reduced row echelon form으로 변화시킨다. [1000∣−12−220100∣1−12−20010∣1−11−10001∣−10−12]\begin{bmatrix} 1 & 0 & 0 & 0 \mid &-1 & 2 & -2 & 2\\ 0 & 1 & 0 & 0 \mid &1 & -1 & 2 & -2\\ 0 & 0 & 1 & 0 \mid& 1 & -1 & 1 & -1\\ 0 & 0 & 0 & 1 \mid& -1 & 0 & -1 & 2\\ \end{bmatrix}

A−1=[−12−221−12−21−11−1−10−12]A^{-1} =\begin{bmatrix} -1 & 2 & -2 & 2\\ 1 & -1 & 2 & -2\\ 1 & -1 & 1 & -1\\ -1 & 0 & -1 & 2\\ \end{bmatrix}

Algorithms for Solving a System of Linear Equations

  • least square solutions
Ax=b  ⟺  ATAx=ATb  ⟺  x=(ATA)−1ATbAx =b \iff A^T A x = A^T b \iff x = (A^TA)^{-1}A^Tb
  • Gaussian eliminations
  • Iterative solution

​