Tag Archives: 遞迴關係式

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

本文的閱讀等級:初級 考慮下列 階線性非齊次遞迴關係式 (linear nonhomogeneous recurrence relation) , 其中 是常數,, 稱為控制項。如果移除 , 稱為關聯齊次遞迴關係式 (associated homogeneous recurrence relation)。令數列 為滿足非齊次遞迴關係式的一個特解 (particular solution),數列 為滿足關聯齊次遞迴關係式的齊次解 (homogeneous solution)。非齊次遞迴關係式的任一解 (即通項) 可表示為 ,證明於下:因為 是一個特解, 。 假設 是任何一個非齊次遞迴關係式的解,即有 。 令上面兩式相減, 。 因此, 滿足關聯齊次遞迴關係式,可得 。本文討論非齊次遞迴關係式的控制項為 的解法,其中 是一個多項式, 是一常數。

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

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

本文的閱讀等級:中級 前文介紹了常係數線性齊次遞迴關係式在特徵多項式有相異根的情況下的兩個線性代數解法 (見“常係數線性遞迴關係式 (上)”)。第一個方法建立於數列形成的無限維向量空間,通過與齊次遞迴關係式的特徵多項式同形式之算子多項式的零空間找出解。然而,當特徵多項式存在重根時,零空間基底的推導過程相當繁複。本文使用第二個方法,以簡潔的矩陣分析解出當特徵多項式存在重根時齊次遞迴關係式的通項表達式。

Posted in 線性代數專欄, 典型形式 | Tagged , , | Leave a comment

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

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

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

答r2123b──關於矩陣與遞迴關係式的特徵多項式

網友r2123b留言: 老師:請問線代的特徵多項式 跟求解遞迴方程式 ,,的 時所用的特徵多項式有什麼關聯嗎?為什麼都叫特徵多項式?

Posted in 特徵分析, 答讀者問 | Tagged , , , , | Leave a comment

遞迴關係式的母函數解法

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

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