Unit 2.2 Convergence of Newton’s Method
Using Taylor’s Theorem to prove the convergence of Newton’s Method involves a three-step proof. Step 1. Using the Taylor Series expansion of about gives
for some between and .
Here we have placed an
where was in the Taylor’s Series formula, an where was, and taken
.
Step 2. We chose to do an expansion of since . Using this and dividing by
Step 3. Rearranging the terms and using the definition of from the method gives
so that
For close to , and thus close to , we get the Error Formula for Newton’s Method:
gives
Convergence Order
Newton’s Method converges quadratically, meaning that the error at step is proportional to the error at squared.
So once the error at step is small, the errors will be going down very, very fast. For example, if the error at step is
then the error at step will be proportional to , and at step it will be proportional to :
and so on.
The catch is we don’t always get this.
Newton’s method converges quadratically provided
1. for near
1. is twice differentiable near
If ever equals zero, the method will fail due to a division by zero.
If is ever near zero, the method will send the next iterate far away.
Interval of Convergence for Newton’s Method
Given the error formula for Newton’s Method, we can write
Multiply both sides by to get
For these quantities to decrease, we need , i.e.,
If is very large, then we need to be correspondingly closer to .
Note: usually we can only estimate , and tend not to have formal estimates of what choices of are “close enough” to .
Example
Solve for using Newton iterations in Julia.
In[]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
In [ ]:
f(x)=(1-x)-exp(x) f¡ä(x) = -1 – exp(x)
x = 1 # Guess x_0 = 1
x = x – f(x)./f¡ä(x)
x = x – f(x)./f¡ä(x)
x = x – f(x)./f¡ä(x)
x = x – f(x)./f¡ä(x)
x = x – f(x)./f¡ä(x)
x = x – f(x)./f¡ä(x)
# this is the text \prime TAB, may not be the best idea. . .
We see that the number of leading zeros in the error roughly doubles per iteration for this example, to machine precision. Rather than repeat this over and over by hand, we can write a function to do the iteration for us.
For Newton’s method, we will use a recursive form (we could also choose to use a while loop):
In [ ]:
function myNewton(f,f¡ä,x,tol) # takes the function, its derivative, an initial gues s, and a tolerance
println(“x=”, x, ” f(x)=”, f(x), ” f¡ä(x)=”, f¡ä(x)) # output the intermediate it erates for illustration
if abs(f(x)) < tol return x
elseif abs(f¡ä(x)) > tol #its lazy, but use the same tol to test for zero x = x – f(x)./f¡ä(x) # get the new Newton iterate myNewton(f,f¡ä,x,tol) # do the recursion
else
throw(DivideError()) end
end
In [ ]:
myNewton(f,f¡ä,1.,1e-8)
Practice Exercise
Use the above Julia function myNewton to find the roots of
starting with some different initial values. Use “Interrupt” in the “Kernel” menu above when you need to.
In[]: f(x)=2.*x-3. f¡ä(x) = 2.
myNewton(f,f¡ä,2,1e-12)
In [ ]:
In[]:
In[]:
f(x) = sin(x)
f¡ä(x) = cos(x)
myNewton(f,f¡ä,2,1e-12)
f(x)=x^2
f¡ä(x) = 2*x myNewton(f,f¡ä,2,1e-12)
f(x)=x^2+1
f¡ä(x) = 2*x myNewton(f,f¡ä,2,1e-12)