MHB For which values of a can we solve it iteratively?

[mathmari]

Hey!

For which values of $a\neq 0$ can we solve iteratively $ax^3-x-2=0$ by $x_{n+1}=ax_n^3-2, \ n=1,2, \ldots $ with appropriate $x_1$ ?

I have done the following:

$$ax^3-x-2=0 \Rightarrow x=ax^3-2$$ So we can consider a fix point problem with $\phi (x)=ax^3-2$.

So we have to check when the fix point iteration converges right?

For that $\phi$ has to be Lipshitz continuous, or not? :unsure:

 

[I like Serena]

Hey mathmari!

Isn't it the other way around?

If a function $f$ defined on the real line with real values is Lipschitz continuous with Lipschitz constant $L<1$, then this function has precisely one fixed point, and the fixed-point iteration converges towards that fixed point for any initial guess $x_0$.​

So we can only use that to prove that if $a$ is on a specific interval, and if the Lipschitz continuity related criterions are satisfied (perhaps on a sub domain), that we have a converging sequence, can't we?

 

[I like Serena]

We can check for which values of $a$ we have that $|\phi'(x)|<1$ at a solution $x$.
I believe that is the case for $-1<a\le\frac 1{27}$.
We can also verify that for different values of $a$ the algorithm diverges.

 

[mathmari]

I believe that is the case for $-1<a\le\frac 1{27}$.

How did you find this interval? :unsure:

 

[I like Serena]

How did you find this interval?

I made a couple of drawings for $a=0,1,-1$ and for $a$ positive/negative and close to zero.
And I considered how the algorithm would progress.
Consequently I discovered a couple of edge cases and calculated where those edges were.

Consider for instance the following graph:
\begin{tikzpicture}[
declare function={
f(\x) = (\x)^3 / 50 - 2;
}]
\draw[help lines] (-6,-6) grid (8,8);
\draw[-latex] (-6,0) -- (8,0);
\draw[-latex] (0,-6) -- (0,8);
\draw[domain=-6:8.2, variable=\x, blue, thick] plot ({\x}, {\x});
\draw[domain=-6:8.2, variable=\x, blue, thick, smooth] plot ({\x}, {f(\x)});
\node[below left] at (0,-2) {$-2$};
\node[above] at (3,0) {$x_1$};
\draw[red, ultra thick, -latex] (3,0) -- (3,{f(3)}) -- ({f(3)},{f(3)}) -- ({f(3)},{f(f(3))}) -- ({f(f(3))},{f(f(3))});
\end{tikzpicture}

In this case the sequence converges, doesn't it?
What would the edge cases be?

 

[mathmari]

I made a couple of drawings for $a=0,1,-1$ and for $a$ positive/negative and close to zero.
And I considered how the algorithm would progress.
Consequently I discovered a couple of edge cases and calculated where those edges were.

Consider for instance the following graph:
\begin{tikzpicture}[
declare function={
f(\x) = (\x)^3 / 50 - 2;
}]
\draw[help lines] (-6,-6) grid (8,8);
\draw[-latex] (-6,0) -- (8,0);
\draw[-latex] (0,-6) -- (0,8);
\draw[domain=-6:8.2, variable=\x, blue, thick] plot ({\x}, {\x});
\draw[domain=-6:8.2, variable=\x, blue, thick, smooth] plot ({\x}, {f(\x)});
\node[below left] at (0,-2) {$-2$};
\node[above] at (3,0) {$x_1$};
\draw[red, ultra thick, -latex] (3,0) -- (3,{f(3)}) -- ({f(3)},{f(3)}) -- ({f(3)},{f(f(3))}) -- ({f(f(3))},{f(f(3))});
\end{tikzpicture}

In this case the sequence converges, doesn't it?
What would the edge cases be?

I cannot see the graph

 

[I like Serena]

I cannot see the graph

Can you tell what is wrong with it? It shows up fine for me.

My previous comment contains the following latex code:

\begin{tikzpicture}[
  declare function={
    f(\x) = (\x)^3 / 50 - 2;
  }]
  \draw[help lines] (-6,-6) grid (8,8);
  \draw[-latex] (-6,0) -- (8,0);
  \draw[-latex] (0,-6) -- (0,8);
  \draw[domain=-6:8.2, variable=\x, blue, thick] plot ({\x}, {\x});
  \draw[domain=-6:8.2, variable=\x, blue, thick, smooth] plot ({\x}, {f(\x)});
  \node[below left] at (0,-2) {$-2$};
  \node[above] at (3,0) {$x_1$};
  \draw[red, ultra thick, -latex] (3,0) -- (3,{f(3)}) -- ({f(3)},{f(3)}) -- ({f(3)},{f(f(3))}) -- ({f(f(3))},{f(f(3))});
\end{tikzpicture}

It should render as an SVG picture.
Perhaps SVG does not work correctly in your browser. Which browser do you use?
And which operating system do you have? Windows? Which version?

Here is a PNG version of the picture:

As you can see, the algorithm converges to the fix point where the slope has magnitude less than 1. That is, where $|\phi'(x)|<1$.

 

[mathmari]

Ok! So we have that $\phi (x)=ax^3-2$. The derivative is equal to $\phi'(x)=3ax^2$. So $\phi$ is increasing if $a>0$ and decreasing if $a<0$, right?

So if we take an interval $(m, n)$ if $a>0$ the maximum is at $x=n$ and if $a<0$ the maximum is at $x=m$, or not? :unsure:

 

[I like Serena]

Ok! So we have that $\phi (x)=ax^3-2$. The derivative is equal to $\phi'(x)=3ax^2$. So $\phi$ is increasing if $a>0$ and decreasing if $a<0$, right?

Yep.

So if we take an interval $(m, n)$ if $a>0$ the maximum is at $x=n$ and if $a<0$ the maximum is at $x=m$, or not?

This is true. It doesn't really help us though, does it? Here's another picture with a bigger $a$.
\begin{tikzpicture}[
declare function={
f(\x) = (\x)^3 / 10 - 2;
}]
\draw[help lines] (-6,-6) grid (8,8);
\draw[-latex] (-6,0) -- (8,0);
\draw[-latex] (0,-6) -- (0,8);
\draw[domain=-6:8, variable=\x, blue, thick] plot ({\x}, {\x});
\draw[domain=-3.7:4.8, variable=\x, blue, thick, smooth] plot ({\x}, {f(\x)});
\node[below left] at (0,-2) {$-2$};
\draw[red, ultra thick, -latex] (2,0) -- (2,{f(2)}) -- ({f(2)},{f(2)}) -- ({f(2)},{f(f(2))}) -- ({f(f(2))},{f(f(2))})
-- ({f(f(2))},{f(f(f(2)))}) -- ({f(f(f(2)))},{f(f(f(2)))}) -- ({f(f(f(2)))},{f(f(f(f(2))))}) -- ({f(f(f(f(2))))},{f(f(f(f(2))))}) -- ({f(f(f(f(2))))},-7);
\draw[red, ultra thick, -latex] (4,0) -- (4,{f(4)}) -- ({f(4)},{f(4)}) -- ({f(4)},{f(f(4))}) -- ({f(f(4))},{f(f(4))}) -- ({f(f(4))},9);
\node[above] at (2,0) {$x_1$};
\node[below] at (4,0) {$x_1$};
\end{tikzpicture}
If you cannot see the picture, you can copy-and-paste the latex code in http://35.164.211.156/tikz/tikzlive.html.

We can see that if we start to the right of the rightmost fix point, that the algorithm diverges because the slope is greater than 1.
And if we start where the slope is less than 1, we "almost" converge. Except that there is no fixpoint to converge to. So we diverge after all. (Sweating)

 

[mathmari]

Here's another picture with a bigger $a$.
\begin{tikzpicture}[
declare function={
f(\x) = (\x)^3 / 10 - 2;
}]
\draw[help lines] (-6,-6) grid (8,8);
\draw[-latex] (-6,0) -- (8,0);
\draw[-latex] (0,-6) -- (0,8);
\draw[domain=-6:8, variable=\x, blue, thick] plot ({\x}, {\x});
\draw[domain=-3.7:4.8, variable=\x, blue, thick, smooth] plot ({\x}, {f(\x)});
\node[below left] at (0,-2) {$-2$};
\draw[red, ultra thick, -latex] (2,0) -- (2,{f(2)}) -- ({f(2)},{f(2)}) -- ({f(2)},{f(f(2))}) -- ({f(f(2))},{f(f(2))})
-- ({f(f(2))},{f(f(f(2)))}) -- ({f(f(f(2)))},{f(f(f(2)))}) -- ({f(f(f(2)))},{f(f(f(f(2))))}) -- ({f(f(f(f(2))))},{f(f(f(f(2))))}) -- ({f(f(f(f(2))))},-7);
\draw[red, ultra thick, -latex] (4,0) -- (4,{f(4)}) -- ({f(4)},{f(4)}) -- ({f(4)},{f(f(4))}) -- ({f(f(4))},{f(f(4))}) -- ({f(f(4))},9);
\node[above] at (2,0) {$x_1$};
\node[below] at (4,0) {$x_1$};
\end{tikzpicture}
If you cannot see the picture, you can copy-and-paste the latex code in http://35.164.211.156/tikz/tikzlive.html.

We can see that if we start to the right of the rightmost fix point, that the algorithm diverges because the slope is greater than 1.
And if we start where the slope is less than 1, we "almost" converge. Except that there is no fixpoint to converge to. So we diverge after all. (Sweating)

Can we see that only using a graph? :unsure:

 

[I like Serena]

Can we see that only using a graph?

The graphs are to help us understand what is happening and what the relevant edge cases are.
We know now that it matters for $a>0$ if we have 1, 2, or 3 fix points.
Note that if $a<0$, then $\phi$ is decreasing, which means we have exactly 1 fixpoint since $x\mapsto x$ is strictly increasing.

If we have 3 fix points (which implies $a>0$), can we prove that $|\phi'(x)|<1$ at the middle fixpoint?
If so, then we can apply the Lipschitz continuity criterion to an interval starting at the middle fixpoint and conclude that the sequence converges.

When do we have 2 fix points? Can we find at which value of $a$ that happens?
Can we apply the Lipschitz continuity criterion then and conclude convergence?

If $a<0$, then we have exactly 1 fixpoint.
What can we say about $\phi'(x)$ at the intersection point? Can we find when it is $-1$?