Problem: Derive the following 2 formulas for approximation of derivatives and show they are both O(\(h^{4}\)) by evaluating their error terms
\begin {align*} f\ ^{\prime }\relax (x) & =\frac {1}{12h}\left [ -f\left (x+2h\right ) +8f\left (x+h\right ) -8f\left (x-h\right ) +f\left (x-2h\right ) \right ] \\ f\ ^{\prime \prime }\relax (x) & =\frac {1}{12h^{2}}\left [ -f\left ( x+2h\right ) +16f\left (x+h\right ) -30f\relax (x) +16f\left ( x-h\right ) -f\left (x-2h\right ) \right ] \end {align*}
Solution:
I could obtain the above results directly from applying Richardson interpolation formulas (which is a short approach), but I assumed the question wanted us to derive these from first principles. I first show how to do one using Richardson, then solve both from first principles.
To obtain the approximation for \(f^{\prime }\relax (x) \) using Richardson, we do the following:
\begin {align} \varphi \relax (h) & =\frac {1}{2h}\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] \nonumber \\ L & =\varphi \relax (h) +a_{2}h^{2}+a_{4}h^{4}+\cdots \tag {1C} \end {align}
Replacing \(h\) by \(2h\)
\begin {equation} L=\varphi \left (2h\right ) +a_{2}4h^{2}+a_{4}16h^{4}+\cdots \tag {2C} \end {equation}
Multiplying (1C) by 4 and subtract (2C) from result
\begin {align*} 3L & =\left (4\varphi \relax (h) +4a_{2}h^{2}+4a_{4}h^{4}+\cdots \right ) -\left (\varphi \left (2h\right ) +a_{2}4h^{2}+a_{4}16h^{4}+\cdots \right ) \\ & =4\varphi \relax (h) -\varphi \left (2h\right ) -12a_{4}h^{4}-\cdots \end {align*}
Hence
\begin {align*} L & =\frac {1}{3}\left (\frac {2}{h}\left [ f\left (x+h\right ) -f\left ( x-h\right ) \right ] -\frac {1}{4h}\left [ f\left (x+2h\right ) -f\left ( x-2h\right ) \right ] -12a_{4}h^{4}-\cdots \right ) \\ & =\frac {2}{3h}\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] -\frac {1}{12h}\left [ f\left (x+2h\right ) -f\left (x-2h\right ) \right ] -4a_{4}h^{4}-\cdots \\ & =\frac {1}{12h}\left (8\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] -\left [ f\left (x+2h\right ) -f\left (x-2h\right ) \right ] \right ) -4a_{4}h^{4}-\cdots \\ & =\frac {1}{12h}\left [ -f\left (x+2h\right ) +8f\left (x+h\right ) -8f\left (x-h\right ) +f\left (x-2h\right ) \right ] -4a_{4}h^{4}-\cdots \end {align*}
Which is the same result obtained earlier using the long approach. We also see that the error term is \(O\left (h^{4}\right ) \)
Now, solve it again, but using direct usage of Taylor (which I assume what the book wanted us to do)
From Taylor expansion, we write, by expanding around \(x+h\) and \(x-h\)
\begin {align*} f\left (x+h\right ) & =f\relax (x) +hf\ ^{\prime }\relax (x) +\frac {h^{2}}{2}f^{\prime \prime }\relax (x) +\frac {h^{3}}{3!}f^{\left ( 3\right ) }\relax (x) +\frac {h^{4}}{4!}f^{\relax (4) }\left ( x\right ) +\frac {h^{5}}{5!}f^{\relax (5) }\left (\xi _{1}\right ) \\ f\left (x-h\right ) & =f\relax (x) -hf\ ^{\prime }\relax (x) +\frac {h^{2}}{2}f^{\prime \prime }\relax (x) -\frac {h^{3}}{3!}f^{\left ( 3\right ) }\relax (x) +\frac {h^{4}}{4!}f^{\relax (4) }\left ( x\right ) -\frac {h^{5}}{5!}f^{\relax (5) }\left (\xi _{2}\right ) \end {align*}
Subtract the second from the first equation
\[ f\left (x+h\right ) -f\left (x-h\right ) =2hf\ ^{\prime }\relax (x) +\frac {h^{3}}{3}f^{\relax (3) }\relax (x) +\frac {h^{5}}{60}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\left ( 5\right ) }\left (\xi _{2}\right ) \right ] \]
Solve for \(f^{\prime }\relax (x) \) we obtain
\begin {equation} f\ ^{\prime }\relax (x) =\frac {1}{2h}\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] -\frac {1}{6}h^{2}f^{\relax (3) }\left ( x\right ) -\frac {1}{120}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \tag {1} \end {equation}
Now we do the same again, but by expanding around \(x+2h\) and \(x-2h\)
\begin {align*} f\left (x+2h\right ) & =f\relax (x) +2hf\ ^{\prime }\relax (x) +\frac {\left (2h\right ) ^{2}}{2}f^{\prime \prime }\relax (x) +\frac {\left (2h\right ) ^{3}}{3!}f^{\relax (3) }\relax (x) +\frac {\left (2h\right ) ^{4}}{4!}f^{\relax (4) }\relax (x) +\frac {\left (2h\right ) ^{5}}{5!}f^{\relax (5) }\left (\xi _{1}\right ) \\ f\left (x-2h\right ) & =f\relax (x) -2hf\ ^{\prime }\relax (x) +\frac {\left (2h\right ) ^{2}}{2}f^{\prime \prime }\relax (x) -\frac {\left (2h\right ) ^{3}}{3!}f^{\relax (3) }\relax (x) +\frac {\left (2h\right ) ^{4}}{4!}f^{\relax (4) }\relax (x) -\frac {\left (2h\right ) ^{5}}{5!}f^{\relax (5) }\left (\xi _{2}\right ) \end {align*}
Subtract the second from the first equation
\begin {align*} f\left (x+2h\right ) -f\left (x-2h\right ) & =4hf\ ^{\prime }\left ( x\right ) +2\frac {\left (2h\right ) ^{3}}{3!}f^{\relax (3) }\left ( x\right ) +\frac {\left (2h\right ) ^{5}}{5!}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \\ & =4hf\ ^{\prime }\relax (x) +\frac {8}{3}h^{3}f^{\relax (3) }\relax (x) +\frac {4}{15}h^{5}\left [ f^{\relax (5) }\left ( \xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \end {align*}
Solve for \(f^{\prime }\relax (x) \) we obtain
\begin {equation} f\ ^{\prime }\relax (x) =\frac {1}{4h}\left [ f\left (x+2h\right ) -f\left (x-2h\right ) \right ] -\frac {4}{6}h^{2}f^{\relax (3) }\left ( x\right ) -\frac {1}{15}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \tag {2} \end {equation}
We want to eliminate \(f^{(3)}\relax (x) \) from the above. So we multiply eq(1) by 4 and subtract eq(2) from the result. So equation (1) becomes
\begin {align} 4f\ ^{\prime }\relax (x) & =4\left (\frac {1}{2h}\left [ f\left ( x+h\right ) -f\left (x-h\right ) \right ] -\frac {1}{6}h^{2}f^{\left ( 3\right ) }\relax (x) -\frac {1}{120}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \right ) \nonumber \\ & =\frac {2}{h}\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] -\frac {4}{6}h^{2}f^{\relax (3) }\relax (x) -\frac {1}{30}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\left ( 5\right ) }\left (\xi _{2}\right ) \right ] \tag {3} \end {align}
Now subtract (2) from (3) we obtain
\begin {align*} 3f^{\prime }\relax (x) & =\frac {2}{h}\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] -\frac {4}{6}h^{2}f^{\relax (3) }\left ( x\right ) -\frac {1}{30}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] -\\ & \left (\frac {1}{4h}\left [ f\left (x+2h\right ) -f\left (x-2h\right ) \right ] -\frac {4}{6}h^{2}f^{\relax (3) }\relax (x) -\frac {1}{15}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\left ( 5\right ) }\left (\xi _{2}\right ) \right ] \right ) \end {align*}
Hence
\begin {align*} 3f^{\prime }\relax (x) & =\frac {2}{h}\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] -\frac {1}{30}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] -\\ & \frac {1}{4h}\left [ f\left (x+2h\right ) -f\left (x-2h\right ) \right ] +\frac {1}{15}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \\ & \\ f^{\prime }\relax (x) & =\frac {2}{3h}\left [ f\left (x+h\right ) -f\left (x-h\right ) \right ] -\frac {1}{12h}\left [ f\left (x+2h\right ) -f\left (x-2h\right ) \right ] +\frac {1}{90}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \\ & =\frac {1}{12h}\left [ 8f\left (x+h\right ) -8f\left (x-h\right ) -f\left (x+2h\right ) -f\left (x-2h\right ) \right ] +\frac {1}{90}h^{4}\left [ f^{\relax (5) }\left (\xi _{1}\right ) +f^{\left ( 5\right ) }\left (\xi _{2}\right ) \right ] \end {align*}
Rearrange terms to make it look as in the textbook
\begin {equation} f^{\prime }\relax (x) =\frac {1}{12h}\left [ -f\left (x+2h\right ) +8f\left (x+h\right ) -8f\left (x-h\right ) -f\left (x-2h\right ) \right ] +\frac {1}{90}h^{4}\left [ f^{\relax (5) }\left (\xi \right ) \right ] \tag {4} \end {equation}
Where we replaced \(\frac {1}{90}h^{4}\left [ f^{\relax (5) }\left ( \xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) \right ] \) by \(\frac {1}{45}h^{4}\left [ \frac {f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) }{2}\right ] =\frac {1}{90}h^{4}\left [ f^{\relax (5) }\left (\xi \right ) \right ] \) with \(f^{\relax (5) }\left (\xi \right ) \) being the mean value of \(\frac {f^{\relax (5) }\left (\xi _{1}\right ) +f^{\relax (5) }\left (\xi _{2}\right ) }{2}\)
Hence from equation (4) we see that the error is \(O\left (h^{4}\right ) \) as required to show.
Hence\[ \fbox {$f^\prime \relax (x) \approx \frac {1}{12h}\left [ -f\left ( x+2h\right ) +8f\left (x+h\right ) -8f\left (x-h\right ) -f\left ( x-2h\right ) \right ] $}\]
Now we need to show the formula for \(f^{\prime \prime }\relax (x) .\) We do the same as above, but instead of subtracting equations, we add them. We start from the top to show these again step by step.
From Taylor expansion, we write, by expanding around \(x+h\) and \(x-h\)
\begin {align*} f\left (x+h\right ) & =f\relax (x) +hf\ ^{\prime }\relax (x) +\frac {h^{2}}{2}f^{\prime \prime }\relax (x) +\frac {h^{3}}{3!}f^{\left ( 3\right ) }\relax (x) +\frac {h^{4}}{4!}f^{\relax (4) }\left ( x\right ) +\frac {h^{5}}{5!}f^{\relax (5) }\relax (x) +\frac {h^{6}}{6!}f^{\relax (6) }\left (\xi _{1}\right ) \\ f\left (x-h\right ) & =f\relax (x) -hf\ ^{\prime }\relax (x) +\frac {h^{2}}{2}f^{\prime \prime }\relax (x) -\frac {h^{3}}{3!}f^{\left ( 3\right ) }\relax (x) +\frac {h^{4}}{4!}f^{\relax (4) }\left ( x\right ) -\frac {h^{5}}{5!}f^{\relax (5) }\relax (x) +\frac {h^{6}}{6!}f^{\relax (6) }\left (\xi _{2}\right ) \end {align*}
Add the second to the first equation
\[ f\left (x+h\right ) +f\left (x-h\right ) =2f\ \relax (x) +h^{2}f^{\prime \prime }\relax (x) +\frac {h^{4}}{12}f^{\relax (4) }\relax (x) +\frac {h^{6}}{6!}\left [ f^{\relax (6) }\left ( \xi _{1}\right ) +f^{\relax (6) }\left (\xi _{2}\right ) \right ] \]
Solve for \(f^{\prime \prime }\relax (x) \) we obtain
\begin {equation} f^{\prime \prime }\relax (x) =\frac {1}{h^{2}}\left [ f\left (x+h\right ) +f\left (x-h\right ) \right ] -\frac {2}{h^{2}}f\ \relax (x) -\frac {h^{2}}{12}f^{\relax (4) }\relax (x) -\frac {1}{720}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\left ( 6\right ) }\left (\xi _{2}\right ) \right ] \tag {1A} \end {equation}
Now we do the same again, but by expanding around \(x+2h\) and \(x-2h\)
\begin {align*} f\left (x+2h\right ) & =f\relax (x) +2hf\ ^{\prime }\relax (x) +\frac {\left (2h\right ) ^{2}}{2}f^{\prime \prime }\relax (x) +\frac {\left (2h\right ) ^{3}}{3!}f^{\relax (3) }\relax (x) +\frac {\left (2h\right ) ^{4}}{4!}f^{\relax (4) }\relax (x) +\frac {\left (2h\right ) ^{5}}{5!}f^{\relax (5) }\relax (x) +\frac {\left (2h\right ) ^{6}}{6!}f^{\relax (6) }\left (\xi _{1}\right ) \\ f\left (x-2h\right ) & =f\relax (x) -2hf\ ^{\prime }\relax (x) +\frac {\left (2h\right ) ^{2}}{2}f^{\prime \prime }\relax (x) -\frac {\left (2h\right ) ^{3}}{3!}f^{\relax (3) }\relax (x) +\frac {\left (2h\right ) ^{4}}{4!}f^{\relax (4) }\relax (x) -\frac {\left (2h\right ) ^{5}}{5!}f^{\relax (5) }\relax (x) +\frac {\left (2h\right ) ^{6}}{6!}f^{\relax (6) }\left (\xi _{1}\right ) \end {align*}
Add the second to the first equation
\begin {align*} f\left (x+2h\right ) +f\left (x-2h\right ) & =2f\ \relax (x) +\left (2h\right ) ^{2}f^{\prime \prime }\relax (x) +\frac {\left ( 2h\right ) ^{4}}{12}f^{\relax (4) }\relax (x) +\frac {\left ( 2h\right ) ^{6}}{6!}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\relax (6) }\left (\xi _{2}\right ) \right ] \\ & =2f\ \relax (x) +4h^{2}f^{\prime \prime }\relax (x) +\frac {4}{3}h^{4}f^{\relax (4) }\relax (x) +\frac {4}{45}h^{6}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\relax (6) }\left ( \xi _{2}\right ) \right ] \end {align*}
Solve for \(f^{\prime \prime }\relax (x) \) we obtain
\begin {equation} f\ ^{\prime \prime }\relax (x) =\frac {1}{4h^{2}}\left [ f\left ( x+2h\right ) +f\left (x-2h\right ) \right ] -\frac {1}{2h^{2}}f\ \left ( x\right ) -\frac {1}{3}h^{2}f^{\relax (4) }\relax (x) -\frac {1}{45}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\left ( 6\right ) }\left (\xi _{2}\right ) \right ] \tag {2A} \end {equation}
We want to eliminate \(f^{(4)}\relax (x) \) from the above. So we multiply eq(1A) by 4 and subtract eq(2) from the result. So equation (1A) becomes
\begin {align} 4f^{\prime \prime }\relax (x) & =4\left (\frac {1}{h^{2}}\left [ f\left (x+h\right ) +f\left (x-h\right ) \right ] -\frac {2}{h^{2}}f\ \left ( x\right ) -\frac {h^{2}}{12}f^{\relax (4) }\relax (x) -\frac {1}{720}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\left ( 6\right ) }\left (\xi _{2}\right ) \right ] \right ) \nonumber \\ & =\frac {4}{h^{2}}\left [ f\left (x+h\right ) +f\left (x-h\right ) \right ] -\frac {8}{h^{2}}f\ \relax (x) -\frac {1}{3}h^{2}f^{\relax (4) }\relax (x) -\frac {1}{180}h^{4}\left [ f^{\relax (6) }\left ( \xi _{1}\right ) +f^{\relax (6) }\left (\xi _{2}\right ) \right ] \tag {3A} \end {align}
Now subtract (2A) from (3A) we obtain
\begin {align*} 3f^{\prime \prime }\relax (x) & =\frac {4}{h^{2}}\left [ f\left ( x+h\right ) +f\left (x-h\right ) \right ] -\frac {8}{h^{2}}f\ \left ( x\right ) -\frac {1}{3}h^{2}f^{\relax (4) }\relax (x) -\frac {1}{180}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\left ( 6\right ) }\left (\xi _{2}\right ) \right ] -\\ & \left (\frac {1}{4h^{2}}\left [ f\left (x+2h\right ) +f\left ( x-2h\right ) \right ] -\frac {1}{2h^{2}}f\ \relax (x) -\frac {1}{3}h^{2}f^{\relax (4) }\relax (x) -\frac {1}{45}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\relax (6) }\left ( \xi _{2}\right ) \right ] \right ) \end {align*}
Hence
\begin {align*} 3f^{\prime \prime }\relax (x) & =\frac {4}{h^{2}}\left [ f\left ( x+h\right ) +f\left (x-h\right ) \right ] -\frac {8}{h^{2}}f\ \left ( x\right ) -\frac {1}{180}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\relax (6) }\left (\xi _{2}\right ) \right ] -\\ & \frac {1}{4h^{2}}\left [ f\left (x+2h\right ) +f\left (x-2h\right ) \right ] +\frac {1}{2h^{2}}f\ \relax (x) +\frac {1}{45}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\relax (6) }\left ( \xi _{2}\right ) \right ] \\ & \\ f^{\prime \prime }\relax (x) & =\frac {4}{3h^{2}}\left [ f\left ( x+h\right ) +f\left (x-h\right ) \right ] -\frac {1}{12h^{2}}\left [ f\left ( x+2h\right ) +f\left (x-2h\right ) \right ] -\frac {8}{3h^{2}}f\ \left ( x\right ) +\frac {1}{6h^{2}}f\ \relax (x) -\\ & \frac {1}{3\times 180}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\relax (6) }\left (\xi _{2}\right ) \right ] +\frac {1}{3\times 45}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\relax (6) }\left (\xi _{2}\right ) \right ] \\ & \\ & =\frac {1}{12h^{2}}\left (16\left [ f\left (x+h\right ) +f\left ( x-h\right ) \right ] -\left [ f\left (x+2h\right ) +f\left (x-2h\right ) \right ] -32f\ \relax (x) +2f\ \relax (x) \right ) +\frac {1}{180}h^{4}\left [ f^{\relax (6) }\left (\xi _{1}\right ) +f^{\left ( 6\right ) }\left (\xi _{2}\right ) \right ] \\ & =\frac {1}{12h^{2}}\left (16f\left (x+h\right ) +16f\left (x-h\right ) -f\left (x+2h\right ) -f\left (x-2h\right ) -30f\ \relax (x) \right ) +\frac {1}{180}h^{4}\left [ f^{\relax (6) }\left (\xi \right ) \right ] \end {align*}
Rearrange terms to make it look as in the textbook
\begin {equation} f^{\prime \prime }\relax (x) =\frac {1}{12h^{2}}\left (-f\left ( x+2h\right ) +16f\left (x+h\right ) -30f\ \relax (x) +16f\left ( x-h\right ) -f\left (x-2h\right ) \right ) +\frac {1}{180}h^{4}\left [ f^{\relax (6) }\left (\xi \right ) \right ] \tag {4A} \end {equation}
Hence from equation (4A) we see that the error is \(O\left (h^{4}\right ) \) as required to show.
Hence\[ \fbox {$f^\prime \prime \relax (x) \approx \frac {1}{12h^2}\left (-f\left ( x+2h\right ) +16f\left (x+h\right ) -30f\ \relax (x) +16f\left ( x-h\right ) -f\left (x-2h\right ) \right ) $}\]
problem: Show that in Richardson extrapolation, \(D\left (2,2\right ) =\frac {16}{15}\psi \left (\frac {h}{2}\right ) -\frac {1}{15}\psi \left ( h\right ) \)
Solution:
\begin {equation} D\left (n,k\right ) =\frac {4^{k}}{4^{k}-1}D\left (n,k-1\right ) -\frac {1}{4^{k}-1}D\left (n-1,k-1\right ) \tag {1} \end {equation}
Now, when \(n=2,k=2\), we obtain from (1)
\begin {align*} D\left (2,2\right ) & =\frac {4^{2}}{4^{2}-1}D\left (2,1\right ) -\frac {1}{4^{2}-1}D\left (1,1\right ) \\ & =\frac {16}{15}D\left (2,1\right ) -\frac {1}{15}D\left (1,1\right ) \end {align*}
But since \(D\left (1,1\right ) =\psi \relax (h) ,D\left (2,1\right ) =\psi \left (\frac {h}{2}\right ) \)
\[ D\left (2,2\right ) =\frac {16}{15}\psi \left (\frac {h}{2}\right ) -\frac {1}{15}\psi \relax (h) \]
problem: Using Taylor series, derive the error term for the approximation
\[ f^{\prime }\relax (x) \approx \frac {1}{2h}\left [ -3f\relax (x) +4f\left (x+h\right ) -f\left (x+2h\right ) \right ] \]
answer:
expand around \(x+h\)
\begin {align} f\left (x+h\right ) & =f\relax (x) +hf^{\prime }\relax (x) +\frac {h^{2}}{2}f^{\prime \prime }\relax (x) +\frac {h^{3}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) \nonumber \\ f^{\prime }\relax (x) & =\frac {1}{h}f\left (x+h\right ) -\frac {1}{h}f\relax (x) -\frac {h}{2}f^{\prime \prime }\relax (x) -\frac {h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) \tag {1} \end {align}
Now expand around \(x+2h\)
\begin {align} f\left (x+2h\right ) & =f\relax (x) +2hf^{\prime }\relax (x) +2h^{2}f^{\prime \prime }\relax (x) +\frac {8h^{3}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) \nonumber \\ f^{\prime }\relax (x) & =\frac {1}{2h}f\left (x+2h\right ) -\frac {1}{2h}f\relax (x) -hf^{\prime \prime }\relax (x) -\frac {4h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) \tag {2} \end {align}
Multiply (2) by \(-\frac {1}{2}\) and add result to (1) we obtain
\begin {align*} -\frac {1}{2}f^{\prime }\relax (x) +f^{\prime }\relax (x) & =-\frac {1}{2}\left (\frac {1}{2h}f\left (x+2h\right ) -\frac {1}{2h}f\left ( x\right ) -hf^{\prime \prime }\relax (x) -\frac {4h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) \right ) +\\ & \left (\frac {1}{h}f\left (x+h\right ) -\frac {1}{h}f\relax (x) -\frac {h}{2}f^{\prime \prime }\relax (x) -\frac {h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) \right ) \\ & \\ \frac {1}{2}f^{\prime }\relax (x) & =\frac {-1}{4h}f\left (x+2h\right ) +\frac {1}{4h}f\relax (x) +\frac {h}{2}f^{\prime \prime }\relax (x) +\frac {2h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) +\frac {1}{h}f\left (x+h\right ) -\frac {1}{h}f\relax (x) -\frac {h}{2}f^{\prime \prime }\relax (x) -\frac {h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) \\ f^{\prime }\relax (x) & =\frac {-1}{2h}f\left (x+2h\right ) +\frac {1}{2h}f\relax (x) +hf^{\prime \prime }\relax (x) +\frac {4h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) +\frac {2}{h}f\left ( x+h\right ) -\frac {2}{h}f\relax (x) -hf^{\prime \prime }\relax (x) -\frac {2h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) \\ & =\left [ \frac {-1}{2h}f\left (x+2h\right ) +\frac {1}{2h}f\relax (x) +hf^{\prime \prime }\relax (x) +\frac {2}{h}f\left (x+h\right ) -\frac {2}{h}f\relax (x) -hf^{\prime \prime }\relax (x) \right ] -\frac {2h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) +\frac {4h^{2}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) \\ & =\frac {1}{2h}\left [ -f\left (x+2h\right ) +f\relax (x) +4f\left ( x+h\right ) -4f\relax (x) \right ] -\frac {h^{2}}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) +\frac {2h^{2}}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \\ & =\frac {1}{2h}\left [ -f\left (x+2h\right ) -3f\relax (x) +4f\left ( x+h\right ) \right ] -h^{2}\left (\frac {1}{3}f^{\prime \prime \prime }\left ( \xi _{1}\right ) +\frac {2}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \right ) \end {align*}
Which is the equation we are asked to show.
From the above we see that the error term is given by \[ h^{2}\left (\frac {1}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) +\frac {2}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \right ) \]
Hence the error is \(O\left (h^{2}\right ) \)
problem: Using Taylor series, derive the error term for the approximation
\[ f^{\prime \prime }\relax (x) \approx \frac {1}{h^{2}}\left [ f\left ( x\right ) -2f\left (x+h\right ) +f\left (x+2h\right ) \right ] \]
Answer: expand around \(x+h\)
\begin {align} f\left (x+h\right ) & =f\relax (x) +hf^{\prime }\relax (x) +\frac {h^{2}}{2}f^{\prime \prime }\relax (x) +\frac {h^{3}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) \nonumber \\ \frac {h^{2}}{2}f^{\prime \prime }\relax (x) & =f\left (x+h\right ) -f\relax (x) -hf^{\prime }\relax (x) -\frac {h^{3}}{6}f^{\prime \prime \prime }\left (\xi _{1}\right ) \nonumber \\ f^{\prime \prime }\relax (x) & =\frac {2}{h^{2}}f\left (x+h\right ) -\frac {2}{h^{2}}f\relax (x) -\frac {2}{h}f^{\prime }\relax (x) -\frac {h}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) \tag {1} \end {align}
Now expand around \(x+2h\)
\begin {align} f\left (x+2h\right ) & =f\relax (x) +2hf^{\prime }\relax (x) +2h^{2}f^{\prime \prime }\relax (x) +\frac {8h^{3}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) \nonumber \\ 2h^{2}f^{\prime \prime }\relax (x) & =f\left (x+2h\right ) -f\left ( x\right ) -2hf^{\prime }\relax (x) -\frac {8h^{3}}{6}f^{\prime \prime \prime }\left (\xi _{2}\right ) \nonumber \\ f^{\prime \prime }\relax (x) & =\frac {1}{2h^{2}}f\left (x+2h\right ) -\frac {1}{2h^{2}}f\relax (x) -\frac {1}{h}f^{\prime }\relax (x) -\frac {2h}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \tag {2} \end {align}
Multiply (2) by \(-2\) and add result to (1) we obtain
\begin {align*} -2f^{\prime \prime }\relax (x) +f^{\prime \prime }\relax (x) & =-2\left (\frac {1}{2h^{2}}f\left (x+2h\right ) -\frac {1}{2h^{2}}f\left ( x\right ) -\frac {1}{h}f^{\prime }\relax (x) -\frac {2h}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \right ) \\ & +\frac {2}{h^{2}}f\left (x+h\right ) -\frac {2}{h^{2}}f\relax (x) -\frac {2}{h}f^{\prime }\relax (x) -\frac {h}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) \\ -f^{\prime \prime }\relax (x) & =-\frac {1}{h^{2}}f\left (x+2h\right ) +\frac {1}{h^{2}}f\relax (x) +\frac {2}{h}f^{\prime }\relax (x) +\frac {4h}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) +\frac {2}{h^{2}}f\left (x+h\right ) -\frac {2}{h^{2}}f\relax (x) -\frac {2}{h}f^{\prime }\relax (x) -\frac {h}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) \\ f^{\prime \prime }\relax (x) & =\frac {1}{h^{2}}f\left (x+2h\right ) -\frac {1}{h^{2}}f\relax (x) -\frac {2}{h}f^{\prime }\relax (x) -\frac {4h}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) -\frac {2}{h^{2}}f\left (x+h\right ) +\frac {2}{h^{2}}f\relax (x) +\frac {2}{h}f^{\prime }\relax (x) +\frac {h}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) \\ & =\frac {1}{h^{2}}f\left (x+2h\right ) -\frac {1}{h^{2}}f\relax (x) -\frac {2}{h^{2}}f\left (x+h\right ) +\frac {2}{h^{2}}f\relax (x) +\frac {h}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) -\frac {4h}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \\ & =\frac {1}{h^{2}}\left (f\left (x+2h\right ) -f\relax (x) -2f\left (x+h\right ) +2f\relax (x) \right ) +h\left (\frac {1}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) -\frac {4}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \right ) \\ & =\frac {1}{h^{2}}\left (f\left (x+2h\right ) +f\relax (x) -2f\left (x+h\right ) \right ) +h\left (\frac {1}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) -\frac {4}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \right ) \end {align*}
Hence
\[ f^{\prime \prime }\relax (x) \approx \frac {1}{h^{2}}\left (f\left ( x+2h\right ) +f\relax (x) -2f\left (x+h\right ) \right ) \]
with the error term \[ h\left (\frac {1}{3}f^{\prime \prime \prime }\left (\xi _{1}\right ) -\frac {4}{3}f^{\prime \prime \prime }\left (\xi _{2}\right ) \right ) \] Hence the error is \(O\relax (h) \)
This is the output
This is the source code
This table summarizes the results of the 3 methods
| Method | RESULTS |
| Simpson | Error term \(\frac {1}{180}\left (b-a\right ) h^{4}\ \max \left \vert f^{\relax (4) }\left (\xi \right ) \right \vert \) |
| \(I=\int _{a}^{b}f\relax (x) dx\approx \frac {h}{3}\left (f\left ( x_{0}\right ) +2\sum _{i=2}^{N/2}f\left (x_{2i-2}\right ) +4\sum _{i=1}^{N/2}f\left (x_{2i-1}\right ) +f\left (x_{N}\right ) \right ) \) | |
| Intervals needed: \(900\) | |
| long format print of numerical integration: \(90.379254649757272\) | |
| Midpoint | Error term \(\frac {1}{24}\left (b-a\right ) h^{2}\max \left \vert f^{\relax (2) }\left (\xi \right ) \right \vert \) |
| \(\int _{a}^{b}f\relax (x) dx\approx h\sum _{i=1}^{N-1}f\left ( \frac {x_{i+1}+x_{i}}{2}\right ) \ \ \ \ \ \ \ \ \ \ \ \ \ \)note: \(N\) here is number of points | |
| Intervals needed: \(174,285\) | |
| long format print of numerical integration: \(90.379254649446878\) | |
| Trapezoid | Error term \(\frac {1}{12}\left (b-a\right ) h^{2}\max \left \vert f^{\relax (2) }\left (\xi \right ) \right \vert \) |
| \(h\left (\frac {f\left (x_{1}\right ) }{2}+\sum _{i=2}^{N-1}f\left ( x_{i}\right ) +\frac {f\left (x_{N}\right ) }{2}\right ) \ \ \ \ \ \ \ \ \ \ \ \ \ \)note: \(N\) here is number of points | |
| Intervals needed: \(246,476\) | |
| long format print of numerical integration: \(90.379254649958952\) | |
The error term in simpson is \(\frac {1}{180}\left (b-a\right ) h^{4}\ \max \left \vert f^{\relax (4) }\left (\xi \right ) \right \vert \) for some \(\xi \) between \(b,a\). Since we want to limit the maximum error, we look to find where \(f\left (\xi \right ) \) is Max.
The function is \(x\ln \relax (x) \), hence \(f^{\relax (4) }\left ( x\right ) =\frac {2}{x^{3}}\) and this is maximum when \(x\) is smallest. Hence the maximum will occur at the lower end of the range, which is \(x=1\) in this example.
Now we find the number of intervals \(N\) from solving \(\frac {1}{180}\left ( b-a\right ) h^{4}\ \max \left \vert f^{\relax (4) }\left (\xi \right ) \right \vert <10^{-9}\) where \(10^{-9}\) is the error we are asked to limit our computation error to be below.
Next, we solve for \(h\) from the above. Knowing \(h\), we find \(N\) which is the number of intervals. Next, we make sure \(N\) is even number by adjusting it if needed. We need to have even number of intervals Next we apply the simpson integration formula which is
\[ I=\int _{a}^{b}f\relax (x) dx\approx \frac {h}{3}\left (f\left ( x_{0}\right ) +2\sum _{i=2}^{N/2}f\left (x_{2i-2}\right ) +4\sum _{i=1}^{N/2}f\left (x_{2i-1}\right ) +f\left (x_{N}\right ) \right ) \]
In the above \(N\) is the number of intervals. Not to be confused with the following 2 algorithms below, where I used \(N\) to be number of points. For simpson, it was easier to stick with \(N\) being number of intervals.
The matlab implementation uses a vectorized version for speed.
To verify that the correct answer is obtain, it was compared with the output from a computer algebra system which uses an arbitrary large number of correct decimal points. The Matlab output was aligned against the CAS output and the digits verified to be correct to 9 decimal places are required.
Source code:
The error term is \(\frac {1}{24}\left (b-a\right ) h^{2}\max \left \vert f^{\relax (2) }\left (\xi \right ) \right \vert \) for some \(\xi \) between \(b,a\). Midterm is evaluated as follows
\[ I=\int _{a}^{b}f\relax (x) dx\approx h\sum _{i=1}^{N-1}f\left ( \frac {x_{i+1}+x_{i}}{2}\right ) \]
where \(N\) is the number of points. And I am using the Matlab convention for indexing, where the first point is \(x_{1}\) and not \(x_{0}\)
We start by finding the number of intervals by solving for \(h\) from \(\frac {1}{24}\left (b-a\right ) h^{2}\max \left \vert f^{\relax (2) }\left ( \xi \right ) \right \vert <10^{-9}\) where \(10^{-9}\) is the error we are asked to limit our computation error to be below.
The function is \(x\ln \relax (x) \), hence \(f^{\relax (2) }\left ( x\right ) =\frac {1}{x}\) which is maximum at \(x=a\).
The matlab implementation is below with the output.
Output is
Midpoint: Number of intervals needed is 174285 answer is I = 90.379254649446878
The error term is \(\frac {1}{12}\left (b-a\right ) h^{2}\max \left \vert f^{\relax (2) }\left (\xi \right ) \right \vert \) for some \(\xi \) between \(b,a\). Trapezoid is evaluated as follows
\[ h\left (\frac {f\left (x_{1}\right ) }{2}+\sum _{i=2}^{n-1}f\left ( x_{i}\right ) +\frac {f\left (x_{n}\right ) }{2}\right ) \]
Where \(n\) is number of points, and I am using the Matlab indexing where \(x_{1}\) is the first point, and not \(x_{0}\), hence the last point is \(x_{n}\)
The following is the source code and the output
Output
Trapezoid: Number of intervals needed is 246476 answer is I = 90.379254649958952