高中數學/不等式與數列/不動點法

閱讀指南

編輯

 

在前面一階遞推關係的求解章節中我們已經知道,對於 這樣的數列,我們可以將其改寫為 ,從而將 整體地當作一個等比數列套用公式。如果係數更麻煩一點,比如對於 這樣的數列,原則上還是可以拆分常數,然後在等號的左右兩邊分別構造出等比數列。但是此時的常數如何拆分不那麼容易直接嘗試出來。一個比較容易想到的辦法是採用待定係數法,先提前假設構造好的數列具有 的形式,初步化簡後再和原來的 放在一起,比較各對應項的數值,即可確定與原關係式匹配的d值。

本節介紹的不動點法則是確定這個待定構造係數的更直接、簡便的方法。不動點法可以解決形如 的非齊次一階常係數線性遞推關係式的構造,也可以解決形如 的一階常係數分式線性遞推關係式的構造。除了這2種類型的遞推式之外,少數可以轉換為這2種情形的特例也可以使用不動點法求解構造係數。

這類不動點法的主要特點就是:

  • 適用條件容易判斷
  • 用起來爽(對於不少常見情況而言)
  • 解釋起來很麻煩

本節花費了不少篇幅提及這些方法背後的由來,其中多半不可避免地會介紹一些來自後續數學課程中的背景知識。如果讀者對於不動點法的使用完全沒有經驗,建議先接觸一些應用不動點解題的例題。了解不動點法解題的大致流程後,再根據需要了解其背後的由來,不然容易對其中的一些推敲思路產生困惑。

考試要求

編輯

不動點法並不被列入普通高中的考試大綱,因此在常規的高中考試中不能直接聲明是在藉助不動點法解題。但是利用不動點法的確可以快速求出所需的待定係數,識別適合使用不動點的問題並能快速地在草稿紙上用此方法求出所需的係數還是比較有必要掌握的。

基礎知識

編輯

不動點的概念

編輯

定義:對於1個給定的函數 ,能使 成立的自變量取值 叫做該函數的不動點(fixed point)[1][2]

與遞推式形式一致的函數也被叫做遞推關係式的特徵函數characteristic function)或背景函數[1]。遞推式特徵函數的不動點也叫做遞推式的不動點。不動點在對應函數圖象上的對應點也叫做函數圖象的不動點[2]

在解決高中數列遞推問題時,我們討論的不動點都是可逆函數的不動點。可逆函數的不動點有以下特點:

  • 如果 是可逆函數 的不動點,等價於 是其反函數 的不動點。換句話說,可逆函數的不動點與其反函數的不動點是一一對應的。
  • 函數的不動點坐標具有 的形式,即不動點一定是函數圖象與特殊直線 的交點。
  • 如果把可逆函數 與其反函數 的圖象畫在同一個直角坐標系中,則它們的圖象交點都是不動點。

不動點本身是拓撲學的知識點,表示物體或空間在某種拓撲變換的作用下,仍保持固定不動的點。它的幾何意義是函數圖象與恆等變換直線 交點的橫坐標。但是它也出現在有關數列的解題方法中。

利用不動點簡化一階常係數線性遞推關係式的通項求解

編輯

在從遞推式 構造等比數列的過程中,使用待定係數法所求的需要分配到等式兩邊的數值,剛好就可以用對應函數 的不動點來確定。我們先給出用不動點法解決這類數列的通用解題步驟,然後結合例題說明它的具體運用。

  用不動點法可以求出一階線性遞推數列  (其中p和q為常數,且 )的通項的一般式[3]。其主要步驟為:
(1) 寫出與 對應的特徵函數 
(2) 求出函數 的不動點 ,即求解方程 ,解得: 
(3) 在原始 的等號兩邊同時減去剛才求出的不動點 ,即:

 

(4) 將 整體地看作一個等比數列求解,求出 的表達式後, 的表達式自然也就知道了。

可以證明,這樣求得的最終結果形式為 [3]。但是實際上,解題時並不需要記住這個最終形式,只需要記住上面的幾個關鍵步驟即可。

  提示:如果求出的不動點形式比較複雜(例如算出的解帶着根號跑),此時使用不動點法對於簡化數列構造時的係數運算也無法提供太多幫助。求解兔子數列的通項公式問題就是一個例子。

一階常係數線性遞推關係式的不動點解法由來

編輯

關於在一階常係數線性遞推關係式的通項求解中,為什麼會與不動點的概念產生聯繫,我們在這裡給予一個比較簡單的論證。

先設 
再假設我們期待的構造好的等比數列形式 
用後一式的兩端同時對前一式的兩端作差,可得:
 
最後一個式子顯然說明所需要的常數p就是函數 的不動點。

從幾何上講,從截距不為零的一次函數(對應於上述非齊次一階線性遞推關係式)變形為正比例函數(對應於構造出來的等比數列滿足的關係式)的變換就是一種圖象平移操作,而此類函數的不動點提供了同時沿y軸方向和x軸方向進行圖象平移的距離參考值。

一階常係數分式線性遞推關係式的概念及其通項的待定係數解法

編輯

形如 的一階常係數分式線性遞推關係式的構造也可以藉助不動點的求解實現[2]

  提示:我們先在本小節簡述如何使用待定係數法求這類分式線性遞推式通項的大體思路,再在後面的小節介紹基於不動點法的優化和解題實例,最後談談在這類情形下可以使用不動點法的原理。

定義:具有以下形式的遞推式 叫做常係數分式線性遞推關係
 

利用不動點簡化一階常係數分式線性遞推關係式的通項求解

編輯

我們接下來從不動點的角度,指出這種常係數分式線性遞推關係的通項公式求解方法。

  提示:本小節前半部分展示的代數變形過程比較冗長羅嗦,主要就是講述了2種情況下最基本的分類討論,外加上常見優化步驟的思路由來。沒有耐心的讀者可以先看結論和具體例題,然後有時間再回過頭來大致瀏覽一下這些純字母化的運算和論證。

設函數 滿足 ,其不動點為 。 其不動點滿足的方程 可能只有1個解,也可能有2個不同的解(不同的實數根或不同的虛數根)[4]

如果 為以上方程的任何一個根(從而 也是函數的不動點),那麼可以先對原遞推式兩邊同時減去不動點:
 
再對上式兩側同時顛倒可得:
 
由上式可知此時 整體來說是一個一階常係數線性遞推數列,且包含有取值為常數的非齊次項。

如果不動點方程 的2個根是重根,則有  。此時可以繼續化簡:
 
 變為以 為首項、 為公差的等差數列,易知其通項為:
  既然在這種情形下都已經得到 的解析式,從而 的解析式也容易知道了。

如果不動點方程 有2個相異的根,那麼最直接的想法是只能麻煩一點,針對得到的常係數線性遞推式再使用不動點法構造一次:
 
此時 構成公比為 的等比數列,即:
 

如果方程有2個不等的根  (是不同的實數根或不同的虛數根都行),此時還有一種基於不動點但是構造方向與上述思路有一些差異的解法。先在原遞推式的兩側分別減去這2個根,可以得到:
 
如果觀察上述2個式子,可以發現它們的右側都有相同的分母,且右側的分子形式非常相似,最好能利用這個相同點去掉它們的分母。於是不妨對上述2個式子的兩端同時作商(相除)可得:
 ,其中 
易知此時 整體來說是一個以 為首項、k為公比的等比數列,所以得到 的通項公式:
 
既然已經得到 的解析式,從而 的解析式也容易知道了。
這種方法此時可以更快地得到同樣的最終結果:
 

  綜上所述,我們可以將常係數分式線性遞推式的通項求解思路簡化如下[5]

  • 當只有1個不動點時,可以對原遞推式的兩邊同時減去不動點,然後再同時取倒數,進而轉化為等差數列求解。
  • 當有2個相異的不動點時,可以先對原遞推式的兩邊同時減去第1個不動點並取倒數,再對原遞推式的兩邊同時減去第2個不動點並取倒數,然後將分別得到的2個式子作商,進而轉化為等比數列求解。

分式線性變換的概念與分式線性遞推式的不動點解法由來

編輯

定義:具有以下形式的函數 叫做分式線性變換linear fractional transformation):
 

因為德國數學家奧古斯特·莫比烏斯曾對其進行過大量研究,所以分式線性變換也叫做莫比烏斯變換Möbius transformation)。[4]

通過簡單的分式分解,易知莫比烏斯函數可以分解為以下形式:   由於我們只考慮自變量值取實數的情形,因此可以對於特定的一組係數可以畫出函數的圖像。而由上述表達式的圖象性質可知,分式線性變換是可逆的。

容易驗證以下性質:

  • 分式線性變換 的逆變換(即反函數)為[4]
 
  • 一次函數是特殊的分式線性變換[4]
  • 分式線性映射之間的複合結果仍然是分式線性變換[4]
  • 如果 是分式線性變換 的不動點,等價於 是其反函數的不動點。這是因為可逆函數的不動點與其反函數的不動點是一一對應的。

我們下面先通過一種計算量較少的思路來說明使用待定係數法時,第一步減去的常數一定是其不動點的原因。
按照待定係數法的思路,假定對分式線性變換解析式的 兩側同時減去某個合適的常數P再同時取倒數後,能得到形式一致的分母。先做第一步減法,得:
 
要使上面的式子取倒數後的分母滿足要求,由於分母取倒數前是位於分子的位置,基於前面的解題實例可知,我們只需要保證上式最左邊的量與最右邊的分子形式相似即可。
即只需要使  的對應係數成相同比例即可。即:
 ,解得: 
顯然,這個所需的P值是 的反函數的不動點。根據前面總結的性質,可知P也是 的不動點。
即對 兩側同時減去其不動點後,再取同時倒數,就一定能構造出一次的常係數非齊次遞推式。

從同胚變換的角度理解函數迭代與遞推式求解

編輯

也可以從函數同胚變換(也就是函數相似變換)的角度出發,來理解函數的多重迭代與分式線性遞推式的求解。不動點法在這兩類問題中都有登場出現。首先由於一次函數屬於特殊的分式線性變換,而且分式線性變換是可逆變化,所以自然想到能否將分式線性遞推式還原為某種更簡單的一次線性遞推式的形式。求出與之相關的一次線性遞推式的迭代結果後,再利用逆變換反推出原遞推式的多次迭代結果。另一方面,我們已經知道使用不動點法可以簡化一次線性遞推式的求解,我們希望將不動點也整合到分式線性變換還原為線性遞推式的係數配湊過程中。

使得 可以與另一個函數 建立下列聯繫的可逆函數 叫做橋函數 [6]
 

此時  叫做關於橋函數 的一對相似函數[6],或者說  關於橋函數 互為相似函數。用拓撲學術語來說,橋函數是一種同胚homeomorphism)變換,它建立了  之間的拓撲共軛topological conjugacy)。

橋函數是計算函數迭代或巧妙構造數列的輔助函數。通過找到合適的橋函數,把不易得到迭代公式的 變為容易得到迭代公式的形式更簡單的 ,計算完 的n次迭代結果後,再使用橋函數的逆變換即可得到 的n次迭代式。這種思路把函數迭代的問題轉化為橋函數的尋找與研究問題。

可以通過數學歸納法驗證函數 的上述相似性(也就是拓撲共軛性)滿足以下規律(  的橋函數, 是其共軛,下標表示迭代計算的次數)[6]
 

  知識背景:將函數藉助一個可逆的輔助函數,變換到另一個更容易求解或更容易研究的形式,在數學與物理學的許多分支中都是常見思想。矩陣對角化傅立葉變換Z變換卷積等技巧都是這類思想的體現。用泛函分析的術語來說,函數可以看成抽象空間中的點,如果一個函數直接研究起來不方便,我們就可以用可逆變換將它挪到其它更簡單明了的空間中再研究。變換的可逆性保證了函數本身的某些關鍵特性在某些恰當選取的空間中並不會改變太多,解決問題以後還可以把結果再變回到原來的空間。

了解了橋函數方法的轉換思想,下面使用不動點法的動機就是藉助不動點套出橋函數可能滿足的性質,以便確定所需橋函數中的未知待定係數。只要確定了橋函數的各個細節,就可以通過相似變換的方法巧妙地得到原函數的n次迭代式。

  假設 ,且  的不動點,那麼 一定也會是 的不動點[6]。這說明如果我們求出了 的不動點,並且有了簡單可行的 ,那麼 的不動點也就知道了。

通常為了便於求解 的n次迭代式,可以嘗試將 取為下列形式[6]

  •  
  •  
  •  
  •  

對於這幾種情況, 的不動點為0或 。此時如果 只有唯一的不動點a,可以考慮取  ;如果 有2個相異的不動點a和b,則可以考慮取 

就分式線性變換的例子來說,如果我們先求出了 的不動點 ,那麼如果還能通過嘗試一些特例猜出合適的橋函數具有 的形式,並且目標函數是一次函數,那麼 也一定是一次函數 的不動點。即有下列關係式成立:
 
我們先不急着移項。因為我們可以從包含無窮大的擴展實數線擴充複平面上考慮問題,易知從方程 解出的唯一不動點是 。所以 ,即可反推:
 
所以所求的關鍵待定係數k就是原函數 的不動點 

其它可以轉換為上述情形的特例

編輯

對於二次函數或包含二次項的分式函數,除了恰巧可以用簡單的配方法將二次項配湊進某個完全平方式的情形,一般都沒有什麼好辦法獲得n次迭代後的簡潔表達式[6]

分式線性遞推的其它方法概述

編輯

其它可以解決分式線性遞推式的方法還包括轉化為二階常係數線性遞推數列多元遞推與矩陣方法

計算機求解

編輯

Mathematica

編輯

本節介紹的一階常係數非齊次線性遞推式和分式線性遞推式都可以用Mathematica軟件提供的「RSolve」命令求解出通項公式。我們在這裡分別用Mathematica展示2種遞推式的通項公式求解方法。它的更多遞推式求解用法還會在常係數線性遞推數列章節中繼續補充。

求解差分方程 的示例:

RSolve[{a[n + 1] == 2 a[n] + 3, a[1] == 1}, a[n], n]; (* 在Mathematica中表示相等,需要2个"="在一起连用 *)

在新單元格(cell)輸入完上述命令後,一般按組合鍵Shift + Enter即可得到結果。

求解分式線性差分方程 的示例:

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: 已知在數列 中,滿足 ,使用Mathematica求它的通項公式。

解答:
在Mathematica軟件中輸入命令(因為只有一行命令,分號此時可以不寫):
RSolve[{a[n + 1] == 2 a[n] + 3, a[1] == 1}, a[n], n];
然後按組合鍵Shift + Enter即可得到結果為: 

答案: 

  相關例題2: 已知數列 滿足 ,使用Mathematica求它的通項公式。

解答:
命令用法示例:
RSolve[{a[n + 1] == (2 a[n] + 3) / (a[n] + 4), a[1] == 1}, a[n], n];
然後按組合鍵Shift + Enter即可得到結果為: 

答案: 

補充習題

編輯

   

參考資料

編輯
  1. 1.0 1.1 梁訓果; 王永明. 第一部分 數列相關問題. 高考數學最後一題. 萬試無憂系列叢書 5. 重慶出版集團. 2011. ISBN 978-7-5366-8521-5 (中文(中國大陸)). 
  2. 2.0 2.1 2.2 蔡小雄. 第4章「用競賽策略優化高考解題」第4.1節「熟悉遞推方法」第4.1.3小節「不動點法」. (編) 董德耀; 沈國明. 更高更妙的高中數學思想與方法 1. 中國杭州天目山路148號: 浙江大學出版社. 2009: 241–243. ISBN 978-7-308-06993-9 (中文(中國大陸)). 
  3. 3.0 3.1 李世傑. 第2章「遞推數列」第1節「遞推數列的定義」. (編) 黃娟琴 (責任編輯); 許佳穎 (文字編輯). 遞推與遞推方法. 高中數學競賽專題講座 1. 中國杭州天目山路148號: 浙江大學出版社. 2008: 26. ISBN 978-7-308-06087-5 (中文(中國大陸)). 
  4. 4.0 4.1 4.2 4.3 4.4 鍾玉泉. 第7章「共形映射」第2節「分式線性變換」. (編) 王瑜 (策劃編輯); 丁鶴齡 (責任編輯). 複變函數論. 朱慧芳 (責任校對) 1. 中國北京市西城區德外大街4號: 高等教育出版社. 2004: 283–289. ISBN 7-04-012943-4 (中文(中國大陸)). 
  5. 趙嘉璐. 用不動點法求分式型遞推數列的通項 (8月). 數學學習與研究: 107. 2018 (中文(中國大陸)). 
  6. 6.0 6.1 6.2 6.3 6.4 6.5 熊斌; 朱臻; 蘇勇. 第6章「函數的迭代」第6.2節「f^n (x)的求法」. (編) 孔令志 (項目編輯); 朱洪敏 (審讀編輯). 函數與函數方程. 數學奧林匹克小叢書·高中卷 2. 中國上海市中山北路3663號: 華東師範大學出版社. 2012: 86–95. ISBN 978-7-5617-9170-7 (中文(中國大陸)). 

外部連結

編輯
 
維基百科中的相關條目:
 
維基百科中的相關條目: