0
$\begingroup$

When doing old exams in basic numerical analysis, I encountered this problem:

enter image description here

Solution proposal from lecturer: enter image description here

My idea was to select $|f(x)| \le 0.5 \times 10^{-5}$ as the convergence criterion. With this criterion, $x=0.652910$ would have been accepted as a root. When looking at the solution, it seems like the convergence criterion is way smaller.

What is the correct way of selecting convergence criterion using the Bisection, Newton-Raphson or Fixed-Point Iterative method for the given problem?

$\endgroup$
  • $\begingroup$ If you want to prove that you have the root to $n$ digits I would choose bisection as it's very easy to know exactly when to stop. The usual stopping criterions for Newtons method ($|f(x_n)| < \epsilon$ or $|x_{n} - x_{n-1}| < \epsilon$ etc.) does not really give any precise information about the actual error (and there is not a general relation between $\epsilon$ and the number of digits). $\endgroup$ – Winther Feb 19 '18 at 14:30
  • $\begingroup$ You error bound would be correct for 5 digits, to get certainty in the 6th digit you want 0.5e-6, to round correctly you also need the 7th digit relatively correct. $\endgroup$ – LutzL Feb 19 '18 at 15:22
1
$\begingroup$

You are asked to find $r$ to 6 decimals, but your proposal only ensures that $f(r)$ is correct to 6 decimals. You are calculating successive approximations to $r$ ($x_0,x_1,\cdots$). Plot $x_i$ vs. $i$: you should be able to see it converge, and identify a point beyond which you are confident that you have approximated the limit value to 6 decimal points.

Besides, your answer is as good as correct.

$\endgroup$
1
$\begingroup$

I don't know why you select function-value as a criterion, it's quite obvious the output is root. So, we iterate with criterion for roots, x, because the output values have fluctuating roots. Therefore, we need to use absolute error or relative error for root. $$\text{Abs. Error : }|x_{i+1}-x_i|$$ $$\text{Rel. Error : }\left|\frac{x_{i+1}-x_i}{x_i}\right|$$ Moreover, the problem requires 10^-6 tolerance, it means Abs. Error has the value less than 10^-6.

In my code, my answer is 0.652918640419205 in the long format of Matlab.

$\endgroup$
  • $\begingroup$ So when no convergence criterion is specified, it is correct to use the absolute error less than the tolerance required? $\endgroup$ – Numerical Newbie Feb 19 '18 at 13:04
  • $\begingroup$ When there is no criterion, you need to select tolerance and criterion. For example, I can say my result "the root is approximately 0.6529186 with 1e-6 absolute error." $\endgroup$ – Lee TY Feb 19 '18 at 13:14
  • $\begingroup$ May I recommend to always use the relative error ? $\endgroup$ – Claude Leibovici Feb 20 '18 at 11:23
  • $\begingroup$ In almost all of my researches and assignments till now(from undergrad. to grad. school), I have used the relative error. $\endgroup$ – Lee TY Feb 20 '18 at 11:28

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.