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

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.