Numerical Methods: Errors, Approximations & Foundations

1. Introduction to Numerical Methods

1.1 Why Numerical Methods?

• Analytical vs. Numerical Solutions:
  • Many mathematical problems (e.g., differential equations, nonlinear systems) lack closed-form analytical solutions.
  • Numerical methods provide approximate solutions using algorithms and computational techniques.
• Applications:
  • Engineering (stress analysis, fluid dynamics).
  • Physics (quantum mechanics, astrophysics).
  • Economics (optimization, forecasting).
  • Biology (population modeling, pharmacokinetics).

1.2 Classification of Numerical Methods

---

2. Error Analysis in Numerical Methods

Errors are inevitable in numerical computations. Understanding them helps in assessing accuracy and designing algorithms.

2.1 Sources of Errors

A. Truncation Error (Discretization Error)

• Definition: Error due to approximating an infinite process (e.g., series, derivatives) with a finite one.
• Examples:
  • Replacing a derivative with a finite difference: $f^{\prime }(x)\approx \frac{f(x+h)-f(x)}{h}$.
  • Using a Taylor series with a finite number of terms.
• Reduction Techniques:
  • Use smaller step sizes ($h\to 0$).
  • Higher-order methods (e.g., 4th-order Runge-Kutta vs. Euler’s 1st-order).

B. Rounding Error (Machine Error)

• Definition: Error due to finite precision in computer arithmetic (e.g., floating-point representation).
• Examples:
  • $0.1+0.2\ne 0.3$ in binary floating-point.
  • Storing $\pi$ as 3.141592653589793 (truncated).
• Mitigation:
  • Use higher precision (double vs. single precision).
  • Error propagation analysis (see Section 2.3).

C. Input Data Error

• Definition: Error from imperfect or noisy input data (e.g., measurements, experimental data).
• Example: Measuring a length as 5.0 cm when the true value is 4.98 cm.

---

2.2 Types of Error Measures

Example:

• True value of $\sqrt{2}\approx 1.414213562$.
• Approximate value: $1.414$.
• Absolute Error: $|1.414213562-1.414|=0.000213562$.
• Relative Error: $\frac{0.000213562}{1.414213562}\approx 0.000151$ (0.0151%).

---

2.3 Error Propagation

When errors accumulate through computations, they grow unpredictably. The absolute error in a function $f(x)$ due to error in $x$ is approximated by: $$E_f\approx |f^{\prime }(x)|\cdot E_x$$ Example: Compute $E_{x^2}$ if $E_x=0.01$ and $x=5$.

• $f(x)=x^2$, $f^{\prime }(x)=2x$.
• $E_{x^2}\approx |2\cdot 5|\cdot 0.01=0.1$.

Key Insight:

• Errors amplify in nonlinear functions (e.g., $x^2$ vs. $x$).
• Stable algorithms minimize error growth (e.g., LU decomposition vs. naive Gaussian elimination).

---

3. Taylor Series and Approximations

Taylor series provides a foundation for numerical approximations by expanding functions into polynomials.

3.1 Taylor Series Expansion

For a function $f(x)$ infinitely differentiable at $x=a$: $$f(x)\approx f(a)+f^{\prime }(a)(x-a)+\frac{f^{\prime \prime }(a)}{2!}(x-a{)}^2+\cdots +\frac{f^{(n)}(a)}{n!}(x-a{)}^n$$ Truncation Error: $$E_n=\frac{f^{(n+1)}(\xi )}{(n+1)!}(x-a{)}^{n+1},\xi \in (a,x)$$

3.2 Applications in Numerical Methods

A. Approximating Functions

Example: Approximate $e^x$ near $x=0$ using 3rd-order Taylor series. $$e^x\approx 1+x+\frac{x^2}{2}+\frac{x^3}{6}$$ For $x=0.1$: $$e^{0.1}\approx 1+0.1+\frac{0.01}{2}+\frac{0.001}{6}=1.1051667$$ (True value: $\mathrm{1.1051709...}$, Error: $0.0000042$).

B. Numerical Differentiation

Replace derivatives with finite differences using Taylor expansions: $$f^{\prime }(x)\approx \frac{f(x+h)-f(x)}{h}\text{(Forward difference)}$$ $$f^{\prime }(x)\approx \frac{f(x+h)-f(x-h)}{2h}\text{(Central difference, higher accuracy)}$$

C. Euler’s Method (ODE Solver)

For $y^{\prime }=f(x,y)$, the Taylor expansion gives: $$y(x+h)\approx y(x)+h\cdot f(x,y(x))$$ Example: Solve $y^{\prime }=2x+y$, $y(0)=1$ at $x=0.4$ with $h=0.1$.

Note: Euler’s method has local truncation error $O(h^2)$ and global error $O(h)$.

---

4. Root-Finding Methods (Preview)

While root-finding is covered in later units, this section introduces error-based stopping criteria critical for all iterative methods.

4.1 Bisection Method (Half-Interval Method)

Algorithm:

1. Choose $[a,b]$ such that $f(a)f(b)<0$ (Intermediate Value Theorem).
2. Compute $c=(a+b)/2$.
3. If $|f(c)|<\text{tolerance}$, stop. Else:
   • If $f(a)f(c)<0$, set $b=c$.
   • Else, set $a=c$.
4. Repeat.

Error Analysis:

• Absolute Error: $|x_{\text{true}}-c|\le \frac{b-a}{2^n}$.
• Convergence: Linear with rate $1/2$.

Example: Find root of $f(x)=x^2-e^{-x}-3$ to 3 significant figures.

• Initial guess: $a=1.0$, $b=2.0$ (since $f(1)=-1.367$, $f(2)=1.135$).
• Iterations:
  1. $c=1.5$, $f(1.5)=-0.446$ → $a=1.5$.
  2. $c=1.75$, $f(1.75)=0.302$ → $b=1.75$.
  3. $c=1.625$, $f(1.625)=-0.072$ → $a=1.625$.
  4. $c=1.6875$, $f(1.6875)=0.115$ → $b=1.6875$.
  5. $c=1.65625$, $f(1.65625)\approx 0.021$ → Stop.
• Root ≈ 1.66 (3 significant figures).

---

4.2 Newton-Raphson Method

Formula: $$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}$$ Convergence: Quadratic ($O(h^2)$) if initial guess is close.

Example: Solve $x^2+4x-9=0$ with tolerance $0.01$.

• $f(x)=x^2+4x-9$, $f^{\prime }(x)=2x+4$.
• Initial guess: $x_0=1.0$.

  Iteration	x_n	f(x_n)	f'(x_n)	x_{n+1} = x_n - f/f'
  0	1.0	-4	6	1.0 - (-4)/6 ≈ 1.6667
  1	1.6667	0.1111	7.3334	1.6667 - 0.1111/7.3334 ≈ 1.6515
  2	1.6515	0.0003	7.3030	1.6515 - 0.0003/7.3030 ≈ 1.6515

Stopping: $|x_{n+1}-x_n|<0.01$ → Root ≈ 1.6515.

Drawbacks:

• Requires $f^{\prime }(x)$ (may be complex).
• Divergence if $f^{\prime }(x_n)\approx 0$ or poor initial guess.
• Oscillations near multiple roots.

---

5. Horner’s Method for Polynomial Evaluation

Efficiently evaluates polynomials by reducing multiplications: $$P(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_0=(\dots ((a_{n}x+a_{n-1})x+\dots )x+a_0$$

Example: Evaluate $2x^3-3x^2+5x-2$ at $x=3$. Using Horner’s form: $$P(x)=(((2x-3)x+5)x-2$$ Steps:

1. $2\cdot 3=6$
2. $6-3=3$
3. $3\cdot 3=9$
4. $9+5=14$
5. $14\cdot 3=42$
6. $42-2=40$

Algorithm:

def horner(poly, x):
    result = 0
    for coeff in reversed(poly):
        result = result * x + coeff
    return result

Advantages:

• Fewer operations ($n$ multiplications vs. $n^2$ for naive method).
• Numerically stable (reduces rounding errors).

---

Exam Tip: How to Score Full Marks in Unit 1

1. Key Topics to Master

2. Common Pitfalls to Avoid

• Ignoring error bounds: Always state whether you’re using absolute/relative error and how it’s calculated.
• Incorrect Taylor expansions: Remember the factorial denominators and signs.
• Stopping criteria: For iterative methods, show both the error check (e.g., $|x_{n+1}-x_n|<ϵ$) and the function value ($|f(x)|<\text{tolerance}$).
• Horner’s method misuse: Ensure coefficients are ordered from highest to lowest degree.

3. Model Answer Structure

For theoretical questions (e.g., "Define absolute error and discuss bisection method"):

1. Definition (1 mark).
2. Key properties (e.g., bisection’s linear convergence, error bound formula) (2 marks).
3. Algorithm steps (with pseudocode if possible) (3 marks).
4. Example trace (show 2-3 iterations) (3 marks).
5. Advantages/disadvantages (1 mark).

For computational questions (e.g., "Solve using Newton-Raphson"):

1. Write the formula and state $f(x)$ and $f^{\prime }(x)$ (1 mark).
2. Show iteration table with all columns (3 marks).
3. State stopping criterion and final answer (1 mark).
4. Discuss convergence (e.g., "Method converged quadratically") (1 mark).

4. High-Scoring Techniques

• Derivations: Always show how you arrived at a formula (e.g., Taylor expansion steps).
• Error analysis: For iterative methods, compute both absolute and relative errors at the final step.
• Comparisons: If asked about multiple methods (e.g., bisection vs. Newton-Raphson), use a table to highlight speed, convergence, and requirements.
• Units and precision: State whether answers are correct to 3 decimal places, 3 significant figures, etc.

5. Past Exam Patterns

• 2022 TU Exam: Derive Newton-Raphson + solve $x^4-x-10=0$ (10 marks).
  • Key: Show $f^{\prime }(x)=4x^3-1$ and iteration table with error checks.
• 2021 PU Exam: Compare bisection and Newton-Raphson for $f(x)=x^2-e^{-x}-3$.
  • Key: Use a table with iterations, errors, and convergence rates.
• 2020 NEB Exam: Evaluate polynomial using Horner’s method + discuss its advantage.
  • Key: Show step-by-step computation and mention "reduces multiplications from $O(n^2)$ to $O(n)$".

---

Summary Checklist

Before submitting, verify: ✅ All error types (absolute/relative/truncation/rounding) are clearly defined. ✅ Taylor series expansions include all terms and truncation error. ✅ Iterative methods show full iteration tables with error checks. ✅ Horner’s method is applied correctly (order of coefficients). ✅ Exam tips are tailored to past question patterns.