ݺߣ

ݺߣShare a Scribd company logo

선형대수 03. LU Decomposition

•Download as PPTX, PDF•
•
AHRA CHO
AHRA CHO

한양대 이상화 교수님 <선형대수> KOCW, 3강 LU Decomposition 강의내용 정리

1 of 6
Downloaded 23 times
Linear Algebra 3. LU Decomposition 한양대 이상화 교수님 <선형대수> http://www.kocw.net/home/search/kemView.do?kemId=977757
가우스 소거법과 행렬 • 가우스 소거법 과정을 행렬 연산으로 표현해 보자 2𝑢 + 𝑣 + 𝑤 = 5 4𝑢 − 6𝑣 = −2 −2𝑢 + 7𝑣 + 2𝑤 = 9 - ① - ② - ③ 2𝑢 + 𝑣 + 𝑤 = 5 −8𝑣 − 2𝑤 = −12 8𝑣 + 3𝑤 = 14 - ① - 2*① - ② - ③ + ① 1st Pivot 2𝑢 + 𝑣 + 𝑤 = 5 −8𝑣 − 2𝑤 = −12 𝑤 = 2 - ②’ - ②’ + ① 2nd Pivot 3rd Pivot Forward Elimination 𝐸31(𝐸21 𝐴) = 1 0 0 0 1 0 1 0 1 2 1 1 0 −8 −2 −2 7 2 −𝑙21(2행) + (-2)(1행) −𝑙31 𝐸32 𝐸31 𝐸21 𝐴 = 1 0 0 0 1 0 0 1 1 2 1 1 0 −8 −2 0 8 3 = 2 1 1 0 −8 −2 0 0 1 𝐸21 𝐴 = 1 0 0 −2 1 0 0 0 1 2 1 1 4 −6 0 −2 7 2 −𝑙32 𝑬 𝟑𝟐 𝑬 𝟑𝟏 𝑬 𝟐𝟏 𝑨 = 𝑼
가우스 소거법과 행렬 • 그래서 연립방정식은 어떻게 푸는 거라고? 𝐴𝑥 = 2 1 1 4 −6 0 −2 7 2 𝑢 𝑣 𝑤 = 5 −2 9 = 𝑏 일 때, 𝑬 𝟑𝟐 𝑬 𝟑𝟏 𝑬 𝟐𝟏 𝑨 = 𝑼 를 적용하면, 𝐸32 𝐸31 𝐸21 𝐴𝑥 = 𝑈𝑥 = 2 1 1 0 −8 −2 0 0 1 𝑢 𝑣 𝑤 = 𝐸32 𝐸31 𝐸21 𝑏 = 5 −12 2 = 𝑐 𝑈𝑥 = 𝑐를 Backward Substitution으로 풀면 연립방정식을 풀 수 있다!
LU Decomposition • 𝑬 𝟑𝟐 𝑬 𝟑𝟏 𝑬 𝟐𝟏 𝑨 = 𝑼를 다시 떠올려보자. 𝐸32 𝐸31 𝐸21 𝐴 = 𝑈  𝐴 = (𝐸32 𝐸31 𝐸21)−1 𝑈 = (𝐸21 −1 𝐸31 −1 𝐸32 −1 ) 𝑈 • 𝑬−𝟏는 어떤 모양일까 1 0 0 −2 1 0 0 0 1 1 0 0 2 1 0 0 0 1 = 1 0 0 2 1 0 0 0 1 1 0 0 −2 1 0 0 0 1 = 𝐈 1 0 0 −𝑙21 1 0 0 0 1 −𝟏 = 1 0 0 𝑙21 1 0 0 0 1 𝑨 = 𝟏 𝟎 𝟎 𝒍 𝟐𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 𝟎 𝒍 𝟑𝟏 𝟎 𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 𝟎 𝟎 𝒍 𝟑𝟐 𝟏 𝑼 = 𝟏 𝟎 𝟎 𝒍 𝟐𝟏 𝟏 𝟎 𝒍 𝟑𝟏 𝒍 𝟑𝟐 𝟏 𝑼 = 𝑳𝑼 Lower Triangular Matrix L : 각 요소는 GE 과정에서 곱한 값들로, L에는 GE의 과정이 담겨있다.
LDU Decomposition • 행렬 A를 한번 더 쪼개보자. 𝐴 = 𝐿𝑈에서 U를 한번 더 분할할 수 있다. 𝑈 = 𝑑1 0 ⋯ 0 ⋮ 𝑑2 ⋮ ⋮ ⋱ ⋮ 0 ⋯ ⋯ 𝑑 𝑛 1 𝑈12 𝑑1 ⋯ 𝑈1𝑛 𝑑1 ⋮ 1 𝑈23 𝑑2 ⋮ ⋮ ⋱ ⋮ 0 ⋯ ⋯ 1 = 𝐷𝑈 행렬 U의 대각 요소들로 대각행렬 D를 만들고, 행렬 U의 각 행을 대각 요소로 나눈 행렬 U’를 구성한다. 𝑨 = 𝑳𝑫𝑼
Permutation Matrix • 가우스 소거법을 진행하다가 행의 순서를 바꾸어야 할 때가 있다. 0 2 3 4 𝑢 𝑣 = 𝑎 𝑏  3 4 0 2 𝑢 𝑣 = 𝑏 𝑎 • 가우스 소거법을 행렬 연산으로 모두 표현했으니, Pivoting도 행렬로 표현할 수 있을 것! Permutation Matrix P = 𝟎 𝟏 𝟏 𝟎  I에서 위치를 변경할 두 행을 뒤바꾼 형태 0 2 3 4 𝑢 𝑣 = 𝑎 𝑏  𝑷𝑨 = 𝟑 𝟒 𝟎 𝟐 𝒖 𝒗 = 𝑷𝒃 = 𝒃 𝒂 • In the non-singular cases, there exists a permutation matrix P, and PA = LU. In the singular cases, there is no P, and elimination fails. (행의 위치를 아무리 바꾸어도 결국 Pivot 자리에 0이 생기기 때문에!)

More Related Content

선형대수 03. LU Decomposition

  • 1. Linear Algebra 3. LU Decomposition 한양대 이상화 교수님 <선형대수> http://www.kocw.net/home/search/kemView.do?kemId=977757
  • 2. 가우스 소거법과 행렬 • 가우스 소거법 과정을 행렬 연산으로 표현해 보자 2𝑢 + 𝑣 + 𝑤 = 5 4𝑢 − 6𝑣 = −2 −2𝑢 + 7𝑣 + 2𝑤 = 9 - ① - ② - ③ 2𝑢 + 𝑣 + 𝑤 = 5 −8𝑣 − 2𝑤 = −12 8𝑣 + 3𝑤 = 14 - ① - 2*① - ② - ③ + ① 1st Pivot 2𝑢 + 𝑣 + 𝑤 = 5 −8𝑣 − 2𝑤 = −12 𝑤 = 2 - ②’ - ②’ + ① 2nd Pivot 3rd Pivot Forward Elimination 𝐸31(𝐸21 𝐴) = 1 0 0 0 1 0 1 0 1 2 1 1 0 −8 −2 −2 7 2 −𝑙21(2행) + (-2)(1행) −𝑙31 𝐸32 𝐸31 𝐸21 𝐴 = 1 0 0 0 1 0 0 1 1 2 1 1 0 −8 −2 0 8 3 = 2 1 1 0 −8 −2 0 0 1 𝐸21 𝐴 = 1 0 0 −2 1 0 0 0 1 2 1 1 4 −6 0 −2 7 2 −𝑙32 𝑬 𝟑𝟐 𝑬 𝟑𝟏 𝑬 𝟐𝟏 𝑨 = 𝑼
  • 3. 가우스 소거법과 행렬 • 그래서 연립방정식은 어떻게 푸는 거라고? 𝐴𝑥 = 2 1 1 4 −6 0 −2 7 2 𝑢 𝑣 𝑤 = 5 −2 9 = 𝑏 일 때, 𝑬 𝟑𝟐 𝑬 𝟑𝟏 𝑬 𝟐𝟏 𝑨 = 𝑼 를 적용하면, 𝐸32 𝐸31 𝐸21 𝐴𝑥 = 𝑈𝑥 = 2 1 1 0 −8 −2 0 0 1 𝑢 𝑣 𝑤 = 𝐸32 𝐸31 𝐸21 𝑏 = 5 −12 2 = 𝑐 𝑈𝑥 = 𝑐를 Backward Substitution으로 풀면 연립방정식을 풀 수 있다!
  • 4. LU Decomposition • 𝑬 𝟑𝟐 𝑬 𝟑𝟏 𝑬 𝟐𝟏 𝑨 = 𝑼를 다시 떠올려보자. 𝐸32 𝐸31 𝐸21 𝐴 = 𝑈  𝐴 = (𝐸32 𝐸31 𝐸21)−1 𝑈 = (𝐸21 −1 𝐸31 −1 𝐸32 −1 ) 𝑈 • 𝑬−𝟏는 어떤 모양일까 1 0 0 −2 1 0 0 0 1 1 0 0 2 1 0 0 0 1 = 1 0 0 2 1 0 0 0 1 1 0 0 −2 1 0 0 0 1 = 𝐈 1 0 0 −𝑙21 1 0 0 0 1 −𝟏 = 1 0 0 𝑙21 1 0 0 0 1 𝑨 = 𝟏 𝟎 𝟎 𝒍 𝟐𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 𝟎 𝒍 𝟑𝟏 𝟎 𝟏 𝟏 𝟎 𝟎 𝟎 𝟏 𝟎 𝟎 𝒍 𝟑𝟐 𝟏 𝑼 = 𝟏 𝟎 𝟎 𝒍 𝟐𝟏 𝟏 𝟎 𝒍 𝟑𝟏 𝒍 𝟑𝟐 𝟏 𝑼 = 𝑳𝑼 Lower Triangular Matrix L : 각 요소는 GE 과정에서 곱한 값들로, L에는 GE의 과정이 담겨있다.
  • 5. LDU Decomposition • 행렬 A를 한번 더 쪼개보자. 𝐴 = 𝐿𝑈에서 U를 한번 더 분할할 수 있다. 𝑈 = 𝑑1 0 ⋯ 0 ⋮ 𝑑2 ⋮ ⋮ ⋱ ⋮ 0 ⋯ ⋯ 𝑑 𝑛 1 𝑈12 𝑑1 ⋯ 𝑈1𝑛 𝑑1 ⋮ 1 𝑈23 𝑑2 ⋮ ⋮ ⋱ ⋮ 0 ⋯ ⋯ 1 = 𝐷𝑈 행렬 U의 대각 요소들로 대각행렬 D를 만들고, 행렬 U의 각 행을 대각 요소로 나눈 행렬 U’를 구성한다. 𝑨 = 𝑳𝑫𝑼
  • 6. Permutation Matrix • 가우스 소거법을 진행하다가 행의 순서를 바꾸어야 할 때가 있다. 0 2 3 4 𝑢 𝑣 = 𝑎 𝑏  3 4 0 2 𝑢 𝑣 = 𝑏 𝑎 • 가우스 소거법을 행렬 연산으로 모두 표현했으니, Pivoting도 행렬로 표현할 수 있을 것! Permutation Matrix P = 𝟎 𝟏 𝟏 𝟎  I에서 위치를 변경할 두 행을 뒤바꾼 형태 0 2 3 4 𝑢 𝑣 = 𝑎 𝑏  𝑷𝑨 = 𝟑 𝟒 𝟎 𝟐 𝒖 𝒗 = 𝑷𝒃 = 𝒃 𝒂 • In the non-singular cases, there exists a permutation matrix P, and PA = LU. In the singular cases, there is no P, and elimination fails. (행의 위치를 아무리 바꾸어도 결국 Pivot 자리에 0이 생기기 때문에!)