特征值和特征向量是矩阵的属性,也就是说这是一个变换的属性。对于矩阵A,假设x为A的一个特征向量,则Ax=μx。可见该变换对于特征向量,只缩放了向量,而没有改变向量的方向,特征值的就是缩放的系数,是一个倍数关系。如果我们有一个向量,我们想设计一个变换,使得该向量经过该变换后不改变方向,只改变大小。那么特征值和特征向量就可以用来作为我们设计变换的依据,即我们要使该变换的特征向量和这个向量的方向相同。
雅可比(Jacobi)算法
雅可比(Jacobi)算法是一个用于计算实对称矩阵的所有特征值和特征向量的经典算法。在以下示例中,A为一个实对称矩阵,U为对应的特征向量构成的矩阵,D为对应的特征值。该算法的代码可参照这个代码中的函数jacobi_4x4
。
雅可比算法的基本原理
1.实对称矩阵
雅可比算法处理的是实对称矩阵,这意味着矩阵等于其转置矩阵(即,A[i][j] = A[j][i]对所有i,j都成立)。实对称矩阵的特征值都是实数,且存在一组正交特征向量。
2.轮换法
算法的核心思想是通过一系列的旋转操作,逐步将矩阵转化为对角矩阵,而对角线上的元素即为矩阵的特征值。每次旋转操作都会选取矩阵的一个非对角元素,并通过旋转使该元素变为0,同时保持矩阵的对称性和特征值不变。
3.旋转矩阵
每次旋转都使用一个旋转矩阵,该旋转矩阵是通过计算旋转角度θ来定义的。旋转的目的是使得在某个特定的非对角位置的元素被置为0。旋转矩阵是正交的,这意味着它不会改变原矩阵的特征值。
关键步骤
1.初始化
方法开始时,将输出矩阵U初始化为单位矩阵,这是因为旋转矩阵的乘积将会累积在这个矩阵中,最终U将包含原矩阵A的特征向量。同时,将A的对角元素复制到D中,作为特征值的初始近似。(A和单位矩阵U,经过相同的初等变换(旋转矩阵),当A为对角矩阵时,U为对应的特征向量)
2.旋转阈值
对于前几次迭代,算法使用一个非零的旋转阈值,以便于早期更积极地进行旋转。随着迭代的进行,这个阈值会被设置为0,从而减少不必要的旋转。
3.旋转操作
对于矩阵A中的每个非对角元素,如果其绝对值大于旋转阈值,则计算一个旋转矩阵X使得该元素被旋转为0。这个旋转同时会影响到矩阵的其他元素,以保持矩阵的对称性和特征值不变。该旋转矩阵根据上一次迭代得到的D计算。
4.更新特征值和特征向量
每次旋转后,都会更新近似的特征值以及累积在U中的特征向量,即U=UX,D=DX。
5.收敛检查
如果所有非对角元素的绝对值之和接近于0,这意味着矩阵已经接近对角化,算法则认为已经收敛,返回真。如果经过预设的迭代次数后仍未收敛,则返回假。此时得到的U即为特征向量构成的矩阵,已经变换为对角矩阵的A的对角元素即为特征值。
explanation
- 雅可比算法通过对原始矩阵 𝐴 和单位矩阵 U 应用一系列相同的旋转变换(也称为初等变换),最终将 𝐴 转换为一个对角矩阵,而对角线上的元素即为 A 的特征值。同时,经过这些旋转变换后的单位矩阵 U 将变成一个包含 A 的所有特征向量的矩阵。
初等旋转变换的几何意义
- 对角化的目标: 对于一个给定的实对称矩阵,我们的目标是通过一系列旋转将其转换为对角矩阵。几何上,这意味着我们希望找到一个新的坐标系,使得在这个坐标系下,矩阵的作用仅为沿着坐标轴的伸缩,而没有任何旋转或剪切。这个新坐标系的基向量,就是矩阵的特征向量。
- 旋转变换: 在二维空间中,旋转变换可以理解为将一个向量围绕原点旋转一个给定的角度。在更高维的空间中,旋转变换涉及到选择两个维度(或称之为轴),然后在这两个维度定义的平面上进行旋转,而保持其他维度不变。
旋转矩阵的右乘作用
几何上,当你对一个向量或者向量空间应用一个旋转变换时,这个旋转变换可以被视为一个矩阵,而该向量或向量空间被这个矩阵右乘。在二维或三维空间中,这相当于围绕原点旋转向量。
D的动态更新
-
特征值的逐步逼近:雅可比旋转算法的目标之一是计算矩阵的特征值,这通过逐渐对角化矩阵 A 来实现。在这个过程中,D 中的对角元素被用来存储 A 对角元素的当前估计,这些估计随着每次旋转而更新。每次旋转都旨在减少 A 的非对角元素,同时影响对角元素的值,使它们更接近真实的特征值。因此,D 的更新是这一过程的核心部分,它确保了特征值的估计随迭代而改进。
-
迭代过程中的收敛判定:D 中对角元素的更新还关系到算法的收敛判定。算法通过监控非对角元素的大小以判断是否达到收敛(即,非对角元素足够小)。在这个过程中,D 的更新提供了关于特征值如何随迭代过程逐渐稳定下来的直接信息。
-
算法的效率和准确性:虽然在理论上可以通过直接对 A 应用旋转变换而不显式更新 D 来追踪特征值的变化,但这样做会降低算法的效率和准确性。显式更新 D 允许算法更直接地追踪特征值的逼近过程,而不需要在每次迭代后重新计算 A 的对角元素。
-
编程实现的简化:从实现的角度看,使用 D 作为一个独立的数据结构简化了编程实现。它使得算法能够清晰地分离矩阵 A 的旋转操作(影响特征向量的计算)和特征值的更新过程。
-
每次迭代中,D都在逐步接近真实值,D同时也作为每次迭代的初始值. 在算法开始时,D 被初始化为 A 的对角元素,这反映了对特征值的初始估计。每次迭代后的 D 代表了更新后的特征值估计。
雅可比旋转的几何过程
-
选择旋转平面: 在每次迭代中,雅可比算法选择矩阵的一个非对角元素进行旋转。从几何上看,这相当于选择了一个由两个基向量定义的平面,目标是在这个平面上调整基向量,使得在这两个方向上的变换变为纯粹的伸缩,消除了这两个方向之间的相互作用(即非对角元素)。
-
旋转以消除非对角元素: 通过旋转,我们实际上是在寻找一个新的坐标系,使得在这个坐标系下,原矩阵在选定的两个维度上的作用变为对角化的形式。几何上,这意味着我们在旋转平面上找到了一个新的基,使得在这个基下,矩阵的变换不再包含旋转分量,仅有伸缩分量。
-
累积旋转到单位矩阵: 初始时,单位矩阵对应的是标准的坐标系。每次旋转变换不仅应用于原矩阵,也同样应用于这个单位矩阵。随着旋转的累积,单位矩阵变换成了特征向量矩阵,其列表示了原矩阵在新坐标系下的基向量。这个新坐标系正是使原矩阵对角化的坐标系。