第2章解线性代数方程组的迭代法ppt课件.ppt

第2章 解线性代数方程组的迭代法,求解线性代数方程组主要有直接法和迭代法两种常见方法。直接法一般适合小型的系数矩阵，为了求解现实当中常见的大型稀疏矩阵，下面我们将重点介绍迭代法。它是一种不断套用一个迭代公式，逐步逼近方程的解的方法。将讨论两类主要方法，一类是逐步逼近法，另一类是下降法，包括最速下降法和共轭梯度法。,为了对线性方程组数值解的精确程度，以及方程组本身的性态进行分析，需要对向量和矩阵的“大小”引进某种度量，范数就是一种度量尺度，向量和矩阵的范数在线性方程组数值方法的研究中起着重要的作用。,2.1 向量、矩阵范数与谱半径,（2）齐次性：对任何实数和向量x|kx|k|x|,（3）三角不等式：对任何向量x和y，都有|xy|x|y|,（1）非负性：对任何向量x，|x|0，且|x|0当且仅当x0,2.2.1 向量的范数,定义2.1 设 是x的实值函数，且满足条件,则称 为 Rn(或Cn)上的一个向量范数(或向量模)，|x|的值为向量 x 的范数。,向量1-范数：,向量2-范数：,向量无穷范数：,容易验证，以上三种范数都满足向量范数的三个条件。,理论上存在多种多样的向量范数，但最常用的是如下三种。,设向量x(x1，x2，xn)T，定义,解:对于 向量 x(1，-3，2，0)T，根据定义可以计算出：,|x|1|1|-3|2|0|6,由此例可见，向量不同范数的值不一定相同，但这并不影响对向量大小做定性的描述，因为不同范数之间存在如下等价关系。,例2.1 设向量x(1，-3，2，0)T，求向量范数|x|p，P1，2，。,定理2.1（范数的等价性）对于Rn上任何两种范数|和|，存在的正常数 m，M，使得：,范数的等价性表明，一个向量若按某种范数是一个小量，则它按任何一种范数也将是一个小量。容易证明，常用的三种向量范数满足下述等价关系。,|x|x|1 n|x|,|x|x|2|x|,|x|x|1|x|2,定义2.2 对于向量序列,及向量,如果,则称向量序列 x(k)收敛于向量 x*。记作,或,2.1.2 矩阵的范数,矩阵范数是反映矩阵“大小”的一种度量，具体定义如下。,定义2.3 设 为A的实值函数，且满足条件：,（1）|A|0，且|A|0时，当且仅当A0（2）|kA|k|A|，kR（3）|AB|A|B|则称 上的一个矩阵范数，|A|的值为矩阵A的范数。,设 n 阶矩阵 A（aij），常用的矩阵范数有：,矩阵1-范数：,矩阵2-范数：,矩阵无穷范数：,列和,行和,以上三种范数都满足矩阵范数的条件，通常将这三种矩阵范数统一表示为|A|p，P1，2，。,例2.2 设矩阵,求矩阵A的范数|A|p，P1，2，。,解 根据定义,由于,此方程的根为矩阵ATA的特征值，解得,因此,则它的特征方程为:,在线性方程组的研究中，经常遇到矩阵与向量的乘积运算，若将矩阵范数与向量范数关联起来，将给问题的分析带来许多方便。设|是一种向量范数，由此范数派生的矩阵范数定义为,注意，此式左端|A|表示矩阵范数，而右端是向量Ax 和 x 的范数，利用向量范数所具有的性质不难验证，由上式定义的矩阵范数满足矩阵范数的条件。,通常将满足上式的矩阵范数称相容范数。,由向量范数|x|p派生出的矩阵范数：,通过向量范数定义的矩阵范数，满足不等式关系：,称之为矩阵A的算子范数，其中 p1，2或。,定理2.2 由上式所定义的矩阵范数为相容范数。,证明：,当x=0时，(1)式显然成立。,2.1.3 矩阵的谱半径,矩阵范数同矩阵特征值之间有密切的联系，设是矩阵A相应于特征向量x的特征值，即 Axx,于是利用,向量-矩阵范数的相容性，得到,|x|=|x|,从而，对A的任何特征值均成立,=|Ax|,|A|x|,|A|（3）,设n阶矩阵A的n个特征值为1,2，n，称,为矩阵A的谱半径。,从(3)式得知，对矩阵A的任何一种相容范数都有(A)|A|。,2.2 迭代法的一般形式与收敛性定理,2.2.1 迭代法的一般形式,已知线性代数方程组,首先将方程组改写成等价的形式,从而建立迭代式：,称 为迭代序列，并称H为迭代矩阵。,则 是线性方程组Ax=b的解。,在等式(2.2.3)两端取极限可得,2.2.2 迭代法的收敛性,利用迭代公式(2.2.3)构造序列，以求得方程组(2.2.2)的近似解的算法称为解(2.2.2)式的简单迭代法。,若迭代序列 收敛，则称此迭代法是收敛的。,两式相减，知误差向量 满足下列迭代关系：,由此递推：,引理2.1：迭代法(2.2.3)式对任何初始近似 均收敛的充分必要条件是,引理2.2：的充要条件是,定理2.4：迭代法(2.2.3)式对任何初始近似 均收敛的充分必要条件是迭代矩阵H的谱半径,推论：若(允许为任何一种相容的矩阵范数)，则迭代法(2.2.3)式收敛。,例1 设 其中，,讨论该迭代法的收敛性。,例2 设 其中，,讨论该迭代法的收敛性。,2.2.3 迭代法的收敛速度,定理2.5 当 时，由迭代法（2.2.3）式所定义的序列 满足如下估计式：,现在讨论使误差减少初始误差的 倍所需的最少迭代次数。,若要求,则,两边取对数得:,2.3 Jacabi方法与Gauss-Seidel方法,2.3.1 Jacabi方法,设A=D-L-U,则,即迭代格式为,也可改写为,迭代矩阵为,分量形式为,2.3.2 Gauss-Seidel方法,计算第i个新分量 时，前i-1个均已求出，一般来说，,后算出来的值有更好的近似，因此可用这些新值来计算,利用最新值进行计算的方法称为Seidel迭代法。,对Jacabi迭代法运用Seidel技巧得到,在用简单迭代法,其矩阵形式为,整理成一般迭代法的形式为,例2.3 用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组,已知方程组得精确解为 x*=(1，1，1)T。,解：先改写方程如下,再写出Jacobi迭代格式,取初值为:x(0)=(0，0，0)T,求得:,x(1)=(1.4，0.5，1.4)T,x(6)=(1.00025，1.00580，1.00251)T,误差为由x*=(1，1，1)T 得到|x(6)-x*|=0.00580。,初值也取为:x(0)=(0，0，0)T,求得近似解：,Gauss-Seidel迭代格式为,初值也取为:x(0)=(0，0，0)T,求得近似解：,误差为由x*=(1，1，1)T 得到|x(4)-x*|=0.00846。,Jacobi迭代法迭代6次与Gauss-Seidel迭代法迭代4次的精度一致，说明Gauss-Seidel迭代法收敛的较快。,x(1)=(1.4，0.78，1.026)T,x(4)=(0.99154，0.99578，1.00210)T,2.3.3 对角占优矩阵与不可约矩阵,定理2.9 设A为对称正定矩阵，则Gauss-Seidel方法收敛。,例2.4 分别用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组是否收敛？,解：由于第一个方程组的系数矩阵严格对角占优，所以Jacobi迭代法和Gauss-Seidel迭代法均收敛。,第二个方程组的系数矩阵不是严格对角占优的，但可以交换两个方程的次序，将原方程变为同解方程组：,这时方程组得系数矩阵严格对角占优，两种迭代法都收敛。,例2.5 用Jacobi迭代法解下列方程组，问是否收敛？,解：方程组的系数矩阵为,非严格对角占优，无法判断迭代法是否收敛。需要通过谱半径判断，先写出Jacobi迭代法的迭代矩阵：,由于无穷范数|H|=31,还无法判断迭代法是否收敛。,这时只能通过求迭代矩阵的谱半径来判断，由迭代矩阵,解得特征值,谱半径(H)1,故Jacobi迭代法收敛.,例2.6 分别用Jacobi迭代法和Gauss-Seidel迭代法解下列方程组，问是否收敛？,由于该矩阵非严格对角占优，无法判断；但由于对称，再看是否正定。,解：系数矩阵为,各阶顺序主子式|A1|=1,|A2|=3/4,|A3|=1/2,说明矩阵对称正定,所以Gauss-Seidel迭代法收敛。但无法判断Jacobi迭代法是收敛，在利用迭代矩阵的范数或者谱半径进行判断。,由系数矩阵A,写出Jacobi迭代矩阵,其-范数|BJ|=1 和 1-范数|BJ|1=1，不小于1，还无法判断是否收敛。再求其谱半径进行判断。,由 det(I-H)=0 求得特征值1=-1，2=3=0.5,谱半径(H)=|1|=1，由此可知Jacobi迭代法是发散的。,2.4 松弛法,用 Jacobi迭代法和Gauss-Seidel迭代法解线性代数方程组时，有时收敛速度很慢，因此引入松弛法，只要松弛因子选取适当，算出的近似值就会更快地接近方程组的解，从而达到加快收敛的目的。,2.4.1 Richardson 迭代,迭代格式收敛的充分必要条件是,或者,若设 表示A的任意特征值，则该条件等价于,为了使收敛速度达到最快，应选参数，使得,最佳参数 应满足,2.4.2 Jacobi松弛法,2.4.3 SOR方法,对Gauss-Seidel方法引入参数,得到迭代格式,称(2.4.6)为解方程组Ax=b的超松弛方法,简记为SOR方法,其迭代矩阵为,矩阵形式为:,2.5 共轭梯度法,在松弛法中含有松弛因子，能使SOR迭代法收敛最快的松弛因子称为最佳松弛因子，但是最佳松弛因子的选择往往很困难。因此引入共轭梯度法，它是一种不必选择松弛因子而且收敛速度至少不低于SOR迭代法的一种迭代算法。它是50年代初期由Hestenes和Stiefel首先提出来的，目前有关的方法和理论已经相当成熟，并且已成为求解大型稀疏线性方程组最受欢迎的一类方法。,2.5.1 等价的极值问题,如果A是对称正定矩阵,则当且仅当 时，二次函数,达到极小值,而 和二次函数,它们的极小值点是相同的，所以求解方程组Ax=b等价于求二次函数H(x)的极小值点,作二次泛函(x):Rn R,(x)具有以下性质：,考虑线性方程组：Ax=b，其中 A 对称正定,(1)(x)的梯度为：,(2)对任意 x,yRn 和 R，有,(3)令 x*=A-1b，则有,定理：设 A 对称正定，则 x*是 Ax=b 的解的充要条件是,解线性方程组 Ax=b,求(x)的最小值点(极小值点),基本思想：任取一个迭代初始向量 x(0)，构造迭代序列 x(0),x(1),x(2),.，使得(x(0)(x(1)(x(2).，且每一步都以“最快的速度”下降到(x)的极小值。,具体作法：设 x(k)已经求得，计算 x(k+1)：(x)沿 x(k)处的最速下降方向，即负梯度方向 r(k)=-(Ax(k)-b)的最小值点，即,2.5.2 最速下降法,计算 k 的值,由(x)的第二个性质可得,从某个初始点 出发，沿H(x)在 点处负梯度方向,求得H(x)的极小点,即,然后从 出发，重复上述过程得到，如此继续下去，得到序列，使得,最速下降法,最速下降法的迭代格式为：,算法：(最速下降法),(1)任取 x(0)Rn，计算 r(0)=b-Ax(0),(2)对 k=0,1,2,.,计算,若，则输出 x*=x(k+1)，停止计算,收敛性,定理：设 A 对称正定，其特征值为 则由最速下降法产生的序列满足,且有,当 1 n 时，收敛会很慢，并可能出现不稳定现象(舍入误差引起),基本想法：在确定 x(k+1)时，不沿负梯度方向取极小，而是寻找一个更好的方向 p(k)，使得(x)下降得更快！,定义：设 A 对称正定，若(x,Ay)=0，则称 x,y 关于 A 正交(A-正交)或 A-共轭，若 z1,z2,.,zn 相互 A-共轭，则称 z1,z2,.,zn 构成 A-正交向量组或A-共轭向量组,2.5.3 共轭梯度法,共轭梯度法,所以具体的基本步骤是：在点 处选取新的搜索方向，使其与前一次的搜索方向 关于A共轭，即,然后从点 出发，在直线上，沿方向 求得H(x)的极小点，,由此得到方程组Ax=b的近似解序列,具体作法：令 p(0)=r(0)，设 x(k)已经求得，则 x(k+1)由下面的公式确定：,其中,几个关系式,共轭梯度法,定理：设 A 对称正定，则由 CG 算法产生的序列满足,(1)当 ij 时，(r(i),r(j)=0，即 r(0),r(1),r(2),.相互正交,(2)当 ij 时，(p(i),Ap(j)=0，即 p(0),p(1),p(2),.相互 A-共轭,共轭梯度法,k 与 k 的计算,算法：(共轭梯度法),(1)任取 x(0)Rn，计算 r(0)=b-Ax(0)，令 p(0)=r(0),(2)对 k=0,1,2,.,计算,若，则输出 x*=x(k+1)，停止计算,收敛性,定理：设 A 对称正定，则共轭梯度法至多 n 步就能找到精确解。,r(0),r(1),.,r(n)相互正交，则至少有一个为 0,定理：设 A 对称正定，x*为精确解，x(k)为共轭梯度法的数值解，则有,其中,2.6 条件数与病态方程组,引进了矩阵的度量标准范数，就可以对方程组求解进行误差分析，对于方程组,Ax=b,如果常数项产生了误差b,并设求解时产生的误差为x，则有,A(x+x)=b+b,两式相减得到 Ax=b,当系数矩阵可逆时,x=A-1b,取范数,|x|=|A-1b|,|A-1|b|,再由 Ax=b，得到,|b|=|Ax|,|A|x|,于是，由|x|A-1|b|,得到解的相对误差为,及|b|A|x|,令 Cond(A)=|A|A-1|,并称其为矩阵A的条件数。,这时,可见，求解线性方程组所产生的误差与系数矩阵的条件数有关。,对于线性方程组 Ax=b，如果系数矩阵的条件数Cond(A)=|A|A-1|太大，则称相应的方程组为病态方程组。,病态现象是方程组的固有属性，无法改变，因此在求解时为了不至于产生太大的误差，应该尽量减少原始数据 A、b 的误差，或者用高精度的计算机计算。,例如：对于方程组,系数矩阵和逆矩阵分别为,可以求得,条件数比较大，可见该方程组为病态方程组。,谱条件数：,其中 分别是按模最小和最大的特征值,如果A是对称非奇异矩阵，A的谱条件数就等于Cond2(A)。,