Exercises — Polynomial interpolation — Lagrange form, Newton's divided differences

KYA: Fitting polynomials count karo. KYUN: $n+1=3$ points ke saath hum degree $\le n=2$ ka polynomial dhundhte hain. Aise polynomial mein $3$ free coefficients $a_0,a_1,a_2$ hote hain $a_0+a_{1}x+a_2{x}^2$ mein. $3$ points se guzarne ki condition $3$ linear equations deti hai — ek square system. Nodes $0,2,3$ distinct hain, isliye Vandermonde determinant ${\prod }_{i<j}(x_j-x_i)=(2-0)(3-0)(3-2)=2\cdot 3\cdot 1=6\ne 0$. Nonzero determinant wale square system ka exactly ek solution hota hai. Answer: exactly $1$.

KYA: Woh switch banao jo sirf $x_1=2$ par "on" ho. Numerator kyun: yeh doosre nodes $x_0=0$ aur $x_2=3$ par zero hona chahiye, isliye factors $(x-0)$ aur $(x-3)$ include karo. Denominator kyun: $L_1(2)=1$ force karne ke liye, numerator ki value $x=2$ par se divide karo. $L_1(x)=\frac{(x-0)(x-3)}{(2-0)(2-3)}=\frac{x(x-3)}{2\cdot (-1)}=\frac{x(x-3)}{-2}.$ Values: $L_1(0)=\frac{0}{-2}=0$, $L_1(3)=\frac{0}{-2}=0$, $L_1(2)=\frac{2(-1)}{-2}=1$. Yeh Kronecker delta property $L_1(x_k)={\delta }_{1k}$ hai. ✔

KYA: $P(x)=\sum y_i{L}_i(x)$ assemble karo. Teeno switches banao (nodes $0,2,3$): $L_0=\frac{(x-2)(x-3)}{(0-2)(0-3)}=\frac{(x-2)(x-3)}{6},$ $L_1=\frac{x(x-3)}{(2-0)(2-3)}=\frac{x(x-3)}{-2},$ $L_2=\frac{x(x-2)}{(3-0)(3-2)}=\frac{x(x-2)}{3}.$ Yeh denominators kyun: har ek apne numerator ki value apne node par hai, jo $L_i(x_i)=1$ guarantee karta hai. $y_i=1,5,4$ se weight karo: $P(x)=1\cdot \frac{(x-2)(x-3)}{6}+5\cdot \frac{x(x-3)}{-2}+4\cdot \frac{x(x-2)}{3}.$ Har ek expand karo:

• $\frac{1}{6}(x^2-5x+6)=\frac{1}{6}{x}^2-\frac{5}{6}x+1$
• $-\frac{5}{2}(x^2-3x)=-\frac{5}{2}{x}^2+\frac{15}{2}x$
• $\frac{4}{3}(x^2-2x)=\frac{4}{3}{x}^2-\frac{8}{3}x$

$x^2$ sum karo: $\frac{1}{6}-\frac{5}{2}+\frac{4}{3}=\frac{1-15+8}{6}=-1$. $x$ sum karo: $-\frac{5}{6}+\frac{15}{2}-\frac{8}{3}=\frac{-5+45-16}{6}=\frac{24}{6}=4$. Constant: $1$. $\boxed{P(x)=-x^2+4x+1.}$ Check: $P(0)=1$✔, $P(2)=-4+8+1=5$✔, $P(3)=-9+12+1=4$✔.

KYA: Divided-difference table banao, top diagonal padho. First differences (secant slopes): $f[x_0,x_1]=\frac{5-1}{2-0}=2,f[x_1,x_2]=\frac{4-5}{3-2}=-1.$ Second difference (un slopes ka slope): $f[x_0,x_1,x_2]=\frac{-1-2}{3-0}=\frac{-3}{3}=-1.$ Top-diagonal coefficients: $f[x_0]=1,f[x_0,x_1]=2,f[x_0,x_1,x_2]=-1$. $P(x)=1+2(x-0)-1(x-0)(x-2)=1+2x-(x^2-2x)=-x^2+4x+1.$ Yeh 2.1 se kyun match karta hai: uniqueness theorem ke according sirf ek degree-$\le 2$ interpolant hota hai — Lagrange aur Newton ek hi curve ke liye do alag recipes hain. ✔

KYA: Table ko fourth node $x_3=5,y_3=-11$ se extend karo; sirf naye bottom entries compute karo. Naya first difference: $f[x_2,x_3]=\frac{-11-4}{5-3}=\frac{-15}{2}=-7.5$. Naya second difference: $f[x_1,x_2,x_3]=\frac{-7.5-(-1)}{5-2}=\frac{-6.5}{3}=-\frac{13}{6}$. Naya third difference (cubic column ka top): $f[x_0,x_1,x_2,x_3]=\frac{-\frac{13}{6}-(-1)}{5-0}=\frac{-\frac{13}{6}+1}{5}=\frac{-\frac{7}{6}}{5}=-\frac{7}{30}.$ Purane terms kyun rakhte hain: naya term factor $(x-0)(x-2)(x-3)$ carry karta hai, jo $x_0,x_1,x_2$ par zero hai — isliye yeh teen values jo pehle se fix hain unhe disturb nahi kar sakta. $P_3(x)=\underset{\text{old quadratic}}{\underbrace{-x^2+4x+1}}-\frac{7}{30}x(x-2)(x-3).$ Naya point check karo: $P_3(5)=(-25+20+1)-\frac{7}{30}\cdot 5\cdot 3\cdot 2=-4-\frac{7}{30}\cdot 30=-4-7=-11.$ ✔

KYA: Dono orderings mein slope compute karo. $f[x_0,x_1]=\frac{4-5}{3-2}=-1,f[x_1,x_0]=\frac{5-4}{2-3}=\frac{1}{-1}=-1.$ Equal hain. Kyun hona zaroori hai: do points ke beech secant slope ek geometric quantity hai — unse guzarti line — is baat se independent ki pehle kaunsa point name kiya. Sign dono numerator aur denominator mein flip hota hai aur cancel ho jaata hai. Faayda kya hai: nodes ko freely reorder kar sakte ho taaki arithmetic clean ho, aur highest-order divided difference ($P$ ka leading coefficient) order chahe kuch bhi ho, same rehta hai.

KYA ($P$ banao): values $f(-2)=\frac{1}{5}$, $f(0)=1$, $f(2)=\frac{1}{5}$. Symmetry se $P$ even hai. Newton table with $x_0=-2,x_1=0,x_2=2$: $f[x_0,x_1]=\frac{1-\frac{1}{5}}{0-(-2)}=\frac{\frac{4}{5}}{2}=\frac{2}{5},f[x_1,x_2]=\frac{\frac{1}{5}-1}{2-0}=-\frac{2}{5},$ $f[x_0,x_1,x_2]=\frac{-\frac{2}{5}-\frac{2}{5}}{2-(-2)}=\frac{-\frac{4}{5}}{4}=-\frac{1}{5}.$ $P(x)=\frac{1}{5}+\frac{2}{5}(x+2)-\frac{1}{5}(x+2)(x-0)=\frac{1}{5}+\frac{2}{5}x+\frac{4}{5}-\frac{1}{5}(x^2+2x).$ Combine karo: constant $\frac{1}{5}+\frac{4}{5}=1$; $x$: $\frac{2}{5}-\frac{2}{5}=0$; $x^2$: $-\frac{1}{5}$. Toh $P(x)=1-\frac{1}{5}{x}^2.$ $x=1$ par: $P(1)=1-\frac{1}{5}=\frac{4}{5}=0.8$. True $f(1)=\frac{1}{2}=0.5$. True error $=0.5-0.8=-0.3$.

KYA (error formula): $n=2$ ke saath, $f(x)-P(x)=\frac{f^{\prime \prime \prime }(\xi )}{3!}(x+2)(x-0)(x-2).$ $x=1$ par node product $(3)(1)(-1)=-3$ hai. $f^{\prime \prime \prime }$ ka bound kyun chahiye: hum $\xi$ nahi jaante, isliye $|f^{\prime \prime \prime }|$ ko $[-2,2]$ par bound karte hain. $f=(1+x^2{)}^{-1}$ ke liye, $f^{\prime \prime \prime }(x)=\frac{24x(1-x^2)}{(1+x^2{)}^4}.$ Iska magnitude $[-2,2]$ par $x\approx \pm 0.32$ ke paas peak karta hai lagbhag $|f^{\prime \prime \prime }|\approx 4.62$ par (confirm karne ke liye evaluate karo). Safe bound $M=4.62$ lo. $|f(1)-P(1)|\le \frac{M}{6}\cdot |-3|=\frac{4.62}{6}\cdot 3\approx \mathrm{2.31.}$ Reading: true error $0.3$ guaranteed bound $2.31$ ke andar aaram se fit hoti hai — bound honest hai lekin loose hai (yeh worst-case $f^{\prime \prime \prime }$ use karta hai). Figure dekho.

Error factor ${\prod }_i(x-x_i)$ interval ke ends ke paas huge ho jaata hai jabki $|f^{(n+1)}|$ bhi explode karta hai, isliye $\frac{1}{1+x^2}$ ka high-degree equispaced interpolation end nodes ke beech wildly oscillate karta hai — Runge phenomenon. Fixes: nodes ko ends ki taraf Chebyshev nodes se cluster karo, ya ek high-degree polynomial ko piecewise low-degree Cubic splines se replace karo.

KYA: Secant-slope definition ka limit lo. $f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}.$ Kyun yeh exactly ek derivative hai: right side difference quotient hai — wahi object jiska limit $f^{\prime }(x_0)$ define karta hai. Jab $x_1\to x_0$, ${\lim }_{x_1\to x_0}\frac{f(x_1)-f(x_0)}{x_1-x_0}=f^{\prime }(x_0).$ Interpretation: jab nodes collide hote hain toh interpolant sirf $x_0$ par value hi nahi balki slope bhi match karne par force ho jaata hai (yeh Hermite interpolation hai). Aage badho toh $f[x_0,\dots ,x_k]\to \frac{f^{(k)}(x_0)}{k!}$, aur Newton's form degenerate hokar Taylor series ban jaata hai — dono ideas alag node spacings par dekhi gayi ek hi theory hai.

2.2 se, $f[x_0,x_1,x_2]=-1$, aur indeed $x^2$ ka coefficient $-1$ hai. Yeh match karte hain. Yeh generally kyun: Newton's form mein $P(x)={\sum }_{k=0}^{n}f[x_0,\dots ,x_k]{\prod }_{j=0}^{k-1}(x-x_j),$ sirf last term ($k=n$) mein $x^n$ hai, aur uska product ${\prod }_{j=0}^{n-1}(x-x_j)$ ka leading term coefficient $1$ ke saath $x^n$ hai. Isliye $P$ mein $x^n$ ka coefficient exactly $f[x_0,\dots ,x_n]$ hai. Symmetry (Ex. 3.2) ke saath combine karo, toh top divided difference data ka ek order-independent fingerprint ban jaata hai.

KYA: Table banao. Sabhi $y=3$ hain. $f[x_0,x_1]=\frac{3-3}{4-1}=0,f[x_1,x_2]=\frac{3-3}{6-4}=0,f[x_0,x_1,x_2]=\frac{0-0}{6-1}=0.$ Newton: $P(x)=3+0(x-1)+0(x-1)(x-4)=3$. Answer: constant wala student sahi hai — $P(x)=3$, degree $0$. Theorem mein "$\le n$" phir kaam aata hai: ek horizontal line par teen points constant polynomial dete hain. Vanishing top divided difference ($=$ leading coefficient) ek diagnostic hai ki true degree $n$ se kam hai. ✔

Uniqueness aati hai ::: ek square Vandermonde system se jiska determinant ${\prod }_{i<j}(x_j-x_i)$ distinct nodes ke liye nonzero hota hai. Top divided difference $f[x_0,\dots ,x_n]$ equal hota hai ::: $P(x)$ ke leading coefficient ke (order-independent). Newton's form mein data point add karna cheap hai kyunki ::: naye term mein factor $\prod (x-x_j)$ hota hai jo sabhi old nodes par vanish karta hai, isliye tum bas ise append karte ho. Error formula sirf ::: ek bound ke roop mein usable hai, $f^{(n+1)}(\xi )$ ko uske max magnitude $M$ se replace karke (kyunki $\xi$ unknown hai).