Introduction to Numerical Methods and Error Analysis

Introduction to Numerical Methods

• Numerical methods are algorithms and techniques designed to solve mathematical problems numerically (using basic arithmetic operations) instead of symbolically (using exact formulas).

• These methods provide approximate solutions to problems that lack analytical solutions or are otherwise impractical to solve via exact formulas.

• The Key Idea: Replace a complex, continuous problem with a sequence of simple arithmetic operations ($+$, $-$, $\times$, $\div$) that a computer is capable of performing billions of times per second.

Analytical vs. Numerical Solutions

• Analytical Solutions (Exact): These involve finding a closed-form formula.

  • Example: For the quadratic equation $x^2 - 5x + 6 = 0$, the exact solution is calculated as:       $x = \frac{5 \pm \sqrt{25 - 24}}{2} = 2, 3$

• Numerical Solutions (Approximate): No formula exists, leading to iterative processes.

  • Example: For the equation $x = \cos(x)$, one uses iteration: $x_{n+1} = \cos(x_n)$, which converges to $x \approx 0.739085$.

  • Abel–Ruffini Theorem: This theorem states that general polynomials of degree $\ge 5$ have no closed-form solution by radicals; therefore, numerical root-finding is the only general choice available.

The Numerical Problem-Solving Workflow

1. Physical Problem: Identify the real-world scenario (e.g., heat flow in a metal rod).

2. Mathematical Model: Establish differential or algebraic equations representing the physical system (introduces modeling error).

3. Numerical Method: Discretize and approximate the model (introduces truncation error).

4. Computer Implementation: Use finite-precision arithmetic (introduces round-off error).

5. Result + Error Analysis: Determine the reliability of the derived answer. Error analysis is viewed as inseparable from numerical methods.

Importance of Numerical Methods

• Solving Unsolvable Problems: Most nonlinear differential equations, complex integrals, and large systems of equations have no analytical solutions. Numerical methods are the only practical solution for weather prediction or airflow simulation over wings.

• Handling Real-World Data: Real-world data is often discrete, messy, incomplete, or uncertain; numerical methods are specifically designed for these approximated systems.

• Scientific Computing and Engineering:

  • Simulation: Fluid dynamics, structural analysis, climate modeling.

  • Optimization: Design optimization, resource allocation.

  • Data Analysis: Interpolation, regression, eigenvalue problems.

• Powering Modern Technology:

  • Graphics: Physics simulation and rendering.

  • Finance: Monte Carlo methods and stochastic differential equations.

  • Signal Processing: Fast Fourier Transform (FFT).

  • Machine Learning: Gradient descent and numerical linear algebra.

• Computational Efficiency: Faster than symbolic computation for large-scale problems and essential for real-time applications like navigation or control systems.

Historical Failures Due to Numerical Errors

• Patriot Missile Failure (1991): Accumulated round-off error in a clock conversion caused a tracking error of approximately $0.34\,\text{s}$, causing the interceptor to miss.

• Ariane 5 Explosion (1996): Caused by a floating-point value overflow during a conversion to a 16-bit integer.

• Vancouver Stock Exchange (1982): Repeated truncation (chopping) caused the index to lose approximately half its value over 22 months.

Key Characteristics and Trade-offs

• Approximation: Solutions require a stated error tolerance.

• Discretization: Converting continuous problems into discrete counterparts.

• Iteration: Using repeated convergent calculations.

• Error Analysis: Controlling rounding and truncation errors.

• Stability & Convergence: Ensuring small errors do not amplify.

• Computational Cost: Balancing accuracy against speed and memory usage.

Common Examples of Numerical Methods

• Root Finding: Newton–Raphson, Bisection.

• Linear Systems: Gaussian Elimination, LU decomposition (solving $Ax = b$).

• Integration: Trapezoidal Rule, Simpson’s Rule.

• Differentiation: Finite difference approximations.

• ODEs: Euler’s method, Runge–Kutta.

• PDEs: Finite Element, Finite Volume, and Finite Difference Methods.

• Optimization: Gradient Descent, Simplex.

Sources of Errors

1. Modeling Errors: Errors introduced when equations approximate physical systems (e.g., neglecting air resistance in projectile motion).

2. Blunders and Mistakes (Human Errors):

   • Blunders: Occur at any stage; avoided by fundamental knowledge and care.

   • Mistakes: Programming errors (e.g., typing $98.1$ instead of $9.81$) or mixing units (e.g., the Mars Climate Orbiter loss in 1999 due to mixing pound-seconds and newton-seconds).

3. Inherent (Data) Errors: Preexist in the problem statement (uncertain measurements, empirical constants). These can only be minimized with better data collection.

4. Machine Representation and Arithmetic (Round-off): Inevitable due to floating-point arithmetic (rounding and chopping).

5. Mathematical Approximation (Truncation/Discretization): Arise from using an approximate formulation for an exact problem (e.g., using finite terms of a Taylor series).

Accuracy vs. Precision

• Accuracy: How closely a computed/measured value agrees with the true value.

• Precision: How closely individual computed/measured values agree with each other.

• Inaccuracy (Bias): Systematic deviation from the truth.

• Imprecision (Uncertainty): The magnitude of the scatter in results.

• Dartboard Analogy:

  • Precise but Inaccurate: Darts are tightly grouped but far from the bullseye.

  • Accurate but Imprecise: Darts are scattered around the bullseye but average out to the center.

Measuring Error

• If $X_E$ is the exact value and $X_A$ is the approximation, the difference is the error.

• Exact Value Formula: $\text{Exact value} = \text{approximate value} + \text{error}$.

Absolute and Relative Errors

• Absolute Error ($E_a$): $E_a = |X_E - X_A|$

• Relative Error ($E_r$): $E_r = \left| \frac{X_E - X_A}{X_E} \right|$ (provided $X_E \ne 0$).

• Percentage Relative Error ($E_p$): $E_p = 100 \times E_r$

Comparison Example: Bridge vs. Rivet

• Bridge: True length $10,000\,\text{cm}$, measured as $9,999\,\text{cm}$.

  • $E_a = 1\,\text{cm}$

  • $E_p = 0.01\%$

• Rivet: True length $10\,\text{cm}$, measured as $9\,\text{cm}$.

  • $E_a = 1\,\text{cm}$

  • $E_p = 10\%$

• Conclusion: While absolute errors are identical, the relative error shows the rivet measurement is far less reliable.

Approximation of $\pi$ by $\frac{22}{7}$

• $X_E = \pi \approx 3.14159265$

• $X_A = \frac{22}{7} \approx 3.14285714$

• $E_a \approx 0.00126449$

• $E_r \approx 4.025 \times 10^{-4}$

• $E_p \approx 0.040\%$

True vs. Approximate Relative Error

• When $X_E$ is unknown (common in iteration), the Approximate Relative Error ($\epsilon_a$) is used:   $\epsilon_a = \left| \frac{\text{current approximation} - \text{previous approximation}}{\text{current approximation}} \right| \times 100\%$

• Scarborough Stopping Criterion: Iterate until \epsilon_a < \epsilon_s = (0.5 \times 10^{2-n})\%, which ensures result is correct to at least $n$ significant figures.

  • For $n = 3$, stopping at \epsilon_a < 0.05\%.

Significant Digits

• Significant digits define the reliability of a number. They are the digits that can be used with confidence.

• Requirement for Significant Digits: $X_A$ approximates $X_E$ to $t$ significant digits if $t$ is the largest non-negative integer satisfying:   \left| \frac{X_E - X_A}{X_E} \right| < 5 \times 10^{-t}

Rules for Counting Significant Digits

1. All non-zero digits ($3.14159$ has 6).

2. Zeros between non-zeros ($5.007$ has 4).

3. Leading zeros are NOT significant ($0.00450$ has 3: the 4, 5, and trailing 0).

4. Trailing zeros after a decimal are significant ($45.300$ has 5).

5. Trailing zeros in integers are ambiguous; scientific notation should be used (e.g., $4.53 \times 10^4$ has 3 vs $4.5300 \times 10^4$ has 5).

Significant Digits Examples

• Case 1: $12.34$ approximating $12.35$

  • $E_r = \frac{0.01}{12.35} \approx 0.0008097$

  • Test $t=4$: 0.0008097 < 0.0005 (No).

  • Test $t=3$: 0.0008097 < 0.005 (Yes).

  • Result: 3 significant digits.

• Case 2: $2.71828$ approximating $e \approx 2.7182818$

  • $E_a = 0.0000018$

  • $E_r \approx 6.6236 \times 10^{-7}$

  • Test $t=7$: 6.6236 \times 10^{-7} < 5 \times 10^{-7} (No).

  • Test $t=6$: 6.6236 \times 10^{-7} < 5 \times 10^{-6} (Yes).

  • Result: 6 significant digits.

• Case 3: Approximation of $\sqrt{2} \approx 1.41421356$ by $1.414$

  • $E_r \approx 1.510 \times 10^{-4}$

  • Test $t=4$: 1.510 \times 10^{-4} < 5 \times 10^{-4} (Yes).

  • Result: 4 significant digits.

Round-off Errors and Machine Representation

Floating-Point Representation

• Numbers stored as $x = \pm m \times b^{e}$.

  • $m$: mantissa.

  • $b$: base (usually 2).

  • $e$: exponent.

• Single Precision (32-bit): ~7 decimal digits.

• Double Precision (64-bit): ~15–16 decimal digits.

• Machine Epsilon ($\epsilon_{mach}$): Smallest number where $1 + \epsilon_{mach} \ne 1$; for double precision, $\epsilon_{mach} \approx 2.22 \times 10^{-16}$.

• Binary error example: $0.1 + 0.2 \ne 0.3$ exactly in a computer because decimals like $0.1_{10}$ repeat forever in binary.

Chopping vs. Rounding

• Example: keeping $n=4$ digits for $\frac{2}{3} = 0.666666...$

  • Chopping: Dropping extra digits ($0.6666$). Error is always biased in one direction ($E_r \le 10^{1-n}$).

  • Rounding: Rounding the last kept digit ($0.6667$). Error is at most half a unit in last place ($E_r \le 0.5 \times 10^{1-n}$).

Arithmetic Effects: Subtractive Cancellation

• Subtracting two nearly equal numbers destroys significant digits (loss of significance).

• High-error example: Computing $f = \sqrt{9.01} - 3$ with 4-digit arithmetic.

  • $\sqrt{9.01} \approx 3.002$

  • $f \approx 3.002 - 3.000 = 0.002$

  • True value: $0.0016662...$ (Relative error ~$20\%$).

• Algebraic Cure: Reformulate to $\frac{(\sqrt{9.01} - 3)(\sqrt{9.01} + 3)}{\sqrt{9.01} + 3} = \frac{0.01}{\sqrt{9.01} + 3} \approx \frac{0.01}{6.002} = 0.001666$.

Truncation Errors and Taylor Series

• Truncation errors arise from approximating an infinite process with a finite one.

• The Taylor Series Formula:   $f(x_{i+1}) = f(x_i) + f'(x_i)h + \frac{f''(x_i)}{2!}h^2 + \dots + \frac{f^{(n)}(x_i)}{n!}h^n + R_n$   where $h = x_{i+1} - x_i$ and the remainder is:   $R_n = \frac{f^{(n+1)}(\xi)}{(n+1)!}h^{n+1} = O(h^{n+1}), \xi \in (x_i, x_{i+1})$

Taylor Series Examples

• Approximating $e^1$: Truncated after 3 terms ($1 + 1 + 0.5 = 2.5$); true value $2.71828$, error $0.21828$.

• Approximating $\ln(2)$ from Base Point $x=1$:

  • Zero order: $0$ ($100\%$ error).

  • First order: $1$ ($44.27\%$ error).

  • Fourth order: $0.583333$ ($15.84\%$ error).

  • Observation: Series converges slowly; higher orders or smaller steps improve it.

• Approximating $\sin(0.5)$ using $x - \frac{x^3}{6}$:

  • Result: $0.5 - \frac{0.125}{6} = 0.4791667$

  • True value: $0.4794255$

  • Remainder bound ($|R| \le \frac{|x|^5}{5!}$): predicts error bound of $2.60 \times 10^{-4}$, very close to actual error ($2.59 \times 10^{-4}$).

The Step-Size Dilemma

• Total Error = Truncation Error + Round-off Error.

• Decreasing step size ($h$) reduces truncation error but increases the number of operations and round-off impact.

• Optimal $h^*$: For central differences in double precision, $h^* \approx \epsilon_{mach}^{1/3} \approx 6 \times 10^{-6}$. Making $h$ smaller than this increases total error.

Error Propagation

• How input uncertainties ($\Delta x_i$) affect output volatility.

General Formulas

• Statistical Formula: $\Delta f = \sqrt{\sum_{i=1}^n \left( \frac{\partial f}{\partial x_i} \Delta x_i \right)^2}$

• Taylor Expansion Approximation: $\Delta F = \sum_{i=1}^n \left| \frac{\partial f}{\partial x_i} \Delta x_i \right|$

Quick Propagation Rules (Relative Error $r_x = \frac{\Delta x}{|x|}$)

• $f = x \pm y$: Absolute errors add ($\Delta f = \Delta x + \Delta y$).

• $f = xy$ or $f = \frac{x}{y}$: Relative errors add ($r_f = r_x + r_y$).

• $f = x^p$: $r_f = |p| r_x$.

• $f = c x$ ($c$ is exact): $r_f = r_x$.

Examples of Propagation

• Sphere Volume: Given $r = 2.00 \pm 0.05\,\text{cm}$.

  • $V = \frac{4}{3}\pi r^3 = 33.51\,\text{cm}^3$

  • $\frac{\partial V}{\partial r} = 4\pi r^2 = 50.27\,\text{cm}^2$

  • $\Delta V = 50.27 \times 0.05 \approx 2.51\,\text{cm}^3$.

  • Result: $V = 33.5 \pm 2.5\,\text{cm}^3$.

• Complex Function $F = 3x^2y^2 + 5y^2z^2 - 7x^2z^2 + 38$:

  • At $x=y=z=1$; $\Delta x = -0.05, \Delta y = 0.001, \Delta z = 0.02$.

  • Max relative error $(E_r)_{max} = \frac{0.496}{39} \approx 0.01272$.

Stability and Conditioning

Definitions

• Conditioning (Problem Property): Sensitivity of the exact solution to small input changes.

• Stability (Algorithm Property): Whether the numerical method amplifies internal errors (round-off/truncation).

Condition Number ($\kappa$)

• $\kappa = \left| \frac{a f'(a)}{f(a)} \right|$

  • $\kappa = 1$: Error unchanged.

  • \kappa > 1: Error amplified.

  • \kappa < 1: Error attenuated.

  • $\kappa \gg 1$: Ill-conditioned problem.

Conditioning of Functions

• $\sqrt{x}$: $\kappa = \frac{1}{2}$ (always well-conditioned).

• $e^x$: $\kappa = a$ (ill-conditioned for large $|a|$).

• $\ln(x)$: $\kappa = \frac{1}{\ln(a)}$ (ill-conditioned near $a=1$).

• $x - c$: $\kappa = \frac{a}{a-c}$ (ill-conditioned for $a \approx c$; subtractive cancellation).

Stability Examples

• Ill-Conditioned System: A small change ($0.0001$) in inputs to a nearly singular matrix results in a $100\%$ change in the solution.

• Recursive Integral $I_n = \int_0^1 x^n e^{x-1} dx$:

  • Forward Recursion ($I_n = 1 - nI_{n-1}$): Unstable. Errors are multiplied by $n!$; by $n=15$, the result is meaningless and negative.

  • Backward Recursion ($I_{n-1} = \frac{1 - I_n}{n}$): Stable. Errors are divided by $n$ at each step, yielding high precision even from a poor initial guess.