Numerical Analysis

UPSC Mathematics Optional · Paper II · Methods, Errors & Formulae

1. Errors & Approximation 2. Root Finding Methods 3. Finite Differences 4. Interpolation 5. Numerical Differentiation 6. Numerical Integration 7. Numerical Solution of ODEs 8. Linear Systems — Iterative Methods

§1 · Errors & Approximation

Types of Errors PYQ★★

Absolute error: \(|x-\tilde x|\)
Relative error: \(|x-\tilde x|/|x|\)
Percentage error: relative \(\times 100\)
Truncation error: from approximating infinite process (series truncation).
Round-off error: from finite precision arithmetic.

Significant figures: digits certain plus one estimated digit.

§2 · Root Finding Methods

Bisection Method

If \(f(a)f(b)<0\): root in \([a,b]\). Repeatedly bisect. Error after \(n\) steps: \(\dfrac{b-a}{2^{n+1}}\). Linear convergence.

Newton-Raphson Method PYQ★★★

\[x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\]

Quadratic convergence (order 2) near simple roots. Fails if \(f'(x_n)=0\).

Error: \(e_{n+1}\approx\dfrac{f''(\alpha)}{2f'(\alpha)}e_n^2\) where \(\alpha\) is the root.

Secant Method & Regula Falsi

Secant: \(x_{n+1}=x_n-f(x_n)\dfrac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}\). Order \(\approx 1.618\).

Regula Falsi: Like secant but always keep bracket (slower, always converges).

Fixed Point Iteration \(x=g(x)\)

Converges if \(|g'(x)|<1\) near root. Order of convergence = order of first non-zero derivative of \(g-x\).

§3 · Finite Differences

Difference Operators PYQ★★★

Forward: \(\Delta f_i=f_{i+1}-f_i\), \(\Delta^n f_i=\sum_{k=0}^n(-1)^k\binom{n}{k}f_{i+n-k}\)
Backward: \(\nabla f_i=f_i-f_{i-1}\)
Central: \(\delta f_i=f_{i+1/2}-f_{i-1/2}\)
Shift: \(E f_i=f_{i+1}\), \(E=1+\Delta\), \(\Delta=E-1\)
Averaging: \(\mu f_i=\tfrac{1}{2}(f_{i+1/2}+f_{i-1/2})\)

\(D=\dfrac{1}{h}\ln E=\dfrac{1}{h}\ln(1+\Delta)\) (differential operator in terms of \(\Delta\)).

§4 · Interpolation

Newton's Forward Difference Formula PYQ★★★

For equally spaced \(x_0,x_1=x_0+h,\ldots\), point \(x=x_0+ph\):

\[f(x)=f_0+p\Delta f_0+\frac{p(p-1)}{2!}\Delta^2 f_0+\frac{p(p-1)(p-2)}{3!}\Delta^3 f_0+\cdots\]

Use near the beginning of the table.

Newton's Backward Difference Formula PYQ★★★

For \(x=x_n+ph\) (usually \(p\in[-1,0]\)):

\[f(x)=f_n+p\nabla f_n+\frac{p(p+1)}{2!}\nabla^2 f_n+\frac{p(p+1)(p+2)}{3!}\nabla^3 f_n+\cdots\]

Use near the end of the table.

Lagrange Interpolation Formula PYQ★★★

For unevenly spaced points \(x_0,x_1,\ldots,x_n\):

\[f(x)=\sum_{i=0}^n f_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\]

Error: \(\dfrac{(x-x_0)\cdots(x-x_n)}{(n+1)!}f^{(n+1)}(\xi)\) for some \(\xi\).

Newton's Divided Difference Formula

\(f(x)=f[x_0]+(x-x_0)f[x_0,x_1]+(x-x_0)(x-x_1)f[x_0,x_1,x_2]+\cdots\)

Divided difference: \(f[x_i,x_j]=\dfrac{f[x_j]-f[x_i]}{x_j-x_i}\), recursively.

Stirling & Bessel Central Difference Formulae PYQ★★

Used near the middle of the table. More accurate than forward/backward for mid-range.

Stirling: \(f(x_0+ph)\approx f_0+p\mu\delta f_0+\dfrac{p^2}{2!}\delta^2 f_0+\dfrac{p(p^2-1)}{3!}\mu\delta^3 f_0+\cdots\)

§5 · Numerical Differentiation

Derivative Formulae PYQ★★

Using forward differences at \(x_0\) (step \(h\)):

\[f'(x_0)=\frac{1}{h}\left[\Delta f_0-\frac{\Delta^2 f_0}{2}+\frac{\Delta^3 f_0}{3}-\cdots\right]\]

\[f''(x_0)=\frac{1}{h^2}\left[\Delta^2 f_0-\Delta^3 f_0+\frac{11}{12}\Delta^4 f_0-\cdots\right]\]

Central difference (more accurate): \(f'(x_0)\approx\dfrac{f_1-f_{-1}}{2h}\). \(f''(x_0)\approx\dfrac{f_1-2f_0+f_{-1}}{h^2}\).

§6 · Numerical Integration

Newton-Cotes Formulae PYQ★★★

Trapezoidal Rule: \(\displaystyle\int_{x_0}^{x_n}f\,dx\approx\frac{h}{2}[f_0+2(f_1+\cdots+f_{n-1})+f_n]\). Error: \(O(h^2)\).

Simpson's \(\frac{1}{3}\) Rule (\(n\) even): \(\displaystyle\int\approx\frac{h}{3}[f_0+4f_1+2f_2+4f_3+\cdots+4f_{n-1}+f_n]\). Error: \(O(h^4)\).

Simpson's \(\frac{3}{8}\) Rule (\(n\) multiple of 3): \(\displaystyle\int\approx\frac{3h}{8}[f_0+3f_1+3f_2+2f_3+3f_4+\cdots+f_n]\). Error: \(O(h^4)\).

Weddle's Rule (6 intervals): \(\displaystyle\int_{x_0}^{x_6}\approx\frac{3h}{10}[f_0+5f_1+f_2+6f_3+f_4+5f_5+f_6]\).

Gaussian Quadrature: \(\displaystyle\int_{-1}^1 f(x)\,dx\approx\sum_i w_i f(x_i)\). More accurate for same number of function evaluations.

§7 · Numerical Solution of ODEs

Euler's Method PYQ★★★

For \(y'=f(x,y)\), \(y(x_0)=y_0\): \(y_{n+1}=y_n+hf(x_n,y_n)\). Error \(O(h)\). Low accuracy.

Modified Euler (Heun): Predictor: \(y^*=y_n+hf_n\). Corrector: \(y_{n+1}=y_n+\dfrac{h}{2}[f_n+f(x_{n+1},y^*)]\). Error \(O(h^2)\).

Runge-Kutta 4th Order (RK4) PYQ★★★

\[k_1=hf(x_n,y_n),\quad k_2=hf\!\left(x_n+\tfrac{h}{2},y_n+\tfrac{k_1}{2}\right)\]

\[k_3=hf\!\left(x_n+\tfrac{h}{2},y_n+\tfrac{k_2}{2}\right),\quad k_4=hf(x_n+h,y_n+k_3)\]

\[y_{n+1}=y_n+\frac{1}{6}(k_1+2k_2+2k_3+k_4)\]

Error \(O(h^4)\). Gold standard for hand calculations.

Milne's Predictor-Corrector PYQ★★

Predictor: \(y_{n+1}^p=y_{n-3}+\dfrac{4h}{3}(2f_n-f_{n-1}+2f_{n-2})\)

Corrector: \(y_{n+1}=y_{n-1}+\dfrac{h}{3}(f_{n+1}^p+4f_n+f_{n-1})\)

Needs 4 starting values (use RK4 to start).

§8 · Linear Systems — Iterative Methods

Gauss-Seidel Method PYQ★★★

For \(a_{11}x_1+a_{12}x_2+a_{13}x_3=b_1\), etc.: update each \(x_i\) using the latest values of other variables.

\[x_i^{(k+1)}=\frac{1}{a_{ii}}\left(b_i-\sum_{ji}a_{ij}x_j^{(k)}\right)\]

Converges if matrix is strictly diagonally dominant (\(|a_{ii}|>\sum_{j\ne i}|a_{ij}|\)).

Gauss-Seidel converges faster than Jacobi (uses updated values immediately).

Gauss Elimination & LU Decomposition

Forward elimination → upper triangular → back substitution. \(O(n^3/3)\) operations.

LU: \(A=LU\) where \(L\) = lower triangular (1's on diagonal), \(U\) = upper triangular. Solve \(L\mathbf{y}=\mathbf{b}\), then \(U\mathbf{x}=\mathbf{y}\).

Cholesky: For symmetric positive definite: \(A=LL^T\). Saves half the work.