矩阵对角化

打开本页,如果没有显示公式,请刷新页面。

可对角化矩阵

定义

矩阵,若存在一个 阶可逆矩阵 ,使得 ,其中 是对角矩阵,则称 可对角化矩阵(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位的近似值是:

一般取 即可。

在历史上,伟大的天文学家开普勒,最早发现了这个结论。

开普勒(Johannes Kepler),德国天文学家、数学家。提出了著名的开普勒三定律,被誉为“为天文立法的人”

为斐波那契数列中的第 项,则:

根据斐波那契数列的特点,设定初始条件:

将(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 umbrasMens coelestis erat, corporis umbra iacet.(“我曾测天高,今欲量地深。”“我的灵魂来自上天,凡俗肉体归于此地。”)https://zh.wikipedia.org/wiki/约翰内斯·开普勒

[5]. 线代启示录:可对角化矩阵与缺陷矩阵的判定

作者: 老齐
链接: http://math.itdiffer.com/fibonacii.html
来源: 老齐教室-机器学习数学基础
本文原创发布于「老齐教室-机器学习数学基础」,转载请注明出处,谢谢合作!

https://gitee.com/qiwsir/images/raw/master/2021-2-15/1613357594979-1.png

results matching ""

    No results matching ""