Convergence rate of Newton's method (Modified+Linear)

For the following question and proof I do not understand 3 things:

1. Why does $$g'(r) = \frac{f(r)f''(r)}{[f'(r)]^2} = 0.$$? I understand that $$g'(x) = \frac{f(x)f''(x)}{[f'(x)]^2}$$ since $$g'(x)=1-\frac{f(x)f''(x)}{[f'(x)]^2}+{[f'(x)]^2}/{[f'(x)]^2}$$ so 1 cancels out but r is a CONSTANT unlike x which is approaching r. so g'(r)=0-... and the 1 from $${[f'(r)]^2}/{[f'(r)]^2}$$ will not cancel out. So am i wrong?

2. For $$e_{n+1} = x_{n+1}-r = g(x_n) - g(r) = \frac{g''(\xi)}{2}(e_n)^2.$$, shouldnt $$\frac{g''(\xi)}{2}$$ be a constant? but $$\xi$$ changes with xn i think? Question: Let f(x)f(x) be a polynomial in one variable xx and let αα be its δδ-multiple root (δ≥2δ≥2).

3. where did $$f(x) \approx \frac{(x-\xi)^\delta}{\delta !}f^{(m)}(\xi)$$ come from?

sorry im a beginner in numerical analysis and have little idea what imdoing

Show that in the Newton's xk+1=xk−f(xk)/f′(xk)xk+1=xk−f(xk)/f′(xk), the rate of convergence to αα is not quadratic.

Proof: For iterative methods, we have a fixed point formula in the form:

$$\tag 1 x_{n+1} = g(x_n)$$

The Newton iteration is given by:

$$\tag 2 \displaystyle x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$$

So, $(2)$ is of the form $(1)$.

Since $r$ is a root of $f(x) = 0, r = g(r)$. Since $x_{n+1} = g(x_n)$, we can write:

$$x_{n+1} - r = g(x_n) - g(r).$$

Lets expand $g(x_n)$ as a Taylor series in terms of $(x_n -r)$, with the second derivative term as the remainder:

$$g(x_n) = g(r)+g'(r)(x_n-r) + \frac{g''(\xi)}{2}(x_n-r)^2$$

where $\xi$ lies in the interval from $[x_n, r]$, since:

$$g'(r) = \frac{f(r)f''(r)}{[f'(r)]^2} = 0.$$

Because $f(r) = 0$ ($r$ is a root), we have:

$$g(x_n) = g(r) + \frac{g''(\xi)}{2}(x_n-r)^2.$$

Letting $x_n-r = e_n$, we have:

$$e_{n+1} = x_{n+1}-r = g(x_n) - g(r) = \frac{g''(\xi)}{2}(e_n)^2.$$

Each successive error term is proportional to the square of the previous error, that is, Newton's method is quadratically convergent.

Multiple Root

Following the same sort of reasoning, if $x_n$ is near a root of multiplicity $\delta \ge 2$, then:

$$f(x) \approx \frac{(x-\xi)^\delta}{\delta !}f^{(m)}(\xi)$$

$$f'(x) \approx \frac{(x-\xi)^{\delta-1}}{(\delta-1) !}f^{(m)}(\xi)$$

So we have:

$$\tag 3 x_{n+1} -\xi = x_n - \xi -\frac{f(x_n)}{f'(x_n)} = \left(\frac{\delta -1}{\delta}\right)(x_n - \xi)$$

The $\delta$ term on the RHS of $(3)$ in not quadratic, hence we have linear convergence.

You should be able to use with your approach to clean up what you did.

I am confused about what you wrote after your derivation, but I am going to guess that you want to figure out the convergence rate for this $f(x)$.

We are given:

$$f(x) =x^2(x-1)$$

There are two roots to this equation at:

• $x = 0$ (a double root)
• $x = 1$ (a single root)

So, we would expect linear convergence at the double root and quadratic convergence at the single root.

The Newton iteration is given by:

$$x_{n+1} = x_n - \frac{(x_n-1) x_n^2}{x_n^2+2 (x_n-1) x_n}$$

For the first root, lets pick a starting point of $x = 0.1$, we get the following cycle:

• $24$ steps to converge to the root $x = 5.341441708552285 \times 10^{-9}$ (yikes!)

For the second root, lets pick a starting point of $x = 1.4$, we get the following cycle:

• $6$ steps to converge to the root $x = 1.000000000000000$ (much better!)

Now, you would use the exact results and compare them numerically and show the convergence rates for each of the cases.

Note: one must choose a sufficient starting point that will converge to one root or the other. Based on that initial selection, the rate is going to be quadratic when the algorithm converges to $1$ and linear when it converges to $0$. We pick a nearby starting point and see where we end up. You could also graph the function to have an idea about starting points. We typically do not know apriori what roots will give us what behavior. Obviously there is a range where convergence happens to one root or the other. I am not sure how one would calculate that analytically because you may as well figure out the roots without numerical methods in that case.

By definition, $$g(x)=x-\frac{f(x)}{f'(x)}.$$ So $$g'(x)=1-\frac{f'(x)f'(x)-f(x)f''(x)}{f'(x)^2}=\frac{f(x)f''(x)}{f'(x)^2}.$$ Now $r$ is chosen so that $f(r)=0$, so the numerator above is zero: thus, $g'(r)=0$.
Your second point is totally valid, and indeed $\xi$ will depend on $n$. But if you know that $g''$ is continuous, as all the $\xi$ lie inside a closed interval, $g''$ will be bounded in that interval. So, while it is not necessarily constant, the factor $g''(\xi)$ in the error is bounded by a constant.
For your third question, if $r$ is a "root of multiplicity $\delta$", it means that $$0=f(r)=f'(r)=\cdots=f^{(\delta-1)}(r).$$ So all those terms in the Taylor expansion will be gone.
• You cannot change $r$ just because you want to: $f$ is fixed, $g$ is fixed, and $r$ is fixed by the condition $f (r)=0$. – Martin Argerami Feb 9 '18 at 13:27