!"#$%$&'()*(++,*()&-./0+1.

/*23&"""

Engineering Mathematics III

Lecture 7: Roots of Equation

---- Newton’s method

1
Bisection Method
!"#$%&'(&)*$&+",)&)*")&)*$&+-(,).'(&/.00&,*"(1$&#.1(#&"#&.)&
2"##$#&)*3-&)*$&3'')4
! !"#$%!"&$'('!
5(,$&/$&*"6$&"&3'')&&)#*+,-,.7&/$&#.8209&$6"0-")$&)*$&8.%:
2'.()&"(%&*"06$&)*$&.()$36"04

f(a)>0

c=(a+b)/2

f(c)>0

a c b

f(b)<0
CIV 303 Eng. Math. III 2
Example of Bisection Method
Use bisection method to find the solution of x2 – x = – 2.
There will be 2 roots, i.e. x1 and x2. Letting F(x) = x2 – x + 2,
Solution: |F(x )| = 0.01, |F(x )| = 0.01
1 2
Lower Upper Mid-point F(x) Check
0.0000 3.0000 1.5000 -1.2500 <0
0.0000 1.5000 0.7500 -2.1875 << 0
1.5000 3.0000 2.2500 0.8125 >0
1.5000 2.2500 1.8750 -0.3594 <0
1.8750 2.2500 2.0625 0.1914 >0
1.8750 2.0625 1.9688 -0.0928 <0
1.9688 2.0625 2.0156 0.0471 Lower > 0Upper Mid-point F(x) Check
-3.0000 0.0000 -1.5000 1.7500 >0
1.9688 2.0156 1.9922 -0.0234 <0
-1.5000 0.0000 -0.7500 -0.6875 <0
1.9922 2.0156 2.0039 0.0117 >0
-0.7500 -1.5000 -1.1250 0.3906 >0
1.9922 2.0039 1.9980 -0.0059 |F(x)| < 0.01
-0.7500 -1.1250 -0.9375 -0.1836 <0
-0.9375 -1.1250 -1.0313 0.0947 >0
Roots: -0.9375 -1.0313 -0.9844 -0.0466 <0
x1 = 1.998 ~ 2 -0.9844 -1.0313 -1.0078 0.0235 >0
x2 = -1.002 ~ -1 -0.9844 -1.0078 -0.9961 -0.0117 <0
-0.9961 -1.0078 -1.0020 0.0059 |F(x)|3< 0.01
Newton’s Method
!"#$%&'()*"$+%,)-%.)/%012&3)4567$2%&()!!89:;<
!"#$%&'()*"$+%,)-%.)/%012&3)4567$2%&()
!"#$%&'( )"$*%+, -.(% /&%#& -( !"#$%&01-2*(%&'(
)"$*%+, 3( -&%$*"4 3$"4-$3%& )"$*%+ 5%4 (%.63&7
"89-$3%&( !:";<=, #*"4" ! 3( -((9)"+ $% *-6" -
>%&$3&9%9( +"436-$36" !#?
@*" )"$*%+ 3( >%))%&.A 9("+ B">-9(" %5 3$( (3)2.3>3$A
-&+ 74"-$ (2""+?

CIV 303 Eng. Math. III 4

Newton’s Method
C(3&7 -& -224%D3)-$" 6-.9" D! %B$-3&"+ 54%) $*" 74-2* %5 5,
#" ."$ "" B" $*" 2%3&$ %5 3&$"4(">$3%& %5 $*" DE-D3( -&+ $*"
$-&7"&$ $% $*" >946" %5 ! -$ "!?

*"&>",

CIV 303 Eng. Math. III 5

Newton’s Method

F& $*" (">%&+ ($"2, #" >%)29$"

F& $*" $*34+ ($"2 DG 54%) DH -7-3& BA $*" (-)" 5%4)9.-,

-&+ (% %&? I" $*9( *-6" $*" -.7%43$*)J
f ( xn )
⇒ xn +1 = xn − !"#$%&'( )
f ' ( xn )

CIV 303 Eng. Math. III 6

Another way to get !"#$%&'()
!"#$%&'()**
1">-.. @-A.%4'( K"43"(

f ( xn +1 ) = f ( xn ) + ( xn +1 − xn ) f ' ( xn ) +!!
neglected
0 ≈ f ( xn ) + ∆xf ' ( xn )
f ( xn )
∆x = xn +1 − xn = −
f ' ( xn ) until convergence

f ( xn ) xn +1 − xn < ε
⇒ xn +1 = xn − !"#$%&'( )
f ' ( xn )
7
Newton’s Method

CIV 303 Eng. Math. III 8

Example of Newton’s Method
f ( xi )
xi +1 = xi −
f ' ( xi )

CIV 303 Eng. Math. III 9

Example of Newton’s Method

f ( xi )
xi +1 = xi −
f ' ( xi )

CIV 303 Eng. Math. III 10

Newton--Raphson Method
Newton – Algorithm

Define iteration
Do k = 0 to ….
k −1
k +1 k ⎡ df ( x )⎤
x = x −⎢ ⎥ f (x k )
⎣ dx ⎦
until convergence
How about convergence?

11
Newton--Raphson Method – Convergence
Newton

0
x = Initial Guess, k = 0
Repeat {
( )
∂f x k
∂x
(x k +1
) ( )
− xk = − f xk

k = k +1
} Until ?

x k +1 − x k < threshold ? ( )
f x k +1 < threshold ?

12
Newton-Raphson Method – Convergence

df ( x k
) d 2
f ( ~
x) *
* k * k k 2
0 = f (x ) = f (x ) + (x − x ) + 2
( x − x )
dx dx

Mean Value theorem

But truncates Taylor series

k
k df ( x ) k +1
0 = f (x ) + (x − xk ) by Newton
dx definition

13
Newton-Raphson Method – Convergence

Subtracting k
df ( x ) k +1 * d f (~ 2
x) k * 2
(x − x ) = 2
( x − x )
dx dx
Dividing through
2
k +1 * df k −1 d f k * 2
( x − x ) = [ ( x )] 2
( x
! )( x − x )
dx d x
df k −1 d 2 f k
Let [ ( x )] 2
( x) = K
!
dx d x
k +1 * k k * 2
then x −x ≤K x −x
Convergence is quadratic
14
Newton-Raphson Method – Convergence

Local Convergence Theorem

If
df ⎫
a) bounded away from zero ⎪
dx ⎪
2 ⎬ K is bounded
d f ⎪
b) bounded
dx 2 ⎪⎭
Then Newton’s method converges given a
sufficiently close initial guess (and
convergence is quadratic)
15
Newton-Raphson Method – Convergence

Example 1
f ( x) = x 2 − 1 = 0, find x ( x* = 1)
df k
( x ) = 2 xk
dx
k
2x (x k +1 k
−x )=− x(( k
)
2
−1 )
(( ) −(x ) )
2 2
k k +1 * k * k k *
2x (x − x ) + 2x (x − x ) = − x

k +1 1
or ( x − x ) = k ( x k − x* ) 2
*

2x Convergence is quadratic
16
Newton-Raphson Method – Convergence

Example 2
2 *
f ( x) = x = 0, x = 0
−1
⎛ df ⎞
df k k Note : ⎜ ⎟ not bounded
(x ) = 2 x ⎝ dx ⎠
dx away from zero
k k +1 k 2
⇒ 2 x ( x − 0) = ( x − 0)
1 k
k +1
x −0 = x −0
2
( ) k *
for x ≠ x = 0

1
or ( xk +1 − x ) = ( xk − x* )
*

2
Convergence is linear
17