.

o n t·e
C n ts

Pr efa ce V

me ric al Co mp uta tio n l

Ch ap ter 1. Er ro rs in Nu
l
l.l . In tro du cti on
2
1.2 . Co mp uta tio na l eff ici enc y
..~ ?
v
1.3 . Co mp ute r ari thm eti c
5
1.4 . Fl oa tin g po int for m
6
1.5 . Er ro rs
7
LG. So urc es of er~ors
7
1.7 . Lo ss of sig nif ica nc e err ors
8
c
1.8 . Er ro rs in co mp ute r ari thm eti
9
1.9 . Er ro r pro pa ga tio n
11
ns
Ch ap ter 2. S~ lut ion of No ~li ne ar Eq ua tio
11
2.1 . In tro du cti on 12
2.2. Bi sec tio n me tho d - 15
2.3. Fix ed po int ite rat ion 19
2.4 . Ne wt on 's me tho d
23
2.5. Se ca nt me tho d . 25
2.6 . Re gu la- fal si me tho d
25
'2.7. Mu lti ple roo ts
25
2.8 . So me nu me ric al res ult s if
tial Eq ua tio ns 29
So lut ion of Or din ary Differen
Ch ap ter 3. 29
3 .1. Int rod uc tio n·
,. .. ~ •.· 30
3.2 . ~u ler 's- ~e th od ... ,
.·. ,
~c ati on err ors 32
3.3 . '1.o c~l ~nd ·gl ob al tru
3·5
3.4 . 'Ta ylo r me tho ds·
3.5 . Ru ng e-K utt a me tho ds
• •• • • 1 ,: •
31

iii '
 ··- - - - - -
J

iv
Co nt eb t, .!i
t
S.6. St&bility
~
3.7. Fi rs t or de r gystems
tio ns 47
Sy ste m s of Linear Eq ua
Ch ap te r 4. Solutio~ (.'f 47
4.1. In tro du cti on
48
ion
4.2. Ga us sia n Elimin:\t 51
on algorithm
4.3. Gaussian eliminati Si
4.4. Pa rti al pivoti11g .5~
vo t:n g
4.5. Scaled pa rti al pi 58
4.6. LU factoriza.tion 60
s
4. 7.Vector an d ma.trix no rm 61
tio n
4.8. Er ro r of ca ku la te d so lu 62
d
~9 . A pr a. ct i~ .error bo un ~
• et ho d
4.10. ·Residua.I coirecti.oa: m 66
. d
4.11. Ja co bi itera.tive m et ho 68
bi m et ho d
4.12. Convergence of th e Ja co 10
ra tiv e m et ho d
4.13. Gauss-Seidel ite 72
th e ite ra tio n
. 4.14. T~~:nination of 73
ho ds
di re ct and ite ra tiv e m et
4. 15 . C om p~ n· ·o r
n
tio ns
-C ha pt er 6. Ap pr o~ ~a .ti on of fu nt 75
S~l. Introduction· . 16
5.2. Lagra.nge form 77
difference formula.
5.3. Ne wt on 's divided 80
no m ia l
6.4. Error of the interpolatf_ng po ly
\

Bi bl io gr ap hy
ent Exercises
Answers to Se lf Assessm
11
ss
Examination Papers

r I
,.

r -
.~, ,..
•'
. ' ....
 Cl1.a pte r 1

Err qrs in ~ um eric al Co mp uta tion \ I

1.1 I_n trodu ction

T_his co'!~e is c~ncerne_d with the use of compu ~ers to "solve~ mat}:le
lems. ~e use, an olgonthm, a. well defined sequ~n ce of opera.t1ons tha.t
matica l pr \ 1
leads to ·:·. .
.!t
· a.pproximate ipliitio n of the ]>roblem. In some cues the algorit hm ma.y give
the
..:; ··-· ·;o11,tion if enct
i.rithmetlc ls used, but· as ~omp~ ters do not use· exact arithm · ·) m
r. ·••

(excep t for integers) t~e

final result will usually be· a.pproxinia.te~ We will comp _mp_ ~t
differe nt algorit hms and their implem entatio n -with regard · to efficiency
and accuracy ·UT
a_nd discus s how the errortin the final r~ult ca.n _be ~tima ted.
~-
Consid er tbe numeri cal solutio n of the quadra tic equatio n
_ax 2 +b:c+ c= 0 .
We know the solution is '
-b± ✓b - 4ac 2
x= ---
2a
---
a.nd tha.~ihere are 3 possibilities; 2 distinc t realroots, 1 repeat ed root, or 2 complei . pmpl r.:
. roots. Of course we ca.n determ ine which case applies from the sign of the
discriminant piir; ,
D = b - 4ac.
2

if we a.re only concer ned with the real roots, then we could use the·following algorith1L

Algorithm to solve a~~ + bx + c = 0

1. Input coe~f icient s a,b,c
2. Comput~ D=b 2 -4ac
3. If D<O, print "Roots are complex" then stop
4. If D=O, print "Repe ated root= -b/2a" then. s t ·.: .
·I
!..
;
;
i
5. Calcu late .Root_ D=sqrt {D), xl= (-b+Ro ot-1)) /2a,
-~ t• ~1;~:!~-~~~,~~~~
, .. •rr :, •~,'!\J ·'" "'' ' ••..- •'· 6. ··r..-u.u1.·~"noot$ ·.are ..f~!#,.Y
x1
,,.~.~~d..~~,R~ff.U.'-"'·ed) :;,_. \,..
x2' an stop· ·
1
'1• t1111 _. ,i•)l••· '- ~-tl~: .\
• • t. , • • ' . . ;:
f ' I
.
, . :

· The soluti~ ns giv~n by this algorithm. wh~~ ~oded° in QBasic ~~d Turbo Pascal and the- . .
a
exa.ct &<>l~tio_~s are given in 'Th.ble 1 for number of-quadratic equati ons. In standar
precision, which · was usecr to ,pr_o duce the results , QB'asic has about 7
d ; ~an~ -':..
decima l digll - ; ·~al
accuracy and Turbo Pascal. h~ about 11 decimal digit accur~ y; A box
has been .. ·. ;~
_r-;{ t··
t~ 1 ,._, ;
: . ,·
 2 :r 2 +b x. .-, lO 0
O
of nu mo ric ru wl ut io n• of
TABLE 1. A comp a.r ison dr a.r n a.roun d th e dtg t t.8 th
at
h :l.!i be en
wi t~ t.he tx ac t solu tio n. A
bo x

are mcorrcct. -
-
Ex ac t
..,- ''J'u rb o P a..1c.a.l
b QBasic -
·2 _5219 14 77 R11? rf0 0
-
2.6 27 91 4 77 86 BE +o o
78 68 E+ oo
- 1. l 2 . 5279151': ➔ 00 - 1.9779 14 77 87 £+ 00 - L9 77 91 47
- 1.9 779 15 £+ 00 97 E+ O0 6. 2943 61 71 96 9E +O 0
6.2 94 36 l 71
89 E- 01
-1 1 6.294362E+00 - 7.94361 719,6 9E - Ol - 7.9 43 6l 71 96
- 7.943-619£ - 0l - 5. 50 90 7593228E+-0 1
6.5090759323E +0 1
.0759 3 22 64 28 E- 02
- 110 5.5 0907 6E +0 l
- 9.07593 22 6fmE--0 2 - 9
9.0 75 9fm £ 02 5.5 0009 09 0769.E+-02
5.5 00 09 09 01 6E +Cl2
5.500 09 l& t-D2 - 9 .09 0768 83 29 2E -0 3
-1 10 0 9.090 75 8'I 94 4E - 03
9.0~ 03 5.5CM 00 90 90 9 E+ 03
5.5 00 00 09 09 1E +0 3
5.5 00 00 1E + 03 -9 .09 09 07 58 82 8£ - 04
-1 10 00 04 9.0 90 90 fl~ 2l llE -0 4
9.rrn5o2 SE 5.5 00 00 0009 09 E+04
5.500000009 lE +- 04
5.5 00 00 0E +0 4 -9 .09 09 09 07 58 8E - 05
-1 1 00 00 9 .08SiOSS~S2E ~os
itOOOOO~+ oo 5. 50 00 00 00 00 9E +0 5
S, S0 00 00 00 0l E+ os
- 11 00000 5.500000E+05 -9 .0 90 90 90 90 76 E- 06
~gQQQQ53E- 06
O. OOOOaE +OO -9 .()3 6 -5 .50 00 00 00 00 0E +0 6
5.SOOOOOE+06 5.SOOOOOOOOOE+0
-9 .0 90 90 90 90 91 E- 07
-1 10 00 00 0
~.QooQO!JE+OO ~-Q~Oo~onoo@+oo
e lar ge r
in the co mp ut ed so lu tio n~ . In bo th ca se s th
t dig its se co nd
dr aw n aro un d the inc orr ec cis ion , bu t th e nu m be r of co rre ct di gi ts in
pre
ro ot ha.s be en fou nd to ma
ch ine
lin ea r te rm is} nc re as ed . Du e to th e hi gh er
eff ici en t of the di ng
ro o t dim ini sh es as the co
sc al re. su it is m or e a.. ec urate th an 'th e co rre sp on
Tu rb o Pa
pre cis ion ari thm eti c, the ·
QB as ic res ult . · e will
on g wi th th e ca lcu lat ib n of th e se co nd ro ot . W
go ing wr na tes
Ob vio us ly so me th in g is
sim ple mo di fic ati on tc, th e al go rit hm eli mi
see ho w a
see lat er wh at· this is; and
th e pr ob lem .

1. 2 C om pu ta tio na l ef
fic ie nc y

of alg or ith ms ca n be co m pa re d by
co un tin g th e nu m b er
Th e co ~p ut ati on al -effici· ency ad •h
d. . ons an d su bt ra ct io ns re qu ire d for ea<;h al go rit
lt
of mu- • pli ca t· d' · 1t1 m
. ions, 1V1S1onsra 1
t). . : . .
(1.e. hy co mp ar in g their o~ tio n co un
.
fol low ing alg or ith ms fo r ev a.l u t·m g t h e po l yn om 1a l
ex am ple , co ns ide. r the , a

Pn(x)::: au + a1x + a2x2 + .. . + an x n _

t:.u , Ji case it is as su me d th at a a an , n an d x ar e gi ve n ·
lJ , u, 1, · · · ,
·
sw n~ a( O)
·
.·,., ., .J . . .... .,•
. .
' ' ..
Fo r i==1 · t~ 11
SW n= sw n-t -a( i) xx i
End Fo r ·
.
Op er ati on co un t: n +' s
t

I n X s, n ex po ne nt iat io ns .-
 ~ ,.,,-> vvwp u t_cr n~1th molt c
3' 3

SUmP'll(O)
x_po1:rer ..11111
Fox- i•1 to n
.x...po we r JI!:} x, xx; ...po~ or J
,um•aurn+-a ( i ) x x...po,:r or _i
End For
Operation count: n +'s , 2n x 's, (0 exponentiat ions).

sum•a (n) · l1
For i,•1 ton
inun•a umxx+ a(n-i)
'End For
Operation count: n +'s, n x's.

The la.st algorit hm is clearly the most efficient, a.nd ·is equiva lent to writin
g p,. (z) in
the ne•ted Iorm
· Pn (x) = (·· · ({an:i: + an-1)z + an-2)x + · · · + ai)x + ao.
1.3 Comp·u ter arith metic

We use a base 10 {decim al) numbe r system, but compu ters use binary numbe
Z) or some system based ort binary (octal (base 8) or hexadecima! (base
rs (base
16)). Just as
J
=
376.21 3 X !°0 2 + 7 X 10 1 + 6 X 10° + 2 X 10-l + 1 X 10- 2
the base b numbe r
n
(d3d2d1do,,cL 1d-2)b = d3 x b3 + d2 x b2 + d 1 x b1 + do x b0
+d-1 X b- 1 + d_2 X b- 2 •
Here do, di, .•• denote a. base b·digit, that is a.ny of 0, 1, 2, ... , b- 1. For
hexad ecima l
numbe rs A, B, C, D, E and Fare used to repres ent the digits 10,11, 12,13,
14 and 15.
JWork ed Exam ple 1_.3.1 Express (A6.D2h~ as a. decimal number.

(A6.D 2hs = 10 X 16 + 6 X 16° +.13 x 16- ·+ 2 X 15-

1 1 2

= .~160+
.
6+
13
+~
. 16 . 256
'= .16'6 + 0.8125 +. 0.0078125
=' '166.8203°125 I
It •18 11 .
• easy convert from decim ~ to b~e ·b. Suppo se x is a. decimal intege r and
l"·•,•;•·.l tt·•,r.~- • ,; .,;"~j, .. ,.,,,;:); dlt\,;:;: 11,(d,.dn ~t ·~·· di.do) • ..,. ,,111: ·,1.~+f>·• '
...,• ., ·''"'~''': ,. ' . ') . . ;1: 1·
.
Then. dividing by· b gives ·.
. : dn x· b" + dn~I X b"~ 1 +·•· +'d1 X b1 +.do·~ b0 •

X .
- = d X bn-1 + d· .. X bn-2
.b ' n . . •. . '.+
d +:
.
do
n-!., 1., +b
integer - < : , •. .
 ut ot1()
Er ro rs in Nu mcrlco.J Co mp
4 , C hn pt cr 1
. - --......~
the rem ain de r Wh
t h e . rem ain de r when x is di\(jd _ed by b. Sim ilarly d 1 is en
5
o is
~ cl_
by 6; ind so on . '
l ie integer pa rt of :r /l 1 is div id ed
cim al fra ction (0 < x < 1)
Now :s uppose th a t x is t he de
:t (.d _1d-2 . .. )b
d_l X b- 1 + d_2 X ~-
2 + ·· •
Mu ltip lyi ng by b gives
bx = d_1
........_., + d_2 x b-
1
+. · · ·
. ~n teger fraction
multiplic ati on by b givei!I d- 2
, ~ - 3, • • •
eg er pa rt of bx . Re pea tec:l
so d-1 is the int

am pl e 1.3 .2 Co nv.ert the nu mb er 25.59375 to bin ar y.

I W o rk ~d Ex
,,
S tar t wi th the int eg er pa rt:
· rertf ainder
2)2.Q 1 . ~
2)12
0 =. d;: !
2)§
0 =d 2_
2).B.
1-= ·ds .
2)1
0
1 = d4

Th us 25 = (11001)2.
nverted :
Th e fra cti on al pa rt is now co
0.59375
int eg er pa rt ..- .
x2
1 = ·d:..1 ·
[IJ .18 75 0
x2
@ 37 50 0
X2 ·
O = d-a ··
@].75000
x2
[].soooo 1 = d_ 4
X2
1 = d- s
[Dooooo
es
0.59375 = (.100011)2, an d combining the two res ult s giv
Therefore - .
25.59375 = (11001.10011)2 I

s 1. 3 .-
; _. Se lf As•se ss m en t Ex er ci se .
·riu_mbers: (a) (11 01 0L ll0 1)2 ,
1;

' res en tat ion ~ of the folJow iAg

l. Fin d the de cim al rep
) 6~
(b) (34 .27) 8 , an d (c) (3 D.9F 1 oc tal an d (c) h~xa.decimal.
t 46 .70 31 25 to (a} -bin ary , (b-)
2. Co n ver
 5 . ~
I
),

§ 1.4 Floati ng point form

point form
1.4. Float ing
AnY base b numbe r z can be put into the form, with d1 -:/= 0,
. bEf--e xpone nt
x
.
=
s1gn(x ) .d 1 d 2 d3 ... X
-.:...... ..:,..
mantis sa.
se only P
The number of digits .tha.t -:a.n be stored in a. compu ter is limite d. Suppo
_the
digfts can be . used for. the mantis sa. If the numbe r Qf digits .~ larger than P,
If the manti ssa
ma.ntissa. must be ckop~ d (trunc ated) or rounde d back to p d1g1ts.
on of is
h·~ fewer than p digits it is filled with O's. The· floatin g-poin t repres entati
:c

denoted by fl(z), and

=
. fl(:r:) .sign-(:c).d~d;d; ••• ~; x bE~
al M1_~
The exponent E is ~tored as a base b intege r and is restric ted to some interv
E ~ M 2 • The amalle.st n~mbe r, other tha.n 0, is.
S .100 •.. 0 x bM1 , =
and the largest is ," I
.
L = .ccc; .. c x bM-i. (c is the larges t digit)
rs, the numb er
There is a. finite numb et of possib le floatin g-poin t or machi ne numbe
for b , 2,·p = 3,
depending 011 b,p,M1 'and M 2 • The positiv e machin e numb ers
Mi= -1 and M2 =
1 are shown on the real numbe r line in Figur e 1.1.

FIGUR E 1.1. The positive bin.a ry numbe rs with three digit mantissas
a.nd ~ne~ ~-·l,O or 1.
ing is used
If r~u~ding is used, fl(z) is the closes t machi ne numbe~ to :c, but if chopp
fl(z) JS t~e next I?achi.n~ n~m_ber in the directi on of O (see ]?igur e
1.2). In both
errors are also
~ the error of convera1oil 1B called the round -off error. Roun d-off
mcurr ed wheaevel'. fl.oa.tjn"g point numbe rs a.re used in a. calcul ation.

JE
1 .1zr .
'

Round ing Chopp ing (a: > O)

FIGU~ E ~.2. ~nv:er sion of a numbe r x to the float.iing point nu m b er

fl(:c) ';)Y round ing or chopp ing.
·1r the· result of any ····•"'t···· ;:·: ,.. ., ... ,.,.,.; ......,. _,. ·~r" •.r ··•·· ,. - .
fffl'Je~Jio;,, ~ 'sJd to h>.~~
mb:!":~::a1~;8s:t ~~~ "b~et ~/~i n Sa magn
• '1

~cCu;rd (the ~_
verl . ou, occurs a.nd"progra.m· .generally "bbmb ,, h a.s itude larger than L
resu t . s w en an attem pt is made to use the .
,.,,
T he va.lues of 6, P~ M.1 , ·u.12, ·
type of conv . ( .
handl ing of
underflow a.n.d overff,ow are all comp ilere:; :n::~n a~o-g -or chopp i_n_g) and
. or exam ple, tlie IEEE stand ard
 · '-'Aa.p c.er J.

fo r sin gle precisio n rcl\ls is 32 bit ( 1 byt~) words with b = 2, p er 24, M, = -12G '-l\

=
M2 127 .

1. 5 E rrors
h ,,
\t is ofte n imp ossib le 0 1 impra.c tical to fi nd tli i>1 e~~t solu tion t o a ma l en~a ti,
pro blem . For exa mpl e, it 1s impossi ble to find fo er' . dx exa-ct ly, ao<l improctieat
l,

so lve a large number of li near equatio ns exac tly.

T he e rro r of a com puted value is define<l a.s
---
;,,._ pe.,odefi::rf~()
E rror := exact value - ap proxim ate value.
No t e that t he sign is retained ; it tells us whethe r the approx imation is too la
rge 01
t oo s m al l. The relat ive error is defined as
Error i~ l rro r - f
Relativ e Error t J • ~ - - - d 1,,.h)fl
=
x=
-~ - - : - -- -.:e.:. .::
ac=-::_:v-=a:=. u: ::.e.....;. J t, I fqf fen er- /
The follow ing notation will be used :
XT - true or exact value
X -
approxi matiQn to XT
Error - xr- xA
XT - ZA
Rel. Error - XT
xr- XA
~ XA

Usually we will not be able to calcula te the error because the exact value
is not known,
an
b ut wi ll only be able to show that IErrorj .$ A for s ome ·numbe r A which is called
error bot.nd. A relati"ve e.rror bound is defined similarly.
Tl1e approx imate value xA has m signific ant digits with respect to XT if the (m+
l)th
digit of the error xr - xA, countin g rom t e first non-zer o digit of XT, is < 5 and the
previou s digits are aLJ zero (the maxim um value. of m is underst o.o d).

✓ I Worke d Examp le 1.5.1 Calcula.te the error, relati~e error and number
of signific ant digits of 125/46 as an approxidJJtion toe. . ·

Error - xr - x A. ....
o,g -.::>(c:JJ u1 o~ 0).2.
_ 12s·
e (O,fll 010),2.
-
-
·0.00089 ./
46
.. .
; 1·,. l. t 1 + .L
"' 1 i . 32
· Error
Rel. Error -
XT :: 0,906215
o,0° 6ir .
0.00089
' e
error 1,:=/ ' o, 0-
.· ' •,, .. . , •. , , ,. ·~-P .,· ,; 11•r I
, ' ·•, 1": ..°"'
.·'· ···= '. 0.00033 ✓:
·: ~,09 3·
xy - 2.71/8281..
._;' o, 0061 [
E;rror 0.00/089
. . · § f. 7. Lo.s s of si.gniflc.a ncc crro r u 7

posa !Lle wJ1il1• k1•••p1nc Lh r

The ve.rtlc-1 ,line is pla.cod as fa.r to th o righ t a.s
<li!) il.6 of :x 7 L<, th e left of
ne~t ,digit of ~he erro r < b, a.nd th e num ber of
125/ 4 6· 2.7173 0 .. ha.a 3
thas hne is th~ number of •sig niflc ant digits . Thu s
slgnifica.nt digits. I

. rcis es 1.5
Self Ass essm ent Exe
ifica nt digit s of 1.73 as an
l. Find the error, relative error and number of sign
a.pproximatlon "8. · of digi ts of 9.87 as an
2. Find the error. rela.~ive erro r and num ber
of sign ific~ nt
2
a.pproximation of ,r •

1.6 Sou rces of erro r~

lly is affec ted by seve ral diffe rent
The numerical solution l>f a. prac tical problem usua
error s. The erro rs ma.y a.rise from:
,
or assu mp-
l. Form ula.t ion .of math ema tical mod eJ-u sua.l ly some appr oxim ation s
tion s a.re ma.He. '
lations, but can be mad e in a
2. Blur iders -nor ma.J ly asso ciate d with hand calcu
n).
prog ram (test with cases where the answer is know
will not be exac t.
3. Erro rs in da.ta:-a.ny measured quan tity
4. Rou nd-o ff erro r-re sult s from usin g a. finite
number of digit s in calcu latio n .
fro~ appr oxim ating an infin ite
. 5. Trun catio n erro r-ma ihem a.tic a.I error resul ting
. process .by a finit e one .(ma.king the sol~tion possible!) .
. ;

.
a.lgo~lthm
--
S~m'e of tliese erro rs ·a.re una.voida.ble; the a.im
s ·tha. t mln~mlze their effect.
of num erica l anal ysis is to design

1.7 Loss ·of significan~e errors

. . . '

almo st equal value a.re subt racte d sign ifica nt digit s are Jost.
Whenever ·two· numbers o(
For example, : ·.
13.13519
.--:-13.13621
-~ z .1i,
lost slgnificant digits
. ', j

The prob lem of loss of significance can often be

overcome by restr uctu ring the cal-
good example. The roots are given ;,,1-
. ~ulation. _F indin g the. roots of a quad ratic is a :t
·r ·,, •·- ·", • .,;. ,:,
,. '''J'.- 1,' • ,W,.jlf/1, •~ •'JI " .. :,, "ti . " , .. ,lf,::ct ;A·.•.-il,!1:, t• ••- --11~1 •' 11 . · ·\ ••

-b ± ✓fil - 4ac
~= 2a-
11

. and if .l4acl < 1,2' then ~

Jb 2
-- 4ac ~ /b/
- · C_bap~er 1
8

and so on.e of the roots will suffer from loss of significance. This is overcome by t~~... ·
-b - sign(b)Jb 2 - 4ac
XJ = 2a

(there will be no loss of significance), and using th~ fact that ax1x2 = c to ca1c~11

C
Xz=-.
ax 1

When the programs that were used to generate tl:ie results tabulated on page 2 w\
modified in this way 1 all digits of both solutions were correct for all of the qua.dr~
eq ua.tio ns_

I Worked Example Evaluating the function f(x) = ~

1.7.l -
Jx--=-1 for large positive values of:: leads _to Joss of significance errors. Mo
jfy the function to avoid this problem. ;

(vx + 1- ✓x - x ,/xTI + ✓x -
1
J(x) - 1)
✓x + 1 + ✓x-1
(x + 1) - (x - 1)
✓x+l+Jx-=-I
2
=

There is no loss of significance errors involved in the evaluation of this for:

since ·the almost equal numbers are being added _ . Note that f(x) ~ 1/,/xft
x»1.I .

Self Assessment Exercises 1. 7

l . Suggest an alternative form of the function f (x) = +
✓900 x - 30 that avoi ·
loss of significance errors for small values of x. '
'2 :,,1odify the function = J(x) l - J(x 2 - 1)/(x 2 +
1) so that loss of significaD :
- - . .) =~ J. ~-l a.·.r, ide d when it is evaluated for large x .
=
. • _:,! ·.:-: ~ Lr.~tion f(x) 1 - cos x 2 in a form that overcomes the loSS
, -.g r. 1:1 -:a..,1ce error when it is evaluated for small values of x.

1.8 Errors in computer arithmetic

We have seen that a small error, called a round-off error, is usually incurred wbe
ever a number is input into the comp~ter or an arithmetic operation is perforlll,
These errors ca~ not Q,e'· a.voidecl-, .~ut they -can be reduced by us\ng_.higher prea'
arithmetic. · ·

T he effect of round-off error~ can· often be reduced by careful design of the algorit~
As an example, consider the situation where Xi = a+ ih, i = 0, 1, ... , n is used
a calc ulation inside a loop _ The value of xi can be 11calculated in the following wa.J'
11
 0
., ,, § 1.9 . E~,r.ror pro pag nti on
..... .

x•a
Fo r 1 • 0 t:o n
Fo r i .. O· to n
x• a+ i•h

x-=x+,h i
Erid for ~
End Fo r ', '
or
rat io ns as, for
of req uir ing fewer ari thm etic ope
!
t me tho d has the adv ant age
The firs sec ond metho<:I.
i, onl y one + is nee ded rat her tha.n the one + and one x for the rou nd-
eac h
sec ond m~ tho d giv es a. mo re acc ura te res ult bec aus e onl y two
However, the nd- off err ors are
erro rs a.re mc utr ed in t·h e calc ula.tion of eac h Xi, while i - 1 rou
off ·
Xi in the firs t me tho d.
accumula..ted in the cal cul atio n of
low . For exa mp le,
etim es a ca.l cula .tio n can be mo difi ed to avo id ove rflo w or und erf
Som z
= v~ ◄ + y◄ ma y cau se ove rflo w for larg e X and y eve n tho ugh
the cal cul atio n of z d by wri ting
ber . Th is ove rflo w can be avo ide
lssmaller tha n the lar ges t pos sib le num

4 lxl ~ IYI
z ={ x {11 + (y/ z) .

y-1/1 + (x/ y) 4 lxl < IYI•

1.9 Er ror pr op ~a tio n

ans we r
is per for me d exa ctly usi ng num ber s tha t con tain err ors , the
If a c.a Jcu lati on d fro m X,< .
tain a pro pag ate d err or; Sup pos e an est ima te ·of f(z r) is cal cul ate
will con
Now the err or of /(z A) is ·

Err or (/{z A)) - /(t:T) - f(x A)

zr and XA (M ean Va lue Theorem)
- f (c) {tr - XA) . c bet we en
;::::: f'(: cf) (xr ..:_ zA) ·
- /'(iA) Err or (xA).
n of 2 or mo re va.ria.bles is
Th e equiva.lent res ult for a. fun ctio
8/
Err or (f(x A, !IA, ... )) ~ - (xA ,YA ,··· )Er ror (zA ) .
8,x
8/ '
+8-y (xA , YA, ... ) Err.or (YA) -1- . .
is usu ally
ors in YA, ... a.re kno wn , so this res ult
Ge ner ally onl y bou nds for the err
XA,
·
used in the for m
 ~

10 Chapt er 1 Er·r ors in Numeric al c"'u~(l

..

I Worked Example 1.9 .l Fjnd a bounq (Q.._r the error ~d tel;.t

if the function c,: sin 11 js evaluated for :r = 1.34) and V == ~' 8S3~ 1,'
all th e digi ts of x and y are significant.

Denote· f (x , y) = es: sin Y, :rA ·1.34 and YA = 1.8. Since all d:

=
significant, \Error(xA)I < 0.00~ an~ f.Error(YA)f ~ 0.05. Now
-
a;{xA, YA) IIError (:r.A)I.
+ 1a1
!Error! < .a1 . _
.0y(~.Adl.A) J Errorr f

- ler..t sin YAIJError (%A)I + le.rA COSYAIIError (YA)/

< (3.7192)(0.005) + (0.8677)(0.05)
- 0.062 ..-
1.e. IError! < 0.062
Also el.~ sin 1.8 ~ 3.7192, so
0.062
!Rel. Error/ < _ = 0.017 I
3 7192

Se lf Assessme nt Exercises 1.9

1. Find a bound for the error and relative· error in calcu1atin · ·

correctly rounded value x.A. = _
0 986 _ g z sin x usrn
2. Find an app~ox.imate interval in which the true value of tan-1 ~ . ~
evaluated using the correctly rou d d val ..,/v'Y 1i~
• n e ues XA. = 3.3 and YA = 0.234.
 {(1 ) ;; Q
)(,. : b ,\ .rea I 3 F(y -1i) -.: DI mo f a
X f, ; pen ye( or a ro r f ( x J ';: 6

C h a p te r 2
I
,.·
ti o n · o f N o n li n e a r E q u a ti o n s
S o lu
1,

2.1 In tro du ct io n 1,
the so lut ion of a no nl in ~ eq ua tio n f(x
) =
0. W h ile
ern ed wi th
Th is ch ap ter is co nc no t.
n be so lve d ex ac tly , mo st can
so me no nli ne ar eq ua tio ns ca. the
f(r ) 0 the n =
we s~ y r is a. root .~r so lut ion of
tha .t =
~ a.nd f '(r ) :f; 0
If r is a. real nW llb er &uch e fuu~ ~~ ff:.~ f(r:_)
equ a.t ion /(z ) = · O. t\Vealso cal l r a zer o of th·
·
the n r is a. aim
_____ ple root (se
_ _ . ; . __ _ e Fig ure 2.1 ).
____
_ _.J'

-to,ca (}.l;\~) r !.d

FI~ UR .E 2.1 . A sim ple
roo t r. ~~--0;,'y~
.
. ( ~ , 2. J
2
?
<t- 1 '<l r 1.J t o · \ · ·u
eg er, we sa y that ,:
Ho we ve r, [_ /(z ) _(z__-:__:.~:
_~.{~) _-~h_e._r_~ '-(r:)_.i...9.~~ m __? l _is an int I ~
or de r m. In thi s ca se flk 1( r) == 0 fo rk = 0, 1, ... , m -
,~
r is a roo t oT '!fjll;#pTicity or
an d'J (m )(r ) :/; O. -- ·-· -- ·· · ·
----

,_/
7 . r1, odd X
m>
r
1, ev en
m _-;;/
,,
. lti pli cit y m > 1.
FIGURE 2.2 . Ro ot. s r of mu '
I

n,a .r''equatfoiis ·'a.ri'."it~rative me tho ds where-~ sequence ;:

.. Tne metli~ds for ~tving nonll is ter mi na ted once· a •-.~
ite rat ion
lut ion is ca lcu lat ed . Th e
s to ~he so
. of ap p~ ox :im ~ti on ra. ~ est im ate is fou nd . · .
suf fic ien tly ac cu
ma.ny ,
, a. fin ite nu mb er of roo ts, or- inf ini tel y ;
An eq ua tio n /{mb z) = 0 ,rriay an d the ir
ha:ve· no ro ots
· nd usi ng a i
roo ts. Th e ~u er of ·r;oots ap pro XI ma te va lue ca n oft en be fou
ske tch . ·· ,.- ·

11

l.
 I t l • I ' ,

( ' li n p( ,•r ? ' i n )11f Int i ()f Not1 llnrl) r Er11J n tl, J,, .
11 2

I \ ,\ !nd<..-<l 1: :xt\ltt pl r :· J I J ),, trun1 11r th r AJ>flrr,,-i m at,o v ... Ju r. ~ ofth 11 rr,,,,.
(l[ a' '.l ... , . 4

'f l"\<'t'q U l.l ·l<"I O( k h l)('Wl l ltrn , , e' -1 :- 2 ao Wfl 1kctch th e fun ctfionn
h
v 11: , ,
'
I
r<l 1n1.to ot e pn!1 "4
and v c 4 :1 'o n th tiaft 1J)l'l\XC \ 1tnrl r.-t t lma t 1J th r z;r.oo
n [ in l CNC"< ti nt\

with r1 ~ -1.9 5 and

F1om th e sketch, we can see that there are two roots
r2 ~ l. I

Se Jf A ss e ss me nt Exer cise s 2 .1
ate value of the roots of
1. Using a sketch deter mine the nu1nber and appr oxim
1

cos X - X + l = o. =
of e-~ + cos z
2. Dete rm ine the appr oxim ate value of all of the roots
0.
-
2.2 Bise ctio n met hod
opposite sign (/(a) /(b) < 0)
If J(x) is cont inuo us on {a, b] and /(a) and f(b) have
is 6~ly one root in the interval,
t hen there is at least one root r E (a , b). Supp ose there
'· !. 1 .. inter val is halve d , the subin terva
l whic h conta in~ the root can be determined,
.. ; r. -. is proce ss conti nued until
the root ls know n _to aµfficient a.ccura.cy. In Figure
val by (a 1 , b1 ) and so on,
·1rigioal interval is deno ted by (ao, bo), the next inter

-- . .- . j - -- - -
C 1,

ILJ //
/

f1GU HE t.J .
tion meth od.
An illustration of the bisec':·. ' .
Suppose that we know that the root lies in the interVcµ (a,
b) We calculate c == (a+b)/Z
E (c,b) so a is replaced,.bY I
.(the midpoint of the inter val), and if f(b)J(c) < ·O·th en;r
now have an inter val w hie:_ is hali _a$
,. c; other wise r E (a, ") so b is re place d by c. We

. '- J
 11
§ 2 , 2 , B is c c.t fo.n motho<'1

tlon o f t he in t cr vaJ jj r<:p e a.t cd unti l w e r.an

lon g e,n d s t.ill con ~aJn s t h e ro o t . T his biMc
.cy.
es t im a.te t.h c root to t h e rcquirc:d oc cura
t itna tc
t irn a tc of th e roo t . S uppo oc t h.½.t an C"..S
At ea c h s tage we t.a k o c as t he curr ent e.s Tl c an be
~ l , w h e re ( is a g iven to le ranc e .
of t he root is req uir ed s uch th a,t !e rror ! o f 1J
not hc· fu r l. hcr fr o m r. t.h :1n th e di s t. a. nee
secc from the follo wi n g fig ~1 rc tlrn t r can
n is te r min ated whe n b - c S c
fro m c, t hat is Ir - cl S b - c so t he ite ratio

a C b
I
FJ GU.R.E2 .4 . At any stag e of the bisection met hod
tween r a.nd c mus t be $ b - c.
the dist ance be-

I
.j
i

Sim ple bisection algo rithm

1. INPUT a.b and tole ran ce £

2 . . Cal cul ate f (b)
3. Cal cul aie c=( a+b )/2 k f(c)
4 . If b - c~ t ,or f(c) =O gQ to 7.
b=c &
5. If · f(b) f(~) <O then set a=c else set
f (b)= f{c)
6 . ·Go to 3 . ·. ;
7 . OUTPUT "Ro ot = c '' and stop

2.2. 1 Use the bisection met hod to find

the roo t of
I Wor ked Exa mpl e
to a to/era.nee of 0.02 .
x - 1 = e- :r that lfes in the inte rval (1 , 1.4}

e gives:
Let / (~) = z - l - e-%.· Putt ing the resu lts in a tabl
a b C /(b) J(c~ f(b) f(c) acti on
1 1.4 1.2 · +0.15 -0.1 0 <O a= c
1.2 1.4. 1.3 +0.1 5 +0.0 27 >0 b = c, f(b) = f(c)
1.2 1.3 1.25 ·. +0.0 27 - 0.037 <0 a= c
1.25 1.3 l .27~ +0.027 - 0.0044 <0 a= c
1.275 1.3 1.2875

The ite~ation is term inat ed because b - ·c =

0.0125 whi ch is sma ller than
is r ::::::: 1.28 75; it is kno wn tha t
the tolerance 0.02. The esti mat e of. the root
". . r.E [l..276,~-~J . 1.,__ ·.• -.~., :·· :•·· ·••:•·•li:H,,t-/ · :· ''·l~! ••rr .. ... ·•.11:,j~ J•r •• · ;;,., . . . ,' ► .. ' ·. •. • -• .. , ..... . ,. ,
· ···~1;1!
· ·· . · · · . · · ··
Only one function e\ra.l f 6 ~ ·is need e<!. for each iter atio n of the bise ctio n met hod
altho ugh th'. . . ,. 1 _ua.; ld
resu lt in und:;o?!i:ceearacr~mt thewill algorithm as given. The pro.duc t' f(b) f(c) cou
. e ,, erm th
become sma ll ·as e roo t is app roac hed . Bot h
of th
ese issues a.re a.ddres.sed in t.h fiO1 . ajgori.thm, which also has a che ck tha t
th e given _inter:i,a.1 is valid : e lowing
 ~
______________ uv1.er
v u _:_ ~
.:,0 1u~ 1'on
. '.
•-ol 1"t o11LU 1car ~ q u111.....tt()). ..-.?
~

!rri p ro ~c~ ~ tlon o..lgod di m ·

1 . I NPt..rf a b o od t ol or anco £
2 . Cal c u la~ ~ s fb • f (b)/l f (b) I 1

3 . If sf bx f ( a. ) > O t h. on OUTP UT ' Inval id int e r val"

and st o p .
4 . Calc ul a te c c ( a ~b )/ 2 an d fc ~f(c)
5 . I f b -c < l o r f c ss O go t o 8 • ·
6 . I f s fb ;fc< O t h en s et a ~c el s e set b ~c k
s fb~fc /l fc l
7 . Go to 4 .
8 . OUTPUT "Root -= c" and stop
8
. discou ra.ged
T h e use o f t he comm and go to is .often ' th (and even does not exist in om,
unti l or a do ~hil;
comp uter langua ges). An altern ative 1s to use e1 er a repea t._.
cons tr uct .
Conv ergen ce of the bisec tion meth od
Denot ing the origin al interv al by (ao,bo) and succe eding ones by
(an,b n), n = 1,2,. ,.
b1-a1 - ½(bo ·-ao)
b2 - a2 - ½(b1 - a{) · ¼(bo - a 0 )
b3 - a3 - ½(&2 - a2) = k(bo - ao)

so clearly

Now since Cn = (an+ bn)/2,

Ir - Cn / < bn - Cn
- ½(bn - an)
- ·2'!+1 (bo .- ao)

so Cn ➔ r as n ➔ oo. Thus the bisect ion meth . o

d .
conve rges. for any
initia l interyij·
conta ining a root (or an odd numb er of roots)
·· ·· ·-Furt her, Jr - ·. Cnl -< 2" (b o·-. ao ) · ~
t·if·~ E, .. lneq..u ality , holds·
and this

(bo - a 0 )
> f ;t

~ (n+l )log2 >

-~ n

Note tf1n.t t Ilie num b er o f ·iterat iow·;:) is .in d epen d cnt of the functi on .
 15
§ z.3 F.~ ep. PP.f Pt it~ rat ion .

ny iterations of the bisection me tho d

I Wo rke d Ex am ple 2.2 .2 Ho w ma
x - l - c = 0 to 4 dec ima l places
if the
a.re req uire d to find the solu tion of
initial interval (1, 1.5] is ~sed?

ller ) is req uire d to ens ure 4 dec ima

l place
A tole ran ce of£ ,= 5 x 10- s (or sma
accuracy.. Now ao =
l and b0 1.5 so =
.
I ,<
logco:ao)
n > -- -- -- -~ - 1
• I
. log 2

log ( / : ;,: , )
- log 2 . - l
~ 12. 29
ure 4 decimal place acc ura cy. I
At least 13 iter ati9 ns are needed to ens

Se lf As s essn;ient -~x erc fse s 2.2

ctio n
/2] , car ry out 3 iter atio ns of the bise
L Beginning wit h the inte rva l (0, r.
t of x = 0.8 + 0.2 sin z.
·method ·to find a.n est ima te of the roo tion of x = 2 sin x tha t
bise ctio n me tho d wit h E = 0.0 5 to find the solu
2. Use the
lies between· z = 1 ,and z = 2. ns of
a bou nd for the err or of the est ima te of the sol utio n afte r 5 iter atio
es a:;: : ....-2 and b = -1. 6 are use d.
_3. Giv e
· the bise ctio n me tho d if init ial valu to find
req uire d by the bise ctio n me tho d
4. Determine the num ber of iter&tions =
roo t of z - 2 sin = 0 tha. t liesz bet wee n z = l and z 2 for the tole ran ce
the
E =
1-0-tJ •
. •.·

2.3 Fix ed -po int ite rat ion -,

:} r = g(r ),
Su pp ~ t~a.t z =g(z) is~ rearran gement of /(z ). = 0. Then /(r l = 0 .-¢= s be fou nd
Uletime
and r is called the fun ctio n g. A fixed poi nt can a<>
fize d poi nt of_ n) -
i~r otio n, m¢ iod of ~s siv e su~stitutio
&

using the /izd. ~in t iteratl~n.(or si~ pk

· n = 0, I, ..• ,
gen-t it~ tfo n.. is. ·shown •in Fig ure
2.5.
g~e n·sottHf Tlii tial es~ ima te ·zo· ·of r~ A c"6n Vet
·· ··
However, the iter atio n· ma y -diverge,
a:s shown jn Fig ure 2.6. ·
Co nve rge nce oC:.fixecf po~nt ite rat
ion I
I
Xn+ l = g(x n)
l, and sinc e r = g(r ) ._ and
I

~ er. ~ ~~-o ~ Z
_ n+1 by en+ l = r - Zn+
•.. ., . , ~,e_n ~t~ -~-~ ·· J.t , . • ~ '.' ~"'1 ··.· ·•·ht., ~Y<l ·~ . .,, . -~•-~•1•• •Jfl ,•J•·.=1,•·-,riie: •[1,t _•i ~ ·. J: · ~,<!•~ . .. .•. ·: · •·J . , _..,
1
_
I
1
<' . t "· 1 !• ,

g(r) - g(znr
• • .'

-en+ l -
r and x · ·
- ·g'(~n)(r - ~n.) M-ea.n Val ue The ore m, {n bet wee n "
- g'({n)en.
•

.11
-
Ch'apter· 2

y == g(z )
g(xo) = x1

r Xo X

.. ;

FIGU RE 2.5. An exam ple of a conv ergen t fixed ·poin t iteta tion Xn+i = g_(xn),

y=x

I,
x2 xq r

FIGU RE 2.6 . An exam ple of a diver gent itera tion Xn+l = g(xn)•
 17
. § z.s Fi xe d ip oi nt ite ra tio n

Su pp.ose /g'( :r )/ S 1( for I~ - rl < ti. Th en

lcn+l I < /(f en/ if /e,./ < O
~ K(Kft!,, _11) if /cn -1
I<O

if leo/ < o.
➔ r as
1, /(" + /cof -t O as n ➔ oo,
1 so ''"+d ➔ 0 and therefore Xn +I
Now if K <
L
r + o)
ges to r for an y zo E (r - o,
,i.- +O O,
.-
Th us the _~xe<!-·po int ite rat ion .rn +l g(z n) =
con ver
all er, the va lue of K the
< a.JI z E (,. - 6, r -f 6). No te 'th ~t the sm will no t
lf }g '(:) i ~ _[< 1 for
o be sho wn t.h at the fixed po int ite rat ion
ce. It can als
fas ter the ~onverge.~ ·
converge i(f g'( r)/ > 1. •

eq ua tio n
Ex am pl e 2.3 .1 Tw o rea rra ng em en ts of the l
I W or ke d a.resin e- 1:. De ter mi ne if the
= fixed I

e-~ = sin x are x =-

Jog (sin x) an d x
t po sit ive solution r ~ 0.6
for the se l
ge to the firs i
po int ite rat ion wiJJ con ver (use xo = 0.6).
i

ng em en ts. If the .ite rat ion does converge, ca/cu/ate :r3 j

i
rea rra
-c ot x giv ing g'( r) ~
If g(:z;)
=
= -Jo g( sin x) the
fg'
n
(r) I
g'{
is
x)=
cle arl
-c os x/ sin x =
y lar ge r tha n 1 the fixed po
int -it era tio n d
;l

- g'(.0.6) -1 .46 . Sin ce

, ·
Xn +l = g(x n) will no t copverge.
so g'( r) ~ -0 .66 . As jg' (x) .•
I is
If g{ z) = a.r esi n ti:..z .th en g'( z)= -e -:
V l-. e -b .
.. po int ite rat ion
y Jes s tha n I in a ne igh bo urh ~o d of the roo t the fixed
ob vio usl
. wilF'con'verge.
g the ite ra. tio n Xn ~I = a.resin e-z~ wi th :ro =
0.6 gives
·· E~ plo yin
6
.. X1 - arc sin ~--~-
- 0.580942
a.resin e-0.580942
Z2 -
..11 - 0.593621
:C3 - arc sin e-0 .59 362 7
- 0.5 85 14 5.
1, vaJu~
gen ce is rat he r slo w (as ex pe cte d fro m the lar ge
No te tha t the con ver · ,
of /g' (r) l), .I

es 2.3 •k
Se lf As se ss me nt Ex er cis ' ..,.,.,. . " . ' •' •" ', · " .. J
. ' ' '' .. , ' :•,. ,,.,..
I • •, , ,.

. 1' s ;· . g~ to the 'fir st po sit ive ro~

t ) ~.
2 =
si'ri Zn ' wil
· ( h~w tt)a t the he2r~t ion Xn+ ing :to = l.9 , fio d x 3 •
1 l con ve~
. '.'§
.O. Us , :1}
· Tr ~ .l. of.-~ - srn xof= the ua tio n e- z - ..
, .
.2 . wo rea rra .ng em eot s
. ~ 2c os x are x =
. -ln (2 cosx)_ an d ;:.
Ar e eit he ~f th ng a ..t'
z = ~r~ co s(e -z/ 2).
ese SUJt~• b!e to_fin d the roo t r::::::: 1.5 usi
fixed po int ite ra. tio n?•
•
 , ,;
~
.
•.; •
,,
- . : . x-~ ~-
~.
5 o l~ t1• o n·.o f N o n li n e a r E
(l\ul~
_ · ~
:;. ~·
•~··
.
;i f o o v e rg e x ic ~ ·
cte O ro ,c lr n a .t io n ro o t r . lf
_:,
J!I. z:21 is a. se q ~
e n c e o f a p p s to a _. Xn ~ r ).
up o5e :t o , z 1 , •••
• c o n v ...~,;:
rnent,
' -+P0 0 we sa.Y th e se q u e n c e , ,s · "'
"•' . • ·r ·
l\ p o rt a .n t. lf
•· )le ra te o f co ,nvergen e is IA••
c
.
,
.• .
1it n
l.c - z"\~I == J~oo jen\P
le n + d - K
~
} n- tO O lr -- Xn -
. .' ::
1~}'· r p o si ti s a y th a t ~ n c ·~~ w · i .
t
n v e rg .f. I( th C -~ e r o1 conve""· ~cri . .
r
,~ ·· v e c o n st a n o
:." _. io r ts K af npd : ~ : : h e sma\\e~ e { a s te r th e c •~
...:-.· ·- P· T h e \a rg e r th e value o dthte v : ~ : ; onvergen~
~~· ._.-. lf p == d K < 1 th se q u e n c e 1·s sa..1 o g e linearly
, a ~ d if p =
>-:'.. 1 a n . u a d ro ti c . e . 2 th\
c o n v e rg e n c e
},r. • is q .
. s h o w n th a t
e fixed P in t it e ra ti o n X n + l == g (x n ) .1 t w a s
~ o
ff ;·: .-· fo r1·th es b e tw e e n d r Thus
en+ 1 '(
g Cn ) en w h
et\
=
} an
~-~
Cn Xn
I .
. \e n + 1 \ == Um
h \g '( c n )\ == \g '( r) \
n--+mOO \e \ n- -+ oo
n
•

. .
so s1mp le. it e ra ti o n c o n v e r ges li n e a rl y 'if O < lg' (r ) I < 1 . ( lf g
'( ) O th e o rd e r
c o n v e rg e n c e ·u b e 2 o r g re a r - 0
1

w1 te r. ) •

The . . th d
b is e c ti o n m O
.
'o r m o re p it s e rr o r b o u . )
J( == ½·
e ' re c 1 se \y n d c o n v e rg. e s li n e a rl y witb
T e rr n 1. n a t'io o
n f th e it e r a ti o n
W e w o u ld li • ·.
ke to st t' w .
\r - :&n l -< E (O r so mo ep pthreese1tt\ebrad1otnO\ haennc ex : 1s0 -ns u ffic·1·' e n t\ y d o s e to r , th a t . hen ·
is to s to p w < e er e c ri te ri o n l.S w
h e n \!(x b t th is d · th a t is u s e •
se e n fr o m th nd )~ o e s n d so m e tt m
e e a rh e r ia - l, . u A n o th e r c ri teo t e n s u re th a t \r - \ < ~
a.s c a n 111. •
jX n +1 - X n < · g;rarns. ri o n th a t is :r n -
I - €. T h 15 a.. 5 0 d o e s n o t always e
. 1 . o ft e n u s e d £
n s u re t h a.t . \ is to s to p w
F o r si m p le it r - X
\ < ~ het
e ra ti o n :
n _ -·
·,

g '( r) .•
' .
_ g'(r) (: tn + l
- :Z:n)
s o if g '( r) is
close to 1 th
·e v e r, g '( r ) e n Ir - X n +
m a y be· a p p l \ w il l b e
ro x im a te d b y K I m u c h la rg
te rm in a te d
w h e n jK '( x
n + l ~_.xn)/(1
= (x n'+ l - X n )/ ' e r th q .n \x n + l - x~\-
(x n - X n -l ) n~~o'
T h e s e p o in
ts a re il lu s
-:- K ') I < L a n d th e 1• te t\ '
tr a ~ e d b y th ra.
re s u lt s s h o w e it e ra ti o n
n in. T a b le
T h e slow c o
n v e rg e n c e is
1. T h e it e
ra te s a re c
Xn+l
0.4 + 0.6x~ 5
· w
= hl" ·.
o n v e rg in g slow h ic h
very,mµ.ch _sD?, to b e e x p e c
te d since g '( ly t o t h e r g a v e t \
·a p p ro a c h e s _a Uer th a n th
th is v a lu e th ~. e rr o r ~n ~ n •· N o te .t h
l) 0 .9 . T h e v a lu
e o f
= o o t r ~ '¢
e e r r o r e s ti m at Z n - :r" ...
No m a tt e r w a te (l a s t c o lu K ' -is _tending to g '{ l) i 11
h a t c ri te ri o n m n )- a p p ro a , ~d ~ -
c h e s th e a c
.i o u s s h o u ld
ue limiLed. in cais..sue sed to te r m in a te a n ·i te r a ti o n tu a l er t 0 ~

,
tc . o f p ro g ra m , th e to ta l n u m b
e r r o r s lo w e r o f itet ,
I d iv e rg e n c e J fli~
to o s m a U a
to lera.
,· 12 _4 · ·-Ne wt on ~• 'm eth od ·

itor-.t ion X n + i ::= 0.4 + 0 .6x ~·5 •

TA BL ~ ,. I. Re sul ts o( tho

K'
n ,s:" Er ror X-n - a::,. _ l I<' l _ K' ,{~n - -Zn_ i)

0 1.100000
1 1.09.2214 - 0.092214 - 0.0 077 86
0.9 422 56 - 0 . 119716
2 1.0 848 77 -0 .0~-4877 - 0.0 073 37
0.9 390 00 - 0 .106046
s 1.0 779 88 -0. 07 79 88 - 0.0 068 89
-0. 04 14 06 - 0 .00 408 7 0 .92 122 0 - 0 .04 779 3
10 1.0 414 06
0.9 080 72
-o; 0l6 46 7 - 0 .00 164 6 - 0 :016255
20 1.015467
0·0 505 0.9 029 08 - 0 .00 562 8
-SO 1.0 055 82 - 0 .005582 - o.0
02 15 0.9 010 26 . -0. 00 19 58
40 1.0 019 46 -0. 00 19 46 -0. 00
00 76 0.9 003 59 -0. 00 06 82
50 l.0 006 81 -0. '00 06 81 -0. 00
00 26 0.9 001 25 -0. 00 02 38
60 1.000238 -0. 00 02 38 -0. 00 i _=
'11 ~ , \I

2.4 Ne wt on 's m eth od 1,

I

ate x 1 of the roo t of / (x) =

0 is cal cu l~t ed
In Ne wt on s me tho d,
1
a.n im r
p_ ov ed est
din g
im
the po int wh ere the tan ge nt to f(x ) . at x
xo =
e ~o by fin
fro m a.n ini tia l estima.t
).
cu ts the ,;-a.,tjs...(s ~ F"sgure 2.7

Ta ng ent ,
slope = /'(~o)

v x0 X

··
.t111..Jt,, ·,,,. ·· ·. •,, •'"'·11!•1;,••tr -1;:•, -i· '" . •_:. ·
.._.,,, ., ~.,. 1 . ,,·.\ ·;_:···· •fli'• ',1 .,..,,, 10• .•1• • · .
· · .'• I· _•,~\11 : ·. ,1'

wt on '~ me tho d the fun cti on is ap pro xim ate d by its tan ge nt.
FIG UR E .2. 7. In · ~e

Eq ~a t~~ twb _e xp r~ lon s. fo~ ,th

e ·sl~pe ~f the ta. n~ e~t ~ves ..
· · · ...,'. ·"·· · ·. · ; '. ·-J(zo) ~ 0 · f'(:& ) '
zo - :t1 . 0 ~
 20
- -- - - - - - - --
· C h a pter 2
---
Solution <?f Nonli11ea,, E
- . - - - -~ q ~~~
-~
'.:::l
and.solving this eq uation for :r 1 we obtain
J (xo)
z 1 = xo - j'(xo). ~
Jf
This procedure is repeated to find x:2 from x1 •· • · 1
60 N~wton' 5 method is
/ (%n) n -~' l 1 • ••
Xn+ l = Xn - / '(x" ) / :
--
I \\l'orked Example 2 .4 .1 Ca.rry o ut two iterations of Newton is lllet
=
with xo 1.2 to fin d an estimate. of the r~ot of x - 1 e- z. hO( U =
[Ii
Le t J(x) =x - 1 - e- s:. Then J'(x) = 1 + exp-x, and
f(xo)
x1 - xo - f'(xo)
ti
/(1.2) n
- 1.2 - /' (1.2) iI
-0.1011942
2
- 1. :-- 1.3011942
- 1.2777703
. f (:ti)
X:2 - X1 - j'(zi)

1 .2777703 _ f (1.2777703)
- I f'(l.2777703)
- 1.2777703 - -0.0008877
1.2786579
- 1.2784645
T hus · r ~ 1.278465 I '
Rate of convergence
Taylor 1s theorem gives

/(r) = /(xn) +(r - Xn)/'(xn) + (r - ;n) 2f"(c,,) 2

fo r some en between r a!}.d Xn• But J(r) = 0, and divi9ing by /'(xn) gives
0 = f (xn) + (r - x ) + (r - Xn)2 /"(en)
f'(xn) n 2/'(zn)
_ ·7 x-- ~-x- 1""'+ rr - x ) +· ·--{r.----X-n-}~.f~~-{;cn) ·
+·

. ' n n J . \' n . 2f'(xn) ·

Si m pli.fying and rearranging we ·ge t
-J"(cn)] · 2
r- Xn+l = .[ 2 f'(xn) . (r - . Xn)
so tha.t • ' I :, • I• t

llrn Ir - xrJ \·= ·. u· · 1_ ,,,(en) I - ·1,'-1" (r) 1·~ K .:,"-' . .

• · . n :-+oo (r - x,i) 2 n-+~ 2/'(xn) - · 2/'(r-) . ~ · · ,
K
f· , .
Therefore Newton s method converges quadratically to: a simple root.
lti~
1
1

(For a tnU
; roo t J' (rj == 0 and .the convergence is linear.) .,.
/
 If so) s:1 ' s-, , .. . an d01Jo to.-,
r - « ., ➔ a ,\,. K( r - rr," ),
2
K (r - l' n-t-1) ~ ~ !K (r - :,;" )]
2
~ { /( fJ(( ,. - It n - t)] 2 ) {/(( r

~ (K (r - :: o)]l" 'i • .
hen ce z" ➔ r . Thu s New ton 's
If K (r - : 0 ) < 1 t hen a.s n ➔ oo K( r - x"+J ) -+ 0 a nd
meth od converges If ~o is ~ osen ao th at

Ir - xol < Ic = l;,:((;;1 ,

, . a.n accu rate initi al estim a te i.s
t ha.t is if :o is sufficiently close to r . If I( is la.rge
od coul d be used t o gene rate t he
need ed t o ensure conv erge nce. The bisec tion meth
initial • tima.te. ·

Stop ping test

Now
J (tt .. ) = /(,;n ) - /(r) (since /(r) = 0)
·- '(zn - r)/'( c_n) (Me an Valu e Theo rem) t

wher e <:,i lies betw een Xn a.nd r . Ther efor e

/(zn )
r - ~n == -'--'-----
/'(c,. .)
~

prov ided Zn is clooe to r a.nd f'(r) #- 0. But , rearr angi ng the form ula for New ton' s
meth od,
'' f(xn )
- f'(xn )
- .:tn+ l - Xn

~ r - :Z:n
- Xn+ l -

l - Xn I < E, whic h shou ld e ns u 1·c

X n.

New ton s meth od ~ there fore term inate d whe n l.:rn+

1

that {r..:. %nl $£fo r a simp le -~oot. Of cour se, Zn+ l

will have an even sma ller e rro r .

New
I
ton's meth od algo rithm
of
1 . IIPU T xO, tole ranc e ~S, . maximum .nwn ber
iter atio ns MAX
2. For i•1 t~ MAX do,_3_. to l·
3. x1cxO~f( ~O) /fda sh xO)
4. If abs x1-x Ot< ~S OUTPUT "Soluti"on·-1s -:tl" a
-..._. "1'~ et()t' ~ LO.ttt" t / · .
~

stop .
.1
6••• . xO•x 1 • · ' · - • ·• • -t• -'ttJ~•· , .. •. ••u · ,·· · · 1·
1 · •} : ' ,: ,_. .. , ,t • "• J / •\,
..
6 . OUTPµT ''Method hasu ' t :c:;.onver ged - curr ent
.· es~i !'l~t e is x1"; stop ·

.when'Thi• ~til: )D . rbow• • ... ~~o d out prer i~,- .

~~ t.he error ~ .t:n is not neces sarily smal l
.
,c~n) small
IS . . . • . . ••, .
I.'
C hnp t er 2 So lutl0n of .N~o~llncar Eq uat tli, ,
I 2i
----:.:
3
Fi nd th e solution of x = 2 to a tolerao ce of
I \,\for k ed Exnmplc 2.4 . 2 . 2
10- • using Newton 's mo tl1 od w1tl1 xo -= 1. .
"'e" gqof\a \:an dere f e.rror-
Let /( %) 3
x -
,
2, rrt" ng J'( x) =
i . 3x2' go
f ex•) -z f (xn
c
+ (x•
/ (2:0) .... ~~ )
x i == xo - f'( z o)
lca)A ~onver9,n ti
/ (1.2)
- 1.2 - /'(1.2)
menuJu ~

- 0.272
- 1. 2 - 4.32
_ 1.2629630

.
Since Ix 1 - xo -
I _ o·0629630 > 10- 4 we calculate
.
the -n ext iterate:

J(x1)
X2 - X1 - f'(xi)
~ /(1.2629630)
- 1.2029630 - /'(1.2629630)
0.0145212 ,,
629630
l.'.2 - 4.7852263 ·
= 1.2599284 ;~

ft Now !x 2 - x 11 = 0.0030346 > 10-4 so vie again calculate the next iterate:
.
i X3 - X2 -
f(x2)
f'(x_2)

L -
. , /(1.2599284)
1.2599284 - /'{1.2599284)
1.2599284 _ 0.0000349 ·
- 4.7622585
- 1.2599211

Now fx3 - x2/ = 0.0000073 < 10-4 so we stop and accept· the approximation
r ~ 1.2599211 .
=
We know the·solution .is ~ 1.25~92104989 .. , so the error in our approxi-
mation is about -5 x 10-s which is much SJ;Jlaller than the given tolerance.
This error is essentially due to the number of digits used in the calculation;
using more digits-shows thit .the error in -~s .is appr~ma.tely 4~3 x .10~-~.t
The error in x 2 is, to the accuracy of the calculated results, equal to x 3 - x2
a.s predicted. I

Self Assessment Exercises 2 .4

, • . • . •. I ,.)

1. Using ;; 0·:= ·1.s, carry ~ut t~o it~rations of Newton•~ me't_

hod io:nnd an estimate.:
- of the root of x :_ 2 sin x. . .
2. Calc.u late the negative solution of e:z:/'l = 2 - x 2 using Newton ~s. method wi th
Xo = ...:..1 .2 and a toled~. nce of 10- 4 . . .. • . .
 2. 5 S ec an t m et
hod
d
th e so lu tio n J( x) = 0 is fo un of
of e
im pr ov ed es ~i m at
e th e ch or d cu ts th
%1
nt m et ho d an e po in t w he re
In th e se ca .ro an d x1 by de
te rm in in g th lu tio n .
tw o es tim at es z do no t ha ve to br ac ke t th e Bo
fr om
2. 8) . Not:e, th at zo an d 1
z-&Xis (see F ig ure

d.
nc ti on is p
a_ pr ox im a. te d by a ch or
th e fu
FI G U RE 2. 8. 1n
th e se b. ri t m et ho d .
. .

e ch or d gi ve s
tw o ex pr ~i on s_ f<;>r_th e sl op e of th
Eq ua .ti ng - /( z i)
l( zo ) - /(~1) _ o - ,
Z2 - Z1
Zo - Z1

e ob ta in
an d solving for z2 w
·. · /( z1 )( z1 - zo)
) •
Z2 ~, %1 - .( zo
/ (z1 ) - ./
..
an d Z2 an d so on ,
is ca le ul a. te d in th e aa m_e wa.y fr om :CJ f

T he ~ext
& pp r6 ~ at io n- ~3
et ho d e& :n be w rit te n as .. ·
·
so th at the secant m ----·-nznITzn'- Z n -1) r
-~ ·: - l' . - -- · - n 1, 2, ~ .• =
=
-. . .
-- - - - . · ·--- . ) /(; ,.· ..•
Zn ~- /( o( ,n -1
Z n+ l , Zn -
· . ·

d. .
C on ve rg en ce
.
t,:~ n v ~ g e fo r so me choices of ~o an
ma,y.. no e ro ot
r ao~e., proble,ID$, .th ~ se ca nt m et ho d an d ·xi ar e su fficiently do se to th
,;.,i . Fo ua ra nt ee d if
erge.nee js'•g
Zo
z1 ,"•Howevert conv
~ 62. C on se qu en tl y
• • •

r. 2 1.
~ { l+ V S )/
.m et ho d is p th e -b is ec tio n m et
ho d
ge n~ of th e se ca nt
#

or de r of co nv er uc h fa st er th an ·
T he converge m ew km ~s m et ho d .
th -~ n. .b e expectecl to
_e ..~ n t ~e t~ od .t1 on .. bu t no t qu it e as fa .s t as
_-N
or-•fixed po m t.1 te ra