Iteration, Recursion, and Search Intervals | Malone Math

The Central Idea

An iteration repeats a computational rule.

A recursive rule defines a new value using one or more earlier values.

A search interval is a restricted range of inputs in which a numerical method looks for a solution.

A typical numerical process has the form

\[ \boxed{ \text{initial information} \longrightarrow \text{repeated rule} \longrightarrow \text{refined result} }. \]

What Is Iteration?

Iteration means repeating a procedure, usually with the output of one step helping determine the next step.

For example, suppose

\[ x_{n+1}=\frac{x_n+4}{2}. \]

Beginning with

\[ x_0=0, \]

we obtain

\[ x_1=\frac{0+4}{2}=2, \] \[ x_2=\frac{2+4}{2}=3, \] \[ x_3=\frac{3+4}{2}=3.5. \]

The rule is applied repeatedly.

Iteration Produces a Sequence

Repeated computation generates a sequence

\[ x_0,\quad x_1,\quad x_2,\quad x_3,\quad\ldots \]

The subscript records the iteration number.

The initial value

\[ x_0 \]

is often called the starting value, initial value, or initial guess.

What Is Recursion?

A recursive definition specifies one or more initial values and gives a rule for producing later values from earlier ones.

For example,

\[ x_0=2, \] \[ \boxed{x_{n+1}=3x_n+1}. \]

Then

\[ x_1=3(2)+1=7, \] \[ x_2=3(7)+1=22, \] \[ x_3=3(22)+1=67. \]

Iteration and Recursion Are Related

Recursion describes how later terms depend on earlier terms.

Iteration is the act of repeatedly applying that rule.

For

\[ x_{n+1}=g(x_n), \]

the formula is recursive, while computing

\[ x_1,\quad x_2,\quad x_3,\quad\ldots \]

is an iterative process.

Indexing Iterations

Numerical methods often begin with an initial estimate \(x_0\).

The next estimate is

\[ x_1, \]

followed by

\[ x_2, \]

and so on.

In general,

\[ x_n \]

denotes the estimate after \(n\) update steps if the initial estimate is indexed by \(0\).

An Update Rule

Many iterative methods can be written as

\[ \boxed{x_{n+1}=g(x_n)}. \]

The function \(g\) is the update rule.

Starting from \(x_0\), evaluate

\[ x_1=g(x_0), \]

then

\[ x_2=g(x_1), \]

and continue.

Example: A Simple Converging Iteration

Consider

\[ x_{n+1}=\frac{x_n+6}{2}, \qquad x_0=0. \]

Then

\[ x_1=3, \] \[ x_2=4.5, \] \[ x_3=5.25, \] \[ x_4=5.625. \]

The values move toward \(6\).

Why \(6\) Is the Limiting Value

If the iteration settles at a value \(L\), then the update should leave that value unchanged:

\[ L=\frac{L+6}{2}. \]

Multiply by \(2\):

\[ 2L=L+6. \]

Therefore,

\[ \boxed{L=6}. \]

A value unchanged by an iteration rule is called a fixed point.

Not Every Iteration Converges

Consider

\[ x_{n+1}=2x_n, \qquad x_0=1. \]

Then

\[ 1,\quad2,\quad4,\quad8,\quad16,\quad\ldots \]

grows without approaching a finite limiting value.

Therefore, repeated calculation alone does not guarantee convergence.

An Iteration Can Oscillate

Consider

\[ x_{n+1}=1-x_n, \qquad x_0=0. \]

Then

\[ x_1=1, \] \[ x_2=0, \] \[ x_3=1, \] \[ x_4=0. \]

The sequence alternates:

\[ 0,\quad1,\quad0,\quad1,\quad\ldots \]

It does not converge to a single value.

Iteration Can Depend on the Starting Value

The same recursive rule may behave differently for different initial guesses.

A starting value may lead to:

rapid convergence;
slow convergence;
oscillation;
divergence;
a different solution.

Initial conditions therefore matter in numerical algorithms.

Iteration as Repeated Substitution

Suppose

\[ x_{n+1}=g(x_n). \]

Then

\[ x_1=g(x_0), \] \[ x_2=g(g(x_0)), \] \[ x_3=g(g(g(x_0))). \]

Iteration repeatedly feeds the previous output back into the same rule.

Iteration Tables

Iterative calculations are often organized in a table.

For

\[ x_{n+1}=\frac{x_n+6}{2}, \qquad x_0=0, \]

we can write:

\(n\)	\(x_n\)
\(0\)	\(0\)
\(1\)	\(3\)
\(2\)	\(4.5\)
\(3\)	\(5.25\)
\(4\)	\(5.625\)

Iteration for Approximation

Iteration becomes especially useful when the target value is difficult to compute directly.

Suppose we want to approximate

\[ \sqrt2. \]

One useful recurrence is

\[ \boxed{ x_{n+1} = \frac12\left(x_n+\frac{2}{x_n}\right) }. \]

Example: Approximating \(\sqrt2\)

Begin with

\[ x_0=1. \]

Then

\[ x_1 = \frac12\left(1+\frac21\right) = 1.5. \]

Next,

\[ x_2 = \frac12\left(1.5+\frac{2}{1.5}\right) = 1.416666\ldots \]

and

\[ x_3\approx1.414215686. \]

The sequence rapidly approaches

\[ \sqrt2\approx1.414213562. \]

Why an Iterative Approximation Needs a Stopping Rule

A computer could continue generating new approximations indefinitely.

Practical numerical methods therefore require a condition that decides when the approximation is good enough.

A simple rule is

\[ \boxed{|x_{n+1}-x_n|<\varepsilon}, \]

where \(\varepsilon\) is a chosen tolerance.

Example: Difference Between Successive Iterates

Suppose

\[ x_4=1.4142135624 \]

and

\[ x_5=1.41421356237. \]

Then

\[ |x_5-x_4| = 0.00000000003. \]

If the tolerance is

\[ 10^{-8}, \]

then the change between these iterates is much smaller than required.

A Small Change Is Not Always Proof of Accuracy

If two successive approximations are close, the sequence may be settling down.

But

\[ |x_{n+1}-x_n| \]

measures the change between iterates, not necessarily the exact error from the true solution.

Strong numerical methods combine stopping rules with mathematical analysis or residual checks.

Search Intervals

A search interval is an interval of inputs selected for numerical investigation.

For example,

\[ [1,2] \]

may be chosen because a root has been shown to lie somewhere between \(1\) and \(2\).

Restricting the search avoids wasting effort on unrelated parts of the domain.

Bracketing a Root

A root is bracketed when two endpoints surround it in a useful way.

For a continuous function, a common condition is

\[ \boxed{f(a)f(b)<0}. \]

This means \(f(a)\) and \(f(b)\) have opposite signs.

The Intermediate Value Theorem then guarantees at least one root in \((a,b)\).

Example: Building a Search Interval

Consider

\[ f(x)=x^3-x-2. \]

Evaluate:

\[ f(1)=1-1-2=-2, \] \[ f(2)=8-2-2=4. \]

Since the signs differ,

\[ \boxed{1 contains at least one root.

Search Intervals Can Be Refined

Once a broad interval is known, we can test interior values.

For

\[ f(x)=x^3-x-2, \]

evaluate

\[ f(1.5)=3.375-1.5-2=-0.125 \]

and

\[ f(2)=4. \]

Therefore, the root lies in

\[ \boxed{1.5

Refining Again

Test

\[ x=1.75. \]

Then

\[ f(1.75) = 1.75^3-1.75-2 = 1.609375. \]

Since

\[ f(1.5)<0 \]

and

\[ f(1.75)>0, \]

the root lies in

\[ \boxed{1.5

Interval Width

If the search interval is

\[ [a,b], \]

its width is

\[ \boxed{b-a}. \]

Narrower intervals localize the solution more precisely.

Example: Measuring Refinement

The interval

\[ [1,2] \]

has width

\[ 1. \]

The refined interval

\[ [1.5,1.75] \]

has width

\[ 0.25. \]

The uncertainty has been reduced substantially.

Search Intervals and Midpoints

The midpoint of

\[ [a,b] \]

\[ \boxed{m=\frac{a+b}{2}}. \]

Testing the midpoint divides the search interval into two equal parts.

Repeating this idea gives the bisection method.

Search Intervals Need Not Be Symmetric

A useful interval simply needs to contain the target region.

It might be

\[ [0,10], \]

\[ [1.52,1.53], \]

\[ [-7.2,-7.1]. \]

The endpoints depend on what is known about the problem.

Search Intervals Can Come from Algebra

Algebraic reasoning may give bounds before any numerical iteration begins.

For

\[ x^2=20, \]

we know

\[ 4^2=16<20 \]

and

\[ 5^2=25>20. \]

Therefore,

\[ \boxed{4<\sqrt{20}<5}. \]

Search Intervals Can Come from Graphs

A graph may show that a curve crosses the \(x\)-axis near a particular region.

For example, a graph may suggest

\[ 2 Numerical evaluation can then test and refine that interval.

Graphing is useful for discovery; numerical checks make the search more precise.

Search Intervals Can Come from Tables

A numerical table may show

\[ f(3.1)<0 \]

and

\[ f(3.2)>0. \]

If the function is continuous, then

\[ \boxed{3.1 is a valid bracketing interval for at least one root.

Search Intervals and Multiple Roots

A broad interval may contain more than one root.

For example, if a polynomial has three zeros between \(-5\) and \(5\), then

\[ [-5,5] \]

is too broad to isolate a single root.

Numerical methods often work more reliably when each target root is isolated in its own search region.

Even-Multiplicity Roots May Not Produce a Sign Change

Consider

\[ f(x)=(x-2)^2. \]

Then

\[ f(x)\ge0 \]

for every real \(x\).

The root at

\[ x=2 \]

does not create opposite signs on the two sides.

Therefore, sign-change bracketing alone cannot detect every possible root.

Discontinuities Can Mislead a Sign-Change Search

Consider

\[ f(x)=\frac{1}{x}. \]

Then

\[ f(-1)=-1 \]

and

\[ f(1)=1. \]

The signs differ, but there is no root between \(-1\) and \(1\).

The function is discontinuous at

\[ x=0. \]

Continuity must be checked before interpreting a sign change as a root guarantee.

Iteration versus Interval Search

Iterative methods and interval methods organize numerical information in different ways.

An iteration may update a single estimate:

\[ x_0\to x_1\to x_2\to x_3\to\cdots \]

An interval method may update a pair of bounds:

\[ [a_0,b_0] \to [a_1,b_1] \to [a_2,b_2] \to\cdots \]

Both are forms of successive refinement.

Recursive Interval Updates

Search intervals themselves can be updated recursively.

Suppose

\[ I_n=[a_n,b_n]. \]

A numerical algorithm may produce a smaller interval

\[ I_{n+1}=[a_{n+1},b_{n+1}] \]

satisfying

\[ I_{n+1}\subseteq I_n. \]

The search becomes progressively more focused.

Nested Search Intervals

A sequence of intervals may look like

\[ [1,2], \] \[ [1.5,2], \] \[ [1.5,1.75], \] \[ [1.5,1.625]. \]

Each interval lies inside the previous one.

Such intervals are called nested intervals.

Iteration Counts

Numerical algorithms often track how many update steps have been performed.

If a method begins at \(n=0\), then after five updates the latest computed value is

\[ x_5. \]

The iteration count is useful for comparing efficiency between methods.

Maximum Iteration Limits

A practical algorithm should not assume convergence will always occur.

One safeguard is to impose a maximum number of iterations.

For example:

\[ \boxed{n\le100}. \]

If the method has not met its stopping condition after \(100\) updates, the algorithm can stop and report that further review is needed.

Two Common Stopping Conditions

For a sequence of approximations, we might stop when

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

For a search interval, we might stop when

\[ b_n-a_n<\varepsilon. \]

These criteria measure different forms of numerical refinement.

Residual-Based Stopping

When solving

\[ f(x)=0, \]

we may also require

\[ |f(x_n)|<\varepsilon. \]

This means the current approximation produces a small residual.

Strong algorithms often monitor more than one criterion.

Example: Combining Conditions

A numerical method might stop only when both

\[ |x_{n+1}-x_n|<10^{-6} \]

and

\[ |f(x_{n+1})|<10^{-6}. \]

The first condition checks stability between iterates.

The second checks how closely the current value satisfies the equation.

Iteration in Pseudocode

A simple iterative process can be described in pseudocode:

set x = initial value

repeat
    new_x = update(x)
    x = new_x
until stopping condition is satisfied

The mathematical rule and the algorithmic loop describe the same repeated process in different languages.

Interval Search in Pseudocode

A general interval-refinement process can be described as:

choose interval [a, b]

repeat
    select a test point inside [a, b]
    evaluate the function
    replace [a, b] with a smaller valid interval
until the interval is sufficiently small

The exact update rule depends on the numerical method.

Recursive Thinking and Algorithms

Recursive notation is compact:

\[ x_{n+1}=g(x_n). \]

But a computer must still execute the recurrence step by step.

This makes recursion an important bridge between mathematical definitions and computational algorithms.

Iteration versus Closed Form

A closed-form expression gives a term directly from its index or parameters.

A recursive expression gives a term from earlier terms.

For example, the arithmetic sequence

\[ 3,\quad7,\quad11,\quad15,\quad\ldots \]

can be written recursively as

\[ a_1=3, \qquad a_{n+1}=a_n+4, \]

or explicitly as

\[ \boxed{a_n=3+4(n-1)}. \]

Why Numerical Methods Often Prefer Iteration

Some equations do not have a convenient explicit solution.

In those cases, an iterative rule may be easier to compute than an exact symbolic form.

Numerical methods trade a one-step formula for a controlled sequence of improving approximations.

Initial Guesses

Some iterative algorithms require only one starting value.

For example,

\[ x_0=2. \]

Others require two initial values:

\[ x_0=1, \qquad x_1=2. \]

Bracketing methods typically begin with two interval endpoints.

Choosing an Initial Guess

A good initial guess may come from:

a graph;
a numerical table;
algebraic bounds;
physical knowledge of the problem;
a previously computed solution;
a simple nearby value.

Good initialization can make a numerical method faster and more reliable.

Common Error: Confusing \(x_n\) with \(x^n\)

The notation

\[ x_n \]

means the \(n\)-indexed value in a sequence.

The notation

\[ x^n \]

means \(x\) raised to the \(n\)th power.

These are completely different objects.

Common Error: Forgetting the Initial Value

A recursive rule alone may not determine a unique sequence.

For example,

\[ x_{n+1}=x_n+2 \]

does not specify whether the sequence begins

\[ 0,2,4,6,\ldots \]

\[ 5,7,9,11,\ldots \]

The initial value is part of the definition.

Common Error: Assuming Iteration Means Convergence

Repetition does not guarantee improvement.

A sequence may:

converge;
diverge;
oscillate;
cycle;
converge to an unintended value.

Convergence must be checked rather than assumed.

Common Error: Using a Sign Change Across a Discontinuity

Opposite endpoint signs are not enough by themselves.

Continuity over the interval must also be established when using the Intermediate Value Theorem.

The function

\[ \frac1x \]

is the standard warning example.

Common Error: Searching Too Broadly

A search interval such as

\[ [-1000,1000] \]

may be mathematically valid but computationally inefficient if the target root is known to lie near \(2\).

Use all available structural information to narrow the search before expensive iteration begins.

Common Error: Stopping Without a Criterion

Saying that an approximation "looks close enough" is not a reproducible numerical rule.

A stopping condition should be stated mathematically, such as

\[ |x_{n+1}-x_n|<10^{-5} \]

\[ b_n-a_n<10^{-4}. \]

A Reliable Iterative Workflow

Identify the equation or target quantity.
Choose an update rule appropriate to the method.
Select an initial value or values.
Compute the next iterate carefully.
Record the result.
Check the stopping condition.
If the condition is not met, repeat the update.
Check the final residual or other verification measure.
Report the approximation with appropriate precision.

A Reliable Search-Interval Workflow

Rewrite the equation as \(f(x)=0\) when useful.
Use algebra, graphs, or tables to identify a candidate interval.
Evaluate the function at the endpoints.
Check continuity assumptions.
Confirm that the interval contains the target behavior.
Select an interior test value.
Replace the interval with a smaller valid interval.
Repeat until the interval satisfies the tolerance.
Verify and report the result.

Example: Full Iterative Workflow

Approximate \(\sqrt5\) using

\[ x_{n+1} = \frac12\left(x_n+\frac5{x_n}\right) \]

with

\[ x_0=2. \]

First iteration:

\[ x_1 = \frac12\left(2+\frac52\right) = 2.25. \]

Second iteration:

\[ x_2 = \frac12\left(2.25+\frac5{2.25}\right) \approx2.236111. \]

Third iteration:

\[ x_3\approx2.236068. \]

Thus,

\[ \boxed{\sqrt5\approx2.236068}. \]

Example: Full Search-Interval Workflow

Approximate the real root of

\[ x^3-x-2=0. \]

Begin with

\[ f(1)=-2, \qquad f(2)=4. \]

Therefore,

\[ [1,2] \]

brackets a root.

Test the midpoint:

\[ f(1.5)=-0.125. \]

Since \(f(1.5)<0\) and \(f(2)>0\), replace the original interval with

\[ \boxed{[1.5,2]}. \]

The next lesson formalizes this midpoint-refinement procedure as the bisection method.

Practice 1: Generate Iterates

Given

\[ x_0=1, \qquad x_{n+1}=\frac{x_n+5}{2}, \]

compute \(x_1\), \(x_2\), and \(x_3\).

Practice 2: Identify the Recursive Rule

The sequence

\[ 4,\quad7,\quad10,\quad13,\quad\ldots \]

begins with \(a_1=4\).

Write a recursive rule for the sequence.

Practice 3: Convergence or Divergence?

Consider

\[ x_{n+1}=3x_n, \qquad x_0=1. \]

Compute the first four terms and describe the behavior.

Practice 4: Oscillation

Let

\[ x_{n+1}=-x_n, \qquad x_0=2. \]

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

Practice 5: Search Interval

For

\[ f(x)=x^2-7, \]

show that the positive root lies in

\[ [2,3]. \]

Practice 6: Refine the Interval

For

\[ f(x)=x^2-7, \]

evaluate \(f(2.5)\) and determine whether the positive root lies in \([2,2.5]\) or \([2.5,3]\).

Practice 7: Interval Width

Find the width of

\[ [2.625,2.65625]. \]

Practice 8: Stopping Condition

Suppose a method stops when

\[ |x_{n+1}-x_n|<0.001. \]

\[ x_n=3.1412 \]

and

\[ x_{n+1}=3.1418, \]

should the method stop?

Practice 9: Detect the Problem

A student says that because

\[ f(-1)<0 \]

and

\[ f(1)>0, \]

the function must have a root between \(-1\) and \(1\).

What additional condition must be checked?

Practice 10: Interpret the Algorithm

Explain what the recurrence

\[ x_{n+1}=g(x_n) \]

means operationally.

Practice Answers

Practice 1

\[ x_1=\frac{1+5}{2}=3. \] \[ x_2=\frac{3+5}{2}=4. \] \[ x_3=\frac{4+5}{2}=4.5. \]

Therefore,

\[ \boxed{x_1=3,\quad x_2=4,\quad x_3=4.5}. \]

Practice 2

Each term is \(3\) more than the previous term:

\[ \boxed{ a_1=4, \qquad a_{n+1}=a_n+3 }. \]

Practice 3

\[ x_0=1, \quad x_1=3, \quad x_2=9, \quad x_3=27. \]

The values grow rapidly and do not approach a finite limit.

Practice 4

\[ x_1=-2, \] \[ x_2=2, \] \[ x_3=-2, \] \[ x_4=2. \]

The sequence oscillates between \(2\) and \(-2\).

Practice 5

\[ f(2)=4-7=-3 \]

and

\[ f(3)=9-7=2. \]

Since the function is continuous and changes sign,

\[ \boxed{2<\sqrt7<3}. \]

Practice 6

\[ f(2.5)=2.5^2-7=6.25-7=-0.75. \]

Since

\[ f(2.5)<0 \]

and

\[ f(3)>0, \]

the root lies in

\[ \boxed{[2.5,3]}. \]

Practice 7

\[ 2.65625-2.625=0.03125. \]

Therefore, the interval width is

\[ \boxed{0.03125}. \]

Practice 8

\[ |3.1418-3.1412| = 0.0006. \]

Since

\[ 0.0006<0.001, \]

the stopping condition is satisfied.

Practice 9

The function must be continuous on the interval being used for the sign-change argument.

Without continuity, opposite signs do not guarantee a zero between the endpoints.

Practice 10

The recurrence means:

begin with a current estimate \(x_n\);
substitute it into \(g\);
use the output as the next estimate \(x_{n+1}\);
repeat as required.

What to Remember

Iteration repeatedly applies a computational rule.
Recursion defines later values from earlier values.
An update rule often has the form \(x_{n+1}=g(x_n)\).
The starting value can affect the behavior of an iterative method.
Iteration may converge, diverge, oscillate, or cycle.
A search interval restricts numerical work to a relevant region.
For continuous functions, opposite endpoint signs bracket at least one root.
Discontinuities and even-multiplicity roots require special care.
Stopping conditions make numerical procedures reproducible.
Iteration and interval refinement are core structures behind numerical algorithms.

Where We Go Next

Iteration, recursion, and search intervals provide the framework for systematic numerical procedures. The next step is to study one of the most reliable interval-based root-finding methods.

The next lesson, Bracketing and Bisection, develops a formal algorithm for repeatedly halving a sign-changing interval until a root is located to the required tolerance.