# Fixed point iteration: g is a contraction mapping

• MHB
• mathmari
In summary, we have approximated the root of the function $f(x)=x^5-\frac{5}{16}$ using three steps of Newton's method with initial value $x_0=\frac{1}{2}$. The resulting approximation is $x_3=0.9465$. We then discussed how to write the Newton's method as a fixed point iteration on the interval $\Omega=\left [\frac{3}{5}, \infty\right )$, and showed that the function $g(x)=x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}$ is a contraction mapping on $\Omega$. We also discussed the properties of $g(x)$, including its
mathmari
Gold Member
MHB
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)

Last edited by a moderator:
mathmari said:
Does this mean that $g(x)=x-\frac{x^5-\frac{5}{16}}{5\cdot x^4}$ ?
Hey mathmari!

Yep. (Nod)

mathmari said:
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)

mathmari said:
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)

I like Serena said:
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)
I like Serena said:
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)
I like Serena said:
Btw, for a contraction mapping, shouldn't we have $0\le L < 1$? (Wondering)

Oh yes!

mathmari said:
\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)

mathmari said:
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)

I like Serena said:
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)

Last edited by a moderator:
mathmari said:
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)

I like Serena said:
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)

mathmari said:
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)

mathmari said:
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)

I like Serena said:
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)
I like Serena said:
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)

mathmari said:
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)

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)

mathmari said:
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.

mathmari said:
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)

I like Serena said:
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)

mathmari said:
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)

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)

Last edited by a moderator:
Yep. (Nod)

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)

mathmari said:
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)

## 1. What is a fixed point iteration?

A fixed point iteration is a method used in mathematics and computer science to find the solution to a problem by repeatedly applying a function to an initial guess until the result converges to a fixed point, or a point where the function value remains the same.

## 2. What does it mean for g to be a contraction mapping?

A contraction mapping is a function g where the distance between any two points in the range of the function is always decreasing when the function is applied. In other words, the function "contracts" the points towards a fixed point, making it easier to find the solution.

## 3. How can we determine if g is a contraction mapping?

One way to determine if g is a contraction mapping is to calculate its Lipschitz constant. If the Lipschitz constant is less than 1, then g is a contraction mapping. Another way is to graph the function and see if it "contracts" the points towards a fixed point.

## 4. What are the advantages of using fixed point iteration with a contraction mapping?

Using fixed point iteration with a contraction mapping can greatly improve the convergence rate of finding a solution to a problem. It also guarantees that the solution will converge to a fixed point, making it a reliable method for finding solutions.

## 5. Are there any limitations to using fixed point iteration with a contraction mapping?

One limitation is that fixed point iteration may not always converge to a solution if the function is not a contraction mapping. It also may be difficult to determine the Lipschitz constant or graph the function, making it challenging to confirm if the method will work for a particular problem.

Replies
7
Views
1K
Replies
1
Views
911
Replies
9
Views
4K
Replies
2
Views
744
Replies
1
Views
9K
Replies
1
Views
4K
Replies
3
Views
1K
Replies
4
Views
1K
Replies
21
Views
3K
Replies
1
Views
5K