Opinion and searsearch
Requirements:
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.
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(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(x)
- Linear system Ax=b
d) Interpret geometrically what a large condition number implies.
Expected demonstration:
(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:
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:
- If the problem is very well-conditioned.
- If perturbations remain small relative to solution scale.
- If instability grows slowly (e.g., sub-exponentially).
- If input data is low-noise.
- If error cancellation occurs.
- 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
| Section | Weight |
|---|---|
| Error Theory | 20% |
| Conditioning | 15% |
| Stability Analysis | 20% |
| Combined Error Modeling | 20% |
| Case Study | 15% |
| Critical Reflection | 10% |