Computer Aided Engineering Design

OPTIMIZATION 341

interval for which reason the method is named so. If sign (f(xl)) = sign (f(xr)), the root lies in the
upper sub-interval and so the lower bound is set to xr. Otherwise, if sign (f(xu)) = sign (f(xr)), the root
lies in the lower sub-interval and thus xu is set to xr. Note that the bounds get redefined after every
step such that the resultant bracket is a subset of the previous one. Thus, certain search region gets
eliminated in the process for which reason the bracketing methods are also called the region elimination
methods. The iterations are terminated when | xu – xl | < ε , a prespecified sufficiently small number.

The method commences with an initial interval [xl,xu] which is shrunk progressively by half into a
new interval containing the root. If Δx° is the initial interval length and if N steps are required to
achieve a desirable interval size, ε = xu – xl, then

ε = Δx^0 /2N or N = log 2 (Δx^0 /ε) (12.1)

Thus, if the initial and final interval lengths are known a priori,the number of steps required can be
computed. Note that at each step, the three function values f(xl),f(xr) and f(xu) may not all be
recomputed. If xl is assigned as xr in the previous step, f(xl) may be assigned the value of f (xr) and
f (xu) may be retained. Otherwise, if xu = xr, then f (xu) = f(xr) and f(xl) may be reused. All then is
required is to compute xr and f(xr) in an iteration.

Example 12.1. Find the root of g′(x)≡f(x)=x^3 – 2x^2 – x + 2. Note that the roots of this equation are
–1, 1 and 2. We commence the bisection method with the initial bracket [–3, 0]. The results are

xl xu xr f(xl) f (xu) f (xr)|xu–xl|

–3.0000 0 – 1.5000 – 40.0000 2.0000 – 4.3750 3.0000

–1.5000 0 – 0.7500 – 4.3750 2.0000 1.2031 1.5000

–1.5000 – 0.7500 – 1.1250 – 4.3750 1.2031 – 0.8301 0.7500

–1.1250 – 0.7500 – 0.9375 – 0.8301 1.2031 0.3557 0.3750

–1.1250 – 0.9375 – 1.0313 – 0.8301 0.3557 – 0.1924 0.1875

–1.0313 – 0.9375 – 0.9844 – 0.1924 0.3557 0.0925 0.0938

–1.0313 – 0.9844 – 1.0078 – 0.1924 0.0925 – 0.0474 0.0469

–1.0078 – 0.9844 – 0.9961 – 0.0472 0.0925 0.0234 0.0234

–1.0078 – 0.9961 – 1.0020 – 0.0472 0.0234 – 0.0117 0.0117

–1.0020 – 0.9961 – 0.9990 – 0.0117 0.0234 0.0059 0.0059

–1.0020 – 0.9990 –1.0005 – 0.0117 0.0059 – 0.0029 0.0029

–1.0005 – 0.9990 – 0.9998 – 0.0029 0.0059 0.0015 0.0015

f(x)

xl xu

x

xr =^12 (xl + xu)

Figure 12.3 Bisection method