For which values of a can we solve it iteratively?

  • MHB
  • Thread starter mathmari
  • Start date
In summary: If we start to the left of the leftmost fix point, the algorithm diverges because the slope is greater than 1.And if we start where the
  • #1
mathmari
Gold Member
MHB
5,049
7
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:
 
Mathematics news on Phys.org
  • #2
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? 🤔
 
Last edited:
  • #3
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. 🤔
 
  • #4
Klaas van Aarsen said:
I believe that is the case for $-1<a\le\frac 1{27}$.

How did you find this interval? :unsure:
 
  • #5
mathmari said:
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? 🤔
 
  • #6
Klaas van Aarsen said:
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 😩😣
 
  • #7
mathmari said:
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:
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:
iterative_algorithm.png

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$. 🤔
 
Last edited:
  • #8
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:
 
  • #9
mathmari said:
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)
 
  • #10
Klaas van Aarsen said:
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:
 
  • #11
mathmari said:
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$? 🤔
 
Last edited:

FAQ: For which values of a can we solve it iteratively?

1. What is meant by "solving iteratively"?

Iterative solving refers to the process of finding a solution to a problem by repeatedly applying a set of steps, each time getting closer to the desired outcome. In this context, it means finding a numerical solution to a given equation or system of equations through a series of repeated calculations.

2. How do we determine the values of a that allow for iterative solving?

The values of a that allow for iterative solving depend on the specific equation or system of equations being solved. In general, the equation or system must be able to be rearranged into a form that can be iteratively solved, such as a linear or quadratic equation. Additionally, the values of a must not lead to any division by zero or other mathematical errors during the iterative process.

3. Can we always solve equations or systems of equations iteratively?

No, not all equations or systems of equations can be solved iteratively. Some equations may have complex solutions that cannot be found through iterative methods, while others may not have any real solutions at all. Additionally, some equations may have solutions that cannot be found through iterative methods due to the values of a leading to mathematical errors.

4. What are the advantages of solving equations or systems of equations iteratively?

Iterative solving can be advantageous because it allows for a numerical solution to be found even if an exact solution cannot be determined. It also allows for equations or systems of equations to be solved quickly and efficiently, often with the use of computer programs or algorithms.

5. Are there any limitations to solving equations or systems of equations iteratively?

Yes, there are limitations to solving equations or systems of equations iteratively. As mentioned before, not all equations can be solved in this manner. Additionally, iterative solving may not always provide an exact solution and may only provide an approximation. It also requires a good initial guess or starting point, which may not always be easy to determine.

Similar threads

Replies
1
Views
936
Replies
4
Views
836
Replies
4
Views
2K
Replies
1
Views
996
Replies
20
Views
2K
Replies
1
Views
942
Replies
1
Views
1K
Back
Top