本文的閱讀等級：初級
給定一序列的可乘矩陣，這些矩陣的乘積稱為矩陣鏈乘積。我們知道矩陣乘法有結合律，所以不論採用何種相乘順序，最後的結果總是一樣的。例如，$$A$$ 是 $$3\times 5$$，$$B$$ 是 $$5\times 2$$，$$C$$ 是 $$2\times 4$$，$$D$$ 是 $$4\times 6$$ 階矩陣，總計有 $$5$$ 種方式刮號乘積，如下：
$$((AB)C)D$$，$$(A(BC))D$$，$$(AB)(CD)$$，$$A((BC)D)$$，$$A(B(CD))$$
雖然矩陣鏈乘積相同，但不同的乘法順序所耗費的運算量並不相同。例如，若以乘法運算為計數單位，$$A(BC)$$ 需要 $$(5\times 2\times 4)+(3\times 5\times 4)=40+60=100$$ 個運算，而 $$(AB)C$$ 只使用 $$(3\times 5\times 2)+(3\times 2\times 4)=30+24=54$$ 個運算，第二種計算方式明顯優於第一種方式。考慮一般情況，如果有 $$n$$ 個矩陣相乘，如何決定最佳的矩陣乘法執行順序？這個問題不存在一般公式解。最直接的方法是比較每一種順序的運算量，不過，這僅適用於小 $$n$$ 的情況。當 $$n=10$$，刮號乘積有 $$16,796$$ 種可能，而當 $$n=20$$ 時，總共有 $$6,564,120,420\approx 6\times 10^9$$ 種可能！對於長矩陣鏈，不難理解蠻力檢查是絕對不可行的。
2010年9月11日 星期六
2010年6月18日 星期五
線性代數的第一堂課——矩陣乘法的定義
本文的閱讀等級：初級
美國數學家 Morris Kline (1908-1992) 說[1]：「矩陣理論在被創造前就已發展完善（the subject of matrix theory was well developed before it was created）。」這句話讓人聽得一頭霧水，要弄清楚這話的意思必須從矩陣的發展歷史說起。西元十七至十九世紀中葉，數學活動在歐洲以快速的步伐朝各領域繁盛發展，此時關於陣列（array）運算的研究全部集中於行列式理論，令人不解的是矩陣代數並未隨著行列式進行，矩陣理論足足落後行列式兩百年之久。西元 1850年，英國數學家 James Joseph Sylvester (1814-1897) 將矩形陣列命名為矩陣（matrix），但他並未定義矩陣乘法。1857 年，英國數學家 Arthur Cayley (1821-1895) 發表 A Memoir on the Theory of Matrices，他將矩陣從行列式抽離出來，視之為單獨數學物件，並定義完備的矩陣代數運算，此篇論文被後世公認為近代矩陣理論和線性代數的基石。這段歷史顯示矩陣乘法——矩陣理論最重要的一個代數運算——絕對不是如數學課本所述那般理所當然；矩陣乘法定義隱含深層的意涵，否則為何眾多優秀數學家竟然看不出矩陣理當如此相乘。今天我們事後諸葛，已然明瞭矩陣代數之所以遲至十九世紀中葉才誕生的最主要原因在於人們一直無法確定矩陣的內涵和本質究竟為何。
美國數學家 Morris Kline (1908-1992) 說[1]：「矩陣理論在被創造前就已發展完善（the subject of matrix theory was well developed before it was created）。」這句話讓人聽得一頭霧水，要弄清楚這話的意思必須從矩陣的發展歷史說起。西元十七至十九世紀中葉，數學活動在歐洲以快速的步伐朝各領域繁盛發展，此時關於陣列（array）運算的研究全部集中於行列式理論，令人不解的是矩陣代數並未隨著行列式進行，矩陣理論足足落後行列式兩百年之久。西元 1850年，英國數學家 James Joseph Sylvester (1814-1897) 將矩形陣列命名為矩陣（matrix），但他並未定義矩陣乘法。1857 年，英國數學家 Arthur Cayley (1821-1895) 發表 A Memoir on the Theory of Matrices，他將矩陣從行列式抽離出來，視之為單獨數學物件，並定義完備的矩陣代數運算，此篇論文被後世公認為近代矩陣理論和線性代數的基石。這段歷史顯示矩陣乘法——矩陣理論最重要的一個代數運算——絕對不是如數學課本所述那般理所當然；矩陣乘法定義隱含深層的意涵，否則為何眾多優秀數學家竟然看不出矩陣理當如此相乘。今天我們事後諸葛，已然明瞭矩陣代數之所以遲至十九世紀中葉才誕生的最主要原因在於人們一直無法確定矩陣的內涵和本質究竟為何。
2009年3月12日 星期四
矩陣乘法的現代觀點 (三)
以分塊作為計算單元定義 AB
假設矩陣 $$A$$ 是 $$m\times n$$ 階，$$B$$ 是 $$n\times p$$ 階，則 $$AB$$ 可以相乘。同樣道理，將 $$A$$ 和 $$B$$ 以分塊矩陣形式表示，例如，$$A$$ 為 $$3\times 2$$ 分塊，$$B$$ 為 $$2\times 2$$ 分塊：
$$A=\begin{bmatrix}
A_{11}&A_{12}\\
A_{21}&A_{22}\\
A_{31}&A_{32}\end{bmatrix}$$ 和 $$B=\begin{bmatrix}
B_{11}&B_{12}\\
B_{21}&B_{22}\end{bmatrix}$$
如此 $$AB$$ 可以用分塊矩陣實現乘法運算。
假設矩陣 $$A$$ 是 $$m\times n$$ 階，$$B$$ 是 $$n\times p$$ 階，則 $$AB$$ 可以相乘。同樣道理，將 $$A$$ 和 $$B$$ 以分塊矩陣形式表示，例如，$$A$$ 為 $$3\times 2$$ 分塊，$$B$$ 為 $$2\times 2$$ 分塊：
$$A=\begin{bmatrix}
A_{11}&A_{12}\\
A_{21}&A_{22}\\
A_{31}&A_{32}\end{bmatrix}$$ 和 $$B=\begin{bmatrix}
B_{11}&B_{12}\\
B_{21}&B_{22}\end{bmatrix}$$
如此 $$AB$$ 可以用分塊矩陣實現乘法運算。
2009年3月11日 星期三
矩陣乘法的現代觀點 (二)
以列作為計算單元定義 AB
這個定義和以行作為計算單元的定義有類比的形式，我們視 $$AB$$ 的每一列為 $$B$$ 其列之線性組合，矩陣 $$A$$ 的對應列給出組合權重，如下：
$$\mathrm{row}_{i}(AB)= \mathrm{row}_{i}(A)\cdot\mathit{B} $$
這個定義和以行作為計算單元的定義有類比的形式，我們視 $$AB$$ 的每一列為 $$B$$ 其列之線性組合，矩陣 $$A$$ 的對應列給出組合權重，如下：
$$\mathrm{row}_{i}(AB)= \mathrm{row}_{i}(A)\cdot\mathit{B} $$
矩陣乘法的現代觀點 (一)
本文的閱讀等級：初級
高中數學課本將矩陣乘積 $$AB$$ 的定義建立於每個 $$(i,j)$$ 元的計算式上，進入大學之後，如果仍緊抓住這個定義不放，對於理解線性代數反而是個阻礙。從比較現代的角度來看，矩陣乘積有許多個更富含意義的等價運算方式。
高中數學課本將矩陣乘積 $$AB$$ 的定義建立於每個 $$(i,j)$$ 元的計算式上，進入大學之後，如果仍緊抓住這個定義不放，對於理解線性代數反而是個阻礙。從比較現代的角度來看，矩陣乘積有許多個更富含意義的等價運算方式。
訂閱：
文章 (Atom)