수치해석 (Numerical Analysis) 일변수 방정식과 함수 (Part 2) 문양세 강원대학교 IT대학 컴퓨터과학전공

We are now … 이분법(bisection method)을 사용한 방정식 풀이 Secant Method 이분법(bisection method)을 사용한 방정식 풀이 뉴튼-랩슨법(Newton-Raphson Method)을 사용한 방정식 풀이 그 외의 방정식 풀이 방법 할선법(Secant Method) 가상 위치법(False Position Method) 극값(extreme value) 찾기 다항식의 인수분해

할선법(Secant Method) 개요 (1/4) 선을 나눈다는 의미인데… 어떻게 한다는 이야기일까요? f(x) a b x r

할선법 개요 (2/4) 뉴튼-랩슨 방법 But, 함수 f(x)의 도함수를 알지 못하거나 존재하지 않는다면? Secant Method 뉴튼-랩슨 방법 현재 포인트인 xi로부터 도함수(f(x))를 사용하여 다음 포인트인 xi+1을 찾는다. But, 함수 f(x)의 도함수를 알지 못하거나 존재하지 않는다면? 할선법: 도함수 대신에 두 점을 사용한 직선의 기울기를 사용한다. 즉, 상기 식에서 f(xi) 대신에 두 점 (xi, f(xi)), (xi-1, f(xi-1))을 사용하여 다음과 같이 f(xi)의 근사 값을 계산한다.

할선법 개요 (3/4) Secant Method f(x) x

할선법 개요 (4/4) 할선법: 뉴튼-랩슨의 f(xi) 대신에 을 대입하여 사용 Secant Method 할선법: 뉴튼-랩슨의 f(xi) 대신에 을 대입하여 사용 Note: 뉴튼-랩슨법에서는 하나의 포인트를 사용하여 다음 포인트를 결정한 반면에, 할선법에서는 두 개의 포인트를 사용한다.

할선법 알고리즘 procedure secant(x1, x2, e: real numbers) Secant Method procedure secant(x1, x2, e: real numbers) { x1 is the first initial value, i.e., the first starting point} { x2 is the second initial value, i.e., the second starting point} { e is an allowable error value.} i := 2; while |f(xi)| > e xi+1 := xi – f(xi)((xi – xi-1)/(f(xi) – f(xi-1)); {get a next value} i := i + 1; return xi;

할선법 프로그램 (1/2) 대상 함수: #include <stdio.h> Secant Method 대상 함수: #include <stdio.h> #include <stdlib.h> #include <math.h> float f(float); // evaluation of f(x) float f_slope(float,float); // evaluation of slope main(int argc, char *argv[]) { int i = 1; float xi_minus, xi, xi_plus, e; if(argc < 4) { printf("Usage: %s x1 x2 e\n", argv[0]); exit(0); } xi_minus = (float)atof(argv[1]); // ascii to float function xi = (float)atof(argv[2]); // ascii to float function e = (float)atof(argv[3]); printf("x1 = %.10f\n", xi_minus); printf("x2 = %.10f\n", xi); printf("e = %.10f\n", e);

할선법 프로그램 (2/2) while(fabs(f(xi)) > e) { Secant Method while(fabs(f(xi)) > e) { xi_plus = xi - f(xi)/f_slope(xi,xi_minus); xi_minus = xi; xi = xi_plus; printf("[Iteration %02d]: The root is %.10f <with error %.10f>\n", i++, xi, fabs(f(xi))); } float f(float x) { return ((float)log(x + 5.0) + x); // float f_slope(float x1, float x2) return ((f(x1)-f(x2))/(x1-x2));

프로그램 실행 결과 Secant Method 뉴튼-랩슨법

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

다른 함수의 예와 실행 결과 (1/2) Secant Method 대상 함수: 할선법 알고리즘(프로그램) 자체는 동일하며, 단지 함수 f(x)만 다음과 같이 달리하면 된다.

다른 함수의 예와 실행 결과 (2/2) Secant Method 뉴튼-랩슨법

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

할선법 알고리즘의 문제점? (1/2) procedure secand(x1, x2, e: real numbers) i := 2; Secant Method procedure secand(x1, x2, e: real numbers) i := 2; while |f(xi)| > e xi+1 := xi – f(xi)((xi – xi-1)/(f(xi) – f(xi-1)); {get a next value} i := i + 1; return xi; i = 2일 때, f(x1), f(x2)가 계산되어 사용된다. i = 3일 때, f(x2), f(x3)이 계산되어 사용된다. i = 4일 때, f(x3), f(x4)가 계산되어 사용된다. i = 5일 때, f(x4), f(x5)가 계산되어 사용된다. ... How can we reduce these duplicated computations?

Any more optimization in memory space? O(N)  O(1)? 할선법 알고리즘의 문제점? (2/2) Secant Method Dynamic Programming Technique: 계산된 내용을 메모리에 저장하고 이를 활용하여 알고리즘의 Complexity를 낮추는 기법 (Space Complexity vs. Time Complexity) procedure secant(x1, x2, e: real numbers) array fval[1..N]; i := 2; fval[i-1] := f(xi-1); fval[i] := f(xi); while |fval[i]| > e xi+1 := xi – fval[i]((xi – xi-1)/(fval[i]– fval[i-1])); i := i + 1; return xi; An Enhanced Secant Algorithm using Dynamic Programming Technique Any more optimization in memory space? O(N)  O(1)?

We are now … 이분법(bisection method)을 사용한 방정식 풀이 Secant Method 이분법(bisection method)을 사용한 방정식 풀이 뉴튼-랩슨법(Newton-Raphson Method)을 사용한 방정식 풀이 그 외의 방정식 풀이 방법 할선법(Secant Method) 가상 위치법(False Position Method) 극값(extreme value) 찾기 다항식의 인수분해

가상 위치법(False Position Method) 개요 (1/6) 이분법의 개선된 형태 이분법에서는 구간 축소를 위하여 기존 구간을 반으로 줄여나가는 방법을 사용하였다. 가상 위치법에서는 현재 구간을 직선으로 연결하여 x축과의 교점을 중심으로 구간을 나눈다.

가상 위치법 개요 (2/6) 이분법 vs. 가상 위치법 Bisection Method False Position Method f(x) f(x) Xm Xm Xm’ Xl’ Xl x Xl x Xh Xh’ Xh Xl’ Xm’ Xh’ Bisection Method False Position Method

가상 위치법 개요 (3/6) False Position Method 교점(xm) 구하기 두 점 (xl, f(xl)), (xh, f(xh))를 잇는 직선의 방정식은 다음과 같다. 직선과 x축과의 교점인 xm은 y=0일 때의 x값에 해당하므로 다음과 같이 구할 수 있다.

가상 위치법 개요 (4/6) 할선법과 가상 위치법의 같은 점: 두 포인트를 대상으로 구한 다음 포인트의 값이 동일하다. False Position Method 할선법과 가상 위치법의 같은 점: 두 포인트를 대상으로 구한 다음 포인트의 값이 동일하다. 할선법의 다음 포인트 가상 위치법의 다음 포인트

가상 위치법 개요 (5/6) False Position Method 할선법과 가상 위치법의 다른 점: 새롭게 구한 포인트를 사용하여 다음 두 포인트를 설정하는 방법이 다르다. 할선법에서는 i번째 포인트인 xi와 다음 포인트인 xi+1이 다다음 포인트인 xi+2 구성에 사용된다. 가상 위치법에서는 (xl, xm) 혹은 (xm, xh) 를 대상으로 부호가 달라지는 쌍을 선택하여 새로운 구간 (xl, xm)으로 삼는다.

가상 위치법 개요 (6/6) 구간 분할: 두 포인트를 연결하는 직선의 x 절편을 분할 값으로 취하는 방법을 사용한다. False Position Method 구간 분할: 두 포인트를 연결하는 직선의 x 절편을 분할 값으로 취하는 방법을 사용한다. 즉, 두 포인트 xl 과 xh 사이에 근이 존재할 때, 분할 값 xm은 다음과 같이 구한다. (이분법과 마찬가지로) f(xm)f(xh)와 f(xm)f(xl)을 조사하여 음수 값을 갖는 경우를 다음 구간으로 사용한다.

가상 위치법 알고리즘 procedure false-position(xl, xh, e: real numbers) False Position Method procedure false-position(xl, xh, e: real numbers) { xl is a left bound value of the range having a root.} { xh is a left bound value of the range having a root.} { e is an allowable error value.} while (xh − xl) > e {f(xm) > e} begin xm := (f(xh)xl - f(xl)xh) / (f(xh) - f(xl)) ; {get the next point} if f(xm)f(xh) = 0 then return xm; else if f(xm)f(xl) < 0 then xh := xm; else if f(xm)f(xh) < 0 then xl := xm; else break; { something wrong  cannot find the root.} end return xm;

가상 위치법 프로그램 (1/2) 대상 함수: #include <stdio.h> False Position Method 대상 함수: #include <stdio.h> #include <stdlib.h> #include <math.h> float f(float x); // evaluation of f(x) main(int argc, char *argv[]) { int i = 1; float xh, xl, xm, e; if(argc < 4) { printf("Usage: %s xh xl e\n", argv[0]); exit(0); } xh = (float)atof(argv[1]); // ascii to float function xl = (float)atof(argv[2]); e = (float)atof(argv[3]); printf("xh = %.10f\n", xh); printf("xl = %.10f\n", xl); printf("e = %.10f\n", e);

가상 위치법 프로그램 (2/2) xm = xh; // set an initial point False Position Method xm = xh; // set an initial point while(fabs((xm)) > e) { xm = (f(xh)*xl - f(xl)*xh) / (f(xh) - f(xl)); if((f(xm)*f(xh)) == (float)0) break; else if((f(xm)*f(xl)) < (float)0) xh = xm; else if((f(xm)*f(xh)) < (float)0) xl = xm; else { printf("Something worng --> cannot find the root.\n"); break; } printf("[Iteration %02d]: The root is %.10f <with error %.10f>\n", i++, xm, fabs(f(xm))); float f(float x) { return ((float)log(x + 5.0) + x); // f(x) = log(x+5.0)+x

프로그램 실행 결과 (1/2) False Position Method 이분법

프로그램 실행 결과 (2/2) False Position Method 이분법

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

다른 함수의 예와 실행 결과 (1/2) False Position Method 대상 함수: 가상 위치법 알고리즘(프로그램) 자체는 동일하며, 단지 함수 f(x)만 다음과 같이 달리하면 된다.

다른 함수의 예와 실행 결과 (2/2) False Position Method 이분법

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

중근의 문제 (1/2) 중근의 예 중근에 대해 알고리즘이 제대로 동작하지 않는 경우 False Position Method 중근의 예 중근에 대해 알고리즘이 제대로 동작하지 않는 경우 이분법(및 가상 위치법)의 경우, 근의 양쪽에서 부호의 변화가 없어서 근을 찾을 수 없게 된다. 뉴튼-랩슨법(및 할선법)의 경우, f(a)의 값이 0이 되면 근을 구할 수 없다. y 중근

중근의 문제 (2/2) False Position Method 중근 해결책 알고리즘에 특수한 경우(special case)를 처리하는 부분을 넣는다. 예) f(xm) == 0 ?, f(xh)f(xl) == 0 ? 등에 대한 처리 삽입 f(a)=0인 경우를 처리하기 위하여 치환법을 사용한다. 예) g(x) = f(x)/f(x)의 새로운 함수를 선언하고, f(x)가 아닌 g(x)의 근을 찾는다. (f(x)=0 이면 반드시 g(x)=0이기 때문에, g(x)=0의 근은 f(x)=0의 근이 될 가능성이 높다.) 자세한 내용은 생략… Why? 일반적으로 중근은 분석적 방법에 의해 찾아낼 수 있다.

We are now … 이분법(bisection method)을 사용한 방정식 풀이 Extreme Value Localization 이분법(bisection method)을 사용한 방정식 풀이 뉴튼-랩슨법(Newton-Raphson Method)을 사용한 방정식 풀이 그 외의 방정식 풀이 방법(할선법, 가상 위치법 등) 극값(extreme value) 찾기 (이분법, 뉴튼법, 포물선) 다항식의 인수분해

극대값(local maximum) 및 최대값(global maximum) 극값 찾기 (Extreme Value Localization) Extreme Value Localization Recall: 극대값(최대값), 극소값(최소값) f(x) x 극대값(local maximum) 및 최대값(global maximum) 극대값(local maximum) 극소값(local minimum) 0점, i.e., 근

극대값? 극소값? 이것이 또 미분과 쪼금 관계가 있다고 합니다. Extreme Value Localization 이것이 또 미분과 쪼금 관계가 있다고 합니다. 여러분 기억을 되살려 다시금 Back to your high school

극대  극소와 미분 (1/4) Extreme Value Localization 함수의 증가와 감소 함수 f(x)가 구간 X내의 임의의 두 수 a, b에 대해서 a < b  f(a) < f(b) 이면, f(x)는 구간 X에서 단조증가 또는 증가한다고 한다. 함수 f(x)가 구간 X내의 임의의 두 수 a, b에 대해서 a < b  f(a) > f(b) 이면, f(x)는 구간 X에서 단조감소 또는 감소한다고 한다. f(x) a b x f(a) f(b) f(x) a b x f(b) f(a)

극대  극소와 미분 (2/4) 함수 f(x)가 구간 X에서 미분가능이고, 그 구간에서 함수 f(x)에서 Extreme Value Localization 함수 f(x)가 구간 X에서 미분가능이고, 그 구간에서 항상 f(x) > 0 이면, f(x)는 구간 X에서 증가한다. (기울기가 양수이므로) 항상 f(x) < 0 이면, f(x)는 구간 X에서 감소한다. (기울기가 음수이므로) 항상 f(x) = 0 이면, f(x)는 구간 X에서 상수이다. (기울기가 0이므로) 함수 f(x)에서 f(a) > 0 이면, f(x)는 x = a 에서 증가상태에 있다. f(a) < 0 이면, f(x)는 x = a 에서 감소상태에 있다.

극대  극소와 미분 (3/4) f(x)에 의한 극대 및 극소의 판정: f(x)에 의한 극값의 판정: Extreme Value Localization f(x)에 의한 극대 및 극소의 판정: 함수 f(x)에서 f(a) = 0 이고, x = a 의 좌우에서 f(x)의 부호가 양에서 음으로 변하면, f(x)는 x = a 에서 극대이고, 극대값은 f(a)이다. 음에서 양으로 변하면, f(x)는 x = a 에서 극소이고, 극소값은 f(a)이다. f(x)에 의한 극값의 판정: 함수 f(x)에서 f(x), f(x)가 존재할 때, f(a) = 0, f(a) < 0(기울기가 감소 상태, f(x)가 양  0  음)이면, f(x)는 x = a 에서 극대이고, 극대값은 f(a)이다. f(a) = 0, f(a) > 0(기울기가 증가 상태, f(x)가 음  0  양)이면, f(x)는 x = a 에서 극소이고, 극소값은 f(a)이다.

극대  극소와 미분 (4/4) 곡선의 요철과 변곡점: Extreme Value Localization 곡선의 요철과 변곡점: f(x) > 0 인 구간(기울기 증가 구간, f(x): 음0양)에서, 곡선 f(x)는 아래로 볼록하다. f(x) < 0 인 구간(기울기 감소 구간, f(x): 양0음)에서, 곡선 f(x)는 위로 볼록하다. f(a) = 0 이고, x = a 의 좌우에서 f(x)의 부호가 바뀌면, 점 (a, f(a))는 곡선 f(x)의 변곡점이다. 아래로 볼록 위로 볼록

테일러 정리를 통한 극대극소의 확인 테일러 정리 극값인 경우, a에서 f(a) = 0이므로, 다음 식이 성립한다. Extreme Value Localization 테일러 정리 극값인 경우, a에서 f(a) = 0이므로, 다음 식이 성립한다. 상기 식에서 (x – a)2는 항상 양의 값을 가지므로, f(a) > 0 이면, f(x)는 x = a 에서 극소값을 갖고, 그 양쪽에서 모두 증가하는 모양을 취한다. 반면에, f(a) < 0 이면, f(x)는 x = a 에서 극대값을 갖고, 그 양쪽에서 모두 감소하는 모양을 취한다.

We are now … 이분법(bisection method)을 사용한 방정식 풀이 Extreme Value Localization 이분법(bisection method)을 사용한 방정식 풀이 뉴튼-랩슨법(Newton-Raphson Method)을 사용한 방정식 풀이 그 외의 방정식 풀이 방법(할선법, 가상 위치법 등) 극값(extreme value) 찾기 (이분법, 뉴튼법, 포물선) 다항식의 인수분해

이분법을 이용한 극소값 찾기 – 개요 (1/2) Extreme Value Localization 극소값의 성질: 일변수 함수 f(x)의 극소값이 xm이라 하면, 다음 조건식 성립한다. y x

이분법을 이용한 극소값 찾기 – 개요 (2/2) Extreme Value Localization 극소값의 성질의 활용: 1) 세 점을 같은 간격으로 배치한다. 2) 세 점이 상기 성질을 만족할 때 까지 같은 간격으로 이동해 간다. 3) 상기 성질을 만족하면, 간격을 반으로 줄인다. 4) 원하는 조건(에러)이 될 때까지 2) ~ 4) 단계를 반복한다. 1) 2) 3) f(x) f(x) f(x)

이분법을 이용한 극소값 찾기 - 알고리즘 procedure bisection-min(xl, s, e: real numbers) Extreme Value Localization procedure bisection-min(xl, s, e: real numbers) { xl is an initial left point.} { s is an initial interval.} { e is an allowable error value.} while s > e xm := xl + s; xr := xm + s; {xr := xl + 2s}; if f(xm) < f(xl) and f(xm) < f(xr) then s := s / 2; {make the interval into a half of it.} else xl := xm; {shift by the interval.} return xm;

이분법을 이용한 극소값 찾기 – 프로그램 I (1/2) Extreme Value Localization 대상 함수: #include <stdio.h> #include <stdlib.h> #include <math.h> float f(float x); // evaluation of f(x) main(int argc, char *argv[]) { int i = 1; float xl, xr, xm, s, e; if(argc < 4) { printf("Usage: %s xl s e\n", argv[0]); exit(0); } xl = (float)atof(argv[1]); s = (float)atof(argv[2]); e = (float)atof(argv[3]); printf("xl = %.10f\n", xl); printf("s = %.10f\n", s); printf("e = %.10f\n", e);

이분법을 이용한 극소값 찾기 – 프로그램 I (2/2) Extreme Value Localization while(s > e) { xm = xl + s; xr = xm + s; if((f(xm) < f(xl)) && (f(xm) < f(xr))) s = s / 2.0; // a half else xl = xm; // shift by s printf("[%02d]: The min is (%.8f, %.8f) <with error %.8f>\n", i++, xm, f(xm), s); } float f(float x) { return ( (2.5*pow(x,2.0)) - (7.0*x) + 2.5); //

이분법을 이용한 극소값 찾기 – 실행 결과 I Extreme Value Localization

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

이분법을 이용한 극소값 찾기 – 프로그램 II 대상 함수: Extreme Value Localization 대상 함수: 이분법 알고리즘(프로그램) 자체는 동일하며, 단지 함수 f(x)만 다음과 같이 달리한다.

발산하거나 통과하는 경우가 종종 발생함에 유의한다… 이분법을 이용한 극소값 찾기 – 실행 결과 II Extreme Value Localization 발산하거나 통과하는 경우가 종종 발생함에 유의한다…

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

이분법을 이용한 극대값 찾기 - 개요 극대값의 성질: 일변수 함수 f(x)의 극대값이 xm이라 하면, 다음 조건식 성립한다. Extreme Value Localization 극대값의 성질: 일변수 함수 f(x)의 극대값이 xm이라 하면, 다음 조건식 성립한다. y x

이분법을 이용한 극대값 찾기 - 알고리즘 procedure bisection-max(xl, s, e: real numbers) Extreme Value Localization procedure bisection-max(xl, s, e: real numbers) { xl is an initial left point.} { s is an initial interval.} { e is an allowable error value.} while s > e xm := xl + s; xr := xm + s; if f(xm) > f(xl) and f(xm) > f(xr) then s := s / 2; {make the interval into a half of it.} else xl := xm; {shift by the interval.} return xm;

You may see this program in the exam. 이분법을 이용한 극대값 찾기 – 프로그램 및 예제 Extreme Value Localization 더 쉬운 방법  함수 f(x)의 극대값 대신에 f(x)의 극소값을 찾으면 된다. Please do it yourself… You may see this program in the exam.

One more tips Extreme Value Localization 일정 간격으로 이동하면서 극한값이 존재하는 구간을 찾는 방법은… 앞서 이분법, 가상 위치법에서 근을 찾는 방법에 활용할 수 있다. 즉, 일정 간격으로 이동하면서, 근이 존재하는 구간을 찾아낸 후, 이분법(or 가상 위치접)을 적용하여 보다 정확한 근을 찾아내는 것이다.

We are now … 이분법(bisection method)을 사용한 방정식 풀이 Extreme Value Localization 이분법(bisection method)을 사용한 방정식 풀이 뉴튼-랩슨법(Newton-Raphson Method)을 사용한 방정식 풀이 그 외의 방정식 풀이 방법(할선법, 가상 위치법 등) 극값(extreme value) 찾기 (이분법, 뉴튼법, 포물선) 다항식의 인수분해

뉴튼법을 이용한 극소값 찾기 – 개요 (1/2) 함수 f(x)의 일차 도함수 f(x)의 성질을 이용한다. Extreme Value Localization 함수 f(x)의 일차 도함수 f(x)의 성질을 이용한다. 1) f(a) < 0 이면, 감소하는 구간으로서 극소값은 a보다 더 오른쪽에 존재하고, 2) f(a) > 0 이면, 증가하는 구간으로서 극소값은 a보다 더 왼쪽에 존재한다. 따라서, 다음 식을 사용하여 xi를 반복 계산하여 극소값으로 수렴해 간다. 1) f(xi) < 0 이면, cf(xi)가 음수(-cf(xi)는 양수)가 되어 xi+1 은 오른쪽으로 이동 2) f(xi) > 0 이면, cf(xi)가 양수(-cf(xi)는 음수)가 되어 xi+1 은 왼쪽으로 이동 상수 c는 좌우로 움직이는 폭을 결정한다.

뉴튼법을 이용한 극소값 찾기 – 개요 (2/2) 상수 c의 값이 Extreme Value Localization 상수 c의 값이 너무 크면, 근을 중심으로 진동이 있을 수 있고, 너무 작으면, 수렴 속도가 너무 느린 문제점이 있다. |xi+1 – xi|가 주어진 에러 값을 가질 때까지 반복하여 근사 값을 찾는다. 뉴튼-랩슨법과 마찬가지로 발산하거나 통과하는 경우가 발생할 수 있다.

뉴튼법을 이용한 극소값 찾기 - 알고리즘 procedure newton-min(x1, c, e: real numbers) Extreme Value Localization procedure newton-min(x1, c, e: real numbers) { x1 is an initial point.} { c is a constant for the Newton equation.} { e is an allowable error value.} i := 0; do i++; xi+1 := xi – cf(xi); while |xi+1 - xi| > e return xi+1;

뉴튼법을 이용한 극소값 찾기 – 프로그램 (1/2) Extreme Value Localization 대상 함수: #include <stdio.h> #include <stdlib.h> #include <math.h> float f(float x); // evaluation of f(x) float f_prime(float x); // evaluation of the derivative of f(x) main(int argc, char *argv[]) { int i = 1; float xi, xi_plus, c, e, delta; if(argc < 4) { printf("Usage: %s x1 c e\n", argv[0]); exit(0); } xi = (float)atof(argv[1]); c = (float)atof(argv[2]); e = (float)atof(argv[3]); printf("x1 = %.10f\n", xi); printf("c = %.10f\n", c); printf("e = %.10f\n", e);

뉴튼법을 이용한 극소값 찾기 – 프로그램 (2/2) Extreme Value Localization do { xi_plus = xi - c*f_prime(xi); delta = fabs(xi_plus - xi); printf("[%02d]: The min is (%.8f, %.8f) <with error %.8f>\n", i++, xi_plus, f(xi_plus), delta); xi = xi_plus; } while(delta > e); } float f(float x) { return ( (2.5*pow(x,2.0)) - (7.0*x) + 2.5); // float f_prime(float x) return ( 5.0*x - 7.0); //

뉴튼법을 이용한 극소값 찾기 – 실행 결과 Extreme Value Localization 이분법

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

뉴튼법을 이용한 극대값 찾기 - 개요 함수 f(x)의 일차 도함수 f(x)의 성질을 이용한다. Extreme Value Localization 함수 f(x)의 일차 도함수 f(x)의 성질을 이용한다. 1) f(a) < 0 이면, 감소하는 구간으로서 극대값은 a보다 더 왼쪽에 존재하고, 2) f(a) > 0 이면, 증가하는 구간으로서 극대값은 a보다 더 오른쪽에 존재한다. 따라서, 다음 식을 사용하여 xi를 반복 계산하여 극대값으로 수렴해 간다. 1) f(xi) < 0 이면, cf(xi)가 음수가 되어 xi+1 은 왼쪽으로 이동한다. 2) f(xi) > 0 이면, cf(xi)가 양수가 되어 xi+1 은 오른쪽으로 이동한다. 상수 c는 좌우로 움직이는 폭을 결정한다.

뉴튼법을 이용한 극대값 찾기 - 알고리즘 procedure newton-max(x1, c, e: real numbers) Extreme Value Localization procedure newton-max(x1, c, e: real numbers) { x1 is an initial point.} { c is a constant for the Newton equation.} { e is an allowable error value.} i := 0; do i++; xi+1 := xi + cf(xi); while |xi+1 - xi| > e return xi+1;

You may see this program in the exam. 이분법을 이용한 극대값 찾기 – 프로그램 및 예제 Extreme Value Localization 더 쉬운 방법  함수 f(x)의 극대값 대신에 f(x)의 극소값을 찾으면 된다. Please do it your self… You may see this program in the exam.

We are now … 이분법(bisection method)을 사용한 방정식 풀이 Extreme Value Localization 이분법(bisection method)을 사용한 방정식 풀이 뉴튼-랩슨법(Newton-Raphson Method)을 사용한 방정식 풀이 그 외의 방정식 풀이 방법(할선법, 가상 위치법 등) 극값(extreme value) 찾기 (이분법, 뉴튼법, 포물선) 다항식의 인수분해

포물선을 이용한 극소값 찾기 – 그 이전에 Extreme Value Localization 포물선 방정식 (이차 방정식) 1) 꼭지점의 좌표 (m, n)이 주어진 경우, 다음 식을 이용한다. 2) x 절편 (, 0), (, 0)가 주어진 경우, 다음 식을 이용한다. 3) 세 점이 주어진 경우, 다음 식을 이용한다.  세 점을 대입한 후, (삼원 일차) 연립 방정식을 풀어낸다. 꼭지점의 좌표

포물선을 이용한 극소값 찾기 – 개요 (1/3) Extreme Value Localization 일변수 함수의 그래프에서 세 점이 주어지면, 이 세 점을 지나는 이차 곡선인 포물선 방정식을 구할 수 있다. 포물선 방정식의 꼭지점 x 좌표를 반복적으로 활용하면, 극소값의 근사값을 계산할 수 있다. 1) 세 점 A, B, C를 지나는 포물선 방정식을 구하고, 그 꼭지점의 x 좌표를 X라 한다. 2) 꼭지점의 x 좌표인 X에 가까운 두 점을 선택하고, 이 둘과 (x, f(x))를 다시 세 점 A, B, C로 삼는다. 3) 원하는 에러 값에 이른 경우, 꼭지점의 x축 값을 극소값으로 삼으며, 그렇지 못한 경우, 상기 1)~3)의 과정을 반복한다.

포물선을 이용한 극소값 찾기 – 개요 (2/3) 포물선 근사를 사용한 극소값 찾기 – 그림 예제 A C B C A X B Extreme Value Localization 포물선 근사를 사용한 극소값 찾기 – 그림 예제 A B C X A B C X

포물선을 이용한 극소값 찾기 – 개요 (3/3) Extreme Value Localization 세 점 (a, f(a)), (b, f(b)), (c, f(c))를 지나는 포물선 방정식을 구했을 때, 꼭지점의 x 좌표는 다음과 같다. Let the equation above be “x = vertex(a, b, c).” 책의 수식(p. 41, 식 13)에 오류 있음 (분모의 첫번째 f(a)  f(c))

포물선을 이용한 극소값 찾기 – 알고리즘 (1/2) Extreme Value Localization procedure brent-min(a, b, c, e: real numbers) { a, b, and c are initial starting points. (a < b < c)} { e is an allowable error value.} do xm := vertex(a, b, c); if xm < a then { Case i)} begin c := b; b := a; a := xm; end else if xm < b then { Case ii)} begin c := b; b := xm; end else if xm < c then { Case iii)} begin a := b; b := xm; end else { Case iv)} begin a := b; b := c; c := xm; end while |a - c| > e return xm;

포물선을 이용한 극소값 찾기 – 알고리즘 (2/2) Extreme Value Localization a b c xm xm xm xm Case i)  a = xm  b = a  c = b Case ii)  a = a  b = xm  c = b Case iii)  a = b  b = xm  c = c Case iv)  a = b  b = c  c = xm

포물선을 이용한 극소값 찾기 – 프로그램 (1/3) Extreme Value Localization 대상 함수: #include <stdio.h> #include <stdlib.h> #include <math.h> float f(float); // evaluation of f(x) float vertex(float, float, float); // find the vertex main(int argc, char *argv[]) { int i = 1; float a, b, c, xm, xe, e; if(argc < 5) { printf("Usage: %s a b c e\n", argv[0]); exit(0); } a = (float)atof(argv[1]); b = xm = (float)atof(argv[2]); c = (float)atof(argv[3]); e = (float)atof(argv[4]); printf("(a, b, c) = (%.8f, %.8f, %.8f)\n", a, b, c); printf("e = %.8f\n", e);

포물선을 이용한 극소값 찾기 – 프로그램 (2/3) Extreme Value Localization do { xe = xm; xm = vertex(a, b, c); if(xm < a) { c = b; b = a; a = xm; } else if(xm < b){ c = b; b = xm; } else if(xm < c){ a = b; b = xm; } else { a = b; b = c; c = xm; } printf("[%02d]: The min is (%.8f, %.8f) <with error %.8f>\n", i++, xm, f(xm), fabs(xm–xe)); } while(fabs(xm-xe) > e); float f(float x) { return ( (2.5*pow(x,2.0)) - (7.0*x) + 2.5); //

포물선을 이용한 극소값 찾기 – 프로그램 (3/3) Extreme Value Localization float vertex(float a, float b, float c) { float xm; float fa = f(a), fb = f(b), fc = f(c); xm = (b-a)*(b-a)*(fb-fc) – (b-c)*(b-c)*(fb-fa); xm = xm / ((b-a)*(fb-fc) – (b-c)*(fb-fa)); xm = b – 0.5 * xm; } 교재 프로그램(p. 43)에 오류 있음 (line 8: (xm < c)  (xm < b))

포물선을 이용한 극소값 찾기 – 실행 결과 Extreme Value Localization 뉴튼법 이분법

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

포물선을 이용한 극소값 찾기 – 프로그램 II 대상 함수: Extreme Value Localization 대상 함수: 알고리즘(프로그램) 자체는 동일하며, 단지 함수 f(x)만 다음과 같이 달리한다.

포물선을 이용한 극소값 찾기 – 실행결과 II Extreme Value Localization 교재의 실행결과(p. 44)에 오류 있음 (구간이 잘못 주어져 극소값 대신에 극대값을 찾은 오류임)

포물선을 이용한 극대값 찾기 개념 및 알고리즘이 극소값 찾기와 동일하다. (꼭지점 찾기이므로…) 극대값 찾기의 예제: Extreme Value Localization 개념 및 알고리즘이 극소값 찾기와 동일하다. (꼭지점 찾기이므로…) 극대값 찾기의 예제:

안드로이드 프로그래밍 – 코드(일부) Bisection Method

안드로이드 프로그래밍 – 실행결과 Bisection Method

We are now … 이분법(bisection method)을 사용한 방정식 풀이 Polynomial Factorization 이분법(bisection method)을 사용한 방정식 풀이 뉴튼-랩슨법(Newton-Raphson Method)을 사용한 방정식 풀이 그 외의 방정식 풀이 방법(할선법, 가상 위치법 등) 극값(extreme value) 찾기 다항식의 인수분해 (Polynomial Factorization)

다항식의 인수분해 n차원 다항식 인수분해 n차원 다항식 인수분해 방법 1) 조립제법 … Polynomial Factorization n차원 다항식 인수분해 n차원 다항식 인수분해 방법 1) 조립제법 … 2) 축 옮기기 + Routh-Hurwitz Test(기계, 항공 등)  교과서 방법 3) Muller 방법 … I’ll skip this section since 1) the text boot is incomplete, and 2) I think it is not important in computer science.

Homework #1 Polynomial Factorization