Polynomial interpolation — Lagrange form, Newton's divided differences: Visual walkthrough

4.8.10 · D2 · Maths › Numerical Methods › Polynomial interpolation — Lagrange form, Newton's divided d

Neeche jo bhi hai, woh un teeno dots ke baare mein hai. Main unhe ek baar seedhe shabdon mein naam deta hoon, taaki koi bhi symbol bina bataye andar na ghus aaye.

Step 1 — Goal, drawn karo

KYA. Hum ek smooth curve chahte hain — ek polynomial — jo teeno dots ko exactly touch kare.

Ek polynomial sirf $x$ ki powers ko jodkar bani curve hoti hai, jaise $a x^{2} + b x + c$ . Iska degree sabse badi power hoti hai. Teen dots ko degree- $2$ (parabola-shaped) curve pin kar sakti hai, kyunki ek degree- $2$ polynomial mein teen knobs hote hain: $a$ , $b$ , $c$ .

$3$ dots ke liye degree $2$ kyun. Knobs ko demands se count karo:

$3 knobs: a, b, c a x^{2} + b x + c must satisfy pass through 3 dots 3 conditions$

Teen knobs, teen demands → curve ko lock karne ke liye bilkul enough. (Generally: $n + 1$ dots ke liye degree $\leq n$ chahiye.)

PICTURE. Teen dots aur woh (spoiler) curve jo hum banana chahte hain.

Step 2 — Lagrange idea: har dot ke liye ek "switch"

KYA. $a, b, c$ seedha solve karne ki jagah, hum har dot ke liye ek chhoti curve banate hain jo ek switch hai: apne dot par $1$ aur baaki sab dots par $0$ . Dot $i$ ke switch ko symbol $L_{i} (x)$ dete hain.

Switch se kya fayda. Agar mere paas teen switches $L_{0}, L_{1}, L_{2}$ hain, to har ek ko uski dot ki height se scale karke add karne par milta hai

$P (x) = y_{0} L_{0} (x) + y_{1} L_{1} (x) + y_{2} L_{2} (x) .$

$y_{i}$ — dot $i$ ki height (ek fixed number).
$L_{i} (x)$ — dot $i$ ka switch (sirf $x_{i}$ par on).

Node $x_{1}$ par, misal ke taur par, $L_{1} = 1$ aur $L_{0} = L_{2} = 0$ , to poora sum $y_{1}$ par collapse ho jaata hai. Curve us dot se force hoti hai bina koi algebra solve kiye.

PICTURE. Teen switch-curves, har ek apne node par $1$ tak spike karti hai, baaki jagah flat-zero.

Recall Switches ek doosre ko disturb kyun nahi karte

Kyunki har $L_{i}$ apne node ko chhodkar baaki sab nodes par zero hai, unhe add karne se koi pehle se set height disturb nahi hoti. Har term sirf apne dot par "bolta" hai.

Step 3 — Ek switch banana, factor by factor

KYA. Aao $L_{0} (x)$ banate hain — dot 0 ka switch (node $x_{0} = 1$ ).

Zeros se kyun shuru karein. Dot 0 ke liye switch ko doosre nodes $x_{1} = 3$ aur $x_{2} = 4$ par zero hona chahiye. Kisi curve ko kisi jagah zero force karne ka sabse saaf tarika hai ek aisa factor multiply karna jo wahan vanish ho jaaye:

$numerator of L_{0} = (x - 3) (x - 4) .$

$(x - 3)$ — ek factor jo exactly $x = 3$ par $0$ hota hai (node 1).
$(x - 4)$ — ek factor jo exactly $x = 4$ par $0$ hota hai (node 2).

Yeh sahi jagahon par vanish ho jaata hai. Lekin apne node $x_{0} = 1$ par yeh $(1 - 3) (1 - 4) = (- 2) (- 3) = 6$ deta hai, $1$ nahi. To switch ko $1$ par normalise karne ke liye hum us value se divide karte hain:

$L_{0} (x) = \frac{( x - 3 ) ( x - 4 )}{( 1 - 3 ) ( 1 - 4 )} = \frac{( x - 3 ) ( x - 4 )}{6} .$

Upar curve ko doosre nodes par maar deta hai.
Neeche $(x_{0} - x_{1}) (x_{0} - x_{2})$ ek fixed number hai jo height ko $x_{0}$ par $1$ par reset karta hai.

PICTURE. Dekho $L_{0}$ kaise banta hai: raw product (sahi jagah zeros), phir vertical rescale taaki peak height $1$ par baithe.

Step 4 — Switches ko stack karke curve banana

KYA. Ab teeno switches add karo, har ek ko uski dot ki height se weight dekar:

$P (x) = 2 L_{0} (x) + 8 L_{1} (x) + 5 L_{2} (x) .$

Yeh har dot se kyun guzarti hai. Node $x_{2} = 4$ par evaluate karo: sirf $L_{2}$ on hai ( $= 1$ ), baaki dono off hain ( $= 0$ ), to $P (4) = 5 \cdot 1 = 5 = y_{2}$ . Har node par same story.

PICTURE. Scaled switches (heights $2$ , $8$ , $5$ ) aur unka sum — red curve jo teeno dots se guzarti hai.

Is sum ko expand karne par $P (x) = - 2 x^{2} + 11 x - 7$ milta hai (neeche verify karte hain). Yahi ek interpolating polynomial hai.

Step 5 — Newton ka idea: usi curve ko nudges se banana

KYA. Lagrange mein ek dot add karne par sab kuch rebuild karna padta hai. Newton curve ko ek correction ek baar badhata hai, aur har correction design ki gayi hai ki woh pehle se fix cheezein disturb na kare.

Yeh kyun kaam karta hai. Dot 0 se shuru karo. Ek term add karo taaki dot 1 bhi hit ho. Phir ek aisa term add karo jo dots 0 aur 1 par zero ho taaki woh dot 2 ko fix kar sake bina unhe todne ke:

$P (x) = start c_{0} + fix dot 1 c_{1} (x - x_{0}) + fix dot 2 c_{2} (x - x_{0}) (x - x_{1})$

$(x - x_{0})$ — dot 0 par vanish hota hai, to doosri term dot 0 ko chhod deti hai.
$(x - x_{0}) (x - x_{1})$ — dots 0 aur 1 par vanish hota hai, to teesri term dono ko chhod deti hai.

Har naaya factor saare pehle wale dots ko "protect" karta hai.

PICTURE. Teen snapshots: height $2$ par flat start, phir dots 0–1 se guzarti tilted line, phir dot 2 ko pakad'ti bent curve — pehle wale dots kabhi nahi hilte.

Step 6 — Newton coefficients kahan se aate hain (slopes of slopes)

KYA. Numbers $c_{0}, c_{1}, c_{2}$ divided differences hain — literally slopes, phir slopes of slopes.

Slopes kyun. Dot 0 se dot 1 tak jaane ke liye, sahi steepness ordinary secant slope $\frac{y _{1} - y _{0}}{x _{1} - x _{0}}$ hai. Dot 2 ke liye sahi bend ke liye, hume chahiye ki woh slope khud kitna change hoti hai.

f [x_{0}] = 2 f [x_{0}, x_{1}] = \frac{8 - 2}{3 - 1} = 3 f [x_{1}, x_{2}] = \frac{5 - 8}{4 - 3} = - 3 f [x_{0}, x_{1}, x_{2}] = \frac{- 3 - 3}{4 - 1} = - 2

$f [x_{0}] = 2$ — bas starting height ( $c_{0}$ ).
$f [x_{0}, x_{1}] = 3$ — dots 0 aur 1 ke beech secant slope ( $c_{1}$ ).
$f [x_{0}, x_{1}, x_{2}] = - 2$ — "slopes ka slope" ( $c_{2}$ ), yaani steepness kitna bend karti hai.

$P (x) = 2 + 3 (x - 1) - 2 (x - 1) (x - 3) .$

PICTURE. Divided-difference triangle, arrows dikhate hue ki har number apne left ke dono numbers ka difference hai, outer nodes ke span se divide kiya hua. Final coefficient $- 2$ highlight kiya hua.

Recall Dot 2 check karo

$P (4) = 2 + 3 (3) - 2 (3) (1) = 2 + 9 - 6 = 5 = y_{2}$ . ✔

Step 7 — Do recipes, ek curve

KYA. Newton's form expand karo: $P (x) = 2 + 3 (x - 1) - 2 (x^{2} - 4 x + 3) = - 2 x^{2} + 11 x - 7,$ jo Step 4 ke Lagrange result se bilkul same hai.

Yeh match kyun karna chahiye. Teeno dots se guzarne wali sirf ek degree- $\leq 2$ polynomial hoti hai (Step 1 ka knob-count, Vandermonde matrix se proven). Do sahi recipes do alag aisi curves nahi bana sakti — to woh ek hi hoti hain.

PICTURE. Dono constructions ek saath; curves ek doosre ke upar hain, ek red.

Step 8 — Degenerate aur edge cases jo tumhe dekhne chahiye

KYA. Teen scenarios jinse recipe ko survive karna hai:

Collinear dots. Agar teen dots ek line par hain, to $x^{2}$ knob aur doosra divided difference dono $0$ hain, to $P$ ek line ban jaati hai — degree $2$ se neeche gir jaati hai. Kuch nahi tootता.
Repeated node ( $x_{i} = x_{j}$ ). Denominator $(x_{i} - x_{j}) = 0$ aata hai — division by zero. Yeh forbidden hai: distinct nodes zaroori hain. Ek spot par do heights koi function nahi hota.
Interval ke ends. Nodes par perfect fit hone ke baad bhi curve unke beech mein bhatak sakti hai. Error mein factor $\prod_{i} (x - x_{i})$ hota hai, jo outer edges ke paas badhta hai — Runge phenomenon ka beej.

Yeh kyun dikhate hain. Recipe tabhi trustworthy hai jab tum jaano ki woh exactly kab succeed karti hai, collapse karti hai, ya illegal hai.

$f (x) - P (x) = \frac{f ^{(n + 1)} ( ξ )}{( n + 1 )!} \prod_{i = 0}^{n} (x - x_{i})$

$\prod_{i} (x - x_{i})$ — nodes par zero, beech/aage bade.
$f^{(n + 1)} (ξ)$ — true function kitna curvy hai; agar wild hai, error wild hai.

PICTURE. Left: collinear dots se ek line. Middle: illegal repeated node (ek vertical clash). Right: error product $\prod (x - x_{i})$ ends par phool raha hai.

Ek-picture summary

Sab kuch ek canvas par: teen dots, teen Lagrange switches (faint), Newton ka nudging path (dashed), aur ek red interpolant $P (x) = - 2 x^{2} + 11 x - 7$ jis par sab agree karte hain — saath mein edges par error product ka hint.

Recall Feynman retelling — poora walkthrough seedhe shabdon mein

Tumhare paas teen dots hain aur ek bendy line chahiye jo sab se guzre. Kyunki ek parabola mein teen dials hain ( $a, b, c$ ) aur tumhare paas teen demands hain, exactly ek aisi curve hoti hai.

Lagrange ka tarika: har dot ke liye ek chhoti "switch" curve banao jo us dot par on ho (height 1) aur baaki par off (height 0). Switch ko kisi jagah off force karne ke liye ek aisa factor multiply karo jo wahan mar jaaye; use apne dot par on force karne ke liye us value se divide karo jo us waqt uski hai. Phir har switch ko uski dot ki height se scale karo aur add karo. Kyunki har switch baaki dots par silent hai, sum teeno se guzar jaata hai.

Newton ka tarika: pehle dot par flat shuru karo. Doosre ko pakadne ke liye tilt karo — unke beech ka plain slope use karke. Phir teesre ko pakadne ke liye bend karo — "slope of the slopes" use karke — aur us correction ko $(x - x_{0}) (x - x_{1})$ se multiply karo taaki woh pehle dono dots par zero ho aur unhe barbaad na kar sake. Tumhe jo numbers chahiye woh sirf differences divided by gaps hain, ek chhote triangle se padhe.

Dono recipes ek hi red curve banati hain — sirf ek hai — woh sirf alag tarike se bookkeeping karte hain. Aur dhyan raho: nodes alag hone chahiye (warna division by zero hoga), aur fit dots par perfect hone ke baad bhi edges par wobble kar sakti hai.

Connections

Parent topic
Vandermonde matrix — teen knobs uniquely fixed kyun hote hain.
Runge phenomenon — edge-wobble real hota hua.
Chebyshev nodes — node spacing jo error product ko tame karta hai.
Cubic splines — ek badi curve ki jagah bahut saari chhoti curves.
Numerical differentiation — slopes ke liye $P (x)$ differentiate karo.
Newton-Cotes quadrature — areas ke liye $P (x)$ integrate karo.
Taylor series — divided differences → derivatives jab nodes coalesce hote hain.