Numerical Methods: Errors, Approximations & Foundations

TAKEAWAYS:

• Numerical methods approximate solutions because exact analytical methods fail for complex real-world problems (e.g., nonlinear equations, large datasets).
• Errors arise from truncation (method limitations), rounding (finite precision), and propagation (accumulation in calculations).
• Absolute error measures raw deviation, while relative error normalizes it to the magnitude of the value (critical for small numbers).
• Condition number determines how sensitive a problem is to input errors—high condition numbers mean tiny input changes cause huge output errors.
• Floating-point arithmetic introduces rounding errors; understanding its limits (e.g., IEEE 754 standard) is key to designing stable algorithms.
• Error analysis guides method selection: choose methods with faster convergence (e.g., Newton-Raphson over bisection) for efficiency.

1. Why Numerical Methods? Exact vs. Approximate Solutions

Most real-world problems cannot be solved exactly using pen-and-paper math. Numerical methods provide approximate solutions with controlled error.

When Do We Need Numerical Methods?

2. Types of Errors in Numerical Computation

Errors are inevitable in numerical calculations. Classifying them helps minimize their impact.

A. Truncation Error

• Definition: Error due to approximating an infinite process with a finite one.
• Example: Using a Taylor series expansion with only 3 terms instead of ∞.
• Real-World Impact:
  • eSewa’s payment processing: If a transaction fee is approximated as a fixed percentage (instead of a dynamic rate), truncation error accumulates over millions of transactions.
  • Weather forecasting: Simplifying atmospheric equations (e.g., ignoring small-scale turbulence) introduces truncation error, leading to less accurate predictions.

Worked Example 1: Truncation Error in Taylor Series Approximate $e^{0.1}$ using a 2nd-order Taylor expansion around 0. Solution: The Taylor series for $e^x$ is: $$e^x\approx 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\dots$$ For 2nd-order ($n=2$): $$e^{0.1}\approx 1+0.1+\frac{(0.1{)}^2}{2}=1.105$$ Exact value: $e^{0.1}\approx 1.105170918$ Truncation error: $$|1.105170918-1.105|=0.000170918$$

Observation: Higher-order terms reduce truncation error. For $e^{0.1}$, a 3rd-order term adds $\frac{(0.1{)}^3}{6}=0.0001667$, improving accuracy.

B. Rounding Error

• Definition: Error introduced when storing numbers with finite precision (e.g., 32-bit floats).
• Example: Storing $\frac{1}{3}$ as 0.333333333 (instead of its true decimal expansion).
• Real-World Impact:
  • Khalti’s transaction logs: Rounding errors in fractional paisa values can accumulate to significant losses over millions of transactions.
  • Bank loan calculations: Interest rates compounded daily may introduce rounding errors, affecting final repayment amounts.

Worked Example 2: Rounding Error in Floating-Point Arithmetic Compute $(1.0-10^{-16})\times 10^{16}$ in 32-bit floating-point. Solution:

• In IEEE 754 (32-bit), the smallest representable number near 1 is $1.0000001$.
• $1.0-10^{-16}$ rounds to 1.0 (since $10^{-16}$ is below the precision limit).
• Result: $1.0\times 10^{16}=10^{16}$ (exact), but the true result should be $10^{16}-1$.

Key Takeaway: Rounding errors can cancel out meaningful digits. Always use higher precision (e.g., double in Python) for critical calculations.

C. Propagation Error

• Definition: Error that grows as calculations proceed (e.g., in iterative methods).
• Example: Solving $x=\sqrt{2+\sqrt{3}}$ with rounded intermediate values.
• Real-World Impact:
  • Pathao’s route optimization: Small errors in distance calculations propagate, leading to inefficient (and costly) delivery routes.
  • NTC’s load forecasting: Errors in initial power demand estimates grow when predicting future consumption.

Worked Example 3: Error Propagation in a Simple Formula Compute $f(x)=\frac{x^2}{x+1}$ for $x=1.001$ with rounding to 3 decimal places. Solution:

1. $x^2=(1.001{)}^2=1.002001\approx 1.002$ (rounded)
2. $x+1=2.001\approx 2.001$
3. $f(x)=\frac{1.002}{2.001}\approx 0.50075$ Exact value: $\frac{1.002001}{2.001}\approx 0.500750$ Propagation error: $|0.500750-0.50075|=0.000000$ (small here, but grows in complex formulas).

flowchart TD
    A["Input: x = 1.001"] --> B["Step 1: x² ≈ 1.002 (rounded)"]
    B --> C["Step 2: x + 1 ≈ 2.001 (rounded)"]
    C --> D["Step 3: f(x) ≈ 0.50075"]
    D --> E["Error propagates if more steps are added"]

3. Absolute vs. Relative Error

Worked Example 4: Comparing Errors

• Case 1: Measuring a 100m distance with an error of 1m.
  • Absolute error: $|100-99|=1$ m
  • Relative error: $\frac{1}{100}=0.01$ (1%)
• Case 2: Measuring a 1m distance with an error of 1mm.
  • Absolute error: $|1-0.999|=0.001$ m
  • Relative error: $\frac{0.001}{1}=0.001$ (0.1%)

Key Insight: Relative error is scale-invariant—critical for comparing errors in different contexts (e.g., financial calculations vs. engineering tolerances).

4. Condition Number and Stability

The condition number ($\kappa$) measures how sensitive a function is to input errors.

$$\kappa (f)=\left|\frac{x\cdot f^{\prime }(x)}{f(x)}\right|$$

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

Real-World Example: NEPSE Stock Prices

• Problem: Predicting stock prices using historical data.
• Issue: Small errors in past prices (due to rounding) can lead to wildly different future predictions if the model is ill-conditioned.
• Solution: Use regularization (e.g., smoothing data) to reduce $\kappa$.

Worked Example 5: Condition Number of a Linear System For the system $A\mathbf{x}=\mathbf{b}$, the condition number is: $$\kappa (A)=\Vert A\Vert \cdot \Vert A^{-1}\Vert$$ where $\Vert \cdot \Vert$ is the matrix norm.

Example: $$A=\left[\begin{array}{cc}1& 1\\ 1& 1.0001\end{array}\right],\mathbf{b}=\left[\begin{array}{c}2\\ 2.0001\end{array}\right]$$

• $\det (A)=0.0001$ (very small → ill-conditioned).
• $\kappa (A)\approx 10^4$: A 1% error in $\mathbf{b}$ could cause a 10,000% error in $\mathbf{x}$.

5. Floating-Point Arithmetic and IEEE 754 Standard

Computers represent numbers in binary floating-point, which introduces rounding errors.

Key Concepts:

1. Sign bit (1 bit): + or –.
2. Exponent (8 bits in single-precision): Range of values.
3. Mantissa (23 bits in single-precision): Precision of the number.

Example: Storing $\frac{1}{3}$ in 32-bit float.

• Exact binary: $0.\overline{0101}\times 2^0$
• Stored as: $0.01010101010101010101011\times 2^0$ (rounded)
• Decimal approximation: 0.33333334326744074

Real-World Impact:

• Google Maps: Rounding errors in GPS coordinates can misplace markers by meters over large distances.
• WhatsApp encryption: Floating-point errors in cryptographic keys (if used) could break security.

classDiagram
    class FloatingPoint {
        +sign: 1 bit
        +exponent: 8 bits
        +mantissa: 23 bits
        +range: ~10^-38 to 10^38
        +precision: ~7 decimal digits
    }
    class IEEE754 {
        <<standard>>
        +single: 32 bits
        +double: 64 bits
        +extended: 80 bits
    }
    FloatingPoint --> IEEE754 : "Implements"

6. Error Analysis in Algorithms

Not all numerical methods are equally sensitive to errors. Convergence and stability are critical.

Worked Example 6: Comparing Bisection vs. Newton-Raphson Find a root of $f(x)=x^2-2$ in [1, 2].

• Bisection:
  • Iteration 1: $x=1.5$, $f(1.5)=0.25$ → new interval [1.5, 2]
  • Iteration 2: $x=1.75$, $f(1.75)=0.0625$ → [1.75, 2]
  • Convergence: Slow (halves error each step).
• Newton-Raphson:
  • $f^{\prime }(x)=2x$
  • $x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$
  • Start at $x_0=1.5$:
    • $x_1=1.5-\frac{0.25}{3}=1.4167$
    • $x_2=1.4167-\frac{-0.000277}{2.8334}\approx 1.414214$
  • Convergence: Quadratically fast (error squared each step).

In the Real World

1. eSewa’s Payment Processing

   • Concept: Rounding and truncation errors in transaction fees.
   • How it works: When eSewa calculates a 1.5% fee on a Rs. 1000 transaction, it rounds to Rs. 15.00 (truncating the paisa). Over 1 million transactions, this accumulates to Rs. 150,000 in lost revenue due to truncation error.
   • Solution: Use arbitrary-precision arithmetic for financial calculations.

2. Pathao’s Delivery Route Optimization

   • Concept: Error propagation in distance calculations.
   • How it works: Pathao’s algorithm uses GPS coordinates to compute distances. A 1-meter error in GPS (due to rounding) can lead to a 5% error in estimated delivery time for long routes, causing delays and customer dissatisfaction.
   • Solution: Apply Kalman filtering to smooth GPS data and reduce propagation errors.

3. NTC’s Power Load Forecasting

   • Concept: Ill-conditioned systems in linear algebra.
   • How it works: NTC uses linear regression to predict electricity demand. If the input data (historical consumption) has high variance, the regression coefficients become extremely sensitive to small changes (high condition number), leading to unreliable forecasts.
   • Solution: Use regularized regression (e.g., Ridge regression) to stabilize the system.

Exam Tip

1. Error Definitions: Always define absolute error, relative error, and truncation/rounding errors with formulas. Examiners love precise definitions.

   • Example: "Absolute error is $|x_{\text{true}}-x_{\text{approx}}|$, while relative error is $\frac{|x_{\text{true}}-x_{\text{approx}}|}{|x_{\text{true}}|}$."

2. Worked Examples: For questions like "Find the relative error of 5.6 if both digits are correct", show step-by-step:

   • True value range: [5.55, 5.65]
   • Maximum absolute error: 0.05
   • Relative error: $\frac{0.05}{5.6}\approx 0.0089$ (0.89%).

3. Condition Number: If asked about stability, always relate it to matrix norms or function derivatives. Example:

   • "For $f(x)=\frac{1}{x}$, $\kappa (f)$ is high near $x=0$ because $f^{\prime }(x)=-\frac{1}{x^2}$, making it ill-conditioned."

4. Floating-Point Pitfalls: Mention IEEE 754 and catastrophic cancellation (e.g., $1.0-10^{-16}$) in your answers. Example:

   • "In floating-point arithmetic, $1.0-10^{-16}$ rounds to 1.0, leading to a loss of 16 significant digits."

5. Method Comparison: For root-finding or integration, compare convergence rates and error bounds. Example:

   • "Newton-Raphson converges quadratically, while bisection converges linearly. For $f(x)=x^2-2$, Newton-Raphson finds $\sqrt{2}$ in 2 iterations, whereas bisection requires ~20."

6. Real-World Links: Always tie numerical concepts to Nepali examples (e.g., NTC, banks, eSewa) or global tech (Google, WhatsApp). Example:

   • "Like how Pathao’s route errors propagate, numerical methods in traffic simulation must account for rounding errors in distance matrices."

Final Note: Numerical methods are everywhere—from mobile apps to national infrastructure. Mastering errors and approximations is the first step to designing reliable, efficient algorithms. Practice error calculations and method comparisons to excel in exams!

In the real world

• eSewa & Khalti (Payment Gateways): Use Rounding Error management in their backend. When processing millions of transactions with fractional paisa values, they use high-precision arithmetic (like double or decimal types) to ensure that tiny rounding errors don't accumulate into significant financial discrepancies in their daily settlement reports.
• Pathao (Ride-Hailing): Relies on Propagation Error control in route optimization. Small errors in GPS coordinates or distance calculations can propagate through the algorithm, leading to inefficient routes. They use robust numerical methods to minimize this accumulation, ensuring drivers take the most cost-effective path.
• NTC (Telecom): Applies Condition Number analysis in load forecasting. When predicting future power or data demand, they assess how sensitive their models are to small input errors (like minor fluctuations in historical data). High condition numbers would mean tiny data changes cause huge forecast errors, so they stabilize their input data to keep predictions reliable.