Root Finding Formulas
Bisection Method
Bracketing (Slow)
$$x_{new} = \frac{a + b}{2}$$
Logic: If \(f(a) \cdot f(x_{new}) < 0\), replace \(b\). Else replace \(a\).
Regula Falsi Method
Bracketing (Faster)
$$x_{new} = \frac{a f(b) – b f(a)}{f(b) – f(a)}$$
Logic: Same update rule as Bisection. Always brackets the root.
Secant Method
Open (Fast)
$$x_{n+1} = x_n – \frac{x_n – x_{n-1}}{f(x_n) – f(x_{n-1})} \cdot f(x_n)$$
Logic: Needs 2 initial guesses. Does not check signs.
Newton-Raphson
Open (Fastest)
$$x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)}$$
Logic: Needs derivative \(f'(x)\). Converges quadratically.
Interpolation & Error Analysis
Error Analysis
Error Term: The error \( E(x) \) is defined as:
$$ E(x) = \frac{\Pi(x)}{(n+1)!} f^{(n+1)}(\xi) $$
Error Bound: To find the maximum error:
$$ |E(x)| \le \frac{1}{(n+1)!} \max |\Pi(x)| \cdot \max |f^{(n+1)}(x)| $$
Where \( \Pi(x) = (x-x_0)(x-x_1)…(x-x_n) \).
Key Formulas
1. Newton’s General Divided Difference
For unequal intervals
$$ f(x) = f(x_0) + (x-x_0)f[x_0, x_1] + \dots $$
2. Lagrange’s Interpolation
For unequal intervals; no table required
$$ P_n(x) = \sum_{i=0}^{n} L_i(x) f(x_i) $$
3. Newton’s Forward Difference
For equal intervals (start of table). Let \( u = \frac{x – x_0}{h} \).
$$ y(x) = y_0 + u \Delta y_0 + \frac{u(u-1)}{2!} \Delta^2 y_0 + \dots $$
4. Newton’s Backward Difference
For equal intervals (end of table). Let \( u = \frac{x – x_n}{h} \).
$$ y(x) = y_n + u \nabla y_n + \frac{u(u+1)}{2!} \nabla^2 y_n + \dots $$
Integration Formulas & Errors
Composite Trapezoidal
O(h²) Error
$$I \approx \frac{h}{2} \left[ (y_0 + y_n) + 2(y_1 + \dots + y_{n-1}) \right]$$
Error Bound:
$$ |E_T| \le \frac{b-a}{12} h^2 \max |f”(x)| $$
Simpson’s 1/3 Rule
Even N | O(h⁴) Error
$$I \approx \frac{h}{3} \left[ (y_0 + y_n) + 4(\Sigma \text{Odd}) + 2(\Sigma \text{Even}) \right]$$
Error Bound:
$$ |E_{1/3}| \le \frac{b-a}{180} h^4 \max |f^{(4)}(x)| $$
Simpson’s 3/8 Rule
Multiple of 3 | O(h⁴)
$$I \approx \frac{3h}{8} \left[ (y_0 + y_n) + 3(\text{Others}) + 2(\text{Mult. of 3}) \right]$$
Error Bound:
$$ |E_{3/8}| \le \frac{b-a}{80} h^4 \max |f^{(4)}(x)| $$
Gauss Legendre
Transformation
1. Transform to \( t \in [-1, 1] \): \( x = \frac{b-a}{2}t + \frac{b+a}{2} \)
2. Apply: \( I \approx \frac{b-a}{2} \sum w_i f(x(t_i)) \)
2. Apply: \( I \approx \frac{b-a}{2} \sum w_i f(x(t_i)) \)
n=2 Points: \( t=\pm 0.577, w=1 \)
n=3 Points: \( t=0, w=8/9 \); \( t=\pm 0.774, w=5/9 \)
ODE Solving Formulas
Euler’s Method
Order 1
$$y_{n+1} = y_n + h \cdot f(x_n, y_n)$$
Local Truncation Error: \( |lte| \le \frac{h^2}{2} \max |y”(t)| \)
Global Error: \( O(h) \)
Global Error: \( O(h) \)
Modified Euler (Midpoint)
RK Order 2
$$k_1 = h f(x_n, y_n)$$
$$k_2 = h f(x_n + \frac{h}{2}, y_n + \frac{k_1}{2})$$
$$y_{n+1} = y_n + k_2$$
Heun’s Method (Improved)
RK Order 2
$$k_1 = h f(x_n, y_n)$$
$$k_2 = h f(x_n + h, y_n + k_1)$$
$$y_{n+1} = y_n + \frac{1}{2}(k_1 + k_2)$$
Runge-Kutta Method
RK Order 4
$$k_1 = h f(x_n, y_n)$$
$$k_2 = h f(x_n + \frac{h}{2}, y_n + \frac{k_1}{2})$$
$$k_3 = h f(x_n + \frac{h}{2}, y_n + \frac{k_2}{2})$$
$$k_4 = h f(x_n + h, y_n + k_3)$$
$$y_{n+1} = y_n + \frac{1}{6}(k_1 + 2k_2 + 2k_3 + k_4)$$