I have been asked if the Newton's method (More concretely Maehly's method) is numerically inestable. I know finding roots of a polynomial is an ill-posed problem, and also that the Newton's method converges to a root $x$ in a small enough neighborhood of $x$.

What can I say about stability? I would say that Newton's method is indeed numerically stable provided the polynomial does not have roots too close to each other, because in practice when two or more roots are too close from each other in the iterations

$$x_{k+1}=x_k-\frac{p(x_k)}{p'(x_k)-p(x_k) \sum_{j=1}^m \frac{1}{x - \alpha_j} }, $$ where the $\alpha_j$ are the already computed roots, you are substracting two terms that are very close, $p'(x_k)-p(x_k)$ (catastrophic cancelation), and then also dividing by a number close to $0$, because both terms tend to $0$.

What do you think? Is this answer correct?

  • $\begingroup$ The problem is not that $p′(x_k)−p(x_k)$ generates catastrophic cancellation, but that both terms are the result of catastrophic cancellation during polynomial evaluation where big terms sum up to something close to zero. The evaluation errors of $p(x_k)$ and $p(x_k)$ being large relative to their size does not get better under division. $\endgroup$ – LutzL Nov 26 '16 at 22:32
  • $\begingroup$ @LutzL Okay, x being close to 0 produces evaluation of monomials being very close to 0 and substracting these produces cancellation errors, But also in Newton's method you are dividing $p(x_k)$ by a number which is very close to zero($p′(x_k)−p(x_k)$), further increasing the error, right? Also, Is it correct the response about stability when roots are not close to each other? $\endgroup$ – D1X Nov 27 '16 at 9:41
  • $\begingroup$ Not exactly. In the opposite, it is when a root $x$ is far away from zero that the large monomials of the polynomial combine to a small value. And your denominator is not $p'(x_k)−p(x_k)$, there is still that sum as a factor. -- For polynomials you can use deflation instead of this method, the problems remain approximately the same. $\endgroup$ – LutzL Nov 27 '16 at 9:53
  • $\begingroup$ @LutzL Could you please explain this a little more, I don't get what you mean. $\endgroup$ – D1X Nov 27 '16 at 10:08
  • $\begingroup$ While the true value of $p(x)=p_nx^n+…+p_0$ is zero or close to it, the error due to evaluation is on the scale of the product of the machine constant $\mu$ and $|p|(|x|)=|p_n|·|x|^n+…+|p_0|$ which even for moderate $n$ and coefficient size will be large. $\endgroup$ – LutzL Nov 27 '16 at 10:41

Your Answer

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

Browse other questions tagged or ask your own question.