1. LU 분해법에 의한 선형 시스템의 풀이

LU분해법 손으로 풀기 : 서울과학기술대학교 기계시스템디자인공학과 / 김성환교수

>> A = [2 1 1; 4 -6 0; -2 7 2]

>> b = [5; -2; 9]

>> A \ b =>    (1, 1,  2)

(1) LU 분할 (LU decomposition or LU factorization)

[교재에 없는 예제 임]

◆ 전개에 충실한 형태

[eqn: ```````2x _{1} +1x _{2} +1x _{3} =``````5``````````````````(1)# ```````4x _{1} -6x _{2} ``````````````````````=-2``````````````````(2)# -2x _{1} +7x _{2} +2x _{3} =``````9`````````````````(3)] [eqn: {bmatrix{2``&1&````1#4``&-6&````0#-2``&7&````2}} LEFT { {matrix{x _{1}#x _{2}#x _{3}}} RIGHT } = LEFT { {matrix{5#-2#9}} RIGHT }] ( [eqn: LEFT [ A RIGHT ] LEFT { x RIGHT } = LEFT { b RIGHT }] ) ▪ (2) □ (2) - 2 × (1) [[eqn: f _{21} =a _{21} /a _{11}]] [eqn: {bmatrix{1``&0&````0#2``&1&````0#0``&0&````1}} {bmatrix{2``&1&````1#0``&-8&````-2#-2``&7&````2}} = {bmatrix{2``&1&````1#4``&-6&````0#-2``&7&````2}}] ▪ (3) □ (3) - -1 × (1) [[eqn: f _{31} =a _{31} /a _{11}]] [eqn: {bmatrix{1``&0&````0#2``&1&````0#-1``&0&````1}} {bmatrix{2``&1&````1#0``&-8&````-2#0``&8&````3}} = {bmatrix{2``&1&````1#4``&-6&````0#-2``&7&````2}}]	▪ (3) □ (3) - -1 × (2) [[eqn: f _{32} =a _{32} /a _{22}]] [eqn: {bmatrix{1``&0&````0#2``&1&````0#-1``&-1&````1}} {bmatrix{2``&1&````1#0``&-8&````-2#0``&0&````1}} = {bmatrix{2``&1&````1#4``&-6&````0#-2``&7&````2}}] [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] = LEFT [ A RIGHT ]] 로 얻어짐 ▪ 결과 [eqn: LEFT [ A RIGHT ] LEFT { x RIGHT } = LEFT { b RIGHT }] 를 [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT [ L RIGHT ] LEFT { d RIGHT }] 로 변형완료 [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] `= LEFT [ A RIGHT ]] (식 a) [eqn: LEFT [ L RIGHT ] LEFT { d RIGHT } = LEFT { b RIGHT }] (식 b) [eqn: LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT { d RIGHT }] (식 c)

◆ 보다 기계적 형태

[eqn: ```````2x _{1} +1x _{2} +1x _{3} =``````5``````````````````(1)# ```````4x _{1} -6x _{2} ``````````````````````=-2``````````````````(2)# -2x _{1} +7x _{2} +2x _{3} =``````9`````````````````(3)] [eqn: {bmatrix{2``&1&````1#4``&-6&````0#-2``&7&````2}} LEFT { {matrix{x _{1}#x _{2}#x _{3}}} RIGHT } = LEFT { {matrix{5#-2#9}} RIGHT }] ( [eqn: LEFT [ A RIGHT ] LEFT { x RIGHT } = LEFT { b RIGHT }] ) ▪ (2) □ (2) - 2 × (1) [[eqn: f _{21} =a _{21} /a _{11}]] ▪ (3) □ (3) - -1 × (1) [[eqn: f _{31} =a _{31} /a _{11}]] [eqn: LEFT [ {matrix{L&`U}} RIGHT ] = {bmatrix{2``&1&````1#2``&-8&````-2#-1``&8&````3}}]	▪ (3) □ (3) - -1 × (2) [[eqn: f _{32} =a _{32} /a _{22}]] [eqn: LEFT [ {matrix{L&`U}} RIGHT ] = {bmatrix{2``&1&````1#2``&-8&````-2#-1``&-1&````1}}] [eqn: {bmatrix{1``&0&````0#2``&1&````0#-1``&-1&````1}} {bmatrix{2``&1&````1#0``&-8&````-2#0``&0&````1}} = {bmatrix{2``&1&````1#4``&-6&````0#-2``&7&````2}}] [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] = LEFT [ A RIGHT ]] 로 얻어짐 ▪ 결과 [eqn: LEFT [ A RIGHT ] LEFT { x RIGHT } = LEFT { b RIGHT }] 를 [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT [ L RIGHT ] LEFT { d RIGHT }] 로 변형완료 [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] `= LEFT [ A RIGHT ]] (식 a) [eqn: LEFT [ L RIGHT ] LEFT { d RIGHT } = LEFT { b RIGHT }] (식 b) [eqn: LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT { d RIGHT }] (식 c)

(2) 전진 대입 (Forward substitution)

(식 b)    [eqn: LEFT [ L RIGHT ] LEFT { d RIGHT } = LEFT { b RIGHT }] 에서 [eqn: LEFT { d RIGHT }]를 구하는 것

[eqn: {bmatrix{1``&0&````0#2``&1&````0#-1``&-1&````1}} LEFT { {matrix{d _{1}#d _{2}#d _{3}}} RIGHT } = LEFT { {matrix{5#-2#9}} RIGHT }]

[eqn: d _{1} =b _{1} =5]

[eqn: d _{2} =b _{2} -(l _{21} *d _{1} )=-2-(2 TIMES 5)=-12]

[eqn: d _{3} =b _{3} -(l _{31} *d _{1} +l _{32} *d _{2} )=9-((-1 TIMES 5)+(-1 TIMES -12))=2]

(3) 후진 대입 (Back substitution)

(식 c)    [eqn: LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT { d RIGHT }] 에서 [eqn: LEFT { x RIGHT }]를 구하는 것

[eqn: {bmatrix{2``&1&````1#0``&-8&````-2#0``&0&````1}} LEFT { {matrix{x _{1}#x _{2}#x _{3}}} RIGHT } = LEFT { {matrix{5#-12#2}} RIGHT }]

[eqn: x _{3} =b _{3} /a _{33} =2/1=2]

[eqn: LEFT { b RIGHT }] 가 바뀌면

(2), (3)의 과정만 다시 수행

[eqn: x _{2} =(b _{2} -(a _{23} *x _{3} ))/a _{22} =(-12-(-2*2))/(-8)=1]

[eqn: x _{1} =(b _{1} -(a _{13} *x _{3} +a _{12} *x _{2} ))/a _{11} =(5-(1*1+1*2))/2=1]

2. LU 분해법의 연습문제 [교재에 없는 예제]

>> A = [2 -1 1; 3 3 9; 3 3 5]

>> b = [-1; 0; 4]

>> A \ b =>    (1, 2, -1)

(1) LU 분할 (LU decomposition or LU factorization)

예제 문제
[eqn: 2x _{1} -1x _{2} +1x _{3} =-1`````````````````(1)# 3x _{1} +3x _{2} +9x _{3} =``````0`````````````````(2)# 3x _{1} +3x _{2} +5x _{3} =``````4`````````````````(3)] [eqn: {bmatrix{2``&-1&````1#3``&3&````9#3``&3&````5}} LEFT { {matrix{x _{1}#x _{2}#x _{3}}} RIGHT } = LEFT { {matrix{-1#0#4}} RIGHT }] ( [eqn: LEFT [ A RIGHT ] LEFT { x RIGHT } = LEFT { b RIGHT }] ) ▪ (2) □ (2) - × (1) [[eqn: f _{21} =a _{21} /a _{11}]] ▪ (3) □ (3) - × (1) [[eqn: f _{31} =a _{31} /a _{11}]]	▪ (3) □ (3) - × (2) [[eqn: f _{32} =a _{32} /a _{22}]] [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] = LEFT [ A RIGHT ]] 로 얻어짐 ▪ 결과 [eqn: LEFT [ A RIGHT ] LEFT { x RIGHT } = LEFT { b RIGHT }] 를 [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT [ L RIGHT ] LEFT { d RIGHT }] 로 변형완료 [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] `= LEFT [ A RIGHT ]] (식 a) [eqn: LEFT [ L RIGHT ] LEFT { d RIGHT } = LEFT { b RIGHT }] (식 b) [eqn: LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT { d RIGHT }] (식 c)

(2) 전진 대입 (Forward substitution)

(식 b)    [eqn: LEFT [ L RIGHT ] LEFT { d RIGHT } = LEFT { b RIGHT }] 에서 [eqn: LEFT { d RIGHT }]를 구하는 것

[eqn: {bmatrix{1``&0&````0#1.5``&1&````0#1.5``&1&````1}} LEFT { {matrix{d _{1}#d _{2}#d _{3}}} RIGHT } = LEFT { {matrix{-1#0#4}} RIGHT }]

[eqn: d _{1} =b _{1} =]

[eqn: d _{2} =b _{2} -(l _{21} *d _{1} )=]

[eqn: d _{3} =b _{3} -(l _{31} *d _{1} +l _{32} *d _{2} )=]

(3) 후진 대입 (Back substitution)

(식 c)    [eqn: LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT { d RIGHT }] 에서 [eqn: LEFT { x RIGHT }]를 구하는 것

[eqn: {bmatrix{2``&-1&````1#0``&4.5&````7.5#0``&0&````-4}} LEFT { {matrix{x _{1}#x _{2}#x _{3}}} RIGHT } = LEFT { {matrix{-1#1.5#4}} RIGHT }]

[eqn: x _{3} =b _{3} /a _{33} =4/(-4)=]

[eqn: x _{2} =(b _{2} -(a _{23} *x _{3} ))/a _{22} =]

[eqn: x _{1} =(b _{1} -(a _{13} *x _{3} +a _{12} *x _{2} ))/a _{11} =]

3. 피봇팅을 사용한 LU 분해법

◆ 기계적 형태

[eqn: ```````2x _{1} +1x _{2} +1x _{3} =``````5``````````````````(1)# ```````4x _{1} -4x _{2} ``````````````````````=``````0``````````````````(2)# -2x _{1} +7x _{2} +2x _{3} =`````9``````````````````(3)] [eqn: {bmatrix{2``&1&````1#4``&-4&````0#-2``&7&````2}} LEFT { {matrix{x _{1}#x _{2}#x _{3}}} RIGHT } = LEFT { {matrix{5#0#9}} RIGHT }] ( [eqn: LEFT [ A RIGHT ] LEFT { x RIGHT } = LEFT { b RIGHT }] ) ▪ A 행렬 [eqn: {bmatrix{2``&1&````1#4``&-4&````0#-2``&7&````2}}] ▪ A 행렬에서 1행과 2행 교환 (피봇팅) 우변에 곱할 치환행렬 [eqn: LEFT [ P RIGHT ]]도 같이 계산. [eqn: {bmatrix{4``&-4&````0#2``&1&````1#-2``&7&````2}}] [eqn: LEFT [ P RIGHT ] = {bmatrix{0``&1&````0#1``&0&````0#0``&0&````1}}] ▪ (2) □ (2) - 0.5 × (1) [[eqn: f _{21} =a _{21} /a _{11}]] ▪ (3) □ (3) - -0.5 × (1) [[eqn: f _{31} =a _{31} /a _{11}]] [eqn: {bmatrix{4``&-4&````0#0.5``&3&````1#-0.5``&5&````2}}]	▪ A 행렬에서 2행과 3행 교환 (피봇팅) 우변에 곱할 치환행렬 [eqn: LEFT [ P RIGHT ]]도 갱신 [eqn: {bmatrix{4``&-4&````0#-0.5``&5&````2#0.5``&3&````1}}] [eqn: LEFT [ P RIGHT ] = {bmatrix{0``&1&````0#0``&0&````1#1``&0&````0}}] ▪ (3) □ (3) - 0.6 × (2) [[eqn: f _{32} =a _{32} /a _{22}]] [eqn: {bmatrix{4``&-4&````0#-0.5``&5&````2#0.5``&0.6&````-0.2}}] [eqn: {bmatrix{1``&0&````0#-0.5``&1&````0#0.5``&0.6&````1}} {bmatrix{4``&-4&````0#0``&5&````2#0``&0&````-0.2}}] ▪ 결과 [eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ] LEFT { x RIGHT } = LEFT [ P RIGHT ] LEFT { b RIGHT }] 를 얻었음 ([eqn: LEFT [ L RIGHT ] LEFT [ U RIGHT ]]가 피봇되어 얻어졌으므로 우변에 [eqn: LEFT [ P RIGHT ]]) [eqn: LEFT [ L RIGHT ] LEFT { d RIGHT } = LEFT [ P RIGHT ] LEFT { b RIGHT }] (식 b) [eqn: LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT { d RIGHT }] (식 c)

(2) 전진 대입 (Forward substitution)

(식 b)    [eqn: LEFT [ L RIGHT ] LEFT { d RIGHT } = LEFT [ P RIGHT ] LEFT { b RIGHT }] 에서 [eqn: LEFT { d RIGHT }]를 구하는 것

[eqn: {bmatrix{1``&0&````0#-1.5``&1&````0#1.5``&0.6&````1}} LEFT { {matrix{d _{1}#d _{2}#d _{3}}} RIGHT } = LEFT { {matrix{0#9#5}} RIGHT }] 에서

[eqn: d _{1} =b _{1} =0]

[eqn: d _{2} =b _{2} -(l _{21} *d _{1} )=9-(-0.5 TIMES 0)=9]

[eqn: d _{3} =b _{3} -(l _{31} *d _{1} +l _{32} *d _{2} )=5-((0.5 TIMES 0)+(0.6 TIMES 9))=-0.4]

(3) 후진 대입 (Back substitution)

(식 c)    [eqn: LEFT [ U RIGHT ] LEFT { x RIGHT } `= LEFT { d RIGHT }] 에서 [eqn: LEFT { x RIGHT }]를 구하는 것

[eqn: {bmatrix{4``&-4&```````0#0``&5&```````2#0``&0&`-0.2}} LEFT { {matrix{x _{1}#x _{2}#x _{3}}} RIGHT } = LEFT { {matrix{0#9#-0.4}} RIGHT }]

[eqn: x _{3} =b _{3} /a _{33} =(-0.4)/(-0.2)=2]

[eqn: x _{2} =(b _{2} -(a _{23} *x _{3} ))/a _{22} =(9-(2*2))/5=1]

[eqn: x _{1} =(b _{1} -(a _{13} *x _{3} +a _{12} *x _{2} ))/a _{11} =(0-(-4*1+0*2))/4=1]

이상.