Tag Archives: 組合數學

特殊矩陣 (15):Pascal 矩陣 (上)

本文的閱讀等級:中級 二項式定理 (binomial theorem) 由牛頓於公元1664-65年間提出,此定理給出 的整數次冪展開公式: , 其中 為 取 的組合數目,稱為二項式係數,它遵守帕斯卡(Pascal)法則: 。 證明如下。令 表示 個元素構成的集合,設 ,由 中選取 個元素可分開兩種情況討論:若不取 ,則必須從 選取 個元素,組合數為 ;若選取 ,則還要從 取其餘 個元素,組合數為 。帕斯卡法則的代數證明請見“二項式係數公式”。 Advertisements

Posted in 特殊矩陣, 線性代數專欄 | Tagged , , , , , , , , , | 1 Comment

矩陣鏈乘積的最佳計算順序

本文的閱讀等級:初級 給定一序列的可乘矩陣,這些矩陣的乘積稱為矩陣鏈乘積。我們知道矩陣乘法有結合律,所以不論採用何種相乘順序,最後的結果總是一樣的。例如, 是 , 是 , 是 , 是 階矩陣,總計有 種方式刮號乘積,如下: ,,,, 雖然矩陣鏈乘積相同,但不同的乘法順序所耗費的運算量並不相同。例如,若以乘法運算為計數單位, 需要 個運算,而 只使用 個運算,第二種計算方式明顯優於第一種方式。考慮一般情況,如果有 個矩陣相乘,如何決定最佳的矩陣乘法執行順序?這個問題不存在一般公式解。最直接的方法是比較每一種順序的運算量,不過,這僅適用於小 的情況。當 ,刮號乘積有 種可能,而當 時,總共有 種可能!對於長矩陣鏈,不難理解蠻力檢查是絕對不可行的。

Posted in 線性方程, 線性代數專欄 | Tagged , , , | Leave a comment