遞迴關係（六）（Recurrence relation-6）

遞迴關係（六）（Recurrence relation-6）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚教授責任編輯

連結：遞迴關係（五）

摘要：本篇介紹一個複雜的遞迴式「Logistic Map（邏輯映射）」，藉此讓讀者認識「混沌（Chaos）」領域。

之前介紹的幾個遞迴式，一般項或者都還能精確求出來（費波那契數，Catalan 數），或至少能知道個大概（Merge  Sort）。本文來介紹一個真正複雜的遞迴式，稱為「Logistic Map（邏輯映射）」—  不是形式複雜，而是結果複雜。這個遞迴式貌似和藹可親，卻非常難以分析和預測。事實上它根本無法求出一般項。

由此遞迴式，竟引出一整個新的數學分支，稱為「混沌（Chaos）」。

\((4)\)  Logistic Map

科學家在研究人口數量模型時，考慮了如下的遞迴關係式：

\(a_n=ra_{n-1}(1-a_{n-1})\)

其中 \(r\) 是一個事先給定的常數，初始值 \(0\leq a_0\leq 1\)。

一個遞迴式可視為一個「離散動態系統」— 簡單來說就是隨著時間變化的一個系統。以此例而言，時間 \(t=n\) 時的人口比例為 \(a_n\)，可以由常數 \(r\) 以及時間 \(t=n-1\) 時的人口比例 \(a_{n-1}\) 所決定。初始值是 \(t=0\) 時的 \(a_0\)。

我們來做幾個實驗。令 \(r=2.5, a_{0}=0.7\)。則數列接下來幾項是

\(\begin{multline*}0.525,~0.6234375,~0.5869079590,\\0.6061175169,~0.5968476814,~0.6015513167\end{multline*}\)

可以感覺到趨近於 \(0.6\)。

令 \(r=2.5, a_{0}=0.2\)。則數列接下來幾項是

\(\begin{multline*}0.225,~0.4359375,~0.6147399902,\\0.5920868368,~0.6038000362,~0.5980638810\end{multline*}\)

看起來也趨近於 \(0.6\)。

沒錯。這個動態系統當\(r=2.5\) 時，不管初始值是多少，最後結果會收斂到 \(0.6\)。亦即人口比例會趨近於一個定值。但是如果以為不管 \(r\) 是多少，丟個初始值進去最後都會收斂到一個值，那就大錯 — 故事才正要開始呢。

如果令 \(r=3.2, a_{0}=0.1\)。則 \(a_{16},a_{17},a_{18},a_{19},a_{20}\) 是

\(\begin{multline*}0.5148102833,~0.7992980978,~0.5133460757,\\0.7994300231,~0.5130933161\end{multline*}\)

嘿，結果居然在兩個數之間擺盪。

如果再令 \(r=3.2, a_{0}=0.7\)。則 \(a_{16},a_{17},a_{18},a_{19},a_{20}\) 是

\(\begin{multline*}0.7955869577,~0.5204107215,~0.7986668879,\\0.5145538882,~0.7993221898\end{multline*}\)

也在兩個數之間擺盪，而且似乎擺到和 \(a_0=0.1\) 時的同樣兩個數。

再多換一些不同的 \(r\)，可以發現這個遞迴式的行為似完全取決於 \(r\)— 亦即一旦 \(r\) 決定了，初始值並不重要。而且不只如此，當 \(r\) 取大一點時，得到非常不可預測的結果。

如上圖，橫軸為 \(r\)，縱軸為收斂值。當 \(r=2.5\) 時，不管初始值是多少，最後結果會收斂到 \(0.6\)；當 \(r=3.2\)，不管初始值是多少，最後結果會在兩個值之間擺盪（上圖中 \(r=3.2\) 對上去會和圖形有兩個交點）。所以這個圖非常有意思。

當 \(r<3\) 時，不管初始值是多少，最後結果會收斂到一個值。

當 \(3<r<1+\sqrt{6}\) 時，不管初始值是多少，最後結果週期為 \(2\)（在兩個值之間擺盪）。

當 \(1+\sqrt{6}<r<3.54\) 時，不管初始值是多少，最後結果週期為 \(4\)。

那右邊一陀黑色是什麼意思呢？比如說 \(r=3.9\) 對上去有多少點？黑壓壓的一片！數列行為變得非常混亂，不可預測。\(r\) 一路在增長時，數列的行為會發生相變（phase change），從收斂，擺盪，到一片混亂。

由此討論下去，引出了混沌（Chaos）這個數學分支。不過就是一個簡單的遞迴由此討論下去，引出了混沌（Chaos）這個數學分支。不過就是一個簡單的遞迴。

連結：遞迴關係（七）

參考文獻：

1. Tucker, Applied Combinatorics, 5th edition, Wiley.
2. Brualdi, Introductory Combinatorics, 5th Edition, Pearson.

延伸閱讀：

1. 教育部，高中課程綱要(99)，2010。
2. Ausloos, Dirickx, The Logistic Map and the Route to Chaos: From the Beginnings to Modern Applications, 2010.