슬라이드 1

Size: px

Start display at page:

Download "슬라이드 1"

하룡 천
5 years ago
Views:

1 9. 소규모의방정식을풀기 9. 순수 Guss 소거법 9. 피봇팅 9.4 삼중대각시스템

2 어떤원리에의해다음과같은 MATLAB 명령어가수행되는가? >> =A\ >> =iva)*

3 9. 소규모의방정식을풀기 /6) 컴퓨터를필요로하지않고소규모연립방정식 ) 에적합한방법 - 도식적방법, Crmer 공식, 미지수소거법 도식적인방법 8 9 두연립선형대수방정식의도식적인해 교점이해를나타냄 )

4 9. 소규모의방정식을풀기 /6) 특이 평행선 해가없음 두선이일치함 해가무한히많음 불량조건 특이에가까워반올림오차에매우민감함 특이시스템과불량조건시스템의도식적표현 ) 해가없음, ) 해가무한히많음, c) 해를식별하기어려움.

5 9. 소규모의방정식을풀기 /6) 행렬식과 Crmer 공식 세개의방정식에대한행렬식을고려하자. [ A]{ } { } 여기서 [ A] 이시스템의행렬식은계수행렬로부터구성되는데다음과같다. D mior ) ) )

6 예제 9. Q. 다음시스템에대하여행렬식을구하라. 풀이 ) ) ) D 0 ) D 0 ) ) D ) 5. D 4 4 불량조건특이조건특이조건

7 9. 소규모의방정식을풀기 4/6) 특이시스템 행렬식 = 0 불량조건시스템 행렬식이 0 에가까움 Crmer 공식 D

8 예제 9. /) Q. Crmer 공식으로다음의연립방정식을풀어라 풀이 ) D

9 예제 9. /) 풀이 ) Crmer 공식은 > 이면비현실적이다.

10 9. 소규모의방정식을풀기 5/6) 미지수소거법 두개의방정식으로구성된경우를고려해보자. 상수를곱하면 뺄셈으로 을소거하면 따라서 이결과를대입하면

11 9. 소규모의방정식을풀기 6/6) 미지수소거법은 Crmer 공식을그대로따른것이다. 이기법은컴퓨터를이용하도록공식화되어있어 프로그램작성이용이하다.

12 9. 순수 Guss 소거법 /4) Guss 소거법의두단계 : 전진소거와후진대입 하나의방정식에 오직하나의미지수만나타나도록방정식을조작한다. 그미지수를풀고, 후진대입을통해나머지미지수도결정한다.

13 9. 순수 Guss 소거법 /4) 알고리즘을개발하면대규모의방정식으로 확장이가능하다. Guss 소거법은가장기본적인알고리즘이다. " 순수 " Guss 소거법은 0 으로나누는경우를 극복하지못한방법이다.

14 9. 순수 Guss 소거법 /4) 개의미지수를가진방정식을다루어보자. 피봇원소 첫번째방정식의미지수의계수 ) 첫번째미지수에대한 ) 피봇방정식

15 9. 순수 Guss 소거법 4/4) 단계 : 미지수의전진소거 방정식을상삼각시스템으로바꿈 ) 두번째에서 번째방정식까지미지수 을소거한다. 첫번째식에 / 을곱하면 두번째식에서빼면 또는 ' ' '

16 9. 순수 Guss 소거법 5/4) 나머지방정식에서도대해반복하면두번째피봇방정식을이용하여미지수 를소거하면 ' ' ' ' ' ' ' ' ' ' ' ' " " " " " " ' ' ' '

17 9. 순수 Guss 소거법 6/4) 나머지피봇방정식을이용하여계속적으로소거를수행하면상삼각행렬시스템을구성할수있다. ) ) " " " ' ' ' '

18 9. 순수 Guss 소거법 7/4) 단계 : 후진대입 ) ) i i) i ji i) ii i) ij j i = -, -,,)

19 예제 9. /) Q. Guss 소거법을이용하여방정식을풀어라. 정해는 =, = -.5, 그리고 = 7) 풀이 ) 전진소거를수행하면

20 예제 9. /) 풀이 ) 후진대입하여해를구하면 결과를확인하면 ) ) ) 결과를확인하면 ) 0..5) ) ) 7.5) ) ) 0..5) )

21 9. 순수 Guss 소거법 8/4) [ 순수 Guss 소거법을수행하는 M- 파일 ] fuctio = GussNiveA,) % GussNive A,): % Guss elimitio without pivotig % iput: % A = coefficiet mtri % = right hd side vector % output: % = solutio vector [m,] = sizea); if m ~=, error'mtri A must e squre'); ed = +; Aug =[A ];

22 9. 순수 Guss 소거법 8/4) [ 순수 Guss 소거법을수행하는 M- 파일 ] % forwrd elimitio for k = :- for i = k+: fctor = Augi,k)/Augk,k); Augi,k:) = Augi,k:)-fctor*Augk,k:); ed ed % ck sustitutio = zeros,); ) = Aug,)/Aug,); for i = -:-: i) = Augi,)-Augi,i+:)*i+:))/Augi,i); ed

23 9. 순수 Guss 소거법 9/4) 연산횟수수행시간 ~ 부동소수점연산 flops) 의횟수몇개의항들을정의하면 m i m i i f c i cf ) ) m i m i m i i g i f i g i f ) ) ) ) m m i k m m k i ) ) O m m m m m i m i ) 6 ) ) O m m m m m m i m i 여기서 Om ) = 크기가 m 차수와그보다낮은차수의항

24 9. 순수 Guss 소거법 0/4) 순수 Guss 소거법의 M- 파일에대하여 외부루프가 k = 에서시작하므로, 내부루프의한계는 i = 에서부터 까지다. 따라서내부루프의반복횟수는 i ) 번반복하는내부루프에대해서 - 나눗셈한번 - 각각의열요소에대해 에서 까지곱셈 + 까지 번의곱셈 ) - 마찬가지로 번뺄셈 - 합하면 + 번곱셈 / 나눗셈과 번뺄셈 - 외부루프를한번지나는것에대해전체적으로 ) + ) 번곱셈 / 나눗셈과 )) 번뺄셈

25 9. 순수 Guss 소거법 /4) 요약하면 외부루프 k 내부루프 i 덧셈 / 뺄셈연산횟수 곱셈 / 나눗셈연산횟수, )) ) + ), ) ) )) k k +, k) + k) k) + k -), )) ))

26 9. 순수 Guss 소거법 /4) 따라서소거를위한전체덧셈 / 뺄셈연산횟수는또는결과적으로다음과같다. 유사한해석을곱셈 / 나눗셈에대해서수행하면 ] ) ) [ ) ) k k k k k k ) ) k k k k k ) ) )] [ )] [ O O O O ) ) )] [ )] [ O O O O

27 9. 순수 Guss 소거법 /4) 최종적으로 O ) O ) 이하의항들은 이증가할수록무시됨을유의하라.. 후진대입에대하여 덧셈 / 뺄셈연산횟수 = )/ 곱셈 / 나눗셈연산횟수 = + )/ 따라서합은 O )

28 9. 순수 Guss 소거법 4/4) 순수 Guss 소거법에소요되는전체연산횟수는다음과같다. O ) Forwrd elimitio O ) Bck sustitutio s icreses 시스템이커질수록연산시간이크게증가한다. 대부분의연산은소거단계에서발생한다. O ) 전진소거후진대입전체연산횟수 / 소거의비율 % % 98.5% 99.85%

29 9. 피봇팅 /) 순수 Guss 소거법의정규화에서 0 으로나누는나눗셈발생! 피봇원소가 0 에가까우면어떤일이일어나는가? 피봇원소의크기가다른원소에비해작으면반올림오차가개입! 처방 각각의행을정규화하기전에해당열에서계수가가장큰것을찾는다. 가장큰원소가피봇원소가되도록순서를바꾼다 부분피봇팅 열과행에서가장큰원소를찾아순서를바꾼다 완전피봇팅 드물게사용됨

30 예제 9.4 부분피봇팅 ) /) Q. Guss 소거법을이용하여다음의방정식을풀어라 첫번째피봇원소는 = 이며, 0 에매우가깝다. 그래서방정식의순서를바꾸는부분피봇팅을취한다. 정해는 = / 과 = / 이다.

31 예제 9.4 부분피봇팅 ) /) 풀이 ) 첫번째식에 /0.000) 을곱하면 0, 두번째식에서이식을빼면결과는 = / 따라서.000 / ) 유효숫자수 의백분율상대오차의절대값

32 예제 9.4 부분피봇팅 ) /) 거의같은두수사이의뺄셈으로인해결과가유효숫자수에매우민감하다. 순서를바꾸어서방정식을풀면 = 부분피봇팅 ) = / 그리고 / ) 유효숫자수 의백분율상대오차의절대값

33 9. 피봇팅 /) [ 부분피봇팅이포함된 Guss 소거법을위한 M- 파일 ] fuctio = GussPivotA,) % GussPivot A,): % Guss elimitio with prtil pivotig % iput: % A = coefficiet mtri % = right hd side vector % output: % = solutio vector [m,] = sizea); if m ~=, error'mtri A must e squre'); ed = +; Aug =[A ];

34 9. 피봇팅 /) [ 부분피봇팅이포함된 Guss 소거법을위한 M- 파일 ] % forwrd elimitio for k = :- % prtil pivotig [ig, i] = msaugk:,k))); ipr = i + k -; if ipr ~= k % pivot the row Aug[k,ipr],:) = Aug[ipr,k],:); ed

35 9. 피봇팅 /) [ 부분피봇팅이포함된 Guss 소거법을위한 M- 파일 ] for i = k+: fctor = Augi,k)/Augk,k); Augi,k:) = Augi,k:)-fctor*Augk,k:); ed ed % ck sustitutio = zeros,); ) = Aug,)/Aug,); for i = -:-: i) = Augi,)-Augi,i+:)*i+:))/Augi,i); ed

36 9. 피봇팅 /) >> y = [; ; 5; ; 4]; >> [ym, im] =my) ym = 5 im = >> A=[0.000 ; ]; =[.000; ]; >> = GussPivotA,) =

37 9.4 삼중대각시스템 /) 띠의폭이 인삼중대각시스템을고려하자. r r r r r f e g f e g f e g f e g f

38 예제 9.5 삼중대각시스템의해 ) /) Q. 다음의삼중대각시스템의해를구하라

39 예제 9.5 삼중대각시스템의해 ) /) 풀이 ) 전진소거를통해 후진대입으로 해를구하면 4 r f r r r 4 4 g f g f g f ) ) )

40 9.4 삼중대각시스템 /) [ 상삼각시스템을풀기위한 M- 파일 ] fuctio = Tridige, f, g, r) % Tridige, f, g, r): % Tridigol system solver % iput: % e = sudigol vector % f = digol vector % g = superdigol vector % r = right hd side vector % output % = solutio vector

41 9.4 삼중대각시스템 /) [ 상삼각시스템을풀기위한 M- 파일 ] = legthf); % forwrd elimitio for k = : fctor = ek)/fk-); fk) = fk) - fctor*gk-); rk) = rk) - fctor*rk-); ed % ck sustitutio dispf); dispr) % check modified coefficiets ) = r)/f); for k = -:-: k) = rk)-gk)*k+))/fk); ed

42 9.4 삼중대각시스템 /) >> e=[0; -; -; -]; >> f=[.04;.04;.04;.04]; >> g=[-; -; -; 0]; >> r=[40.8; 0.8; 0.8; 40.8]; >> = Tridige, f, g, r) = 대부분의상삼각시스템에서는피봇팅이필요하지않으나드물게요구되는경우도있다. 상삼각시스템에소요되는계산노력 ~ 참고로 Guss 소거법 ~ )

슬라이드 1

슬라이드 1 장연립방정식을 풀기위한반복법. 선형시스템 : Guss-Sedel. 비선형시스템 . 선형시스템 : Guss-Sedel (/0) 반복법은초기근을가정한후에더좋은근의값을추정하는체계적인절차를이용한다. G-S 방법은선형대수방정식을푸는반복법중에서 가장보편적으로사용되는방법이다. 개의방정식에서 인 ( 대각원소들이모두 0 이아닌 ) 경우를다루자. j j b j b j j j