← 2017 Paper 2

UPSC 2017 Maths Optional Paper 2 Q8b — Step-by-Step Solution

15 marks · Section B

Newton-Raphson method (convergence, geometric meaning) · Numerical Analysis · asked 6× in 13 yrs · Read the full method →

Question

Write an algorithm in the form of a flow chart for Newton–Raphson method. Describe the cases of failure of this method.

Technique

State the iteration $x_{n+1}=x_n-f(x_n)/f'(x_n)$; draw the flow chart (read → compute $f,f'$ → check $f'=0$ → update → convergence test → loop/stop); enumerate failure modes.

Solution

Method. To solve $f(x)=0$, the Newton–Raphson iteration is

starting from an initial guess $x_0$, derived from the tangent line to $y=f(x)$ at $x_n$ meeting the $x$-axis.

Step 1 — Algorithm (flow chart)

        ┌─────────────────────────────┐
        │            START            │
        └──────────────┬──────────────┘
                       ▼
   ┌───────────────────────────────────────────┐
   │  READ initial guess x0, tolerance ε,        │
   │       max iterations N                       │
   └──────────────────────┬──────────────────────┘
                          ▼
                   ┌─────────────┐
                   │  n ← 0       │
                   └──────┬──────┘
                          ▼
            ┌───────────────────────────┐
            │  Compute f(xn), f′(xn)     │
            └─────────────┬─────────────┘
                          ▼
                 ╱───────────────╲
                ╱  is f′(xn) = 0 ? ╲ ── yes ──►  PRINT "Failure:
                ╲   (or |f′|<δ)   ╱                derivative ≈ 0";  STOP
                 ╲───────┬───────╱
                         │ no
                         ▼
        ┌────────────────────────────────────┐
        │  x_{n+1} ← xn − f(xn)/f′(xn)        │
        └─────────────────┬──────────────────┘
                          ▼
              ╱──────────────────────╲
             ╱ |x_{n+1} − xn| < ε   ? ╲ ── yes ──►  PRINT root x_{n+1};  STOP
              ╲   (or |f(x_{n+1})|<ε) ╱
               ╲──────────┬──────────╱
                          │ no
                          ▼
              ╱──────────────────────╲
             ╱     n + 1 ≥ N  ?       ╲ ── yes ──►  PRINT "No convergence
              ╲                       ╱                in N iterations"; STOP
               ╲──────────┬──────────╱
                          │ no
                          ▼
                 ┌──────────────────┐
                 │ xn ← x_{n+1};     │
                 │ n ← n + 1         │ ──┐
                 └──────────────────┘   │
                          ▲             │
                          └─────────────┘  (loop back to "Compute f(xn), f′(xn)")

Step 2 — Cases of failure

1. Zero (or near-zero) derivative, $f'(x_n)=0$. The tangent is horizontal, so $x_{n+1}=x_n-f/f'$ involves division by zero — the next iterate flies off to infinity. Even $f'(x_n)\approx0$ causes a huge, erratic jump. (Occurs near a turning point/extremum of $f$.)

2. Bad initial guess (far from the root). Convergence is only local; if $x_0$ is not close enough, the iteration may diverge or converge to a different root than intended.

3. Divergence / overshoot. For functions whose curvature is unfavourable, successive tangents push the iterate further from the root, e.g. $f(x)=x^{1/3}$ from any $x_0\ne0$ gives $x_{n+1}=-2x_n$ — the iterates double in magnitude and diverge.

4. Oscillation (cycling). The iterates can fall into a repeating cycle $x_0\to x_1\to x_0\to\cdots$ and never settle, when the geometry maps a point back to itself after a step or two.

5. Root of multiplicity $>1$. At a multiple root $f$ and $f'$ vanish together; convergence degrades from quadratic to merely linear (slow), and round-off near $f'\approx0$ can stall the process.

6. Discontinuity / non-differentiability of $f$ or $f'$ near the root invalidates the tangent construction.

Verification

python3 (illustrations):
  f(x)=x²−2, x0=1:   1 → 1.5 → 1.41667 → 1.414216 → 1.4142136  (quadratic) ✓
  f(x)=x^{1/3}, x0=1: 1 → −2 → 4 → −8 → 16 ...   (diverges, x_{n+1}=−2x_n) ✓ (failure)
  f(x)=x³−2x+2, x0=0: 0 → 1 → 0 → 1 → ...        (2-cycle, oscillation)   ✓ (failure)