- Thread starter
- #1

also, how to do the first part, that is, how to see linear convergence with rate constant 3/4? And how to prove the second part and find the rate constant?

- Thread starter ianchenmu
- Start date

- Thread starter
- #1

also, how to do the first part, that is, how to see linear convergence with rate constant 3/4? And how to prove the second part and find the rate constant?

- Admin
- #2

- Admin
- #3

- Mar 5, 2012

- 8,774

Let's define $\Delta x_k$ as the difference between $x_k$ and the actual root.

also, how to do the first part, that is, how to see linear convergence with rate constant 3/4? And how to prove the second part and find the rate constant?

In your case that means that $\Delta x_k = x_k - 2$.

The method is:

$\qquad x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)}$

It follows that:

$\Delta x_{k+1} = \Delta x_k - \dfrac{f(x_k)}{f'(x_k)}$

$\qquad = \Delta x_k - \dfrac{(x_k-2)^4+(x_k-2)^5}{4(x_k-2)^3+5(x_k-2)^4}$

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4}{4(\Delta x_k)^3} + \mathcal O ((\Delta x_k)^2)$

$\qquad = \Delta x_k - \frac 1 4 \Delta x_k + \mathcal O ((\Delta x_k)^2)$

$\qquad = \frac 3 4 \Delta x_k + \mathcal O ((\Delta x_k)^2)$

To make this approximately zero, we need to multiply the part that is subtraced by 4.

Note that the factor 4 is the multiplicity of the root.

That way we will get (at least) quadratic convergence.

With this factor 4 we get:

$\Delta x_{k+1} = \Delta x_k - 4 \dfrac{f(x_k)}{f'(x_k)}$

$\qquad = \Delta x_k - 4 \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \dfrac{1+\Delta x_k}{1+\frac 5 4 \Delta x_k} \Delta x_k$

With a first order expansion of the fraction it follows what the quadratic rate constant will be.

- Thread starter
- #4

whyLet's define $\Delta x_k$ as the difference between $x_k$ and the actual root.

In your case that means that $\Delta x_k = x_k - 2$.

The method is:

$\qquad x_{k+1} = x_k - \dfrac{f(x_k)}{f'(x_k)}$

It follows that:

$\Delta x_{k+1} = \Delta x_k - \dfrac{f(x_k)}{f'(x_k)}$

$\qquad = \Delta x_k - \dfrac{(x_k-2)^4+(x_k-2)^5}{4(x_k-2)^3+5(x_k-2)^4}$

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4}{4(\Delta x_k)^3} + \mathcal O ((\Delta x_k)^2)$

$\qquad = \Delta x_k - \frac 1 4 \Delta x_k + \mathcal O ((\Delta x_k)^2)$

$\qquad = \frac 3 4 \Delta x_k + \mathcal O ((\Delta x_k)^2)$

To make this approximately zero, we need to multiply the part that is subtraced by 4.

Note that the factor 4 is the multiplicity of the root.

That way we will get (at least) quadratic convergence.

With this factor 4 we get:

$\Delta x_{k+1} = \Delta x_k - 4 \dfrac{f(x_k)}{f'(x_k)}$

$\qquad = \Delta x_k - 4 \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \dfrac{1+\Delta x_k}{1+\frac 5 4 \Delta x_k} \Delta x_k$

With a first order expansion of the fraction it follows what the quadratic rate constant will be.

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4}{4(\Delta x_k)^3} + \mathcal O ((\Delta x_k)^2)$?

And where you showed the second method is quadratic convergence and what's the rate constant?

- Admin
- #5

- Mar 5, 2012

- 8,774

Do you know what $\mathcal O(y^2)$ means?why

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \dfrac{(\Delta x_k)^4}{4(\Delta x_k)^3} + \mathcal O ((\Delta x_k)^2)$?

If not you can just ignore it and replace each $=$ by $\approx$.

When $\Delta x_k$ approaches zero, $(\Delta x_k)^5$ becomes negligible with respect to $(\Delta x_k)^4$.

We can write: $(\Delta x_k)^4+(\Delta x_k)^5 = (\Delta x_k)^4+ \mathcal O((\Delta x_k)^5) = (\Delta x_k)^4( 1 + \mathcal O(\Delta x_k))$.

Alternatively, you can do an expansion.

Using $\frac 1 {1+y} = 1 - y + y^2 - ... = 1 - y + \mathcal O(y^2)$

we can expand as follows:

$\qquad \Delta x_k - \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \frac 1 4 \dfrac{1+\Delta x_k}{1+ \frac 5 4 \Delta x_k}\Delta x_k$

$\qquad = \Delta x_k - \frac 1 4 (1+\Delta x_k)(1 - \frac 5 4 \Delta x_k + ...)\Delta x_k$

$\qquad = \Delta x_k - \frac 1 4 (1 - \frac 1 4 \Delta x_k + ...)\Delta x_k$

$\qquad = \Delta x_k - \frac 1 4 \Delta x_k + \mathcal O ((\Delta x_k)^2)$

Can you make an expansion similar to the one I just did to the following expression (which was the last)?And where you showed the second method is quadratic convergence and what's the rate constant?

$\Delta x_{k+1} = \Delta x_k - \dfrac{1+\Delta x_k}{1+\frac 5 4 \Delta x_k} \Delta x_k$

Last edited:

- Thread starter
- #6

So in your way, for the second method, is the rate constant 1/4? SinceDo you know what $\mathcal O(y^2)$ means?

If not you can just ignore it and replace each $=$ by $\approx$.

When $\Delta x_k$ approaches zero, $(\Delta x_k)^5$ becomes negligible with respect to $(\Delta x_k)^4$.

We can write: $(\Delta x_k)^4+(\Delta x_k)^5 = (\Delta x_k)^4+ \mathcal O((\Delta x_k)^5) = (\Delta x_k)^4( 1 + \mathcal O(\Delta x_k))$.

Alternatively, you can do an expansion.

Using $\frac 1 {1+y} = 1 - y + y^2 - ... = 1 - y + \mathcal O(y^2)$

we can expand as follows:

$\qquad \Delta x_k - \dfrac{(\Delta x_k)^4+(\Delta x_k)^5}{4(\Delta x_k)^3+5(\Delta x_k)^4}$

$\qquad = \Delta x_k - \frac 1 4 \dfrac{1+\Delta x_k}{1+ \frac 5 4 \Delta x_k}\Delta x_k$

$\qquad = \Delta x_k - \frac 1 4 (1+\Delta x_k)(1 - \frac 5 4 \Delta x_k + ...)\Delta x_k$

$\qquad = \Delta x_k - \frac 1 4 (1 - \frac 1 4 \Delta x_k + ...)\Delta x_k$

$\qquad = \Delta x_k - \frac 1 4 \Delta x_k + \mathcal O ((\Delta x_k)^2)$

Can you make an expansion similar to the one I just did to the following expression (which was the last)?

$\Delta x_{k+1} = \Delta x_k - \dfrac{1+\Delta x_k}{1+\frac 5 4 \Delta x_k} \Delta x_k$

$\Delta x_{k+1} = \Delta x_k - \dfrac{1+\Delta x_k}{1+\frac 5 4 \Delta x_k} \Delta x_k$

$\qquad = \Delta x_k - \Delta x_k + \frac 1 4 (\Delta x_k)^2 +\mathcal O ((\Delta x_k)^3)$

Last edited:

- Admin
- #7

- Mar 5, 2012

- 8,774

Yep!So in your way, for the second method, is the rate constant 1/4? Since

$\Delta x_{k+1} = \Delta x_k - \dfrac{1+\Delta x_k}{1+\frac 5 4 \Delta x_k} \Delta x_k$

$\qquad = \Delta x_k - \Delta x_k + \frac 1 4 (\Delta x_k)^2 +\mathcal O ((\Delta x_k)^3)$

- Thread starter
- #8

Hey I have a similar question may need your help. It's at here:Yep!

how to prove sequence converges quadratically to a root of multiplicity

You may need to use Taylor series of $f(x_k)$

Thank you!

Last edited: