矩阵加速
JRzyh
·
·
题解
从矩阵基础讲起。
\large\texttt{Part 1 基础}
\large\texttt{定义}
由 n\times m 个数排成 m 行 n 列矩形的数表
\left(\begin{array}{cc}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}\\
\end{array}\right)
称为一个 m\times n 的矩阵，记作 A。其中 a_{ij} 称为第 i 行第 j 列的元素。
\large\texttt{特殊矩阵}
\texttt{零矩阵}
所有元素都是零的矩阵。
\left(\begin{array}{cc}
0&0&\cdots&0\\
0&0&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&0\\
\end{array}\right)
记为 \texttt{0} 。^{(1)}
\texttt{对角矩阵}
在一个 n\times n 的矩阵里，只有主对角线有值。
\left(\begin{array}{cc}
a_{11}&0&\cdots&0\\
0&a_{22}&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&a_{nn}\\
\end{array}\right)
\texttt{单位矩阵}
一个对角矩阵切对角线上都是 1。
\left(\begin{array}{cc}
1&0&\cdots&0\\
0&1&\cdots&0\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&1\\
\end{array}\right)
记作 I 。
\texttt{上三角矩阵}
只有右上的一部分有值，主对角线以下都是 0。
\left(\begin{array}{cc}
a_{11}&a_{12}&\cdots&a_{1n}\\
0&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
0&0&\cdots&a_{nn}\\
\end{array}\right)
主要的特殊矩阵就这些。^{(2)}
\large\texttt{矩阵运算}
\texttt{相等}
矩阵 A,B 相等当且仅当他们大小相等且对于所有 ij 都有 a_{ij}=b_{ij}
官方定义，总结成一句话，就是他们长的一模一样。
\left(\begin{array}{cc}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}\\
\end{array}\right)=\left(\begin{array}{cc}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}\\
\end{array}\right)
\texttt{矩阵加法}
若 C=A+B 则对于所有 ij 都有 c_{ij}=a_{ij}+b_{ij} 。
要求 A 的大小要等于 B 的大小。
总结成一句话，一个一个加。
\left(\begin{array}{cc}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}\\
\end{array}\right)+\left(\begin{array}{cc}
b_{11}&b_{12}&\cdots&b_{1n}\\
b_{21}&b_{22}&\cdots&b_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
b_{m1}&b_{m2}&\cdots&b_{mn}\\
\end{array}\right)=\left(\begin{array}{cc}
a_{11}+b_{11}&a_{12}+b_{12}&\cdots&a_{1n}+b_{1n}\\
a_{21}+b_{21}&a_{22}+b_{22}&\cdots&a_{2n}+b_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}+b_{m1}&a_{m2}+b_{m2}&\cdots&a_{mn}+b_{mn}\\
\end{array}\right)
减同理。
\texttt{矩阵的数量乘法}
用一个数 k 去乘 A 就等于 k 成他的每一位。
总结成一句话，一个一个乘。
k\left(\begin{array}{cc}
a_{11}&a_{12}&\cdots&a_{1n}\\
a_{21}&a_{22}&\cdots&a_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
a_{m1}&a_{m2}&\cdots&a_{mn}\\
\end{array}\right)=\left(\begin{array}{cc}
ka_{11}&ka_{12}&\cdots&ka_{1n}\\
ka_{21}&ka_{22}&\cdots&ka_{2n}\\
\vdots&\vdots&\ddots&\vdots\\
ka_{m1}&ka_{m2}&\cdots&ka_{mn}\\
\end{array}\right)
\texttt{矩阵乘法}
首先要求 A 的列数要等于 B 的行数。
若 A=(a_{ij})_{m\times r} ，B=(b_{ij})_{r\times n}，则乘出的矩阵大小是 C=(c_{ij})_{m\times n}
其中
c_{ij}=\sum_{k=1}^n a_{ik}·b_{kj}
称为 A 与 B 的乘积，记做 C=AB。^{(3)}
矩阵乘法的性质：
任何矩阵乘 \texttt{0} 得 \texttt{0}：\texttt{0}A=A\texttt{0}=\texttt{0}
任何矩阵乘 I 得本身：IA=AI=A
结合律：A(BC)=(AB)C
左分配律：A(B+C)=AB+AC
右分配律：(B+C)A=BA+CA
注意矩阵乘法没有交换律。
\large\texttt{Part 2 应用}
\large\texttt{矩阵快速幂}
求一个矩阵 A 的 k 次方。
现在来分析一下问题，就是求：
\begin{matrix} n \\ \overbrace{ A\times A\times A\times A\times \dots\times A } \end{matrix}
根据结合律：
\begin{matrix} \frac{n}{2} \\ \overbrace{ ( A\times A\times \dots\times A) } \end{matrix}
\begin{matrix} ~~~\frac{n}{2} \\\times \overbrace{ (A\times A\times \dots\times A) } \end{matrix}
就是 (A^{\frac{n}{2}})^2
分治快速幂的性质仍然在。^{(4)}
就和快速幂一样做就好了
\large\texttt{斐波那契数列}
精典！
构造一个 1\times 2 的矩阵：
\left(\begin{array}{cc}
F_{2}&F_{1}\\
\end{array}\right)
和一个 2\times 2 的矩阵：
\left(\begin{array}{cc}
1&1\\
1&0\\
\end{array}\right)
两个做矩阵乘法：
c_{11}=\sum_{k=1}^n a_{ik}·b_{kj}=a_{11}\times b_{11}+a_{12}\times b_{21}=F_2+F_1=F_3
c_{12}=\sum_{k=1}^n a_{ik}·b_{kj}=a_{11}\times b_{12}+a_{12}\times b_{22}=F_2
结果是
\left(\begin{array}{cc}
F_{3}&F_{2}\\
\end{array}\right)
看到没有，往前推了一位，我们只需要将他乘 n-1 个矩阵，就能得到答案，这样就可以用快速幂求。
\large\texttt{矩阵加速}
搞一道例题
F_x= \begin{cases} 1 & x \in\{1,2,3\}\\ F_{x-1}+F_{x-3} & x \geq 4 \end{cases}
求 F_x 。
还是需要两个矩阵，其中一个当然是
\left(\begin{array}{cc}
F_{3}&F_{2}&F_{1}\\
\end{array}\right)
现在看看如何构造出单位矩阵。
下面一个表格，展示了他每行每列的意义
|
F_{k-1} |
F_{k-2} |
F_{k-3} |
| F_{k}~ |
|
|
|
| F_{k-1} |
|
|
|
| F_{k-2} |
|
|
|
他里面要填什么呢？
显然 F_{k}=1\times F_{k-1}+0\times F_{k-2}+1\times F_{k-3}
所以第一行是
|
F_{k-1} |
F_{k-2} |
F_{k-3} |
| F_{k}~ |
1 |
0 |
1 |
| F_{k-1} |
|
|
|
| F_{k-2} |
|
|
|
F_{k-1}=1\times F_{k-1}+0\times F_{k-2}+0\times F_{k-3}
F_{k-2}=0\times F_{k-1}+1\times F_{k-2}+0\times F_{k-3}
表填完是
|
F_{k-1} |
F_{k-2} |
F_{k-3} |
| F_{k}~ |
1 |
0 |
1 |
| F_{k-1} |
1 |
0 |
0 |
| F_{k-2} |
0 |
1 |
0 |
单位矩阵就求得了。
\left(\begin{array}{cc}
1&0&1\\
1&0&0\\
0&1&0\\
\end{array}\right)
$(2):$ 还有纯量矩阵，对称矩阵，下三角矩阵等，用的不多，不讲了。
$(3):$ 也有做 $A\times B$，$A·B$ 的。
$(4):$ 其实快速幂分两种，常见的是二进制快速幂，经常有人把他们混为一谈。分治快速幂的基础是 $(a^{\frac{n}{2}})^2=a$ 。二进制快速幂是 $\sum 2^{k_i}=n$ 则 $\prod a^{(2^{k_i})}=a^n$ 。