Introduction Notes Theory HOWTO Examples
Engineering Error Questions Matlab Maple
Given that we are using Newton's method to approximate a root of the function f(x).
Suppose we have an approximation of the root xn which has an error of (r - xn). What is the error of the next approximation xn + 1 found after one iteration of Newton's method?
Suppose r is the actual root of f(x). Then from the Taylor series, we have that:
where ξ ∈ [r, xn]. Note, however, that f(r) = 0, so if we set the left-hand side to zero and divide both sides by f(1)(xn), we get:
We can bring the first two terms to the left-hand side and multiple each side by -1. For the next step, I will group two of the terms on the terms on the left-hand side:
Note that the object in the parentheses on the left-hand side is, by definition, xn + 1 (after all, xn + 1 = xn - f(xn)/f(1)(xn) ), and thus we have:
But the left hand side is the error of xn + 1, and therefore we see that error is reduced by a scalar multiple of the square of the previous error.
To demonstrate this, let us find the root of f(x) = ex - 2 starting with x0 = 1. We note that the 1st and 2nd derivatives of f(x) are equal, so we will approximate ½ f(2)(ξ)/f(1)(xn) by ½. Table 1 shows the Newton iterates, their absolute errors, and the approximation of the error based on the square previous error.
Table 1. Newton iterates in finding a root of f(x) = ex - 2.
| n | xn | errn = ln(2) - xn | ½ errn - 12 |
|---|---|---|---|
| 0 | 1.0 | -3.069 ⋅ 10-1 | N/A |
| 1 | 0.735758882342885 | -4.261 ⋅ 10-2 | -4.708 ⋅ 10-2 |
| 2 | 0.694042299918915 | -8.951 ⋅ 10-4 | -9.079 ⋅ 10-4 |
| 3 | 0.693147581059771 | -4.005 ⋅ 10-7 | -4.006 ⋅ 10-7 |
| 4 | 0.693147180560025 | -8.016 ⋅ 10-14 | -8.020 ⋅ 10-14 |
Note that the error at the nth step is very closely approximated by the error of the (n - 1)th step. Now, in reality, we do not know what the actual error is (otherwise, we wouldn't be using Newton's method, would we?) but this reassures us that, under reasonable conditions, Newton's method will converge very quickly.
Failure of Newton's Method
The above formula suggests that there are three situations where Newton's method may not converge quickly:
- Our approximation is far away from the actual root,
- The 2nd derivative is very large, or
- The derivative at xn is close to zero.
Copyright ©2005 by Douglas Wilhelm Harder. All rights reserved.
