4.8.10
Diye gaye n + 1 ( x 0 , y 0 ) , … , ( x n , y n ) distinct x i ≤ n exactly ek polynomial hota hai.
WHY unique? Degree ≤ n n + 1 n + 1 n + 1 Vandermonde matrix) invertible hota hai jab x i Lagrange aur Newton bas do alag recipes hain isi same polynomial ko likhne ki. Same curve, alag algebra.
Definition Interpolation problemPolynomial P ( x ) deg P ≤ n P ( x i ) = y i i = 0 , … , n x i distinct hain (koi repeated nodes nahi).
WHY distinct nodes matter: agar x i = x j y i = y j ∏ i < j ( x j − x i ) = 0 ,
Main ek aisa polynomial chahta hun jo node x i aur baaki sabhi nodes par 0 ho . Ise L i ( x ) x i P ( x ) = ∑ i = 0 n y i L i ( x ) P ( x k ) = y k x k L k = 1
HOW to build L i ( x ) Mujhe j = i x j numerator = ∏ j = i ( x − x j ) . x i = 1
Worked example Do points (unse guzarne wali line)Points ( 1 , 2 ) , ( 3 , 8 ) L 0 = 1 − 3 x − 3 = − 2 x − 3 L 1 = 3 − 1 x − 1 = 2 x − 1 P ( x ) = 2 ⋅ − 2 x − 3 + 8 ⋅ 2 x − 1 = − ( x − 3 ) + 4 ( x − 1 ) = 3 x − 1 Ye step kyun? Har L dusre node par zero hone ke liye force kiya gaya hai, isliye y i P ( 1 ) = 2 P ( 3 ) = 8
Intuition Doosra form kyun?Lagrange elegant hai lekin rigid hai: ek naya data point add karo aur tumhe har L i P ek term append karna ho — growing data ke liye perfect.
Definition Divided differences (recursive)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 ] = x i + 1 − x i y i + 1 − y i
Worked example Teen points, Newton's tarika( 1 , 2 ) , ( 3 , 8 ) , ( 4 , 5 )
x f [ ⋅ ] 1st
2nd
1
2
3 − 1 8 − 2 = 3
3
8
4 − 1 − 3 − 3 = − 2
4 − 3 5 − 8 = − 3
4
5
Top diagonal coefficients: 2 , 3 , − 2 P ( x ) = 2 + 3 ( x − 1 ) − 2 ( x − 1 ) ( x − 3 ) . Ye step kyun? Main bas har column ka top read karta hun — ye 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
Worked example Same data → same polynomial (Lagrange vs Newton)Newton expand karo: P ( x ) = 2 + 3 x − 3 − 2 ( x 2 − 4 x + 3 ) = − 2 x 2 + 11 x − 7 − 2 x 2 + 11 x − 7 Ye kyun matter karta hai (Forecast-then-Verify): Forecast — unhe agree karna hi padega (uniqueness theorem). Verify — karte hain. Forms sirf bookkeeping mein alag hain.
Common mistake "Lagrange aur Newton alag polynomials dete hain."Kyun sahi lagta hai: formulas bilkul alag dikhte hain. Fix: uniqueness theorem — sirf ek degree-≤ n zaroor same cheez mein expand honge.
Common mistake "Divided differences points ke order par depend karti hain."Kyun sahi lagta hai: recursion ordered indices use karta hai. Fix: f [ x 0 , … , x k ] symmetric hai — points reorder karne se jo terms likhte hain wo alag ho sakti hain lekin final P P
Common mistake "Zyada points = hamesha better fit."Kyun sahi lagta hai: zyada data matlab zyada accuracy lagta hai. Fix: equally spaced nodes par high-degree polynomials wildly oscillate karte hain (Runge). Chebyshev nodes ya low-degree splines use karo.
Common mistake Lagrange numerator kox i − x j Kyun sahi lagta hai: numerator mein pehle se sahi zeros hain. Fix: denominator ke bina L i ( x i ) = 1 P ( x i ) = y i
Recall Feynman: 12 saal ke bache ko explain karoSocho tumhare paas graph paper par kuch dots hain aur tum chahte ho ek smooth bendy line unme se sabse guzre. Polynomial interpolation us line ka rule hai.
Lagrange tarika: har dot ke liye ek special bump-curve banao jo apne dot par exactly 1 ho aur baaki sabhi par 0 ho . Bumps ko stack karo, har ek ko apne dot ki height se scale karke. Line har dot se force hokar guzaregi.
Newton tarika: pehle dot se shuru karo. Correction add karo taki doosra bhi hit ho. Ek aur correction add karo jo pehle do par zero ho taki teesre ko hit kare — aur aise aage. Har correction ek "fix" hai jo pehle ki fixes kabhi nahi todta. Dono tarike same line banate hain — bas do alag recipes hain.
Mnemonic Dono forms yaad karo"L for Local switches, N for New terms."
Lagrange = har basis L ocal hai (ek node par 1, baaki par 0). Newton = har step ek N aya term N udge karta hai jo purane nodes ko respect karta hai.
Vandermonde matrix — interpolation ka unique solution kyun hota hai.Runge phenomenon — high-degree equispaced interpolation kyun fail hoti hai.Chebyshev nodes — node placement jo error product ko tame karta hai.Cubic splines — piecewise low-degree alternative.Numerical differentiation — P ( x ) Newton-Cotes quadrature — interpolant ko integrate karna.Taylor series — divided differences ki limit jab nodes coalesce hote hain (f [ x 0 , … , x k ] → f ( k ) / k !
n + 1 Vandermonde system square hai aur nonzero determinant ∏ i < j ( x j − x i )
Lagrange basis polynomial L i ( x ) L i ( x ) = ∏ j = i x i − x j x − x j x i
L i P ( x ) = ∑ y i L i ( x ) L i ( x k ) = δ ik P ( x k ) = y k
Divided difference ki recursive definition do. 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 ] = y i
Newton's forward interpolation polynomial likho. P ( x ) = ∑ k = 0 n f [ x 0 , … , x k ] ∏ j = 0 k − 1 ( x − x j )
Newton's form mein ek data point cheaply add kyun ho sakta hai lekin Lagrange mein nahi? Newton ke naye term mein ∏ ( x − x j ) L i
Kya Lagrange aur Newton interpolants same polynomial hain? Haan — uniqueness se wo identical hain; sirf algebraic form alag hota hai.
Interpolation error formula batao. f ( x ) − P ( x ) = ( n + 1 )! f ( n + 1 ) ( ξ ) ∏ i = 0 n ( x − x i ) ξ
Interpolation error interval ends ke paas kyun badhti hai? ∏ ( x − x i )
Kya divided difference f [ x 0 , … , x k ] Haan — nodes reorder karne se iska value change nahi hota; ye interpolating polynomial ke leading coefficient ke barabar hota hai.
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
