Contents

• 1  Newton-Raphson's method
• 2  Exercise

Newton-Raphson's method

Newton's method can be explained as an iterative method where

• The curve is replaced by its tangent line at a point.
• The zero of the curve approaches the zero of the tangent line.
• We take the zeros of the tangent line at this point as an approximation of the zero.
• We repeat until a stop condition is met.

Once Loop Reflect

The equation of the tangent line of $f$ at the point $x_0$ is given by $$y = f'(x_0)(x-x_0)+f(x_0)$$

The zero of this line is $x_1$ and we obtain it by making $y=0,$ in the equation of the tangent line, which gives us the point where the line intersects the $OX$ axis.

$$0 = f'(x_0)(x_1-x_0)+f(x_0)$$

If we solve this equation in $x_1$

$$-f(x_0)= f'(x_0)(x_1-x_0)\quad \Rightarrow\quad -\frac{f(x_0)}{f'(x_0)}=x_1 -x_0 $$

and

$$x_1=x_0-\frac{f(x_0)}{f'(x_0)}$$

Similarly, to obtain $x_2$

$$x_2=x_1-\frac{f(x_1)}{f'(x_1)}$$

and so on.

Algorithm

• Given an initial guess $x_0$
• for $k=1,2,\ldots,\mathrm{MaxNumIter}$:

  • Compute $x_k=x_{k-1}-\dfrac{f(x_{k-1})}{f'(x_{k-1})}$
  • If $x_k$ meets the stopping condition, stop.
  • Else, perform another iteration.

• In general, the method only converges if the starting point, $x_0$ is close enough to the root, $\alpha$. In practice, the bisection method is used previously, or $x_0$ is selected on a plot of $f$ to initialize the algorithm.
• In general, but not always, Newton's method order of convergence is 2.

Advantages

• It is an algorithm that converges quickly.
• It is easy to implement.

Disadvantages

• Depending on the starting point, sometimes it converges, sometimes it doesn't.
• We need the exact derivative of the function, which is not always possible to supply.

Exercise

Approximate, using Newton’s method, $r=\sqrt{3}.$ Use as initial guess $x_{0}=1,$ give three iterations, and compute the residual. Use a calculator to estimate the absolute error of the approximation.

---

Our equation is

$$x=\sqrt{3} \quad \Rightarrow \quad x^2=3 \quad \Rightarrow \quad x^2-3=0$$

Therefore $f(x)=x^2-3$ and $f'(x) = 2x$

The iteration function is given by the expression

$$x_{k+1} = x_k-\frac{f(x_k)}{f'(x_k)}$$

In this case

$$x_{k+1} = x_k-\frac{x_k^2-3}{2x_k}=\frac{2x_k^2-x_k^2+3}{2x_k}=\frac{x_k^2+3}{2x_k}$$

That is

$$x_{k+1} =\frac{x_k^2+3}{2x_k}$$

Iterations

• $x_0=1$, $x_1 =\dfrac{x_0^2+3}{2x_0}=\dfrac{1^2+3}{2}=2$

• $x_1=2$, $x_2 =\dfrac{x_1^2+3}{2x_1}=\dfrac{2^2+3}{2(2)}=1.75$

• $x_2=1.75$, $x_3 =\dfrac{x_2^2+3}{2x_2}=\dfrac{1.75^2+3}{2(1.75)}=1.732143$

Once Loop Reflect

As $\alpha= 1.732051$ the absolute error is

$$e_a = |x_3-\alpha|=|1.732143-1.732051|=0.000092\approx 0.0001$$

The value of the function at the root is zero. The value of the function in the approximation is called residual and, if it is a good approximation, it is a small

$$r =|f(x_3)|=|1.732143^2-3|=0.0003$$

Also, the residual in step $k$ is known, while the error is unknown (we need the exact solution, which is what we are looking for).