矩陣乘法

维基百科，自由的百科全书

這篇文章給出多種矩陣相乘方法的綜述。

[编辑] 一般矩陣乘積

矩陣相乘最重要的方法當然是一般矩陣乘積了，它只有在第一個矩陣的行數和第二個矩陣的列數相同時才有定義。一般單指矩陣乘積時，指的便是一般矩陣乘積。若A為m×n矩陣，B為n×p矩陣，則他們的乘積AB(有時記做A · B)會是一個m×p矩陣。其乘積矩陣的元素如下面式子得出：

$(AB)_{ij} = \sum_{r=1}^n a_{ir}b_{rj} = a_{i1}b_{1j} + a_{i2}b_{2j} + \cdots + a_{in}b_{nj}.$

以上是用矩陣單元的代數系統來說明這類乘法的抽象性質。

[编辑] 由定義直接計算

左邊的圖表示出要如何計算AB的(1,2)和(3,3)元素，當A是個4×2矩陣和B是個2×3矩陣時。分別來自兩個矩陣的元素都依箭頭方向而兩兩配對，把每一對中的兩個元素相乘，再把這些乘積加總起來，最後得到的值即為箭頭相交位置的值。

$(AB)_{1,2} = \sum_{r=1}^2 a_{1,r}b_{r,2} = a_{1,1}b_{1,2}+a_{1,2}b_{2,2}$

$(AB)_{3,3} = \sum_{r=1}^2 a_{3,r}b_{r,3} = a_{3,1}b_{1,3}+a_{3,2}b_{2,3}$

[编辑] 係數－向量方法

這種矩陣乘積亦可由稍微不同的觀點來思考：把向量和各係數相乘後相加起來。設A和B是兩個給定如下的矩陣：

$\mathbf{A} = \begin{bmatrix} a_{1,1} & a_{1,2} & \dots \\ a_{2,1} & a_{2,2} & \dots \\ \vdots & \vdots & \ddots \end{bmatrix}$ and $\mathbf{B} = \begin{bmatrix} b_{1,1} & b_{1,2} & \dots \\ b_{2,1} & b_{2,2} & \dots \\ \vdots & \vdots & \ddots \end{bmatrix}$

則

$\mathbf{AB} = \begin{bmatrix} a_{1,1} \begin{bmatrix} b_{1,1} & b_{1,2} & \dots \end{bmatrix} + a_{1,2} \begin{bmatrix} b_{2,1} & b_{2,2} & \dots \end{bmatrix} + \cdots \\\\ a_{2,1} \begin{bmatrix} b_{1,1} & b_{1,2} & \dots \end{bmatrix} + a_{2,2} \begin{bmatrix} b_{2,1} & b_{2,2} & \dots \end{bmatrix} + \cdots \\ \vdots \end{bmatrix}$

舉個例子來說:

$\begin{bmatrix} 1 & 0 & 2 \\ -1 & 3 & 1 \end{bmatrix} \cdot \begin{bmatrix} 3 & 1 \\ 2 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 1 \begin{bmatrix} 3 & 1 \end{bmatrix} + 0 \begin{bmatrix} 2 & 1 \end{bmatrix} + 2 \begin{bmatrix} 1 & 0 \end{bmatrix} \\ -1 \begin{bmatrix} 3 & 1 \end{bmatrix} + 3 \begin{bmatrix} 2 & 1 \end{bmatrix} + 1 \begin{bmatrix} 1 & 0 \end{bmatrix} \end{bmatrix} = \begin{bmatrix} \begin{bmatrix} 3 & 1 \end{bmatrix} + \begin{bmatrix} 0 & 0 \end{bmatrix} + \begin{bmatrix} 2 & 0 \end{bmatrix} \\ \begin{bmatrix} -3 & -1 \end{bmatrix} + \begin{bmatrix} 6 & 3 \end{bmatrix} + \begin{bmatrix} 1 & 0 \end{bmatrix} \end{bmatrix}$

$= \begin{bmatrix} 5 & 1 \\ 4 & 2 \end{bmatrix}$

左面矩陣的列為為係數表，右邊矩陣為向量表。例如，第一列是[1 0 2]，因此將1乘上第一個向量，0乘上第二個向量，2則乘上第三個向量。

[编辑] 向量表方法

一般矩陣乘積也可以想為是行向量和列向量的內積。若A和B為給定如下的矩陣：

$\mathbf{A} = \begin{bmatrix} a_{1,1} & a_{1,2} & a_{1,3} & \dots \\ a_{2,1} & a_{2,2} & a_{2,3} & \dots \\ a_{3,1} & a_{3,2} & a_{3,3} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ \vdots \end{bmatrix}$ and $\mathbf{B} = \begin{bmatrix} b_{1,1} & b_{1,2} & b_{1,3} & \dots \\ b_{2,1} & b_{2,2} & b_{2,3} & \dots \\ b_{3,1} & b_{3,2} & b_{3,3} & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} B_1 & B_2 & B_3 & \dots \end{bmatrix}$

其中

A₁是由所有a_1,x元素所組成的向量，A₂是由所有a_2,x元素所組成的向量，以此類推。

b₁是由所有b_x,1元素所組成的向量，B₂是由所有b_x,2元素所組成的向量，以此類推。

則

$\mathbf{AB} = \begin{bmatrix} A_1 \\ A_2 \\ A_3 \\ \vdots \end{bmatrix} * \begin{bmatrix} B_1 & B_2 & B_3 & \dots \end{bmatrix} = \begin{bmatrix} (A_1 \cdot B_1) & (A_1 \cdot B_2) & (A_1 \cdot B_3) & \dots \\ (A_2 \cdot B_1) & (A_2 \cdot B_2) & (A_2 \cdot B_3) & \dots \\ (A_3 \cdot B_1) & (A_3 \cdot B_2) & (A_3 \cdot B_3) & \dots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$

[编辑] 性質

矩陣乘法是不可交換的(即AB ≠ BA)，除了一些較特別的情況。很清楚可以知道，不可能預期說在改變向量的部份後還能得到相同的結果，而且第一個矩陣的行數必須要和第二個矩陣的列數相同，也可以看出為什麼矩陣相乘的順序會影響其結果。

雖然矩陣乘法是不可交換的，但AB和BA的行列式總會是一樣的(當A、B是同樣大小的方陣時)。其解釋在行列式條目內。

當A、B可以被解釋為線性算子，其矩陣乘積AB會對應為兩個線性算子的複合函數，其中B先做用。

[编辑] 演算法

The complexity of matrix multiplication, if carried out naively, is O(n³), but more efficient algorithms do exist. Strassen's algorithm, devised by Volker Strassen in 1969 and often referred to as "fast matrix multiplication", is based on a clever way of multiplying two 2 × 2 matrices which requires only 7 multiplications (instead of the usual 8). Applying this trick recursively gives an algorithm with a cost of $O( n^{\log_{2}7}) \approx O(n^{2.807})$ . In practice, though, it is rarely used since it is awkward to implement and it lacks numerical stability. The constant factor involved is about 4.695 asymptotically; Winograd algorithm improves on this slightly by reducing it to an asymptotic 4.537.

The best algorithm currently known, which was presented by Don Coppersmith and S. Winograd in 1990, has an asymptotic complexity of O(n^2.376). It is similar to Strassen's algorithm: a clever way is devised for multiplying two k × k matrices with less than k³ multiplications, and this technique is applied recursively. However, the constant implied in the O(n^2.376) result is so large that the Coppersmith–Winograd algorithm is only worthwhile for matrices that are too big to handle on present-day computers.

Since any algorithm for multiplying two n × n matrices has to process all n² entries, it cannot run faster than O(n²). Most researchers believe that an optimal algorithm will run in essentially O(n²) time (Robinson, 2005).

[编辑] 純量乘積

矩陣A = (a_ij)和純量r的純量乘積rA的矩陣大小和A一樣，rA的各元素定義如下：

$(rA)_{ij} = r \cdot a_{ij}. \,$

若我們考慮於一個環的矩陣時，上述的乘積有時會稱做左乘積，而右乘積的則定義為

$(Ar)_{ij} = a_{ij} \cdot r. \,$

當環是可交換時，例如實數體或複體體，這兩個乘積是相同的。但無論如何，若環是不可交換的話，如四元數，他們可能會是不同的。例如，

$i\begin{bmatrix} i & 0 \\ 0 & j \\ \end{bmatrix} = \begin{bmatrix} -1 & 0 \\ 0 & k \\ \end{bmatrix} \ne \begin{bmatrix} -1 & 0 \\ 0 & -k \\ \end{bmatrix} = \begin{bmatrix} i & 0 \\ 0 & j \\ \end{bmatrix}i$

[编辑] 阿達馬乘積

給定兩個相同維度的矩陣，我們有阿達馬乘積，或稱做分素乘積(entrywise product)。兩個m×n矩陣A、B的阿達馬乘積標記為A • B，為一定義為 (A•B)_ij = a_ijb_ij的m×n矩陣。例如，

$\begin{bmatrix} 1 & 3 & 2 \\ 1 & 0 & 0 \\ 1 & 2 & 2 \end{bmatrix} \bullet \begin{bmatrix} 0 & 0 & 2 \\ 7 & 5 & 0 \\ 2 & 1 & 1 \end{bmatrix} = \begin{bmatrix} 1 \cdot 0 & 3 \cdot 0 & 2 \cdot 2 \\ 1 \cdot 7 & 0 \cdot 5 & 0 \cdot 0 \\ 1 \cdot 2 & 2 \cdot 1 & 2 \cdot 1 \end{bmatrix} = \begin{bmatrix} 0 & 0 & 4 \\ 7 & 0 & 0 \\ 2 & 2 & 2 \end{bmatrix}$

需注意的是，阿達馬乘積是克羅內克乘積的子矩陣。

[编辑] 克羅內克乘積

主條目: 克羅內克乘積.

給定任兩個矩陣A和B，我們可以得到兩個矩陣的直積，或稱為克羅內克乘積A⊗B，其定義如下

$\begin{bmatrix} a_{11}B & a_{12}B & \cdots & a_{1n}B \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{bmatrix}.$

當A是一m×n矩陣和B是一p×r矩陣時，A⊗B會是一mp×nr矩陣，而且此一乘積也是不可交換的。

舉個例子，

$\begin{bmatrix} 1 & 2 \\ 3 & 1 \\ \end{bmatrix} \otimes \begin{bmatrix} 0 & 3 \\ 2 & 1 \\ \end{bmatrix} = \begin{bmatrix} 1\cdot 0 & 1\cdot 3 & 2\cdot 0 & 2\cdot 3 \\ 1\cdot 2 & 1\cdot 1 & 2\cdot 2 & 2\cdot 1 \\ 3\cdot 0 & 3\cdot 3 & 1\cdot 0 & 1\cdot 3 \\ 3\cdot 2 & 3\cdot 1 & 1\cdot 2 & 1\cdot 1 \\ \end{bmatrix} = \begin{bmatrix} 0 & 3 & 0 & 6 \\ 2 & 1 & 4 & 2 \\ 0 & 9 & 0 & 3 \\ 6 & 3 & 2 & 1 \end{bmatrix}$ .

若A和B分別表示兩個線性算子V₁ → W₁和V₂ → W₂，A⊗B便為其映射的張量乘積，V₁ ⊗ V₂ → W₁ ⊗ W₂.

[编辑] 共同性質

上述三種乘積都符合結合律：

A(BC) = (AB)C

以及分配律:

A(B + C) = AB + AC

(A + B)C = AC + BC

而且和純量乘積相溶：

c(AB) = (cA)B

(Ac)B = A(cB)

(AB)c = A(Bc)

注意上述三個分開的表示式只有在純量體的乘法及加法是可交換(即純量體為一可交換環)時會相同。

[编辑] 另見

Strassen演算法 (1969)
Winograd演算法 (1980)
Coppersmith–Winograd演算法 (1990)
邏輯矩陣
矩陣鏈乘積
逆矩陣
關係複合
BLAS
矩陣加法

[编辑] 外部連結

[编辑] 參考

Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969.
Coppersmith, D., Winograd S., Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9, p. 251-280, 1990.
Horn, Roger; Johnson, Charles: "Topics in Matrix Analysis", Cambridge, 1994.
Robinson, Sara, Toward an Optimal Algorithm for Matrix Multiplication, SIAM News 38(9), November 2005.

来自“http://zh.wikipedia.org../../../%E7%9F%A9/%E9%99%A3/%E4%B9%98/%E7%9F%A9%E9%99%A3%E4%B9%98%E6%B3%95.html”

页面分类: 矩陣 | 二元運算