Term Paper Segmentation Guide

Main Research Question

How do truncation errors, rounding errors, and conditioning collectively influence the stability of numerical algorithms, and under what theoretical conditions can an unstable algorithm still produce acceptable results?

SECTION I: Foundations of Error Theory (Conceptual + Theoretical Demonstration)

1. Truncation Error

Students should:

a) Define truncation error formally.
b) Derive truncation error for at least one example:

• Taylor series approximation
• Finite difference derivative
• Numerical integration formula

c) Show how truncation error depends on step size $h$h.
d) Prove the order of accuracy for the chosen method.

Expected demonstration:
Mathematical derivation using Taylor expansion and Big-O notation.

2. Rounding Error

Students should:

a) Define floating-point representation and machine epsilon.
b) Explain how rounding errors accumulate in iterative algorithms.
c) Derive error bounds caused by floating-point arithmetic.
d) Provide an example (e.g., subtraction of nearly equal numbers).

Expected demonstration:
Model floating-point arithmetic as:

$fl\left(x\right)=x(1+),??{}_{machine}$fl(x)=x(1+),??machine

and propagate this through an algorithm.

3. Conditioning of a Problem

Students should:

a) Define well-conditioned vs ill-conditioned problems.
b) Define the condition number of a function and of a matrix.
c) Derive the condition number for:

• Scalar function $f\left(x\right)$f(x)
• Linear system $Ax=b$Ax=b

d) Interpret geometrically what a large condition number implies.

Expected demonstration:

$\left(A\right)=A{A}^1$(A)=AA1

Show sensitivity of solution to perturbations.

SECTION II: Stability of Algorithms

4. Distinguish Conditioning vs Stability

Students must:

a) Explain why conditioning is a property of the problem.
b) Explain why stability is a property of the algorithm.
c) Provide examples where:

• Well-conditioned problem + unstable algorithm
• Ill-conditioned problem + stable algorithm

Expected demonstration:
Formal reasoning, possibly using linear systems.

5. Forward and Backward Error Analysis

Students should:

a) Define forward error.
b) Define backward error.
c) Show how backward stability is used to assess algorithms.
d) Demonstrate backward error analysis for:

• Gaussian elimination
  OR
• Newtons method

Expected demonstration:
Prove that computed solution solves a slightly perturbed problem.

SECTION III: Interaction Between the Three Concepts

6. Combined Error Model

Students must:

a) Construct a total error model:

$\text{Total Error}=\text{Truncation Error}+\text{Rounding Error}$Total Error=Truncation Error+Rounding Error

b) Show how decreasing step size reduces truncation error but increases rounding error.
c) Derive an expression for optimal step size balancing both errors.

Expected demonstration:
Minimize error expression using calculus.

7. Case Study Analysis

Students should analyze one algorithm (choose one):

• Numerical differentiation
• Gaussian elimination
• Eulers method
• Iterative solvers

They must:

a) Identify all three error sources.
b) Analyze how they interact.
c) Discuss stability implications.

SECTION IV: When Can an Unstable Algorithm Still Work?

This is the deeper theoretical part.

Students must investigate:

8. Theoretical Conditions for Acceptable Results

They should analyze and justify:

1. If the problem is very well-conditioned.
2. If perturbations remain small relative to solution scale.
3. If instability grows slowly (e.g., sub-exponentially).
4. If input data is low-noise.
5. If error cancellation occurs.
6. If instability is dominated by truncation error.

They must:

a) Provide at least one mathematical example.
b) Use error bounds to justify conclusions.
c) Provide a counterexample where instability destroys accuracy.

SECTION V: Critical Reflection

Students should conclude by addressing:

• Can a stable algorithm solve an ill-conditioned problem accurately?
• Is backward stability sufficient for reliability?
• How does finite precision arithmetic limit theoretical guarantees?

Optional Grading Structure