Newton's method, as the most fundamental root-finding algorithm, usually appears no later than Chapter 2 in most numerical analysis textbooks. It uses the first two terms of the Taylor series of a function $f(x)$ in the vicinity of a suspected root to find successively better approximations to the root, using the formula $$ x^{(k+1)} = x^{(k)} - \frac{f(x^{(k)})}{f'(x^{(k)})}. $$
Let's consider $f(x) = x^3-3x^2+2$, which has several roots, as we see in the next plot.
LW = 'linewidth'; lw = 2; MS = 'MarkerSize'; ms = 18; dom = [-3 3]; f = chebfun('x.^3-3*x.^2+2', dom); plot(f, LW, lw), hold on plot(dom, [0 0], 'k'), hold off
Here are the roots.
roots(f)
ans = -0.732050807568878 1.000000000000003 2.732050807568877
If we try to locate the leftmost root by Newton's method, we need to pick an initial guess, for example $-3$.
fprime = diff(f); d = norm(f,inf); tol = 1e-8; xold = -2; x = []; i = 0; plot(f, LW, lw), xlim([-2.5 0]), hold on plot(dom, [0 0], 'k') while(d > tol) x = [x xold]; xnew = xold - f(xold)/fprime(xold); d = abs(xnew - xold); plot(xold, f(xold), 'ok') strx = ['x_{' num2str(i) '}']; text(xold - 0.05, 1.2, strx,'fontsize',12) plot(xold, 0, '.k', MS, ms) plot([xold xold], [0 f(xold)], '--k', LW, lw) plot([xold xnew], [f(xold) 0], '-.k', LW, lw) xold = xnew; i = i+1; end hold off root1 = xnew
root1 = -0.732050807568876
In the above plot, the solid black dots are the successive approximations of the root, while the circles are their projections on the curve, from which the Newton's method locates the next approximation along the tangent (black dash-dot lines). The following table tells us with no surprise that Newton's method is quadratically convergent.
n = size(x,2); res = abs(x - xnew); LogRes = log(res); disp('iterations Logarithm of the step size') for i = 1:n fprintf('%5d %25.8f\n', i, LogRes(i)) end
iterations Logarithm of the step size 1 0.23740079 2 -0.65787813 3 -1.98646163 4 -4.28606060 5 -8.73432460 6 -17.61270705 7 -35.12736266
You may expect that the same order of convergence to appear when we approximate the middle root in this example.
d = norm(f,inf); xold = 0.5; x = []; while(d > tol) x = [x xold]; xnew = xold - f(xold)/fprime(xold); d = abs(xnew - xold); xold = xnew; end hold off root2 = xnew n = size(x,2); res = abs(x - xnew); LogRes = log(res); disp('iterations Logarithm of the step size') for i = 1:n fprintf('%5d %25.8f\n', i, LogRes(i)) end
root2 = 1.000000000000002 iterations Logarithm of the step size 1 -0.69314718 2 -2.19722458 3 -6.98471632 4 -21.35961353
But now, this time we are evidently achieving cubic convergence! Is there something wrong? No, for it is to be expected if you notice that $f''(1) = 0$ in this example.