수치해석 (Numerical Analysis) 보간법 (Interpolation) 문양세 강원대학교 IT 대학 컴퓨터과학전공

Numerical Analysis by Yang-Sae Moon Page 2 보간법 (Interpolation) In this chapter … 보간법이란 ? 통계적 혹은 실험적으로 구해진 데이터들 (x i ) 로부터, 주어진 데이터를 만족하는 근사 함수 (f(x)) 를 구하고, 이 식을 이용하여 주어진 변수에 대한 함수 값을 구하는 일련의 과정을 의 미한다. 예를 들어, (0, 0), (1, 10), (2, 20) 이 주어졌을 때, 이들에 대한 근사 함수 를 f(x) = 10x 로 구하고, 1.5 에 대한 함수 값으로 15 를 구하는 것이다. We will cover … 선형 보간법 라그랑제 다항식 보간법 네빌레의 반복 보간법 뉴튼 다항식에 의한 보간법 3 차원 스플라인 보간법

Numerical Analysis by Yang-Sae Moon Page 3 We are now … 선형 보간법 라그랑제 다항식 보간법 네빌레의 반복 보간법 뉴튼 다항식에 의한 보간법 Linear Interpolation

Numerical Analysis by Yang-Sae Moon Page 4 Linear Interpolation 선형 보간법 개념 (1/2) 선형 보간법은 주어진 두 점을 이은 직선의 방정식을 근사 함수로 사용하 는 단순한 방법이다. 함수 f(x) 가 폐구간 [a,b] 위에서 정의되고, 이 구간에 있는 n 개의 점 x 1, x 2, …, x n 에 대하여 각각의 함수 값을 안다고 하자. 이때, 임의의 두 점 (x i, f(x i )), (x i+1, f(x i+1 )) 을 지나는 직선의 방정식은 다 음과 같다. 상기 식에서, g(x) 는 (x i, x i+1 ) 사이의 임의의 x 값에 대한 선형 보간 값이 되는 것이다.

Numerical Analysis by Yang-Sae Moon Page 5 Linear Interpolation 선형 보간법 개념 (2/2) 선형 보간법의 원리 xixi X i+1 f(xi)f(xi) f(x i+1 ) f(x)f(x) g(x)g(x) f(a)f(a) a g(a)g(a)

Numerical Analysis by Yang-Sae Moon Page 6 선형 보간법 - 알고리즘 procedure linear_inter(x 1, x 2, y 1, y 2 : real numbers, x m : real number) { (x 1,y 1 ) and (x 2,y 2 ) are the initial points. } { x m is the value that we want to get the f(x). } g(x) := return g(x m ); Linear Interpolation

Numerical Analysis by Yang-Sae Moon Page 7 주어진 문제 : 함수 f(x) = e x 에서 f(1) = e, f(2) = e 2 를 안다고 할 때, f(1.0), f(1.1), f(1.2), …, f(1.9), f(2.0) 의 값을 선형 보간법으로 구하라. 선형 보간법 - 프로그램 Linear Interpolation

Numerical Analysis by Yang-Sae Moon Page 8 선형 보간법 – 실행 결과 Linear Interpolation

Numerical Analysis by Yang-Sae Moon Page 9 We are now … 선형 보간법 라그랑제 다항식 보간법 네빌레의 반복 보간법 뉴튼 다항식에 의한 보간법 Lagrange Interpolation

Numerical Analysis by Yang-Sae Moon Page 10 라그랑제 보간법 개념 (1/6) 점들을 단순하게 직선으로 연결하는 것이 아니라, 여러 개의 점들을 지나 는 곡선으로 연결하는 방법을 사용한다. 즉, 여러 개의 점들이 주어졌을 경우, 이들 점들을 지나는 다항식을 구하 고, 이 다항식을 사용하여 주어진 점에 대한 보간 값을 구한다. Lagrange Interpolation xixi X i+1 f(xi)f(xi) f(x i+1 ) f(x)f(x) g(a)g(a) X i+2 g(x)g(x) f(a)f(a) a

Numerical Analysis by Yang-Sae Moon Page 11 라그랑제 보간법 개념 (2/6) (n+1) 개의 점을 지나는 n 차 다항식은 오로지 한 개 존재한다. (n+1) 개의 점들이 다음과 같이 주어진다고 가정하자. 여기에서, x 0, x 1, …, x n 은 (n+1) 개 점들의 x 축 값이며, 그 간격은 일정하지 않아도 된다. Lagrange Interpolation

Numerical Analysis by Yang-Sae Moon Page 12 라그랑제 보간법 개념 (3/6) 구하고자 하는 n 차 다항식은 다음과 같이 표현할 수 있다. 다항식 g(x) 에 (n+1) 개 점들을 대입하여 다음의 (n+1) 개 연립 방정식을 얻 을 수 있다. Lagrange Interpolation

Numerical Analysis by Yang-Sae Moon Page 13 라그랑제 보간법 개념 (4/6) 연립 방정식을 풀기 위해서는 다른 프로그램이 필요하고, 정확성도 보장 할 수 없다. Lagrange Interpolation 상기 연립 방정식을 풀면, 계수 a 0, a 1, …, a n 을 구할 수 있고, 결국 다항식 g(x) 를 구하여 다른 x 값에 대한 보간 값을 구하는데 사용할 수 있다.  라그랑제 보간법 : 연립 방정식을 풀지 않고 다항식을 결정함

Numerical Analysis by Yang-Sae Moon Page 14 라그랑제 보간법 개념 (5/6) 함수 F(x) 는 x = x 0, x 1, x 2, …, x n 일 때 각각 0 이 된다. Lagrange Interpolation 라그랑제의 식은 n 차일 때의 식이 다음과 같다. F(x) 를 각각의 F(x i ) 로 나눈 식을 다음과 같이 G i (x) 라 놓는다. ( 단, 나눌 때 (x  x i ) 은 분모 및 분자에서 제외한다.)

Numerical Analysis by Yang-Sae Moon Page 15 라그랑제 보간법 개념 (6/6) Lagrange Interpolation 각각의 G i (x) 에 y i 를 곱하고, 이를 서로 더하면 그 합은 다음과 같이 n 차 다항식이 된다. 상기 g(x) 는 0 과 n 사이의 모든 i 에 대해서 g(x i ) = y i 를 만족한다. 즉, g(x) 는 모든 (x i, f(x i )) 를 지나는 다항식이 된다.

Numerical Analysis by Yang-Sae Moon Page 16 라그랑제 보간법 - 알고리즘 procedure lagrange(x 0 ~x n, y 0 ~ y n : real numbers, x: real number) { (x i,y i )’s are the given points. } { x is the value that we want to get the f(x). } y := return y; Lagrange Interpolation

Numerical Analysis by Yang-Sae Moon Page 17 주어진 문제 : 다음 표와 같이 네 개의 x 값과 이의 함수 값이 주어졌을 때, x = 1.5, 2.7, 3.4 일 때의 근사 함수 값을 라그랑제 보간법으로 구하시오. 라그랑제 보간법 – 프로그램 (1/3) Lagrange Interpolation 참고 : 상기 표의 함수 값은 f(x) = log 10 (x) 에 해당한다. xf(x)f(x)

Numerical Analysis by Yang-Sae Moon Page 18 라그랑제 보간법 – 프로그램 (2/3) Lagrange Interpolation

Numerical Analysis by Yang-Sae Moon Page 19 라그랑제 보간법 – 프로그램 (3/3) Lagrange Interpolation

Numerical Analysis by Yang-Sae Moon Page 20 라그랑제 보간법 – 실행 결과 (1/2) Lagrange Interpolation 입력 파일 실행 결과 (x = 1.5)

Numerical Analysis by Yang-Sae Moon Page 21 라그랑제 보간법 – 실행 결과 (2/2) Lagrange Interpolation 실행 결과 (x = 2.7) 실행 결과 (x = 3.4)

Numerical Analysis by Yang-Sae Moon Page 22 We are now … 선형 보간법 라그랑제 다항식 보간법 네빌레의 반복 보간법 뉴튼 다항식에 의한 보간법 Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 23 네빌레의 반복 보간법 개념 (1/5) 라그랑제 보간법의 문제점 : 기존 데이터에 덧붙여 새로운 점이 하나만 추가되어도, ( 앞서 구성한 다항식을 사용하지 못하고 ) 다항식을 다시 계산해야 한다.  네빌레의 반복 보간법 : 앞서 구한 계산이나 결과를 다음 단계에서 사용하 는 방법으로서, 새로운 점이 지속적으로 추가될 경우 매우 적합하다. Nevile Interpolation 네빌레의 반복 보간법의 다항식 구성 개념 한 점에 대한 0 차 다항식을 구한다. 앞서 구한 0 차 다항식을 사용하여, 두 점에 대한 1 차 다항식을 구한다. 앞서 구한 1 차 다항식을 사용하여, 세 점에 대한 2 차 다항식을 구한다. … 앞서 구한 (n  1) 차 다항식을 사용하여, (n+1) 개 점에 대한 n 차 다항식을 구한다.

Numerical Analysis by Yang-Sae Moon Page 24 네빌레의 반복 보간법 개념 (2/5) 한 점에 대한 0 차 다항식을 다음과 같이 구한다. ( 단, g i (x) = g(x i ) 이다.) Nevile Interpolation 두 점에 대한 1 차 다항식을 앞서의 0 차 다항식을 사용하여 구한다. 라그랑제 보간법에 따르면, 두 점 x 0, x 1 을 지나는 1 차 다항식은 다음과 같다. 마찬가지로, 두 점 x 1, x 2 을 지나는 1 차 다항식은 다음과 같다.

Numerical Analysis by Yang-Sae Moon Page 25 네빌레의 반복 보간법 개념 (3/5) 다음 표기법을 사용하여, 두 점을 지나는 1 차 다항식을 간략히 나타낸다. Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 26 네빌레의 반복 보간법 개념 (4/5) 같은 방식으로, 세 점에 대한 2 차 다항식을 앞서의 1 차 다항식을 사용하 여 구한다. Nevile Interpolation 마찬가지로, 네 점에 대한 3 차 다항식을 앞서의 2 차 다항식을 사용하여 구한다.

Numerical Analysis by Yang-Sae Moon Page 27 네빌레의 반복 보간법 개념 (5/5) 지금까지 구한 다항식들은 다음과 같이 표로 나타낼 수 있다. Nevile Interpolation 결국, 주어진 개수의 점을 사용하여 다항식을 구하고, 이를 근사 값 계산 에 사용한다. 그 이후에, 새로운 점이 추가되면, 이전 다항식에 이 점을 추가한 다항식 을 다시 구하고, 이를 근사 값 계산에 사용한다. xixi xxixxi f i (x)=g i (x) 근사 함수 x0x0 xx0xx0 g0(x)g0(x) x1x1 xx1xx1 g1(x)g1(x)g 0,1 (x) x2x2 xx2xx2 g2(x)g2(x)g 1,2 (x), g 0,1,2 (x) x3x3 xx3xx3 g3(x)g3(x)g 2,3 (x), g 1,2,3 (x), g 0,1,2,3 (x) …………

Numerical Analysis by Yang-Sae Moon Page 28 네빌레의 반복 보간법 – 알고리즘 (1/2) procedure nevile(x 0 ~x n-1, y 0 ~ y n-1 : real numbers, x: real number) { (x i,y i )’s are the given points. } { x is the value that we want to get the f(x). } for i := 0 to n  1 {increment} begin g cur [0] = y i ; // g xxx [0] = g i, g xxx [1] = g i-1,i, g xxx [2] = g i-2,i-1,I, … k := 1; // g prev [i]: previous row, g cur [i]: current row for j := i to 1 {decrement} begin g cur [i  j+1] := calc_product(g prev [i  j], g cur [i  j], x i, x (i-k), x); k := k+1; end for j := 0 to i g prev [j] = g cur [j]; end return y; Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 29 네빌레의 반복 보간법 – 알고리즘 (2/2) procedure calc_product(g prev, g cur, x e, x s, x: real numbers) y := return y; Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 30 주어진 문제 : 다음 표와 같이 다섯 개의 x 값과 이의 함수 값이 주어졌을 때, x = 2.7 에 대한 근사 함수 값을 네빌레의 반복 보간법으로 구하시오. 네빌레의 반복 보간법 – 프로그램 (1/4) 참고 : 상기 표의 함수 값은 에 해당한다. xf(x)f(x) Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 31 네빌레의 반복 보간법 – 프로그램 (2/4) Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 32 네빌레의 반복 보간법 – 프로그램 (3/4) Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 33 네빌레의 반복 보간법 – 프로그램 (4/4) Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 34 네빌레의 반복 보간법 – 실행 결과 입력 파일 실행 결과 (x = 2.7) Nevile Interpolation

Numerical Analysis by Yang-Sae Moon Page 35 We are now … 선형 보간법 라그랑제 다항식 보간법 네빌레의 반복 보간법 뉴튼 다항식에 의한 보간법 Interpolation on Newton Polynomials

Numerical Analysis by Yang-Sae Moon Page 36 뉴튼 보간법 개요 뉴튼 보간법은 ( 네빌레 보간법과 유사하게 ) 라그랑제 보간법의 1) 하나의 보간을 위해 필요한 계산량이 많고, 2) 데이터의 수가 증가할 때, 바로 직전의 결과를 사용하지 못하며, 3) 에러 계산이 용이하지 않은 문제점을 해결한다. 뉴튼 보간법에서는 기존 데이터를 기초로 차분표 (differential table) 를 구 성하고, 이 차분표를 사용하여 보간 공식을 구한다. 또한, 새로운 데이터가 추가되어도 그 차수를 늘리기 쉬운 장점이 있다. 뉴튼 보간법은 데이터의 종류 및 방법에 따라 다음 세 가지가 있다. 주어진 점의 x 값 간격이 등간격이 아닌 경우 : 분할 차분법 주어진 점의 x 값 간격이 등간격인 경우 : 전향 차분법 혹은 후향 차분법 Interpolation on Newton Polynomials

Numerical Analysis by Yang-Sae Moon Page 37 분할 차분법 개념 (1/4) 서로 다른 (n+1) 개의 점 x 0, x 1, x 2, …, x n 에 대해서, 함수 f(x) 와 함수 값이 같은 n 차 이하의 다항식 P n (x) 가 다음과 같이 주어진다고 하자. ( 다음과 같은 형태를 뉴튼형이라 한다.) Interpolation on Newton Polynomials 그러면, 각 x i 값에 따라서 다음 관계가 만족하고, 이에 따라 상수항 a 0, a 1, … 을 순서대로 구할 수 있다.

Numerical Analysis by Yang-Sae Moon Page 38 분할 차분법 개념 (2/4) 중복된 계산식 ( 예 : (x 2  x 0 )) 을 줄이기 위해, 분할 차분 기호를 사용한다. (  일종의 dynamic programming 기법으로 볼 수 있다.) Interpolation on Newton Polynomials 이를 일반화 시켜서 표현하면 다음과 같다.

Numerical Analysis by Yang-Sae Moon Page 39 분할 차분법 개념 (3/4) 분할 차분 기호를 사용하여 P n (x) 를 다시 표현하면 다음과 같다. Interpolation on Newton Polynomials

Numerical Analysis by Yang-Sae Moon Page 40 분할 차분법 개념 (4/4) 차분 기호를 이용한 방정식 풀이를 위해 차분표를 작성하면 다음과 같다. Interpolation on Newton Polynomials ixixi f[xi]f[xi]f[x i,x i+1 ]f[x i,x i+1,x i+2 ]f[x i,x i+1,x i+2,x i+3 ]… x0x1x2x3x4x0x1x2x3x4 f[x0]f[x1]f[x2]f[x3]f[x4]f[x0]f[x1]f[x2]f[x3]f[x4] f[x0,x1]f[x1,x2]f[x2,x3]f[x3,x4]f[x0,x1]f[x1,x2]f[x2,x3]f[x3,x4] f[x0,x1,x2]f[x1,x2,x3]f[x2,x3,x4]f[x0,x1,x2]f[x1,x2,x3]f[x2,x3,x4] f[x0,x1,x2,x3]f[x1,x2,x3,x4]f[x0,x1,x2,x3]f[x1,x2,x3,x4] …………………

Numerical Analysis by Yang-Sae Moon Page 41 분할 차분법 – 알고리즘 procedure newton-diff(x 0 ~x n-1, y 0 ~ y n-1 : real numbers, x: real number) { (x i,y i )’s are the given points. } { x is the value that we want to get the f(x). } for i := 0 to n  1 f cur [i] := f prev [i] := y i ; for i := 1 to n  1 begin for j := i to n  1 f cur [j] := (f prev [j]  f prev [j  1])/(x j  x j  i ); for j := i to n  1 f prev [j] := f cur [j]; end y := 0;t := 1; for i := 0 to n  1 begin y := y + (f prev [i]  t); t := t  (x  x i ); end return y; Interpolation on Newton Polynomials 교재에서는 2-D Array 를 사용하였으나, 실제로는 1-D Array 들로 해결이 가능하다.

Numerical Analysis by Yang-Sae Moon Page 42 주어진 문제 : 다음 데이터를 참고로 하여, x = 3.8 일 때의 근사 함수 값을 뉴튼의 분할 차분법을 이용하여 구하시오. 분할 차분법 – 프로그램 (1/3) xf(x)f(x) Interpolation on Newton Polynomials

Numerical Analysis by Yang-Sae Moon Page 43 분할 차분법 – 프로그램 (2/3) Interpolation on Newton Polynomials

Numerical Analysis by Yang-Sae Moon Page 44 분할 차분법 – 프로그램 (3/3) Interpolation on Newton Polynomials

Numerical Analysis by Yang-Sae Moon Page 45 분할 차분법 – 실행 결과 입력 파일 실행 결과 (x = 3.8) Interpolation on Newton Polynomials

Numerical Analysis by Yang-Sae Moon Page 46 전향 차분법 및 후향 차분법 개념 전향 차분법과 후향 차분법은 기본적으로 분할 차분법과 동일하나, 주어진 데이터가 등간격인 경우에 사용하는 좀 더 간략화된 방법이다. Interpolation on Newton Polynomials 전향 차분법은 주어진 점 x i (i = 0, 1, 2, …, n) 의 간격이 h 일 때, 함수 값을 구하고자 하는 점 x 를 (x 0 +sh) 로 놓고 다음 관계를 활용하는 방법이다. 후향 차분법은 주어진 점 x i (i = 0, 1, 2, …, n) 의 간격이 h 일 때, 함수 값을 구하고자 하는 점 x 를 (x n +sh) 로 놓고 다음 관계를 활용하는 방법이다. 분할 차분법과 유도 과정이 동일하므로, 알고리즘 및 프로그램은 생략한다.

Numerical Analysis by Yang-Sae Moon Page 47 Homework #4 Interpolation on Newton Polynomials