Finding backward finite difference approximation to derivatives

[visharad]

Problem - Find backward finite difference approximations to first, second and third order derivatives to error of order h^3

Attempt
By Tailor’s series expansion
f(x-h) = f(x) - h f’(x) + h^2/2! f’’(x) - h^3/3! f’’’(x) + …
Therefore, f’(x) with error of order h^3 is given by
f(x-h) = f(x) - h f’(x) + h^2/2! f’’(x) - h^3/3! f’’’(x)
h f’(x) = f(x) – f(x-h) + h^2/2! f’’(x) – h^3/3! f’’’(x)
f’(x) = [f(x) – f(x-h)]/h + h/2! f’’(x) – h^2/3! f’’’(x)

But I do not know what to substitute for f''(x) and f'''(x)
Also, what to do for 2nd and 3rd order derivatives?

 

[TheoMcCloskey]

For the first derivatives, you will need to eliminate other higher order terms. Construct additional Taylor expansions in the form of

f(x-2h) = f(x) - ...
f(x-3h) = f(x) - ...
f(x-4h) = f(x) - ...
...

Use as many as necessary with your first exapnsion to eliminate the unwanted terms and leaving the h^3 remainder term.

 

[visharad]

Thank you. This is what I did for 1st derivative. Please see if it is correct.

Taylor’s series expansion of f(x-h):
f(x-h) = f(x) – h f’(x) + h^2/2! f’’(x) - h^3/3! f’’’(x) + O(h^4)
f(x-h) = f(x) – h f’(x) + (1/2)h^2 f’’(x) – (1/6) h^3 f’’’(x) + O(h^4) ------------(1)

Taylor’s series expansion of f(x-2h) is
f(x-2h) = f(x) – 2h f’(x) + 4 h^2/2! f’’(x) – 8 h^3/3! f’’’(x) + O(h^4)
f(x-2h) = f(x) – 2h f’(x) + 2 h^2 f’’(x) – (4/3) h^3 f’’’(x) + O(h^4) ------------(2)

Multiplying equation (1) by 4, we get
4 f(x-h) = 4 f(x) – 4h f’(x) + 2 h^2 f’’(x) – (2/3) h^3 f’’’(x) + O(h^4)
Subtracting equation (2) from the above equation, we get
3 f(x-h) = 3 f(x) – 2h f’(x) + (2/3) h^3 f’’’(x) + O(h^4)----------------------(3)
Using 2h in place of h, we get
3 f(x-2h) = 3 f(x) – 4h f’(x) + (16/3) h^3 f’’’(x) + O(h^4)-----------------------(4)
Multiplying equation (3) by 8,
24 f(x-h) = 24 f(x) – 16 h f’(x) + (16/3) h^3 f’’’(x) + O(h^4)
Subtracting equation (4) from the above equation, we get
24 f(x-h) – 3 f(x-2h) = 21 f(x) – 12 h f’(x) + O(h^4)
12 h f’(x) = 21 f(x) – 24 f(x-h) + 3 f(x-2h) + O(h^4)
12 h f’(x) = 21 f(x) – 21 f(x-h) – 3 f(x-h) + 3 f(x-2h) + O(h^4)
12 h f’(x) = 21 [f(x) –f(x-h)] – 3 [f(x-h) - f(x-2h)] + O(h^4)
Dividing both sides by 12 h,
f’(x) = (7/4) [f(x) –f(x-h)]/h – (1/4) [f(x-h) - f(x-2h)]/h + O(h^3)
Therefore, the first derivative to error of order h^3 is
f’(x) = (7/4) [f(x) –f(x-h)]/h – (1/4) [f(x-h) - f(x-2h)]/h

 

[TheoMcCloskey]

You started out OK, but not quite enough.

Since you want an approximation of third order, and since the first derviative terms will have a factor of "h" in them, the expansions need to be carried out to the fourth order term (h^4) so that a remainder term will be third order when the final division of h is done to yield the first derivative.

Since you need expansions to the fourth order, you will have terms involving the first, second and third order that you need to "eliminate" (ie, "solve for"). That's three "variables" (call them f', f'', and f''' for short).

This means you'll need three equations, or expansions. Let
<br /> f_{-i} = f(x-i\,h)<br />
then the (truncated) expansions needed are
<br /> f_{-1} = f_{0} - h\,f&#039; + \frac{1}{2!}h^2\,f&#039;&#039; - \frac{1}{3!}h^3\,f&#039;&#039;&#039; + \frac{1}{4!}h^4\,f^{(4)}<br />
<br /> f_{-2} = f_{0} - 2h\,f&#039; + \frac{1}{2!}(2h)^2\,f&#039;&#039; - \frac{1}{3!}(2h)^3\,f&#039;&#039;&#039; + \frac{1}{4!}(2h)^4\,f^{(4)}<br />
<br /> f_{-3} = f_{0} - 3h\,f&#039; + \frac{1}{2!}(3h)^2\,f&#039;&#039; - \frac{1}{3!}(3h)^3\,f&#039;&#039;&#039; + \frac{1}{4!}(3h)^4\,f^{(4)}<br />

I left the fourth order terms in for now so that we can see, in the end, the resulting leading error term.

You now need to solve this system of equations for f'

We can see that these are indeed a system of linear equations fore if we let the vector \textbf{b} = [b_1, b_2, b_3]^T such that
<br /> b_1 = f_{-1} - f_{0} -\frac{1}{4!}h^4\,f^{(4)}<br />
<br /> b_2 = f_{-2} - f_{0} -\frac{1}{4!}(2h)^4\,f^{(4)}<br />
<br /> b_3 = f_{-3} - f_{0} -\frac{1}{4!}(3h)^4\,f^{(4)}<br />
and let the vector \textbf{g} be
<br /> \textbf{g} = [f&#039;, f&#039;&#039;, f&#039;&#039;]^T<br />
Then the system resulting is
<br /> \textbf{b} = \textbf{A}\, \textbf{g}<br />
where the 3 x 3 matrix \textbf{A} has elements
<br /> a_{i,j} = \frac{(-1)^j\, (i\,h)^j }{j!}<br />

A simple, but careful reduction of this system easily yields the solution for f'

To achieve the other derivatives, to the same third order accuracy, will require more terms in the expansions, which means more expansions to solve for the desired derivative. The system of equations will expand to 4 x 4 for the second derivative and 5 x 5 for the third derivative.

BTW - I did look at your approach in detail and noticed an error at the point when you substituted "2h" in for "h". At this point, your left hand side is not correct since you should have a f(x-4\,h) term. I'm not saying this approach won't work (once corrected), but it will involve terms of f_{0}, f_{-1}, f_{-2} and f_{-4} and not the customary f_{0}, f_{-1}, f_{-2} and f_{-3}.

 

[visharad]

Yes, I noticed the error and below is my updated solution. Do you already know the expressions for 1st, 2nd, 3rd order derivatives to error of order h^3 using backward finite differences? Then I can see if my answer is correct.

Taylor’s series expansion of f(x-h):
f(x-h) = f(x) – h f’(x) + h^2/2! f’’(x) - h^3/3! f’’’(x) + O(h^4)
f(x-h) = f(x) – h f’(x) + (1/2)h^2 f’’(x) – (1/6) h^3 f’’’(x) + O(h^4) ------------(1)

Putting 2h in place of h,
f(x-2h) = f(x) – 2h f’(x) + 2 h^2 f’’(x) – (4/3) h^3 f’’’(x) + O(h^4) ------------(2)

Putting 3h in place of h,
f(x-3h) = f(x) – 3h f’(x) + (9/2)h^2 f’’(x) – (9/2) h^3 f’’’(x) + O(h^4) --------(3)

Choose constants a and b such that performing a*(1) + b*(2) – (3) cancels terms of f’’(x) and f’’’(x)
a/2 + 2b = 9/2--------------(4)
a/6 + 4b/3 = 9/2--------------(5)

Multiplying equation (5) by 3 and subtracting equation (4) from it,
2b = 9
b = 9/2
Substituting the value of b into equation (4),
a/2 + 9 = 9/2
a/2 = -9/2
a = -9

-18 * (1) + 9 * (2) – 2 * (3):
-18 f(x-h) + 9 f(x-2h) – 2 f(x-3h) = -11 f(x) + 6 h f’(x) + O(h^4)
6 h f’(x) = 11 f(x) -18 f(x-h) + 9 f(x-2h) – 2 f(x-3h) + O(h^4)
6 h f’(x) = 11 f(x) -11 f(x-h) -7 f(x-h) + 7 f(x-2h) + 2 f(x-2h) – 2 f(x-3h) + O(h^4)
6 h f’(x) = 11 [f(x) - f(x-h)] -7 [f(x-h) - f(x-2h)] + 2 [f(x-2h) – f(x-3h)] + O(h^4)
Dividing both sides by 6h will give the desired equation.

 

[TheoMcCloskey]

Yes, your answer for the first derivative agrees with mine. I yield
<br /> f&#039;(x) \approx \frac{11\,f_{0} - 18\,f_{-1} + 9\,f_{-2} - 2\,f_{-3} }{6\,h} + \frac{1}{4}h^3\,f^{(4)}(\zeta(x))<br />

I have not computed the other derivatives.

 

[visharad]

Thank you.
I was wondering if the expressions for other derivatives are already available in some book or web page, which you are aware of. I searched a lot but did not find.

 

[TheoMcCloskey]

Well, sometimes these expressions are hard to find, especially for the degree of approximation your looking for.

I should note that I led you down the most direct approach for computing these expressions. There are other methods, some of them using readily available expressions and a more theoretical result that leads to a surprisingly and (relatively) easy construction for any degree for any order of accuracy.

Let's consider another construction to the first derivative. Recall the Taylor expression:
<br /> f_{-1} = f_{0} - h\,f&#039; + \frac{1}{2!}h^2\,f&#039;&#039; - \frac{1}{3!}h^3\,f&#039;&#039;&#039; + \frac{1}{4!}h^4\,f^{(4)} + \cdots<br />
From here, solve for h\,f&#039; in the truncated series to yield
<br /> h\,f&#039; = (f_{0} - f_{-1}) + \frac{1}{2!}h^2\,f&#039;&#039; - \frac{1}{3!}h^3\,f&#039;&#039;&#039; + \frac{1}{4!}h^4\,f^{(4)}<br />
Now, to complete our task, all we need are suitable approximations to f&#039;&#039; and f&#039;&#039;&#039;. By "suitable", we mean that the approximations must be of sufficient degree of accuracy to yield an acceptable overall degree of accuracy when used in the equation (remember, we will be dividing by h). Thus, we want to see oders of approximation within the terms of the expression for h\,f&#039; that are of O(h^4).

This means we need:
a) a 2nd order (O(h^2)) approx for f&#039;&#039;
b) a 1st order (O(h)) approx for f&#039;&#039;&#039;

If we had those, we could substitute into the expression for h\,f&#039; to yield the final expression.

From available sources, we have the following:
<br /> h^2\,f&#039;&#039; = 2\,f_{0} - 5\,f_{-1} + 4\,f_{-2} - f_{-3} + O(h^4)<br />
<br /> h^3\,f&#039;&#039;&#039; = f_{0} - 3\,f_{-1} + 3\,f_{-2} - f_{-3} + O(h^4)<br />
Substituting these into the expression and collecting terms, we see that we can once again yield our result
<br /> 6h\,f&#039; = 11\,f_{0} - 18\,f_{-1} + 9\,f_{-2} - 2\,f_{-3}<br />

We can perform a similar construction for f&#039;&#039;. We now have
<br /> \frac{h^2}{2!}\,f&#039;&#039; = (f_{-1} - f_{0}) + h\,f&#039; + \frac{1}{3!}h^3\,f&#039;&#039;&#039; - \frac{1}{4!}h^4\,f^{(4)}<br />
and we require approximations
a) O(h^4) approx for f&#039;
b) O(h^2) approx for f^{(3)}
c) O(h) approx for f^{(4)}

From sources, we have
<br /> 12h\,f&#039; = 25\,f_{0} - 48\,f_{-1} + 36\,f_{-2} - 16\,f_{-3} + 3\,f_{-4} + O(h^5)<br />
<br /> 2h^3\,f&#039;&#039;&#039; = 5\,f_{0} - 18\,f_{-1} + 24\,f_{-2} - 14\,f_{-3} + 3\,f_{-4} + O(h^5)<br />
<br /> h^4\,f^{(4)} = f_{0} - 4\,f_{-1} + 6\,f_{-2} - 4\,f_{-3} + f_{-4} + O(h^5)<br />

Substituting into the expression, collecting terms, and solving for f&#039;&#039; yields
<br /> f&#039;&#039; = \frac{ 35\,f_{0} - 104\,f_{-1} + 114\,f_{-2} - 56\,f_{-3} + 11\,f_{-4} }{12\,h^2} + O(h^3)<br />

Unfortunately, continuing this approach for the third derivative requires fifth order approximation to f&#039; which may not be so readily available. In summary, the required approximations are:
a) O(h^5) approx for f&#039;
b) O(h^4) approx for f^&#039;&#039;
c) O(h^2) approx for f^{(4)}
d) O(h) approx for f^{(5)}

Instead of pursuing this approach, we should look at the last technique, ie, the technique/results of finite difference calculus. I won't get into it, but just simply reference the results (cf, eg, Hildebrand, Introduction to Numerical Analysis).

But - let's take a break - I'll post some more about this a little later. Just to suffice, I present what I think is the third derivative (this needs to be checked).
<br /> f^{(3)} \approx \frac{ 17\,f_{0} - 71\,f_{-1} + 118\,f_{-2} - 98\,f_{-3} + 41\,f_{-4} + 7\,f_{-5} }{4\,h^3} + O(h^3)<br />