Error analysis of finite differences

4.8.14 · Maths › Numerical Methods

HUM KYA approximate kar rahe hain?

KAISE: truncation error ko scratch se derive karo

Sab kuch Taylor's theorem se aata hai $x$ ke baare mein: $f(x+h)=f(x)+h{f}^{\prime }(x)+\frac{h^2}{2}{f}^{\prime \prime }(x)+\frac{h^3}{6}{f}^{\prime \prime \prime }(x)+\cdots$

Forward difference

Yeh step kyun? $f(x)$ subtract karo aur $h$ se divide karo — exactly wohi jo formula karta hai. $\frac{f(x+h)-f(x)}{h}=f^{\prime }(x)+\frac{h}{2}{f}^{\prime \prime }(x)+\frac{h^2}{6}{f}^{\prime \prime \prime }(x)+\cdots$ To $D_{+}f(x)-f^{\prime }(x)=\frac{h}{2}{f}^{\prime \prime }(x)+O(h^2)=\boxed{O(h)}.$ Yeh kyun matter karta hai: leading error $\propto h$ hai → first order accurate. Exact remainder (Lagrange form) $\frac{h}{2}{f}^{\prime \prime }(\xi )$ hai kisi $\xi \in (x,x+h)$ ke liye.

Central difference

Dono expansions likho: $f(x+h)=f(x)+h{f}^{\prime }+\frac{h^2}{2}{f}^{\prime \prime }+\frac{h^3}{6}{f}^{\prime \prime \prime }+\cdots$ $f(x-h)=f(x)-h{f}^{\prime }+\frac{h^2}{2}{f}^{\prime \prime }-\frac{h^3}{6}{f}^{\prime \prime \prime }+\cdots$ Subtract kyun karo? Even-power terms ($f$, $f^{\prime \prime }$) cancel ho jaate hain, sirf odd wale bachte hain: $f(x+h)-f(x-h)=2h{f}^{\prime }(x)+\frac{h^3}{3}{f}^{\prime \prime \prime }(x)+\cdots$ $2h$ se divide karo: $D_{0}f(x)-f^{\prime }(x)=\frac{h^2}{6}{f}^{\prime \prime \prime }(x)+O(h^4)=\boxed{O(h^2)}.$ Yeh kyun matter karta hai: cancellation $O(h)$ term ko khatam kar deta hai → second order. $h$ ko half karne se truncation error ~4 guna kam ho jaata hai.

KAISE: rounding error kahan se aata hai

Machine $f(x)$ exactly store nahi karta; wo $\tilde{f}(x)=f(x)+\delta$ store karta hai, jahan $|\delta |\le {\epsilon }_m|f(x)|$ aur ${\epsilon }_m\approx 2.2\times 10^{-16}$ (double precision machine epsilon) hai.

Central formula ke liye, computed numerator mein $2\epsilon$ tak error hota hai jahan $\epsilon ={\epsilon }_m|f|$ hai, isliye: ${\epsilon }_{\text{round}}\lesssim \frac{2\epsilon }{2h}=\frac{\epsilon }{h}.$ $1/h$ kyun? Hum ek aisa roundoff divide karte hain jo shrink nahi hota ek tiny $h$ se → yeh blow up ho jaata hai. Yahi catastrophic cancellation hai: $f(x+h)$ aur $f(x-h)$ almost equal hote hain, isliye subtract karne par significant digits kho jaate hain.

Optimal step — minimize karke derive karo

Differentiate kyun? $E(h)$ ka minimum wahan hai jahan $E^{\prime }(h)=0$. $E^{\prime }(h)=\frac{h}{3}{M}_3-\frac{\epsilon }{h^2}=0\Rightarrow h^3=\frac{3\epsilon }{M_3}$ $\boxed{h_{\text{opt}}={\left(\frac{3\epsilon }{M_3}\right)}^{1/3}\sim {\epsilon }^{1/3}\approx 6\times 10^{-6}}$ Us point par $E\sim {\epsilon }^{2/3}\approx 10^{-11}$ — machine precision nahi! Forward difference ke liye $h_{\text{opt}}\sim {\epsilon }^{1/2}\approx 10^{-8}$, $E\sim {\epsilon }^{1/2}$ milta hai.

Worked examples

Common mistakes

Active recall

Connections

• Taylor's Theorem — har truncation term ke peeche yahi engine hai.
• Forward and Backward Difference Operators
• Central Difference Operator
• Floating Point Arithmetic and Machine Epsilon
• Catastrophic Cancellation
• Richardson Extrapolation — leading truncation term cancel karke order boost karta hai.
• Numerical Differentiation
• Order of Accuracy

Concept Map