[수치해석] 10. LU Decomposition & Positive definitive

LU decomposition

• $2x_1+x_2=1,\ x_1+2x_2=3$의 방정식 가정
  • $\begin{bmatrix} 2\ 1:1\\ 1\ 2:3 \end{bmatrix}$ : augmented matrix
  • x계수 행렬을 system matrix라고 함
• Gauss Elimination : 계수 소거
  • $\begin{bmatrix} 2\ 1:1\\ 0\ \frac{3}{2}:\frac{5}{2} \end{bmatrix}$
  • 2열에 1열 / 2한 것을 빼서 계산
  • $x_2=5/3$, $x_1=-1/3$
• $Ax=b$를 Gaussian Elimination을 통해 $Ux=b'$으로 변환
  • $U=\begin{bmatrix} a\ b\\ 0\ d \end{bmatrix}$꼴의 행렬

---

• $Ax=b_1,\ Ax=b_2,\ Ax=b_3, ...$의 행렬식을 푼다고 하면 각 행렬마다 Gauss Elimination이 적용되어야 함

  • Lower - Triangle Matrix L : $L=\begin{bmatrix} a\ 0\\ c\ d \end{bmatrix}$
  • Gauss-Elimitation 연산을 기억하는 효과
  • $A=LU$

• LU Decomposition

  • $A = \begin{bmatrix} 2\ 1\\ 1\ 2 \end{bmatrix} = LU$
    • $U = \begin{bmatrix} 2\ 1\\ 0\ \frac{3}{2} \end{bmatrix}$
    • $L = \begin{bmatrix} 1\ 0\\ k\ 1 \end{bmatrix}$
      • k = 상수항 제거를 위해 Gauss Elimination에 적용한 계수
  • $Ax=b\rarr LUx=b$

• Gauss Elimitnation은 계수 행렬 A에서 항 하나가 제거된 Lower Matrix L로 변환하는 과정을 거침

• LU-Decomposition은 계수행렬 A를 L과 U의 곱으로 변환

  • 우항이 바뀌어도 LU식은 변화 없음

---

• m x n 행렬의 LU decomposition
  • i행 j열 위치의 값을 $a_ji$라고 할 때,
  • j번째 행의 원소 $E_j$의 값을 $E_j-m_{j1}E_1$로 바꿔준다 ($m_j1=\frac{a_j1}{a_11}$)
  • j번째 행의 원소 $E_j$의 값을 $E_j-m_{j2}E_1$로 바꿔준다
  • 1열의 모든 행에 대해 위 계산을 반복한 결과 행렬이 U행렬
  • 위 식에서 계산한 계수 m으로 이루어진 행렬이 L행렬이다.
• Permutation
  • Gauss Elimination 연산이 불가능한 경우 계수 행렬의 열을 맞바꿈
  • P = (a, b) : 바꿀 두 행 a, b를 지정
    • ex. P = (1, 2) (2, 4)의 경우, 1 - 2행을 바꾼 후 2 - 4행을 바꿈
    • $P \begin{bmatrix} 0\ 1\ 0\ 0\\ 0\ 0\ 0\ 1\\ 0\ 0\ 1\ 0\\ 1\ 0\ 0\ 0 \end{bmatrix}$
  • PA = LU의 관계식을 만족
  • $A = P^{-1}LU = P^tLU$

---

Positive definitive

• n x n 행렬 A가 있을 때,
  • $|a_{ii}|\geq\sum^n_{j=1, j\not ={i}}|a_{ij}|$이면 diagonally dominant 하다고 표현
  • $|a_{ii}|>\sum^n_{j=1, j\not ={i}}|a_{ij}|$ 이면 strictly digonally dominant
• $det(A)\not ={0}\lrArr A^{-1}\ exist$
  • determinant가 0이 아님을 증명하는 계산 과정은 복잡
  • 그 대신 (strictly) diagnally dominant이면 $A^{-1}$이 존재하다는 것을 이용
  • $diag.\ dominant A\larr A^{-1}\ exist$
  • $strictly\ diag.\ dominant A\lrarr A^{-1}\ exist$ : non-singluar

---

• 0이 아닌 벡터 x에 대해
  • $x^tAx>0$이면 A는 positive definitive하다고 정의
• positive definitive할 경우
  • 역행렬이 존재
  • 모든 대각 성분은 양수
  • 행렬 내 임의 값의 최대값보다 대각 성분의 최대값이 더 큼
  • i행 j열에서 $(a_{ij})^2<a_{ii}a_{jj}$

---

• n x n 행렬 내에는 n개의 leading submatrix가 존재
  • leading submetrix : 행렬의 1,1 원소를 공통으로 갖는 1 x 1, ..., n x n 크기의 대칭행렬
  • 대칭행렬 A의 leading submatrix가 모두 행렬식이 양수인 경우, A는 positive definitive