递推方程增长阶：求解给定递推序列的收敛速率
Hey there, let's break down this recurrence relation to figure out how the sequence $x_t$ behaves as $t$ grows. I'll walk through each case step by step so it's clear.
First, let's restate the problem to make sure we're aligned:
For $t \geq 2$, the sequence follows:
$$x_t = c_1\left(-\frac{1}{x_{t-1}} + \sqrt{\frac{1}{x_{t-1}^2} + c_2}\right)$$
with initial value $x_1 = c_3$, where $c_1, c_2, c_3 > 0$ are positive constants.
Step 1: Simplify the Recurrence (Rationalization Trick)
The square root makes the recurrence look messy, so let's rationalize the expression inside the parentheses. Multiply the numerator and denominator by the conjugate term $\frac{1}{x_{t-1}} + \sqrt{\frac{1}{x_{t-1}^2} + c_2}$:
$$x_t = c_1 \cdot \frac{\left(-\frac{1}{x_{t-1}} + \sqrt{\frac{1}{x_{t-1}^2} + c_2}\right)\left(\frac{1}{x_{t-1}} + \sqrt{\frac{1}{x_{t-1}^2} + c_2}\right)}{\frac{1}{x_{t-1}} + \sqrt{\frac{1}{x_{t-1}^2} + c_2}}$$
Using the difference of squares $(a-b)(a+b)=a2-b2$, the numerator simplifies to just $c_2$. This gives us a way cleaner recurrence:
$$x_t = \frac{c_1 c_2 x_{t-1}}{1 + \sqrt{1 + c_2 x_{t-1}^2}}$$
Way better to work with!
Step 2: Fixed Point & Convergence Cases
We'll split this into three cases based on the product $c_1 c_2$, since that's the key parameter driving behavior.
Case 1: $c_1 c_2 > 2$ (Positive Fixed Point Exists)
First, let's find the steady-state value $x^$ where $x_t = x_{t-1} = x^$. Plugging into the simplified recurrence and dividing both sides by $x^$ (since it's positive):
$$1 = \frac{c_1 c_2}{1 + \sqrt{1 + c_2 (x*)2}}$$
Rearranging and squaring both sides (valid because $c_1 c_2 >2$ makes the right-hand side positive), we solve for $x^$:
$$x^* = \sqrt{c_1(c_1 c_2 - 2)}$$
To find the convergence rate, we look at the derivative of the recurrence function $f(z) = \frac{c_1 c_2 z}{1 + \sqrt{1 + c_2 z^2}}$ at $x^$. After computing the derivative (using quotient rule and substituting our fixed point values), we get:
$$f'(x^) = \frac{1}{c_1 c_2 - 1}$$
Since $c_1 c_2 >2$, this derivative is between 0 and 1. That means the sequence converges linearly to $x^$: the error $e_t = x_t - x^$ shrinks geometrically by a factor of $\frac{1}{c_1 c_2 -1}$ each step (so $e_t \sim K \cdot \left(\frac{1}{c_1 c_2 -1}\right)^t$ for some constant $K$ as $t \to \infty$).
Case 2: $c_1 c_2 = 2$ (Boundary Case)
Here, the fixed point equation leads to $x^* =0$. To find the decay rate, let's substitute $y_t = \frac{1}{x_t}$ (since $x_t$ stays positive). The recurrence becomes:
$$y_t = \frac{y_{t-1} + \sqrt{y_{t-1}^2 + c_2}}{2}$$
This is an increasing sequence (since $\sqrt{y_{t-1}^2 + c_2} > y_{t-1}$). For large $y_{t-1}$, we can approximate the square root with a Taylor expansion: $\sqrt{y_{t-1}^2 + c_2} \approx y_{t-1} + \frac{c_2}{2 y_{t-1}}$. Plugging this in gives:
$$y_t \approx y_{t-1} + \frac{c_2}{4 y_{t-1}}$$
Treating this as a differential equation (for continuous approximation), we solve to find $y_t \sim \sqrt{\frac{c_2}{2} t}$. Translating back to $x_t$, this means $x_t = \frac{1}{y_t} = O\left(\frac{1}{\sqrt{t}}\right)$. So the sequence decays to 0 at a polynomial rate of $1/\sqrt{t}$.
Case 3: $0 < c_1 c_2 < 2$ (No Positive Fixed Point)
Again, use the $y_t = \frac{1}{x_t}$ substitution. The recurrence becomes:
$$y_t = \frac{y_{t-1} + \sqrt{y_{t-1}^2 + c_2}}{c_1 c_2}$$
For large $y_{t-1}$, the square root approximates to $y_{t-1} + \frac{c_2}{2 y_{t-1}}$, so:
$$y_t \approx \frac{2 y_{t-1}}{c_1 c_2}$$
Since $\frac{2}{c_1 c_2} >1$ (because $c_1 c_2 <2$), $y_t$ grows exponentially. This means $x_t = \frac{1}{y_t}$ decays exponentially to 0, with a decay rate of $\frac{c_1 c_2}{2}$ (so $x_t \sim K' \cdot \left(\frac{c_1 c_2}{2}\right)^t$ for some constant $K'$).
Quick Summary
- $c_1 c_2 >2$: Converges linearly to $x^* = \sqrt{c_1(c_1 c_2 -2)}$, error shrinks by $\frac{1}{c_1 c_2 -1}$ each step.
- $c_1 c_2 =2$: Decays to 0 at polynomial rate $O(1/\sqrt{t})$.
- $0 < c_1 c_2 <2$: Decays to 0 exponentially, with rate $\frac{c_1 c_2}{2}$.
内容的提问来源于stack exchange，提问作者user52705
