## Trapezoidal Rule Approximates the integral of a function by summing up areas of trapezoids. - Implicit, because $u^{n+1}$ appears on both sides - Second-order accurate in time Given an ODE: $\frac{du}{dt}=f(t,u)$ The trapezoidal rule updates the solution as: $u^{n+1}=u^n+\frac{\Delta t}{2}\left[f(t^n,u^n)+f(t^{n+1},u^{n+1})\right]$ **Single interval:** $\int_a^b f(x) \, dx \approx \frac{h}{2} \left[ f(a) + f(b) \right]$ **Composite trapezoidal rule:** - $n$: number of subintervals - $h = \frac{b - a}{n}$ - $x_i = a + i h$ $\int_a^b f(x)\, dx \approx \frac{h}{2} \left[ f(x_0) + 2 \sum_{i=1}^{n-1} f(x_i) + f(x_n) \right]$ Accuracy: $\mathcal{O}(h^2)$, improves with smaller $h$ (finer grid) ## Romberg Integration Improves the accuracy of the trapezoidal rule using **Richardson extrapolation**. - Trapezoidal rule: error $\mathcal{O}(h^2)$ - Romberg integration: applies Richardson recursively for $\mathcal{O}(h^4)$, $\mathcal{O}(h^6)$, etc. - Efficient for **smooth** functions when high accuracy is needed 1. Compute trapezoidal estimates with step sizes $h$, $h/2$, $h/4$, etc. 2. Extrapolate to cancel $\mathcal{O}(h^2)$, $\mathcal{O}(h^4)$ errors and so on. Let $R_{i,0}$ be the trapezoidal estimate using $2^i$ intervals. $R_{i,j} = \frac{4^j R_{i,j-1} - R_{i-1,j-1}}{4^j - 1}$ Each $j$ increases the order of accuracy by 2. **Romberg table structure:** | $i \backslash j$ | 0 (trapezoid) | 1 (Rich. 1) | 2 (Rich. 2) | |------------------|---------------|-------------|-------------| | 0 | $R_{0,0}$ | | | | 1 | $R_{1,0}$ | $R_{1,1}$ | | | 2 | $R_{2,0}$ | $R_{2,1}$ | $R_{2,2}$ | **Stopping criterion:** $|R_{i,j} - R_{i,j-1}| < \text{tolerance}$ ## Crank-Nicolson Time integration scheme that is the trapezoidal rule applied to spacially discretized PDEs. - implicit - 2nd order accurate in time Example: 1D diffusion equation: $\frac{\partial u}{\partial t}=\kappa\frac{\partial^2 u}{\partial x^2}$ Discretize space (e.g., finite differences), yielding: $\frac{du}{dt}=\kappa D u$ Apply the trapezoidal rule: $u^{n+1}=u^n+\frac{\Delta t}{2}\kappa\left(Du^n+Du^{n+1}\right)$ Rearranged into matrix form: $\left(I-\frac{\Delta t}{2}\kappa D\right)u^{n+1}=\left(I+\frac{\Delta t}{2}\kappa D\right)u^n$ ## ADI Schemes An Alternating Direction Implicit method is a time-stepping scheme that is: - Implicit in time (unconditionally stable) - Often second-order accurate in time - Only tridiagonal (1D) solves required per step - Great for 2D heat/diffusion problems $\frac{\partial u}{\partial t} = \kappa\left(\frac{\partial^2 u}{\partial x^2} + \frac{\partial^2 u}{\partial y^2}\right)$ A full time step is split into two half steps: 1. First half-step (implicit in $x$, explicit in $y$): $u^* = u^n + \frac{\Delta t}{2}\kappa\left(\frac{\partial^2 u^*}{\partial x^2} + \frac{\partial^2 u^n}{\partial y^2}\right)$ 2. Second half-step (implicit in $y$, explicit in $x$): $u^{n+1} = u^* + \frac{\Delta t}{2}\kappa\left(\frac{\partial^2 u^*}{\partial x^2} + \frac{\partial^2 u^{n+1}}{\partial y^2}\right)$ Each step only requires solving a 1D tridiagonal system — much cheaper than solving a full 2D system. ## Initial Value Problems After discretizing the spatial derivatives we obtain a (coupled) system of (nonlinear) ODEs for IVPs, developed with a single equations similar methods to solving steady problems by iterations linear diff eq's can be solved analytically non-linear equations require numerical solutions Forward difference is bad because truncation error is always the same sign ### Numerical IVP Solving Given: $\frac{dy}{dt} = f(t, y), \quad y(t_0) = y_0$ Use Taylor expansion to step forward: $y(t+h) = y(t) + h f(t, y) + \frac{h^2}{2} f_t + \cdots$ Where $f_t = \frac{d}{dt} f(t, y) = \frac{\partial f}{\partial t} + \frac{\partial f}{\partial y} \cdot f$ #### First-Order (Euler) $y_{n+1} = y_n + h f(t_n, y_n)$ - Truncates after 1st term - Local truncation error: $\mathcal{O}(h^2)$ - Global error: $\mathcal{O}(h)$ #### Second-Order Taylor $y_{n+1} = y_n + h f(t_n, y_n) + \frac{h^2}{2} f_t(t_n, y_n)$ - More accurate but needs derivative of $f$