2.3: Secant Method

The Secant Method is second best to Newton’s Method, and is used when a faster convergence than Bisection is desired, but it is too difficult or impossible to take an analytical derivative of the function $f(x)$. We write in place of $f^{\prime}\left(x_{n}\right)$,

$$f^{\prime}\left(x_{n}\right) \approx \frac{f\left(x_{n}\right)-f\left(x_{n-1}\right)}{x_{n}-x_{n-1}} \nonumber$$

Starting the Secant Method requires a guess for both $x_{0}$ and $x_{1}$.

2.3.1. Estimate $\sqrt{2}=1.41421356$ using Newton’s Method

The $\sqrt{2}$ is the zero of the function $f(x)=x^{2}-2$. To implement Newton’s Method, we use $f^{\prime}(x)=2 x$. Therefore, Newton’s Method is the iteration

$$x_{n+1}=x_{n}-\frac{x_{n}^{2}-2}{2 x_{n}} \nonumber$$

We take as our initial guess $x_{0}=1$. Then

$$\begin{aligned} &x_{1}=1-\frac{-1}{2}=\frac{3}{2}=1.5 \\ &x_{2}=\frac{3}{2}-\frac{\frac{9}{4}-2}{3}=\frac{17}{12}=1.416667, \\ &x_{3}=\frac{17}{12}-\frac{\frac{17^{2}}{12^{2}}-2}{\frac{17}{6}}=\frac{577}{408}=1.41426 . \end{aligned} \nonumber$$

2.3.2. Example of fractals using Newton’s Method

Consider the complex roots of the equation $f(z)=0$, where

$$f(z)=z^{3}-1 \nonumber$$

These roots are the three cubic roots of unity. With

$$e^{i 2 \pi n}=1, \quad n=0,1,2, \ldots \nonumber$$

the three unique cubic roots of unity are given by

$$1, \quad e^{i 2 \pi / 3}, \quad e^{i 4 \pi / 3} \nonumber$$

With

$$e^{i \theta}=\cos \theta+i \sin \theta, \nonumber$$

and $\cos (2 \pi / 3)=-1 / 2, \sin (2 \pi / 3)=\sqrt{3} / 2$, the three cubic roots of unity are

$$r_{1}=1, \quad r_{2}=-\frac{1}{2}+\frac{\sqrt{3}}{2} i, \quad r_{3}=-\frac{1}{2}-\frac{\sqrt{3}}{2} i \nonumber$$

The interesting idea here is to determine which initial values of $z_{0}$ in the complex plane converge to which of the three cubic roots of unity.

Newton’s method is

$$z_{n+1}=z_{n}-\frac{z_{n}^{3}-1}{3 z_{n}^{2}} \nonumber$$

If the iteration converges to $r_{1}$, we color $z_{0}$ red; $r_{2}$, blue; $r_{3}$, green. The result will be shown in lecture.