Newton Interpolation and Divided Differences

In this video, we introduce the Newton Interpolation method and Divided Differences. We start with the general concept, then the recurrence relation and the divided difference table. Finally, we run through a quick example in order to understand how the method is used in practice.
Chapters
0:00 - Introduction
05:40 - The Recurrence Relation
10:56 - The Divide Difference Table
12:48 - Example
Errata and Clarifications:
- at 9:00, the numerator should read (x_k - x_0)qn(x_k) + (x_n+1 - x_k)pn(x_k)
The product links below are Amazon affiliate links. If you buy certain products on Amazon soon after clicking them, I may receive a commission. The price is the same for you, but it does help to support the channel :-)
In-video References:
1. "Applied Numerical Methods with MatLab" by Steven C. Chapra -amzn.to/3quGfE1
2. "Approximation Theory and Methods" by M.J.D. Powell - amzn.to/3JazCy6
FAQ : How do you make these animations?
Animations are made in Apple Keynote which has lots of functionality for animating shapes, lines, curves and text (as well as really good LaTeX). Editing and voiceover work in DaVinci Resolve.
Supporting the Channel.
If you would like to support me in making free mathematics tutorials then you can make a small donation over at
www.buymeacoffee.com/DrWillWood
Thank you so much, I hope you find the content useful.

[@amansartaz5864]

This is my first video of yours and you got my subs ! Nice explaination.

[@user-tz3wt9xc2s]

Thanks for high-level explantion, examples!

[@dvir-ross]

Great video! This is high level but understandable. Love it.

[@DrWillWood]

Thanks a lot!

[@dvir-ross]

@@DrWillWood thank you! Can i ask how do you animate these videos? Is it manim?

[@DrWillWood]

@@dvir-ross Everything on my channel has been done in Keynote (the Apple version of Microsoft powerpoint if you're not a Mac user!). Then I do a bit of editing to make the videos flow a bit better and add background music :-)

[@dvir-ross]

@@DrWillWood wow! That is amazing! I didn't know that one can get such great results with using Powerpoint. Briliant!

[@rishadislam8574]

Thanks for this great video! Would really appreciate if you made new videos on forward, backward and centererd difference based off of divided differnce formula.

[@avyakthaachar2.718]

Amazing explanation and proof, just what I needed, thank you so much

[@duartecastro623]

Great explanation! Thanks for the help

[@AJ-et3vf]

Awesome video! Thank you!

[@dahner6362625]

very easy to understand, thank you

[@perseusz1691]

Great job! You teach very good.

[@mrshodz]

Great video Doc.

[@YousifAbdelKarim-e4i]

very well made video! keep it up

[@avocadolover257]

thank you so much sir, well comprehensive

[@armanboss2257]

sir you are lifesaver for my upcoming semesters

[@ryanrodrigue9653]

what class do you learn this in

[@youssefmagdy5472]

@@ryanrodrigue9653 Numerical Computations

[@yogitajindal3149]

Very helpful Thank you 🙏🏻

[@almuktadirkhan9201]

This is superb. Thank u so much

[@twomoonsinthesky_]

Good explanation, thanks to you I was able to attain a better understanding of the Newton Interpolation and the idea of divided differences. I still don't understand the correlation between divided differences and writing them as integrals, which is what I need for proving the Hermite relation; but I understand this is not part of this video.

[@carlosrodriguezronchel2031]

Brilliant

[@oraviram]

Before I forget: small error at 9:15, in the second line, it's p_n that should be multiplied by x_n+1, and q_n is multiplied by x_0. The signs should stay as they are. This doesn't really matter since q_n and p_n agree at x_k, but it may still be a good idea to add it to the errata. Anyway, the main reason I came here is to say thanks and that this was a great video. My university does a really bad job with numerical analysis. Most courses here are taught with the university's own books, and they are very high quality. First year courses like Calculus 1 and Linear Algebra 1 set very high standards for rigor, both using precise definitions and giving complete proofs of everything. Last semester I took set theory which basically completed the hole in my knowledge by giving an axiomatic foundation of math. Now I am taking numerical analysis and it's like all the rigor is thrown into the trash. We are using Burden's book and it's hard to even call it a math book. Definitions are not consistent, it contradicts itself, the proofs are sloppy and sometimes incorrect, statements of theorems often require extra conditions which are not mentioned, and theorems are applied even when not all the conditions are met. The worst thing, though, is their favorite proof method: do a few examples and notice the pattern, hope it applies forever. Sorry this became a rant about the book, but I just want to make it clear how this video saved me. The way divided differences were introduced in our book was...stupid: we already studied interpolation polynomials (with that they did an alright job), so they went like "let's try to present them in this form". They calculated the first two coefficients, introduced divided differences using the recurrence relation, and said "as you may guess, the nth coefficient is f[x0,...,xn]". No proof no nothing, they just moved on like nothing. It's fine if they did that if the proof was trivial, but like, it's far from it??? Even on Wikipedia I could barely get much help, but then your video introduced it in like the most perfect way it could. Defining the divided differences as the coefficients of the interpolation polynomials in terms of the newton polynomial basis makes more sense than an out-of-the-blue recurrence relation (and it's also easy to make rigorous using linear algebra). After doing that you just gave a simple proof which makes you understand why the recurrence relation makes sense. I just don't get why it was omitted from the course I am taking. It's far from trivial, and it's not that complicated, but our book just decided to brush it under the rug and hope we take its word for it. Alright that's it, sorry for the rant, and thanks for putting out this video.

[@konzo5942]

this guy is the goat

[@mohamadkhanafer2630]

thank you, much better than my teacher's 4hours useless lecture.

[@user-so1rh4zh9h]

谢谢！

[@randhir2126]

thanks

[@pauselab5569]

there are even cooler things about newton polynomials. they are in some sense the discrete counterparts to taylor series and have relations with the calculus of discrete difference where you just have to adjust the divided difference a little.

[@casperspook4415]

Great content! Considering extrapolation rather than interpolation, would this newton polynomial work better, worse or identically to a taylor polynomial of the same order whose coefficients are determined by finite difference schemes?

[@DrWillWood]

Interesting question! I'm not sure, this might depend on the function you're approximating... but there is one interesting point, if you let all the nodes tend to the same value (say x0) then the newton polynomial becomes the Taylor polynomial about x0 of the same order! so in a sense, Newton interpolation kind of "stretches" the Taylor polynomial so it extrapolates better. Probably, at the cost of its ability to follow closely the area close to x0.

[@amansartaz5864]

@@DrWillWood can the polynomial generated in the example represent a sin function or it only follow sin function at the nodes?

[@kalkhasse]

Thanks for awesome videos! Does this method give the same polynomials as Lagrange interpolation? And if so, when would you use one method over the other?

[@DrWillWood]

Yes! for n+1 nodes there is only one polynomial of order n which interpolates them. so all methods give the same polynomial (but probably disguised in a different form). Where Lagrange interpolation has a nice advantage is if you want to approximate multiple functions at the same nodes, since the you can just multiply the same Lagrange polynomials l_i by the new y values. Newton interpolation has a clear advantage if you want the add a new node, since you can just add another column to the divided difference table. All things equal, I think Newton interpolation is easier to do both, by hand (not that you'd do that outside of an exam!) and programmatically: I calculated the example from the video in a spreadsheet!

[@mikewood8175]

Hey, Wonderful Video! Really I was struggling to understand this and now its so simple. Can you make a video on Radial Basis function interpolation or Kernel Interpolation? I am really working on some stuffs and I need it. Also What is the difference between Lagrange's and Newton Interpolation? When to use which? Also why can't we use Taylor series for polynomial approximation? Thank you!

[@Alex-bc3tt]

There are a lot of questions in this comment, I will answer the last one, "why can't we use Taylor series for polynomial approximation?" well we do, we use Taylor series to approximate a polynomial centered at a certain point or more accurately in the neighborhood of a certain point. What this means is if you center a Taylor series at x=a then you approximate the polynomial to the neighborhood of x=a meaning all values of f(x) close to x=a can be approximated using a Taylor series polynomial T(x).... but this has a limitation, for values not in the neighborhood of x=a (that is far away from a) the approximation fails dismally. This implies that the Taylor Series can only approximate close to a certain point but cannot approximate on an interval say [a.b] which is where we need Interpolation methods such as Newton Interpolation divided differences and Lagrange's Polynomial interpolation. Hope this answers your last question.

[@comuniunecuosho-campulbudi7611]

Mike Wood, as you progress on your stuffs keep us up to date with your discoveries and with the answers you have come to know (to your own questions), we also want to learn these things

[@user-py1db9ly6n]

how can we get the equation at 9:16? seems like it has to be Xk (Qn (Xk)+Pn (Xk)) - (X0Qn(Xk)+Xn+1Pn(Xk))

[@DrWillWood]

well spotted! thanks for pointing that out. it seems I accidentally wrote x_k - x_n+1 in the first equation when it should be x_n+1 - x_k. sorry about that!

[@user-py1db9ly6n]

@@DrWillWood yeah, now it makes sense. Thanks a lot. I really enjoy your videos

[@leonardoongari1853]

@@DrWillWood also on the next line, at " x_n+1 qn(x_k) - x_0 pn(x_k) ". Am I wrong or p and q need to be switched ?

[@veselinborisov369]

@@leonardoongari1853 Yes, they should swap.

[@janplechaty1702]

👏👏👏

[@QT-yt4db]

At 6:34, I seemed to have lost of what is the purpose of proof. First, what's the definition of f[x0,x1,...,xn+1]? seems the proof is to prove the definition. But a definiton is just definition and it needs not to be proved, unless there is another definition of f[x0,x1,...,xn+1] in the first place.

[@linco011235]

For a second I thought the music in the background was L’s music from death note. Tbh I could put that behind any math video lol

[@kalinkochnev5669]

At 10:54, I am having a hard time following where x^n+1 comes from

[@azzabadawy4059]

When can i using only Newton's method?

[@theodoremercutio1600]

I found the bit starting from 2:20 somewhat confusing and explained too quickly. Helpful video nonetheless. Thank you.

[@user-pr6ed3ri2k]

😅 3:54 familiargradien

[@kimberlydrake5511]

𝐩𝐫𝐨𝐦𝐨𝐬𝐦 💐