1
$\begingroup$

The minimum number of iterations to find $√28$ correct up to three decimal places by Newton-Raphson method using $5$ as the initial guess is .....

  • I took $x_0$=5 and used the formula $x_{n+1}=x_n - f(x_n)/f'(x_n)$ to get $x_1=5.3$, $x_2=5.21950943$ and $x_3=5.21950262$. As the last two approximations are same up to 5 decimal places, hence the answer is 3. Am I correct? What is the general method to find minimum number of iterations in Newton-Raphson method to get the root correct to n decimal places?
$\endgroup$
2
$\begingroup$

You need some estimates on the range covered by the iteration, a minimum bound $m_1$ for the first and a maximum bound $M_2$ for the second derivative over that region.

Here we have $f(x)=x^2-28$ over the interval $[5,6]$. As $$ N(x)=x-\frac{f(x)}{f'(x)}\implies f(N(x))=\frac12f''(\tilde x)\frac{f(x)^2}{f'(x)^2} $$ gives contraction for $$ \frac12M_2m_1^{-2}|f(x)|<1\iff|f(x)|<2m_1^2/M_2 $$ Using $$ \min_{x\in[5,6]}|f'(x)|=10\text{ and }f''(x)\equiv 2 $$ this is satisfied on this interval and one gets the estimate of the quadratic convergence $$ |f(N(x))|\le 10^{-2}|f(x)|^2\implies |f(x_n)|\le 100·\left(10^{-2}|f(x_0)|\right)^{2^n}=100·\left(0.03\right)^{2^n} $$ As $|x-x_*|\le 0.1 ·|f(x)|$, the distance to the root satisfies $$ |x_n-x_*|\le 10·\left(0.03\right)^{2^n} $$

To get 5 digits after the dot you need $|x_n-x_*|\le 5·10^{-6}$ and $n=2$ gives $|x_2-x_*|\le 81·10^{-7}$ which is slightly too large, so $n=3$ will satisfy the error bound with a wide margin.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.