뉴턴 계차상 공식 유도
공식
서로 다른 $x_{0} , \cdots , x_{n}$ 의 데이터 $(x_{0}, f(x_{0} )) , \cdots , (x_{n} , f( x_{n} ) )$ 에 대해 $$ p_{n} (x) =\sum_{i=0}^{n} f [ x_{0} , \cdots , x_{i} ] \prod_{j=0}^{i-1} (x - x_{j} ) $$
설명
복잡해보이지만 $n=0,1,2$ 에 대해서 실제로 전개를 해보면 다음과 같이 단순하게 나타난다. $$ \begin{align*} p_{0} (x) =& f(x_{0}) \\ p_{1} (x) =& f( x_{0} ) + (x - x_{0} ) f [ x_{0} , x_{1} ] \\ p_{2} (x) =& f( x_{0} ) + (x - x_{0} ) f [ x_{0} , x_{1} ] + ( x - x_{0} ) ( x - x_{1} ) f [ x_{0} , x_{1} , x_{2} ] \end{align*} $$ 뉴턴 계차상 공식은 계차상을 이용해 폴리노미얼 인터폴레이션을 나타내는 방법으로, 라그랑주 공식에 비해서 복잡해보이지만 데이터가 추가됨에 따라 업데이트를 해야할 땐 훨씬 편리하다. 뉴턴 계차상 공식을 재귀적으로 나타내면 $$ p_{n} (x) = p_{n-1}(x) + f[x_{0} , \cdots , x_{n} ] \prod_{i=0}^{n-1} (x - x_{i}) $$ 과 같은 형태가 되는데, 라그랑주 공식밖에 없었다면 $p_{n-1}$ 을 이미 알고 있는데 또 $(n+1) \times (n+1)$ 사이즈의 역행렬을 계산해야하는 수고를 해야한다. 어떤 방식으로 계산하든 결과 자체는 라그랑주 공식과 똑같으므로 추가되는 데이터가 적다면 뉴턴 계차상 공식이 유용하게 쓰일 수 있다.
한편 라그랑주 공식과 정확히 같으면서도 다른 모양을 갖고 있다는 점을 이용해 계차상에 대한 여러가지 유용한 정리들을 증명할 수 있다.
유도
전략: $p_{n}$ 과 $p_{n-1}$ 의 차를 $C$ 라고 두면 $p_{n}$ 과 $C$ 의 최고차항의 계수는 같아야하므로 $C$ 의 계수만 계산해서 간접적으로 재귀식을 유도한다.
$$ 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}) $$ 와 같이 나타난다. $p_{n}$ 과 $C$ 의 최고차항은 같으므로, $a_{n} = f [ x_{0} , \cdots , x_{n}]$ 이 성립함을 보이면 된다.데이터 $\left\{ x_{0}, \cdots , x_{k} \right\}$ 에서 $x_{k}$ 가 빠진 데이터 $\left\{ x_{0}, \cdots , x_{k-1} \right\}$ 로 얻은 폴리노미얼 인터폴레이션을 $L_{k-1}(x)$, $x_{0}$ 가 빠진 데이터 $\left\{ x_{1}, \cdots , x_{k} \right\}$ 로 얻은 폴리노미얼 인터폴레이션을 $R_{k-1}(x)$ 이라고 하자. 각각의 알파벳은 왼쪽Left과 오른쪽Right을 의미한다. 이에 대해 $p_{k}$ 를 다음과 같이 두자. $$ p_{k}(x) := {{ (x-x_{0}) R_{k-1} (x) - (x-x_{k}) L_{k-1} (x) } \over { x_{k} - x_{0} }} $$ 그러면 $i=1,\cdots , k-1$ 에 대해 $$ p_{k}(x_{0}) = L_{k-1} (x_{0}) = f(x_{0}) $$
$$ p_{k}(x_{i}) = L_{k-1} (x_{i}) = R_{k-1} (x_{i}) = f(x_{i}) $$
$$ p_{k}(x_{k}) = R_{k-1} (x_{k}) = f(x_{k}) $$ 따라서 $p_{k}$ 는 주어진 데이터를 잘 인터폴레이트함이 보장된다. $p_{k}$ 의 최고차항의 계수를 $a_{k}$ 라고 할 때, $a_k = f[ x_{0} , \cdots , x_{k} ]$ 이 성립함을 수학적 귀납법으로 보일 것이다.
$k=1$ 일 때 $$ p_{1}(x) = {{ (x-x_{0}) f(x_{1}) - (x-x_{k}) f(x_{0}) (x) } \over { x_{1} - x_{0} }} $$ 이므로 최고차항 $x$ 의 계수는 $$ a_{1} = {{ f(x_{1} - x_{0}) } \over { x_{1} - x_{0} }} = f[x_{0},x_{1}] $$ $k > 1$ 일 때 $a_{k-1} = f[ x_{0} , \cdots , x_{k-1} ]$ 이 성립한다고 가정하면 $L_{k-1}$ 의 최고차항의 계수는 $f[ x_{0} , \cdots , x_{k-1} ]$ 이고, $R_{k-1}$ 최고차항의 계수는 $f[ x_{1} , \cdots , x_{k} ]$ 이다. $p_{k}$ 의 분수꼴을 헤쳐보면 $$ p_{k}(x) = {{ R_{k-1} (x) - L_{k-1} (x) } \over { x_{k} - x_{0} }} x + {{ x_{k} L_{k-1} (x) - x_{0} R_{k-1} (x) } \over { x_{k} - x_{0} }} $$ 따라서 $p_{k}(x)$ 의 최고차항의 계수는 $$ a_{k} = {{ f[ x_{1} , \cdots , x_{k} ]- f[ x_{0} , \cdots , x_{k-1} ] } \over { x_{k} - x_{0} }} = f[ x_{0} , \cdots , x_{k} ] $$ 수학적 귀납법에 모든 자연수 $n$ 에 대해 $$ a_{n} = f [ x_{0} , \cdots , x_{n}] $$
■