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 where int64 versus float64 can 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

  1. Forward Elimination: Transform the matrix $A$ into an upper triangular matrix $U$ using row operations.
  2. 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:

  1. Truncation Error: Arises from approximating a mathematical process (e.g., using a finite Taylor series to represent $e^x$).
  2. Round-off Error: Arises from the finite precision of computer memory (e.g., representing $1/3$ as $0.33333333$).
  3. 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.2 does not exactly equal 0.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.
  1. 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
  2. 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)$
  3. 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
  4. 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.
  5. In Python, what is the result of 2 ** 3 * 2?
    • A) 12
    • B) 16
    • C) 64
    • D) 8
  6. 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 for loop that implements an iterative sum? Do you understand how if/elif/else blocks 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.
Midterm Review and Practice - Numerical Analysis and Computational Methods - image 1
Midterm Review and Practice - Numerical Analysis and Computational Methods - image 1
Midterm Review and Practice - Numerical Analysis and Computational Methods - diagram 1
Midterm Review and Practice - Numerical Analysis and Computational Methods - diagram 1
Midterm Review and Practice - Numerical Analysis and Computational Methods - diagram 2
Midterm Review and Practice - Numerical Analysis and Computational Methods - diagram 2
Midterm Review and Practice - Numerical Analysis and Computational Methods - diagram 3
Midterm Review and Practice - Numerical Analysis and Computational Methods - diagram 3

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 section

All sections of Numerical Analysis and Computational Methods · Browse more course pages

Midterm Review and Practice — Numerical Analysis and Computational Methods | Lykke