矩阵乘法及其代价

映射的复合

乘积 $AB$ 是先作用 $B$ 再作用 $A$ 得到的映射： $(AB)\mathbf{x}=A(B\mathbf{x})$ 。乘积的第 $(i,j)$ 个元素是 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列的点积，所以形状必须匹配： $m\times n$ 矩阵乘 $n\times p$ 矩阵得 $m\times p$ 矩阵。乘法满足结合律 $(AB)C=A(BC)$ 和对加法的分配律，但一般不满足交换律： $AB\neq BA$ ，因为两个操作的顺序很重要。

(AB)_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj},\qquad (AB)^{T}=B^{T}A^{T}

(1)

对 $m\times n$ 与 $n\times p$ 矩阵计算 $AB$ 需要 $mnp$ 次乘加（约 $2mnp$ 次浮点运算）。两个 $n\times n$ 矩阵就是 $n^3$ ： $n$ 翻倍，工作量变成 8 倍。矩阵乘向量只需 $n^2$ 。因为乘法满足结合律，括号的位置不改变结果，却可能极大地改变代价。

顺序有两重意义取

A=\begin{pmatrix}1&2\\0&1\end{pmatrix}

、

B=\begin{pmatrix}0&1\\1&0\end{pmatrix}

：

AB=\begin{pmatrix}2&1\\1&0\end{pmatrix}

，而

BA=\begin{pmatrix}0&1\\1&2\end{pmatrix}

，顺序改变了结果。括号则改变代价：对

n\times n

矩阵

A,B

和向量

\mathbf{v}

，

(AB)\mathbf{v}

需要

n^3+n^2

次乘加，而

A(B\mathbf{v})

只需

2n^2

次。

n=1000

时，是十亿次对两百万次。

形状规则： $(m\times n)(n\times p)=(m\times p)$ ；内侧的维数必须一致。
不可交换：一般 $AB\neq BA$ ，因此不要交换因子。
代价： $mnp$ 次乘加；矩阵乘向量是 $n^2$ ，矩阵乘矩阵是 $n^3$ 。

从向量一侧加括号当一串矩阵以向量结尾时，要从向量一侧开始乘：

A(B(C\mathbf{v}))

只用到矩阵乘向量。组合风险

\mathbf{w}^{T}\Sigma\mathbf{w}

要算成

\mathbf{w}\cdot(\Sigma\mathbf{w})

，而不是先由

\mathbf{w}

构造出一个矩阵。

实验：评分内容

乘积 AB20 分
乘积 BA15 分
乘积的形状10 分
数乘加次数15 分
两种加括号的方式20 分
为什么加括号很重要20 分

映射的复合

(AB)_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj},\qquad (AB)^{T}=B^{T}A^{T}

(1)

顺序有两重意义取

A=\begin{pmatrix}1&2\\0&1\end{pmatrix}

、

B=\begin{pmatrix}0&1\\1&0\end{pmatrix}

：

AB=\begin{pmatrix}2&1\\1&0\end{pmatrix}

，而

BA=\begin{pmatrix}0&1\\1&2\end{pmatrix}

，顺序改变了结果。括号则改变代价：对

n\times n

矩阵

A,B

和向量

\mathbf{v}

，

(AB)\mathbf{v}

需要

n^3+n^2

次乘加，而

A(B\mathbf{v})

只需

2n^2

次。

n=1000

时，是十亿次对两百万次。

形状规则： $(m\times n)(n\times p)=(m\times p)$ ；内侧的维数必须一致。
不可交换：一般 $AB\neq BA$ ，因此不要交换因子。
代价： $mnp$ 次乘加；矩阵乘向量是 $n^2$ ，矩阵乘矩阵是 $n^3$ 。

从向量一侧加括号当一串矩阵以向量结尾时，要从向量一侧开始乘：

A(B(C\mathbf{v}))

只用到矩阵乘向量。组合风险

\mathbf{w}^{T}\Sigma\mathbf{w}

要算成

\mathbf{w}\cdot(\Sigma\mathbf{w})

，而不是先由

\mathbf{w}

构造出一个矩阵。

实验：评分内容

乘积 AB20 分
乘积 BA15 分
乘积的形状10 分
数乘加次数15 分
两种加括号的方式20 分
为什么加括号很重要20 分

映射的复合

实验：评分内容

登录后即可运行你的代码。

矩阵乘法及其代价

映射的复合

实验：评分内容

登录后即可运行你的代码。