Week # 3

Chapter 6

1
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Today’s Quote
“Wake up with determination, go to bed with
satisfaction!”
-[Link]

2
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Open Methods
Chapter 6
Figure 6.1
• Open methods
are based on
formulas that
require only a
single starting
value of x or two
starting values
that do not
necessarily
bracket the root.
3
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Open Methods
FIGURE 6.1
Graphical depiction of the
fundamental difference
between the (a) bracketing
and (b) and (c) open methods
for root location. In (a), which is
the bisection method, the root
is constrained within the interval
prescribed by xl and xu. In
contrast, for the open method
depicted in (b) and (c), a
formula is used to project from
xi to xi+1 in an iterative fashion.
Thus, the method can either (b)
diverge or (c) converge
rapidly, depending on the
value of the initial guess.
4
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Open Methods

Open methods employ a formula to predict the

root. Such a formula can be developed for
simple fixed-point iteration (or, as it is also
called, one-point iteration or successive
substitution) by rearranging the function f(x)= 0
so that x is on the left-hand side of the
equation.

5
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Simple Fixed-point Iteration
•Rearrange the function so that x is on the
left side of the equation:
f ( x) = 0  g ( x) = x
xk = g ( xk −1 ) xo given , k = 1, 2, ...
•Bracketing methods are “convergent”.
•Fixed-point methods may sometime
“diverge”, depending on the stating point
(initial guess) and how the function behaves.
6
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Simple Fixed-point Iteration

7
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Simple Fixed-point Iteration
Example:
f ( x) = x − x − 2
2
x0
g ( x) = x 2 − 2
or
g ( x) = x+2
or
2
g ( x) = 1 +
x
 8
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Example

9
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Convergence Figure 6.2

10
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Conclusion
• Fixed-point iteration converges if

g ( x )  1 (slope of the line f(x) = x)

•When the method converges, the error is

roughly proportional to or less than the error of
the previous step, therefore it is called “linearly
convergent.”

11
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Quiz # 1_15 Minutes
Q1. Use Bisection method to determine the real root of

Consider initial guesses of Xl =0.5 and Xu = 1 and iterate until the estimated error
falls below a level of 10%.

12
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Let the learning continue….

13
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Newton-Raphson Method
(Also known as Newton’s Method)
Given an initial guess of the root x0,
Newton-Raphson method uses information
about the function and its derivative at that
point to find a better guess of the root.
Assumptions:
– f(x) is continuous and the first derivative is
known
– An initial guess x0 such that f’(x0)≠0 is given

14
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Newton-Raphson Method
• Most widely used method.
• Based on Taylor series expansion:
x 2
f ( xi +1 ) = f ( xi ) + f ( xi ) x + f ( xi ) + Ox 3
2!
The root is the value of x i +1 when f(x i +1 ) = 0
Rearrangin g,
Solve for
0 = f(xi ) + f (x i )( xi +1 − xi )
f ( xi )
xi +1 = xi − Newton-Raphson formula
f ( xi )
15
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Fig. 6.5

• A convenient method for

functions whose
derivatives can be
evaluated analytically. It
may not be convenient
for functions whose
derivatives cannot be
evaluated analytically.

16
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Newton Raphson Method
- Graphical Depiction -
• If the initial guess at the
root is xi, then a tangent
to the function of xi that
is f’(xi) is extrapolated
down to the x-axis to
provide an estimate of
the root at xi+1.

17
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Derivation of Newton’s Method
Given : xi an initial guess of the root of f ( x ) = 0
Question : How do we obtain a better estimate xi +1?
__________ __________ __________ ______
Taylor Therorem : f ( x + h )  f ( x ) + f ' ( x ) h
Find h such that f ( x + h ) = 0.
f ( x)
h− Newton − Raphson Formula
f ' ( x)
f ( xi )
A new guess of the root : xi +1 = xi −
f ' ( xi )
18
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Convergence Analysis
Remarks

When the guess is close enough to a simple

root of the function then Newton’s method is
guaranteed to converge quadratically.

Quadratic convergence means that the number

of correct digits is nearly doubled at each
iteration.

19
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Problems with Newton’s Method

• If the initial guess of the root is far from

the root the method may not converge.
• Newton’s method converges linearly near
multiple zeros { f(r) = f’(r) =0 }. In such a
case, modified algorithms can be used to
regain the quadratic convergence.

20
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Multiple Roots
f ( x) = x 3
f ( x) = ( x + 1)
2

f(x) has three f(x) has two

zeros at x = 0 zeros at x = -1
21
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Problems with Newton’s Method
- Runaway -

x0 x1

The estimates of the root is going away from the root.

22
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Problems with Newton’s Method
- Flat Spot -

x0

The value of f’(x) is zero, the algorithm fails.

If f ’(x) is very small then x1 will be very far from x0.
23
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Problems with Newton’s Method
- Cycle -

x1=x3=x5

x0=x2=x4

The algorithm cycles between two values x0 and x1

24
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Drawbacks of Newton-Raphson Method

Fig. 6.6
25
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 The Secant Method
• A slight variation of Newton’s method for
functions whose derivatives are difficult to
evaluate. For these cases the derivative can be
approximated by a backward finite divided
difference.

xi − xi −1
f ( xi ) 
f ( xi ) − f ( xi −1 )
xi − xi −1
xi +1 = xi − f ( xi ) i = 1,2,3, 
f ( xi ) − f ( xi −1 )
26
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Fig. 6.7

• Requires two initial

estimates of x , e.g, xo,
x1. However, because
f(x) is not required to
change signs between
estimates, it is not
classified as a
“bracketing” method.
• The secant method has
the same properties as
Newton’s method.
Convergence is not
guaranteed for all xo,
f(x).

27
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Fig. 6.8

28
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 29
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
 Multiple Roots
• None of the methods deal with multiple roots
efficiently, however, one way to deal with problems
is as follows:
f ( xi )
Set u ( xi ) = This function has
f ( xi ) roots at all the same
locations as the
u ( xi )
Then find xi +1− original function
u ( xi )

30
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Examine Fig. 6.13a at
x =1. Notice that the function touches the axis
but does not cross it at the root.

Notice that the graphical depiction (Fig. 6.13b) Fig. 6.13

again indicates that the function is tangent to
the axis at the root, but that for this case the
axis is crossed. In general, odd multiple roots
cross the axis,
whereas even ones do not.

For example, the quadruple root in Fig. 6.13c

does not cross
the axis.

31
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
• “Multiple root” corresponds to a point where a
function is tangent to the x axis.
• Difficulties
– Function does not change sign at the multiple root,
therefore, cannot use bracketing methods.
– Both f(x) and f′(x)=0, division by zero with
Newton’s and Secant methods.

32
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Modified Newton-Raphson methods

33
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.