1

The question I am trying to answer is stated as follows:

The iteration

$x_{n+1} = 2 - (1+c)x_n + cx_n^3$

will converge to $\alpha = 1$ for some values of $c$ (provided that $x_0$ is sufficiently close to $\alpha$). Find the values of $c$ for which this is true. For what values of $c$ will the convergence be quadratic?

In approaching this problem, I have assumed that it is some variant of Newton's method. A large part of this assumption comes from the fact that we are both using $x$ rather than $y$, and that convergence is assumed so long as our initial guess is "sufficiently close". At first, I tried exploring with other basic iterative methods that aren't root finding (such as Euler's method) with the consideration that perhaps $c$ represented some step size. Attempts at that had failed.

If I can show that this is some variant of Newton's method, I think that quadratic convergence would come automatically. However, that makes me think that that wouldn't be the case. If it was, why would they ask? In that case, it could be some other method with super-linear convergence, but gains quadratic convergence with stricter values of $c$. The last thing here that throws me off is, expanding the parenthesis, I get a leading term of $-x_n$. I'm not sure how to approach this either.

I appreciate any help or suggestions!

cnolte
  • 414
  • 1
    What about solving directly the question at hand, instead of trying to link it to "some variant of Newton's method", starting from $$x_{n+1}-1=r_n\cdot(x_n-1),\qquad r_n=cx_n(x_n+1)-1,$$ and studying the sequence $(r_n)$? – Did Jul 22 '16 at 16:34

2 Answers2

1

Since you're wondering whether $x_n\to1$ it may make things more transparent if you set $x_n=y_n+1$ and check whether $y_n\to0$ (just because "small" can be easier to see than "close to $1$"). You get $$y_{n+1}=(c-1)y_n+cy_n^2.$$

Now regardless of $c$, if $y_n$ is small enough then $cy_n^2$ is even smaller. When could you conclude that $(c-1)y_n$ is smaller than $y_n$?

Oops That's all wrong. I misread the original recurrence. So substitute $x_n=y_n+1$ into the actual recurrence. You get $$y_{n+1}=Ay_n+By_n^2+Cy_n^3,$$where $A$, $B$, and $C$ are certain constants depending on $c$. As above, if $y_n$ is small enough then the last two terms are even smaller, so you need to figure out what valuues of $c$ will make $Ay_n$ even smaller, given that $y_n$ is small.

David C. Ullrich
  • 89,985
  • I like the idea of rewriting it to show that $y_n$ will go to one, but I'm a little bit confused on your approach. I've tried separating my original problem into those pieces, splitting the $2$ into $1 + 1$ and designating the second half as $y_{n+1}$, but I am not able to derive what you have (did you mean to have $cy_n^3$?. I've also tried direct substitution, which was messy. As for your second statement, I'm not sure how to justify $y+{n+1} \rightarrow 0$. Certainly, for c = 1, the former term will be smaller. In fact, it's true for all values of $c \leq 2$, assuming $y_n > 0$. But I'm not – cnolte Jul 22 '16 at 17:08
  • sure how to tie this into the rest of my statement – cnolte Jul 22 '16 at 17:08
  • @burnmfburn Misread the question. See edit... – David C. Ullrich Jul 22 '16 at 17:21
  • ah, I see. When I had said it was messy, I meant in the context of trying to get it to fit what you had written above the edit. I was trying to factor something out of that to make it fit, and that was a disaster. Thank you for the edit – cnolte Jul 22 '16 at 17:26
  • @burnmfburn Fine - I removed the snarky remark from the answer. – David C. Ullrich Jul 22 '16 at 17:29
  • Not a problem - I really do appreciate the help, I just wanted to indicate that I had put forth the effort. I have that cubic exactly, and now the comment about choosing my value for $c$ is much clearer. Thank you again! – cnolte Jul 22 '16 at 17:35
1

As always with iterative systems $x_{n+1}=f(x_n)$ you get convergence around the fixed point $x_*$ if $|f'(x_*)|<1$. In this case, $$ f(x)=2-(1+c)x+cx^3\implies f'(x)=-(1+c)+3cx^2,\quad f'(1)=-1+2c $$ Thus for $c\in (0,1)$ you get a locally contractive iteration around $x_*=1$.

Lutz Lehmann
  • 126,666
  • This is is an interesting insight that I had never considered before. Do you know where I could find more information to verify this on my own? For example, I'm thinking in my problem statement, what if I had said that the method would converge to $\alpha = 2$? In this case, $|f'(2)| < 1$ when $c \in (0, \frac{2}{11} ) \subset (0,1)$. In using this contraction method, then, would it necessarily be assumed that I know $x_*$ in advance? Because in this previous example, I have an appropriate value of $c$ that can be shown to converge to two different values for $\alpha$. – cnolte Jul 24 '16 at 15:49
  • After doing some reading on my own, I realize that this is more or less a basic statement from introductory numerical (duh) for the Contraction Mapping/Fixed Point Theorem. That being said, I'm still not sure how to handle the issue that I brought up previously, but I will see what I can do to reconcile that on my own. Thank you again for your help – cnolte Jul 24 '16 at 16:25
  • 1
    $α=2$ would require that it was actually a fixed point. However, $2=f(2)=6c$ only works for $c=\frac13$. -- And yes, it is a basic statement about the stability of fixed points. – Lutz Lehmann Jul 24 '16 at 16:52