I'm really trying to understand this. The paper says:

At a multiple root, the Newton-Raphson method converges linearly (I get that). The method is given by:

$$x_{i+1} = x_{i} - m {f(x_{i})\over f'(x_{i})}$$

Where $\space m \space$ is the multiplicity of the root, will restore quadratic convergence at such a root.

Here is what I don't understand.

I have been told to write a program in Maple (if that helps) that approximates $\space m \space$.

But isn't $\space x_{i+1} \space$ recursive?

I am given the value of $\space x_{0} \space$. But $\space x_{i+1} \space$ is still unknown because we don't know $\space m \space$.

Can someone help me please? I hope I'm making sense.

Thank You.

  • 1
    $\begingroup$ It is recursive, you simply can't know $x_{i+1}$ immediately from $x_0$. But you can let the programme do that (pseudo): for k in range(i): x = x-m*f(x)/f'(x). $\endgroup$ – Vim May 11 '17 at 7:19
  • $\begingroup$ @Vim - Thank you for responding. Can you please expand on that code. $\endgroup$ – Max Echendu May 11 '17 at 12:41
  • 1
    $\begingroup$ do you know how value-assigning works in a programme? x=g(x) is an value assigning expression instead of a mathematical statement, so it means "update x with the new value f(x)". Such "updates" are what Newton method is. $\endgroup$ – Vim May 11 '17 at 12:46
  • 1
    $\begingroup$ the for loop carries out i iterations and get the value of x_i+1, assuming x_0 is given. $\endgroup$ – Vim May 11 '17 at 12:58
  • 1
    $\begingroup$ Ok I misread your question sorry. It seems you're confused about $m$ which I just assumed known. I think it might help if you can clarify what the muliplicitu of the root means. $\endgroup$ – Vim May 11 '17 at 13:10

Let be $e_n=\left\vert x_{n+1}-x_n\right\vert$. You can estimate the value of $m$ considering $$e_{n+1}=\frac{m-1}{m}e_n.$$ Just make two normal Newton steps and use $x_0,x_1,x_2$ to evaluate the two succesive errors. The first steps of any iterative method may not be very good, specially in multiple roots, so you can discard $x_0,x_1$ and take two additional steps before approximate $m$.

Deepening a little more: if a function $f$ has a multiple root $r$ with multiplicity $m$, then $f$ is of the form $$f(x)=(x-r)^mg(x)$$ with necessarly $g(r)\neq 0$ and $f^\prime(x)=f^{\prime\prime}(x)=\cdots =f^{(m-1)}(x)=0$. Let be $u(x)=f(x)/f^\prime (x)$. The function $u(x)$ has only one root (easy to proof) and you can use the iteration $$x_{n+1}=x_n-\frac{u(x)}{u^\prime (x)}$$ and it converges cuadratically.

Also you can dynamically estimate $m$ with $$m=\max\left\{1, INT\left(\frac{x_n-x_{n-1}}{u(x_n)-u(x_{n-1})}\right)\right\}$$ as William Kahan suggest.


Your Answer

