MHB An optimization problem with Newton's method

[i_a_n]

Apply Newton's method to $f(x)=(x-2)^4+(x-2)^5$ with initial guess $x_0=3$. We can observe that the sequence converges linearly with rate constant $3/4$. Now apply the iterative mathod $x_{k+1}=x_k-4f(x_k)/f'(x_k)$. This method should converge more rapidly for this problem. But how to prove that the new method converges quadratically and determine the rate constant?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?

 

[MarkFL]

You should be able to demonstrate that Newton's method leads to:

$\displaystyle x_{k+1}=\frac{3}{4}x_{k}+\frac{7}{16}+\frac{3}{16(4x_{k}-5)}$

and the second method leads to:

$\displaystyle x_{k+1}=\frac{7}{4}+\frac{3}{4(4x_{k}-5)}$

 

[I like Serena]

Apply Newton's method to $f(x)=(x-2)^4+(x-2)^5$ with initial guess $x_0=3$. We can observe that the sequence converges linearly with rate constant $3/4$. Now apply the iterative mathod $x_{k+1}=x_k-4f(x_k)/f'(x_k)$. This method should converge more rapidly for this problem. But how to prove that the new method converges quadratically and determine the rate constant?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?

Let'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.

 

[i_a_n]

Let'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.

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)$?
And where you showed the second method is quadratic convergence and what's the rate constant?

 

[I like Serena]

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)$?

Do 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)$

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

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$

 

[i_a_n]

Do 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$

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)$

 

[I like Serena]

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)$

Yep! ;)

 

[i_a_n]

Yep! ;)

Hey I have a similar question may need your help. It's at here:
http://www.mathhelpboards.com/showthread.php?p=15336

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