Fixed-Point Iteration

The Central Idea

A number \(r\) is a fixed point of a function \(g\) if

Fixed-point iteration begins with an initial estimate \(x_0\) and repeatedly applies

If the sequence converges to a limit \(r\), and \(g\) is continuous at \(r\), then

The limiting value is therefore a fixed point of \(g\).

What Is a Fixed Point?

A fixed point is an input that a function sends back to itself.

For example, let

A fixed point satisfies

Solving,

Indeed,

Fixed Points and Equations

Many equations can be rewritten so that their solutions become fixed points.

Suppose we want to solve

If the equation can be rearranged into

then every solution of the original equation that preserves the rearrangement is a fixed point of \(g\).

From Equation to Iteration Rule

Consider

Rearrange:

This suggests the iteration

Example: Beginning the Iteration

Use

with

Then

Next,

Continuing the Iteration

Continue:

The sequence alternates around the root while gradually moving closer.

The real solution is approximately

An Iteration Table

Fixed-point iterations are often organized in a table.

A longer table makes the convergence easier to observe.

Fixed-Point Iteration Is Repeated Substitution

If

then

and so on.

Each new estimate is created by substituting the previous estimate into the same function.

Graphical Meaning of a Fixed Point

A fixed point satisfies

and

at the same point.

Therefore, fixed points are the \(x\)-coordinates where the graphs of

and

intersect.

The Line \(y=x\)

The line

plays a special role in fixed-point iteration.

At a fixed point \(r\),

so the point

lies on both \(y=g(x)\) and \(y=x\).

Cobweb Interpretation

Fixed-point iteration can be visualized graphically.

Starting at \(x_0\):

1. move vertically to the graph \(y=g(x)\);
2. move horizontally to the line \(y=x\);
3. repeat.

The resulting path is often called a cobweb diagram.

If the path contracts toward an intersection, the iteration converges.

Convergence

A fixed-point iteration converges when the sequence

approaches a limiting value \(r\).

Symbolically,

If \(g\) is continuous at \(r\), then the limit must satisfy

Divergence

An iteration diverges when the successive values do not approach the desired finite fixed point.

Divergence may appear as:

• unbounded growth;
• persistent oscillation;
• cycling among several values;
• movement toward another fixed point;
• failure of the formula because an operation becomes undefined.

The Same Equation Can Produce Different Iterations

A crucial feature of fixed-point methods is that one equation can often be rearranged in several ways.

Consider

One rearrangement is

giving

Another is

giving a very different iteration.

A Poor Rearrangement Can Fail

Use

with

Then

The sequence cycles between \(1\) and \(3\).

It does not converge to \(\sqrt3\).

A Better Rearrangement

Now use

with

Then

This iteration converges rapidly to

Why the Rearrangement Matters

Algebraically equivalent formulas can behave very differently when used as iteration rules.

The equation

determines the fixed point, but the shape of \(g\) near that point strongly affects whether nearby iterates move toward or away from it.

The Derivative Test: The Main Local Idea

Near a fixed point \(r\), the magnitude of

gives important information about local behavior.

Roughly:

tends to pull nearby points toward the fixed point, while

tends to push nearby points away.

Why \(|g'(r)|<1\) Encourages Convergence

If \(x_n\) is near the fixed point \(r\), then a linear approximation gives

Since

we obtain

Therefore, if

the error is locally multiplied by a factor whose magnitude is less than \(1\).

Positive and Negative Derivatives

If

Example of Alternating Convergence

Recall

Then

Near the positive fixed point \(r\approx0.682328\), the derivative is negative with magnitude less than \(1\).

This is consistent with the observed pattern of alternating convergence.

When \(|g'(r)|>1\)

If

small errors near the fixed point are typically enlarged rather than reduced.

The fixed point is then locally repelling for the iteration.

A nearby starting value will generally not converge to that fixed point.

The Borderline Case \(|g'(r)|=1\)

If

the simple derivative test does not decide the outcome.

Higher-order behavior may produce convergence, divergence, or neutral behavior.

More analysis is needed.

A Stronger Interval Condition

A useful sufficient condition is available when an interval

satisfies both:

1. \(g(x)\in I\) for every \(x\in I\);
2. \(|g'(x)|\le k<1\) for every \(x\in I\).

Under these conditions, the iteration has a unique fixed point in the interval and starting values in the interval converge to it.

This is a standard contraction principle.

Mapping an Interval into Itself

The condition

means that once the iteration enters the interval, the update rule keeps future iterates inside it.

This helps prevent the sequence from escaping into an unrelated region.

Contraction

A function acts like a contraction on an interval when it consistently reduces distances.

A derivative bound

provides one common way to establish this behavior.

The smaller \(k\) is, the stronger the contraction tends to be.

Estimated Rate of Convergence

Near a fixed point,

If

then the error may shrink by roughly a factor of \(0.2\) per iteration near the fixed point.

If

convergence may be much slower.

Choosing a Starting Value

Fixed-point iteration requires an initial guess

Useful starting values may come from:

• a graph;
• a numerical table;
• a bracketing interval;
• physical constraints;
• previous calculations;
• simple nearby values.

Initial Guess and Basin of Attraction

A fixed point may attract some starting values but not others.

The collection of starting values that converge to a particular fixed point is called its basin of attraction.

In elementary work, the practical lesson is simple: a reasonable starting estimate matters.

Example: Solving \(x=\cos x\)

Consider

The equation is already in fixed-point form with

Use the iteration

Beginning the Cosine Iteration

Let

Then

The values oscillate while gradually narrowing around the fixed point.

Continuing the Cosine Iteration

Further iterations give

The sequence approaches

Why the Cosine Iteration Converges

Here,

At the fixed point \(r\approx0.739085\),

The magnitude is less than \(1\), which is consistent with local convergence.

Residual Checking

If \(x_n\) is intended to solve

evaluate

A small value of

supports the claim that \(x_n\) is close to satisfying the original equation.

Fixed-Point Residual

For the fixed-point equation

one natural residual is

At an exact fixed point,

Stopping by Successive Difference

A common stopping condition is

This checks whether the sequence is changing by less than a specified tolerance.

It is easy to compute because both values are already available.

Stopping by Residual

Another condition is

If solving an original equation \(f(x)=0\), we may instead require

These checks ask whether the current estimate nearly satisfies the target equation.

Using More Than One Stopping Condition

A robust implementation may require both

and

This checks both stability of the iteration and satisfaction of the equation.

Maximum Iteration Safeguard

Fixed-point iteration is not guaranteed to converge for every rule and starting value.

Therefore, computational implementations should also include a maximum iteration count such as

If convergence has not occurred by then, the algorithm can stop and report failure to meet the tolerance.

Fixed-Point Iteration in Pseudocode

set x = initial guess

repeat
    new_x = g(x)

    if stopping condition is satisfied
        return new_x

    x = new_x
until maximum iterations are reached

This simple loop captures the basic structure of the method.

Adding a Residual Check

set x = initial guess

repeat
    new_x = g(x)

    if abs(new_x - x) < tolerance
       and abs(f(new_x)) < tolerance
        return new_x

    x = new_x
until maximum iterations are reached

The exact stopping logic depends on the problem and the error guarantees required.

Fixed-Point Iteration versus Bisection

Bisection maintains a bracket:

Fixed-point iteration usually maintains a single current estimate:

Bisection offers strong interval guarantees under its assumptions.

Fixed-point iteration can be faster or simpler, but its convergence depends more strongly on the chosen update rule.

Fixed-Point Iteration versus Direct Algebra

If an equation has a simple exact algebraic solution, fixed-point iteration may be unnecessary.

For example,

is solved immediately by

Numerical iteration is most useful when direct algebra is unavailable, inconvenient, or embedded inside a larger computational process.

Fixed-Point Iteration as a Building Block

Many important numerical methods can be interpreted as specialized fixed-point iterations.

Newton's method, for example, updates by

This can be viewed as

for a particular choice of \(g\).

Common Error: Assuming Any Rearrangement Will Work

Algebraic equivalence does not guarantee numerical convergence.

Two formulas may have the same fixed point but very different iterative behavior.

The rule

illustrates this danger for \(x^2=3\).

Common Error: Ignoring the Starting Value

A convergent rule near one fixed point may fail from a distant starting value.

Always consider whether the initial guess lies in a region where the update rule is defined and expected to converge.

Common Error: Dividing by Zero

Some iteration formulas contain denominators.

For example,

is undefined when

Domain restrictions must be checked before and during iteration.

Common Error: Treating a Repeating Cycle as Convergence

The sequence

does not converge merely because it repeats predictably.

Convergence requires the sequence to approach a single limiting value.

Common Error: Stopping Because Several Digits Look Similar

Visual similarity is not a mathematical stopping rule.

Use a criterion such as

or

Common Error: Reporting More Precision Than the Iteration Supports

If the stopping tolerance controls only about four decimal places, reporting twelve digits suggests unjustified accuracy.

The reported precision should match the numerical evidence.

Common Error: Forgetting the Original Equation

The purpose of fixed-point iteration is to solve the original problem.

After convergence, substitute the approximation into the original equation or compute its residual.

This guards against algebraic rearrangement errors and unintended fixed points.

A Reliable Fixed-Point Workflow

1. Write the target equation clearly.
2. Rearrange it into \(x=g(x)\).
3. Check domain restrictions introduced by the rearrangement.
4. Choose a reasonable initial guess \(x_0\).
5. Examine \(g'(x)\) near the expected fixed point when possible.
6. Compute \(x_{n+1}=g(x_n)\).
7. Record the successive estimates.
8. Apply a stated stopping condition.
9. Impose a maximum iteration count.
10. Verify the final approximation in the original equation.

Example: Full Workflow for \(x=\cos x\)

Solve

The equation already has the form

with

Choose

Iterate:

Continue until

Verifying the Cosine Solution

The iteration gives approximately

Check:

Equivalently, for

the residual is close to zero.

Practice 1: Identify the Fixed Point

Find the fixed point of

Practice 2: Generate Iterates

Let

Compute \(x_1,x_2,x_3,x_4\).

Practice 3: Rearrange into Fixed-Point Form

Rewrite

in the form

by isolating the linear \(x\)-term.

Practice 4: Detect a Cycle

Use

Compute the first four iterates and describe the behavior.

Practice 5: Derivative Test

A fixed point \(r\) satisfies

What does this suggest about local convergence?

Practice 6: Repelling Fixed Point

A fixed point satisfies

What does this suggest about nearby iteration?

Practice 7: Stopping Condition

Suppose

and

Does the condition

hold?

Practice 8: Fixed-Point Residual

If

and

write the fixed-point residual.

Practice 9: Domain Check

Why is

invalid for the iteration

Practice 10: Compare Methods

State one major advantage of bisection and one major advantage of fixed-point iteration.

Practice Answers

Practice 1

Solve

Then

Practice 2

Therefore,

Practice 3

From

isolate \(x\):

Therefore, one fixed-point form is

Whether the associated iteration converges is a separate numerical question.

Practice 4

The sequence cycles between \(1\) and \(4\) rather than converging to the positive solution \(2\).

Practice 5

Since

the fixed point is locally attracting, so nearby starting values are expected to converge under appropriate smoothness conditions.

Practice 6

Since

the fixed point is locally repelling, so nearby errors tend to grow.

Practice 7

Since

the condition is satisfied.

Practice 8

The fixed-point residual is

Practice 9

The iteration contains the term

If

the first update requires division by zero, so the iteration is undefined.

Practice 10

Bisection provides a strong bracket and predictable error reduction when its conditions hold.

Fixed-point iteration can use a very simple one-value update and may converge efficiently when a good iteration function is chosen.

What to Remember

• A fixed point satisfies \(g(r)=r\).
• Fixed-point iteration uses \(x_{n+1}=g(x_n)\).
• Solutions of an equation can often be found by rewriting it as \(x=g(x)\).
• Different rearrangements of the same equation can behave very differently.
• Local convergence is often associated with \(|g'(r)|<1\).
• If \(|g'(r)|>1\), the fixed point is typically locally repelling.
• The case \(|g'(r)|=1\) requires additional analysis.
• Starting values and domain restrictions matter.
• Stopping conditions should use numerical criteria, not visual judgment.
• The final approximation should be checked against the original equation.

Where We Go Next

Fixed-point iteration shows how a carefully chosen update rule can move a single estimate toward a solution. The next method uses local slope information to construct a particularly powerful update rule.

The next lesson, Newton's Method, uses tangent lines and derivatives to generate approximations that often converge much faster than basic fixed-point iteration.