From the free course Numerical Analysis and Computational Methods on Lykke
Midterm Review and Practice
Key concepts: Algorithm Implementation · Error Bound Calculation · Method Comparison
Synthesis of material from the first half of the course to prepare for formal assessment.
Midterm Review and Practice
The transition from theoretical mathematics to numerical computing requires a fundamental shift in perspective. In pure mathematics, we often deal with infinite precision and exact solutions; in numerical analysis, we operate in a world of approximations, floating-point arithmetic, and iterative convergence. This midterm review serves as a rigorous synthesis of the first half of the course, bridging the gap between Python implementation and the mathematical bounds that govern algorithmic reliability.
Foundational Computing in Python
Before diving into complex algorithms, a mastery of the computational environment is required. Python serves as our primary vehicle due to its high-level abstraction and robust scientific libraries. Unlike lower-level languages like C++ or Java, Python utilizes implicit typing and dynamic memory management, which allows the researcher to focus on the logic of the numerical method rather than the boilerplate of the machine architecture.
Variable Handling and Type Inference
In Python, variables are essentially pointers to objects in memory. When you assign x = 10.0, Python interprets this as a float; x = 10 is interpreted as an integer. For numerical analysis, this distinction is critical because integer division and floating-point division can yield different results in older versions of languages, though Python 3 defaults to float division with the / operator.
The Implicit Typing Rule: Python determines the data type at runtime based on the value assigned. Use the
type()function to debug precision issues, especially when dealing with large arrays or matrices whereint64versusfloat64can impact memory and result accuracy.
Operator Precedence and Logic
Numerical algorithms often involve complex nested equations. Understanding the order of operations is the first line of defense against "silent errors"—code that runs without crashing but produces the wrong answer.
| Precedence | Operator | Description |
|---|---|---|
| 1 (Highest) | ** |
Exponentiation |
| 2 | +x, -x, ~x |
Unary plus, minus, and bitwise NOT |
| 3 | *, /, //, % |
Multiplication, Division, Floor division, Modulo |
| 4 | +, - |
Addition, Subtraction |
| 5 | <<, >> |
Bitwise shifts |
| 6 | & |
Bitwise AND |
| 7 | ^ |
Bitwise XOR |
| 8 | | |
Bitwise OR |
| 9 (Lowest) | ==, !=, >, <, etc. |
Comparisons and Identity |
Root-Finding Algorithms: Theory and Implementation
Root-finding is the process of finding a value $x$ such that $f(x) = 0$. This is a cornerstone of numerical computing, used in everything from optimizing structural loads to calculating the internal rate of return in finance.
1. The Bisection Method
The Bisection Method is a "bracketing" method based on the Intermediate Value Theorem. If a continuous function $f(x)$ changes sign over an interval $[a, b]$, a root must exist within that interval.
- How it works: The algorithm repeatedly halves the interval and selects the sub-interval where the sign change occurs.
- Convergence: It is guaranteed to converge if the function is continuous and the initial signs differ. However, it is relatively slow, possessing linear convergence.
- Error Bound: After $n$ iterations, the maximum possible error is: $$E_n = \frac{b - a}{2^n}$$
2. Newton-Raphson Method
The Newton-Raphson Method is an "open" method that uses the derivative of the function to find the root. It approximates the function as a tangent line and finds where that line crosses the x-axis.
- Algorithm: $x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$
- Convergence: When it works, it is extremely fast, exhibiting quadratic convergence ($e_{n+1} \approx Ce_n^2$).
- Pitfalls: It requires the derivative $f'(x)$, and it can fail if $f'(x)$ is zero or if the initial guess $x_0$ is too far from the actual root.
3. Method Comparison for Midterm Preparation
| Feature | Bisection Method | Newton-Raphson Method | Secant Method |
|---|---|---|---|
| Convergence Rate | Linear | Quadratic | Superlinear (~1.618) |
| Requirements | Sign change in $[a, b]$ | Initial guess $x_0$, $f'(x)$ | Two initial guesses |
| Stability | Always converges | Can diverge/oscillate | Can diverge |
| Computational Cost | Low (1 function eval) | High (func + deriv eval) | Medium (1 function eval) |
Implementation Review: Python Code for Root Finding
In the midterm, you may be asked to identify errors in code or complete a function. Below are the standard implementations for the two primary methods.
def bisection_method(f, a, b, tol, max_iter):
"""
Implements the Bisection Method to find a root of f(x) = 0.
"""
if f(a) * f(b) >= 0:
print("Bisection method fails: Sign does not change.")
return None
for i in range(max_iter):
c = (a + b) / 2
if abs(f(c)) < tol or (b - a) / 2 < tol:
return c
if f(c) * f(a) < 0:
b = c
else:
a = c
return (a + b) / 2
def newton_method(f, df, x0, tol, max_iter):
"""
Implements Newton-Raphson Method.
f: function, df: derivative of f.
"""
x = x0
for i in range(max_iter):
fx = f(x)
dfx = df(x)
if abs(dfx) < 1e-12: # Avoid division by zero
print("Derivative too small; method fails.")
return None
x_new = x - fx / dfx
if abs(x_new - x) < tol:
return x_new
x = x_new
return x
Linear Systems and Gaussian Elimination
Solving systems of linear equations ($Ax = b$) is the "heavy lifting" of numerical analysis. For the midterm, you must understand both the manual trace and the algorithmic complexity.
Gaussian Elimination Steps
- Forward Elimination: Transform the matrix $A$ into an upper triangular matrix $U$ using row operations.
- Back Substitution: Solve for the variables starting from the last row.
Pivoting Strategies
Numerical instability occurs when a pivot element (the diagonal element used to eliminate others) is very close to zero. This leads to massive rounding errors.
- Partial Pivoting: Before eliminating a column, swap the current row with the row below it that has the largest absolute value in the pivot column. This is the standard for most robust implementations.
Complexity Analysis
The computational cost of these operations is measured in FLOPS (Floating Point Operations).
| Stage | Complexity (Big O) | Notes |
|---|---|---|
| Forward Elimination | $O(n^3)$ | Dominant cost; involves nested loops. |
| Back Substitution | $O(n^2)$ | Relatively cheap. |
| Total | $O(n^3)$ | Scaling is cubic; doubling $n$ increases time by $8\times$. |
Error Analysis and Bounds
A numerical solution without an error estimate is often useless. In this course, we categorize errors into three main types:
- Truncation Error: Arises from approximating a mathematical process (e.g., using a finite Taylor series to represent $e^x$).
- Round-off Error: Arises from the finite precision of computer memory (e.g., representing $1/3$ as $0.33333333$).
- Absolute vs. Relative Error:
- Absolute Error: $|x_{true} - x_{approx}|$
- Relative Error: $\frac{|x_{true} - x_{approx}|}{|x_{true}|}$
Machine Epsilon ($\epsilon$ ): The smallest positive number such that $1.0 + \epsilon \neq 1.0$. In standard 64-bit floats (double precision), $\epsilon \approx 2.22 \times 10^{-16}$.
Error Bound Calculation Example
If we use the Bisection method on the interval $[1, 2]$ and we want an error less than $10^{-4}$, how many iterations $n$ are required?
Using the formula $E_n = \frac{b-a}{2^n} < \text{tol}$: $$\frac{2-1}{2^n} < 10^{-4}$$ $$1 < 10^{-4} \cdot 2^n$$ $$10^4 < 2^n$$ $$\log_2(10000) < n$$ $$n > 13.28$$ Therefore, 14 iterations are required.
Common Exam Patterns and Pitfalls
Based on previous recitations and practice materials, the midterm often focuses on the following "trap" areas:
1. Convergence Failure
- Newton's Method: If the function has a local minimum/maximum near the root, the derivative $f'(x)$ will be near zero, sending the next guess $x_{n+1}$ to infinity.
- Bisection: If the function is tangent to the x-axis (e.g., $f(x) = x^2$), the sign does not change, and Bisection cannot even start.
2. Manual Matrix Tracing
When performing Gaussian Elimination by hand:
- Mistake: Forgetting to apply the row operation to the vector $b$ (the right-hand side).
- Mistake: Sign errors during subtraction ($R_2 = R_2 - m \cdot R_1$).
3. Floating Point Logic
- Comparison: Never use
if x == 0.1:in Python. Due to binary representation,0.1 + 0.2does not exactly equal0.3. Always use a tolerance:if abs(x - 0.1) < 1e-9:.
Practice Problem Walkthrough
Problem: Find the root of $f(x) = x^3 - x - 1$ using Newton's Method, starting at $x_0 = 1.5$. Perform two iterations.
Step 1: Find the derivative. $f'(x) = 3x^2 - 1$
Step 2: Iteration 1. $f(1.5) = (1.5)^3 - 1.5 - 1 = 3.375 - 1.5 - 1 = 0.875$ $f'(1.5) = 3(1.5)^2 - 1 = 3(2.25) - 1 = 6.75 - 1 = 5.75$ $x_1 = 1.5 - \frac{0.875}{5.75} \approx 1.5 - 0.15217 = 1.34783$
Step 3: Iteration 2. $f(1.34783) \approx (1.34783)^3 - 1.34783 - 1 \approx 2.448 - 1.34783 - 1 = 0.10017$ $f'(1.34783) \approx 3(1.34783)^2 - 1 \approx 3(1.8166) - 1 = 4.4498$ $x_2 = 1.34783 - \frac{0.10017}{4.4498} \approx 1.34783 - 0.02251 = 1.32532$
Analysis: Notice how quickly $f(x)$ approaches zero. In just two steps, the value dropped from $0.875$ to $0.100$. This demonstrates the power of quadratic convergence.
- Bisection Method: A root-finding method that repeatedly bisects an interval and then selects a subinterval in which a root must lie for further processing.
- Newton-Raphson Method: An iterative method for finding the roots of a differentiable function $f$, which are solutions to the equation $f(x) = 0$.
- Gaussian Elimination: An algorithm in linear algebra for solving a system of linear equations, finding the rank of a matrix, and calculating the inverse of an invertible square matrix.
- Partial Pivoting: A technique used in Gaussian elimination to improve numerical stability by swapping rows to ensure the pivot element is the largest possible in its column.
- Relative Error: The ratio of the absolute error of a measurement to the actual measurement.
- Machine Epsilon: The upper bound on the relative error due to rounding in floating-point arithmetic.
- Quadratic Convergence: A property of an iterative method where the number of correct digits roughly doubles with each iteration.
- Forward Elimination: The first phase of Gaussian elimination that reduces a matrix to upper triangular form.
- Back Substitution: The process of solving an upper triangular system of linear equations.
- Truncation Error: The error made by truncating an infinite sum and approximating it by a finite sum.
- Which method is guaranteed to converge for a continuous function if the initial interval brackets a root?
- A) Newton-Raphson
- B) Secant Method
- C) Bisection Method
- D) Gaussian Elimination
- What is the Big O complexity of the Forward Elimination phase in Gaussian Elimination for an $n \times n$ matrix?
- A) $O(n)$
- B) $O(n^2)$
- C) $O(n^3)$
- D) $O(2^n)$
- If the absolute error is $0.001$ and the true value is $100$, what is the relative error?
- A) 0.001
- B) 0.00001
- C) 0.1
- D) 1.0
- Why is partial pivoting used in Gaussian Elimination?
- A) To speed up the calculation.
- B) To reduce the memory footprint.
- C) To avoid division by zero or very small numbers.
- D) To make the matrix symmetric.
- In Python, what is the result of
2 ** 3 * 2?- A) 12
- B) 16
- C) 64
- D) 8
- Which convergence rate is associated with the Newton-Raphson method?
- A) Linear
- B) Quadratic
- C) Cubic
- D) Logarithmic
Answers: 1-C, 2-C, 3-B, 4-C, 5-B, 6-B.
Midterm Preparation Checklist
- Python Proficiency: Can you write a
forloop that implements an iterative sum? Do you understand howif/elif/elseblocks control the flow of the Bisection method? - Root-Finding Mechanics: Practice solving $f(x) = 0$ manually for 2-3 iterations using both Bisection and Newton.
- Error Estimation: Be prepared to solve for $n$ (number of iterations) given a target tolerance and an initial interval.
- Linear Algebra: Practice Gaussian Elimination on a 3x3 matrix. Ensure you can perform back-substitution without calculation errors.
- Method Selection: Know the pros and cons of each method. If a function is expensive to evaluate and you don't have the derivative, which method should you use? (Answer: Secant).
- Conceptual Definitions: Be able to define Machine Epsilon, Truncation Error, and the difference between Absolute and Relative error.
- Code Debugging: Look at a snippet of Gaussian elimination code and identify where the pivoting logic should be inserted.

Source Materials
Study Numerical Analysis and Computational Methods on Lykke
This course page is free to open: signed out, you can read its first two sections, and signing in, on any plan, opens the rest. The free Lykke Chrome extension syncs your own Canvas courses, so ChatGPT, Claude and Muse can answer from your classes and deadlines. It only reads Canvas.
Add the free extensionSign in to open every sectionAll sections of Numerical Analysis and Computational Methods · Browse more course pages