UPSC 2018 Maths Optional Paper 2 Q5e — Step-by-Step Solution

10 marks · Section B

Bisection Method (Convergence, Error) · Numerical Analysis · Read the full method →

Question

Write down the basic algorithm for solving the equation $xe^x-1=0$ by bisection method, correct to 4 decimal places.

Technique

Bisection (interval halving) with a sign-change bracket; iteration count fixed by $1/2^n\le0.5\times10^{-4}\Rightarrow n=15$ .

Solution

Setup. Let $f(x)=xe^x-1$ . Then $f(0)=-1<0$ and $f(1)=e-1\approx1.718>0$ , so by the Intermediate Value Theorem a root lies in $[0,1]$ . $f$ is continuous and strictly increasing on $[0,1]$ ( $f'(x)=(1+x)e^x>0$ ), so the root is unique. Bisection repeatedly halves the bracketing interval, keeping the half on which $f$ changes sign.

Step 1 — Stopping criterion for 4-decimal accuracy

After $n$ bisections the bracket has length $\dfrac{b_0-a_0}{2^n}=\dfrac{1}{2^n}$ . For the error to be below $0.5\times10^{-4}$ :

\frac{1}{2^n}\le 0.5\times10^{-4}\ \Longrightarrow\ 2^n\ge 2\times10^4=20000\ \Longrightarrow\ n\ge 15\quad(2^{15}=32768).

So 15 iterations guarantee 4-decimal accuracy; equivalently iterate until $|b-a|<10^{-4}$ .

Step 2 — The algorithm (pseudocode)

ALGORITHM Bisection — solve f(x) = x*e^x - 1 = 0 to 4 dp

INPUT : f(x) = x*e^x - 1,  a = 0,  b = 1,  tol = 0.5e-4   (or maxit = 15)

STEP 1.  Compute fa = f(a),  fb = f(b).
         IF fa * fb > 0 THEN STOP  ("no sign change — no root bracketed").

STEP 2.  REPEAT
             c  <- (a + b) / 2            // midpoint
             fc <- f(c)
             IF fc = 0  OR  (b - a)/2 < tol  THEN
                 OUTPUT c ;  STOP          // root found to required accuracy
             END IF
             IF fa * fc < 0 THEN
                 b  <- c ;  fb <- fc       // root in left half
             ELSE
                 a  <- c ;  fa <- fc       // root in right half
             END IF
         UNTIL (b - a) < 1e-4   (i.e. after at most 15 iterations)

STEP 3.  OUTPUT  root ≈ (a + b)/2  rounded to 4 decimal places.

Step 3 — Worked outcome

Carrying out the iteration converges to the root

\boxed{\;x\approx 0.5671\;}\quad(\text{the Omega constant, } W(1)).

Verification

python3: bisection on f(x)=x*e^x-1, [0,1], 15 iterations
  iter 1  c=0.50000  f<0  -> a=0.5
  iter 5  c=0.56250  f<0
  iter 10 c=0.56714
  iter 15 c=0.56714  -> root = 0.5671 (4 dp)
  cross-check f(0.5671) = 0.5671*e^0.5671 - 1 = -2.4e-5 ≈ 0   ✓
  scipy/known value: Omega constant W(1) = 0.5671432904...    ✓