Source of the Problem
The Mathematics Research and Development Forum, which I frequently visit, once had a thread discussing the asymptotic solution of the following nonlinear difference equation: a_{n+1}=a_n+\frac{1}{a_n^2},\, a_1=1 The original thread can be found here. I benefited greatly from that discussion and learned many new techniques. The main idea was to cube both sides and set x_n=a_n^3, transforming it into an equivalent recurrence problem: x_{n+1}=x_n+3+\frac{3}{x_n}+\frac{1}{x_n^2},\,x_1=1 Then, through clever techniques, one can obtain an asymptotic expansion: x_n = 3n+\ln n+a+\frac{\frac{1}{3}(\ln n+a)-\frac{5}{18}}{n}+\dots I will not detail the specific process here; readers can study the aforementioned thread on their own.
However, while this form of solution is exquisite, there are several aspects I find somewhat unsatisfactory:
1. The solution is an asymptotic series, which implies that the radius of convergence is actually 0;
2. It is a solution in the form of n^{-k}, making it difficult to calculate for small n, which complicates high-precision computation;
3. Of course, the original purpose was asymptotic calculation, but asymptotic analysis does not seem to necessitate expanding so many terms;
4. It contains a constant a that is inherently difficult to calculate;
5. The derivation process seems slightly less than intuitive.
Admittedly, some of these criticisms are nitpicking. However, it was precisely these shortcomings that prompted me to search for a better form of solution, which ultimately led to this article.
Implicit Solution
The first-order asymptotic solution for the recurrence x_{n+1}=x_n+3+\frac{3}{x_n}+\frac{1}{x_n^2},\,x_1=1 is obtained by neglecting the terms \frac{3}{x_n}+\frac{1}{x_n^2}, resulting in x_{n+1}=x_n+3, so x_n=3n-2.
There are many subsequent approaches, such as iteration or undetermined coefficients, to find asymptotic solutions. However, I tried another path: seeking an implicit solution. First, let us consider: x_{n+1}+f(x_{n+1})=x_n+3+\frac{3}{x_n}+\frac{1}{x_n^2}+f\left(x_n+3+\frac{3}{x_n}+\frac{1}{x_n^2}\right) Expanding the last term to the first order at x_n: x_{n+1}+f(x_{n+1})=x_n+3+\frac{3}{x_n}+\frac{1}{x_n^2}+f(x_n)+f'(x_n)\left(3+\frac{3}{x_n}+\frac{1}{x_n^2}\right) Taking 1/x_n as the order and neglecting second-order terms, we get: x_{n+1}+f(x_{n+1})=x_n+f(x_n)+3+3\left[\frac{1}{x_n}+f'(x_n)\right] If we let f(x_n)=-\ln x_n, then the term in the square brackets becomes zero, thus yielding: x_{n+1}-\ln x_{n+1}=x_n-\ln x_n+3 The accuracy of this equality is \mathcal{O}(x_n^{-2}). To balance simplicity and accuracy, it is better to start from x_2=8, so: x_n - \ln x_n = 3(n-2)+8-\ln 8 This is an implicit (approximate) solution with an accuracy of \mathcal{O}(x_n^{-1}). It maintains nearly the same accuracy for almost all n. The key point here is to introduce new terms so that it becomes a linear recurrence (an arithmetic progression). This process can be continued. By introducing new functions based on the previous step and expanding to the second order, we calculate: x_{n+1}-\ln x_{n+1}+\frac{5}{6x_{n+1}}=x_n-\ln x_n+\frac{5}{6x_n}+3 This has an accuracy of \mathcal{O}(x_n^{-3}), from which an implicit solution with an accuracy of \mathcal{O}(x_n^{-2}) can be solved.
Why Implicit Solutions?
Why look for implicit solutions? There are several benefits.
Generally, traditional asymptotic solutions are obtained through Taylor series expansions. Taylor expansions themselves have limitations (requiring differentiability and finite derivatives), so asymptotic solutions often arise where the radius of convergence might be small even if they don’t diverge. Implicit solutions, however, are usually more stable and have better convergence properties. Although they might still be asymptotic, the rate of divergence is significantly reduced. For example, x=\sqrt{1+t} expanded as a power series has a radius of convergence of only 1, but it can be expressed in implicit form as x^2-1=t, which maintains both accuracy and simplicity.
In short, if an explicit expansion can do it, an implicit function can generally do it too; and if an explicit expansion cannot do it, an implicit function might still be able to. Therefore, implicit functions clearly offer better performance.
Furthermore, for the recurrence in this article, the implicit solution is more concise and does not involve the difficult-to-calculate constant a everywhere. Readers might feel that solving a nonlinear equation every time x_n is needed is complicated. In fact, if desired, one can directly obtain an explicit solution from the implicit solution by finding the inverse function, but this leads back to asymptotic series, which is somewhat unnecessary.
Recursive Format for Programming
The two terms calculated earlier were merely introductory demonstrations. Since the order was low, the calculation was not difficult. However, to proceed further, especially for programmed computation, it is necessary to construct a recursive format that is easy to understand, much like the recursive calculations in perturbation methods.
Assuming the introduced f(x_n) is exact, then clearly, for an exact f(x), it must satisfy: \frac{3}{x}+\frac{1}{x^2}+f\left(x+3+\frac{3}{x}+\frac{1}{x^2}\right)-f(x)=0 In this case, the original recurrence becomes: x_{n+1}+f(x_{n+1})=x_{n}+f(x_{n})+3 Solving this is much easier.
Through analysis, we can manually introduce a parameter q and treat f(x) as a function of two variables f(x,q). We solve for the series solution of f(x,q) and then let q=1 to obtain f(x)=f(x,1). The introduced format is as follows: \frac{3q}{x}+\frac{q^2}{x^2}+f\left(x+3q+\frac{3q^2}{x}+\frac{q^3}{x^2},q\right)-f(x,q)=0 The logic for introducing it this way is: using x^{-1} as the infinitesimal order, and letting f^{(n)}(x) also have the order x^{-n}. Thus, inside f(), x^{-n} \to q^{n+1}x^{-n}, and outside f(), x^{-n} \to q^n x^{-n}. At this point, software like Mathematica can be used to expand it quickly:
Series[f[x + 3*q + 3*q^2/x + q^3/x^2, q] - f[x, q] + 3*q/x + q^2/x^2, {q, 0, 5}]The result is: \begin{aligned}&q \left(3 f^{(1,0)}(x,0)+\frac{3}{x}\right)\\ +&q^2 \left(\frac{3 f^{(1,0)}(x,0)}{x}+3 f^{(1,1)}(x,0)+\frac{9}{2} f^{(2,0)}(x,0)+\frac{1}{x^2}\right)\\ +&q^3 \left(\frac{f^{(1,0)}(x,0)}{x^2}+\frac{3 f^{(1,1)}(x,0)}{x}+\frac{3}{2} f^{(1,2)}(x,0)\right.\\ &\qquad\qquad\left.+\frac{9 f^{(2,0)}(x,0)}{x}+\frac{9}{2} f^{(2,1)}(x,0)+\frac{9}{2} f^{(3,0)}(x,0)\right)\\ +&\dots \end{aligned} Setting the coefficients of each order of q to zero, we successively solve: \begin{aligned}&f^{(0,0)}(x,0)=-\ln x\\ &f^{(0,1)}(x,0)=\frac{5}{6x}\\ &f^{(0,2)}(x,0)=\frac{4}{3 x^2}\\ &\dots \end{aligned} Therefore: f(x)=f(x,1)=-\ln x+\frac{5}{6x}+\frac{2}{3 x^2}+\dots Which means: \begin{aligned}&x_{n+1}-\ln x_{n+1}+\frac{5}{6x_{n+1}}+\frac{2}{3 x_{n+1}^2}\\ =&x_{n}-\ln x_{n}+\frac{5}{6x_{n}}+\frac{2}{3 x_{n}^2}+3\end{aligned} Resulting in: \begin{aligned}&x_{n}-\ln x_{n}+\frac{5}{6x_{n}}+\frac{2}{3 x_{n}^2}\\ =&3(n-2)+8-\ln 8+\frac{5}{6\times 8}+\frac{2}{3\times 8^2}\end{aligned} This has an accuracy of \mathcal{O}(x_n^{-3}).
By slightly modifying the approach, an automatic calculation program can be written in Mathematica:
g[x_] = 0;
ff[x_] = 3*1/x + 1/x^2
Do[e = q^n;
g[x_] = g[x] +
q^n*Integrate[-D[
f[x + 3*q*e + ff[x/q]*e*q, q] - f[x, q] +
g[x + 3*q + ff[x/q]*q] - g[x] + ff[x/q], {q,
n + 1}] /. {q -> 0, f -> 0} // Simplify, x]/
3/(n + 1)!;, {n, 0, 5}]
h[x_] = g[x] /. {q -> 1} // ExpandBy modifying the 5 in {n, 0, 5}, the precision can be
increased or decreased. The code above gives: f(x)=-\ln x+\frac{5}{6 x}+\frac{2}{3
x^2}+\frac{77}{108 x^3}+\frac{133}{240 x^4}-\frac{2669}{5400 x^5} +
\dots
Asymptotic Results and Limit Values
At this point, we have solved: x_n+f(x_n)=3(n-k)+x_k+f(x_k),\,\text{given } x_k \text{ as the initial value} Let a=x_k+f(x_k)-3k+\ln 3 We get: x_n + f(x_n)=3n+a-\ln 3 If one wishes to obtain an explicit asymptotic expression, an iterative formula can be constructed based on the above equation: x^{(k+1)}_n=3n+a-\ln 3 -f(x^{(k)}_n) Where x^{(k)}_n refers to the k-th level approximation of x_n. Using x^{(0)}_n=3n+a-\ln 3 as the initial value for iteration and expanding, we get: \begin{aligned}x_n=&3n+a+\ln n+\frac{6 a+6 \ln n-5}{18 n}+\\ &\frac{-3 a^2-6 a \ln n+11 a-3 \ln ^2 n+11 \ln n-9}{54 n^2}+\dots\end{aligned} This is identical to the asymptotic formula given by mathe on the research forum.
The Mathematica code for the iteration is (continued from before):
p[n_] = 3*n + a - Log[3];
Do[p[n_] =
Normal[Series[-h[p[n]] + 3*n + a - Log[3], {n, Infinity, 5}]], {i,
0, 5}]
Series[p[n], {n, Infinity, 5}]From this, we discover that the a here is exactly the limit value a: a=\lim_{n\to\infty} (x_n - 3n - \ln n) This also simultaneously provides an asymptotic expression for calculating a: x_k+f(x_k)-3k+\ln 3 Using the value of x_{10^9} calculated by wayne and substituting it into the above formula, we calculate: a=1.1352558473155037141953943477479\dots
Original Address: https://kexue.fm/archives/3696
For more details on reprinting, please refer to: Scientific Space FAQ