Numerical Analysis

Root finding, interpolation, numerical integration, numerical ODE methods, and iterative linear solvers for GATE preparation with error analysis throughout.

Root Finding Interpolation Numerical Integration Numerical ODE Linear Systems

0 / 5 units completed0%

Root Finding Methods

Numerical methods for solving \(f(x) = 0\). We study convergence rates and conditions under which each method is applicable.

◆ Bisection Method

Algorithm Given \(f(a)f(b) < 0\) (with \(f\) continuous), repeatedly bisect \([a,b]\) and select the subinterval containing the root. After \(n\) steps, the error satisfies: \[|e_n| \le \frac{b - a}{2^n}\]

The bisection method has linear convergence with rate \(r = 1\). It always converges but is relatively slow.

◆ Newton-Raphson Method

Newton’s Iteration \[x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\] If \(f'(x^*) \ne 0\) and \(x_0\) is sufficiently close to the root \(x^*\), then Newton's method converges quadratically: \[|e_{n+1}| \approx \frac{|f''(x^*)|}{2|f'(x^*)|}\,|e_n|^2\]

★ Example

Use Newton's method to find \(\sqrt{2}\) starting from \(x_0 = 1\). Take \(f(x) = x^2 - 2\).

\(f'(x) = 2x\). The iteration is \(x_{n+1} = x_n - \frac{x_n^2 - 2}{2x_n} = \frac{x_n + 2/x_n}{2}\).
\(x_0 = 1\), \(x_1 = 1.5\), \(x_2 = 1.41\overline{6}\), \(x_3 = 1.414215686\ldots\)
Rapid quadratic convergence to \(\sqrt{2} \approx 1.41421356\ldots\)

◆ Secant Method

Secant Iteration \[x_{n+1} = x_n - f(x_n)\,\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}\] The secant method has superlinear convergence with order \(\phi = \frac{1+\sqrt{5}}{2} \approx 1.618\) (the golden ratio). It requires two initial guesses but avoids computing the derivative.

Interpolation

Constructing polynomials that pass through given data points. Key formulations include Lagrange, Newton, and spline interpolation.

◆ Lagrange Interpolation

Lagrange Interpolating Polynomial Given \(n+1\) data points \((x_0,y_0),\ldots,(x_n,y_n)\), the interpolating polynomial is: \[P_n(x) = \sum_{i=0}^{n} y_i \prod_{\substack{j=0\\j\ne i}}^{n} \frac{x - x_j}{x_i - x_j}\]

Interpolation Error If \(f \in C^{n+1}[a,b]\), then: \[f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^{n}(x - x_i)\] for some \(\xi\) between the smallest and largest of \(x, x_0, \ldots, x_n\).

◆ Newton’s Divided Differences

Newton’s Form \[P_n(x) = f[x_0] + f[x_0,x_1](x-x_0) + f[x_0,x_1,x_2](x-x_0)(x-x_1) + \cdots\] where the divided differences are defined recursively: \[f[x_i,\ldots,x_{i+k}] = \frac{f[x_{i+1},\ldots,x_{i+k}] - f[x_i,\ldots,x_{i+k-1}]}{x_{i+k} - x_i}\]

★ Example

Find the interpolating polynomial for the data: \((1,1)\), \((2,8)\), \((3,27)\).

\(f[x_0] = 1\), \(f[x_0,x_1] = \frac{8-1}{2-1} = 7\), \(f[x_1,x_2] = \frac{27-8}{3-2} = 19\), \(f[x_0,x_1,x_2] = \frac{19-7}{3-1} = 6\).
\(P_2(x) = 1 + 7(x-1) + 6(x-1)(x-2) = 6x^2 - 11x + 6\).
Note: these are values of \(x^3\), and indeed \(x^3 \ne 6x^2 - 11x + 6\), but the quadratic interpolant matches at the three given points.

◆ Spline Interpolation

Cubic Spline A cubic spline \(S(x)\) through \(n+1\) points satisfies:

\(S(x)\) is a cubic polynomial on each subinterval \([x_i, x_{i+1}]\)
\(S\), \(S'\), and \(S''\) are continuous on \([x_0, x_n]\)
\(S(x_i) = y_i\) at each data point

Natural spline boundary conditions: \(S''(x_0) = S''(x_n) = 0\). The error for a natural cubic spline is \(O(h^4)\) where \(h\) is the maximum spacing.

Numerical Integration

Quadrature rules for approximating definite integrals, with error bounds and convergence analysis.

◆ Trapezoidal & Simpson’s Rules

Composite Trapezoidal Rule \[\int_a^b f(x)\,dx \approx \frac{h}{2}\left[f(a) + 2\sum_{i=1}^{n-1}f(x_i) + f(b)\right]\] Error: \(-\frac{(b-a)h^2}{12}f''(\xi)\) for some \(\xi \in [a,b]\), i.e., \(O(h^2)\).

Composite Simpson’s Rule (n even) \[\int_a^b f(x)\,dx \approx \frac{h}{3}\left[f(a) + 4\sum_{\text{odd }i}f(x_i) + 2\sum_{\text{even }i}f(x_i) + f(b)\right]\] Error: \(-\frac{(b-a)h^4}{180}f^{(4)}(\xi)\), i.e., \(O(h^4)\).

★ Example

Approximate \(\int_0^1 e^x\,dx\) using the trapezoidal rule with \(n=2\).

\(h = 0.5\), nodes: \(0, 0.5, 1\).
\(T = \frac{0.5}{2}[e^0 + 2e^{0.5} + e^1] = 0.25[1 + 2(1.6487) + 2.7183] = 0.25 \times 7.0157 = 1.7539\).
Exact value: \(e - 1 \approx 1.7183\). Error \(\approx 0.0356\).

◆ Gaussian Quadrature

Gaussian Quadrature \[\int_{-1}^{1} f(x)\,dx \approx \sum_{i=1}^{n} w_i\,f(x_i)\] where nodes \(x_i\) are roots of the Legendre polynomial \(P_n(x)\), and weights \(w_i\) are chosen so the rule is exact for polynomials of degree \(\le 2n-1\).

For 2-point Gauss-Legendre: \(x_{1,2} = \pm\frac{1}{\sqrt{3}}\), \(w_{1,2} = 1\). This is exact for all cubics.

Numerical Methods for ODEs

One-step and multi-step methods for solving initial value problems \(y' = f(t,y)\), \(y(t_0) = y_0\).

◆ Euler’s Method & Improved Euler

Forward Euler Method \[y_{n+1} = y_n + h\,f(t_n, y_n)\] This is a first-order method: local truncation error is \(O(h^2)\), global error is \(O(h)\).

Modified Euler (Heun’s Method) \[\tilde{y}_{n+1} = y_n + h\,f(t_n,y_n)\] \[y_{n+1} = y_n + \frac{h}{2}\bigl[f(t_n,y_n) + f(t_{n+1},\tilde{y}_{n+1})\bigr]\] This is a second-order method with global error \(O(h^2)\).

◆ Runge-Kutta Methods

Classical 4th-Order Runge-Kutta (RK4) \[y_{n+1} = y_n + \frac{h}{6}(k_1 + 2k_2 + 2k_3 + k_4)\] where: \[k_1 = f(t_n, y_n),\quad k_2 = f\!\left(t_n+\tfrac{h}{2},\, y_n+\tfrac{h}{2}k_1\right)\] \[k_3 = f\!\left(t_n+\tfrac{h}{2},\, y_n+\tfrac{h}{2}k_2\right),\quad k_4 = f(t_n+h,\, y_n+hk_3)\] Global error: \(O(h^4)\). RK4 is the most widely used single-step method.

★ Example

Solve \(y' = y\), \(y(0)=1\) using Euler's method with \(h=0.1\) for one step.

\(y_1 = y_0 + h\,f(0,1) = 1 + 0.1(1) = 1.1\).
Exact: \(y(0.1) = e^{0.1} \approx 1.10517\). Error \(\approx 0.00517\).

◆ Multi-Step Methods

Adams-Bashforth (Explicit, 2-step) \[y_{n+1} = y_n + \frac{h}{2}\bigl[3f(t_n,y_n) - f(t_{n-1},y_{n-1})\bigr]\]

Adams-Moulton (implicit) methods use future values and are more accurate but require solving an equation at each step. Predictor-corrector pairs combine both.

Numerical Linear Algebra

Direct and iterative methods for solving linear systems \(Ax = b\).

◆ LU Decomposition

LU Factorization Factor \(A = LU\) where \(L\) is lower triangular (with 1s on diagonal) and \(U\) is upper triangular. Then solve \(Ly = b\) (forward substitution) and \(Ux = y\) (back substitution). Cost: \(\frac{2n^3}{3}\) flops for factorization.

◆ Iterative Methods: Jacobi & Gauss-Seidel

Jacobi Iteration Decompose \(A = D + L + U\) (diagonal, strict lower, strict upper). Then: \[x^{(k+1)} = D^{-1}(b - (L+U)x^{(k)})\] Component form: \(x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{j\ne i} a_{ij}x_j^{(k)}\right)\)

Gauss-Seidel Iteration Uses the most recently computed values: \[x_i^{(k+1)} = \frac{1}{a_{ii}}\left(b_i - \sum_{ji} a_{ij}x_j^{(k)}\right)\]

Convergence Criterion Both methods converge if \(A\) is strictly diagonally dominant: \(|a_{ii}| > \sum_{j\ne i}|a_{ij}|\) for all \(i\). More generally, convergence requires the spectral radius of the iteration matrix to be less than 1.

★ Example

Apply one Jacobi iteration to \(\begin{pmatrix}4&1\\1&3\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}=\begin{pmatrix}1\\2\end{pmatrix}\), starting from \(x^{(0)}=(0,0)^T\).

\(x_1^{(1)} = \frac{1}{4}(1 - 1\cdot 0) = 0.25\), \(x_2^{(1)} = \frac{1}{3}(2 - 1\cdot 0) = 0.667\).
So \(x^{(1)} = (0.25, 0.667)^T\).

★ Key Takeaways

Newton-Raphson converges quadratically; bisection is guaranteed but only linearly convergent.
Lagrange interpolation error depends on \(f^{(n+1)}\) and the product \(\prod(x - x_i)\).
Simpson's rule is \(O(h^4)\), two orders better than the trapezoidal rule's \(O(h^2)\).
RK4 gives \(O(h^4)\) accuracy for ODEs with only 4 function evaluations per step.
Diagonal dominance guarantees convergence of both Jacobi and Gauss-Seidel iterations.

📝 Practice Problems

Problem 1

How many bisection iterations are needed to find a root in \([1,2]\) accurate to \(10^{-6}\)?

Show Solution ▼

We need \(\frac{1}{2^n} < 10^{-6}\), so \(2^n > 10^6\), giving \(n > 6\log_2 10 \approx 19.93\). Thus 20 iterations suffice.

Problem 2

Find the Newton iteration formula for \(f(x) = x^3 - 2\) and compute \(x_1\) starting from \(x_0 = 1\).

Show Solution ▼

\(x_{n+1} = x_n - \frac{x_n^3 - 2}{3x_n^2} = \frac{2x_n^3 + 2}{3x_n^2}\). With \(x_0 = 1\): \(x_1 = \frac{2+2}{3} = \frac{4}{3} \approx 1.3333\). The root is \(\sqrt[3]{2} \approx 1.2599\).

Problem 3

Use Simpson's rule (\(n=2\)) to approximate \(\int_0^{\pi} \sin x\,dx\).

Show Solution ▼

\(h = \pi/2\). \(S = \frac{h}{3}[f(0) + 4f(\pi/2) + f(\pi)] = \frac{\pi/2}{3}[0 + 4(1) + 0] = \frac{2\pi}{3} \approx 2.0944\). Exact value is 2. Error \(\approx 0.0944\).

Problem 4

What is the order of accuracy of 2-point Gaussian quadrature?

Show Solution ▼

2-point Gaussian quadrature is exact for polynomials of degree \(\le 2(2)-1 = 3\). It has order of accuracy 4 (it integrates cubics exactly).

Problem 5

Is the matrix \(A = \begin{pmatrix}5&1&1\\1&4&1\\2&1&6\end{pmatrix}\) strictly diagonally dominant?

Show Solution ▼

Row 1: \(|5| > |1|+|1| = 2\). Row 2: \(|4| > |1|+|1| = 2\). Row 3: \(|6| > |2|+|1| = 3\). Yes, \(A\) is strictly diagonally dominant, so Jacobi and Gauss-Seidel both converge.

🎯 Interactive Quiz

1. The order of convergence of Newton-Raphson method (for a simple root) is:

A 1 (linear)

B 2 (quadratic)

C 3 (cubic)

D 1.618 (superlinear)

2. The error in the composite trapezoidal rule with step size \(h\) is of order:

A \(O(h)\)

B \(O(h^2)\)

C \(O(h^3)\)

D \(O(h^4)\)

3. In the classical RK4 method, how many function evaluations per step are required?

A 2

B 3

C 4

D 5

4. A natural cubic spline on \(n+1\) points has the boundary condition:

A \(S'(x_0) = S'(x_n) = 0\)

B \(S''(x_0) = S''(x_n) = 0\)

C \(S(x_0) = S(x_n)\)

D \(S'(x_0) = a,\; S'(x_n) = b\)

5. Gauss-Seidel differs from Jacobi iteration in that it:

A Uses updated values as soon as they are computed

B Ignores the diagonal of \(A\)

C Solves the system in one step

D Always converges regardless of the matrix