从一个递推式谈谈线性空间


  本篇博文将从一个简单的问题出发,并使用两种方法求解。笔者希望通过写这篇博文融汇一下自己所学的知识、加深直觉上的理解并做分享。笔者非数学科班出身,如有错误之处请斧正。

问题描述:

  已知有递推式

         \(s_{n} = -s_{n-1}+6s_{n-2}\,\,\)    (\(\,n\,\ge\,2\,)\,\,\,\,(0)\)

  其中

         \(s_{0}\,=\,7\) , \(s_{1}\,=\,4\)

  求\(\,s_n\,\)的通项公式

谈谈解法一:用辅助方程求解


  由题给定的递推关系可知这是一个二阶常系数线性齐次差分方程,它的辅助方程是
$$x^2\,=\,-x\,+\,6$$
  把方程整理一下
$$x^2\,+\,x\,-6\,=\,0$$
$$\Rightarrow (\,x\,+\,3\,)(\,x\,-\,2\,)=\,0$$
  解出 \(\lambda_{1}=-3,\lambda_{2}=2\)
  因为 \(\lambda_{1}\) 不等于 \(\lambda_{2}\),所以有$$s_{n}=c_{1}\lambda_{1}^{n}+c_{2}\lambda_{2}^n$$
  (如果\(\lambda_{1} = \lambda_{2}=\lambda\),则有\(s_{n}=(c_{1}+nc_{2})\lambda^{n}\) )
  接着把\(s_0\,,s_1\,,\lambda_1\,,\lambda_2\)代入求出参数\(c_{1},c_{2}\)

$$\left\{\begin{matrix}
c_{1}(-3)^0+c_{2}2^0=7 \\
c_{1}(-3)^1+c_{2}2^1=4
\end{matrix}\right.$$
  解得\(c_1=2\,,\,c_2=5\,\Longrightarrow\,s_n=2\cdot (-3)^n+5\cdot 2^n\)

辅助方程来得太突然?

  这个辅助方程来自哪里?为什么会有这样的辅助方程?我们一步一步来探讨。
  记得读高中的时候,数学老师也曾教过用这种辅助方程(或者叫特征方程)求解,但是当时实在是不能理解,不知所以然,总觉得辅助方程来得太突然。今天,我尝试用线性代数的知识去诠释这个辅助方程
  假设有递推式
$$s_{n+k}+c_{n+k-1}s_{n+k-1}+c_{n+k-2}s_{n+k-2}+\ldots+c_{n}s_{n}=0$$
  若\(a_{n},b_{n}\)都满足上述递推式,显然数列\(a_{n}±b_{n}\)也满足递推式。即满足该递推式的数列集合构成了一个线性空间。
  因此,我们提出的问题,其递推式同样也形成了一个线性空间。另一方面,递推式本身是可以表示成矩阵\(A=\begin{bmatrix} -1 &6 \\ 1 &0 \end{bmatrix}
\)通过这个矩阵可以把\(\begin{bmatrix} s_{n}\\s_{n-1} \end{bmatrix}
\)变换成\(\begin{bmatrix} s_{n+1}\\s_{n} \end{bmatrix}\)
  比如:\(\begin{bmatrix}
-1 &6 \\
1 &0 \end{bmatrix}
\cdot\begin{bmatrix} s_{1}\\
s_{0} \end{bmatrix}=\begin{bmatrix}
s_{2}\\
s_{1}
\end{bmatrix}\)
  假设矩阵\(A\)的特征值是\(\lambda_0,\lambda_1\),对应于有特征向量\(V_0,V_1\).
  把初始化向量(意思是这个向量决定了整个数列)\(V_{init}=\begin{bmatrix} s_{1}\\s_{0} \end{bmatrix}\)
  表示成特征向量的线型组合,即\(\begin{bmatrix} s_{1}\\s_{0} \end{bmatrix}=c_{0}V_{0}+c_{1}V_{1}\),求出了\(c_{0},c_{1}\)后,
$$A^{n-1}
\begin{bmatrix}
s_{1} \\
s_{0}
\end{bmatrix}
=c_{0}\lambda_{0}^{n-1}V_{0}+c_{1}\lambda_{1}^{n-1}V_{1}
=\begin{bmatrix}
s_{n} \\
s_{n-1}
\end{bmatrix}\,,\,\,(n\geq 2)$$
  到这里就可以求出\(s_{n}\)的通项公式了。
  本文就是对这个上述过程进行一个剖析,如果读者你已经看懂了就不必费时往下看了。

特征值与特征向量定义

定义:设\(A\) 是\(n\)阶矩阵,如果数\(\lambda\)和\(n\)维非零列向量\(x\)关系式
$$Ax=\lambda x\,\,\,(1)$$成立,那么,这样的数\(\lambda\)称为矩阵\(A\)的特征值,非零向量\(x\)称为\(A\)的对应于特征值\(\lambda\)的特征向量。

关键是求出特征值

  上面的关系式可以写成 \((A-\lambda E)x=0,\)令它有非零解的充分必要条件是系数行列式
$$|A-\lambda E|=0\,\,\,(2)$$
  到这里,我们可以看到,求解特征值其实就是求解使这个行列式等于0的\(\lambda\)值。关于特征值和特征向量的具体求解过程可以参考同济大学的教学资料 ,这份资料很明了地介绍了特征值和特征向量的求解方法,这里就不再赘述了。要注意的是,特征值\(\lambda\)可以不唯一,也可能会有重根。特征向量在于方向,而不在于长度。

线性空间的定义及递推式所阐述的线性空间

  来看看问题中的递推式\(\,\,s_{n} = -s_{n-1}+6s_{n-2}\,\,,\,\,n\ge\,2\,\)
  数学里的空间到底是什么,其实就是一个集合,然后再给这个集合加上一些定义(结构)和运算规则,就有了线性空间,仿射空间,巴拿赫空间等。
  我们说,这个递推式也定义了一个线性空间,那么,这个线性空间(集合)里的元素是什么呢?是一个满足递推式的数列。正如前面说到的,若\(a_{n},b_{n}\)都满足上述递推式,显然数列\(a_{n}±b_{n}\)也满足递推式。显然,这个空间(集合)有线性空间的运算规则(性质),所以,这个空间是一个线性空间。
  那么,这个元素的维度是多少呢?表面上看是是无限(数列\(s_{n}\)可以无限长),但我们知道,只要连续的两个元素\(s_{k},s_{k+1},(k为非负整数)\)确定了,那么整个数列就可以确定了(根据递推式递推出来)。所以,数列可以用最前面的元素\(s_{0},s_{1}\)做代表,这样一来,这个线性空间里的每一个元素(数列)i就会有一个\((s_{i0},s_{i1})\)二元组相对应,也就是可以用二维平面上的一个点表示。
  前面说到,
  “递推式本身是可以表示成矩阵\(A=\begin{bmatrix} -1 &6 \\ 1 &0 \end{bmatrix}\)通过乘这个矩阵可以把\(\begin{bmatrix} s_{n}\\s_{n-1} \end{bmatrix}\)变换成\(\begin{bmatrix} s_{n+1}\\s_{n} \end{bmatrix}\)”
  我们知道,矩阵表示一种运动,乘一次矩阵表示运动一次。那如果多次乘一个矩阵会怎么样呢? \(A\begin{bmatrix} s_{0}\\s_{1} \end{bmatrix}=
\begin{bmatrix} s_{1}\\s_{2} \end{bmatrix},
A\begin{bmatrix} s_{1}\\s_{2} \end{bmatrix}=
\begin{bmatrix} s_{2}\\s_{3} \end{bmatrix},
A\begin{bmatrix} s_{2}\\s_{3} \end{bmatrix}=
\begin{bmatrix} s_{3}\\s_{4} \end{bmatrix},
\cdots
\) ,那将会“一步一步地移动”。

三步揭秘辅助方程的生世并求解

  前面说到,$$A^{n-1}
\begin{bmatrix}
s_{1} \\
s_{0}
\end{bmatrix}
=c_{0}\lambda_{0}^{n-1}V_{0}+c_{1}\lambda_{1}^{n-1}V_{1}
=\begin{bmatrix}
s_{n} \\
s_{n-1}
\end{bmatrix}\,,\,\,(n\geq 2)$$
  乘一个矩阵的高次幂,一步一步迭代求出\(s_{n}\),这样计算起来显然不方便,所以这里,我们就要利用特征值和特征向量了。
  第一步,先求解矩阵\(
\begin{bmatrix}
-1&6 \\
1&0
\end{bmatrix}\)特征值和特征向量,
$$|A-\lambda E|=\begin{vmatrix}
-1-\lambda &6\\
1 & 0-\lambda
\end{vmatrix}=0$$
$$\Rightarrow (\lambda+3)(\lambda-2)=0$$
  解得特征值\(\lambda_{0}=-3,\lambda_{1}=2\)以及对应的特征向量\(V_{0}=\begin{bmatrix}
3\\
-1
\end{bmatrix},V_{1}
=\begin{bmatrix}
2\\
1
\end{bmatrix}
\)
  不难发现,特征值的求解方程就是所谓的辅助方程,即辅助方程由此而来。
  第二步,用特征向量的线性组合表示向量\(\begin{bmatrix}
s_{1} \\
s_{0}
\end{bmatrix} \)
$$\begin{bmatrix} s_{1}\\s_{0} \end{bmatrix}=c_{0}V_{0}+c_{1}V_{0}$$
$$\Rightarrow \begin{bmatrix}
4\\
7 \end{bmatrix}
=c_{0}\begin{bmatrix}
3\\
-1
\end{bmatrix}+
c_{1}\begin{bmatrix}
2\\
1
\end{bmatrix}$$
  解得:\(c_{0}=-2,c_{1}=5\)
  第三步,利用特征值和特征向量的性质,式(1)

$$A^{n-1}
\begin{bmatrix}
s_{1} \\
s_{0}
\end{bmatrix}
=A^{n-1}(c_{0}V_{0}+c_{1}V_{1})
=c_{0}\lambda_{0}^{n-1}V_{0}+c_{1}\lambda_{1}^{n-1}V_{1}
=\begin{bmatrix}
s_{n} \\
s_{n-1}
\end{bmatrix}\,,\,\,(n\geq 2)$$

  代入\(c_{0},c_{1},V_{0},V_{1},\lambda_{0},\lambda_{1}\),求得
$$\begin{bmatrix}
s_{n} \\
s_{n-1}
\end{bmatrix}
= -2 \cdot (-3)^{n-1}
\begin{bmatrix}
3 \\
-1\end{bmatrix}
+5 \cdot 2^{n-1}
\begin{bmatrix}
2 \\
1 \end{bmatrix}
$$

$$\Rightarrow s_{n} = -2\cdot(-3)^{n} +5\cdot 2^{n} $$

  至此,辅助方程的生世已经揭秘完毕,接下来就这个线性空间以及变换矩阵\(A\)分享一些直觉的理解。

矩阵所描述的运动

  一个向量乘一个矩阵,可以理解成运动,也可以理解成基的变换(在本文暂且理解成运动)。关于矩阵的更多理解请参考这里
比如:
$$\begin{bmatrix}
-1 &6 \\
1 & 0
\end{bmatrix}\cdot
\begin{bmatrix}
4 \\
7 \end{bmatrix}
=\begin{bmatrix}
38 \\
4 \end{bmatrix}$$
  所谓的运动就是指\(\begin{bmatrix}
4 \\
7 \end{bmatrix}\)乘了一个矩阵变成\(\begin{bmatrix}
38 \\
4 \end{bmatrix}\),也可以理解为从位置(4,7)到位置(38,4)的“突变”。
  那么,一个向量多次乘上同一个矩阵\(A^{n-1}V_{init}\)会是什么情况呢?多次运动?如果一次运动算作“一步”,那“一步一步”后是否会走出“运动轨迹”?回到问题中的递推式(0),前面我们谈到,满足递推式的数列由最开始的\(s_{0},s_{1}\)决定,现在就四个不同的起点\((s_{0},s_{1})\),做个实验看看

  对于这个图,可以这样看,以两个圈圈之间的线段看做一个运动对象,线段\((s_{k-1},s_k)\)走“一步”后(一次运动)就到了线段\((s_{k},s_{k+1})\)。显然,虽然起点不同,但是乘的矩阵是一样的,运动的“步调”也是一致的。

这个线性空间、空间中的元素、矩阵之间的关系

  1. 满足递推式(0)数列构成一个线性空间,在这个线性空间里的线性运算是封闭的。
  2. 一个数列(线性空间中元素),已经由最开始的两个元素决定。
  3. 若把递推式写成矩阵,最初的两个元素决定运动起点和“步伐大小”,“步伐方向”(决定参数\(c_{0},c_{1}\)),“一步一步”后形成了“运动轨迹”,也就是数列。
  4. 所有运动轨迹的“步伐大小”“步伐方向”都是矩阵的特征向量的线性组合。
  5. 是“运动轨迹”(数列)集合构成线性空间,不是\((s_{i0},s_{i1})\)。\((s_{i0},s_{i1})\)是“运动轨迹”(数列)的“身份证”,有一一对应关系。

谈谈解法二:\(Z\) 变换


  问题中的递推式明显是个二阶的差分方程,既然是差分方程很自然就想到用\(Z\)变换去求解(零输入响应),这实在是太简单了。
  在这里,由于数列\(s_{n},n\)为非负整数,又因为\(Z\)变换的移位性,所以需要给这个递推式换个形式。
$$
s_{n} = -s_{n-1}+6s_{n-2}\,\,\,\,,n\geq 2 \\
\Leftrightarrow
s_{n+2} = -s_{n+1}+6s_{n}\,\,\,\,,n\geq 0 $$
  把\(s_{n}\)写成\(s(n)\),即把数列的下标形式写成函数形式,并把右边的项移到左边
$$
s(n+2) + s(n+1)-6s(n)=0\,\,\,\,,n为非负整数\,\,\,\,(a)
$$
  式(a)就是我们做\(Z\)变换需要的。对式(a)做\(Z\)变换
$$
[z^{2}Y(z)-s(0)z^{2}-s(1)z]+[zY(z)-s(0)z]-6Y(z)=0 \\
\Rightarrow
Y(z)=\frac{s(0)z^{2}+s(1)z+s(0)z}{z^{2}+z-6}
$$
  代入 \(s(0)=7,s(1)=4\),整理得
$$
Y(z)=\frac{7z^{2}+11z}{(z+3)(z-2)}
$$
  用部分分式展开法求得
$$Y(z)=\frac{2z}{z+3}+\frac{5z}{z-2} =\frac{2}{1+3z^{-1}} +\frac{5}{1-2z^{-1}}
$$
  利用变换对 $$a^{k}\varepsilon(k) \leftrightarrow \frac{1}{1-az^{-1}}\,\,\,,|z|>1$$
  再利用线性性质,\(Z\)逆变换回来得到通向式\(s(n)\)
$$s(n)=\mathbb{Z}^{-1}[Y(z)]=[2(-3)^{n}+5(2)^n]\varepsilon(n) \\
\Leftrightarrow
s(n)=2(-3)^{n}+5(2)^n\,\,\,\,\,, n为非负整数
$$

  关于\(Z\)变换的介绍以及求解方法,请参考这里

  呼~,至此曲毕。

Reference:

  1. 孟岩的博文《理解矩阵》:http://blog.csdn.net/myan/article/details/647511
  2. 线代启示录:https://ccjou.wordpress.com/