Finite Differences
Nodes a = t 0 < ⋯ < t n = b a = t_0 < \cdots < t_n = b a = t 0 < ⋯ < t n = b t i = a + i h t_i = a + ih t i = a + ih h = b − a n h = \frac{b - a}{n} h = n b − a
f ′ ( x ) = lim h → 0 f ( x + h ) − f ( x ) h , f ′ ( t i ) ≈ 1 h ∑ k = − p q a k f ( t i + k h ) f'(x) = \lim_{h \to 0} \frac{f(x + h) - f(x)}{h}, \qquad f'(t_i) \approx \frac{1}{h}\sum_{k=-p}^{q} a_k f(t_i + kh) f ′ ( x ) = h → 0 lim h f ( x + h ) − f ( x ) , f ′ ( t i ) ≈ h 1 k = − p ∑ q a k f ( t i + kh ) Shifting so the point is 0 (s = x − t i s = x - t_i s = x − t i f ~ ( s ) = f ( s + t i ) \tilde{f}(s) = f(s + t_i) f ~ ( s ) = f ( s + t i ) d f d x ∣ x = t i = d f ~ d s ∣ s = 0 \frac{df}{dx}\big|_{x = t_i} = \frac{d\tilde{f}}{ds}\big|_{s = 0} d x df x = t i = d s d f ~ s = 0 f ′ ( 0 ) f'(0) f ′ ( 0 )
Forward f ′ ( x ) ≈ f ( x + h ) − f ( x ) h f'(x) \approx \frac{f(x + h) - f(x)}{h} f ′ ( x ) ≈ h f ( x + h ) − f ( x ) p = 0 p = 0 p = 0 q = 1 q = 1 q = 1 a 0 = − 1 a_0 = -1 a 0 = − 1 a 1 = 1 a_1 = 1 a 1 = 1 Backward f ′ ( x ) ≈ f ( x ) − f ( x − h ) h f'(x) \approx \frac{f(x) - f(x - h)}{h} f ′ ( x ) ≈ h f ( x ) − f ( x − h ) q = 0 q = 0 q = 0 Centered f ′ ( x ) ≈ f ( x + h ) − f ( x − h ) 2 h f'(x) \approx \frac{f(x + h) - f(x - h)}{2h} f ′ ( x ) ≈ 2 h f ( x + h ) − f ( x − h ) p = q = 1 p = q = 1 p = q = 1 a − 1 = − 1 2 a_{-1} = -\frac{1}{2} a − 1 = − 2 1 a 0 = 0 a_0 = 0 a 0 = 0 a 1 = 1 2 a_1 = \frac{1}{2} a 1 = 2 1
The centered formula is the derivative at 0 of the quadratic interpolant through − h , 0 , h -h, 0, h − h , 0 , h
Q ( x ) = x ( x − h ) 2 h 2 f ( − h ) − x 2 − h 2 h 2 f ( 0 ) + x ( x + h ) 2 h 2 f ( h ) , Q ′ ( 0 ) = f ( h ) − f ( − h ) 2 h Q(x) = \frac{x(x - h)}{2h^2}f(-h) - \frac{x^2 - h^2}{h^2}f(0) + \frac{x(x + h)}{2h^2}f(h), \qquad Q'(0) = \frac{f(h) - f(-h)}{2h} Q ( x ) = 2 h 2 x ( x − h ) f ( − h ) − h 2 x 2 − h 2 f ( 0 ) + 2 h 2 x ( x + h ) f ( h ) , Q ′ ( 0 ) = 2 h f ( h ) − f ( − h ) For the second derivative,
f ′ ′ ( 0 ) ≈ f ( − h ) − 2 f ( 0 ) + f ( h ) h 2 f''(0) \approx \frac{f(-h) - 2f(0) + f(h)}{h^2} f ′′ ( 0 ) ≈ h 2 f ( − h ) − 2 f ( 0 ) + f ( h ) Truncation error τ f ( h ) = f ′ ( 0 ) − 1 h ∑ k = − p q a k f ( k h ) \tau_f(h) = f'(0) - \frac{1}{h}\sum_{k=-p}^q a_k f(kh) τ f ( h ) = f ′ ( 0 ) − h 1 ∑ k = − p q a k f ( kh ) O ( h ) O(h) O ( h ) O ( h 2 ) O(h^2) O ( h 2 )
τ f ( h ) = f ′ ( 0 ) − 1 2 h [ ( f ( 0 ) + h f ′ ( 0 ) + 1 2 h 2 f ′ ′ ( 0 ) + 1 6 h 3 f ′ ′ ′ ( 0 ) + O ( h 4 ) ) − ( f ( 0 ) − h f ′ ( 0 ) + 1 2 h 2 f ′ ′ ( 0 ) − 1 6 h 3 f ′ ′ ′ ( 0 ) + O ( h 4 ) ) ] = − h 2 6 f ′ ′ ′ ( 0 ) + O ( h 3 ) \tau_f(h) = f'(0) - \frac{1}{2h}\Big[ \big(f(0) + hf'(0) + \tfrac{1}{2}h^2 f''(0) + \tfrac{1}{6}h^3 f'''(0) + O(h^4)\big) - \big(f(0) - hf'(0) + \tfrac{1}{2}h^2 f''(0) - \tfrac{1}{6}h^3 f'''(0) + O(h^4)\big) \Big] = -\frac{h^2}{6}f'''(0) + O(h^3) τ f ( h ) = f ′ ( 0 ) − 2 h 1 [ ( f ( 0 ) + h f ′ ( 0 ) + 2 1 h 2 f ′′ ( 0 ) + 6 1 h 3 f ′′′ ( 0 ) + O ( h 4 ) ) − ( f ( 0 ) − h f ′ ( 0 ) + 2 1 h 2 f ′′ ( 0 ) − 6 1 h 3 f ′′′ ( 0 ) + O ( h 4 ) ) ] = − 6 h 2 f ′′′ ( 0 ) + O ( h 3 ) Coefficient tables Centered, coefficients of f ( − 4 h ) , … , f ( − h ) f(-4h), \ldots, f(-h) f ( − 4 h ) , … , f ( − h ) a 0 = 0 a_0 = 0 a 0 = 0 a k = − a − k a_k = -a_{-k} a k = − a − k f ( 0 ) , … , f ( 4 h ) f(0), \ldots, f(4h) f ( 0 ) , … , f ( 4 h )
order − 4 h − 3 h − 2 h − h 2 − 1 2 4 1 12 − 2 3 6 − 1 60 3 20 − 3 4 8 1 280 − 4 105 1 5 − 4 5 order 0 h 2 h 3 h 4 h 1 − 1 1 2 − 3 2 2 − 1 2 3 − 11 6 3 − 3 2 1 3 4 − 25 12 4 − 3 4 3 − 1 4 \begin{array}{c|cccc}
\text{order} & -4h & -3h & -2h & -h \\
\hline
2 & & & & -\frac{1}{2} \\
4 & & & \frac{1}{12} & -\frac{2}{3} \\
6 & & -\frac{1}{60} & \frac{3}{20} & -\frac{3}{4} \\
8 & \frac{1}{280} & -\frac{4}{105} & \frac{1}{5} & -\frac{4}{5}
\end{array}
\qquad \qquad
\begin{array}{c|ccccc}
\text{order} & 0 & h & 2h & 3h & 4h \\
\hline
1 & -1 & 1 & & & \\
2 & -\frac{3}{2} & 2 & -\frac{1}{2} & & \\
3 & -\frac{11}{6} & 3 & -\frac{3}{2} & \frac{1}{3} & \\
4 & -\frac{25}{12} & 4 & -3 & \frac{4}{3} & -\frac{1}{4}
\end{array} order 2 4 6 8 − 4 h 280 1 − 3 h − 60 1 − 105 4 − 2 h 12 1 20 3 5 1 − h − 2 1 − 3 2 − 4 3 − 5 4 order 1 2 3 4 0 − 1 − 2 3 − 6 11 − 12 25 h 1 2 3 4 2 h − 2 1 − 2 3 − 3 3 h 3 1 3 4 4 h − 4 1 Backward formulas come from f ^ ( x ) = f ( − x ) \hat{f}(x) = f(-x) f ^ ( x ) = f ( − x )
f ′ ( 0 ) ≈ 1 h [ 1 12 f ( − 2 h ) − 2 3 f ( − h ) + 2 3 f ( h ) − 1 12 f ( 2 h ) ] , f ′ ( 0 ) ≈ 1 h [ 1 2 f ( − 2 h ) − 2 f ( − h ) + 3 2 f ( 0 ) ] f'(0) \approx \frac{1}{h}\Big[ \tfrac{1}{12}f(-2h) - \tfrac{2}{3}f(-h) + \tfrac{2}{3}f(h) - \tfrac{1}{12}f(2h) \Big], \qquad f'(0) \approx \frac{1}{h}\Big[ \tfrac{1}{2}f(-2h) - 2f(-h) + \tfrac{3}{2}f(0) \Big] f ′ ( 0 ) ≈ h 1 [ 12 1 f ( − 2 h ) − 3 2 f ( − h ) + 3 2 f ( h ) − 12 1 f ( 2 h ) ] , f ′ ( 0 ) ≈ h 1 [ 2 1 f ( − 2 h ) − 2 f ( − h ) + 2 3 f ( 0 ) ] Numerical Integration
I = ∫ a b f ( x ) d x ≈ Q = h ∑ i = 0 n w i f ( t i ) = h [ w 0 f ( t 0 ) + w 1 f ( t 1 ) + ⋯ + w n f ( t n ) ] I = \int_a^b f(x)\, dx \approx Q = h\sum_{i=0}^n w_i f(t_i) = h[w_0 f(t_0) + w_1 f(t_1) + \cdots + w_n f(t_n)] I = ∫ a b f ( x ) d x ≈ Q = h i = 0 ∑ n w i f ( t i ) = h [ w 0 f ( t 0 ) + w 1 f ( t 1 ) + ⋯ + w n f ( t n )] with weights w i w_i w i f f f piecewise linear interpolant ∑ i f ( t i ) H i ( x ) \sum_i f(t_i)H_i(x) ∑ i f ( t i ) H i ( x )
I ≈ ∫ a b ∑ i = 0 n f ( t i ) H i ( x ) d x = ∑ i = 0 n f ( t i ) ∫ a b H i ( x ) d x , w i = h − 1 ∫ a b H i ( x ) d x = { 1 i = 1 , … , n − 1 1 2 i = 0 , n I \approx \int_a^b \sum_{i=0}^n f(t_i)H_i(x)\, dx = \sum_{i=0}^n f(t_i) \int_a^b H_i(x)\, dx, \qquad w_i = h^{-1}\int_a^b H_i(x)\, dx = \begin{cases} 1 & i = 1, \ldots, n - 1 \\ \frac{1}{2} & i = 0, n \end{cases} I ≈ ∫ a b i = 0 ∑ n f ( t i ) H i ( x ) d x = i = 0 ∑ n f ( t i ) ∫ a b H i ( x ) d x , w i = h − 1 ∫ a b H i ( x ) d x = { 1 2 1 i = 1 , … , n − 1 i = 0 , n which is the trapezoid rule
T f ( n ) = h [ 1 2 f ( t 0 ) + f ( t 1 ) + f ( t 2 ) + ⋯ + f ( t n − 1 ) + 1 2 f ( t n ) ] T_f(n) = h\Big[ \tfrac{1}{2}f(t_0) + f(t_1) + f(t_2) + \cdots + f(t_{n-1}) + \tfrac{1}{2}f(t_n) \Big] T f ( n ) = h [ 2 1 f ( t 0 ) + f ( t 1 ) + f ( t 2 ) + ⋯ + f ( t n − 1 ) + 2 1 f ( t n ) ] Its error is bounded by the interpolant's,
∣ I − T f ( n ) ∣ = ∣ ∫ a b [ f ( x ) − p ( x ) ] d x ∣ ≤ ( b − a ) max x ∈ [ a , b ] ∣ f ( x ) − p ( x ) ∣ = O ( h 2 ) |I - T_f(n)| = \Big| \int_a^b [f(x) - p(x)]\, dx \Big| \le (b - a)\max_{x \in [a, b]} |f(x) - p(x)| = O(h^2) ∣ I − T f ( n ) ∣ = ∫ a b [ f ( x ) − p ( x )] d x ≤ ( b − a ) x ∈ [ a , b ] max ∣ f ( x ) − p ( x ) ∣ = O ( h 2 ) Euler-Maclaurin
I = T f ( n ) − h 2 12 [ f ′ ( b ) − f ′ ( a ) ] + h 4 720 [ f ′ ′ ′ ( b ) − f ′ ′ ′ ( a ) ] + O ( h 6 ) = T f ( n ) − ∑ k = 1 ∞ B 2 k h 2 k ( 2 k ) ! [ f ( 2 k − 1 ) ( b ) − f ( 2 k − 1 ) ( a ) ] I = T_f(n) - \frac{h^2}{12}[f'(b) - f'(a)] + \frac{h^4}{720}[f'''(b) - f'''(a)] + O(h^6) = T_f(n) - \sum_{k=1}^\infty \frac{B_{2k}h^{2k}}{(2k)!}\big[f^{(2k-1)}(b) - f^{(2k-1)}(a)\big] I = T f ( n ) − 12 h 2 [ f ′ ( b ) − f ′ ( a )] + 720 h 4 [ f ′′′ ( b ) − f ′′′ ( a )] + O ( h 6 ) = T f ( n ) − k = 1 ∑ ∞ ( 2 k )! B 2 k h 2 k [ f ( 2 k − 1 ) ( b ) − f ( 2 k − 1 ) ( a ) ] with B 2 k B_{2k} B 2 k f ′ ( b ) = f ′ ( a ) f'(b) = f'(a) f ′ ( b ) = f ′ ( a )
Extrapolation
If A 0 = A ( h ) + c 1 h + c 2 h 2 + c 3 h 3 + ⋯ A_0 = A(h) + c_1 h + c_2 h^2 + c_3 h^3 + \cdots A 0 = A ( h ) + c 1 h + c 2 h 2 + c 3 h 3 + ⋯ A ( h ) A(h) A ( h ) h h h n n n
I = T f ( n ) + c 2 n − 2 + c 4 n − 4 + ⋯ = T f ( 2 n ) + 1 4 c 2 n − 2 + 1 16 c 4 n − 4 + ⋯ I = T_f(n) + c_2 n^{-2} + c_4 n^{-4} + \cdots = T_f(2n) + \tfrac{1}{4}c_2 n^{-2} + \tfrac{1}{16}c_4 n^{-4} + \cdots I = T f ( n ) + c 2 n − 2 + c 4 n − 4 + ⋯ = T f ( 2 n ) + 4 1 c 2 n − 2 + 16 1 c 4 n − 4 + ⋯ and eliminating the n − 2 n^{-2} n − 2
S f ( 2 n ) = 1 3 [ 4 T f ( 2 n ) − T f ( n ) ] , I = S f ( 2 n ) + O ( n − 4 ) = S f ( 2 n ) + b 4 n − 4 + b 6 n − 6 + ⋯ S_f(2n) = \frac{1}{3}[4T_f(2n) - T_f(n)], \qquad I = S_f(2n) + O(n^{-4}) = S_f(2n) + b_4 n^{-4} + b_6 n^{-6} + \cdots S f ( 2 n ) = 3 1 [ 4 T f ( 2 n ) − T f ( n )] , I = S f ( 2 n ) + O ( n − 4 ) = S f ( 2 n ) + b 4 n − 4 + b 6 n − 6 + ⋯ which is Simpson's rule, 4th order. Repeating with I = S f ( 4 n ) + 1 16 b 4 n − 4 + 1 64 b 6 n − 6 + ⋯ I = S_f(4n) + \frac{1}{16}b_4 n^{-4} + \frac{1}{64}b_6 n^{-6} + \cdots I = S f ( 4 n ) + 16 1 b 4 n − 4 + 64 1 b 6 n − 6 + ⋯
R f ( 4 n ) = 1 15 [ 16 S f ( 4 n ) − S f ( 2 n ) ] R_f(4n) = \frac{1}{15}[16S_f(4n) - S_f(2n)] R f ( 4 n ) = 15 1 [ 16 S f ( 4 n ) − S f ( 2 n )] is 6th order.