Convergence Concepts in Root-Finding I

students, imagine trying to find the exact spot where a curve crosses the $x$-axis. In many real problems, the answer cannot be found neatly with algebra, so numerical methods give us repeated estimates instead. The big question is: do those estimates improve and settle down near the true root, or do they wander forever? That is the heart of convergence ✨

In this lesson, you will learn how convergence works in root-finding, why it matters, and how to tell whether a method is likely to succeed. By the end, you should be able to:

explain the main ideas and language of convergence,
use basic numerical reasoning to judge whether an iteration is converging,
connect convergence to methods like bisection and fixed-point iteration,
describe why convergence is a central idea in Root-Finding I,
support your understanding with simple examples and evidence.

What Convergence Means

In numerical analysis, a method is said to converge if its sequence of approximations gets closer and closer to the exact answer. For root-finding, the exact answer is a root $r$ of a function $f(x)$, meaning $f(r)=0$.

Suppose a method generates numbers $x_0, x_1, x_2, \dots$. If these values approach the root $r$ as the number of steps increases, then we write $x_n \to r$ as $n \to \infty$. This means the error usually becomes smaller over time, where the error at step $n$ is often written as $e_n = x_n - r$.

A method may also fail to converge. It might oscillate, move away from the root, or settle on the wrong value. So convergence is not just about getting an answer, but about getting the right answer in a stable way 📈

A key idea is that convergence is about the behavior of a sequence, not just one step. One lucky estimate does not prove success. We care about the full pattern of improvement.

Measuring Improvement: Error and Tolerance

To understand convergence, we need a way to measure accuracy. A common idea is absolute error, which is $|x_n-r|$. This tells us how far the approximation is from the true root.

In practice, the exact root $r$ is usually unknown, so we often use a stopping rule based on changes between approximations. For example, if $|x_{n+1}-x_n|$ becomes very small, then the method may be close to convergence. A computer program may stop when the change is less than a chosen tolerance $\varepsilon$, such as $10^{-6}$.

A typical stopping condition might be

$$|x_{n+1}-x_n|<\varepsilon.$$

This does not prove the root is exact, but it gives a practical signal that the estimate is stable enough for use.

students, think of a navigation app that keeps updating your location. If each update changes only a tiny amount, the app is probably settling on your true position. That is similar to convergence in a numerical method 🚗

Bisection Method and Guaranteed Convergence

The bisection method is one of the most reliable root-finding methods because it has a strong convergence guarantee under the right conditions. If $f$ is continuous on $[a,b]$ and $f(a)$ and $f(b)$ have opposite signs, then by the Intermediate Value Theorem there is at least one root in the interval.

The method repeatedly halves the interval:

find the midpoint $m=\frac{a+b}{2}$,
check the sign of $f(m)$,
keep the half-interval that still contains a sign change.

Because the interval length is cut in half each time, the error bound also shrinks predictably. After $n$ steps, the interval length is

$$\frac{b-a}{2^n}.$$

This shows why bisection converges. The estimates get trapped in a smaller and smaller interval that still contains the root.

The convergence is linear in a broad sense, meaning the error decreases by a constant factor each step. It is not the fastest method, but it is dependable. That is why bisection is often used when reliability matters more than speed.

Example: if $f(x)=x^2-2$ on $[1,2]$, then $f(1)=-1$ and $f(2)=2$. Since the signs differ, a root lies in the interval. Bisection will repeatedly narrow the interval until the approximation is sufficiently accurate. The true root is $\sqrt{2}$, and the approximations move steadily toward it.

Fixed-Point Iteration and Convergence

Fixed-point iteration works differently. Instead of solving $f(x)=0$ directly, we rewrite the problem as

$$x=g(x),$$

then generate approximations using

$$x_{n+1}=g(x_n).$$

A value $r$ is a fixed point if $r=g(r)$.

Convergence here depends on the function $g$. If the iteration gets closer to a fixed point, then it converges. If not, it may diverge or oscillate. A useful idea is the derivative test: if $g$ is differentiable near the fixed point and

$$|g'(r)|<1,$$

then the iteration is likely to converge locally. If

$$|g'(r)|>1,$$

it often diverges near that point.

This condition makes intuitive sense. If the graph of $g$ is too steep near the fixed point, small errors can grow. If it is flat enough, errors tend to shrink.

Example: solve $x=\cos x$. We can use

$$x_{n+1}=\cos(x_n).$$

This iteration converges to the fixed point near $0.739$ if started from a reasonable initial guess, such as $x_0=1$. Since the derivative is $g'(x)=-\sin x$, and near the solution $|g'(r)|<1$, the sequence settles down.

But not every rearrangement is good. For instance, rewriting the same equation in a different way may produce an iteration that diverges. So the choice of $g(x)$ is important.

Types of Convergence and Why Speed Matters

Not all convergent methods behave at the same speed. Numerical analysis often describes how fast the error shrinks.

A sequence $x_n$ converges to $r$ with linear convergence if, roughly speaking, the error decreases by about a constant factor each step. In simple terms, if the error is multiplied by a number less than $1$ each time, the method is linearly convergent.

A method with quadratic convergence is much faster. That means the error shrinks roughly like the square of the previous error. If the error is already small, squaring it makes it much smaller. Newton’s method is a famous example of a method that can converge quadratically under suitable conditions.

Why does this matter? Because in real applications, speed saves time and computing power. A slower method may still be useful if it is robust. A faster method may be better if it is stable and started close enough to the root.

Example: if one method reduces the error from $10^{-2}$ to about $10^{-4}$ in one step, that is much faster than reducing it to about $5\times10^{-3}$. Faster convergence means fewer iterations to reach the same tolerance.

How to Judge Convergence in Practice

When using root-finding algorithms, students, you usually look for evidence rather than proof. Here are common signs that a method is converging:

successive approximations are changing less and less,
the function values $f(x_n)$ are moving closer to $0$,
the estimates remain in a sensible region near the expected root,
the stopping rule based on tolerance is nearly satisfied.

However, small changes alone are not enough. A method could appear to stabilize while still not being near a root. That is why it helps to check both $|x_{n+1}-x_n|$ and $|f(x_n)|$.

For example, if $|f(x_n)|$ is close to $0$, then the approximation is likely useful. If the values are not close to $0$, a small change between iterates may be misleading. Good numerical practice uses multiple checks 🧠

A graph can also help. If the approximations jump around or move away from the $x$-axis, the method may not be converging. If they cluster near the crossing point, convergence is likely.

Connection to Root-Finding I

Convergence concepts are the glue that holds Root-Finding I together. Bisection, fixed-point iteration, and other methods are not only about producing numbers. They are about producing numbers that improve in a controlled way.

In bisection, convergence is guaranteed by interval shrinking and sign changes. In fixed-point iteration, convergence depends on the behavior of $g(x)$ near the fixed point. In both cases, the main goal is to move from a rough guess to a dependable root approximation.

This lesson also prepares you for later root-finding ideas. More advanced methods often aim for better convergence speed while keeping accuracy and stability. If you understand convergence now, later methods like Newton-type algorithms will make much more sense.

Conclusion

Convergence tells us whether a numerical method is actually getting closer to the answer. In root-finding, that answer is a root $r$ such that $f(r)=0$. The bisection method gives guaranteed convergence under the right conditions, while fixed-point iteration depends on the choice of $g(x)$ and the behavior of $g'(x)$ near the fixed point. Different methods can converge at different speeds, and the rate of convergence affects efficiency.

The main idea is simple but powerful: a good numerical method does not just produce guesses, it produces better guesses over time. That is why convergence is one of the most important ideas in Numerical Analysis ✅

Study Notes

Convergence means a sequence of approximations gets closer to the true root $r$.
In root-finding, the goal is to solve $f(r)=0$.
A common error measure is $|x_n-r|$, but in practice the root is often unknown.
A practical stopping rule is $|x_{n+1}-x_n|<\varepsilon$.
The bisection method converges when $f$ is continuous and $f(a)$ and $f(b)$ have opposite signs.
In bisection, the interval length after $n$ steps is $\frac{b-a}{2^n}$.
Fixed-point iteration uses $x_{n+1}=g(x_n)$ and seeks a fixed point $r=g(r)$.
A useful local convergence test for fixed-point iteration is $|g'(r)|<1$.
Linear convergence means the error shrinks by about a constant factor each step.
Quadratic convergence is much faster and often reduces error dramatically.
To judge convergence in practice, check both $|x_{n+1}-x_n|$ and $|f(x_n)|$.
Convergence concepts connect all of Root-Finding I and prepare you for more advanced methods.