Untitled

马尔科夫矩阵¶

马尔科夫矩阵（Markov matrix）是指具有以下两个特性的矩阵：

1. 矩阵中的所有元素大于等于0；（因为马尔科夫矩阵与概率有关，而概率是非负的。）
2. 每一列的元素之和为1

对于马尔科夫矩阵，我们关心幂运算过程中的稳态（steady state）。与上一讲不同，指数矩阵关系特征值是否为0，而幂运算要达到稳态需要特征值为1。

根据上面两条性质，我们可以得出两个推论：

1. 马尔科夫矩阵必有特征值为1；
2. 其他的特征值的绝对值皆小于1。

使用第二十二讲中得到的公式进行幂运算u_k=A^ku_0=S\Lambda^kS^{-1}u_0=S\Lambda^kS^{-1}Sc=S\Lambda^kc=c_1\lambda_1^kx_1+c_2\lambda_2^kx_2+\cdots+c_n\lambda_n^kx_n，从这个公式很容易看出幂运算的稳态。比如我们取\lambda_1=1，其他的特征值绝对值均小于1，于是在经过k次迭代，随着时间的推移，其他项都趋近于0，于是在k\to\infty时，有稳态u_k=c_1x_1，这也就是初始条件u_0的第1个分量。

我们来证明第一个推论，取A=\begin{bmatrix}0.1&0.01&0.3\0.2&0.99&0.3\0.7&0&0.4\end{bmatrix}，则A-I=\begin{bmatrix}-0.9&0.01&0.3\0.2&-0.01&0.3\0.7&0&-0.6\end{bmatrix}。观察A-I易知其列向量中元素之和均为0，因为马尔科夫矩阵的性质就是各列向量元素之和为1，现在我们从每一列中减去了1，所以这是很自然的结果。而如果列向量中元素和为0，则矩阵的任意行都可以用“零减去其他行之和”表示出来，即该矩阵的行向量线性相关。

用以前学过的子空间的知识描述，当n阶方阵各列向量元素之和皆为1时，则有\begin{bmatrix}1\1\\vdots\1\end{bmatrix}在矩阵A-I左零空间中，即(A-I)^T行向量线性相关。而A特征值1所对应的特征向量将在A-I的零空间中，因为Ax=x\rightarrow(A-I)x=0。

另外，特征值具有这样一个性质：矩阵与其转置的特征值相同。因为我们在行列式一讲了解了性质10，矩阵与其转置的行列式相同，那么如果\det(A-\lambda I)=0，则有\det(A-\lambda I)^T=0，根据矩阵转置的性质有\det(A^T-\lambda I^T)=0，即\det(A^T-\lambda I)=0。这正是A^T特征值的计算式。

然后计算特征值\lambda_1=1所对应的特征向量，(A-I)x_1=0，得出x_1=\begin{bmatrix}0.6\33\0.7\end{bmatrix}，特征向量中的元素皆为正。

接下来介绍马尔科夫矩阵的应用，我们用麻省和加州这两个州的人口迁移为例：

\begin{bmatrix}u_{cal}\u_{mass}\end{bmatrix}{k+1}\begin{bmatrix}0.9&0.2\0.1&0.8\end{bmatrix}\begin{bmatrix}u{cal}\u_{mass}\end{bmatrix}_k，元素非负，列和为一。这个式子表示每年有10%的人口从加州迁往麻省，同时有20%的人口从麻省迁往加州。注意使用马尔科夫矩阵的前提条件是随着时间的推移，矩阵始终不变。

设初始情况\begin{bmatrix}u_{cal}\u_{mass}\end{bmatrix}0=\begin{bmatrix}0\1000\end{bmatrix}，我们先来看第一次迁徙后人口的变化情况：\begin{bmatrix}u{cal}\u_{mass}\end{bmatrix}_1=\begin{bmatrix}0.9&0.2\0.1&0.8\end{bmatrix}\begin{bmatrix}0\1000\end{bmatrix}=\begin{bmatrix}200\800\end{bmatrix}，随着时间的推移，会有越来越多的麻省人迁往加州，而同时又会有部分加州人迁往麻省。

计算特征值：我们知道马尔科夫矩阵的一个特征值为\lambda_1=1，则另一个特征值可以直接从迹算出\lambda_2=0.7。

计算特征向量：带入\lambda_1=1求A-I的零空间有\begin{bmatrix}-0.1&0.2\0.1&-0.2\end{bmatrix}，则x_1=\begin{bmatrix}2\1\end{bmatrix}，此时我们已经可以得出无穷步后稳态下的结果了。u_{\infty}=c_1\begin{bmatrix}2\1\end{bmatrix}且人口总数始终为1000，则c_1=\frac{1000}{3}，稳态时\begin{bmatrix}u_{cal}\u_{mass}\end{bmatrix}_{\infty}=\begin{bmatrix}\frac{2000}{3}\\frac{1000}{3}\end{bmatrix}。注意到特征值为1的特征向量元素皆为正。

为了求每一步的结果，我们必须解出所有特征向量。带入\lambda_2=0.7求A-0.7I的零空间有\begin{bmatrix}0.2&0.2\0.1&0.1\end{bmatrix}，则x_2=\begin{bmatrix}-1\1\end{bmatrix}。

通过u_0解出c_1, c_2，u_k=c_11^k\begin{bmatrix}2\1\end{bmatrix}+c_20.7^k\begin{bmatrix}-1\1\end{bmatrix}，带入k=0得u_0=\begin{bmatrix}0\1000\end{bmatrix}=c_1\begin{bmatrix}2\1\end{bmatrix}+c_2\begin{bmatrix}-1\1\end{bmatrix}，解出c_1=\frac{1000}{3}, c_2=\frac{2000}{3}。

另外，有时人们更喜欢用行向量，此时将要使用行向量乘以矩阵，其行向量各分量之和为1。

傅里叶级数¶

在介绍傅里叶级数（Fourier series）之前，先来回顾一下投影。

设q_1,q_2,\cdots q_n为一组标准正交基，则向量v在该标准正交基上的展开为v=x_1q_1+x_2q_2+\cdots+x_nq_n，此时我们想要得到各系数x_i的值。比如求x_1的值，我们自然想要消掉除x_1q_1外的其他项，这时只需要等式两边同乘以q_1^T，因为的q_i向量相互正交且长度为1，则q_i^Tq_j=0, q_i^2=1所以原式变为q_1^Tv=x_1。

写为矩阵形式有\Bigg[q_1\ q_2\ \cdots\ q_n\Bigg]\begin{bmatrix}x_1\x_2\\vdots\x_n\end{bmatrix}=v，即Qx=v。所以有x=Q^{-1}v，而在第十七讲我们了解到标准正交基有Q^T=Q^{-1}，所以我们不需要计算逆矩阵可直接得出x=Q^Tv。此时对于x的每一个分量有x_i=q_i^Tv。

接下来介绍傅里叶级数。先写出傅里叶级数的展开式：

傅里叶发现，如同将向量v展开（投影）到向量空间的一组标准正交基中，在函数空间中，我们也可以做类似的展开。将函数f(x)投影在一系列相互正交的函数中。函数空间中的f(x)就是向量空间中的v；函数空间中的1,\cos x,\sin x,\cos 2x,\sin 2x,\cdots就是向量空间中的q_1,q_2,\cdots,q_n；不同的是，函数空间是无限维的而我们以前接触到的向量空间通常是有限维的。

再来介绍何为“函数正交”。对于向量正交我们通常使用两向量内积（点乘）为零判断。我们知道对于向量v,w的内积为v^Tw=v_1w_1+v_2w_2+\cdots+v_nw_n=0，也就是向量的每个分量之积再求和。而对于函数f(x)\cdot g(x)内积，同样的，我们需要计算两个函数的每个值之积而后求和，由于函数取值是连续的，所以函数内积为：

在本例中，由于傅里叶级数使用正余弦函数，它们的周期都可以算作2\pi，所以本例的函数点积可以写作f^Tg=\int_0^{2\pi}f(x)g(x)\mathrm{d}x。我来检验一个内积\int_0^{2\pi}\sin{x}\cos{x}\mathrm{d}x=\left.\frac{1}{2}\sin^2x\right|_0^{2\pi}=0，其余的三角函数族正交性结果可以参考傅里叶级数的“希尔伯特空间的解读”一节。

最后我们来看\cos x项的系数是多少（a_0是f(x)的平均值）。同向量空间中的情形一样，我们在等式两边同时做\cos x的内积，原式变为\int_0^{2\pi}f(x)\cos x\mathrm{d}x=a_1\int_0^{2\pi}\cos^2x\mathrm{d}x，因为正交性等式右边仅有\cos x项不为零。进一步化简得a_1\pi=\int_0^{2\pi}f(x)\cos x\mathrm{d}x\rightarrow a_1=\frac{1}{\pi}\int_0^{2\pi}f(x)\cos x\mathrm{d}x。

于是，我们把函数f(x)展开到了函数空间的一组标准正交基上。