1
$\begingroup$

How is Newton's Iteration achieved?

I mean, can you please explain where does Newton's iterative formula

$x_{k+1}=\frac{1}{2}(x_k+\frac{N}{x_k})$

come from?

2 Answers 2

0

gt6989b has given a good general definition of Newton's method. Applying it to $f(x)=N-x^2$ we have the equation $f'(x)=-2x$. Then $f(x_{k+1}) =x_k-\frac{f(x_k)}{f'(x_k)}=x_k-\frac{N-x_k^2}{-2x_k}=\frac{x_k}2+\frac N{2x_k}$

2

Intuitively, Newton's method assumes that your function is a line at every point. So assume you are starting from some point $P_n = (x_n, f(x_n))$ and the slope of the Newton approximation line is given by $m = f'(x_n)$, which is given to you as well.

Now, the equation of the line that with slope $m$ that passes through $P_n$ must be $y - f(x_n) = m(x - x_n)$, or in other words $y = f(x_n) + f'(x_n)(x - x_n)$.

You are looking to find the root, i.e. the place where $y=0$. That line has a root when $0 = f(x_n) + f'(x_n)(x - x_n)$, or in other words, where

$x = x_n - \frac{f(x_n)}{f'(x_n)}$,

which is what you would choose as the next iteration point. In other words,

$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$