Rate of Convergence

Definition:
If there exists a p > 0 and c such that |e[n+1]|/|e[n]|^p
approaches c as n approaches infinity, then the
rate of convergence of the sequence {x[n]}, n = 1,. . . ,infinity,
is p.
If p = 1, the sequence converges linearly.
If p = 2, the sequence converges quadratically.

Exercise 3

Exercise 4

Newton's method converges quadratically because

e[n+1] is approximately c e[n]^2

To get a feel for whether or not this is a fast rate of convergence, let's look at a simplified case. Suppose c is approximately 1 and e[0] = 10^(-1). Then

e[1] @ e[0]^2 = 10^(-2)
e[2] @ e[1]^2 = 10^(-4)
e[3] @ e[2]^2 = 10^(-8)
e[4] @ e[3]^2 = 10^(-16)

Wonderful! You can see that the error diminishes very quickly.

Up to Error Analysis