ch 2. solving linear equations

원준식·2022년 9월 14일
선형대수

Introduction to Linear Algebra (Gilbert Strang) 5th Edition

목록 보기
2/3

링크텍스트

위 강의를 듣고 정리하는 글입니다.

2.1 vectors and linear equations

A system of equations

(1−232)(xy)=(111)\begin{pmatrix} 1 & -2 \\ 3 & 2 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 11 \end{pmatrix}
  • row picture
{x−2y=13x+2y=11\begin{cases} x - 2y = 1 \\ 3x + 2y = 11 \end{cases}
  • column picture
x(13)+y(−22)=(111)x\begin{pmatrix} 1 \\ 3 \end{pmatrix} + y\begin{pmatrix} -2 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 \\ 11 \end{pmatrix}

column picture의 의미: 두 벡터

(13) and (2−2)\begin{pmatrix} 1 \\ 3 \end{pmatrix} \ and \ \begin{pmatrix} 2 \\ -2 \end{pmatrix}

의 linear combination으로 답을 만들 수 있니?

2.2 idea of elimination

Gaussian elimination

(1−232)(xy)=(111)\begin{pmatrix} 1 & -2 \\ 3 & 2 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 11 \end{pmatrix}

위 식의 1행을 봤을 때 0이 아닌 첫 번째 수 1: first pivot

→ 첫 번째 행에 -3을 곱해서 두 번째 행과 더함

(1−208)(xy)=(18)\begin{pmatrix} 1 & -2 \\ 0 & 8 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 8 \end{pmatrix}

2행에서 0이 아닌 수 중 첫 번째 수는 second pivot

더 이상 elimination을 할 수 없다면 back substitution으로 계산(8y=88y = 8부터 위로 )

예제)

(1−23−6)(xy)=(13)\begin{pmatrix} 1 & -2 \\ 3 & -6 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 3 \end{pmatrix}
(1−200)(xy)=(10)\begin{pmatrix} 1 & -2 \\ 0 & 0 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}

number of pivots = 1

0∗y=00 * y = 0 → y: free variable

x: pivot variable

우변이 0벡터가 아니기 때문에 위 방정식은 nonhomogeneous equation

  • nonhomobeneous equation 푸는 법: homogeneous equation을 풀고 nonhomogeneous equation의 particular solution(특정한 해)을 더해주면 됨

homogeneous equation 풀기

(1−200)(xy)=(00)\begin{pmatrix} 1 & -2 \\ 0 & 0 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}

free variable의 개수만큼 벡터가 나옴

(xy)=c(??)\begin{pmatrix} x \\ y \end{pmatrix} = c\begin{pmatrix} ? \\ ? \end{pmatrix}

free variable 자리에 1을 넣기(여기에 0을 넣으면 다른 애들도 다 0이 되기 때문에 의미가 없음)

(free variable이 여러 개라면 하나에만 1 넣고 나머진 0 넣어주는 식으로)

(xy)=c(?1)\begin{pmatrix} x \\ y \end{pmatrix} = c\begin{pmatrix} ? \\ 1 \end{pmatrix}

pivot variable 계산해서 넣기

(xy)=c(21)\begin{pmatrix} x \\ y \end{pmatrix} = c\begin{pmatrix} 2 \\ 1 \end{pmatrix}

nonhomogeneous equation 풀기

(1−200)(xy)=(10)\begin{pmatrix} 1 & -2 \\ 0 & 0 \end{pmatrix}\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}

여기선 free variable에 어떤 수를 넣어도 되겠지

(xy)=(10)\begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix}

최종 해

(xy)=c(21)+(10)\begin{pmatrix} x \\ y \end{pmatrix} = c\begin{pmatrix} 2 \\ 1 \end{pmatrix} + \begin{pmatrix} 1 \\ 0 \end{pmatrix}

2.3 elimination using matrices

permutation matrix(자리 바꾸기)

P23=(100001010)P_{23} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix}

augmented matrix

[A∣b]  where  Ax=b[A | b] \ \ where \ \ Ax = b

예시)

(100−210001)(24−2 ∣ 249−3 ∣ 8−2−3    7  ∣ 10)=(24−2 ∣ 201   1 ∣ 4−2−3    7  ∣ 10)\begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} 2 & 4 & -2 \ |\ 2\\ 4 & 9 & -3 \ |\ 8 \\ -2 & -3 & \ \ \ \ 7 \ \ |\ 10 \end{pmatrix}= \begin{pmatrix} 2 & 4 & -2 \ |\ 2\\ 0 & 1 & \ \ \ 1 \ |\ 4 \\ -2 & -3 & \ \ \ \ 7 \ \ |\ 10 \end{pmatrix}

왼쪽 행렬은 elimination matrix: 1행으로 2행의 elimination을 진행하는 행렬

E[A∣b]=[EA∣Eb]E[A | b] = [EA | Eb]

행렬 곱의 다른 방법

(∣∣a1a2∣∣)(−b1−−b2−)=(∣a1∣)(−b1−)+(∣a2∣)(−b2−)\begin{pmatrix} | & | \\ a_1 & a_2 \\ | & | \end{pmatrix} \begin{pmatrix} - & b_1 & - \\ - & b_2 & - \\ \end{pmatrix}= \begin{pmatrix} | \\ a_1 \\ | \end{pmatrix} \begin{pmatrix} - & b_1 & - \\ \end{pmatrix}+ \begin{pmatrix} | \\ a_2 \\ | \end{pmatrix} \begin{pmatrix} - & b_2 & - \\ \end{pmatrix}

2.5 inverse matrices

nxn matrix(square matrix) A is invertible if ∃(exist) A−1A^{-1} such that AA−1=A−1A=IAA^{-1} = A^{-1}A=I

  1. A−1A^{-1} exists

    if and only if Gaussian elimination produces n pivots.

  2. suppose BA=IBA=I, AC=IAC=I → B랑 C랑 똑같니?(A의 역행렬이 unique하니?)

    B(AC)=(BA)CB(AC) = (BA)C

    BI=ICBI = IC

    B=CB=C → A의 역행렬은 unique하구나

  3. if A−1A^{-1} exists, Ax=bAx=b has the unique solution.

  4. Ax=0Ax=0을 만족하는 nonzero vector xx가 존재하려면 A−1A^{-1}은 존재하지 않는다.

    A−1A^{-1}이 존재하면 x=0A−1=0x = 0A^{-1} = 0이 되니까

(abcd)−1=1ad−bc(d−b−ca)\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \frac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}
ad−bc=determinantad-bc = determinant

calculation A−1A^{-1} by Gauss-Jordan elimination

[A∣I][A|I] → [E1A∣E1I][E_1A|E_1I] → [E2E1A∣E2E1I][E_2E_1A|E_2E_1I] → … → [Em…E1A∣Em…E1I][E_m…E_1A|E_m…E_1I] = [I∣A−1][I|A^{-1}]

AA가 diagonal matrix될 때 까지 elimination matrix를 곱해준 뒤 II가 되게 나눠줌 → 이렇게 곱해준 Em…E1E_m…E_1이 A−1A^{-1}이겠지

2.6 LU factorization

A=LUA = LU

LL: lower triangular matrix

UU: upper triangular matrix

역행렬 구할 때와 마찬가지로 Gauss-Jordan elimination을 이용해 구하면 됨

2.7 transpose and permutations

(A+B)T=AT+BT(A+B)^T = A^T + B^T

(AB)T=BTAT(AB)^T = B^TA^T

(A−1)T=(AT)−1(A^{-1})^T = (A^T)^{-1}

AA가 invertible하면 ATA^T도 invertible하다.(ATA^T의 역행렬은 A−1A^{-1}을 transpose하면 된다.)

A−1A=IA^{-1}A = I

(A−1A)T=I(A^{-1}A)^T = I

AT(A−1)T=IA^T(A^{-1})^T = I

AT(AT)−1=IA^T(A^T)^{-1} = I

SS가 n by n matrix이고 ST=SS^T = S이면 SS는 symmetric matrix

SS가 symmetric하면 S−1S^{-1}도 symmetric하다.

(S−1)T=(ST)−1=S−1(S^{-1})^T = (S^T)^{-1} = S^{-1}

Gaussian elimination for symmetric matrices

(1227)=(1021)(1203)=(1021)(1003)(1201)\begin{pmatrix} 1 & 2 \\ 2 & 7 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 0 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 0 \\ 0 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 \\ 0 & 1 \end{pmatrix}

S=LU=LDLTS = LU = LDL^T

→ UU를 DD(diagonal matrix)와 LTL^T(U와는 다른 행렬이지만 어쨌든 upper triangular matrix이긴 함)로 더 decomposition 가능하다.

permutation matrices: n by n matrix이고 every row에 1이 하나, every column에 1이 하나

profile
원준식
이전 포스트

ch 1. introduction to vectors

다음 포스트

ch 3. vector spaces

0개의 댓글