logo

뉴턴 계차상 공식 유도 📂수치해석

뉴턴 계차상 공식 유도

공식

서로 다른 x0,⋯ ,xnx_{0} , \cdots , x_{n} 의 데이터 (x0,f(x0)),⋯ ,(xn,f(xn))(x_{0}, f(x_{0} )) , \cdots , (x_{n} , f( x_{n} ) ) 에 대해 pn(x)=∑i=0nf[x0,⋯ ,xi]∏j=0i−1(x−xj) p_{n} (x) =\sum_{i=0}^{n} f [ x_{0} , \cdots , x_{i} ] \prod_{j=0}^{i-1} (x - x_{j} )

설명

복잡해보이지만 n=0,1,2n=0,1,2 에 대해서 실제로 전개를 해보면 다음과 같이 단순하게 나타난다. p0(x)=f(x0)p1(x)=f(x0)+(x−x0)f[x0,x1]p2(x)=f(x0)+(x−x0)f[x0,x1]+(x−x0)(x−x1)f[x0,x1,x2] \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*} 뉴턴 계차상 공식은 계차상을 이용해 폴리노미얼 인터폴레이션을 나타내는 방법으로, 라그랑주 공식에 비해서 복잡해보이지만 데이터가 추가됨에 따라 업데이트를 해야할 땐 훨씬 편리하다. 뉴턴 계차상 공식을 재귀적으로 나타내면 pn(x)=pn−1(x)+f[x0,⋯ ,xn]∏i=0n−1(x−xi) p_{n} (x) = p_{n-1}(x) + f[x_{0} , \cdots , x_{n} ] \prod_{i=0}^{n-1} (x - x_{i}) 과 같은 형태가 되는데, 라그랑주 공식밖에 없었다면 pn−1p_{n-1} 을 이미 알고 있는데 또 (n+1)×(n+1)(n+1) \times (n+1) 사이즈의 역행렬을 계산해야하는 수고를 해야한다. 어떤 방식으로 계산하든 결과 자체는 라그랑주 공식과 똑같으므로 추가되는 데이터가 적다면 뉴턴 계차상 공식이 유용하게 쓰일 수 있다.

한편 라그랑주 공식과 정확히 같으면서도 다른 모양을 갖고 있다는 점을 이용해 계차상에 대한 여러가지 유용한 정리들을 증명할 수 있다.

유도

전략: pnp_{n} 과 pn−1p_{n-1} 의 차를 CC 라고 두면 pnp_{n} 과 CC 의 최고차항의 계수는 같아야하므로 CC 의 계수만 계산해서 간접적으로 재귀식을 유도한다.

pn(x)=pn−1(x)+C(x) p_{n}(x) = p_{n-1}(x) + C(x) 이라고 하면 deg⁡C=n\deg C = n 이고 i=0,⋯ ,(n−1)i= 0, \cdots, (n-1) 에 대해서 pn(xi)=f(xi)=pn−1(xi) p_{n}(x_{i}) = f(x_{i}) = p_{n-1}(x_{i}) 이므로 어떤 상수 an≠0a_{n} \ne 0 에 대해 C(x)=an(x−x0)⋯(x−xn−1) C (x) = a_{n} (x - x_{0}) \cdots (x - x_{n-1}) 와 같이 나타난다. pnp_{n} 과 CC 의 최고차항은 같으므로, an=f[x0,⋯ ,xn]a_{n} = f [ x_{0} , \cdots , x_{n}] 이 성립함을 보이면 된다.데이터 {x0,⋯ ,xk}\left\{ x_{0}, \cdots , x_{k} \right\} 에서 xkx_{k} 가 빠진 데이터 {x0,⋯ ,xk−1}\left\{ x_{0}, \cdots , x_{k-1} \right\} 로 얻은 폴리노미얼 인터폴레이션을 Lk−1(x)L_{k-1}(x), x0x_{0} 가 빠진 데이터 {x1,⋯ ,xk}\left\{ x_{1}, \cdots , x_{k} \right\} 로 얻은 폴리노미얼 인터폴레이션을 Rk−1(x)R_{k-1}(x) 이라고 하자. 각각의 알파벳은 왼쪽Left과 오른쪽Right을 의미한다. 이에 대해 pkp_{k} 를 다음과 같이 두자. pk(x):=(x−x0)Rk−1(x)−(x−xk)Lk−1(x)xk−x0 p_{k}(x) := {{ (x-x_{0}) R_{k-1} (x) - (x-x_{k}) L_{k-1} (x) } \over { x_{k} - x_{0} }} 그러면 i=1,⋯ ,k−1i=1,\cdots , k-1 에 대해 pk(x0)=Lk−1(x0)=f(x0) p_{k}(x_{0}) = L_{k-1} (x_{0}) = f(x_{0})

pk(xi)=Lk−1(xi)=Rk−1(xi)=f(xi) p_{k}(x_{i}) = L_{k-1} (x_{i}) = R_{k-1} (x_{i}) = f(x_{i})

pk(xk)=Rk−1(xk)=f(xk) p_{k}(x_{k}) = R_{k-1} (x_{k}) = f(x_{k}) 따라서 pkp_{k} 는 주어진 데이터를 잘 인터폴레이트함이 보장된다. pkp_{k} 의 최고차항의 계수를 aka_{k} 라고 할 때, ak=f[x0,⋯ ,xk]a_k = f[ x_{0} , \cdots , x_{k} ] 이 성립함을 수학적 귀납법으로 보일 것이다.

k=1k=1 일 때 p1(x)=(x−x0)f(x1)−(x−xk)f(x0)(x)x1−x0 p_{1}(x) = {{ (x-x_{0}) f(x_{1}) - (x-x_{k}) f(x_{0}) (x) } \over { x_{1} - x_{0} }} 이므로 최고차항 xx 의 계수는 a1=f(x1−x0)x1−x0=f[x0,x1] a_{1} = {{ f(x_{1} - x_{0}) } \over { x_{1} - x_{0} }} = f[x_{0},x_{1}] k>1k > 1 일 때 ak−1=f[x0,⋯ ,xk−1]a_{k-1} = f[ x_{0} , \cdots , x_{k-1} ] 이 성립한다고 가정하면 Lk−1L_{k-1} 의 최고차항의 계수는 f[x0,⋯ ,xk−1]f[ x_{0} , \cdots , x_{k-1} ] 이고, Rk−1R_{k-1} 최고차항의 계수는 f[x1,⋯ ,xk]f[ x_{1} , \cdots , x_{k} ] 이다. pkp_{k} 의 분수꼴을 헤쳐보면 pk(x)=Rk−1(x)−Lk−1(x)xk−x0x+xkLk−1(x)−x0Rk−1(x)xk−x0 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} }} 따라서 pk(x)p_{k}(x) 의 최고차항의 계수는 ak=f[x1,⋯ ,xk]−f[x0,⋯ ,xk−1]xk−x0=f[x0,⋯ ,xk] 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} ] 수학적 귀납법에 모든 자연수 nn 에 대해 an=f[x0,⋯ ,xn] a_{n} = f [ x_{0} , \cdots , x_{n}]

■