Skip to content

Iteration, Newton-Raphson and Rate of Convergence

CSIR NET numerical analysis: bisection, fixed-point iteration, Newton-Raphson, secant and regula falsi, order of convergence and multiple roots.

  • 24 min read
  • Updated
On this page · 14 sections
  1. Prerequisites
  2. The Hook: Same Root, Four Different Fates
  3. Setting Up: Roots and Brackets
  4. Rate (Order) of Convergence
  5. Fixed-Point Iteration
  6. Newton-Raphson Method
  7. Secant, Regula Falsi and Other Methods
  8. Memory Tricks
  9. Don’t Confuse
  10. Common Mistakes
  11. Practice
  12. Quick Revision Table
  13. Key Takeaways
  14. What’s Next

Prerequisites

The Hook: Same Root, Four Different Fates

Setting Up: Roots and Brackets

We want a root \( \alpha \) of \( f(x) = 0 \), with \( f \) continuous (and usually smooth) near \( \alpha \). Write \( e_n = x_n - \alpha \) for the error of the \( n \)-th iterate.

Locating a root. If \( f \) is continuous on \( [a, b] \) and \( f(a) f(b) < 0 \), the intermediate value theorem gives a root in \( (a, b) \). If moreover \( f' \) does not vanish on \( (a, b) \), the root is unique there.

Bisection

Halve the bracket each step: with \( c = \frac{a + b}{2} \), keep whichever of \( [a, c] \), \( [c, b] \) still has a sign change.

After \( n \) steps, the midpoint \( c_n \) satisfies

$$\lvert c_n - \alpha \rvert \le \frac{b - a}{2^n},$$

so an accuracy \( \varepsilon \) needs \( n \ge \log_2 \frac{b - a}{\varepsilon} \) steps, a number you can compute before starting. Bisection always converges (given a sign change), never uses \( f' \), and is slow: the error bound halves each step, so it gains roughly one decimal digit every 3.3 steps (\( \log_2 10 \approx 3.32 \)).

Rate (Order) of Convergence

Let \( x_n \to \alpha \) with \( e_n \ne 0 \). The sequence has order of convergence \( p \ge 1 \) if

$$\lim_{n\to\infty} \frac{\lvert e_{n+1} \rvert}{\lvert e_n \rvert^p} = C, \qquad 0 < C < \infty,$$

with the extra requirement \( C < 1 \) when \( p = 1 \). The constant \( C \) is the asymptotic error constant.

NameConditionWhat you see in the digits
Linear\( p = 1 \), \( 0 < C < 1 \)a fixed number of digits gained per step (about \( -\log_{10} C \))
Superlinear\( \frac{\lvert e_{n+1} \rvert}{\lvert e_n \rvert} \to 0 \)the gain per step keeps growing
Quadratic\( p = 2 \)correct digits roughly double each step
Cubic\( p = 3 \)correct digits roughly triple each step

Reading the order from data. From three consecutive errors,

$$p \approx \frac{\log \lvert e_{n+1} / e_n \rvert}{\log \lvert e_n / e_{n-1} \rvert}.$$

For the errors \( 2 \times 10^{-1}, 3.2 \times 10^{-2}, 8.2 \times 10^{-4}, 5.4 \times 10^{-7} \) this gives \( p \approx 2.00 \), and \( \frac{e_{n+1}}{e_n^2} \approx 0.80 \) throughout: quadratic with \( C \approx 0.8 \).

Fixed-Point Iteration

Rewrite \( f(x) = 0 \) as \( x = g(x) \) and iterate \( x_{n+1} = g(x_n) \). If \( x_n \to \alpha \) and \( g \) is continuous, then \( \alpha = g(\alpha) \).

Both hypotheses matter: \( g \) must map the interval into itself, and \( \lvert g' \rvert \) must be bounded by some \( L < 1 \) (not merely \( \lvert g' \rvert < 1 \) pointwise on an unbounded set). The proof is the mean value theorem: \( x_{n+1} - \alpha = g(x_n) - g(\alpha) = g'(\xi_n)(x_n - \alpha) \).

Local behaviour is decided by \( g'(\alpha) \)

From \( e_{n+1} = g'(\xi_n) e_n \) with \( \xi_n \to \alpha \):

\( g'(\alpha) \)Behaviour near \( \alpha \)
\( \lvert g'(\alpha) \rvert > 1 \)repelling: iterates move away (unless they land exactly on \( \alpha \))
\( 0 < g'(\alpha) < 1 \)linear convergence, monotone (one side of \( \alpha \))
\( -1 < g'(\alpha) < 0 \)linear convergence, oscillating (alternate sides)
\( g'(\alpha) = 0 \)at least quadratic
\( \lvert g'(\alpha) \rvert = 1 \)the test is silent; look at higher terms

For linear convergence the asymptotic constant is exactly \( C = \lvert g'(\alpha) \rvert \). Smaller is faster: \( g'(\alpha) = \frac{1}{4} \) gains about 0.6 digits per step, \( -\frac{1}{2} \) about 0.3.

This is Taylor’s theorem at \( \alpha \): \( g(x_n) = \alpha + \frac{g^{(p)}(\xi)}{p!} e_n^p \).

Aitken’s \( \Delta^2 \) acceleration

For a linearly convergent sequence, the extrapolated value

$$\hat{x}_n = x_n - \frac{(x_{n+1} - x_n)^2}{x_{n+2} - 2x_{n+1} + x_n}$$

converges faster than \( x_n \). Applying it repeatedly to fixed-point iterates (restart from each \( \hat{x} \)) is Steffensen’s method, which is quadratic for a simple fixed point with \( g'(\alpha) \ne 1 \) and needs no derivative.

Newton-Raphson Method

Derivation. Replace \( f \) by its tangent at \( x_n \): \( f(x) \approx f(x_n) + f'(x_n)(x - x_n) \). Setting this to zero:

$$\boxed{x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}}$$

Why it is quadratic. Newton is the fixed-point iteration with \( g(x) = x - \frac{f(x)}{f'(x)} \). Differentiating,

$$g'(x) = \frac{f(x) f''(x)}{f'(x)^2},$$

so \( g'(\alpha) = 0 \) whenever \( f'(\alpha) \ne 0 \). More precisely, Taylor’s formula with \( f(\alpha) = 0 \) gives

$$e_{n+1} = \frac{f''(\xi_n)}{2 f'(x_n)} e_n^2, \qquad \frac{e_{n+1}}{e_n^2} \to \frac{f''(\alpha)}{2 f'(\alpha)}.$$

Standard Newton formulas

Task\( f(x) \)Iteration
\( \sqrt{N} \)\( x^2 - N \)\( x_{n+1} = \frac{1}{2}\left(x_n + \frac{N}{x_n}\right) \)
\( N^{1/k} \)\( x^k - N \)\( x_{n+1} = \frac{1}{k}\left((k - 1)x_n + \frac{N}{x_n^{k-1}}\right) \)
\( \frac{1}{N} \) (no division)\( \frac{1}{x} - N \)\( x_{n+1} = x_n(2 - N x_n) \)
\( \frac{1}{\sqrt N} \)\( \frac{1}{x^2} - N \)\( x_{n+1} = \frac{x_n}{2}(3 - N x_n^2) \)

The square-root iteration is the Babylonian (Heron’s) method. For \( \sqrt 3 \) from \( x_0 = 2 \): \( x_1 = \frac{7}{4} \), \( x_2 = \frac{97}{56} \approx 1.7321429 \), \( x_3 = \frac{18817}{10864} \approx 1.73205081 \). For \( \frac{1}{7} \) from \( x_0 = 0.1 \): \( 0.13, 0.1417, 0.142848, 0.14285714 \). The reciprocal iteration converges only for \( 0 < x_0 < \frac{2}{N} \).

When Newton behaves (and when it does not)

A sufficient condition (Fourier). If \( f(a) f(b) < 0 \), \( f' \) and \( f'' \) are non-zero and of constant sign on \( [a, b] \), and \( x_0 \in [a, b] \) is chosen with \( f(x_0) f''(x_0) > 0 \), then the Newton iterates converge monotonically to the root.

Example: for \( f(x) = x^2 - N \), \( f'' = 2 > 0 \), so any \( x_0 > \sqrt{N} \) gives a decreasing sequence to \( \sqrt N \); any \( x_0 \in (0, \sqrt N) \) overshoots to \( x_1 > \sqrt N \) and is monotone from then on (by the AM-GM inequality). So Newton for \( \sqrt N \) converges from every \( x_0 > 0 \).

FailureExample
Zero derivative at an iterate\( f'(x_n) = 0 \): the tangent is horizontal, \( x_{n+1} \) undefined
2-cycle\( f(x) = x^3 - 2x + 2 \), \( x_0 = 0 \): \( x_1 = 1 \), \( x_2 = 0 \), \( x_3 = 1, \dots \)
Divergence for every \( x_0 \ne 0 \)\( f(x) = x^{1/3} \) (real cube root): \( x_{n+1} = -2x_n \)
Slow (linear) convergencemultiple root, e.g. \( f(x) = (x - 1)^2(x + 2) \): error ratio \( \to \frac{1}{2} \)
Jumps to another root\( x_0 \) near a critical point of \( f \): the tangent sends \( x_1 \) far away

Multiple roots

If \( f(x) = (x - \alpha)^m h(x) \) with \( h(\alpha) \ne 0 \), then near \( \alpha \)

$$g'(\alpha) = 1 - \frac{1}{m},$$

so Newton is linear with constant \( \frac{m-1}{m} \): \( \frac{1}{2} \) for a double root, \( \frac{2}{3} \) for a triple root. Two cures restore quadratic convergence:

  1. Modified Newton (multiplicity known): \( x_{n+1} = x_n - m\,\frac{f(x_n)}{f'(x_n)} \). Then \( g'(\alpha) = 0 \).
  2. Newton on \( u = \frac{f}{f'} \) (multiplicity unknown): \( u \) has a simple root at \( \alpha \), so \( x_{n+1} = x_n - \frac{u(x_n)}{u'(x_n)} \) is quadratic.

For \( f(x) = (x - 1)^2(x + 2) \) from \( x_0 = 2 \), plain Newton’s error ratios are \( 0.54, 0.52, 0.51, 0.506, \dots \to \frac{1}{2} \), while modified Newton with \( m = 2 \) gives \( 1.111, 1.0019, 1.0000006, 1.00000000000007 \).

Secant, Regula Falsi and Other Methods

Secant method. Replace \( f'(x_n) \) by a difference quotient:

$$x_{n+1} = x_n - f(x_n)\,\frac{x_n - x_{n-1}}{f(x_n) - f(x_{n-1})}.$$

The error satisfies \( e_{n+1} \approx \frac{f''(\alpha)}{2f'(\alpha)} e_n e_{n-1} \), which gives order \( p = \frac{1 + \sqrt 5}{2} \approx 1.618 \) (the positive root of \( p^2 = p + 1 \)). It needs two starting values, only one new \( f \)-evaluation per step, and no derivative. It does not keep a bracket, so it can fail like Newton.

Regula falsi (false position). The same formula, but always keep two points with \( f \) of opposite signs. It always converges (like bisection), but for a convex or concave \( f \) one endpoint stays fixed for ever and the convergence is only linear.

MethodOrderNew evaluations per stepNeeds bracket?Always converges?
Bisection1 (error bound halves)1 (\( f \))yesyes
Regula falsi1 (in general)1 (\( f \))yesyes
Fixed point1 if \( g'(\alpha) \ne 0 \)1 (\( g \))noif contraction
Secant\( \frac{1 + \sqrt 5}{2} \approx 1.618 \)1 (\( f \))nolocally
Muller\( \approx 1.84 \)1 (\( f \))nolocally
Newton-Raphson2 (simple root)2 (\( f \), \( f' \))nolocally
Chebyshev3 (simple root)3 (\( f, f', f'' \))nolocally

Efficiency. If each step needs \( d \) function evaluations and the order is \( p \), the efficiency index is \( p^{1/d} \): Newton \( \sqrt 2 \approx 1.414 \), secant \( 1.618 \). Per unit of work, the secant method beats Newton when \( f' \) costs as much as \( f \).

Chebyshev’s iteration is \( x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} - \frac{1}{2}\frac{f(x_n)^2 f''(x_n)}{f'(x_n)^3} \); it is the next term of the same Taylor idea.

Memory Tricks

Don’t Confuse

ThisvsThat
Secant: drops the oldest point, order 1.618Regula falsi: keeps a sign change, order 1
Order \( p \) (exponent in \( e_n^p \))asymptotic constant \( C \) (the multiplier)
\( \lvert g'(\alpha) \rvert < 1 \) (local convergence near \( \alpha \))\( \lvert g' \rvert \le L < 1 \) on an interval mapped into itself (global on that interval)
Newton, simple root: quadraticNewton, multiple root: linear, \( C = 1 - \frac{1}{m} \)
\( g'(\alpha) > 0 \): monotone approach\( g'(\alpha) < 0 \): alternate sides
Error bound known in advance (bisection)error only estimated from iterates (Newton, secant)

Common Mistakes

Practice

All questions below are original practice questions written for this page. They are not from any CSIR NET paper. In Level 3, as in Part C, one or more options may be correct.

Level 1: Foundation

  1. State the order of convergence of the secant method and of Newton’s method at a simple root.
  2. Write the Newton iteration for computing \( \frac{1}{N} \) without division.
  3. For an iteration \( x_{n+1} = g(x_n) \) with fixed point \( \alpha \) and \( g'(\alpha) = -0.3 \), describe the convergence.
Answers
  1. Secant: \( \frac{1 + \sqrt 5}{2} \approx 1.618 \). Newton at a simple root: 2.
  2. \( x_{n+1} = x_n(2 - N x_n) \), from \( f(x) = \frac{1}{x} - N \); it converges for \( 0 < x_0 < \frac{2}{N} \).
  3. Linear, with asymptotic constant 0.3; since \( g'(\alpha) < 0 \), successive iterates lie on alternate sides of \( \alpha \).

Level 2: Part B Style

Practice Q1. Newton’s method for \( f(x) = x^2 - 3 \) with \( x_0 = 2 \) gives \( x_2 = \)

(a) \( \frac{7}{4} \) (b) \( \frac{97}{56} \) (c) \( \frac{26}{15} \) (d) \( \frac{19}{11} \)

Answer: (b)

\( x_{n+1} = \frac{1}{2}\left(x_n + \frac{3}{x_n}\right) \). \( x_1 = \frac{1}{2}\left(2 + \frac{3}{2}\right) = \frac{7}{4} \). \( x_2 = \frac{1}{2}\left(\frac{7}{4} + \frac{12}{7}\right) = \frac{1}{2} \cdot \frac{49 + 48}{28} = \frac{97}{56} \approx 1.73214 \). (Option (c), \( \frac{26}{15} \), is a good rational approximation to \( \sqrt 3 \) but not a Newton iterate from 2.)

Practice Q2. The bisection method is applied to \( f(x) = x^3 - x - 1 \) on \( [1, 2] \). Using the bound \( \lvert c_n - \alpha \rvert \le \frac{b - a}{2^n} \), the least \( n \) that guarantees \( \lvert c_n - \alpha \rvert < 10^{-3} \) is

(a) 9 (b) 10 (c) 11 (d) 12

Answer: (b)

\( f(1) = -1 < 0 \), \( f(2) = 5 > 0 \), so a root is bracketed. We need \( \frac{1}{2^n} < 10^{-3} \), i.e. \( 2^n > 1000 \). Since \( 2^9 = 512 \) and \( 2^{10} = 1024 \), \( n = 10 \).

Practice Q3. Newton’s method is applied to \( f(x) = (x - 1)^3 e^x \) with \( x_0 \) close to 1. Then the iterates converge to 1

(a) quadratically (b) linearly with asymptotic constant \( \frac{1}{3} \) (c) linearly with asymptotic constant \( \frac{2}{3} \) (d) cubically

Answer: (c)

The root 1 has multiplicity \( m = 3 \) (\( e^x \ne 0 \)). For Newton at a root of multiplicity \( m \), \( g'(\alpha) = 1 - \frac{1}{m} = \frac{2}{3} \), so the convergence is linear with constant \( \frac{2}{3} \). The modified iteration \( x_{n+1} = x_n - 3\frac{f(x_n)}{f'(x_n)} \) would be quadratic.

Practice Q4. To find the positive root of \( x^2 - x - 2 = 0 \), which iteration converges for every starting value \( x_0 \ge 0 \)?

(a) \( x_{n+1} = x_n^2 - 2 \) (b) \( x_{n+1} = \sqrt{x_n + 2} \) (c) \( x_{n+1} = 2x_n - \frac{4}{x_n} \) (d) \( x_{n+1} = 2x_n^2 - x_n - 4 \)

Answer: (b)

\( g(x) = \sqrt{x + 2} \) maps \( [0, \infty) \) into \( [\sqrt 2, \infty) \subset [0, \infty) \) and \( 0 < g'(x) = \frac{1}{2\sqrt{x+2}} \le \frac{1}{2\sqrt 2} < 1 \) there, so it is a contraction and converges to 2 from every \( x_0 \ge 0 \). (a) \( g'(2) = 4 \): repelling. (c) is undefined at \( x_0 = 0 \); its fixed points satisfy \( x^2 = 4 \), but \( g'(x) = 2 + \frac{4}{x^2} \) gives \( g'(2) = 3 \): repelling. (d) \( g(x) = 2x^2 - x - 4 \) has fixed point 2 (\( 8 - 2 - 4 = 2 \)) but \( g'(2) = 7 \): repelling.

Level 3: Part C Style

Practice Q5. Consider \( x_{n+1} = g(x_n) \) with \( g(x) = \frac{x^2 + 6}{5} \). Which statements are true?

(a) The fixed points of \( g \) are 2 and 3. (b) For every \( x_0 \in (-3, 3) \), the iterates converge to 2. (c) For \( x_0 = 3.1 \), the iterates converge to 3. (d) The convergence to 2 is linear with asymptotic error constant \( \frac{4}{5} \).

Answer: (a), (b) and (d)
  • (a) True. \( x = \frac{x^2 + 6}{5} \iff x^2 - 5x + 6 = 0 \iff x \in \{2, 3\} \).
  • (b) True. \( g(x) - x = \frac{(x - 2)(x - 3)}{5} \) and \( g \) is increasing on \( [0, \infty) \). For \( x_0 \in (-3, 3) \), \( x_1 = g(x_0) \in [\frac{6}{5}, 3) \). If \( x_1 < 2 \), then \( g(x) > x \) and \( g(x) < g(2) = 2 \) on \( [\frac{6}{5}, 2) \): the sequence increases and is bounded by 2. If \( 2 < x_1 < 3 \), then \( g(x) < x \) and \( g(x) > 2 \): it decreases and is bounded below by 2. Either way it converges, and the only fixed point it can reach is 2. Numerically from \( x_0 = 0 \): 1.2, 1.488, 1.643, 1.740, …, increasing to 2.
  • (c) False. \( g'(3) = \frac{6}{5} > 1 \): 3 repels. Indeed \( g(3.1) = 3.122 > 3.1 \), and the iterates increase to \( +\infty \).
  • (d) True. \( g'(x) = \frac{2x}{5} \), \( g'(2) = \frac{4}{5} \in (0, 1) \): linear, monotone, \( C = 0.8 \).

Practice Q6. Which statements about Newton’s method \( x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} \) are true?

(a) For \( f(x) = x^2 - a \), \( a > 0 \), it converges to \( \sqrt a \) from every \( x_0 > 0 \). (b) For \( f(x) = x^{1/3} \) (the real cube root), it diverges from every \( x_0 \ne 0 \). (c) At a root of multiplicity 2, it converges quadratically if \( x_0 \) is close enough. (d) For \( f(x) = x^3 - 2x + 2 \) and \( x_0 = 0 \), the iterates alternate between 0 and 1.

Answer: (a), (b) and (d)
  • (a) True. \( x_{n+1} - \sqrt a = \frac{(x_n - \sqrt a)^2}{2x_n} \ge 0 \), so \( x_n \ge \sqrt a \) from \( n = 1 \) on; then \( x_{n+1} - x_n = \frac{a - x_n^2}{2x_n} \le 0 \), so the sequence decreases and is bounded below by \( \sqrt a \). Its limit solves \( L = \frac{1}{2}(L + \frac{a}{L}) \), so \( L = \sqrt a \).
  • (b) True. \( \frac{f}{f'} = \frac{x^{1/3}}{\frac{1}{3}x^{-2/3}} = 3x \), so \( x_{n+1} = -2x_n \) and \( \lvert x_n \rvert = 2^n \lvert x_0 \rvert \to \infty \).
  • (c) False. At a double root, \( g'(\alpha) = 1 - \frac{1}{2} = \frac{1}{2} \): linear, constant \( \frac{1}{2} \).
  • (d) True. \( f'(x) = 3x^2 - 2 \). \( x_1 = 0 - \frac{2}{-2} = 1 \); \( x_2 = 1 - \frac{1}{1} = 0 \). The 2-cycle repeats.

Practice Q7. Two root-finding methods A and B are run on the same problem. Their errors \( \lvert e_n \rvert \) at four consecutive steps are:

StepAB
\( n \)\( 2.0 \times 10^{-1} \)\( 1.0 \times 10^{-1} \)
\( n + 1 \)\( 3.2 \times 10^{-2} \)\( 4.0 \times 10^{-2} \)
\( n + 2 \)\( 8.2 \times 10^{-4} \)\( 1.6 \times 10^{-2} \)
\( n + 3 \)\( 5.4 \times 10^{-7} \)\( 6.4 \times 10^{-3} \)

Assuming each continues with the pattern shown, which statements are true?

(a) A is quadratically convergent with asymptotic error constant about 0.8. (b) B is linearly convergent with asymptotic error constant 0.4. (c) The next error of A is about \( 4.3 \times 10^{-7} \). (d) B needs at least 10 more steps after step \( n + 3 \) to bring its error below \( 10^{-6} \).

Answer: (a), (b) and (d)
  • (a) True. \( \frac{3.2 \times 10^{-2}}{(0.2)^2} = 0.80 \), \( \frac{8.2 \times 10^{-4}}{(0.032)^2} \approx 0.80 \), \( \frac{5.4 \times 10^{-7}}{(8.2 \times 10^{-4})^2} \approx 0.80 \). The order estimate \( \frac{\log(e_{n+2}/e_{n+1})}{\log(e_{n+1}/e_n)} \approx 2.0 \).
  • (b) True. Each error is 0.4 times the previous one.
  • (c) False. The next error of A is about \( 0.8 \times (5.4 \times 10^{-7})^2 \approx 2.3 \times 10^{-13} \). The value \( 4.3 \times 10^{-7} \) is what a linear method with \( C = 0.8 \) would give.
  • (d) True. We need \( 6.4 \times 10^{-3} \times 0.4^k < 10^{-6} \), i.e. \( 0.4^k < 1.5625 \times 10^{-4} \), \( k > \frac{\ln(1.5625 \times 10^{-4})}{\ln 0.4} \approx 9.56 \). So \( k = 10 \).

Quick Revision Table

IdeaFact
Bisection\( \lvert c_n - \alpha \rvert \le \frac{b - a}{2^n} \); needs a sign change; always converges
Order \( p \)\( \frac{\lvert e_{n+1} \rvert}{\lvert e_n \rvert^p} \to C \in (0, \infty) \); \( C < 1 \) if \( p = 1 \)
Fixed-point theorem\( g([a, b]) \subset [a, b] \), \( \lvert g' \rvert \le L < 1 \) \( \Rightarrow \) unique fixed point, convergence from every \( x_0 \)
Error bound\( \lvert x_n - \alpha \rvert \le \frac{L^n}{1 - L}\lvert x_1 - x_0 \rvert \)
Local test\( \lvert g'(\alpha) \rvert < 1 \) attract (sign: monotone / oscillate); \( > 1 \) repel
Order of fixed pointfirst non-zero \( g^{(p)}(\alpha) \) gives order \( p \), \( C = \frac{\lvert g^{(p)}(\alpha) \rvert}{p!} \)
Newton\( x_{n+1} = x_n - \frac{f}{f'} \); simple root: order 2, \( C = \lvert \frac{f''}{2f'} \rvert \)
Newton, multiplicity \( m \)linear, \( C = 1 - \frac{1}{m} \); fix: step \( \times m \), or Newton on \( \frac{f}{f'} \)
Secant / regula falsi1.618 / linear
Square root\( x_{n+1} = \frac{1}{2}(x_n + \frac{N}{x_n}) \), converges from every \( x_0 > 0 \)

Key Takeaways

What’s Next