5.6. The Secant Method

The secant method is yet another iterative technique for solving nonlinear equations; it closely mimics Newton’s method, but relaxes the requirement that an analytic expression for the derivative \(f'(x)\) must be provided. It operates as follows:

• We bootstrap the iteration not only with one initial guess \((x_0)\), but also with a second improved approximation \(x_1\).

• At the \(k\)-th step of the iteration, we first approximate

  \[f'(x_k)\approx\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}\]

  Remember that since

  \[f'(x_k)=\lim_{y\rightarrow x_k}\frac{f(x_k)-f(y)}{x_k-y}\]

  as the iterates \(x_{k-1}\), \(x_k\) get closer to one another (while they both approach the solution) this approximation becomes more and more accurate. We then replace this particular approximation for \(f'(x_k)\) in Newton’s method \(x_{k+1}=x_k-f(x_k)/f'(x_k)\) to obtain:

  \[x_{k+1}=x_k-\frac{f(x_k)}{\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}}\]

Geometrically, Newton’s method approximates \(f(x)\) at each step by the tangent line to the graph of \(f(x)\), while the method we just described approximates \(f\) by the secant line as illustrated below:

We can show that, once we are “close enough” to the solution, the error \(e_k\) for the secant method satisfies

\[|e_{k+1}|\leq c|e_k|^d,\enspace\enspace\mbox{where $d=\frac{1+\sqrt{5}}{2}\approx 1.6$}\]

Thus, the secant method provides superlinear convergence. In practice, it may need a few more iterations (about \(50\%\) more?) than Newton’s method, but we need to weigh in the fact that each iteration is likely cheaper, since no derivatives of \(f\) need to be evaluated.

Order of convergence: Let the exact solution be \(a\), i.e., \(f(a)=0\). Define \(e_k=x_k-a\) and \(f_k=f(x_k)\). Then,

\[\begin{split}e_{k+1}=x_{k+1}-a &=& \enspace x_k-\frac{x_k-x_{k-1}}{f_k-f_{k-1}}f_k-a \\ &=& \enspace \frac{(x_{k-1}-a)f_k-(x_k-a)f_{k-1}}{f_k-f_{k-1}} \\ &=& \enspace \frac{e_{k-1}f_k-e_kf_{k-1}}{f_k-f_{k-1}} \\ &=& \enspace \frac{e_{k-1}f(a+e_k)-e_kf(a+e_{k-1})}{f_k-f_{k-1}}\end{split}\]

Expanding \(f(a+e_k)\) using Taylor’s series gives

\[\begin{split}e_{k+1} &=& \enspace \frac{e_{k-1}(e_kf'(a)+e_k^2f''(a)/2+O(e_k^3))-e_k(e_{k-1}f'(a)+e_{k-1}^2f''(a)/2+O(e_{k-1}^3))}{e_kf'(a)+e_k^2f''(a)/2+O(e_k^3)-(e_{k-1}f'(a)+e^2_{k-1}f''(a)/2+O(e_{k-1}^3))} \nonumber \\ &=& \enspace \frac{e_{k-1}e_kf''(a)(e_k-e_{k-1})/2+O(e_{k-1}^4)}{(e_k-e_{k-1})(f'(a)+(e_k+e_{k-1})f''(a)/2+O(e_{k-1}^2))}\end{split}\]

(1)\[\Rightarrow e_{k+1} = \frac{e_{k-1}e_kf''(a)}{2f'(a)}+O(e_{k-1}^3)\]

We want to find \(\alpha\) such that \(|e_{k+1}|=C|e_k|^\alpha\). Since the first term in equation (1) dominates the error, we ignore the cubic term and solve

(2)\[\left|\frac{e_{k-1}e_kf''(a)}{2f'(a)}\right|=C|e_k|^\alpha\]

Canceling \(e_k\) from both sides and changing \(k\) to \(k+1\) gives \(|e_{k+1}|^{\alpha-1}=D|e_k|\), where \(D=|f''(a)/(2Cf'(a))|\). Raising both sides by the power \(\alpha\) gives

(3)\[|e_{k+1}|^{\alpha (\alpha-1)}=D^\alpha|e_k^\alpha|\]

Equating equations (2) and (3) gives, \(C=D^\alpha\) and \(\alpha (\alpha-1)=1\). The negative solution can be discarded because we know that the order of convergence is positive. Thus, the order of convergence is \(\alpha=(1+\sqrt{5})/2\approx1.618\).