제 5 장. 보간법(Interpolation)

Presentation on theme: "제 5 장. 보간법(Interpolation)"— Presentation transcript:

1 제 5 장. 보간법(Interpolation)
보간법이란? 선형 보간법 다항식에 의한 보간법 Newton 보간 공식의 차분 표현 반복 선형 보간법 보간다항식의 오차 Spline 함수 보간법

2 Problem solving tools :
Computer Statistics, Numerical Methods, Graphics, etc Theory Problem Definition Mathematical Model Numeric or graphic results Implementation Data

3 1. 보간법이란? 측정하지 않았거나, 측정할 수 없는 값을 구해야 할 경우에 사용.
x0 < x1 <  < xn으로 주어진 n + 1개의 변수에 대한 함수 값을 알고 있을 때, 이들 n + 1개의 모든 점을 통과하는 근사 함수를 이용하여, 구간 [x0 , xn]내의 임의의 점 x에 대한 함수 값을 구하는 방법을 보간법이라고 한다. 보간 함수로는 다항식이 주로 사용된다.

4 1. 보간법이란?(cont.) 다항식을 이용한 보간법
(n + 1)개의 데이터들이 존재한다면, 모든 점들을 통과하는 다항식은 차수가 n으로서 유일한 다항식이다.

5 2. 선형 보간법 두 개의 점이 주어졌을 경우, 두 점을 지나는 함수 f(x)를 직선의 방정식으로 구한다.
를 직선의 방정식이라고 하면, 두 점(x0, f(x0)), (x1, f(x1))를 지나는 직선을 구할 수 있다.

6 2. 선형 보간법(cont.) 일반적으로 데이터 점들 사이의 간격이 작으면 작을수록 더욱 좋은 근사값을 얻게 됨.
간격이 감소함으로써 연속함수를 직선으로 근사 시키기가 좋기 때문임.

7 2. 선형 보간법(cont.) Examples: 자연로그 ln 2를 계산하기 ln1=0과 ln6 = 1.7917595 사이에서

8 3. 다항식에 의한 보간법 (n + 1)개의 점을 지나는 다항식을 n 차 이하의 유일한 다항식으로 표시할 수 있다.
다항식을 찾아내는 방법 미정 계수법 Newton 보간법 Lagrange 보간법

9 3.1 미정 계수법 다항식을 찾아내는 가장 보편적인 방법이다.
보간 다항식을 p(x) = a0+a1x+a2x2+…+anxn 라고 하면, 주어진 자료 점에서 다음과 같은 관계가 성립한다.

10 3.1 미정 계수법(cont.) 이 식을 행렬로 표현하면 다음과 같다.
Gauss 소거법 등으로 계산하여, a0 , a1 ,… an을 구한다.

11 3.1 미정 계수법(cont.) 소거법을 사용하면, 계산 시간이 많이 걸리고 오차가 많이 발생하게 됨.
보간 다항식을 다르게 표현하여 계산 과정을 줄임으로써 오차를 작게 하는 방법이 필요 Newton 보간법 Lagrange 보간법

12 3.2 Newton 보간법 Newton 보간 다항식 pn(x)을 정의하고, 각 계수를 구하는 방법이다.

13 3.2 Newton 보간법(cont.)

14 3.2 Newton 보간법(cont.) 계수 행렬이 하삼각 행렬이므로 계산 횟수가 미정 계수법 보다 작아짐.
모든 다항식의 계수 값을 쉽게 구할 수 있음.

15 3.3 Lagrange 보간법 제차분 계산을 하지 않도록 Newton 다항식을 간단하게 다시 공식화 한 것.
(n+1)개의 점을 지나는 n 차 이하 보간 다항식 pn(x) = L0(x)a0 + L1(x)a1 + … + Ln(x)an을 정의하고, 각 계수를 구하는 방법.

16 3.3 Lagrange 보간법(cont.) pn(x) = L0(x)a0 + L1(x)a1 + … + Ln(x)an 에 모든 점을 대입.

17 3.3 Lagrange 보간법(cont.) 위 식을 계산하면, 다항식의 계수는 f(xi)인 값을 갖게 된다.
pn(x) = L0(x)f(x0) + L1(x) f(x1) + … + Ln(x) f(xn) 교재 p.193 : 예제 (5.2) (5.3) 계산 시간이 비교적 짧고, 간단하며 자료의 구간에 관계없이 사용할 수 있음.

18 4. Newton보간 공식의 차분 표현 유한 차분 종류 : 함수 f(x)의 차분은 f(x1)과 f(x2)의 차이가 된다.
전향 차분 :  f(xi) 후향 차분 :  f(xi) 중심 차분 :  f(xi)

19 4. 차분 표현(cont.) 계차와 차분표 제 1 계차 : x를 m등분한 점들 의 함수 값의 차분 .
제 2 계차는 제 1 계차의 차분, 제 k 계차는 제 k-1 계차에서 인접한 2개의 함수 값의 차분. 제 k 계차는 Dk 로 표시한다. 계차표 : textbook p.195

20 4. 차분 표현(Cont.) 차분상과 보간법 제1 계 차분상 : 제 2 계 차분상 : 제 k 계 차분상 :

21 4. 차분 표현(Cont.) 차분상은 Newton 보간법의 계수를 구할 수 있음.

22 4. 차분 표현(Cont.) Newton의 보간 공식은 다시 정의할 수 있다.

23 4. 차분 표현(Cont.) 이 식을 Newton의 제차분 보간 다항식이라고 한다.
데이터 점들이 등 간격일 필요가 없으며, 차분상 값을 계수 값으로 사용하므로 계산이 편리하다.

24 4.1 Newton 전향 보간식 전향 차분 : 교재 p.196(식 5.15 & 5.16) 참조 Newton 전향 보간 공식
n+1 개 점이 주어지고, x가 n개 등 구간으로 주어진 경우, xi+1 – xi = h라고 가정.

25 4.1 Newton 전향 보간식(cont.) Newton의 n차 전향 보간 공식

26 4.1 Newton 전향 보간식(cont.) 좌표가 n개의 등구간으로 주어지면, 기점 x0를 정할 수 있다.
k = (x – x1) / h + 1의 정수부를 취하여, x0 = x1 + (k – 1)h ,if n  k + m x0 = x1 + (n – m – 1)h ,if n < k + m

27 4.2 Newton 후향 보간식 Newton의 후향 차분 :  f(xi) = f(xi) – f(xi-1)
xi (0 i  n)가 등 간격의 좌표 점이라 하면, 기점을 좌표의 끝점 xn으로 취하고, Newton의 보간 다항식을 정의하면 다음과 같다.

28 4.2 Newton 후향 보간식(cont.) x = xn 일 때, yn = pn(xn)이므로 xn부터 x0 까지 역으로 대입하면, 다음과 같이 된다.

29 4.2 Newton 후향 보간식(cont.) 위의 식을 ai에, 대하여 풀면 다음과 같다. 일반적으로,

30 4.2 Newton 후향 보간식(cont.) 계수 대입하여 식을 다시 정의. 인 경우, Newton의 후향 보간식 :

31 4.2 Newton 후향 보간식(cont.) x1부터 xn까지 구간의 크기가 일정한 점으로 주어졌을 때, 오차를 줄이기 위한 기점 xi를 구할 수 있다. k = (x – x1)/h + 1의 정수부를 취하여, xi = x1 + kh ,if k > m (m차의 후향 보간식일 경우) xi = x1 + nh ,if k  m

32 5. 반복 선형 보간법 두 점에서 출발하여 한 점씩 증가시켜 가면서, 선형 보간법을 적용하는 방법.
바로 전단계에서 계산된 보간 값과 매우 비슷할 경우에 계산을 중지. 선형 보간법을 적용할 2개의 좌표 점을 취하는 방법에 따라서 Aitken 보간법 Neville 보간법

33 5.1 Aitken 보간법 어느 한 점을 고정시키고, 나머지 점들과의 선형 보간식을 만들어 보간 값을 계산하는 방법이다.
(x0, y0)와 (x1, y1)을 지나는 1차 보간식 (x0, y0)와 (x2, y2)을 지나는 1차 보간식 (x0, y0)와 (xi, yi)을 지나는 1차 보간식

34 5.1 Aitken 보간법(cont.) 보간값 p1,1(x)를 y1으로, p2.1(x)를 y2으로 pi.1(x)를 yi으로 대신하여 좌표 점을 만들면, 이들 좌표 점에 대하여 다시 선형 보간식을 적용 (x0, y0)와 (x1, y1), (x2, y2)을 지나는 2차 보간식

35 5.1 Aitken 보간법(cont.) 반복해 나가는 과정을 일반식으로 표현하면,
단, j = 1, 2, …, n에 대하여 i = j, j+1, …, n

36 5.1 Aitken 보간법(cont.) Aitken보간법의 계산 순서
각 차수 j에 대하여 좌표 점을 n까지 모두 계산하지 않고, 계속 한 점씩 추가하면서 진행한다. 1 2 4 3 5 6

37 5.2 Neville 보간법 다음 단계의 선형 보간식을 현 단계와 인접한 두 점의 값에서 구해 나가는 방법이다.
단, j = 1, 2, …, n에 대하여 i = j, j+1, …, n

38 5.2 Neville 보간법(cont.) Neville 보간법의 계산 순서 1 2 4 3 5 6

39 6. 보간 다항식의 오차 Taylor급수의 절단오차 공식으로부터, n차 보간 다항식의 오차 관계식을 정의.
여기에서, 는 xi와 xi+1 사이에 있다.

40 6. 보간 다항식의 오차(cont.) n+1차 도함수를 근사하기 위하여, 유한 차분을 사용하여 정의할 수 있다.

41 6.1 Rolle의 정리를 이용한 오차

42 6.1 Rolle의 정리를 이용한 오차(cont.)

43 6.1 Rolle의 정리를 이용한 오차(cont.)

44 6.1 Rolle의 정리를 이용한 오차(cont.)

45 6.1 Rolle의 정리를 이용한 오차(cont.)

46 7. Spline 함수 보간법 자료 점들의 부분집합에 저차 다항식을 적용시켜나가는, 연결 다항식을 스플라인 함수라고 한다.
함수는 일반적으로 완만하게 변하지만, 특정 구역에서는 급격히 변하는 경우도 있다. 스플라인 함수는 국부적으로 급격히 변화하는 함수의 거동에 우수한 근사값을 제공한다.

47 7. Spline 함수 보간법 x1 x2 x3 x4 x5 x6 x7 x8

48 7. Spline 함수 보간법(cont.) 주어진 구간 [a, b]가 a = x1 < x2 < …< xn = b와 같이 (n-1)개의 소 구간으로 이루어졌을 때 차수가 k인 spline 함수 s(x)는 다음 조건을 만족해야 한다. 조건 1 : s(x)는 i = 1, 2,…, n에 대한 소 구간 [xi, xi+1] 에서 k차 이하의 다항식으로 표현된다. 조건 2 : s(x), s'(x), s'' (x), …, sk-1(x) 등의 도함수들은 구간 [a, b]에서 연속이어야 한다.

49 7. Spline 함수 보간법(cont.) 두 조건을 만족하는 최소의 차수는 3차로서, 모든 소 구간[xi, xi+1]에서 3차 다항식으로 표시되는 함수를 3차 spline함수라고 한다. 점(xi, yi)(xi+1, yi+1)로 주어지는 i번째 소 구간에 대한 3차식의 일반형은 다음과 같다.

50 7. Spline 함수 보간법(cont.) 소 구간의 양 끝점 (xi, yi)와 (xi+1, yi+1)를 지나야 하므로,
hi = xi+1 – xi 로 놓으면, …..(식1)

51 7. Spline 함수 보간법(cont.) Spline 함수 조건을 만족해야 하므로 미분하면,
si 를 점(xi, yi)에서, si+1 를 점 (xi+1, yi+1)에서 2차 도함수라고 하면,

52 7. Spline 함수 보간법(cont.) 3차식의 계수를 구하면 다음과 같다.
yi’=s’(xi)=ci이므로, 다음과 같이 유도할 수 있다. ai와 bi를(식1)에 대입하여 ci를 구함 xi-1에서 xi로의 기울기는 yi’ = s’(xi-1)

53 7. Spline 함수 보간법(cont.) 이 식을 간단하게 정리하면,

54 7. Spline 함수 보간법(cont.) 위 식에 전 구간 내의 모든 좌표점(i=2,…,n-1)을 대입하면,

55 7. Spline 함수 보간법(cont.) 좌표점을 대입하여 만든 식을 행렬로 표현.

56 7. Spline 함수 보간법(cont.) 이렇게 n – 2개의 si에 관한 연립 방정식이 생기고, 양 끝점을 제외한 (n – 2)개의 si 값을 얻는다. 양 끝점을 택하는 세가지 경우: s1 = sn = 0 : 끝점에서의 함수형이 1차 함수 s1 = s2 , sn = sn-1 : 끝점에서의 함수형이 2차 함수 s1은 s2와 s3 , sn은 sn-1 과 sn-2의 선형 외삽법을 사용.

57 7. Spline 함수 보간법(cont.) 조건 1(자연 spline) : s1 = sn = 0
조건 2 : s1 = s2 , sn = sn-1

58 7. Spline 함수 보간법(cont.) 각 소구간에 대하여 si 의 값이 구해지면, 3차 spline 함수의 계수들을 구할 수 있다. i번째 소구간의 계수들의 식

59 Summary : 3차 Spline 보간법 i번째 소구간에서 3차 spline 함수의 일반식
구간의 크기 h를 이용하여 s1, s2, … sn의 값을 구한다 s를 이용하여 3차식의 계수를 구한다

60 3차 Spline 예제 5.12 조건의 비교 : 어떤 조건일 때 오차가 감소할까? x = 2.3 일 때
1 2 3 4 y -8 -7 19 56 x = 2.3 일 때 조건 1 : s1 = sn = 0 조건 2 : s1 = s2 , sn = sn-1

61 Spline 함수의 적용 21개 좌표점을 이용하여 이미지의 윤곽선을 근사 Lagrange 보간법

62 8. 외삽법 보간 다항식을 이용해서 구간 [x0, xn] 밖의 영역에서 x의 함수 값을 구하는 방법이다. x1 x2 x3 x
*

63 9. 역 보간법 주어진 f(x)값을 이용하여 해당하는 x값을 결정해야 하는 경우를 역 보간
Newton의 전향 보간 공식을 이용하여, 반복 과정을 거치면서 x값을 구할 수 있음 이 식의 양변을 yo로 나누어 u에 대하여 정리한다.

64 9. 역 보간법 (cont.) 이 식은 u = g(u) 형태의 고정점 반복식이 된다. u의 시점으로 를 선택
식(1)을 반복하여 u1, u2 , u3, …, un 을 계산해서 그 결과가 수렴할 때, 반복을 중지 값이 변화가 없으면 반복을 중지하고 다음 식을 x에 대하여 정리

65 9. 역 보간법 (cont.) 예제 5.14 : y = 6.25일 때 x = ? 1회 반복 후 : 2회 반복 후 :
좌표 점의 개수가 4개이므로 3차식을 이용 x y y y2 y3 2 4 5 3 9 7 16 25 1회 반복 후 : 2회 반복 후 :