From the free course CS323: Numerical Analysis and Computing on Lykke

Root-Finding Algorithms

Key concepts: Bisection Method · Newton's Method · Secant Method · Fixed-Point Iteration · Order of Convergence

Numerical techniques for finding the zeros of nonlinear functions.

Root-Finding Algorithms

Overview

Finding the root of $f(x) = 0$ is a fundamental problem in optimization and science. This section compares methods based on their speed and reliability.

Key Concepts

  • Bisection Method: Reliable and robust; uses the Intermediate Value Theorem to narrow down an interval. Slow (linear convergence).
  • Newton's Method: Uses the derivative to find roots. Extremely fast (quadratic convergence) but requires a good initial guess and the derivative $f'(x)$.
  • Secant Method: A variation of Newton's that approximates the derivative using two points. Faster than bisection but slower than Newton.
  • Fixed-Point Iteration: Rewriting $f(x) = 0$ as $x = g(x)$ and iterating. Convergence depends on the magnitude of $g'(x)$.

Comparison

Midterm #2 materials emphasize the trade-offs between these methods, particularly regarding their convergence rates and computational cost per iteration.

Source Materials

Study CS323: Numerical Analysis and Computing 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 CS323: Numerical Analysis and Computing · Browse more course pages