0
$\begingroup$

I have programmed Newton's method in Matlab and it is working quite good. However if the multiplicity of the found root is greater than one, the method doesn't work very well. Therefore I did some research on the internet and found out about the accelerated Newton's method.This calculates the roots by taking the multiplicity of the root in consideration: $x_{n+1} = x_n - m \frac{f(x_n)}{f'(x_n)}$.

I can guess the multiplicity for some functions, but sometimes it is too difficult to guess. How can I calculate this $m$ in Matlab (for example doing a few iterations and updating $m$).

I have read that $\frac{f(x_n)}{f'(x_n)}$ is equal to $\frac{x-\alpha}{m}$ for $x$ close to $\alpha$?

How can I use this above to calculate $m$?

$\endgroup$
1
$\begingroup$

If you don't know $m$, you could always use what Burden and Faires call the "modified Newton's Method," which is to apply Newton's method to $\mu(x) = f(x)/f'(x)$.

But both the modified Newton's Method, and the method you propose, will suffer from the same practical problem. As $x_n$ gets close to the root, $f'(x_n)$ gets very close to zero. Thus $f(x_n)/f'(x_n)$ is very close to $0/0$. So while the answer isn't theoretically undefined, the numerical errors will be large, and eventually your iterates will be "Nan" (which stands for "not a number").

Anyway, if you do want to use the method you propose, then I think the best way to find $m$ is to try the accelerated Newton's Method for different $m$, and see which one converges fast.

This is essentially equivalent to the method you propose, that is, finding out how $f(x)/f'(x)$ compares to $(x-\alpha)/m$ for $x$ close to $\alpha$. This is because your method requires knowing what $\alpha$ is, and the only approximations to $\alpha$ you have are the iterates of your algorithm.

$\endgroup$
  • $\begingroup$ If I want to do my method, what is the best way to do it? Do 3 iterations for example, then use the value of the third iteration as alpha, and then calculate m using (x−α)/m for x close to α. Then you have m and then do the three iterations again, but now with xn+1=xn−mf(xn)f′(xn) included? And then repeat this process? Or is there a more efficient way? Thanks in advance! $\endgroup$ – Dennis Kraakman Mar 7 '15 at 19:01
  • $\begingroup$ I think you will find it very hard to overcome the numerical errors, no matter which way you do it. $\endgroup$ – Stephen Montgomery-Smith Mar 7 '15 at 19:52
  • $\begingroup$ But why don't you try it and see. $\endgroup$ – Stephen Montgomery-Smith Mar 7 '15 at 19:52

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.