Exercises — Error in polynomial interpolation

HUM KYA COUNT KARTE HAIN: $4$ nodes matlab $n+1=4$, toh $n=3$. Polynomial ka degree $\le 3$ hai. KAUN SA derivative: formula use karta hai $f^{(n+1)}=f^{(4)}$, jo $(n+1)!=4!=24$ se divide hota hai. $E(x)=\frac{f^{(4)}(\xi )}{24}(x-x_0)(x-x_1)(x-x_2)(x-x_3).$ Answer: $n=3$, aur $f^{(4)}$ aata hai.

Condition: $f\in C^{n+1}[a,b]$ — $f$ ke $n+1$ continuous derivatives hain interval par. Kyun: derivation mein helper function $g$ ko exactly $n+1$ baar differentiate kiya jaata hai (parent proof ka Step 5), toh $f^{(n+1)}$ ko exist karna aur continuous hona chahiye taaki Rolle zeros produce karta rahe.

$\omega (x)=(x-0)(x-1)(x-3)=x(x-1)(x-3).$ $x=2$ par: $\omega (2)=2\cdot (2-1)\cdot (2-3)=2\cdot 1\cdot (-1)=-2.$ Answer: $\omega (x)=x(x-1)(x-3)$, aur $\omega (2)=-2$.

KYA: linear matlab $n=1$, toh hum $f^{\prime \prime }$ aur $\omega (x)=(x-0)(x-0.2)$ use karte hain. $E(x)=\frac{f^{\prime \prime }(\xi )}{2!}x(x-0.2).$ Derivative bound karo: $f^{\prime \prime }(x)=-\cos x$, toh $|f^{\prime \prime }|\le 1$ on $[0,0.2]$ (sabse bada $x=0$ par, $|-\cos 0|=1$). Isliye $M_2=1$. Point par $\omega$ evaluate karo: $\omega (0.1)=0.1\cdot (0.1-0.2)=0.1\cdot (-0.1)=-0.01$, toh $|\omega (0.1)|=0.01$. Combine karo: $|E(0.1)|\le \frac{M_2}{2}|\omega (0.1)|=\frac{1}{2}\cdot 0.01=\mathrm{0.005.}$ Answer: $|E(0.1)|\le 0.005$.

$h$ yahan kya hai: do nodes $0$ aur $0.2$ hain, toh node spacing $h=x_1-x_0=0.2$ hai, aur $\max |f^{\prime \prime }|=1$. $\max |E|\le \frac{h^2}{8}\cdot 1=\frac{0.04}{8}=\mathrm{0.005.}$ YEH KYU MATCH KARTE HAIN: $[0,0.2]$ ka midpoint hi $x=0.1$ hai, aur midpoint exactly wahan hai jahan $|\omega |=h^2/4=0.01$ sabse bada hota hai. Isliye Exercise 2.1 ka pointwise bound midpoint par global worst-case bound ke barabar hai. Answer: $0.005$ — bilkul same, kyunki $0.1$ sabse bura point hai.

$\frac{2h^3}{3\sqrt{3}}$ KAHAN SE AATA HAI (figure dekho): teen equally spaced nodes ke liye node polynomial ek cubic $\omega (x)=(x-x_0)(x-x_0-h)(x-x_0-2h)$ hai. Yeh teen nodes par zero cross karta hai aur do interior humps hain — ek positive, ek negative — equal size ke (red curve). Hump height dhundhne ke liye calculus karte hain: ${\omega }^{\prime }(x)=0$ set karo, do turning points solve karo, aur wapas plug karo. Yeh karne par (parent, Example 3) peak magnitude $\frac{2h^3}{3\sqrt{3}}$ milti hai. Figure mein do symmetric red humps dikhte hain jinki height exactly yahi value hai. KYA: $n=2$, toh hume $f^{\prime \prime \prime }$ chahiye. $f=e^x$ ke liye, $f^{\prime \prime \prime }=e^x$, aur ${\max }_{[0,1]}|f^{\prime \prime \prime }|=e^1=e$. Node-polynomial max: $h=\frac{1}{2}$, toh $\max |\omega |=\frac{2h^3}{3\sqrt{3}}=\frac{2\cdot (1/2{)}^3}{3\sqrt{3}}=\frac{2\cdot \frac{1}{8}}{3\sqrt{3}}=\frac{1/4}{3\sqrt{3}}=\frac{1}{12\sqrt{3}}.$ Combine karo: $\max |E|\le \frac{1}{6}\cdot \frac{1}{12\sqrt{3}}\cdot e=\frac{e}{72\sqrt{3}}\approx \frac{2.71828}{124.708}\approx \mathrm{0.021797.}$ Answer: $\max |E|\lesssim 0.0218$.

YEH OBJECT KYA HAI (figure mein red curve): $[x_0,x_1]$ par, $\omega (x)=(x-x_0)(x-x_1)$ ek downward-opening parabola hai (apni do roots $x_0=1,x_1=3$ ke beech negative hai, jo axis par do black dots hain). Magnitude mein yeh wahan sabse bada hota hai jahan red parabola sabse neeche jaati hai. CALCULUS KYUN: ek smooth curve ka extremum dhundne ke liye, derivative zero set karo. Yahi sawaal hai "extremum kahan hai?" $\omega (x)=x^2-(x_0+x_1)x+x_0{x}_1,{\omega }^{\prime }(x)=2x-(x_0+x_1)=0\Rightarrow x=\frac{x_0+x_1}{2}.$ YEH KAISA DIKHTA HAI: figure mein dashed vertical line $x=\frac{x_0+x_1}{2}=2$ mark karti hai, aur yeh red curve se exactly uske lowest point par milti hai — labeled arrow "$|\omega |=h^2/4$" wahan point karta hai. Evaluate karo: $m=\frac{x_0+x_1}{2}$ rakho. Phir $m-x_0=\frac{h}{2}$ aur $m-x_1=-\frac{h}{2}$, toh $\omega (m)=\left(\frac{h}{2}\right)(-\frac{h}{2})=-\frac{h^2}{4}\Rightarrow |\omega {|}_{\max }=\frac{h^2}{4}.$ In nodes ke saath $h=x_1-x_0=2$, toh sabse gehra dip $-h^2/4=-1$ hai, exactly picture mein red vertex ki depth. Answer: maximum midpoint par, value $h^2/4$. $1/2!$ ke saath combine karke famous $h^2/8$ factor milta hai.

FIGURE KYA DIKHATA HAI: red curve $[-1,1]$ ke axis par marked saat equally spaced black nodes ke liye $|\omega (x)|$ hai. Consecutive nodes ke beech yeh ek "hump" mein uthta hai aur har node par wapas zero par girta hai. $\omega$ KYA MEASURE KARTA HAI: $|\omega (x)|={\prod }_i|x-x_i|$ hai $x$ se har node tak distances ka product. ENDS KYUN BURE HAIN: node cluster ke middle ke paas ek point ke dono taraf nodes hote hain, toh kai $|x-x_i|$ chhote hote hain — product chhota rehta hai, isliye red curve ke central humps bahut chhote hain. Endpoint ke paas ek point ke ek hi taraf saare door node hote hain; almost har factor bada hota hai, toh product blow up karta hai — isliye do outermost red humps central walon se kaafi upar hote hain (arrow "end humps blow up" sabse unche ko point karta hai). Consequence: equally spaced nodes aur high $n$ ke saath, yeh end-humps explosively badhte hain — yahi Runge Phenomenon ka mechanism hai. Chebyshev Nodes ise ends ke paas nodes denser rakh ke fix karte hain, un end-humps ko chhota karke.

KYA: node $x=x_j$ par, $\omega (x)={\prod }_i(x-x_i)$ ke andar factor $(x-x_j)$ ban jaata hai $(x_j-x_j)=0$, toh $\omega (x_j)=0$. ISLIYE $E(x_j)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\cdot 0=0$ chahe $\xi$ kuch bhi ho. KYUN CONSISTENT HAI: $p_n$ ka poora point yahi hai ki $p_n(x_j)=f(x_j)$, toh $E(x_j)=f(x_j)-p_n(x_j)=0$ by construction. Formula yeh reproduce karta hai kyunki $\omega$ ko nodes par vanish karne ke liye banaya gaya tha — unknown $\xi$ kabhi matter nahi karta node par kyunki yeh zero se multiply hota hai.

Pehle plan (WHY helper function). Hum prove karna chahte hain ki kuch chosen point $\bar{x}$ par error ka exact form $(\text{constant})\times \omega (\bar{x})$ hai. Rolle's Theorem hamara ek hi tool hai: yeh kehta hai ek function ke do zeros ke beech uske derivative ka ek zero hota hai. Ise use karne ke liye hume ek aisi function chahiye jo pehle se kai points par zero ho. Na $f-p_1$ (sirf $2$ nodes par zero) na akela $\omega$ (sirf nodes par zero) kaafi hai. Trick: $\bar{x}$ par ek extra zero manufacture karo $\omega$ ka ek multiple ghata ke jo wahan combination vanish kare. Yahi poori wajah hai neeche $g$ ki shape ki — yeh $f-p_1$ hai (jo already nodes par zero hai) minus $K\omega$ (jo nodes par bhi zero hai lekin jiska free constant $K$ hum bend karte hain $g$ ko $\bar{x}$ par bhi kill karne ke liye).

Step 1 — shape assume karo / $K$ define karo. Ek non-node $\bar{x}\in (x_0,x_1)$ fix karo. Constant $K$ choose karo taaki $f(\bar{x})-p_1(\bar{x})=K\omega (\bar{x}),\omega (t)=(t-x_0)(t-x_1).$ Yeh sirf ratio ka naam rakhna hai; abhi kuch commit nahi kiya. Agar hum show kar sakein $K=\frac{f^{\prime \prime }(\xi )}{2}$, toh kaam ho gaya. Step 2 — helper function. $g(t)=f(t)-p_1(t)-K\omega (t).$ (Upar motivate kiye anusar exactly banaya gaya.) Step 3 — zeros count karo. $g(x_0)=g(x_1)=0$ (nodes) aur $g(\bar{x})=0$ (jaise $K$ choose kiya): teen distinct zeros. Step 4 — Rolle. Teen zeros of $g$ $\Rightarrow$ do zeros of $g^{\prime }$ $\Rightarrow$ $g^{\prime \prime }$ ka ek zero; use $\xi$ kaho. Step 5 — do baar differentiate karo. $p_1$ degree $\le 1$ hai $\Rightarrow p_1^{\prime \prime }\equiv 0$; aur $\omega (t)=t^2-(x_0+x_1)t+x_0{x}_1\Rightarrow {\omega }^{\prime \prime }(t)=2$. Isliye $g^{\prime \prime }(t)=f^{\prime \prime }(t)-K\cdot 2.$ Step 6 — $\xi$ par evaluate karo. $0=g^{\prime \prime }(\xi )=f^{\prime \prime }(\xi )-2K\Rightarrow K=\frac{f^{\prime \prime }(\xi )}{2}=\frac{f^{\prime \prime }(\xi )}{2!}.$ Step 7 — substitute karo. $f(\bar{x})-p_1(\bar{x})=\frac{f^{\prime \prime }(\xi )}{2}(\bar{x}-x_0)(\bar{x}-x_1).$ $■$ Parent ke Example 1 se $n+1=2$ ke saath match karta hai.

KYA BADLA: har piece ki node spacing $h=0.5$ hai, aur har piece par hum linear bound $\frac{h^2}{8}\max |f^{\prime \prime }|$ use karte hain. Derivative: $f^{\prime \prime }(x)=-1/x^2$, $|f^{\prime \prime }|\le 1$ on $[1,2]$ (worst $x=1$ par). Is common bound $M_2=1$ use karke: $\max |E|\le \frac{h^2}{8}\cdot M_2=\frac{(0.5{)}^2}{8}\cdot 1=\frac{0.25}{8}=\mathrm{0.03125.}$ Compare karo: $h=1$ se single piece ne $0.125$ diya tha. $h$ ko half karne se bound $4$ se divide hua — hallmark $O(h^2)$ behaviour. Piecewise linear (chhota $h$) ek bade high-degree fit se behtar hai. Answer: $\le 0.03125$, poore interval bound se chaar guna chhota.

KYA: $\omega (x)=x^3-x$. Interior extrema locate karne ke liye, ${\omega }^{\prime }(x)=0$ set karo: ${\omega }^{\prime }(x)=3x^2-1=0\Rightarrow x=\pm \frac{1}{\sqrt{3}}.$ Evaluate karo: $x=\frac{1}{\sqrt{3}}$ par, $\omega \left(\frac{1}{\sqrt{3}}\right)=\frac{1}{3\sqrt{3}}-\frac{1}{\sqrt{3}}=\frac{1-3}{3\sqrt{3}}=-\frac{2}{3\sqrt{3}}.$ Odd symmetry $\omega (-x)=-\omega (x)$ se, doosra extremum $+\frac{2}{3\sqrt{3}}$ deta hai. Endpoints $\omega (\pm 1)=0$ dete hain. Toh $\max |\omega |=\frac{2}{3\sqrt{3}}\approx \mathrm{0.3849.}$ Parent ke general formula $\frac{2h^3}{3\sqrt{3}}$ se consistency check: yahan node spacing $h=1$ hai, jo $\frac{2}{3\sqrt{3}}$ deta hai — match karta hai. ✓ Error bound: $n=2$, toh $\max |E|\le \frac{\max |f^{\prime \prime \prime }|}{3!}\cdot \frac{2}{3\sqrt{3}}=\frac{2}{6\cdot 3\sqrt{3}}\max |f^{\prime \prime \prime }|=\frac{1}{9\sqrt{3}}\max |f^{\prime \prime \prime }|\approx 0.06415\max |f^{\prime \prime \prime }|.$ Answer: max $x=\pm 1/\sqrt{3}$ par, value $2/(3\sqrt{3})\approx 0.3849$; bound $\frac{\max |f^{\prime \prime \prime }|}{9\sqrt{3}}$.

DO FACTORS KYA KARTE HAIN: $|E|\lesssim \underset{\text{derivative knob}}{\underbrace{\frac{\max |f^{(n+1)}|}{(n+1)!}}}\cdot \underset{\text{node knob}}{\underbrace{\max |\omega |}}.$ Derivative knob: $\max |f^{(n+1)}|\approx (n+1)!5^{n+1}$ se, factorial cancel ho jaata hai: $\frac{\max |f^{(n+1)}|}{(n+1)!}\approx 5^{n+1}\stackrel{n\to \infty }{\to }\infty .$ Node knob: $[-1,1]$ par equally spaced nodes ke liye, $\max |\omega |$ sirf ek chhote power/exponential ki tarah decay karta hai jo $5^{n+1}$ ko beat nahi kar sakta. Toh product badhta hai — error endpoints ke paas blow up karta hai. Yahi exactly Runge Phenomenon hai. FACTORIAL KYUN NAHI BACHATA: parent ka mistake callout ne warning diya tha ki denominator mein $(n+1)!$ lagta hai ki hamesha jeetta hai, lekin yahan numerator apna khud ka $(n+1)!$ times $5^{n+1}$ carry karta hai. Cure: node knob switch karo — Chebyshev Nodes use karo (ends par denser), jo $\max |\omega |$ ko $2^{-n}$ scale tak shrink karta hai, ya high degree bilkul chhod do aur piecewise / spline interpolation use karo. Dono product ko bounded rakhte hain. Answer: $(n+1)!$ function ki apni growth ke against cancel ho jaata hai, $\sim 5^{n+1}\to \infty$ bachta hai; cure = Chebyshev nodes ya piecewise interpolation.

• Nodes $=n+1$; error $f^{(n+1)}$ use karta hai $(n+1)!$ se divide hokar times $\omega$.
• Tum sirf $\omega$ control karte ho (node placement); wiggly $f^{(n+1)}$ ko fix nahi kar sakte.
• Linear: worst midpoint par, $\max |\omega |=h^2/4$, bound $\frac{h^2}{8}{M}_2$.
• Quadratic on width-$h$ spacing: $\max |\omega |=\frac{2h^3}{3\sqrt{3}}$.
• $n$ badhane se error worse ho sakta hai (Runge); cure = Chebyshev nodes ya piecewise fits.