Newton Divided Difference Interpolation Polynomial

In summary, divided differences are finite approximations to derivatives and are used in the Newton's polynomial formula. They are defined as the rate of change between two points and can be used to approximate higher derivatives. An interesting fact about divided differences is that the n-th divided difference of an n-th degree polynomial is a constant and is an "invariant" of the polynomial. This means that it is equal for any set of points chosen within the polynomial.
  • #1
JaredPM
20
0
f(x)= a(0) + a1(x-x(0)) + a2(x-x(1))(x-x(0))

I am having a hard time understanding the intuition of (x-x(1))(x-x(0)) being multiplied by the coefficient a(2). For example, if I added a(3) to the equation, I would have had to multiply a(3) by (x-x(0))(x-x(1))(x-x(2)). I've researched the Mean Value Theorem and can't make the connection. I don't understand how the multiplications keep increasing. I understand that it needs 4 points to be able to compute the 3rd divided difference. I can't seem to grasp how it works. I am a visual learner, but can slowly reason through arithmetic. Thanks for you help!
 
Mathematics news on Phys.org
  • #2
The best explanation, I've found on the web is https://mat.iitm.ac.in/home/sryedida/public_html/caimna/interpolation/nddf.html . However, the typography on that page is horribly mangled when I view it.

There are two concepts involve in this topic. The first concept is "divided difference". The second concept is how Newtons polynomial formula is a consequence of the properties of a "divided difference". (The formula for Newtons polynomial is not the formula that defines a "divided difference". )

Let's devote this post just to the topic of "divided differences".

You can think of "divided differences" as finite approximations to derivatives.

The "first divided difference of ##f## evaluated at ##x_0,x_1## is denoted by ##f[x_0,x_1]## It is defined as ##f[x_0,x_1] = \frac{ f(x_1) - f(x_0)} {x_1 - x_0} ##.

To make the analogy with a derivative clear, think of "##x_1##" as "##x_0 + h##" and "##x_1 - x_0##" as "##h##". Then ##f[x_0,x_1] = \frac{ f(x_0+h) - f(x_0)}{h} ##. If we took ##lim_{h\rightarrow 0} ## of that algebraic expression, we would have ##f'(x_0)##.

The second divided difference ##f[x_0, x_1, x_2]## can be regarded as an approximation for the second derivative ##f''(x_0)## computed as the approximate rate of change between two approximations for the first derivative.

##f[x_0, x_1, x_2] = \big{(} \frac{ f(x_2)- f(x_1) } {x2- x_1} - \frac{f(x_1) - f(x_0)}{x_1 - x_0} \big{)} / (x_2 - x_0) ##

It's more concise to denote that expression as ##f[x_0, x_1,x_2] = \frac{ f[x_2,x_1] - f[x_1,x_0] } {x_2 - x_0}##The third divided difference can regarded as an approximation for a third derivative. If we wrote out the algebra it would be the average rate of change between two approximations for second derivatives and the approximations for each of the second derivatives would involve two approximations for first derivatives. So it's more humane to define the third divided difference using the notation ##f[x_0,x_1,x_2,x_3] = \frac{ f[x_1,x_2,x_3] - f[x_0,x_1,x_2]}{x3 - x_0}##.

As you recall, the first derivative of a first degree polynomial is a constant, the second derivative of a second degree polynomial is a constant, and, in general, the n-th derivative of a n-degree polynomial is a constant.

It's an amazing fact that an analogous statement holds true for divided differences of polynomial functions, even though the divided differences do not involve taking any limits. The n-th divided difference of an n-th degree polynomial ##f(x)## is a constant. This is true even if we choose the points ##x_0,x_1,x_2,...,x_n## to be widely separated.

Another way of asserting the same claim is to say that the n-th divided difference of an n-th degree polynomial is an "invariant" of the polynomial. If we have two sets of points ##\{a_1,a_2,...a_n\}## and ##\{b_1,b_2,...b_n\}## then ##f[a_0,a_1,a_2,...,a_n] = f[b_0,b_1,b_2,...,b_n]## for an nth-degree polynomial ##f(x)## because both sides of the equation are equal to the same constant.
 

FAQ: Newton Divided Difference Interpolation Polynomial

What is the Newton Divided Difference Interpolation Polynomial?

The Newton Divided Difference Interpolation Polynomial is a method of approximating a function using a polynomial. It is named after Sir Isaac Newton, who developed the method as a way to efficiently calculate polynomial interpolations.

How does the Newton Divided Difference Interpolation Polynomial work?

The method involves constructing a polynomial that passes through a set of given data points. This is done by using divided differences, which are the ratios of the differences between the data points. The resulting polynomial can then be used to estimate values at points in between the given data points.

What are the advantages of using the Newton Divided Difference Interpolation Polynomial?

One advantage is that it can accurately approximate a function even if the data points are not evenly spaced. It also allows for the addition of new data points without having to recompute the entire polynomial. Additionally, it is a relatively simple and efficient method.

What are the limitations of the Newton Divided Difference Interpolation Polynomial?

One limitation is that it can produce large oscillations between data points if the degree of the polynomial is too high. It also requires knowledge of the data points beforehand, so it cannot be used for predicting values outside of the given data range.

How is the accuracy of the Newton Divided Difference Interpolation Polynomial measured?

The accuracy of the method can be measured by comparing the estimated values with the actual values at the given data points. It is also important to consider the degree of the polynomial used, as higher degrees can lead to overfitting and reduced accuracy.

Similar threads

Replies
3
Views
1K
Replies
2
Views
1K
Replies
3
Views
1K
Replies
2
Views
1K
Replies
4
Views
522
Replies
2
Views
1K
Replies
5
Views
1K
Back
Top