Newton s method control Patrick Dale McCray Ph D 29 March 2011 Introduction The typical way of controling an iterative scheme is to compare successive values of the quantity being computed with the preceding value In order to achieve high accuracy in computed quantities this notebook introduces a Module based on the idea of having Mathematica perform the iteration with exact values and inspecting the resulting exact values numerically with the N function Exact computation Decimal numbers with a few digits are stored with limited machine precision Here we compute a value z using approximate machine numbers In 130 Out 130 z 12 4567 37 8 z N z N z 100 0 329542 0 329542 0 329542 On the other hand numbers calculated with whole numbers are stored exactly such as w In 131 Out 131 w 124 567 10 000 378 10 w N w N w 100 124 567 0 329542 378 000 0 3295423280423280423280423280423280423280423280423280423280423280423280423280 423280423280423280423280 How do these two same values compare In 132 Out 132 z w 5 55112 10 17 The correct exact value of the computation namely 124567 378000 is rational hence has an eventually periodic decimal expansion that never terminates unlike the machine version 0 329542 which is finite and incorrect Sometimes extra precision may be required The default value of the maximum extra precision is 50 In 133 Out 133 MaxExtraPrecision 50 We will have to increase this in the following discussion 2 Newtons method control nb Code for Newton s method Suppose we wish to solve f x 0 for x The basic Newton step may be computed as follows In 134 NewtonStep x x f x D f t t t x For example evaluate the Newton step at x 3 would yield In 135 Out 135 NewtonStep 3 3 f 3 f 3 Using the function NewtonStep we may write a module for iterating until a desired level of accuracy is obtained The following Module is intended to iterate until the iterates agree to within 40 decimal places and takes one argument the initial value for the interation namely x0 In 136 NewtonIteration xinit Module k test x0 change local variables k 0 test True x0 xinit While test is true repeat the following xk NewtonStep x0 k k 1 change Abs xk x0 test change 1 10 100 Print x k N xk 45 N change 9 x0 xk Print Stop Example Let us solve the following equation In 137 x 3 Sin x x Out 137 3 Sin x Newtons method control nb In 138 Plot x 3 Sin x x 0 Pi 1 0 0 8 0 6 Out 138 0 4 0 2 0 5 1 0 1 5 2 0 2 5 3 0 First we code the Newton step In 139 g x 3 Sin x x In 140 NewtonStep x x g x g x In 141 NewtonStep x Out 141 x x 3 Sin x 1 3 Cos x Now we invoke our module with an initial value of 2 first checking the default value of the maximum extra precision In 142 Out 142 In 143 MaxExtraPrecision 50 NewtonIteration 2 3 4 Newtons method control nb x1 2 32373206111338325354188208345366581392706335 0 323732061 x2 2 27959482163992639068772151841669254197757185 0 0441372395 x3 2 27886286684763997073119345250115932298600016 0 000731954792 x4 2 27886266007584482041679741117310186574317502 2 06771795 10 7 x5 2 27886266007582831269995110466710382941208700 1 65077168 10 14 x6 2 27886266007582831269995110456188862881827474 1 05215201 10 28 N meprec Internal precision limit MaxExtraPrecision 50 reached while evaluating 2 2 3 Sin 2 1 3 Cos 2 1 1 1 3 1 1 3 2 2 3 1 1 3 1 3 1 1 3 Sin 1 1 3 Cos 2 4 Times 3 3 Sin 1 N meprec Internal precision limit MaxExtraPrecision 50 reached while evaluating 1 1 3 Cos 1 x7 2 27886266007582831269995110456188862881827474 4 3 10 57 N meprec Internal precision limit MaxExtraPrecision 50 reached while evaluating 2 2 3 Sin 2 1 3 Cos 2 1 1 1 3 1 1 4 2 2 3 1 1 3 1 4 1 1 1 3 Cos 2 5 Times 3 3 Sin 1 General stop Further output of N meprec will be suppressed during this calculation x8 2 27886266007582831269995110456188862881827474 0 10 59 Stop Since the internal precision limit has been exceeded we increase it and try again In 144 Out 144 In 145 MaxExtraPrecision 200 200 NewtonIteration 2 x1 2 32373206111338325354188208345366581392706335 0 323732061 x2 2 27959482163992639068772151841669254197757185 0 0441372395 x3 2 27886286684763997073119345250115932298600016 0 000731954792 x4 2 27886266007584482041679741117310186574317502 2 06771795 10 7 x5 2 27886266007582831269995110466710382941208700 1 65077168 10 14 x6 2 27886266007582831269995110456188862881827474 1 05215201 10 28 x7 2 27886266007582831269995110456188862881827474 4 27426496 10 57 x8 2 27886266007582831269995110456188862881827474 7 05386830 10 114 Stop Now we reset the internal precision limit back to its original default value 3 Sin 1 Newtons method control nb In 146 Out 146 5 MaxExtraPrecision 50 50 Investigating the final iterate Solution achieved for iterates agreeing to withing 100 places In 147 Out 147 N xk 100 2 27886266007582831269995110456188862881827474073977651652558552924834446470183 9186256781340580146512 Mathematica high precision calculation In 148 Out 148 Xk x FindRoot g x 0 x 2 2 WorkingPrecision 250 2 27886266007582831269995110456188862881827474073977651652558552924834446470183 918625678134058014651238961301225219230809486894388499883713738384535069911700 350133544421600937321857149974060257640464532197063595607329840058254563749323 3865175964304189 The difference In 149 Out 149 xk Xk 1 9211406436879307525509 10 227 As we may see since the computations are done EXACTLY the corresponding expressions for x 1 x2 x3 get rather LARGE In 150 Out 150 In 151 Out 151 x1 NewtonStep 2 2 2 3 Sin 2 1 3 Cos 2 x2 NewtonStep x1 2 2 3 Sin 2 1 3 Cos 2 2 2 3 Sin 2 1 3 Cos 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 6 Newtons method control nb In 152 Out 152 x3 NewtonStep x2 2 2 3 Sin 2 1 3 Cos 2 2 2 1 3 Cos 2 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 1 3 Cos 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 3 Sin 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 3 Sin 2 1 3 Cos 2 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 3 Sin 2 1 3 Cos 2 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2 2 3 Sin 2 1 3 Cos 2
View Full Document
Unlocking...