수치해석 () (Part 1) 문양세 ( 컴퓨터과학전공, IT 특성화대학, 강원대학교 ) In this chapter (1/2) 일변수방정식 (single variable equations) 에서 1) 근을구하는문제, 2) 최대값과최소값을구하는문제를다룬다. 일변수방정식이란? 변수가하나인방정식을의미한다. 즉, 일반적으로 f() 와같은형식으로변수가만주어지는방정식을의미한다. 일변수방정식의근을구하는문제는 f() = 0 꼴의식을만족하는 값을찾는문제라할수있다. ( 0 점찾기 (zero crossing localization) 라고도한다.) 저차식 (1차, 2차, 3차 ) 인경우, 인수분해등의분석적방법을사용한다. But, 고차식인경우, 비선형함수 ( 삼각, 지수, 로그함수 ) 인경우, 이들함수들이복합적으로섞인복잡한방정식인경우에는어떻게하나 분석적방법이어려우므로수치해석적인방법 (Numerical Method) 을통하여풀어낸다. Page 2 1
In this chapter (2/2) 근, 최대값, 최소값, 극대값, 극소값 f() 극대값 (local maimum) 및최대값 (global maimum) 극대값 (local maimum) 극소값 (local minimum) 0 0 점, i.e., 근 We will cover 이분법 (bisection method) 을사용한방정식풀이 뉴튼-랩슨법 () 을사용한방정식풀이 그외의방정식풀이방법 ( 할선법, 가상위치법등 ) 극값 (etreme value) 찾기 다항식의인수분해 Page 3 본론에들어가기에앞서서 (1/2) 앞으로많은프로그램을배우게된다. 프로그램을쓰기위해서는알고리즘을기술할수있어야한다. 본강의에서는 알고리즘기술은알고리즘과목에서가장널리쓰이는 Pascal 형식의 Pseudo Code 를사용하고, 프로그램은 ( 여러분이잘사용하는, 외부에서도가장많이쓰이는, 많은다른언어의기초로작용하는 ) C 언어를사용한다. 그러므로, 본강의에서는 우선, 알고리즘을기술하는방법은간략하게소개한다. C 언어의경우, 기본적인내용만을다루므로, 익숙하지않은학생이라도스스로학습하여이기회에 C 언어에좀더실력을쌓아야한다. Page 4 2
본론에들어가기에앞서서 (2/2) C 프로그램의경우 강의에서는 UNIX(or Linu) 환경에서 C 프로그래밍을보여준다. 그러나, 여러분은 Windows, Linu, Uni 등어느환경에서작업을해도상관이없다. ( 우리가배우는내용은 OS 및 Platform Independent 하다.) 다만, 스스로프로그래밍할수있는자신의환경을구축하기를 ( 매우강력하게 ) 권고한다. UNIX/Linu 를사용한경험이있는학생이나컴퓨터특강을수강한학생은 UNIX/Linu 환경을권장한다. 그렇지않은학생은 Windows 환경을포함한어느환경을사용해도무방하다. 환경구축에대한문의사항은 Page 5 Pseudocode Language procedure name(argument: type) variable := epression informal statement begin statements end {comment if condition then statement [else statement] for variable := initial value to final value statement while condition statement procname(arguments) Not defined in book: return epression Page 6 3
procedure procname(arg arg: type) Declares that the following tet defines a procedure named procname that takes inputs (arguments) named arg which are data objects of the type type. Eample: procedure maimum(l: list of integers) [statements defining maimum ] Page 7 variable := epression An assignment statement evaluates the epression, then reassigns the variable to the value that results. Eample: v := 3+7 (If is 2, changes v to 13.) In pseudocode, the epression might be informal: := the largest integer in the list L Page 8 4
Informal Statement Sometimes we may write a informal statement, if the meaning is still clear and precise: swap and y. Keep in mind that real programming languages never allow this. ( 궁극적으로는알고리즘을쓰고이를구현해야한다.) When we ask for an algorithm to do so-and-so, writing Do so-and-so isn t enough! ( 를찾는알고리즘을기술하라 했는데, Find 라하는것은충분치않다!) Break down algorithm into detailed steps. Page 9 begin statements end Groups a sequence of statements together: begin statement 1 statement 2 statement n end Allows sequence to be used like a single statement. ( 한문장인양..) Might be used: After a procedure declaration. In an if statement after then or else. In the body of a for or while loop. Page 10 5
{ comment Not eecuted (does nothing). Natural-language tet eplaining some aspect of the procedure to human readers. (Reader 의이해도모 ) Also called a remark in some real programming languages. Eample: {Note that v is the largest integer seen so far. Page 11 If condition then statement Evaluate the propositional epression condition. If the resulting truth value is true, then eecute the statement; otherwise, just skip on ahead to the net statement. ( 조건이 true 일때만문장을수행한다.) Variant: if cond then stmt1 else stmt2 Like before, but iff truth value is false, eecutes stmt2. Page 12 6
while condition statement (1/2) Evaluate the propositional epression condition. If the resulting value is true, then eecute statement. Continue repeating the above two actions over and over until finally the condition evaluates to false; then go on to the net statement. ( 조건이 true 인한문장을반복하여수행한다.) Page 13 while comment statement (2/2) Also equivalent to infinite nested ifs, like so: (if 를무한히써서구현할수도있다. 설마 ~) if condition begin statement if condition begin statement (continue infinite nested if s) end end Page 14 7
for var := initial to final stmt Initial is an integer epression. Final is another integer epression. Repeatedly eecute stmt, first with variable var := initial, then with var := initial+1, then with var := initial+2, etc., then finally with var := final. What happens if stmt changes the value that initial or final evaluates to? For can be eactly defined in terms of while, like so: begin var := initial while var final begin stmt var := var + 1 end end Page 15 procedure(argument argument) A procedure call statement invokes the named procedure, giving it as its input the value of the argument epression. Various real programming languages refer to procedures as functions (since the procedure call notation works similarly to function application f()), or as subroutines, subprograms, or methods. Page 16 8
Ma Procedure in Pseudocode Write finding maimum number in pseudo-code. procedure ma(a 1, a 2,, a n : integers) v := a 1 {largest element so far for i := 2 to n {go thru rest of elems if a i > v then v := a i {found bigger? {at this point v s value is the same as the largest integer in the list return v Page 17 We are now Bisection Method 이분법 (bisection method) 을사용한방정식풀이뉴튼-랩슨법 () 을사용한방정식풀이그외의방정식풀이방법 ( 할선법, 가상위치법등 ) 극값 (etreme value) 찾기다항식의인수분해 Page 18 9
이분법 (Bisection Method) 개요 (1/2) Bisection Method Motivation: 연속함수의경우, 실근의전후에서함수값은서로다른부호를갖는다. ( 단, 중근의경우예외가있으며, 이는 Ch. 1.4 에서다루기로한다.) 이분법개요 어떤구간의두경계값에서함수값의부호에변화가있는지검사한다. 부호에변화가있다면, 그구간내에근이존재한다는의미이다. 따라서, ( 좀더정확한근을구하기위하여 ) 해당구간을반으로나누어두개의새로운구간을만든다. 두구간중에서부호의변화가있는구간을찾아낸다. 상기과정을원하는정밀도까지반복한다. Page 19 이분법개요 (2/2) Bisection Method 구간분할 : 중간값을취하는방법을사용한다. 두값 l 과 h 사이에근이존재할때, 중간값 m 은다음과같이구한다. f() m = l + 2 h X l X m X h X l X m X h f( m ) f( h ) 와 f( m ) f( l ) 을조사하여음수값을갖는경우를다음구간으로사용한다. In Computer Science, we call this method as binary search. Page 20 10
이분법알고리즘 Bisection Method procedure bisection( l, h, e: real numbers) { l is a left bound value of the range having a root. { h is a right bound value of the range having a root. { e is an allowable error value. while ( h l ) > e begin m := ( h + l ) / 2; {get a medium value if f( m ) f( h ) = 0 then return m ; { m is a root! else if f( m ) f( l ) < 0 then h := m ; else if f( m ) f( h ) < 0 then l := m ; else break; { something wrong cannot find the root. end return m ; Page 21 이분법프로그램 (1/2) 대상함수 : f ( ) = log( + 5.0) + Bisection Method #include <stdio.h> #include <stdlib.h> #include <math.h> float f(float); // evaluation of f() main(int argc, char *argv[]) { int i = 1; float h, l, m, e; if(argc < 4) { printf("usage: %s h l e\n", argv[0]); eit(0); h = (float)atof(argv[1]); l = (float)atof(argv[2]); e = (float)atof(argv[3]); // ascii to float function printf("h = %.10f\n", h); printf("l = %.10f\n", l); printf("e = %.10f\n", e); Page 22 11
이분법프로그램 (2/2) Bisection Method while((h - l) > e) { m = (h + l) / 2.0; if((f(m)*f(h)) == (float)0) break; else if((f(m)*f(l)) < (float)0) h = m; else if((f(m)*f(h)) < (float)0) l = m; else { printf( Something worng --> cannot find the root.\n ); break; printf("[iteration %02d]: The root is %.10f <with error %.10f>\n", i++, m, h-l); float f(float ) { return ((float)log( + 5.0) + ); // f ( ) = log( + 5.0) + Page 23 프로그램실행결과 Bisection Method Page 24 12
다른함수의예와실행결과 (1/2) Bisection Method 대상함수 : 3 2 f( ) = + 4 10= 0 이분법알고리즘 ( 프로그램 ) 자체는동일하며, 단지함수 f() 만다음과같이달리하면된다. 참고 : pow(, y) = y Page 25 다른함수의예와실행결과 (2/2) Bisection Method Page 26 13
이분법 - 재귀알고리즘 (recursive algorithm) Bisection Method procedure bisection( l, h, e: real numbers) { l is a left bound value of the range having a root. { h is a left bound value of the range having a root. { e is an allowable error value. m := ( h + l ) / 2; {get a medium value if f(m) f( h ) = 0 then return m; else if f(m) f( l ) < 0 then h := m; else if f(m) f( h ) < 0 then l := m; else break; {something wrong cannot find the root. if ( h + l ) e then return m else return bisection( h, l, e); Page 27 이분법 - 재귀프로그램 (1/2) 대상함수 : f ( ) = log( + 5.0) + Bisection Method #include <stdio.h> #include <stdlib.h> #include <math.h> int i = 1; float f(float); // evaluation of f() void bisection(float, float, float); // recursive function main(int argc, char *argv[]) { float h, l, e; if(argc < 4) { printf("usage: %s h l e\n", argv[0]); eit(0); h = (float)atof(argv[1]); l = (float)atof(argv[2]); e = (float)atof(argv[3]); printf("h = %.10f\n", h); printf("l = %.10f\n", l); printf("e = %.10f\n", e); bisection(h, l, e); Page 28 14
이분법 - 재귀프로그램 (2/2) Bisection Method void bisection(float h, float l, float e) { float m; m = (h + l) / 2.0; if((f(m)*f(h)) == (float)0) return; else if((f(m)*f(l)) < (float)0) h = m; else if((f(m)*f(h)) < (float)0) l = m; else { printf( Something worng --> cannot find the root.\n ); eit(-1); printf("[recursion %02d]: The root is %.10f <with error %.10f>\n", i++, m, h-l); if((h - l) <= e) return; else bisection(h, l, e); float f(float ) { return ((float)log( + 5.0) + ); // f ( ) = log( + 5.0) + Page 29 재귀프로그램 - 실행결과 Bisection Method Page 30 15
We are now 이분법 (bisection method) 을사용한방정식풀이뉴튼-랩슨법 () 을사용한방정식풀이그외의방정식풀이방법 ( 할선법, 가상위치법등 ) 극값 (etreme value) 찾기다항식의인수분해 Page 31 뉴튼 -랩슨 (Newton-Raphson Raphson) 방법이전에 미분그까이껏 ~ 고딩시절에다배운것인데 뭘 ~ 더구나, 1 학년때 Calculus 열심히공부해서 별걱정없을껄 ~ 여러분의기억력을믿지만, 그래도 Back to the Future 미분 (differentiation) 의정의를복습하고, 몇가지중요한함수들에대한도함수 (derivative) 를살펴본다. 뉴튼랩슨방법의이론적 Background 에해당하는테일러정리 (Tayler s Theorem) 에대해서살펴본다. Page 32 16
미분과도함수 (1/10) 정의 : 함수 f() 에서 가 a와다른값을가지면서, a에한없이가까워질때, f() 의값이일정한값 α에한없이가까워지면, a일때, f() 는 α에수렴한다하고, lim a f ( ) = α 와같이나타낸다. 그리고, 이때 α를 f() 의 (a에대한) 극한 ( 값 ) 이라한다. 예제 : lim 03 = 3 = 1 0 1-2 lim 9 log 3 = log33 = 2 Page 33 미분과도함수 (2/10) 정의 : 함수 f() 에서 a일때f() 의값이한없이커지면, a일때f() 는양의무한대로발산한다하고, lim a f ( ) = 와같이나타낸다. 그리고, 이때 f() 의극한은 라한다. 정의 : 함수 f() 에서 a일때f() 의값이음수로서, 그절대값이한없이커지면, a일때f() 는음의무한대로발산한다하고, lim a f ( ) = 와같이나타낸다. 그리고, 이때 f() 의극한은 라한다. 예제 : lim 1 0 = 2 1 2 3 lim 2 ( 1) = Page 34 17
미분과도함수 (3/10) 정의 : f가실수집합x상에정의된함수일때, lim a f ( ) = f ( a ) 이면, f는 a에서연속이라한다. 또한, f가 X의모든점에대해서연속이면f는 X ( 위 ) 에서연속이라한다. y = 2+ 1 예제 연속함수의예 : f( ) = 2+ 1 연속함수가아닌예 : f( ) = 1 2 y = 1 2 Page 35 미분과도함수 (4/10) 정의 : f 가실수집합 X 상에정의된함수라하자. 만일, f'( a) = lim a f( ) f( a) a 이존재하면, f는 a에서미분가능 (differentiable) 하다고한다. 또한, f (a) 를 a에서 f의도함수 (derivative) 라부른다. 그리고, X에있는모든점에서도함수를갖는함수를 X 위에서미분가능하다고하며, a에서 f의도함수는 (a, f(a)) 그래프에대한접선의기울기에해당한다. 다음페이지그래프참조 Page 36 18
미분과도함수 (5/10) 접선은기울기 f (a) 를갖는다. f( a) ( afa, ( )) y = f( ) a 정리 : 만일 f 가 a 에서미분가능하다면, f 는 a 에서연속이다. Page 37 미분과도함수 (6/10) Rolle의정리 : 함수 f가폐구간 [a,b] 에서연속이고개구간 (a,b) 에서미분가능하다고하자. 이때, 만일 f(a) = f(b) 이면, f (c)=0이되는한점c가 (a,b) 상에존재한다. f'( c ) = 0 f( a) = f( b) y = f( ) a c b Page 38 19
미분과도함수 (7/10) 평균값의정리 : 함수 f 가 [a,b] 에서연속이고 (a,b) 에서미분가능하다면, f'( c) = f( b) f( a) b a 가되는수c가 (a,b) 상에존재한다. 평행선 기울기 f'( c) f( b) f( a) 기울기 b a y = f( ) a c b Page 39 미분과도함수 (8/10) 미분법의기본공식 (1) f( ) = c f'( ) = 0 n (2) y= y' = n n 1 (3) y= c f( ) y' = c f'( ) (4) y= f( ) ± g( ) y' = f'( ) ± g'( ) (5) y= f( ) g( ) y' = f'( ) g( ) + f( ) g'( ) f( ) f'( ) g( ) f( ) g'( ) (6) y= ( g( ) 0 ) y' = 2 g ( ) ( ) 1 g'( ) (7) y= y' = g ( ) g( ) { 2 { g Page 40 20
미분과도함수 (9/10) 합성함수의미분법 dy dy du y = f( u), u = g( ) f'( ) = d = du d 3 2 4 y= ( + 2 + 3) 3 2 3 3 2 y' = 4( + 2 + 3) ( + 2 + 3)' 3 2 3 2 y' = 4( + 2 + 3) (3 + 4 ) 삼각함수의미분법 (1) y= sin y' = cos (2) y= cos y' = sin (3) y= tan y' = sec (4) y= cot y' = csc 2 2 1 csc= sin 1 sec= cos 1 cot= tan (5) y= sec y' = sec tan (6) y= csc y' = csc cot Page 41 미분과도함수 (10/10) 지수함수의미분법 (1) y= e y' = e (2) y= a y' = a loga 1 e= lim 1+ = 2.7182818284904523536028... 0 d Given f( ) = a, a that satifies f( ) = f( ) is e. d 로그함수의미분법 (1) y= log 1 y' = (2) y= log a 1 1 y' = loga Page 42 21
테일러정리 (Tayler s Theorem) 함수 f 와 f 의도함수들인 f, f,, f (n) 이 [a,b] 에서연속이고 f (n) 이 (a,b) 에서미분가능하다면, 다음식을만족하는수 c n+1 이존재한다. f( b) = f ''( a) 2 f( a) + f '( a)( b a) + ( b a) + 2! ( n) ( n+ 1) f ( a) n f ( cn+ 1) + ( b a) + ( b a) n! ( n+ 1)! n+ 1 테일러정리를사용한 Approimation Formulas f( ) f( a) + f '( a)( a) f( ) f ''( a) f( a) + f '( a)( a) + ( a) 2 2! Page 43 뉴튼 -랩슨방법개요 (1/6) 이분법의단점 근이존재하는구간을미리알고있어야한다. 지정된구간에근이두개있는경우를해결하지못한다.... 뉴튼-랩슨방법 다음근의값 ( i+1 ) 을현재근의값 ( i ), 함수값, 도함수값을사용하여정한다. f ( 즉, i ) 을사용한다. i+ 1 = i f '( ) 뉴튼-랩슨방법의유도 테일러정리에서유도할수있다. 도함수의정의에의해유도할수있다. i Page 44 22
뉴튼 -랩슨방법개요 (2/6) 테일러정리에서유도 테일러정리에서두번째항까지만을고려한 Approimation Formula 는 f( ) f( a) + f '( a)( a) 이다. 그런데, 근이되는점 에서 f()=0 이므로, 좌변을 0 으로놓고정리하면 = a f ( a) f '( a) 가된다. Page 45 뉴튼 -랩슨방법개요 (3/6) 도함수정의를사용한유도 방법 1 점 (a, f(a)) 에서의접선방정식은기울기가 f (a) 이므로, f '( a) f ( ) f( a) a Recall that f'( a) = lim a f( ) f( a) a 과같이나타낼수있다. 그런데, 근이되는점 에서 f()=0 이므로, f() 를 0 으로놓고정리하면 = a f ( a) f '( a) 가된다. Page 46 23
뉴튼 -랩슨방법개요 (4/6) 도함수정의를사용한유도 - 방법 2 점 (a, f(a)) 에서의접선방정식은다음과같이구할수있다. y = f '( a) +α f ( a) = f '( a) a+α (it goes through ( a, f( a)).) α= f( a) f '( a) a y = f '( a) + f( a) f '( a) a 여기서, y=0으로놓고정리하면다음과같이근을구할수있다. ( ) if y = 0, then = a f a f '( a) 가된다. Page 47 뉴튼 -랩슨방법개요 (5/6) 뉴튼 - 랩슨법으로근을찾아가는과정 기울기 = f ( i ) 기울기 = f ( i+1 ) 기울기 = f ( i+2 ) i + 2 i + 1 i Page 48 24
뉴튼 -랩슨방법개요 (6/6) 뉴튼 - 랩슨법의장점 : 수렴속도가매우빨라서빠른시간내에근을찾을수있다. 뉴튼 - 랩슨법의문제점 : 근을찾지못하는경우가있다. ( 교재 p. 22 의그림 1.4 참조 ) Page 49 뉴튼 -랩슨방법알고리즘 procedure newton( i, e: real numbers) { i is an initial value, i.e., a starting point { e is an allowable error value. while f( i ) > e i := i f( i )/f ( i ); {get a net value return i; Page 50 25
뉴튼 -랩슨방법프로그램 (1/2) 대상함수 : #include <stdio.h> #include <stdlib.h> #include <math.h> f ( ) = log( + 5.0) +, 1.0 f '( ) = + 1.0 ( + 5.0) 1 y= log y' = float f(float); float f_prime(float); // evaluation of f() // evaluation of f () main(int argc, char *argv[]) { int i = 1; float i, e; if(argc < 3) { printf("usage: %s i e\n", argv[0]); eit(0); i = (float)atof(argv[1]); // ascii to float function e = (float)atof(argv[2]); printf("i = %.10f\n", i); printf("e = %.10f\n", e); Page 51 뉴튼 -랩슨방법프로그램 (2/2) while(fabs(f(i)) > e) { i = i - f(i)/f_prime(i); printf("[iteration %02d]: The root is %.10f <with error %.10f>\n", i++, i, fabs(f(i)); float f(float ) { return ((float)log( + 5.0) + ); // f ( ) = log( + 5.0) + float f_prime(float ) { return (1.0/(+5.0) + 1.0); // 1.0 f '( ) = 1.0 + 5.0 + Page 52 26
프로그램실행결과 Page 53 다른함수의예와실행결과 (1/2) 대상함수 : 3 2 2 f ( ) = + 4 10= 0, f '( ) = 3 + 8 이분법알고리즘 ( 프로그램 ) 자체는동일하며, 단지함수 f() 와 f () 만다음과같이달리하면된다. Page 54 27
다른함수의예와실행결과 (2/2) Page 55 28