← 2013 Paper 2

UPSC 2013 Maths Optional Paper 2 Q7a — Step-by-Step Solution

20 marks · Section B

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

Question

Develop an algorithm for Newton–Raphson method to solve $f(x)=0$ starting with initial iterate $x_0$, $n$ be the number of iterations allowed, $\mathrm{eps}$ be the prescribed relative error and $\mathrm{delta}$ be the prescribed lower bound for $f'(x)$.

Technique

Standard Newton–Raphson iteration with three safeguards: max iterations, relative tolerance, derivative-lower-bound.

Solution

Strategy. Implement the Newton–Raphson iteration $x_{k+1}=x_k-f(x_k)/f'(x_k)$ with proper termination criteria: (a) iteration count limit, (b) convergence tolerance on relative change, (c) safeguard against small derivatives.

Algorithm

INPUT:  f, f' (function and derivative)
        x0 (initial iterate)
        n (maximum number of iterations)
        eps (prescribed relative error tolerance)
        delta (prescribed lower bound for |f'(x)|; must satisfy |f'(x_k)| >= delta)

OUTPUT: an approximate root x_root (or a failure indicator)

ALGORITHM Newton-Raphson:

1.  x_prev <- x0
    converged <- FALSE
    
2.  FOR k = 1, 2, ..., n DO:
    
    2.1.  Evaluate f_val <- f(x_prev) and fprime_val <- f'(x_prev)
    
    2.2.  IF |fprime_val| < delta THEN:
              PRINT "Derivative too small at iteration k; method fails"
              EXIT (failure due to small derivative)
          END IF
    
    2.3.  x_curr <- x_prev - f_val / fprime_val
    
    2.4.  IF |x_curr - x_prev| <= eps * |x_curr| THEN:
              converged <- TRUE
              EXIT loop
          END IF
    
    2.5.  x_prev <- x_curr
    
    END FOR

3.  IF converged THEN:
        OUTPUT x_root = x_curr  (success)
    ELSE:
        PRINT "Failed to converge in n iterations"
        OUTPUT x_curr (with warning)
    END IF

Step-by-step explanation

1. Initialisation: Set the working variable x_prev to the user-supplied initial guess $x_0$. The flag converged tracks whether the tolerance has been met.

2. Main loop (up to $n$ iterations):

   2.1. Evaluate $f$ and $f'$ at the current iterate. (Each iteration costs one function evaluation and one derivative evaluation.)

   2.2. Safeguard: If $|f'(x_k)|<\mathrm{delta}$, the iteration formula $x_{k+1}=x_k-f(x_k)/f'(x_k)$ would divide by a tiny number, causing wild overshoot. Abort with an error message instead.

   2.3. Newton step: Apply the update.

   2.4. Convergence test (relative error): Compare $|x_{k+1}-x_k|$ against $\mathrm{eps}\cdot|x_{k+1}|$. The relative-error form $\mathrm{eps}\cdot|x_{k+1}|$ is preferred over the absolute form $\mathrm{eps}$ because it scales with the magnitude of the root. If the change is within tolerance, declare convergence.

   2.5. Otherwise, update x_prev and continue.

3. Final output:

   • On convergence: return $x_\text{root}=x_\text{curr}$.
   • On exhaustion of $n$ iterations: return the last iterate with a warning.

Convergence properties (informational)

Newton–Raphson has quadratic convergence near a simple root $x^*$: if $|x_k-x^*|=\epsilon_k$, then $\epsilon_{k+1}\le M\epsilon_k^{2}$ for some constant $M$ depending on $\max|f''|/\min|f'|$ near $x^*$. So convergence is very fast once the iterate is close.

Caveats:

• Quadratic convergence fails at multiple roots (linear instead).
• The “small derivative” safeguard catches both genuine non-convergence (function has zero derivative somewhere) and slow approach to a multiple root.
• The initial guess $x_0$ must be in a basin of attraction of the desired root; bad initial guesses lead to divergence, oscillation, or convergence to a wrong root.