0

For the root $a$ of the function $\displaystyle{f(a)=\frac{a}{\sqrt{1+a^2}}=0}$ I want to use the sequence $\{x_n\}_{n\geq 0}$ such that $x_{k+1}=x_k-f(x_k)/f'(x_k)$ then for what initial value $x_0$ that the sequence converge to $a$ and how to find it? and also what we can tell about the behaviour of he sequence for other initial value?

Any ideas or theorems should I apply here? I know that $0$ is the only root here and $f'(x)=\frac{1}{(\sqrt{1+x^2})^3}$ so $f'(0)=1$ if $f'(0)>1$ then for all initial value $x_0$ the sequence do not converge but what about $f'(0)=1$

user76608
  • 471
  • Probably the best approach is to evaluate $x_{k+1}$ and check whether it moves closer to or further from the only root at $a = 0$. – hardmath Jul 18 '13 at 19:05

1 Answers1

1

Formally, Newton-Raphson Theorem (NRT) says:

Assume that $f\in C^2[a,b]$ and there exists a number $x\in[a,b]$, where $f(x)=0$. If $f'(x)\neq0$, then there exists a $\epsilon>0$ such that the sequence $\{x_k\}_{k=0}^\infty$ defined by the iteration: $$ x_{k+1} = x_k-\frac{f(x_k)}{f'(x_k)} \qquad\text{for}\qquad k=0,1,\dots $$ will converge to $p$ for any initial approximation $x_0\in[x-\epsilon,x+\epsilon]$.

Just eyeballing your function, I would note the following:

1) As $x\rightarrow\pm\infty$, the square root in the denominator gets dominated by the $x^2$ term: $$ (\sqrt{1+x^2})|_{x\rightarrow\infty} \approx \sqrt{x^2} = x $$ so the function itself starts to look like $f(x)=1$, which has derivative $f'(x)=0$, so your algorithm fails if $|x|\gg1$.

2) The converge of the function depends on the behavior of $\frac{f(x_k)}{f'(x_k)}$. Note that the NRT says:

$f\in C^2[a,b]\longrightarrow$ [twice differentiable]

so let's look at the second derivative: $$ f''(x) = \frac{3x}{(\sqrt{1+x^2})^5} $$ which exhibits linear behavior in the range $(-1/2,1/2)$. If you plot $f(x)$, $f'(x)$, and $f''(x)$, you'll see that for $x\in[-1/2,1/2]$ the functions are linear and have relatively close slopes, so the iterations should converge. Also note that $f''$ has zero slopes at $x=\pm1/2$, indicating the rapid chages in behavior of $f'$, which hints at possible converge issues for $x_0$ values near there. The behavior of both the numerator and denominator in $\frac{f(x_k)}{f'(x_k)}$ are not too erratic for $x\in(-1/2,1/2)$.

In short, to make sure your NR iterations converge, take a look at $f'(x)$ and $f''(x)$ to see if the functions' "behavior" is too unstable (e.g.: rapid changes in $f$ or $f'$ values) for a given range $[a,b]$ of $x$-values. That determines whether the $x_0$ you choose will converge to your desired solution.

Note: In general, it's unfortunately not easy to just code in something which checks the error between $x_k$ values for proper convergence, because there are such things as "oscillatory convergence" and convergence to the wrong root:

Oscillatory Convergence Wrong Root

Kendra Lynne
  • 378