Tag Archives: 費布納西數列

常係數線性遞迴關係式 (上)

本文的閱讀等級:初級 一 階常係數線性遞迴關係式 (linear recurrence relation) 可表示如下: , 其中 是常數,, 稱為控制項。滿足上式的序列 稱為線性遞迴數列,由設定的初始值 唯一決定。考慮較簡單的情況,,我們稱之為齊次 (homogeneous) 遞迴關係式。例如,費布納西 (Fibonacci) 數列 的二階遞歸生成規則如下 (見“費布納西數列的表達式”): , 初始條件為 和 。通項 的代數表達式有兩種常見解法:母函數法 (見“遞迴關係式的母函數解法”) 與線性代數法。下面以費布納西數列為例說明兩個線性代數解法。 Advertisements

Posted in 特徵分析, 線性代數專欄 | Tagged , , , | 7 Comments

遞迴關係式的母函數解法

本文的閱讀等級:初級 美國數學教授維爾夫 (Herbert Wilf) 說[1]:「母函數 (生成函數,generating function) 是一列用來展示一串數字的掛衣架。」母函數是一數列 的一種形式冪級數 (formal power series),其中每一項的係數可以提供關於這個數列的訊息。母函數有多種不同的形式,數列 的普通母函數為 母函數 本身並不是一個從某個定義域映射至某個值域的函數,變數 沒有甚麼特別的意義,取名「函數」僅是出於歷史原因。母函數是一個代數物件而非分析物件,我們只對它的表達形式感興趣,並不關心它是否收斂。母函數經常源自遞迴關係式 (即差分方程)。本文將介紹如何利用母函數方法解出遞迴關係式的代數式。由於我們完全忽略收斂性,母函數方法是否能經得起推敲不免令人生疑。不過母函數至少能夠導出遞迴關係式的猜想,而猜想又可以用數學歸納法來證明。

Posted in 特別主題 | Tagged , , , , , , | Leave a comment

特殊矩陣 (19):Hessenberg 矩陣

本文的閱讀等級:中級 令 為一 階矩陣。若 , ,則 稱為上 Hessenberg 矩陣,也就是說, 的主對角下標元 (subdiagonal,即 ) 之下的所有元為零。若 的主對角上標元 (superdiagonal,即 ) 之上的所有元為零,則稱為下 Hessenberg 矩陣。此特殊矩陣因德國工程師黑森貝格 (Karl Adolf Hessenberg) 而得名。見下例, 是上 Hessenberg 矩陣, 是下 Hessenberg 矩陣, 同時是上、下 Hessenberg 矩陣,稱為三對角 (tridiagonal) 矩陣 (見“特殊矩陣 (11):三對角矩陣”): 。 明顯地,對稱 Hessenberg 矩陣必定是三對角矩陣。下 … Continue reading

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , , | Leave a comment

利用馬可夫鏈計算擲幣事件發生的機率

本文的閱讀等級:中級 美國康乃爾大學心理學教授季洛維奇 (Thomas Gilovich) 每年都會在他的統計學課堂中安排一個實驗[1]。他要求每位學生各自寫下一組心中模擬投擲一枚公正硬幣20次所產生的隨機序列,分別以 O 和 X 代表正面和反面。但是,其中一位學生則被指派實際投擲一枚硬幣20次,也寫下他的實驗結果。季洛維奇在實驗進行前走出教室,等他返回教室後,他將接受一項挑戰:檢視所有學生繳交的實驗記錄,然後判斷其中那一張紙記載了實際擲幣產生的序列。季洛維奇總是能令學生們驚訝不已,他無一次例外地揀選出真實的擲幣序列。究竟他是怎麼辦到的?季洛維奇既沒有暗藏機關也不具特異能力,他掌握的技能不過就是「資訊不對稱」。身為心理學教授,他知道絕大多數人──包括教室中的學生──總是低估了出現連續正面或反面的機率。真實的擲幣結果幾乎都是那張記錄著最長的連續正面或反面的序列,例如: OXXXXXOXOOXOOXOOXOOX, 而學生們想像出來的擲幣序列則經常如下: XXOXOOOXOOXOXXOOXXOO。 本文的主題即在破解季洛維奇的戲法:釐清投擲一枚公正硬幣 次,計算出現至少連續 次正面的機率。

Posted in 機率統計 | Tagged , , , , , , | 3 Comments

費布納西數列的表達式

本文的閱讀等級:初級 公元十三世紀義大利數學家費布納西 (Leonardo Pisano Bigollo,又名 Leonardo Fibonacci) 在研究兔群生長的問題時發明了一種無窮數列:第0項為0,第1項為1,以後的各項等於之前兩項的和。後人稱它為費布納西數列,下面列出最初幾項: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,… 費布納西數列和許多自然界現象的數學結構有密切關係。大多數植物的花瓣數目都屬於費布納西數 (費布納西數列的各項)。大型向日葵頭上的小花 (floret) 排列成兩組交錯螺線,一組順時針旋轉,另一組逆時針旋轉。兩組螺線確切的數目由品種決定,但通常是兩相鄰的費布納西數[1],譬如,34與55,或55與89[維基百科圖例]。不僅如此,兩相鄰費布納西數的比趨於黃金比例: 例如,55/34=1.6176470588…,89/55=1.6181818181…。西方人著迷黃金比例已有超過二千年的歷史[2],費布納西數列與黃金比例的特殊關係更因此讓它蒙上一層神秘色彩。由於上述種種原因,費布納西數列經常出現於大眾文化中,如電影、文學、視覺藝術,甚至音樂[3]。本文要討論的是一個單純的數學問題:推導費布納西數列的一般表達式。

Posted in 特徵分析, 線性代數專欄 | Tagged , , , , , | 6 Comments