수치해석 (Numerical Analysis) 다변수 방정식과 함수 (Part 2) 문양세 강원대학교 IT대학 컴퓨터과학전공
We are now … 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) Gradient Search 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) 더욱 세밀한 이차원 이분 격자법 다차원 극값을 구하기 위한 경사도 탐색 (Gradient Search) 이차원 경사도 탐색법 수치 미분을 사용한 방법 가파른 경사법 (Steepest Descent)
들어가기 이전에 … 편미분(partial derivative)에 대한 기본적인 이해가 있어야 한다. Gradient Search 편미분(partial derivative)에 대한 기본적인 이해가 있어야 한다. 미분도 어려운데, 편미분이 머야? 편두통은 몰라도… 글고, my high school 시절에 편미분 배웠나? 대학에서 배운 거 같기는 한데… 뭐 더라?
편미분 기초 (1/3) Gradient Search 변수 x에 대한 함수 f(x,y)의 편미분 (partial derivative of f w.r.t. x) y를 상수(constant)로 보고 f를 x에 대해 미분한다. 편미분 예제 (1/2)
편미분 기초 (2/3) Gradient Search 편미분 예제 (2/2)
편미분 기초 (3/3) 고차 편미분 (High order partial derivatives) 고차 편미분 예제 Gradient Search 고차 편미분 (High order partial derivatives) 고차 편미분 예제
다차원 극값의 특성 Gradient Search 극값과 차원 일차원: x 값을 변화시키면서 극값을 찾아나간다. 이차원: x 값과 함께 y 값도 변화시키면서 극값을 찾아나가야 한다. 연속인 함수 f(x,y)는 다음 조건 하에서 임계점(critical point)을 갖는다. (임계점이란, 극소값, 극대값, 변곡점을 통칭한다.) 상기 조건의 의미는 x축 관점에서도 기울기가 0이고, y축 관점에서도 기울기가 0이란 의미이다. (일차원의 경우, f(c) = 0이면 임계점을 가짐과 동일하다.)
We are now … 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) Gradient Search 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) 더욱 세밀한 이차원 이분 격자법 다차원 극값을 구하기 위한 경사도 탐색 (Gradient Search) 이차원 경사도 탐색법 수치 미분을 사용한 방법 가파른 경사법 (Steepest Descent)
Recall: 뉴튼법을 이용한 일차원 극소값 찾기 Gradient Search 함수 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는 좌우로 움직이는 폭을 결정한다.
이차원 경사도 탐색법 개념 일차원 뉴튼법을 이차원으로 확장시킨다. 상수 c는 좌우 및 상하로 움직이는 폭을 결정한다. Gradient Search 일차원 뉴튼법을 이차원으로 확장시킨다. 1) 이면, 가 음수가 되어 xi+1 은 오른쪽으로 이동한다. 2) 이면, 가 양수가 되어 xi+1 은 왼쪽으로 이동한다. 3) 이면, 가 음수가 되어 yi+1 은 위쪽으로 이동한다. 4) 이면, 가 양수가 되어 yi+1 은 아래쪽으로 이동한다. 상수 c는 좌우 및 상하로 움직이는 폭을 결정한다.
Recall: 뉴튼법을 이용한 극소값 찾기 - 알고리즘 Gradient Search 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 – cf(xi); while |xi+1 - xi| > e return xi+1;
이차원 경사도 탐색법 알고리즘 (1/2) Gradient Search procedure gradient-min(x1, y1, c, e: real numbers) { (x1, y1) 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 – ; yi+1 := yi – ; while return (xi+1,yi+1);
이차원 경사도 탐색법 알고리즘 (2/2) 에러 의 의미 Gradient Search 에러 의 의미 극(소)값에 접하는 평면의 x 기울기( ) 및 y 기울기( )는 모두 0이 된다. 따라서, 상기 에러 값은 이들 기울기의 제곱 합에 대한 제곱근(Euclidean distance)를 나타낸다. 에러의 더더욱 많은 의미에 대해서는 다른 교재를 참조하세요…
이차원 경사도 탐색법 프로그램 (1/3) Gradient Search 대상 함수:
이차원 경사도 탐색법 프로그램 (2/3) Gradient Search
이차원 경사도 탐색법 프로그램 (3/3) 교재 p. 87 및 p. 91의 f(x,y)식에서 –y2는 +y2가 되어야 함 Gradient Search 교재 p. 87 및 p. 91의 f(x,y)식에서 –y2는 +y2가 되어야 함
이차원 경사도 탐색법 실행 결과 Gradient Search
안드로이드 프로그래밍 – 코드(일부)
안드로이드 프로그래밍 – 실행결과
We are now … 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) Gradient Search 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) 더욱 세밀한 이차원 이분 격자법 다차원 극값을 구하기 위한 경사도 탐색 (Gradient Search) 이차원 경사도 탐색법 수치 미분을 사용한 방법 가파른 경사법 (Steepest Descent)
수치 미분법의 동기 편미분을 구하기 어려운 방정식에 대해서, 편미분의 정의를 활용한다. Numeric Derivatives 편미분을 구하기 어려운 방정식에 대해서, 편미분의 정의를 활용한다. 상기 식에서 x 및 y에 대하여, 충분히 작은 상수 값 를 사용하여, 편미분의 근사값을 구하고, 이를 편미분 대신 사용한다. 근을 찾을 때, 뉴튼-랩슨 대신에 할선법을 사용한 개념과 동일하다.
수치 미분법의 개념 경사도 탐색법의 편미분 수식 대신에 다음 식과 같이 를 도입한다. Numeric Derivatives 경사도 탐색법의 편미분 수식 대신에 다음 식과 같이 를 도입한다. 상기 식에서 는 0에 가까운 충분히 작은 수이며, 상수 c는 좌우 및 상하로 움직이는 폭을 결정한다.
수치 미분법 알고리즘 procedure numeric-der(x1, y1, c, , e: real numbers) Numeric Derivatives procedure numeric-der(x1, y1, c, , e: real numbers) { (x1, y1) is an initial point.} { c is a constant for the Newton equation.} { is the user-specified interval value.} { e is an allowable error value.} i := 0; do i++; xi+1 := xi – ; yi+1 := yi – ; while return (xi+1,yi+1);
수치 미분법 프로그램 (1/3) Numeric Derivatives 대상 함수:
수치 미분법 프로그램 (2/3) Numeric Derivatives
수치 미분법 프로그램 (3/3) Numeric Derivatives
수치 미분법 실행 결과 Numeric Derivatives 이차원 경사도 탐색법
안드로이드 프로그래밍 – 코드(일부)
안드로이드 프로그래밍 – 실행결과
다른 함수 예제 프로그램 (교재) Numeric Derivatives 대상 함수: 다음과 같이 함수 부분만 다름
다른 함수 예제 실행 결과 (교재) Numeric Derivatives
안드로이드 프로그래밍 – 코드 & 실행결과
We are now … 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) Steepest Descent 이차원 이분 격자(bisection grid)법 영점 곡선 추적 (Zero-Curve Tracking) 더욱 세밀한 이차원 이분 격자법 다차원 극값을 구하기 위한 경사도 탐색 (Gradient Search) 이차원 경사도 탐색법 수치 미분을 사용한 방법 가파른 경사법 (Steepest Descent)
가파른 경사법 개념 경사도 탐색법에서는 일정한 비율로 경사를 탐색해 나가는 반면에, Steepest Descent 경사도 탐색법에서는 일정한 비율로 경사를 탐색해 나가는 반면에, 가파른 경사법에서는 경사가 급한 방향으로 탐색해 나간다. 자세한 개념, 유도 과정, 알고리즘은 생략한다.
Homework #2