# Use Newton's Method to approximate $x$, accurate to within $10^{-4}$ that produces the point on $y=x^2$ closest to $(1,0)$

Use Newton's Method to approximate $x$, accurate to within $10^{-4}$ that produces the point on $y=x^2$ closest to $(1,0)$.

$\textbf{My approach:}$

I consider the distance between some arbitrary point on $y=x^2$ and $(1,0)$, this is given by: \begin{align}d(x) &= \sqrt{(x-1)^2 + (x^2-0)^2} \\ &= \sqrt{x^4 + x^2 -2x +1} \end{align}

Now, if $d$ is to have a minimum at some point $x_0$, it's slope must be $0$ there, so I want to use Newton's Method to approximate $x_0$ such that $d'(x_0)=0$. In addition, since we require a minimum, we also want $d''(x_0)>0$.

$\textbf{Some questions:}$

Using a program to apply Newton's Method in computing $d'(x)=0$, after 200 iterations with initial value $0.5$, I am nowhere close to the expected root $0.5897$. Is my problem that of finding a good initial value?

I noticed that computing $d''(x)=0$ gives me the result after 3 iterations. Why does finding the root of the second derivative of $d$ give the result when my problem is to minimize $d$?

## 4 Answers

You can define your objective function as

$h(x) = x^4+x^2-2\,x+1$

$h'(x) = 4\,x^3+2\,x-2$

$h''(x) = 12\,x^2+2$

We can see that $h''$ is strictly positive, so you do not have to worry about it, you only need to find the point where $h'=0$.

So, using Newton's Method:

$x_0=0.5\\ x_1 = x_0-\frac{h'(x_0)}{h''(x_0)} = 0.5 - \frac{0.5+1-2}{3+2} = 0.6\\ x_2 = x_1-\frac{h'(x_1)}{h''(x_1)} = 0.6 - \frac{0.864+1.2-2}{4.32+2} = 0.5899$

Since you are not getting the right result, probably there is an implementation error.

As already said in answers, you probably have an implementation error.

If you consider the function you are looking the zero of $$f(x) = 4\,x^3+2\,x-2$$ which is a simple cubic equation, the discriminant is $\Delta=-1856 <0$; then the equation has one real root and two non-real complex conjugate roots. So, you could start from any $x_0$ and you will reach the solution (using more or less iterations depending on how close is $x_0$ to the root). During iterations, you could have one overshoot of the solution; but you can avoid it if you start at a point $x_0$ such that $f(x_0)\times f''(x_0) > 0$ (by Darboux theorem).

Let me give you the iterates of Newton method using various starting points $$\left( \begin{array}{cc} n & x_n \\ 0 & 5.000000000 \\ 1 & 3.317880795 \\ 2 & 2.193845652 \\ 3 & 1.447081888 \\ 4 & 0.967322116 \\ 5 & 0.698571154 \\ 6 & 0.601733590 \\ 7 & 0.589916734 \\ 8 & 0.589754543 \\ 9 & 0.589754512 \end{array} \right)$$

$$\left( \begin{array}{cc} n & x_n \\ 0 & 1.000000000 \\ 1 & 0.714285714 \\ 2 & 0.605168701 \\ 3 & 0.590022042 \\ 4 & 0.589754594 \\ 5 & 0.589754512 \end{array} \right)$$

$$\left( \begin{array}{cc} n & x_n \\ 0 & 0.500000000 \\ 1 & \color{red} {0.600000000} \\ 2 & 0.589873418 \\ 3 & 0.589754529 \\ 4 & 0.589754512 \end{array} \right)$$

In the last case, you can notice the overshoot at the first iteration : this is because $f(\frac 12)=-\frac 12$ while $f''(\frac 12)=12$.

You need to start close to the solution.

With the objective $d$, I get $x_0 = 0.5, x_1\approx 0.6087, x_2\approx 1, x_3 \approx 0.5898$.

If you start at $x_0 = 2$, for example, the iterates go 'wild'.

The function $d^2$ is a little better behaved from a Newton's method perspective as Daniel's answer illustrates.

For $y = x^2$, the slope at $(a, a^2)$ is $2a$, so the slope of the normal is $-\frac1{2a}$.

The equation of the normal is thus $\frac{y-a^2}{x-a} =-\frac1{2a}$.

If this passes through $(1, 0)$, then $\frac{-a^2}{1-a} =-\frac1{2a}$ so that $2a^3 = 1-a$ or $2a^3+a-1 = 0$.

According to Wolfy, this has a real root of about $0.589754512301458$ and two complex roots of about $0.294877256150729 \pm 0.872271625461329 i$.

This is easily generalized.