MHB Fixed point iteration: g is a contraction mapping

[mathmari]

Hey!

We have the function $f(x)=x^5-\frac{5}{16}$.

I have approximated the root of that function using three steps of Newton's method with initla value $x_0=\frac{1}{2}$ :

\begin{align*}x_1&=x_0-\frac{f(x_0)}{f'(x_0)}\approx \frac{7}{5} \\ x_2&=x_1-\frac{f(x_1)}{f'(x_1)} \approx 1.1362692628 \\ x_3&=x_2-\frac{f(x_2)}{f'(x_2)}\approx 0.9465088238\end{align*}

So, $x_3=0.9465$ is an approximation of the root of $f(x)=x^5-\frac{5}{16}$. Now, I want to write the Newton's method for the above function as a fixed point iteration $x_{k+1}=g(x_k)$ on $\Omega=\left [\frac{3}{5}, \infty\right )$ and to show that $g$ is a contraction mapping, i.e. to show that it holds that $g( \Omega )\subset\Omega$ and $|g(x)-g(y)|\leq L|x-y|$ for $x,y\in \Omega$. The Newton's method is $$x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}=x_n-\frac{x_n^5-\frac{5}{16}}{5\cdot x_n^4}$$ Does this mean that $g(x)=x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}$ ?

To show that $g( \Omega )\subset\Omega$ do we have to check if the function is monotone?

About the second property, we have the following:
\begin{align*}|g(x)-g(y)|&=\left |\left (x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}\right )-\left (y-\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right )\right |\\ & = \left |x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}-y+\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right | \\ & = \left |\left (x-y\right )-\left (\frac{x^5-\frac{5}{16}}{5\cdot x^4}-\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right )\right |\\ & \leq \left |x-y\right |+\left |\frac{x^5-\frac{5}{16}}{5\cdot x^4}-\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right | \end{align*}

Is the last step correct? How can we bound the second term? (Wondering)

 

[I like Serena]

Does this mean that $g(x)=x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}$ ?

Hey mathmari!

Yep. (Nod)

To show that $g( \Omega )\subset\Omega$ do we have to check if the function is monotone?

I think we need to check that if $x\ge \frac 35$ that then $g(x) \ge \frac 35$, don't we? (Wondering)

About the second property, we have the following:
\begin{align*}|g(x)-g(y)|&=\left |\left (x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}\right )-\left (y-\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right )\right |\\ & = \left |x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}-y+\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right | \\ & = \left |\left (x-y\right )-\left (\frac{x^5-\frac{5}{16}}{5\cdot x^4}-\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right )\right |\\ & \leq \left |x-y\right |+\left |\frac{x^5-\frac{5}{16}}{5\cdot x^4}-\frac{y^5-\frac{5}{16}}{5\cdot y^4}\right | \end{align*}

Is the last step correct? How can we bound the second term?

How about checking if the derivative is bounded?
Then we can apply the Mean Value Theorem can't we?
What can we say about $g'(x)$? (Wondering)

Btw, for a contraction mapping, shouldn't we have $0\le L < 1$? (Wondering)

 

[mathmari]

I think we need to check that if $x\ge \frac 35$ that then $g(x) \ge \frac 35$, don't we? (Wondering)

\begin{align*}&g(x)=x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}=x-\frac{x^5}{5\cdot x^4}+\frac{\frac{5}{16}}{5\cdot x^4}=x-\frac{x}{5}+\frac{x^{-4}}{16}=\frac{4x}{5}+\frac{x^{-4}}{16}\\ & \Rightarrow g'(x)=\frac{4}{5}-\frac{4x^{-5}}{16}=\frac{4}{5}-\frac{x^{-5}}{4}=\frac{4}{5}-\frac{1}{4x^5}\end{align*}

We have that $g'(x)=0 \Rightarrow \frac{4}{5}-\frac{1}{4x^5}=0 \Rightarrow x^5-\frac{5}{16}=0$

From the Newton's method we have that the root is approximately $0,9$.

So, after $0.9$ it doesn't change the sign. Or can we not say that, because we don't know if there are also other real roots?

If we can we that, we can find if the function is increasing or decreasing at $\left [\frac{3}{5}, \infty\right )$ and so find the image, or not? (Wondering)

Or is there an other way to check if $g(x)\geq \frac{3}{5}$ for $x\geq \frac{3}{5}$ ? (Wondering)

How about checking if the derivative is bounded?
Then we can apply the Mean Value Theorem can't we?
What can we say about $g'(x)$? (Wondering)

The derivative looks like the function f(x), but not exactly. Or not? (Wondering)

Btw, for a contraction mapping, shouldn't we have $0\le L < 1$? (Wondering)

Oh yes!

 

[I like Serena]

\begin{align*}&g(x)=x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}=x-\frac{x^5}{5\cdot x^4}+\frac{\frac{5}{16}}{5\cdot x^4}=x-\frac{x}{5}+\frac{x^{-4}}{16}=\frac{4x}{5}+\frac{x^{-4}}{16}\\ & \Rightarrow g'(x)=\frac{4}{5}-\frac{4x^{-5}}{16}=\frac{4}{5}-\frac{x^{-5}}{4}=\frac{4}{5}-\frac{1}{4x^5}\end{align*}

We have that $g'(x)=0 \Rightarrow \frac{4}{5}-\frac{1}{4x^5}=0 \Rightarrow x^5-\frac{5}{16}=0$

From the Newton's method we have that the root is approximately $0,9$.

So, after $0.9$ it doesn't change the sign. Or can we not say that, because we don't know if there are also other real roots?

If we can we that, we can find if the function is increasing or decreasing at $\left [\frac{3}{5}, \infty\right )$ and so find the image, or not? (Wondering)

Or is there an other way to check if $g(x)\geq \frac{3}{5}$ for $x\geq \frac{3}{5}$ ?

We've found that $g$ has a local minimum at $x_0=\sqrt[5]{\frac 5{16}}\approx 0.9$ didn't we?
Doesn't it suffice then if $g(x_0) \ge \frac 35$? (Wondering)

The derivative looks like the function f(x), but not exactly. Or not?

In particular we have $g'(x) < \frac 45$ for $x\in\Omega$ don't we?
Doesn't that mean that $|g(x)-g(y)| < \frac 45 |x-y|$? (Thinking)

 

[mathmari]

We've found that $g$ has a local minimum at $x_0=\sqrt[5]{\frac 5{16}}\approx 0.9$ didn't we?
Doesn't it suffice then if $g(x_0) \ge \frac 35$? (Wondering)

But it is a local minimum, can we say that for every $x\geq \frac{3}{5}$ it holds that $g(x)\geq g(x_0)$ ? (Wondering)

 

[I like Serena]

But it is a local minimum, can we say that for every $x\geq \frac{3}{5}$ it holds that $g(x)\geq g(x_0)$ ?

Isn't it a global minimum on $\Omega$? (Thinking)

 

[mathmari]

Isn't it a global minimum on $\Omega$? (Thinking)

How do we know that? (Wondering)
From the Mean Vaue Theorem we have that for $x,y\in \Omega$ and $c\in [y,x]$: \begin{equation*}g'(c)=\frac{g(x)-g(y)}{x-y}\end{equation*} So we get \begin{equation*}g'(c)<\frac{4}{5} \Rightarrow \frac{g(x)-g(y)}{x-y}<\frac{4}{5}\Rightarrow g(x)-g(y)<\frac{4}{5}(x-y)\end{equation*} right? How do we get the absolute values? (Wondering)

 

[I like Serena]

How do we know that?

Isn't $g$ continuous on $\Omega$ with only a single point $x_0$ with $g'(x_0)=0$?
That means that $g$ has a local extremum at $x_0$ and possibly another one at the boundary $x=\frac 35$.
When we evaluate $g(x_0)$ and $g(\frac 35)$, and since $g(x)\to\infty$ for $x\to \infty$, doesn't it follow that we have a global minimum at $x_0$ and a local maximum at the boundary $\frac 35$? (Wondering)

From the Mean Vaue Theorem we have that for $x,y\in \Omega$ and $c\in [y,x]$: \begin{equation*}g'(c)=\frac{g(x)-g(y)}{x-y}\end{equation*} So we get \begin{equation*}g'(c)<\frac{4}{5} \Rightarrow \frac{g(x)-g(y)}{x-y}<\frac{4}{5}\Rightarrow g(x)-g(y)<\frac{4}{5}(x-y)\end{equation*} right? How do we get the absolute values? (Wondering)

We can write it as
\begin{equation*}|g'(c)|=\left|\frac{g(x)-g(y)}{x-y}\right|\end{equation*}
can't we?

And yes, it does mean that we need to check $|g'(\frac 35)|$, since it can be bigger than $\frac 45$.
Is it? (Wondering)

 

[mathmari]

Isn't $g$ continuous on $\Omega$ with only a single point $x_0$ with $g'(x_0)=0$?
That means that $g$ has a local extremum at $x_0$ and possibly another one at the boundary $x=\frac 35$.
When we evaluate $g(x_0)$ and $g(\frac 35)$, and since $g(x)\to\infty$ for $x\to \infty$, doesn't it follow that we have a global minimum at $x_0$ and a local maximum at the boundary $\frac 35$? (Wondering)

That means that $g(x)\geq g(x_0)$ for every $x\in \Omega$, right?

So we have to calculate the value of $g(x_0)$, right?

(Wondering)

We can write it as
\begin{equation*}|g'(c)|=\left|\frac{g(x)-g(y)}{x-y}\right|\end{equation*}
can't we?

And yes, it does mean that we need to check $|g'(\frac 35)|$, since it can be bigger than $\frac 45$.
Is it? (Wondering)

We have that $g'(c)<\frac{4}{5}$, but that doesn't necesarily that $|g'(c)|<|\frac{4}{5}|$, does it? (Wondering)

 

[I like Serena]

That means that $g(x)\geq g(x_0)$ for every $x\in \Omega$, right?
So we have to calculate the value of $g(x_0)$, right?

We have that $g'(c)<\frac{4}{5}$, but that doesn't necesarily that $|g'(c)|<|\frac{4}{5}|$, does it?

Yep and yep. (Nod)

 

[mathmari]

We have that $g(x_0)=\frac{4x_0}{5}+\frac{x_0^{-4}}{16}=\frac{4\cdot 0.9}{5}+\frac{0.9^{-4}}{16}\approx 0.8>\frac{3}{5}$.

So, we have for each $x\in \left [\frac{3}{5}, \infty\right )$: $$g(x)\geq g(x_0)>\frac{3}{5}$$
right? (Wondering)
I haven't really understood how we get $|g'(c)|<\frac{4}{5}$, I mean with the absolute values. Could you explain this to me? (Wondering)

 

[I like Serena]

We have that $g(x_0)=\frac{4x_0}{5}+\frac{x_0^{-4}}{16}=\frac{4\cdot 0.9}{5}+\frac{0.9^{-4}}{16}\approx 0.8>\frac{3}{5}$.

So, we have for each $x\in \left [\frac{3}{5}, \infty\right )$: $$g(x)\geq g(x_0)>\frac{3}{5}$$
right?

Yep.

I haven't really understood how we get $|g'(c)|<\frac{4}{5}$, I mean with the absolute values. Could you explain this to me? (Wondering)

Won't we have:
$$0\le |g'(x)| \le \max\left(|\inf_\Omega g'(x)|, |\sup_\Omega g'(x)|\right)$$
?
It means we have to find the maxima and minima of $g'(x)$ on $\Omega$. (Thinking)

 

[mathmari]

Won't we have:
$$0\le |g'(x)| \le \max\left(|\inf_\Omega g'(x)|, |\sup_\Omega g'(x)|\right)$$
?
It means we have to find the maxima and minima of $g'(x)$ on $\Omega$. (Thinking)

We have that $g''(x)=\frac{5}{4}x^{-6}$ which hasn't any roots. Does this mean that the minima or maxima, if they exist, must be on the boundaries? (Wondering)

 

[I like Serena]

We have that $g''(x)=\frac{5}{4}x^{-6}$ which hasn't any roots. Does this mean that the minima or maxima, if they exist, must be on the boundaries?

Yep. (Nod)

 

[mathmari]

Since $g''(x)>0$ for $x\in \Omega$. So, the derivative $g'$ is increasing.

That means that $x\geq \frac{3}{5}\Rightarrow g'(x)\geq g'\left (\frac{3}{5}\right )\approx -2.4$.

That means that the minimum is about $-2.4$, right?

The maximum is $\frac{4}{5}$, right?

So, we have that $-2.4\leq g'(x)<\frac{4}{5}<2.4\Rightarrow |g'(x)|<2.4$ and nnow we can apply the Mean value theorem, right?

But we will get then $L=2,4$ and not less than $1$, or not?

(Wondering)

 

[I like Serena]

Yep. (Nod)

 

[mathmari]

So, we get the following:
\begin{equation*}|g'(c)|<2.4 \Rightarrow \frac{|g(y)-g(x)|}{|y-x|}<2.4 \Rightarrow |g(y)-g(x)|<2.4|y-x|\end{equation*}
At the exercise statement it is not mentioned that L must be less than 1, but in Wikipedia this condition is mentioned.

So, is it correct what I have found with 2.4? (Wondering)

 

[I like Serena]

So, we get the following:
\begin{equation*}|g'(c)|<2.4 \Rightarrow \frac{|g(y)-g(x)|}{|y-x|}<2.4 \Rightarrow |g(y)-g(x)|<2.4|y-x|\end{equation*}
At the exercise statement it is not mentioned that L must be less than 1, but in Wikipedia this condition is mentioned.

So, is it correct what I have found with 2.4?

I believe the 2.4 is correct.
And it seems to me that we really need the constant to be less than 1 for a contraction mapping.
Otherwise we can't guarantee that the iterations will converge, which is what it's for.
We can fix it by picking $\frac 34$ instead of $\frac 35$. Could there be a typo? (Wondering)

In this particular case the iterations will converge anyway though, since the first iteration will yield a point to the right of $x_0$ after which we're in the contracting part of the domain. (Thinking)