矩阵对角化
打开本页，如果没有显示公式，请刷新页面。
可对角化矩阵
定义
令 是 矩阵，若存在一个 阶可逆矩阵 ，使得 ，其中 是对角矩阵，则称 是可对角化矩阵（diagonalizable matrix）， 是 的对角化矩阵（diagonalizing matrix）。
如果不存在满足上述条件的 ，则称 是不可对角化矩阵。
可对角化矩阵的判定
设 是 的特征值（含相同的特征值），对应的特征向量 ， 。可以写出 个特征方程：
将（1.1）式写成矩阵形式：
设 ， 是特征值构成的对角矩阵，即 ，则上式化为：
若 有 个线性无关的特征向量，则 是可逆的，由（1.2）式得：
- 可分解为：
- 对角化 ：
若 不拥有 个完整的线性无关的特征向量，则 不可逆。故无法对角化 。
所以，可以通过判断 的特征向量是否完全线性无关，进而确定其是否可对角化。
那么，如何判断特征向量完全线性无关？可以通过特征值部分判断。
特征值两两相异
定理1：若 的特征值两两相异，则 有完整的线性无关特征向量。
证明1
设 为相异特征值， ，对应特征向量集合 ，考虑：
将（1.3）式等号两侧左乘 ，并且 ，得：
因为 ，且 ，所以： 。
同理，可得： 。
故 是一个完整的线性无关集合。
证毕。
证明2（反证法）
设 是线性相关集合，在不失一般性的原则下，设 是最大的线性无关集，则：
其中 不全为零（因为 ）。
（1.4）式等号两侧分别左乘 ，可得：
且：
以上两式相减：
因为 是线性无关的向量集，且 两两相异，所以： 。与（1.4）式假设中的系数矛盾。故假设不成立。
证毕。
若 有相同的特征值，在可能可对角化，也可能不可对角化。
对于 阶方阵 ，特征多项式：
特征值 即为 的根。
将 阶行列式展开，（1.5）式即为 次多项式，故有 个根。
- 将（1.5）式的根中相重的根的数量，称为代数重数（algebraic multiplicity）。
由 得 ，根据零空间的概念，可知，每个特征值对应的特征向量必定属于 ，称之为对应 的特征空间（eigenspace）：
- 特征空间中的非零向量都是特征向量。
- 对应特征值 的特征空间维数， ，即所能找到的最大线性无关向量个数，称为 的几何重数（geometric multiplicity）
可对角化充要条件
定理2： 阶方阵 可对角化的一个充要条件是：每个特征值 ，代数重数等于集合重数。或者说，不可对角化矩阵同义语缺陷矩阵。
证明
证明
假设 可对角化，则有 个线性无关的特征向量。设 的代数重数为 ，一定有可逆矩阵 将 对角化为：
且 不为 阶对角矩阵 的特征值，故 是可逆矩阵。因为：
因为可逆矩阵相乘，不改变矩阵的秩，所以：
根据“秩—零花度原理”：
故：特征值 的集合重数等于代数重数。
证明
设方阵 有 个相异特征值 。其几何重数等于代数重数，记作 。
则特征向量总数为： 。
因为对应特征值 的 个特征向量线性无关，这些向量为特征空间 的基；又因为两个相异特征值的特征空间无交集， ，则两个特征值对应的特征向量线性无关。
所以， 有完整的 个线性无关的特征向量。
斐波那契数列
神奇的斐波那契数列。公元1150年印度数学家首先描述了斐波那契数列，此后，意大利人斐波那契（Leonardo Fibonacci）在描述兔子繁殖的数量，这样描述：
- 第一个月初有一对刚诞生的兔子
- 第二个月之后（第三个月初）它们可以生育
- 每月每对可生育的兔子会繁殖一对新兔子
- 兔子永不死
假设在 月有兔子共 对， 月共有 对，在 月必定共有 对：因为在 月的时候，前一月（n+1月）的 对兔子可以存留至第 月（在当月属于新诞生的兔子尚不能生育）。而新生育出的兔子对数等于所有在 月就已存在的 对。
即设 ，
按照表达式，可知斐波那契数是：
编程序，计算斐波那契数。可以有多种方法。
计算斐波那契数
递归
这里编写了一个用递归方法计算斐波那契数的函数，关于函数的创建方法，请参阅参考文献[1]。
# 递归
def fib_recu(n):
if n <= 1:
return n
else:
return fib_recu(n-1) + fib_recu(n-2)
print("fibonacci number:")
for i in range(10):
print(f"{fib_recu(i)}", end=" ")
# 输出：
fibonacci number:
0 1 1 2 3 5 8 13 21 34
递归方法，思路简单，但是执行效率比较低。
循环
def fib_loop(n):
fibs = [0, 1]
if n <= 1:
return n
else:
for i in range(n-2):
fibs.append(fibs[-2] + fibs[-1])
return fibs
print(f"fibonacci number: {fib_loop(10)}")
# 输出：
fibonacci number: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
循环方法，也称为递推法，即递增。随着数量的增大，执行速度会越来越慢。
迭代器对象
class Fibs:
def __init__(self, max):
self.max = max
self.a = 0
self.b = 1
def __iter__(self):
return self
def __next__(self):
fib = self.a
if fib > self.max:
raise StopIteration
self.a, self.b = self.b, self.a + self.b
return fib
fibs = Fibs(100000)
lst = [ fibs.__next__() for i in range(10)]
print(lst)
# 输出
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
生成器对象
def fibs():
prev, curr = 0, 1
while True:
yield prev
prev, curr = curr, prev + curr
import itertools
print(list(itertools.islice(fibs(), 10)))
# 输出
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
通过fibs()得到了含有无限项斐波那契数的对象，只不过在上面只向内存中读入了10个。
矩阵
import numpy as np
def fib_matrix(n):
F = np.mat([[1,1], [1,0]])
F_m = pow(F, n)
return F_m[0, 0]
print("fibonacci numbers:")
for i in range(10):
print(fib_matrix(i), end=" ")
# 输出
fibonacci numbers:
1 1 2 3 5 8 13 21 34 55
黄金分割
如果用斐波那契数列中的后面的数字除以前面的数字，结果会如何？
def fib_iter():
prev, curr = 0, 1
while True:
yield prev
prev, curr = curr, prev + curr
import itertools
fibs = list(itertools.islice(fib_iter(), 100))
for i in range(2, 30):
print(f"{fibs[i+1]}/{fibs[i]}={fibs[i+1]/fibs[i]}")
# 输出
2/1=2.0
3/2=1.5
5/3=1.6666666666666667
8/5=1.6
13/8=1.625
21/13=1.6153846153846154
34/21=1.619047619047619
55/34=1.6176470588235294
89/55=1.6181818181818182
144/89=1.6179775280898876
233/144=1.6180555555555556
377/233=1.6180257510729614
610/377=1.6180371352785146
987/610=1.618032786885246
1597/987=1.618034447821682
2584/1597=1.6180338134001253
4181/2584=1.618034055727554
6765/4181=1.6180339631667064
10946/6765=1.6180339985218033
17711/10946=1.618033985017358
28657/17711=1.6180339901755971
46368/28657=1.618033988205325
75025/46368=1.618033988957902
121393/75025=1.6180339886704431
196418/121393=1.6180339887802426
317811/196418=1.618033988738303
514229/317811=1.6180339887543225
832040/514229=1.6180339887482036
从上面的输出结果发现：
这就是我们熟悉的黄金分割——黄金比例，准确值是 ，这是一个无理数，小数点后20位的近似值是：
一般取 即可。
在历史上，伟大的天文学家开普勒，最早发现了这个结论。
设 为斐波那契数列中的第 项，则：
根据斐波那契数列的特点，设定初始条件： 。
将（5.1）式写成：
以矩阵方式表示为：
推导通项表达式 的第一种方法
令 ，由（5.2）式得到：
其中， ，初始条件 。
（5.3）式即为《机器学习数学基础》第3章3.2.2节中所介绍的差分方程。又因为：
所以，只要计算出 ，然后将它与初始条件 相乘，即得到 。
对于矩阵 ，其特征多项式：
根据特征方程： ，得：
解得：
显然， 。
再根据 计算（5.6）中每个特征值所对应的特征向量。
当 时，设特征向量为 ，则：
可得： 是满足条件的一个向量，即特征向量 （将 代入到上式，并利用（5.5）式，上式成立，即说明 是一个基向量）。
同理，求得另外一个特征值 所对应的特征向量 。
很显然，特征向量 和 线性无关，则矩阵 可以对角化（参阅《机器学习数学基础》第3章3.3.3节）。
设 ，其中 的列向量即为 的特征向量， 为特征向量构成的对角矩阵（参阅《机器学习数学基础》第3章3.3.3节（3.3.10）式和（3.3.11）式）。
因为：
于是（5.4）式可以转化为：
由于 是一个列向量，则 结果也是列向量，故令 ，（5.8）式变换为：
若用一般化的式子表示， （由 的 个特征向量组成）， ，代入（5.9）式：
即：
若 ，则（5.9）式即为： ，从而得到（5.10）式中的系数 。（5.10）式即为差分方程的通解（《机器学习数学基础》第3章3.2.2节，给出了差分方程通解的另外一种计算方法，在该方法中没有使用对矩阵 可对角化的假设）。
现在将 的特征向量（5.7）和特征值（5.6）式分别代入（5.10）式，即得到（5.3）差分方程的通解：
当 时， ，，代入（5.11）式：
解得：
代入（5.11），同时将特征值和特征向量也代入，得：
在（5.3）式中假设 ，对比上式，则：
这样就得到了斐波那契数列通项表达式。
推导通项表达式 的第二种方法
由于 可对角化，根据 得：
其中 （ 由特征向量 、 构成），则
由（5.4）式可得：
将（5.13）代入上式，可得：
所以，通项表达式：
与（5.12）式一样的结果。
性质1：
证明
对于 ，由（5.12）式得：
（ ）
证毕。
所以，在前面的程序中，显示后项除以前项的结果趋近于黄金分割。
性质2： 幂矩阵
因为 ，又因为斐波那契数列 ，所以：
以此类推，可得：
其中
这就是矩阵法计算斐波那契数列的程序编写依据。
性质3：Cassini等式
在《机器学习数学基础》第2章2.4节中曾经介绍过行列式的性质，下面应用其中一条： 。
由（5.14）可得：
又因为：
所以：
（5.15）式即为Cassini等式。表明了斐波那契数列的数之间的一种关系。如：
性质4：前 项的和
由（5.1）式得：
上面各式等号相加，得：
因为 ，所以，前 项的和是：
性质5：每项的平方和
又因为： ，所以：
参考文献
[1]. 齐伟. Python大学实用教程[M]. 北京：电子工业出版社. 2019年3月，第1版
[2]. 齐伟. 跟老齐学Python：数据分析[M]. 北京：电子工业出版社. 2018年6月，第1版
[3]. https://zh.wikipedia.org/wiki/黄金分割率
[4]. 开普勒的墓志铭：Mensus eram coelos, nunc terrae metior umbras；Mens coelestis erat, corporis umbra iacet.（“我曾测天高，今欲量地深。”“我的灵魂来自上天，凡俗肉体归于此地。”）https://zh.wikipedia.org/wiki/约翰内斯·开普勒
[5]. 线代启示录：可对角化矩阵与缺陷矩阵的判定
作者: 老齐
链接: http://math.itdiffer.com/fibonacii.html
来源: 机器学习
本文原创发布于「机器学习」,转载请注明出处,谢谢合作!
