定義:對於1個給定的函數
f
(
x
)
{\displaystyle f(x)}
,能使
f
(
x
)
=
x
{\displaystyle f(x)=x}
成立的自變量取值
x
=
x
0
{\displaystyle x=x_{0}}
叫做該函數的不動點(fixed point) 。[ 1] [ 2]
與遞推式形式一致的函數也被叫做遞推關係式的特徵函數 (characteristic function )或背景函數 [ 1] 。遞推式特徵函數的不動點也叫做遞推式的不動點。不動點在對應函數圖象上的對應點也叫做函數圖象的不動點 [ 2] 。
在解決高中數列遞推問題時,我們討論的不動點都是可逆函數的不動點。可逆函數的不動點有以下特點:
如果
(
x
0
,
y
0
)
{\displaystyle (x_{0},y_{0})}
是可逆函數
y
=
f
(
x
)
{\displaystyle y=f(x)}
的不動點,等價於
(
y
0
,
x
0
)
{\displaystyle (y_{0},x_{0})}
是其反函數
x
=
f
−
1
(
y
)
{\displaystyle x=f^{-1}(y)}
的不動點。換句話說,可逆函數的不動點與其反函數的不動點是一一對應的。
函數的不動點坐標具有
(
x
0
,
x
0
)
{\displaystyle (x_{0},x_{0})}
的形式,即不動點一定是函數圖象與特殊直線
y
=
x
{\displaystyle y=x}
的交點。
如果把可逆函數
y
=
f
(
x
)
{\displaystyle y=f(x)}
與其反函數
x
=
f
−
1
(
y
)
{\displaystyle x=f^{-1}(y)}
的圖象畫在同一個直角坐標系中,則它們的圖象交點都是不動點。
不動點本身是拓撲學 的知識點,表示物體或空間在某種拓撲變換的作用下,仍保持固定不動的點。它的幾何意義是函數圖象與恆等變換直線
y
=
x
{\displaystyle y=x}
交點的橫坐標。但是它也出現在有關數列的解題方法中。
利用不動點簡化一階常係數線性遞推關係式的通項求解
編輯
在從遞推式
a
n
+
1
=
p
a
n
+
q
(
p
≠
1
)
{\displaystyle a_{n+1}=pa_{n}+q\quad (p\neq 1)}
構造等比數列的過程中,使用待定係數法所求的需要分配到等式兩邊的數值,剛好就可以用對應函數
f
(
x
)
=
p
x
+
q
{\displaystyle f(x)=px+q}
的不動點來確定。我們先給出用不動點法解決這類數列的通用解題步驟,然後結合例題說明它的具體運用。
用不動點法可以求出一階線性遞推數列
a
n
+
1
=
p
a
n
+
q
{\displaystyle a_{n+1}=pa_{n}+q}
(其中p和q為常數,且
p
≠
1
{\displaystyle p\neq 1}
)的通項的一般式[ 3] 。其主要步驟為:
(1) 寫出與
a
n
+
1
=
p
a
n
+
q
{\displaystyle a_{n+1}=pa_{n}+q}
對應的特徵函數
f
(
x
)
=
p
x
+
q
{\displaystyle f(x)=px+q}
(2) 求出函數
f
(
x
)
{\displaystyle f(x)}
的不動點
x
0
{\displaystyle x_{0}}
,即求解方程
f
(
x
0
)
=
x
0
⇒
p
x
0
+
q
=
x
0
{\displaystyle f(x_{0})=x_{0}\Rightarrow px_{0}+q=x_{0}}
,解得:
x
0
=
q
1
−
p
{\displaystyle x_{0}={\frac {q}{1-p}}}
(3) 在原始
a
n
+
1
=
p
a
n
+
q
{\displaystyle a_{n+1}=pa_{n}+q}
的等號兩邊同時減去剛才求出的不動點
x
0
{\displaystyle x_{0}}
,即:
a
n
+
1
−
x
0
=
p
a
n
+
q
−
x
0
⇒
a
n
+
1
−
x
0
=
p
(
a
n
+
q
−
x
0
p
)
⇒
a
n
+
1
−
x
0
=
p
(
a
n
−
x
0
)
{\displaystyle a_{n+1}-x_{0}=pa_{n}+q-x_{0}\quad \Rightarrow \quad a_{n+1}-x_{0}=p(a_{n}+{\frac {q-x_{0}}{p}})\quad \Rightarrow \quad a_{n+1}-x_{0}=p(a_{n}-x_{0})}
(4) 將
a
n
−
x
0
{\displaystyle a_{n}-x_{0}}
整體地看作一個等比數列求解,求出
a
n
−
x
0
{\displaystyle a_{n}-x_{0}}
的表達式後,
a
n
{\displaystyle a_{n}}
的表達式自然也就知道了。
可以證明,這樣求得的最終結果形式為
a
n
=
a
1
p
n
−
1
+
q
(
1
−
p
n
−
1
)
1
−
p
{\displaystyle a_{n}=a_{1}p^{n-1}+{\frac {q(1-p^{n-1})}{1-p}}}
[ 3] 。但是實際上,解題時並不需要記住這個最終形式,只需要記住上面的幾個關鍵步驟即可。
提示:如果求出的不動點形式比較複雜(例如算出的解帶着根號跑),此時使用不動點法對於簡化數列構造時的係數運算也無法提供太多幫助。求解兔子數列的通項公式問題就是一個例子。
關於在一階常係數線性遞推關係式的通項求解中,為什麼會與不動點的概念產生聯繫,我們在這裡給予一個比較簡單的論證。
先設
a
n
+
1
=
k
a
n
+
d
{\displaystyle a_{n+1}=ka_{n}+d}
再假設我們期待的構造好的等比數列形式
a
n
+
1
−
p
=
k
(
a
n
−
p
)
{\displaystyle a_{n+1}-p=k(a_{n}-p)}
用後一式的兩端同時對前一式的兩端作差,可得:
(
a
n
+
1
−
p
)
−
a
n
+
1
=
k
(
a
n
−
p
)
−
(
k
a
n
+
d
)
⇒
−
p
=
−
k
p
−
d
⇒
p
=
k
p
+
d
{\displaystyle {\begin{array}{l}(a_{n+1}-p)-a_{n+1}=k(a_{n}-p)-(ka_{n}+d)\\\Rightarrow -p=-kp-d\quad \Rightarrow \quad p=kp+d\end{array}}}
最後一個式子顯然說明所需要的常數p就是函數
f
(
x
)
=
k
x
+
d
{\displaystyle f(x)=kx+d}
的不動點。
從幾何上講,從截距不為零的一次函數(對應於上述非齊次一階線性遞推關係式)變形為正比例函數(對應於構造出來的等比數列滿足的關係式)的變換就是一種圖象平移操作,而此類函數的不動點提供了同時沿y軸方向和x軸方向進行圖象平移的距離參考值。
一階常係數分式線性遞推關係式的概念及其通項的待定係數解法
編輯
形如
a
n
+
1
=
A
a
n
+
B
C
a
n
+
D
{\displaystyle a_{n+1}={\frac {Aa_{n}+B}{Ca_{n}+D}}}
的一階常係數分式線性遞推關係式的構造也可以藉助不動點的求解實現[ 2] 。
提示:我們先在本小節簡述如何使用待定係數法求這類分式線性遞推式通項的大體思路,再在後面的小節介紹基於不動點法的優化和解題實例,最後談談在這類情形下可以使用不動點法的原理。
定義:具有以下形式的遞推式
a
n
+
1
=
f
(
a
n
)
{\displaystyle a_{n+1}=f(a_{n})}
叫做常係數分式線性遞推關係 :
a
n
+
1
=
A
a
n
+
B
C
a
n
+
D
(
n
∈
N
+
,
A
,
B
,
C
,
D
∈
R
,
A
D
−
B
C
≠
0
)
{\displaystyle a_{n+1}={\frac {Aa_{n}+B}{Ca_{n}+D}}\quad (n\in \mathbb {N} ^{+},A,B,C,D\in \mathbb {R} ,AD-BC\neq 0)}
利用不動點簡化一階常係數分式線性遞推關係式的通項求解
編輯
我們接下來從不動點的角度,指出這種常係數分式線性遞推關係的通項公式求解方法。
提示:本小節前半部分展示的代數變形過程比較冗長羅嗦,主要就是講述了2種情況下最基本的分類討論,外加上常見優化步驟的思路由來。沒有耐心的讀者可以先看結論和具體例題,然後有時間再回過頭來大致瀏覽一下這些純字母化的運算和論證。
設函數
f
(
x
)
=
A
x
+
B
C
x
+
D
{\displaystyle f(x)={\frac {Ax+B}{Cx+D}}}
滿足
x
,
A
,
B
,
C
,
D
∈
C
,
A
D
−
B
C
≠
0
{\displaystyle x,A,B,C,D\in \mathbb {C} ,AD-BC\neq 0}
,其不動點為
x
=
λ
{\displaystyle x=\lambda }
。
其不動點滿足的方程
λ
=
A
λ
+
B
C
λ
+
D
{\displaystyle \lambda ={\frac {A\lambda +B}{C\lambda +D}}}
可能只有1個解,也可能有2個不同的解(不同的實數根或不同的虛數根)[ 4] 。
如果
x
0
{\displaystyle x_{0}}
為以上方程的任何一個根(從而
x
0
{\displaystyle x_{0}}
也是函數的不動點),那麼可以先對原遞推式兩邊同時減去不動點:
a
n
+
1
−
x
0
=
A
a
n
+
B
C
a
n
+
D
−
x
0
=
(
A
−
C
x
0
)
(
a
n
−
x
0
)
C
a
n
+
D
{\displaystyle a_{n+1}-x_{0}={\frac {Aa_{n}+B}{Ca_{n}+D}}-x_{0}={\frac {(A-Cx_{0})(a_{n}-x_{0})}{Ca_{n}+D}}}
再對上式兩側同時顛倒可得:
1
a
n
+
1
−
x
0
=
C
a
n
+
D
(
A
−
C
x
0
)
(
a
n
−
x
0
)
=
C
x
0
+
D
A
−
C
x
0
1
a
n
−
x
0
+
C
A
−
C
x
0
{\displaystyle {\frac {1}{a_{n+1}-x_{0}}}={\frac {Ca_{n}+D}{(A-Cx_{0})(a_{n}-x_{0})}}={\frac {Cx_{0}+D}{A-Cx_{0}}}{\frac {1}{a_{n}-x_{0}}}+{\frac {C}{A-Cx_{0}}}}
由上式可知此時
{
1
a
n
−
x
0
}
{\displaystyle \{{\frac {1}{a_{n}-x_{0}}}\}}
整體來說是一個一階常係數線性遞推數列,且包含有取值為常數的非齊次項。
如果不動點方程
λ
=
A
λ
+
B
C
λ
+
D
{\displaystyle \lambda ={\frac {A\lambda +B}{C\lambda +D}}}
的2個根是重根,則有
x
1
=
x
2
=
A
−
D
2
C
{\displaystyle x_{1}=x_{2}={\frac {A-D}{2C}}}
且
C
x
1
+
D
A
−
C
x
1
=
1
{\displaystyle {\frac {Cx_{1}+D}{A-Cx_{1}}}=1}
。此時可以繼續化簡:
1
a
n
+
1
−
x
0
=
C
x
0
+
D
A
−
C
x
0
1
a
n
−
x
0
+
C
A
−
C
x
0
=
1
a
n
−
x
0
+
C
A
−
C
x
0
{\displaystyle {\frac {1}{a_{n+1}-x_{0}}}={\frac {Cx_{0}+D}{A-Cx_{0}}}{\frac {1}{a_{n}-x_{0}}}+{\frac {C}{A-Cx_{0}}}={\frac {1}{a_{n}-x_{0}}}+{\frac {C}{A-Cx_{0}}}}
即
{
1
a
n
−
x
0
}
{\displaystyle \{{\frac {1}{a_{n}-x_{0}}}\}}
變為以
1
a
1
−
x
0
{\displaystyle {\frac {1}{a_{1}-x_{0}}}}
為首項、
C
A
−
C
x
0
{\displaystyle {\frac {C}{A-Cx_{0}}}}
為公差的等差數列,易知其通項為:
1
a
n
−
x
0
=
1
a
1
−
x
0
+
2
C
(
n
−
1
)
A
+
D
{\displaystyle {\frac {1}{a_{n}-x_{0}}}={\frac {1}{a_{1}-x_{0}}}+{\frac {2C(n-1)}{A+D}}}
既然在這種情形下都已經得到
1
a
n
−
x
0
{\displaystyle {\frac {1}{a_{n}-x_{0}}}}
的解析式,從而
a
n
{\displaystyle a_{n}}
的解析式也容易知道了。
如果不動點方程
λ
=
A
λ
+
B
C
λ
+
D
{\displaystyle \lambda ={\frac {A\lambda +B}{C\lambda +D}}}
有2個相異的根,那麼最直接的想法是只能麻煩一點,針對得到的常係數線性遞推式再使用不動點法構造一次:
1
a
n
+
1
−
x
1
+
1
x
1
−
x
2
=
A
−
C
x
1
A
−
C
x
2
(
1
a
n
−
x
1
+
1
x
1
−
x
2
)
{\displaystyle {\frac {1}{a_{n+1}-x_{1}}}+{\frac {1}{x_{1}-x_{2}}}={\frac {A-Cx_{1}}{A-Cx_{2}}}({\frac {1}{a_{n}-x_{1}}}+{\frac {1}{x_{1}-x_{2}}})}
此時
{
1
a
n
−
x
1
+
1
x
1
−
x
2
}
{\displaystyle \{{\frac {1}{a_{n}-x_{1}}}+{\frac {1}{x_{1}-x_{2}}}\}}
構成公比為
A
−
C
x
1
A
−
C
x
2
{\displaystyle {\frac {A-Cx_{1}}{A-Cx_{2}}}}
的等比數列,即:
1
a
n
−
x
1
+
1
x
1
−
x
2
=
(
1
a
n
−
x
1
+
1
x
1
−
x
2
)
(
A
−
C
x
1
A
−
C
x
2
)
n
−
1
⇒
1
a
n
−
x
1
=
(
1
a
n
−
x
1
+
1
x
1
−
x
2
)
(
A
−
C
x
1
A
−
C
x
2
)
n
−
1
−
1
x
1
−
x
2
⇒
a
n
=
x
2
(
a
1
−
x
1
)
(
A
−
C
x
1
)
n
−
1
−
x
1
(
a
1
−
x
2
)
(
A
−
C
x
2
)
n
−
1
(
a
1
−
x
1
)
(
A
−
C
x
1
)
n
−
1
−
(
a
1
−
x
2
)
(
A
−
C
x
2
)
n
−
1
{\displaystyle {\begin{aligned}{\frac {1}{a_{n}-x_{1}}}+{\frac {1}{x_{1}-x_{2}}}=({\frac {1}{a_{n}-x_{1}}}+{\frac {1}{x_{1}-x_{2}}})({\frac {A-Cx_{1}}{A-Cx_{2}}})^{n-1}\\\Rightarrow {\frac {1}{a_{n}-x_{1}}}=({\frac {1}{a_{n}-x_{1}}}+{\frac {1}{x_{1}-x_{2}}})({\frac {A-Cx_{1}}{A-Cx_{2}}})^{n-1}-{\frac {1}{x_{1}-x_{2}}}\\\Rightarrow a_{n}={\frac {x_{2}(a_{1}-x_{1})(A-Cx_{1})^{n-1}-x_{1}(a_{1}-x_{2})(A-Cx_{2})^{n-1}}{(a_{1}-x_{1})(A-Cx_{1})^{n-1}-(a_{1}-x_{2})(A-Cx_{2})^{n-1}}}\end{aligned}}}
如果方程有2個不等的根
x
1
{\displaystyle x_{1}}
和
x
2
{\displaystyle x_{2}}
(是不同的實數根或不同的虛數根都行),此時還有一種基於不動點但是構造方向與上述思路有一些差異的解法。先在原遞推式的兩側分別減去這2個根,可以得到:
{
a
n
+
1
−
x
1
=
(
A
−
C
x
1
)
(
a
n
−
x
1
)
C
a
n
+
D
a
n
+
1
−
x
2
=
(
A
−
C
x
2
)
(
a
n
−
x
2
)
C
a
n
+
D
{\displaystyle \left\{{\begin{array}{l}a_{n+1}-x_{1}={\frac {(A-Cx_{1})(a_{n}-x_{1})}{Ca_{n}+D}}\\a_{n+1}-x_{2}={\frac {(A-Cx_{2})(a_{n}-x_{2})}{Ca_{n}+D}}\end{array}}\right.}
如果觀察上述2個式子,可以發現它們的右側都有相同的分母,且右側的分子形式非常相似,最好能利用這個相同點去掉它們的分母。於是不妨對上述2個式子的兩端同時作商(相除)可得:
a
n
+
1
−
x
1
a
n
+
1
−
x
2
=
k
a
n
−
x
1
a
n
−
x
2
{\displaystyle {\frac {a_{n+1}-x_{1}}{a_{n+1}-x_{2}}}=k{\frac {a_{n}-x_{1}}{a_{n}-x_{2}}}}
,其中
k
=
A
−
C
x
1
A
−
C
x
2
{\displaystyle k={\frac {A-Cx_{1}}{A-Cx_{2}}}}
。
易知此時
{
a
n
−
x
1
a
n
−
x
2
}
{\displaystyle \{{\frac {a_{n}-x_{1}}{a_{n}-x_{2}}}\}}
整體來說是一個以
a
1
−
x
1
a
1
−
x
2
{\displaystyle {\frac {a_{1}-x_{1}}{a_{1}-x_{2}}}}
為首項、k為公比的等比數列,所以得到
{
a
n
−
x
1
a
n
−
x
2
}
{\displaystyle \{{\frac {a_{n}-x_{1}}{a_{n}-x_{2}}}\}}
的通項公式:
a
n
−
x
1
a
n
−
x
2
=
a
1
−
x
1
a
1
−
x
2
k
n
−
1
=
(
A
−
C
x
1
A
−
C
x
2
)
n
−
1
a
1
−
x
1
a
1
−
x
2
{\displaystyle {\frac {a_{n}-x_{1}}{a_{n}-x_{2}}}={\frac {a_{1}-x_{1}}{a_{1}-x_{2}}}k^{n-1}=({\frac {A-Cx_{1}}{A-Cx_{2}}})^{n-1}{\frac {a_{1}-x_{1}}{a_{1}-x_{2}}}}
既然已經得到
a
n
−
x
1
a
n
−
x
2
{\displaystyle {\frac {a_{n}-x_{1}}{a_{n}-x_{2}}}}
的解析式,從而
a
n
{\displaystyle a_{n}}
的解析式也容易知道了。
這種方法此時可以更快地得到同樣的最終結果:
a
n
=
x
2
(
a
1
−
x
1
)
(
A
−
C
x
1
)
n
−
1
−
x
1
(
a
1
−
x
2
)
(
A
−
C
x
2
)
n
−
1
(
a
1
−
x
1
)
(
A
−
C
x
1
)
n
−
1
−
(
a
1
−
x
2
)
(
A
−
C
x
2
)
n
−
1
{\displaystyle a_{n}={\frac {x_{2}(a_{1}-x_{1})(A-Cx_{1})^{n-1}-x_{1}(a_{1}-x_{2})(A-Cx_{2})^{n-1}}{(a_{1}-x_{1})(A-Cx_{1})^{n-1}-(a_{1}-x_{2})(A-Cx_{2})^{n-1}}}}
綜上所述,我們可以將常係數分式線性遞推式的通項求解思路簡化如下[ 5] :
當只有1個不動點時,可以對原遞推式的兩邊同時減去不動點,然後再同時取倒數,進而轉化為等差數列求解。
當有2個相異的不動點時,可以先對原遞推式的兩邊同時減去第1個不動點並取倒數,再對原遞推式的兩邊同時減去第2個不動點並取倒數,然後將分別得到的2個式子作商,進而轉化為等比數列求解。
分式線性變換的概念與分式線性遞推式的不動點解法由來
編輯
定義:具有以下形式的函數
f
:
C
→
C
{\displaystyle f:\mathbb {C} \rightarrow \mathbb {C} }
叫做分式線性變換 (linear fractional transformation ):
f
(
x
)
=
A
x
+
B
C
x
+
D
(
A
,
B
,
C
,
D
∈
C
,
A
D
−
B
C
≠
0
)
{\displaystyle f(x)={\frac {Ax+B}{Cx+D}}\quad (A,B,C,D\in \mathbb {C} ,AD-BC\neq 0)}
因為德國數學家奧古斯特·莫比烏斯 曾對其進行過大量研究,所以分式線性變換也叫做莫比烏斯變換 (Möbius transformation )。[ 4]
通過簡單的分式分解,易知莫比烏斯函數可以分解為以下形式:
f
(
x
)
=
B
C
−
A
D
C
1
C
x
+
D
+
A
C
{\displaystyle f(x)={\frac {BC-AD}{C}}{\frac {1}{Cx+D}}+{\frac {A}{C}}}
由於我們只考慮自變量值取實數的情形,因此可以對於特定的一組係數可以畫出函數的圖像。而由上述表達式的圖象性質可知,分式線性變換是可逆的。
容易驗證以下性質:
分式線性變換
f
(
x
)
=
A
x
+
B
C
x
+
D
(
A
D
−
B
C
≠
0
)
{\displaystyle f(x)={\frac {Ax+B}{Cx+D}}\quad (AD-BC\neq 0)}
的逆變換(即反函數)為[ 4] :
x
=
−
D
y
+
B
C
y
−
A
{\displaystyle x={\frac {-Dy+B}{Cy-A}}}
一次函數是特殊的分式線性變換[ 4] 。
分式線性映射之間的複合結果仍然是分式線性變換[ 4] 。
如果
x
=
x
0
{\displaystyle x=x_{0}}
是分式線性變換
f
(
x
)
{\displaystyle f(x)}
的不動點,等價於
f
(
x
0
)
{\displaystyle f(x_{0})}
是其反函數的不動點。這是因為可逆函數的不動點與其反函數的不動點是一一對應的。
我們下面先通過一種計算量較少的思路來說明使用待定係數法時,第一步減去的常數一定是其不動點的原因。
按照待定係數法的思路,假定對分式線性變換解析式的
f
(
x
)
{\displaystyle f(x)}
兩側同時減去某個合適的常數P再同時取倒數後,能得到形式一致的分母。先做第一步減法,得:
a
n
+
1
−
P
=
A
a
n
+
B
C
a
n
+
D
−
P
=
A
a
n
+
B
−
P
C
a
n
−
D
P
C
a
n
+
D
=
(
A
−
P
C
)
a
n
+
(
B
−
D
P
)
C
a
n
+
D
{\displaystyle a_{n+1}-P={\frac {Aa_{n}+B}{Ca_{n}+D}}-P={\frac {Aa_{n}+B-PCa_{n}-DP}{Ca_{n}+D}}={\frac {(A-PC)a_{n}+(B-DP)}{Ca_{n}+D}}}
要使上面的式子取倒數後的分母滿足要求,由於分母取倒數前是位於分子的位置,基於前面的解題實例可知,我們只需要保證上式最左邊的量與最右邊的分子形式相似即可。
即只需要使
a
n
+
1
−
P
{\displaystyle a_{n+1}-P}
與
(
A
−
P
C
)
a
n
+
(
B
−
D
P
)
{\displaystyle (A-PC)a_{n}+(B-DP)}
的對應係數成相同比例即可。即:
1
A
−
P
C
=
−
P
B
−
D
P
{\displaystyle {\frac {1}{A-PC}}={\frac {-P}{B-DP}}}
,解得:
P
=
B
−
D
P
C
P
−
A
{\displaystyle P={\frac {B-DP}{CP-A}}}
。
顯然,這個所需的P值是
f
(
x
)
{\displaystyle f(x)}
的反函數的不動點。根據前面總結的性質,可知P也是
f
(
x
)
{\displaystyle f(x)}
的不動點。
即對
f
(
x
)
{\displaystyle f(x)}
兩側同時減去其不動點後,再取同時倒數,就一定能構造出一次的常係數非齊次遞推式。
也可以從函數同胚變換(也就是函數相似變換)的角度出發,來理解函數的多重迭代與分式線性遞推式的求解。不動點法在這兩類問題中都有登場出現。首先由於一次函數屬於特殊的分式線性變換,而且分式線性變換是可逆變化,所以自然想到能否將分式線性遞推式還原為某種更簡單的一次線性遞推式的形式。求出與之相關的一次線性遞推式的迭代結果後,再利用逆變換反推出原遞推式的多次迭代結果。另一方面,我們已經知道使用不動點法可以簡化一次線性遞推式的求解,我們希望將不動點也整合到分式線性變換還原為線性遞推式的係數配湊過程中。
使得
f
(
x
)
{\displaystyle f(x)}
可以與另一個函數
g
(
x
)
{\displaystyle g(x)}
建立下列聯繫的可逆函數
T
(
x
)
{\displaystyle T(x)}
叫做橋函數
[ 6] :
f
(
x
)
=
T
−
1
(
g
(
T
(
x
)
)
)
{\displaystyle f(x)=T^{-1}(g(T(x)))}
此時
f
(
x
)
{\displaystyle f(x)}
和
g
(
x
)
{\displaystyle g(x)}
叫做關於橋函數
T
(
x
)
{\displaystyle T(x)}
的一對相似函數 [ 6] ,或者說
f
(
x
)
{\displaystyle f(x)}
和
g
(
x
)
{\displaystyle g(x)}
關於橋函數
T
(
x
)
{\displaystyle T(x)}
互為相似函數。用拓撲學術語來說,橋函數是一種同胚 (homeomorphism )變換,它建立了
f
(
x
)
{\displaystyle f(x)}
和
g
(
x
)
{\displaystyle g(x)}
之間的拓撲共軛 (topological conjugacy )。
橋函數是計算函數迭代或巧妙構造數列的輔助函數。通過找到合適的橋函數,把不易得到迭代公式的
f
(
x
)
{\displaystyle f(x)}
變為容易得到迭代公式的形式更簡單的
g
(
x
)
{\displaystyle g(x)}
,計算完
g
(
x
)
{\displaystyle g(x)}
的n次迭代結果後,再使用橋函數的逆變換即可得到
f
(
x
)
{\displaystyle f(x)}
的n次迭代式。這種思路把函數迭代的問題轉化為橋函數的尋找與研究問題。
可以通過數學歸納法驗證函數
f
(
x
)
{\displaystyle f(x)}
的上述相似性(也就是拓撲共軛性)滿足以下規律(
T
(
x
)
{\displaystyle T(x)}
為
f
(
x
)
{\displaystyle f(x)}
的橋函數,
g
(
x
)
{\displaystyle g(x)}
是其共軛,下標表示迭代計算的次數)[ 6] :
f
n
(
x
)
=
T
−
1
(
g
n
(
T
(
x
)
)
)
{\displaystyle f_{n}(x)=T^{-1}(g_{n}(T(x)))}
知識背景:將函數藉助一個可逆的輔助函數,變換到另一個更容易求解或更容易研究的形式,在數學與物理學的許多分支中都是常見思想。矩陣對角化 、傅立葉變換 、Z變換 、卷積 等技巧都是這類思想的體現。用泛函分析 的術語來說,函數可以看成抽象空間中的點,如果一個函數直接研究起來不方便,我們就可以用可逆變換將它挪到其它更簡單明了的空間中再研究。變換的可逆性保證了函數本身的某些關鍵特性在某些恰當選取的空間中並不會改變太多,解決問題以後還可以把結果再變回到原來的空間。
了解了橋函數方法的轉換思想,下面使用不動點法的動機就是藉助不動點套出橋函數可能滿足的性質,以便確定所需橋函數中的未知待定係數。只要確定了橋函數的各個細節,就可以通過相似變換的方法巧妙地得到原函數的n次迭代式。
假設
f
(
x
)
=
T
−
1
(
g
(
T
(
x
)
)
)
{\displaystyle f(x)=T^{-1}(g(T(x)))}
,且
x
0
{\displaystyle x_{0}}
是
f
(
x
)
{\displaystyle f(x)}
的不動點,那麼
T
(
x
0
)
{\displaystyle T(x_{0})}
一定也會是
g
(
x
)
{\displaystyle g(x)}
的不動點[ 6] 。這說明如果我們求出了
f
(
x
)
{\displaystyle f(x)}
的不動點,並且有了簡單可行的
T
(
x
)
{\displaystyle T(x)}
,那麼
g
(
x
)
{\displaystyle g(x)}
的不動點也就知道了。
通常為了便於求解
g
(
x
)
{\displaystyle g(x)}
的n次迭代式,可以嘗試將
g
(
x
)
{\displaystyle g(x)}
取為下列形式[ 6] :
g
(
x
)
=
x
+
a
{\displaystyle g(x)=x+a}
g
(
x
)
=
a
x
{\displaystyle g(x)=ax}
g
(
x
)
=
a
x
2
{\displaystyle g(x)=ax^{2}}
g
(
x
)
=
a
x
3
{\displaystyle g(x)=ax^{3}}
對於這幾種情況,
g
(
x
)
{\displaystyle g(x)}
的不動點為0或
∞
{\displaystyle \infty }
。此時如果
f
(
x
)
{\displaystyle f(x)}
只有唯一的不動點a,可以考慮取
g
(
x
)
=
x
−
a
{\displaystyle g(x)=x-a}
或
g
(
x
)
=
1
x
−
a
{\displaystyle g(x)={\frac {1}{x-a}}}
;如果
f
(
x
)
{\displaystyle f(x)}
有2個相異的不動點a和b,則可以考慮取
g
(
x
)
=
x
−
a
x
−
b
{\displaystyle g(x)={\frac {x-a}{x-b}}}
。
就分式線性變換的例子來說,如果我們先求出了
f
(
x
)
=
A
x
+
B
C
x
+
D
{\displaystyle f(x)={\frac {Ax+B}{Cx+D}}}
的不動點
x
0
{\displaystyle x_{0}}
,那麼如果還能通過嘗試一些特例猜出合適的橋函數具有
T
(
x
)
=
1
x
−
k
{\displaystyle T(x)={\frac {1}{x-k}}}
的形式,並且目標函數是一次函數,那麼
p
=
T
(
x
0
)
{\displaystyle p=T(x_{0})}
也一定是一次函數
g
(
x
)
=
a
x
+
b
{\displaystyle g(x)=ax+b}
的不動點。即有下列關係式成立:
p
=
g
(
p
)
⇒
p
=
a
p
+
b
{\displaystyle p=g(p)\quad \Rightarrow \quad p=ap+b}
我們先不急着移項。因為我們可以從包含無窮大的擴展實數線 或擴充複平面 上考慮問題,易知從方程
λ
=
a
λ
+
b
(
a
,
b
≠
0
)
{\displaystyle \lambda =a\lambda +b\quad (a,b\neq 0)}
解出的唯一不動點是
λ
=
∞
{\displaystyle \lambda =\infty }
。所以
p
=
λ
=
∞
{\displaystyle p=\lambda =\infty }
,即可反推:
T
(
x
0
)
=
p
=
∞
⇒
1
x
0
−
k
=
∞
⇒
k
=
x
0
{\displaystyle T(x_{0})=p=\infty \quad \Rightarrow \quad {\frac {1}{x_{0}-k}}=\infty \quad \Rightarrow \quad k=x_{0}}
所以所求的關鍵待定係數k就是原函數
f
(
x
)
{\displaystyle f(x)}
的不動點
x
0
{\displaystyle x_{0}}
。
對於二次函數或包含二次項的分式函數,除了恰巧可以用簡單的配方法將二次項配湊進某個完全平方式的情形,一般都沒有什麼好辦法獲得n次迭代後的簡潔表達式[ 6] 。
其它可以解決分式線性遞推式的方法還包括轉化為二階常係數線性遞推數列 和多元遞推與矩陣方法 。
本節介紹的一階常係數非齊次線性遞推式和分式線性遞推式都可以用Mathematica軟件 提供的「RSolve」命令求解出通項公式。我們在這裡分別用Mathematica展示2種遞推式的通項公式求解方法。它的更多遞推式求解用法還會在常係數線性遞推數列 章節中繼續補充。
求解差分方程
a
1
=
1
,
a
n
+
1
=
2
a
n
+
3
{\displaystyle a_{1}=1,a_{n+1}=2a_{n}+3}
的示例:
RSolve [{ a [ n + 1 ] == 2 a [ n ] + 3 , a [ 1 ] == 1 }, a [ n ], n ]; (* 在Mathematica中表示相等,需要2个"="在一起连用 *)
在新單元格(cell)輸入完上述命令後,一般按組合鍵Shift + Enter即可得到結果。
求解分式線性差分方程
a
1
=
1
,
a
n
+
1
=
a
n
+
2
3
a
n
+
4
{\displaystyle a_{1}=1,a_{n+1}={\frac {a_{n}+2}{3a_{n}+4}}}
的示例:
RSolve [{ a [ n + 1 ] == ( a [ n ] + 2 ) / ( 3 a [ n ] + 4 ), a [ 1 ] == 1 }, a [ n ], n ]; (* 在Mathematica中表示相除,需要使用"/"符号 *)
此題的答案很複雜很可怕哦~
提示:如果RSolve命令沒有輸入錯誤,但是執行後出現「RSolve::deqn: Equation or list of equations expected instead of True in the first argument True.」一類的報錯信息,一般是由於沒有清除同名標識符 中的已有信息。如果是這種情況:(1)可以先在其它地方輸入獨立命令「ClearAll[a]」清除標識符a中的內容,然後重新執行RSolve命令;(2)也可以改用除a以外的其它未使用過的標識符來命名要求解的數列。
提示:「RSolve」命令中的「R」是遞推(recurrence relation)、遞歸(recursion)的意思。它與「Resolve」命令拼寫相似,但功能不同。Resolve是用於化簡約束條件的,例如可以求解一些不等式或不等式組。
相關例題1:
已知在數列
{
a
n
}
{\displaystyle \{a_{n}\}}
中,滿足
a
1
=
1
,
a
n
+
1
=
2
a
n
+
3
{\displaystyle a_{1}=1,a_{n+1}=2a_{n}+3}
,使用Mathematica求它的通項公式。
解答:
在Mathematica軟件中輸入命令(因為只有一行命令,分號此時可以不寫):
RSolve[{a[n + 1] == 2 a[n] + 3, a[1] == 1}, a[n], n];
然後按組合鍵Shift + Enter即可得到結果為:
a
n
=
1
2
(
(
1
−
2
)
n
+
(
1
+
2
)
n
)
{\displaystyle a_{n}={\frac {1}{2}}((1-{\sqrt {2}})^{n}+(1+{\sqrt {2}})^{n})}
。
答案:
a
n
=
−
3
+
2
1
+
n
{\displaystyle a_{n}=-3+2^{1+n}}
。
相關例題2:
已知數列
{
a
n
}
{\displaystyle \{a_{n}\}}
滿足
a
1
=
1
,
a
n
+
1
=
2
a
n
+
3
a
n
+
4
{\displaystyle a_{1}=1,a_{n+1}={\frac {2a_{n}+3}{a_{n}+4}}}
,使用Mathematica求它的通項公式。
解答:
命令用法示例:
RSolve[{a[n + 1] == (2 a[n] + 3) / (a[n] + 4), a[1] == 1}, a[n], n];
然後按組合鍵Shift + Enter即可得到結果為:
a
n
=
1
2
(
(
1
−
2
)
n
+
(
1
+
2
)
n
)
{\displaystyle a_{n}={\frac {1}{2}}((1-{\sqrt {2}})^{n}+(1+{\sqrt {2}})^{n})}
。
答案:
a
n
=
3
(
(
−
1
)
n
+
(
−
1
)
1
+
n
5
1
−
n
)
3
(
−
1
)
n
+
(
−
1
)
n
5
1
−
n
{\displaystyle a_{n}={\frac {3((-1)^{n}+(-1)^{1+n}5^{1-n})}{3(-1)^{n}+(-1)^{n}5^{1-n}}}}
。