第9章矩阵特征值问题的数值 方法 9.1 特征值与特征向量 9.2 Hermite矩阵特征值问题 9.3 Jacobi方法 9.4 对分法 9.5 乘幂法 9.6 反幂法 9.7 QR方法
9.1 特征值与特征向量设A是n阶矩阵,x是非零列向量. 如果有数λ存在,满足, (1) 那么,称x是矩阵A关于特征值λ的特征向量.
如果把(1)式右端写为 ,那么(1)式又可写为: x λ ()0 I A x λ-=||0 I A λ-=即1110 ()||...n n n f I A a a a λλλλλ--=-=++++记 它是关于参数λ的n 次多项式,称为矩阵A 的特 征多项式, 其中a 0=(-1)n |A |. (2)
显然,当λ是A的一个特征值时,它必然 是的根. 反之,如果λ是的根,那么齐次方程组(2)有非零解向量x,使(1)式 成立. 从而,λ是A的一个特征值. A的特征值也称为A的特征根 . ()0 fλ= ()0 fλ=
矩阵特征值和特征向量有如下主要性质: 定理9.1.1 n阶矩阵A是降秩矩阵的充分必要 条件是A有零特征值. 定理9.1.2 设矩阵A与矩阵B相似,那么它们 有相同的特征值. 定理9.1.3 n阶矩阵A与A T有相同的特征值. 定理9.1.4 设λ ≠λj是n阶矩阵A的两个互异特 i 征值,x、y分别是其相应的右特征向 量和左特征向量,那么,x T y=0 .
9.2 Hermite矩阵特征值问题?设A为n阶矩阵,其共轭转置矩阵记为A H. 如果A=A H,那么,A称为Hermite矩阵.
求矩阵特征值算法及程序简介 1.幂法 1、幂法规范化算法 (1)输入矩阵A、初始向量( 0),误差eps; (2) k 1; (3)计算V(k)A(k 1); (4)m k max(V(k)) ,m k1max( V ( k 1)); (5) (k)V(k)/m k; (6)如果m k m k 1eps,则显示特征值1和对应的特征向量x(1) ),终止; (7)k k 1, 转(3) 注:如上算法中的符号max(V )表示取向量V 中绝对值最大的分量。本算法使用了数据规范化处理技术以防止计算过程中出现益出错误。 2、规范化幂法程序 Clear[a,u,x]; a=Input[" 系数矩阵A="]; u=Input[" 初始迭代向量u(0)="]; n=Length[u]; eps=Input[" 误差精度eps ="]; nmax=Input[" 迭代允许最大次数nmax="]; fmax[x_]:=Module[{m=0,m1,m2}, Do[m1=Abs[x[[k]]]; If[m1>m,m2=x[[k]];m=m1], {k,1,Length[x]}]; m2] v=a.u; m0=fmax[u]; m1=fmax[v]; t=Abs[m1-m0]//N; k=0; While[t>eps&&k 机械振动中的特征值问题 机械振动是指系统在某一位置(通常是静平衡位置,简称平衡位置)附近所作的往复运动。显然这是一种特殊形式的机械运动。人类的大多数活动都包括这样或那样的机械振动。例如,我们能听见周围的声音是由于鼓膜的振动;我们能看见周围的物体是由于光波振动的结果;人的呼吸与肺的振动紧密相关;行走时人的腿和手臂也都在作机械振动;我们能讲话正是喉咙(和舌头)作机械振动的结果。 早期机械振动研究起源于摆钟与音乐。至20世纪上半叶,线性振动理论基本建立起来。欧拉(Euler)于1728年建立并求解了单摆在阻尼介质中运动的微分方程。1739年他研究了无阻尼简谐强迫振动,从理论上解释共振现象。1747年他对n个等质量质点由等刚度弹簧连接的系统列出了微分方程组并求出精确解,从而发现系统的振动是各阶简谐振动的叠加。1760年拉格朗日(Lagrange)建立了离散系统振动的一般理论。最早研究的连续系统是弦线。1746年达朗伯(d’Alembert)用片微分方程描述弦线振动而得到波动方程并求出行波解。1753年伯努利(Bernoulli)用无穷多个模态叠加的方法得到弦线振动的驻波解。1759年拉格朗日从驻波解推得性波解,但严格的数学证明直到1811年傅里叶(Fourier)提出函数的级数展开理论才完成。 一个振动系统本质上是一个动力系统,这是由于其变量如所受到的激励(输入)和相应(输出)都是随时间变化的。一个振动系统的响应一般来说是依赖于初始条件和外部激励的。大多数实际振动系统都十分复杂,因而在进行数学分析时把所有的细节都考虑进来是不可能的。为了预测在指定输入下振动系统的行为,通常只是考虑那些最重要的特性。也会经常遇到这样的情况,即对一个复杂的物理系统,即使采用一个比较简单的模型也能够大体了解其行为。对一个振动系统进行分析通常包括以下步骤。 步骤1,建立数学模型。建立数学模型的目的是揭示系统的全部重要特性,从而得到描述系统动力学行为的控制方程。一个系统的数学模型应该包括足够多的细节,能够用方程描述系统的行为但又不致使其过于复杂。根据基本元件行为的属性,一个振动系统的数学模型可以是线性的,也可以是非线性的。线性模型处理简单,容易求解。但是非线性模型有时能够揭示线性模型不能够预测到的某些系统特性。所以需要对实际系统做大量的工程判断以得到振动系统比较合理的模型。有时为了得到更准确的结果,需要对系统的数学模型不断进行完善。此时可以先用一个比较粗略的模型,以便能够较快地对系统的大体属性有所了解。之后再通过增加更多的元件和细节对模型不断改进,以便进一步分析系统的动力学行为。 步骤2,推导控制方程。一旦有了系统的数学模型,就可以利用动力学定律推导系统响应变化规律的运动微分方程。系统的运动微分方程可以通过作每一个质量块的受力分析图方便地得到。每一个质量块的受力分析图可以通过分离该质量块并加上其所受的全部主动力、反作用力和惯性力得到。一个振动系统的运动微分方程对于离散系统来说,通常是一个常微分方程组;对于连续系统来说,通常是一个偏微分方程组。根据基本元件行为的属性,一个振动系统的运动微分方程(组)可以是线性的,也可以是非线性的。以下几种方法经常用来推导系统的控制方程:牛顿第二运动定律、达朗贝尔原理和能量守恒原理。 步骤3,求控制方程的解。为了得到振动系统响应的规律,必须求解控制方程。根据问题具体特点,可以采取下述方法之一:求解微分方程的常规方法,拉普拉斯变换方法、矩阵方法和数值计算方法。如果控制方程是非线性的,则很少能够得到其封闭形式的解。另外,求解偏微分方程的情况也远比求解常微分方程的情况多。利用计算机的数值计算方法求解微分方程是非常便捷的,但欲根据数据计算结果得到关于系统行为的一般结论却是困难的。 步骤4,结果分析。虽然控制方程的解给出系统中不同质量块的振动位移、速度和加速度的表达式,但是这些结果还必须就某些目的做进一步分析,以期分析结果可能揭示对设计的某些指导意义。 非线性成分分析作为一个核的特征值问题 摘要 我们用于一种新方法描述如何执行主成分分析非线性形式。通过对积分算子核函数的使用。通过一些相关的非线性映射输入空间,我们可以有效计算在高维特征空间的主成分组成部分;比如在16 *16的图像空间中所有可能的5个像素的乘积。这篇论文中我们给出了该方法的推导,连同由非线性与内核的方法形成的讨论,并且展现目前对模式识别的非线性特征提取的第一批实验结果。 1 引入 主成分分析是尽可能提取高维数据集的一种强大的配套技术.它很容易通过求解一个特征值问题或者用迭代算法来估计主成分;现有的文献(看Jolliffe(1986) and Diamataras & Kung (1996))。PCA是将我们所描述的数据的坐标系进行正交变换。用新的坐标值所表示的数据我们称为主成分。通常情况下,少数的主成分组足以说明数据的主要结构。这些少数的数据我们有时候叫做数据的因素及潜在变量。 目前的主成分分析的推广工作,我们相对投射空间的主要成分而言,对输入空间中的变量或特征更感兴趣,因为它与输入变量时非线性相关的。其中包括对输入变量之间采取高层次的相关性得到的实例变量。在图像分析的情况下,这就相当于是对输入数据所张成的空间就行寻找主要成分。 为了这个目的,我们在输入空间中依据核函数来表达特征空间中的点积。对于给出的任何一个算法我们都可以通过点积单独的被表示 出来,也就是说,即使变量本身没有明确的算法,我们也可以通过这个核函数组建不同的非线性函数。(Aizerman,Braverman,和 Rozonoer,1964;Boser,Guyon&Vapnik,1992)。尽管这个方法已被广泛的认知(Burges,1996),它的对机器学习的用途不是很大,除了在支持向量机方面。(Vapnik,1995) 在这篇论文中,我们给出了通过这种方法构造非线性函数的几个例子。第一个例子是主成分分析的非线性形式,我们将会给出方法的细节及实验结果(第2到4节),我们也将主要描绘出具体的算法(第7节)。 在下一节中,我们首先回顾一下标准PCA 的算法。为了能把它推广到非线性情况下,我们将用对应的唯一的点积的方法将PCA 算法公式化。在第3节中,我们将在特征空间中通过计算点积来讨论核方法。这两节主要是第4节的基础,第4节将提出对于非线性的PCA 得核的基本算法。第5节中将讨论基本核PCA 算法与其他推广的PCA 算法的不同。在第6节中,我们将给出在模式识别的特征值提取中的核基本算法的一些第一次实验结果。然后在第7节将探讨关于核方法在其他领域的应用,将在第8节中对于探讨给出总结。最后,一些技术性的材料,对于论据不构成主要的线索我们将放入附录中。 2 特种空间的PCA 给出一组以M 为中心的观测值1,1,...,,,0M N k k k k x k M x R x ==∈=∑ PCA 算法对角化后的协方差矩阵为 11M T j j j C x x M ==∑ (1) 第八章 矩阵特征值计算 1 特征值性质和估计 工程实践中有许多种振动问题,如桥梁或建筑物的振动,机械机件的振动,飞机机翼的颤动等,这些问题的求解常常归纳为求矩阵的特征值问题。另外,一些稳定分析问题及相关问题也可以转化为求矩阵特征值与特征向量的问题。 1.1 特征值问题及性质 设矩阵n n ?∈A R (或n n ?C ),特征值问题是:求C λ∈和非零向量n R ∈x ,使 λ=Ax x (1.1) 其中x 是矩阵A 属于特征值λ的特征向量。A 的全体特征值组成的集合记为sp()A 。 求A 的特征值问题(1.1)等价于求A 的特征方程 ()det()0p I λλ=-=A (1.2) 的根。因为一般不能通过有限次运算准确求解()0p λ=的根,所以特征值问题的数值方法只能 是迭代法。反之,有时为了求多项式 111()n n n n q a a a λλλλ--=++++L 的零点,可以把()q λ看成矩阵 123101010n a a a a ----???????????????? L O O 的特征多项式(除(1)n -因子不计)。这是一个Hessenberg 矩阵,可用QR 方法求特征值,从而求出代数方程()0q λ=的根。 矩阵特征值和特征向量的计算问题可分为两类:一类是求矩阵A 的全部特征值及其对应的向量;另一类是求部分特征值(一个或几个、按模最大或最小)及其对应的特征向量。本章介绍部分特征值和特征向量的幂法、内积法;求实对称矩阵全部特征值的雅可比法、Given 方法和Householder 方法;求任意矩阵全部特征值的QR 算法。 在第5章已给出特征值的一些重要性质,下面再补充一些基本性质。 定理1 设n n R ?∈A ,则 (1) 设λ为A 的特征值,则λμ-为μ-A I 的特 第八章 矩阵的特征值与特征向量的数值解法 某些工程计算涉及到矩阵的特征值与特征向量的求解。如果从原始矩阵出发,先求出特征多项式,再求特征多项式的根,在理论上是无可非议的。但一般不用这种方法,因为了这种算法往往不稳定.常用的方法是迭代法或变换法。本章介绍求解特征值与特征向量的一些方法。 §1 乘幂法 乘幂法是通过求矩阵的特征向量来求特征值的一种迭代法,它适用于求矩阵的按模最大的特征值及对应的特征向量。 定理8·1 设矩阵An ×n 有n 个线性无关的特征向量X i(i=1,2,…,n),其对应的特征值λi (i =1,2,…,n)满足 |λ1|>|λ2|≧…≧|λn | 则对任何n维非零初始向量Z 0,构造Zk = AZ k-1 11()lim ()k j k k j Z Z λ→∞ -= (8·1) 其中(Zk )j表示向量Z k 的第j个分量。 证明 : 只就λi是实数的情况证明如下。 因为A 有n 个线性无关的特征向量X i ,(i = 1,2,…,n)用X i(i = 1,2,…,n)线性表示,即Z 0=α1X 1 + α2X2 +用A 构造向量序列{Z k }其中 ? 21021010, ,k k k Z AZ Z AZ A Z Z AZ A Z -=====, (8.2) 由矩阵特征值定义知AXi =λi X i (i=1,2, …,n),故 ? 0112211122211121k k k k k n n k k k n n n k n k i i i i Z A Z A X A X A X X X X X X ααααλαλαλλλααλ===++ +=+++???? ??=+ ?????? ? ∑ (8.3) 同理有 1 1 11 1121k n k i k i i i Z X X λλααλ---=? ? ????=+ ????? ? ? ∑ (8.4) 将(8.3)与(8.4)所得Zk 及Z k-1的第j 个分量相除,设α1≠0,并且注意到 |λi |<|λ1|(i=1,2,…,n )得 第六章 矩阵特征值问题及二次型 6.1 求下列矩阵的特征值与特征向量: 1); 2); 3); ????????4221?????????????6123020663???? ????????3202300054); 5). ??????????422242224????????????? ?00011000010000106.2 设,证明:和有完全相同的特征值。 n n A A ×=T A A 6.3 设12=λ为方阵的特征值,求满足的关系式。 ???? ?????????=a b A 4417447b a ,6.4 设,证明:若有一个常数项不为零的多项式n n A A ×=)(x ?使得0)(=A ?,则的特征值必全不为零。 A 6.5 设λ为阶可逆方阵的特征值,证明:n A 12 +?? ????λA 是()I A +?2的特征值。 6.6 设21,λλ是方阵的两个互异的特征值,A 21,ξξ分别是的属于特征值A 21,λλ的特征向量,证明:21ξξ+不是的特征向量。 A 6.7 设321,,λλλ是方阵的三个互异的特征值,A 321,,ξξξ分别是的属于特征值A 321,,λλλ的特征向量,证明:321ξξξ++不是的特征向量。 A 6.8 设均为阶方阵且可逆,证明:~ B A ,n A AB .BA 6.9 设;求. ????????? ?????=163053064A 10A 6.10 设为2阶实方阵,且A 0trA ,则相似于对角阵A 第八章矩阵的特征值和特征向量的计算 矩阵的特征值和特征向量 乘幂法 反幂法 矩阵特征值和特征向量计算 特征值与特征向量A x = λx ( λ∈C ,x ≠0 ) 性质 (1)tr(A ) = a 11+ a 22+ ???+ a nn = λ1 + λ2+ ???+ λn (2)det(A ) = λ1 λ2???λn (3)若B = P -1AP 则A 与B 具有相同的特征值;x 是B 的特征向量?Px 是A 的特征向量. /* Calculation of Eigenvalue and Eigenvector of Matrix */ 乘幂法 乘幂法:计算实矩阵按模最大的特征值 假设:(1) |λ1| >|λ2| ≥…≥|λn | ≥0 (2)对应的n 个线性无关特征向量为:x 1, x 2, ..., x n 。 计算过程:任取一个非零向量v ,要求满足(x 1,v )≠0 计算v 1=Av 0, v 2=Av 1, ..., v k +1=Av k , ...,直到收敛。 收敛分析 011221(0) n n v x x x αααα=+++≠10111222n n n v Av x x x αλαλαλ==+++111 1222k k k k k n n n v Av x x x αλαλαλ-==+++ 21112211k k k n n n x x x λλλαααλλ??????=+++?? ? ????????? 1 11 k x λα 当k 充分大时,有 1 11k k v x λα≈11111 k k v x λα++≈11k k v v λ+≈又1k k v Av +=1k k Av v λ≈()()11 k j k j v v λ+≈( j =1, 2, ... , n ) v k 为λ1的近似特征向量 乘幂法的收敛速度取决于的大小。 21 r λλ=算法(乘幂法) 任取非零向量v 0,计算 1. v k +1 = Av k 2. 对v k 中所有非零分量(v k )j ,判断是否近似于某个常 数,如果是,则停机;否则转第1 步。 ()()1k j k j v v +乘幂法 9 矩阵特征值计算 在实际的工程计算中,经常会遇到求n 阶方阵 A 的特征值(Eigenvalue)与特征向量(Eigenvector)的问题。对于一个方阵A,如果数值λ使方程组 Ax=λx 即(A-λI n )x=0 有非零解向量(Solution Vector)x,则称λ为方阵A的特征值,而非零向量x为特征值λ所对应的特征向量,其中I n 为n阶单位矩阵。 由于根据定义直接求矩阵特征值的过程比较复杂,因此在实际计算中,往往采取一些数值方法。本章主要介绍求一般方阵绝对值最大的特征值的乘幂(Power)法、求对称方阵特征值的雅可比法和单侧旋转(One-side Rotation)法以及求一般矩阵全部特征值的QR 方法及一些相关的并行算法。 1.1 求解矩阵最大特征值的乘幂法 1.1.1 乘幂法及其串行算法 在许多实际问题中,只需要计算绝对值最大的特征值,而并不需要求矩阵的全部特征值。乘幂法是一种求矩阵绝对值最大的特征值的方法。记实方阵A的n个特征值为λi i=(1,2, …,n),且满足: │λ1 │≥│λ2 │≥│λ3 │≥…≥│λn │ 特征值λi 对应的特征向量为x i 。乘幂法的做法是:①取n维非零向量v0 作为初始向量;②对于 k=1,2, …,做如下迭代: 直至u k+1 ∞ - u k u k =Av k-1 v k = u k /║u k ║∞ <ε为止,这时v k+1 就是A的绝对值最大的特征值λ1 所对应的特征向∞ 量x1 。若v k-1 与v k 的各个分量同号且成比例,则λ1 =║u k ║∞;若v k-1 与v k 的各个分量异号且成比例,则λ1 = -║u k ║∞。若各取一次乘法和加法运算时间、一次除法运算时间、一次比较运算时间为一个单位时间,则因为一轮计算要做一次矩阵向量相乘、一次求最大元操作和一次规格化操作,所以下述乘幂法串行算法21.1 的一轮计算时间为n2+2n=O(n2 )。 算法21.1 单处理器上乘幂法求解矩阵最大特征值的算法 输入:系数矩阵A n×n ,初始向量v n×1 ,ε 输出:最大的特征值m ax Begin while (│diff│>ε) do (1)for i=1 to n do (1.1)sum=0 (1.2)for j= 1 to n do sum=sum+a[i,j]*x[j] end for 第3章 矩阵特征值与特征向量的计算 一些工程技术问题需要用数值方法求得矩阵的全部或部分特征值及相关的特征向量。 3.1 特征值的估计 较粗估计ρ(A ) ≤ ||A || 欲将复平面上的特征值一个个用圆盘围起来。 3.1.1 盖氏图 定义3.1-1 设A = [a ij ]n ?n ,称由不等式∑≠=≤-n i j j ij ii a a z 1 所确定的复区域为A 的第i 个盖氏图, 记为G i ,i = 1,2,…,n 。 >≤-=<∑≠=}:{1n i j j ij ii i a a z z G 定理3.1-1 若λ为A 的特征值,则 n i i G 1 =∈ λ 证明:设Ax = λx (x ≠ 0),若k 使得∞ ≤≤==x x x i n i k 1max 因为 k n j j kj x x a λ=∑=1 ?∑≠= -n k j j kj k kk x a x a )(λ ?∑∑∑ ≠=≠=≠≤≤= -n k j j kj n k j j k j kj n k j k j kj kk a x x a x x a a 11λ ? n i i k G G 1 =? ∈λ 例1 估计方阵????? ?? ?? ???----=41 .03.02.05.013.012.01 .035.03.02.01.01A 特征值的范围 解: G 1 = {z :|z – 1|≤ 0.6};G 2 = {z :|z – 3|≤ 0.8}; G 3 = {z :|z + 1|≤ 1.8};G 4 = {z :|z + 4|≤ 0.6}。 注:定理称A 的n 个特征值全落在n 个盖氏圆上,但未说明每个圆盘内都有一个特征值。 3.1.2 盖氏圆的连通部分 称相交盖氏圆之并构成的连通部分为连通部分。 孤立的盖氏圆本身也为一个连通部分。 定理3.1-2 若由A 的k 个盖氏圆组成的连通部分,含且仅含A 的k 个特征值。 证明: 令D = diag(a 11,a 12,…,a nn ),M = A – D ,记 )10(00 0)(2 1 22111222 11≤≤?? ?? ? ? ? ??+??????? ? ?=+=εεεε n n n n nn a a a a a a a a a M D A 则显然有A (1) = A ,A (0) = D ,易知A (ε)的特征多项式的系数是ε的多项式,从而A (ε)的特征 值λ1(ε),λ2(ε),…,λn (ε)为ε的连续函数。 A (ε)的盖氏圆为:)10(,}||||:{)(11≤≤?=≤ -=∑∑≠=≠=εεεεi n i j j ij n i j j ij ii i G a a a z z G 因为A (0) = D 的n 个特征值a 11,a 12,…,a nn ,恰为A 的盖氏圆圆心,当ε由0增大到1时,λi (ε)画出一条以λi (0) = a ii 为始点,λi (1) = λi 为终点的连续曲线,且始终不会越过G i ; 不失一般性,设A 开头的k 个圆盘是连通的,其并集为S ,它与后n – k 个圆盘严格分离,显然,A (ε)的前k 个盖氏圆盘与后n – k 个圆盘严格分离。 当ε = 0时,A (0) = D 的前k 个特征值刚好落在前k 个圆盘G 1,…,G k 中,而另n – k 个特征值则在区域S 之外,ε从0变到1时, k i i G 1 )(=ε与 n k i i G 1 )(+=ε始终分离(严格) 。连续曲线始终在S 中,所以S 中有且仅有A 的k 个特征值。 注:1) 每个孤立圆中恰有一个特征值。 2) 例1中G 2,G 4为仅由一个盖氏圆构成的连通部分,故它们各有一个特征值,而G 1,G 3构成的连通部分应含有两个特征值。 3) 因为例1中A 为实方阵,所以若λ为A 的特征值,则λ也是A 的特征值,所以G 2,G 4机械振动中的特征值问题
非线性成分分析作为一个核的特征值问题
第8章 矩阵特征值计算
第八章矩阵的特征值与特征向量的数值解法
矩阵特征值问题及二次型
第八章 矩阵的特征值和特征向量的计算
并行计算-矩阵特征值计算--
3矩阵特征值与特征向量的计算