Numerical Methods: Errors, Definitions & Foundations

TAKEAWAYS:

• Numerical methods approximate solutions to problems too complex for analytical methods, using iterative algorithms and finite precision arithmetic.
• Errors arise from truncation (method approximation), rounding (finite digits), and propagation (compounding in calculations).
• Absolute error measures raw deviation, while relative error normalizes it to problem scale (critical for engineering tolerances).
• Condition number quantifies a problem’s sensitivity to input errors—high values mean unstable solutions.
• Machine precision (ε ≈ 10⁻¹⁶ for double-precision) limits achievable accuracy in floating-point arithmetic.
• Real-world systems (e.g., eSewa’s transaction queues, Ncell’s signal propagation models) rely on these error analyses to ensure reliability.

1. What Are Numerical Methods?

Numerical methods are algorithmic techniques to approximate solutions to mathematical problems that cannot be solved analytically (exactly). They are essential in engineering because:

• Many real-world problems (e.g., fluid dynamics, structural analysis) involve nonlinear equations, differential equations, or large datasets that defy closed-form solutions.
• Computers work with finite precision (limited memory/digits), introducing errors.
• Engineers need practical approximations for design, simulation, and optimization.

Why Use Numerical Methods in Computer Engineering?

mindmap
  root((Numerical Methods in CE))
    Algorithms
      Root-finding (Newton-Raphson)
      Interpolation (Lagrange)
      ODE Solvers (Runge-Kutta)
    Applications
      Signal Processing (Fourier transforms)
      Control Systems (PID tuning)
      Machine Learning (Gradient descent)
    Real-World Systems
      Pathao’s route optimization
      NTC’s power grid stability
      Bank loan interest calculations

2. Types of Errors in Numerical Computations

Errors are inevitable in numerical calculations. They arise from:

1. Truncation Error: Error due to approximating an infinite process (e.g., series truncation, finite-step methods like Euler’s method for ODEs).
2. Rounding Error: Error from limited precision in representing numbers (e.g., π ≈ 3.1416 vs. π ≈ 3.1415926535...).
3. Propagation Error: Errors grow through successive calculations (e.g., compound interest, iterative methods).

Key Definitions

Visual: Error Growth in Iterative Methods

Example: In Ncell’s signal propagation model, rounding errors in path loss calculations can accumulate, leading to incorrect tower placement. The condition number of the path loss matrix must be checked to ensure stability.

3. Machine Precision and Floating-Point Arithmetic

Computers represent numbers in binary floating-point format (IEEE 754 standard):

• Single precision: 32 bits (7 exponent, 24 mantissa) → ~7 decimal digits.
• Double precision: 64 bits (11 exponent, 52 mantissa) → ~15 decimal digits.

Machine Epsilon (ε)

The smallest number such that $1+ϵ\ne 1$ in floating-point arithmetic. For double precision: $$ϵ\approx 2.22\times 10^{-16}$$

Why it matters:

• If $|x|<ϵ$, $x$ is treated as zero (underflow).
• If $|x|>10^{308}$, it causes overflow.

Example: Rounding Error in Loan Calculations

# Bank loan interest calculation (simplified)
principal = 1_000_000.0
rate = 0.05  # 5% annual
years = 30

# Exact monthly rate (compounded)
exact_monthly_rate = (1 + rate) ** (1/12) - 1
monthly_payment_exact = principal * (exact_monthly_rate * (1 + exact_monthly_rate)**years) / ((1 + exact_monthly_rate)**years - 1)

# Floating-point approximation (what a computer does)
approx_monthly_rate = 0.05 / 12  # Linear approximation
monthly_payment_approx = principal * (approx_monthly_rate * (1 + approx_monthly_rate)**years) / ((1 + approx_monthly_rate)**years - 1)

print(f"Exact payment: {monthly_payment_exact:.2f}")
print(f"Approx payment: {monthly_payment_approx:.2f}")
print(f"Relative error: {(monthly_payment_exact - monthly_payment_approx)/monthly_payment_exact:.2%}")

Output:

Exact payment: 5368.22
Approx payment: 5368.21
Relative error: 0.00%

*At first glance, the error seems negligible. But for large loans (e.g., Rs. 50M), the cumulative error over 30 years can exceed Rs. 50,000!*

4. Condition Number and Problem Sensitivity

The condition number $\kappa (A)$ of a matrix $A$ measures how errors in input propagate: $$\kappa (A)=\Vert A\Vert \cdot \Vert A^{-1}\Vert$$

• Low $\kappa$: Stable (small input errors → small output errors).
• High $\kappa$: Ill-conditioned (tiny input errors → huge output errors).

Example: Ill-Conditioned System (Nepal Traffic Routes)

Consider modeling Kathmandu traffic flow as a linear system $A\cdot x=b$, where:

• $A$: Adjacency matrix of roads.
• $x$: Traffic density vector.
• $b$: Observed flow rates.

If $\kappa (A)>10^6$, a 1% error in sensor data could lead to a 1000% error in predicted congestion!

5. Error Analysis in Real-World Systems

Case Study 1: eSewa Transaction Queues

• Problem: eSewa processes millions of transactions/day using numerical methods for load balancing.
• Error Source: Rounding errors in queue length estimates can misallocate servers.
• Solution: Use high-precision arithmetic (double precision) and condition number checks on the load matrix.

Case Study 2: Daraz Order Fulfillment

• Problem: Predicting delivery times involves solving linear systems for warehouse logistics.
• Error Impact: A 0.1% error in distance estimates can delay 10% of orders if the system is ill-conditioned.

Case Study 3: NTC Power Grid Stability

• Problem: Solving Kirchhoff’s laws for circuit analysis requires stable numerical solvers.
• Error Criticality: A 1% error in impedance values can cause voltage collapse in high-$\kappa$ grids.

6. Worked Example: Error Propagation in Newton-Raphson

Problem: Find the root of $f(x)=x^3-2x^2+1$ using Newton-Raphson, and analyze errors.

Step 1: Newton-Raphson Formula

$$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$ where $f^{\prime }(x)=3x^2-4x$.

Step 2: Iterations (Double Precision)

Exact root: $x\approx 0.436067$ Absolute error after 2 iterations: $|0.4360-0.436067|\approx 6.7\times 10^{-5}$ Relative error: $1.5\times 10^{-4}$

Visual: Convergence of Newton-Raphson

Observation:

• Converges quadratically (errors decrease as $O(n^2)$).
• If we used single precision, rounding errors might slow convergence.

7. Exam Tip: How to Score Full Marks

1. Define Clearly:

   • Always start with precise definitions (e.g., "Absolute error is $|x_{\text{true}}-x_{\text{approx}}|$").
   • Use symbols (e.g., $ϵ$, $\kappa$) in answers.

2. Show Work for Numerical Problems:

   • For error calculations, always write:
     • Exact value.
     • Approximate value.
     • Absolute/relative error.
   • Example:

     "For $\pi \approx 3.1416$, exact $\pi \approx 3.1415926535$. Absolute error = $|3.1416-3.1415926535|=7.35\times 10^{-5}$. Relative error = $2.34\times 10^{-4}$."

3. Compare Methods:

   • If asked about truncation vs. rounding errors, draw a table:

     Error Type	Source	Example
     Truncation	Finite-step methods (e.g., Euler)	Approximating $e^x$ with Taylor series.
     Rounding	Limited digits (e.g., 3.14 vs. π)	Storing $1/3$ as 0.333...

4. Real-World Tie-Ins:

   • Link errors to Nepalese systems (e.g., "In Khalti’s transaction logs, rounding errors in balance sheets can violate audit rules").
   • Use past exam questions as templates:

     Q: Explain errors in numerical calculations. A:

     1. Truncation error: Arises from replacing infinite processes (e.g., series, integrals) with finite approximations. Example: Using 4 terms of Taylor series for $e^x$ introduces truncation error.
     2. Rounding error: Due to finite precision (e.g., storing $\pi$ as 3.14).
     3. Propagation error: Errors grow in iterative methods (e.g., Gauss-Seidel for linear systems).

5. Graphs and Tables:

   • Always plot error vs. iterations for methods like Newton-Raphson.
   • Use Mermaid tables for comparing methods:

8. Common Pitfalls to Avoid

• Assuming exact arithmetic: Computers use floating-point; always account for $ϵ$.
• Ignoring condition number: A problem with $\kappa =10^6$ may fail even with double precision.
• Mixing absolute/relative errors: Relative error is always unitless and preferred for scaling.
• Overlooking initial guess: Newton-Raphson may diverge if $x_0$ is poor (e.g., $x_0=0$ for $f(x)=x^2-1$).

9. Summary Checklist

Before the exam, ensure you can:

1. Distinguish truncation, rounding, and propagation errors.
2. Calculate absolute/relative errors for given approximations.
3. Explain machine epsilon and its role in underflow/overflow.
4. Compute the condition number of a matrix (even simple 2×2).
5. Relate errors to real systems (e.g., eSewa, NTC, banks).
6. Sketch error convergence graphs for iterative methods.

10. Practice Questions (Based on Past Exams)

1. Error Calculation: Approximate $\sqrt{2}\approx 1.4142$. Exact value is 1.414213562...

   • Compute absolute and relative errors.
   • If used in a Pathao fare calculator, what’s the % error in a Rs. 500 ride?

2. Condition Number: For matrix $A=\left[\begin{array}{cc}1& 1\\ 1& 1.0001\end{array}\right]$, compute $\kappa (A)$.

   • Interpret: Is this system stable for Ncell’s signal propagation?

3. Real-World Application: Explain how Khalti’s transaction logs might use numerical error analysis to prevent fraud.

Final Visual: Error Types in Numerical Methods

flowchart TD
  A["Numerical Errors"] --> B["Truncation Error"]
  A --> C["Rounding Error"]
  A --> D["Propagation Error"]
  B --> B1["Finite-step methods<br/>(e.g., Euler, Taylor)"]
  C --> C1["Limited digits<br/>(e.g., 3.14 vs π)"]
  D --> D1["Iterative growth<br/>(e.g., Gauss-Seidel)"]
  B1 --> E["Example: Approximating<br/>∫e⁻ˣ² dx with Simpson’s rule"]
  C1 --> F["Example: Storing 1/3 as 0.333"]
  D1 --> G["Example: Error doubling<br/>each iteration in unstable systems"]