MATH/APPM 4650
Class notes, February 18
Numerical differentiation
Most of today's notes will be on the board. Here are the basic ideas.
If f(x) = xx
then f'(x) = (1+ln(x)) xx
and e.g. f'(2.0000000) = 6.7725887.
If we try to compute f'(2) numerically, using
f'(2) ≈ [f(2+h) - f(2)] / h
for h small, we get (with eight digit roundoff)
|
h
|
f'(2) ≈
|
|
10-1
|
7.4963810
|
|
10-2
|
6.8404000
|
|
10-3
|
6.7793000
|
|
10-4
|
6.7730000
|
|
10-5
|
6.7700000
|
|
10-6
|
6.8000000
|
|
10-7
|
7.0000000
|
|
10-8
|
0.0000000
|
Observe the closest we get is when h = 10-4, and the error is 4 × 10-4.
Taking h smaller than this makes the approximation worse.
What's going on?
When h = 0.0001, we have
[f(2.0001000) - f(2.0000000)] / [2.0001000 - 2.0000000]
= [4.0006773 - 4.0000000] / [0.00010000000]
= 0.00067730000 / 0.00010000000
= 6.7730000.
Roundoff error!
Lesson: if you possibly can, remember your calculus formulas!
If you can't or won't remember the formulas, or (more likely) if you don't know the function precisely, what to do?
Suppose you have a table of values
|
x
|
1.8
|
1.9
|
2.0
|
2.1
|
2.2
|
|
f(x)
|
2.88
|
3.39
|
4.00
|
4.75
|
5.67
|
We could approximate the derivative as
f'(2) ≈ [f(2.1)-f(2.0)]/0.1 = 7.5
or
f'(2) ≈ [f(2.0)-f(1.9)]/0.1 = 6.1
or
f'(2) ≈ [f(2.1)-f(1.9)]/0.2 = 6.8
The last one is clearly the best. Why?
Use Taylor polynomials to estimate the error.
(See board.)
Optimal formulas (see board for derivations):
- If you are given f(x), f(x+h), and f(x-h),
the best formula to use is
f'(x) ≈ [f(x+h) - f(x - h)] / [2h].
- If you are given f(x), f(x+h), and f(x+2h), the best formula to use is
f'(x) ≈ [-f(x+2h) + 4f(x+h) - 3f(x)] / [2h].
- If you are given f(x), f(x-h), and f(x-2h), the best formula to use is
f'(x) ≈ [f(x-2h) - 4f(x-h) + 3f(x)] / [2h].
These are called three-point formulas and they all have theoretical error
f'(x) - [f(x+h) - f(x - h)] / [2h] = O(h2).
Generally one can always derive an (n+1)-point formula that has theoretical error O(hn).
Given the di, you just expand out
c0 f(x+d0h) + c1 f(x+d1h) + . . . + cn f(x+dnh)
as a Taylor series in h up to order O(hn+1).
Set the coefficient of f'(x) to be one and the coefficient of all other terms to be zero.
Then solve the system of equations for the coefficients ci.
Note: You can also use the exact same procedure to find f''(x) or higher derivatives, if you have enough sample points.
Generally these will be less accurate (for example, a three-point second derivative formula will only be order O(h)).
Roundoff error:
Observe the pattern in the errors in the computation above.
|
h
|
f'(2) ≈
|
|
10-1
|
7 × 10-1
|
|
10-2
|
7 × 10-2
|
|
10-3
|
7 × 10-3
|
|
10-4
|
4 × 10-4
|
|
10-5
|
3 × 10-3
|
|
10-6
|
3 × 10-2
|
|
10-7
|
2 × 10-1
|
|
10-8
|
7 × 100
|
For the first few terms, the theoretical roundoff error O(h) is the dominant error term.
Eventually that becomes negligible, and we get roundoff due to loss of digits of precision.
With 8 digits of precision and h=10-k, we have potential roundoff of up to 9 × 10k-7.
In general with m digits of precision and h=10-k we'd have roundoff error about 10k-m+1.
Roughly speaking, the roundoff error is about 10m+1/h.
So the total error, again roughly, is at most the theoretical error plus the roundoff error:
e(h) ≈ C hn-1 + 10m+1/h
for the optimal n-point method.
Hence the best possible h is roughly 10m/n.
(See derivation on board.)