3
$\begingroup$

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$?

$\endgroup$
0
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy