Intuition The big pictureGiven n + 1 n+1 n + 1 ( x 0 , y 0 ) , … , ( x n , y n ) (x_0,y_0),\dots,(x_n,y_n) ( x 0 , y 0 ) , … , ( x n , y n ) distinct x i x_i x i exactly one polynomial of degree ≤ n \le n ≤ n
WHY unique? A polynomial of degree ≤ n \le n ≤ n n + 1 n+1 n + 1 n + 1 n+1 n + 1 n + 1 n+1 n + 1 Vandermonde matrix) is invertible when the x i x_i x i Lagrange and Newton are just two different recipes to write down this same polynomial. Same curve, different algebra.
Definition Interpolation problemFind polynomial P ( x ) P(x) P ( x ) deg P ≤ n \deg P \le n deg P ≤ n P ( x i ) = y i P(x_i)=y_i P ( x i ) = y i i = 0 , … , n i=0,\dots,n i = 0 , … , n x i x_i x i distinct (no repeated nodes).
WHY distinct nodes matter: if x i = x j x_i=x_j x i = x j y i ≠ y j y_i\ne y_j y i = y j ∏ i < j ( x j − x i ) ≠ 0 , \prod_{i<j}(x_j-x_i)\ne 0, ∏ i < j ( x j − x i ) = 0 ,
I want a polynomial that is 1 at node x i x_i x i and 0 at every other node . Call it L i ( x ) L_i(x) L i ( x ) x i x_i x i P ( x ) = ∑ i = 0 n y i L i ( x ) P(x)=\sum_{i=0}^n y_i\,L_i(x) P ( x ) = ∑ i = 0 n y i L i ( x ) P ( x k ) = y k P(x_k)=y_k P ( x k ) = y k x k x_k x k L k = 1 L_k=1 L k = 1
HOW to build L i ( x ) L_i(x) L i ( x ) I need zeros at all x j x_j x j j ≠ i j\ne i j = i numerator = ∏ j ≠ i ( x − x j ) . \text{numerator}=\prod_{j\ne i}(x-x_j). numerator = ∏ j = i ( x − x j ) . = 1 =1 = 1 x i x_i x i
Worked example Two points (the line through them)Points ( 1 , 2 ) , ( 3 , 8 ) (1,2),(3,8) ( 1 , 2 ) , ( 3 , 8 ) L 0 = x − 3 1 − 3 = x − 3 − 2 L_0=\dfrac{x-3}{1-3}=\dfrac{x-3}{-2} L 0 = 1 − 3 x − 3 = − 2 x − 3 L 1 = x − 1 3 − 1 = x − 1 2 L_1=\dfrac{x-1}{3-1}=\dfrac{x-1}{2} L 1 = 3 − 1 x − 1 = 2 x − 1 P ( x ) = 2 ⋅ x − 3 − 2 + 8 ⋅ x − 1 2 = − ( x − 3 ) + 4 ( x − 1 ) = 3 x − 1 P(x)=2\cdot\dfrac{x-3}{-2}+8\cdot\dfrac{x-1}{2}=-(x-3)+4(x-1)=3x-1 P ( x ) = 2 ⋅ − 2 x − 3 + 8 ⋅ 2 x − 1 = − ( x − 3 ) + 4 ( x − 1 ) = 3 x − 1 Why this step? Each L L L other node, so weighting by y i y_i y i P ( 1 ) = 2 P(1)=2 P ( 1 ) = 2 P ( 3 ) = 8 P(3)=8 P ( 3 ) = 8
Intuition Why a second form?Lagrange is elegant but rigid : add one new data point and you must recompute every L i L_i L i P P P appends one term — perfect for growing data.
Definition Divided differences (recursive)f [ x i ] = y i , f [ x i , … , x i + k ] = f [ x i + 1 , … , x i + k ] − f [ x i , … , x i + k − 1 ] x i + k − x i f[x_i]=y_i,\qquad f[x_i,\dots,x_{i+k}]=\frac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i} f [ x i ] = y i , f [ x i , … , x i + k ] = x i + k − x i f [ x i + 1 , … , x i + k ] − f [ x i , … , x i + k − 1 ] f [ x i , x i + 1 ] = y i + 1 − y i x i + 1 − x i f[x_i,x_{i+1}]=\dfrac{y_{i+1}-y_i}{x_{i+1}-x_i} f [ x i , x i + 1 ] = x i + 1 − x i y i + 1 − y i
Worked example Three points, Newton's way( 1 , 2 ) , ( 3 , 8 ) , ( 4 , 5 ) (1,2),(3,8),(4,5) ( 1 , 2 ) , ( 3 , 8 ) , ( 4 , 5 )
x x x f [ ⋅ ] f[\cdot] f [ ⋅ ] 1st
2nd
1
2
8 − 2 3 − 1 = 3 \frac{8-2}{3-1}=3 3 − 1 8 − 2 = 3
3
8
− 3 − 3 4 − 1 = − 2 \frac{-3-3}{4-1}=-2 4 − 1 − 3 − 3 = − 2
5 − 8 4 − 3 = − 3 \frac{5-8}{4-3}=-3 4 − 3 5 − 8 = − 3
4
5
Top diagonal coefficients: 2 , 3 , − 2 2,\,3,\,-2 2 , 3 , − 2 P ( x ) = 2 + 3 ( x − 1 ) − 2 ( x − 1 ) ( x − 3 ) . P(x)=2+3(x-1)-2(x-1)(x-3). P ( x ) = 2 + 3 ( x − 1 ) − 2 ( x − 1 ) ( x − 3 ) . Why this step? I just read the top of each column — those are f [ x 0 ] , f [ x 0 , x 1 ] , f [ x 0 , x 1 , x 2 ] f[x_0],f[x_0,x_1],f[x_0,x_1,x_2] f [ x 0 ] , f [ x 0 , x 1 ] , f [ x 0 , x 1 , x 2 ] P ( 4 ) = 2 + 9 − 2 ( 3 ) ( 1 ) = 11 − 6 = 5 P(4)=2+9-2(3)(1)=11-6=5 P ( 4 ) = 2 + 9 − 2 ( 3 ) ( 1 ) = 11 − 6 = 5
Worked example Same data → same polynomial (Lagrange vs Newton)Expand Newton: P ( x ) = 2 + 3 x − 3 − 2 ( x 2 − 4 x + 3 ) = − 2 x 2 + 11 x − 7 P(x)=2+3x-3-2(x^2-4x+3)=-2x^2+11x-7 P ( x ) = 2 + 3 x − 3 − 2 ( x 2 − 4 x + 3 ) = − 2 x 2 + 11 x − 7 − 2 x 2 + 11 x − 7 -2x^2+11x-7 − 2 x 2 + 11 x − 7 Why this matters (Forecast-then-Verify): Forecast — they must agree (uniqueness theorem). Verify — they do. The forms differ only in bookkeeping.
Common mistake "Lagrange and Newton give different polynomials."Why it feels right: the formulas look totally different. The fix: uniqueness theorem — only one degree-≤ n \le n ≤ n must expand to the same thing.
Common mistake "Divided differences depend on the order of points."Why it feels right: the recursion uses ordered indices. The fix: f [ x 0 , … , x k ] f[x_0,\dots,x_k] f [ x 0 , … , x k ] symmetric in its arguments — reordering points changes which terms you write but not the final P P P P P P
Common mistake "More points always = better fit."Why it feels right: more data sounds like more accuracy. The fix: high-degree polynomials on equally spaced nodes oscillate wildly (Runge). Use Chebyshev nodes or low-degree splines instead.
Common mistake Forgetting to divide the Lagrange numerator byx i − x j x_i-x_j x i − x j Why it feels right: the numerator already has the right zeros. The fix: without the denominator L i ( x i ) ≠ 1 L_i(x_i)\ne1 L i ( x i ) = 1 P ( x i ) ≠ y i P(x_i)\ne y_i P ( x i ) = y i
Recall Feynman: explain to a 12-year-oldImagine you have a few dots on graph paper and you want one smooth bendy line through ALL of them. Polynomial interpolation is the rule for that line.
The Lagrange way: for each dot, build a special bump-curve that is exactly 1 on its own dot and 0 on all the others . Stack the bumps, each scaled by its dot's height. The line is forced through every dot.
The Newton way: start with the first dot. Add a correction so it also hits the second. Add another correction that's zero at the first two so it hits the third — and so on. Each correction is a "fix" that never breaks earlier fixes. Both ways draw the same line — they're just two recipes.
Mnemonic Remember the two forms"L for Local switches, N for New terms."
Lagrange = each basis is L ocal (1 at one node, 0 elsewhere). Newton = each step N udges in a N ew term that respects old nodes.
Vandermonde matrix — why interpolation has a unique solution.Runge phenomenon — why high-degree equispaced interpolation fails.Chebyshev nodes — node placement that tames the error product.Cubic splines — piecewise low-degree alternative.Numerical differentiation — derivatives via differentiating P ( x ) P(x) P ( x ) Newton-Cotes quadrature — integrating the interpolant.Taylor series — limit of divided differences as nodes coalesce (f [ x 0 , … , x k ] → f ( k ) / k ! f[x_0,\dots,x_k]\to f^{(k)}/k! f [ x 0 , … , x k ] → f ( k ) / k !
Why does a unique interpolating polynomial of degree ≤ n exist for n+1 distinct nodes? The Vandermonde system is square with nonzero determinant
∏ i < j ( x j − x i ) \prod_{i<j}(x_j-x_i) ∏ i < j ( x j − x i ) when nodes are distinct, so the coefficients are uniquely determined.
Define the Lagrange basis polynomial L i ( x ) L_i(x) L i ( x ) L i ( x ) = ∏ j ≠ i x − x j x i − x j L_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j} L i ( x ) = ∏ j = i x i − x j x − x j ; it equals 1 at
x i x_i x i and 0 at every other node.
What property of L i L_i L i P ( x ) = ∑ y i L i ( x ) P(x)=\sum y_i L_i(x) P ( x ) = ∑ y i L i ( x ) L i ( x k ) = δ i k L_i(x_k)=\delta_{ik} L i ( x k ) = δ ik , so at each node only one term survives, giving
P ( x k ) = y k P(x_k)=y_k P ( x k ) = y k .
Give the recursive definition of a divided difference. f [ x i , … , x i + k ] = f [ x i + 1 , … , x i + k ] − f [ x i , … , x i + k − 1 ] x i + k − x i f[x_i,\dots,x_{i+k}]=\dfrac{f[x_{i+1},\dots,x_{i+k}]-f[x_i,\dots,x_{i+k-1}]}{x_{i+k}-x_i} f [ x i , … , x i + k ] = x i + k − x i f [ x i + 1 , … , x i + k ] − f [ x i , … , x i + k − 1 ] , with
f [ x i ] = y i f[x_i]=y_i f [ x i ] = y i .
Write Newton's forward interpolation polynomial. P ( x ) = ∑ k = 0 n f [ x 0 , … , x k ] ∏ j = 0 k − 1 ( x − x j ) P(x)=\sum_{k=0}^n f[x_0,\dots,x_k]\prod_{j=0}^{k-1}(x-x_j) P ( x ) = ∑ k = 0 n f [ x 0 , … , x k ] ∏ j = 0 k − 1 ( x − x j ) .
Why can you add a data point cheaply in Newton's form but not Lagrange's? The new Newton term has factor
∏ ( x − x j ) \prod(x-x_j) ∏ ( x − x j ) that vanishes at old nodes, so just append one term; Lagrange requires recomputing every basis
L i L_i L i .
Are Lagrange and Newton interpolants the same polynomial? Yes — by uniqueness they are identical; only the algebraic form differs.
State the interpolation error formula. f ( x ) − P ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) f(x)-P(x)=\dfrac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i) f ( x ) − P ( x ) = ( n + 1 )! f ( n + 1 ) ( ξ ) ∏ i = 0 n ( x − x i ) for some
ξ \xi ξ in the interval.
Why does interpolation error grow near interval ends? The factor
∏ ( x − x i ) \prod(x-x_i) ∏ ( x − x i ) becomes large there (Runge phenomenon), inflating the error.
Is the divided difference f [ x 0 , … , x k ] f[x_0,\dots,x_k] f [ x 0 , … , x k ] Yes — reordering nodes does not change its value; it equals the leading coefficient of the interpolating polynomial.
Unique polynomial deg <= n
Vandermonde matrix invertible
Basis L_i = 1 at x_i, 0 elsewhere
Add point rebuilds everything
Divided differences slope of slopes
Add point appends one term
Intuition Hinglish mein samjhoDekho, idea simple hai: tumhare paas kuch points hain (x,y) aur tum chahte ho ek smooth polynomial curve jo exactly har point ke through jaaye. Agar n + 1 n+1 n + 1 ≤ n \le n ≤ n x i x_i x i
Lagrange form ka jugaad yeh hai: har node ke liye ek "switch" banao L i ( x ) L_i(x) L i ( x ) 1 1 1 0 0 0 ( x − x j ) (x-x_j) ( x − x j ) 1 1 1 P ( x ) = ∑ y i L i ( x ) P(x)=\sum y_i L_i(x) P ( x ) = ∑ y i L i ( x )
Newton's divided differences isi kaam ko incremental tareeke se karta hai. Pehle dot se shuru karo, phir ek term add karo jo second dot ko fix kare, phir teesra term jo pehle do nodes pe zero ho taaki purana kaam na bigde. Yeh "slope of slopes" table banake top diagonal padh lo — wahi coefficients hain. Faayda: naya data point aaye to bas ek term append karna padta hai, poora dobara nahi karna.
Dono forms same polynomial dete hain (uniqueness theorem), bas likhne ka tareeka alag hai. Aur ek warning: zyada points se zyada degree lene se curve ends pe wildly oscillate karta hai (Runge phenomenon), kyunki error mein ∏ ( x − x i ) \prod(x-x_i) ∏ ( x − x i )
