수치해석학에서의 계차상
정의
함수 $f : \mathbb{R} \to \mathbb{R}$ 와 서로 다른 $x_{1} , \cdots , x_{n}$ 에 대해 다음을 $f$ 의 계차상divided Difference이라고 한다.
$$ \begin{align*} f[x_{0}] :=& f( x_{0} ) \\ f [ x_{0} , x_{1} ] :=& {{ f ( x_{1} ) - f ( x_{0} ) } \over { x_{1} - x_{0} }} \\ f [ x_{0} , x_{1} , x_{2} ] :=& {{ f [ x_{1} , x_{2} ] - f [ x_{0} , x_{1} ] } \over { x_{2} - x_{0} }} \\ f [ x_{0} , \cdots , x_{n} ] :=& {{ f [ x_{1} , \cdots , x_{n} ] - f [ x_{0} , \cdots , x_{n-1} ] } \over { x_{n} - x_{0} }} \end{align*} $$
정리
- [1]: $f [ x_{0} , \cdots , x_{n} ]$ 는 $x_{0} , \cdots , x_{n}$ 의 순서와 상관 없이 항상 같다.
- [2]: $$f [ x_{0} , \cdots , x_{n} ] = \sum_{i=0}^{n} {{ f( x_{i} ) } \over { \prod_{j \in \left\{ 0 , \cdots , n \right\} \setminus \left\{ i \right\} } ( x_{i} - x_{j} ) }}$$
- [3]: 다음을 만족하는 $\xi$ 가 $\mathscr{H} \left\{ x_{0} , x_{1} \right\}$ 에 존재한다.$$f’ ( \xi ) = f [ x_0 , x_{1} ]$$
- [4]: 다음을 만족하는 $\xi$ 가 $\mathscr{H} \left\{ x_{0} , \cdots , x_{n} \right\}$ 에 존재한다.$${{1} \over {n!}} f^{(n)} ( \xi ) =f [ x_{0} , \cdots , x_{n} ]$$
- [3]’: $$f [ x_{i} , x_{i} ] = f ' ( x_{i} )$$
- [4]’: $$f [ \underbrace{ x_{i} , \cdots , x_{i} }_{ n+1 } ] = {{1} \over {n!}} f^{(n)} ( x_{i} )$$
- $\mathscr{H} \left\{ a,b,c, \cdots \right\}$ 는 $a,b,c, \cdots$ 를 포함하는 가장 작은 구간을 나타낸다.
설명
계차상은 수치해석의 여러가지 이론들을 표현할 때 지면을 아끼는데 큰 도움을 준다.
정리 [2]는 실제 계산에 있어서 특히 유용한데, $$ f [ x_{0} , x_{1} , x_{2} ] = {{ f( x_{0} ) } \over { ( x_{0} - x_{1} ) ( x_{0} - x_{2} ) }} + {{ f( x_{1} ) } \over { ( x_{1} - x_{2} ) ( x_{1} - x_{0} ) }} + {{ f( x_{2} ) } \over { ( x_{2} - x_{0} ) ( x_{2} - x_{1} ) }} $$ 와 같이 나타나기 때문에 실제 정의와 같이 재귀적으로 반복계산을 할 수고를 덜어준다.
[3]은 사실 평균값 정리로써, 미분을 한 때 ‘순간 변화율’과 같은 개념으로 생각한 적이 있다면 왜 계차상이 미분을 대신하고 Divided Difference이라는 이름을 갖는지 이해할 수 있을 것이다. 정리 [4]와 같은 형태로 일반화가 가능하다. 증명은 거꾸로 계차상의 인수들이 한없이 가까워지는, 즉 극한을 취하는 느낌을 생각해보면 [3]’, [4]‘와 같이 $n$계 미분계수로 볼 수 있다. 이러한 개념적 접근은 계차상의 정의에서 오는 한계를 극복하고 수치해석의 이론을 더욱 풍부하게 만들어준다.
예시
간단히 $f(x) := x^2 + 1$ 에 대해 몇몇 계차상을 구해보자.
한 점에 대해서는, $$ f[3] = f(3) = 10 $$
두 점에 대해서는, $$ f[0,5] = {{ f(0) - f(5) } \over { 0 - 5}} = {{1 - 26 } \over { -5 }} = 5 $$
세 점에 대해서는, $$ \begin{align*} f[2,3,-1] =& {{ \displaystyle {{ f(2) - f( 3) } \over { 2 - 3 }} - {{ f(3) - f(-1) } \over { 3 - (-1) }} } \over { 2 - (-1) }} \\ =& {{ \displaystyle {{ 5 - 10 } \over { -1 }} - {{ 10 - 2 } \over { 4 }} } \over { 3}} \\ =& {{ 5 -2 } \over {3}} \\ =& 1 \end{align*} $$ 계차상은 물론 유한한 벡터에 대해서 늘 구할 수 있지만 보통은 위와 같이 $n=2$ 까지만 사용하며, 그 외엔 쓸 일이 거의 없다.
구현
다음은 계차상을 R 코드로 구현한 것으로써, 함수 $f$ 와 벡터 $\mathbb{x} = ( x_{0} , \cdots , x_{n} )$ 을 받아 $f [ x_{0} , \cdots , x_{n} ]$ 을 반환한다.
f<-function(x) {x^2 + 1}
dd<-function(f,X){
if(length(X)==1) {return(f(X))}
temp<-numeric(0)
for(i in 1:length(X)) {temp[i]<-prod(X[i]-X[-i])}
return(sum(f(X)/temp))
}
dd(f,c(3))
dd(f,c(0,5))
dd(f,c(2,3,-1))
위 코드를 실행시킨 결과는 다음과 같으며, $f(x) = x^2 +1$ 에 대한 손계산과 정확히 일치함을 확인할 수 있다.
증명
[2]
전략: 라그랑주 공식과 뉴턴 계차상 공식의 차수를 비교한다.
$$ \Psi_{n} (x) := (x-x_{0}) \cdots (x - x_{n}) $$ $\Psi_{n}$ 을 $x$ 에 대해 미분하고 $x = x_{j}$ 를 대입하면 $$ \Psi’_{n} (x_{j}) := (x-x_{0}) \cdots (x - x_{j-1})(x - x_{j+1}) \cdots (x - x_{n}) $$
$$ \implies {{ \Psi (x)_{n} } \over { (x - x_{j}) \Psi’_{n}(x_{j}) }} \equiv {{ (x - x_{0} ) \cdots (x - x_{j-1} ) (x - x_{j+1} ) \cdots (x - x_{n} ) } \over { (x_{j} - x_{0} ) \cdots (x_{j} - x_{j-1} ) (x_{j} - x_{j+1} ) \cdots (x_{j} - x_{n} ) }} = l_{j} (x) $$ 라그랑주 공식에 따르면 $f$ 의 폴리노미얼 인터폴레이션은 $$ p_{n} (x) = \sum_{j=0}^{n} {{ \Psi_{n} (x) } \over { (x - x_{j}) \Psi’_{n} (x_{j}) }} \cdot f( x_{j}) $$ 따라서 $p_{n}$ 의 최고차항의 계수는 $\displaystyle \sum_{j=0}^{n} {{ f( x_{j}) } \over { \Psi’_{n} (x_{j}) }}$ 인데, 뉴턴 계차상 공식에서 $p_{n}$ 의 최고차항의 계수는 $f [x_{0} , \cdots , x_{n} ]$ 이므로 $$ f [ x_{0} , \cdots , x_{n} ] = \sum_{i=0}^{n} {{ f( x_{i} ) } \over { \displaystyle \prod_{j \in \left\{ 0 , \cdots , n \right\} \setminus \left\{ i \right\} } ( x_{i} - x_{j} ) }} $$
■
[1]
정리 [2]에 의해 $[x_{0} , \cdots , x_{n}]$ 내부의 순서를 바꾸는 것은 $\displaystyle \sum_{i=0}^{n} {{ f( x_{i} ) } \over { \displaystyle \prod_{j \in \left\{ 0 , \cdots , n \right\} \setminus \left\{ i \right\} } ( x_{i} - x_{j} ) }}$ 을 계산할 때 덧셈의 순서를 바꾸는 것에 불과하므로 항상 같다.
■
[4]
전략: 라그랑주 공식과 뉴턴 계차상 공식의 차수를 비교한다.
$p_{n}(x) = p_{n-1}(x) + C(x)$ 이라고 하면 $\deg C = n$ 이고 $i= 0, \cdots, (n-1)$ 에 대해서 $p_{n}(x_{i}) = f(x_{i}) = p_{n-1}(x_{i})$ 이므로 어떤 상수 $a_{n} \ne 0$ 에 대해 $C (x) = a_{n} (x - x_{0}) \cdots (x - x_{n-1})$ 와 같이 나타난다. $C(x)$ 에 $x=x_{n}$ 을 대입해보면 $$ C(x_{n} ) = p_{n} (x_{n}) - p_{n-1}(x_{n}) $$
$$ C (x_{n}) = a_{n} (x_{n} - x_{0}) \cdots (x_{n} - x_{n}) $$ $p_{n}$ 은 $f$ 의 폴리노미얼 인터폴레이션이므로 $p_{n} (x_{n}) = f(x_{n})$ 이고 $$ a_{n} (x_{n} - x_{0}) \cdots (x_{n} - x_{n-1}) = f (x_{n}) - p_{n-1}(x_{n}) $$
$$ a_{n} = {{ f (x_{n}) - p_{n-1}(x_{n-1}) } \over { (x_{n} - x_{0}) \cdots (x_{n} - x_{n-1}) }} $$
폴리노미얼 인터폴레이션과 실제 함수와의 오차: $n$번 미분가능한 $f : \mathbb{R} \to \mathbb{R}$ 와 어떤 $\xi \in \mathscr{H} \left\{ x_{0} , \cdots , x_{n-1} \right\}$ 에 대해 $f$ 의 폴리노미얼 인터폴레이션 $p_{n-1}$ 은 어떤 $x_{n} \in \mathbb{R}$ 에 대해 $$ f(x_{n}) - p_{n-1} (x_{n}) = {{ (x_{n} - x_{0}) \cdots (x_{n} - x_{n-1}) } \over { n! }} f^{(n)} ( \xi ) $$
폴리노미얼 인터폴레이션과 실제 함수와의 오차 공식에 따라 $$ a_{n} = {{ f^{(n)} ( \xi ) } \over { n! }} $$ 다. 한편 뉴턴 계차상 공식에서 $p_{n}$ 의 최고차항의 계수는 $a_{n} = f [x_{0} , \cdots , x_{n} ]$ 이므로 $$ {{1} \over {n!}} f^{(n)} ( \xi ) =f [ x_{0} , \cdots , x_{n} ] $$
■
[3]
정리 [4]에 의해 자명하다.
■