NA05b数值方法课件.pptVIP

2、化一般矩阵为拟上三角阵 3、拟上三角矩阵的QR分解 ?带原点移位的QR方法 * Ch.5 Power Method – Deflation Technique ? 原点平移法 /* deflation technique */ 决定收敛的速度，特别 是 | ?2 / ?1 | 希望 | ?2 / ?1 | 越小越好。 不妨设 ?1 ?2 ? … ? ?n ，且 | ?2 | | ?n |。 ?1 ?2 ?n O p = ( ?2 + ?n ) / 2 思路 令 B = A ? pI ，则有 | ?I?A | = | ?I?(B+pI) | = | (??p)I?B | ?A ? p = ?B 。若需求?1 ,我们首先应选择p满足: | ?1 -p| | ?n –p|,此时对于B = A ? pI 的幂法来说,收敛的快慢决定于: How are we supposed to know where p is? 反幂法 所以，A和A－1的特征值互为倒数 这样，求A－1的按模最大特征值，就可以求出A的按模最小特征值 为避免求逆的运算，可以解线性方程组 ? 反幂法 /* Inverse Power Method */ Ch.5 Power Method –Inverse Power Method 若知道某一特征根 ?l 的大致位置 p ，即对任意 i? l 有| ?l ? p | | ?i ? p | ，并且如果 (A ? pI)?1存在，则可以用反幂法求(A ? pI)?1的主特征根 1/(?l ? p ) ，收敛将非常快。 思路 ?带原点位移反幂法 只要近似值p适当地好,收敛的速度是很快的 若已知A的全部近似特征值,用该法可求A的 全部特征向量,同时改进特征值。该法收敛快, 精度高,是目前求解特征向量最有效的方法. P为n阶可逆阵，则A与P－1AP相似，相似阵有相同的特征值。 若A对称，则存在正交阵Q(QTQ=I)，使得 直接找Q不大可能。我们可以构造一系列特殊形式的正交阵Q1,...,Qn对A作正交变换 使得对角元素比重逐次增加，非对角元变小。当非对角元已经小得无足轻重时，可以近似 认为对角元就是A的所有特征值。Jacobi方法就是这样一类方法。 ? Jacobi方法 /* Jacobi Method */ 1、Givens旋转变换 对称阵 为正交阵 p列 q列 记： 则： 变换的目的是为了减少非对角元的分量，即使 知 的按模较小根 所以： 2、Jacobi迭代 取p,q使 ，则 定理： 若A对称，则 解 记 A(0)=A,取p=1,q=2,apq(0)=a12(0)=2,于是有 例 用Jacobi 方法计算对称矩阵的全部特征值. 从而有 所以 再取p=2,q=3,apq(1)=a23(1)=2.020190,类似地可得 从而A的特征值可取为 ?1?2.125825, ?2?8.388761, ?3?4.485401 为了减少有哪些信誉好的足球投注网站非对角线绝对值最大元素时间, 对经典的Jacobi方法可作进一步改进. 1.循环Jacobi方法: 按(1,2),(1,3),…,(1,n),(2,3),(2,4),…,(2,n),…,(n-1,n)的顺序, 对每个(p,q)的非零元素apq作Jacobi变换,使其零化,逐次重复扫描下去,直至?(A)?为止. 2.过关Jacobi方法: 取单调下降收敛于零的正数序列??k?,先以?1为关卡值,依照1中顺序,将绝对值超过?1的非对角元素零化,待所有非对角元素绝对值均不超过?1时,再换下一个关卡值?2 ,直到关卡值小于给定的精度? . 60年代出现的QR算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。 理论依据：任一非奇异实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。 ?基本QR方法 /* Basic QR Method */ 定理（QR方法的收敛性） 可证，在一定条件下，基本QR方法产生 的矩阵序列｛A(k)｝ “基本”收敛于一个上三角 阵（或分块上三角阵）。即主对角线（或主对 角线子块）及其以下元素均收敛，主对角线 （或主对角线子块）以上元素可以不收敛。特 别的，如果A是实对称阵，则｛A(k)｝ “基本” 收敛于对角矩阵。 因为上三角阵的主对角元（或分块上三角阵 中，主对角线子块的特征值）即为该矩阵的特 征值，故当k充分大时， A(k)的主对角元（或主 对角线子块的特征值）就可以作为A的特征值的 近似。基本的QR方法的主要运算是对矩阵QR分 解，分解的方法有多种。介绍一种Schmit正交化 方法。