第2章解线性代数方程组的迭代法ppt课件.ppt
《第2章解线性代数方程组的迭代法ppt课件.ppt》由会员分享,可在线阅读,更多相关《第2章解线性代数方程组的迭代法ppt课件.ppt(73页珍藏版)》请在三一办公上搜索。
1、第2章 解线性代数方程组的迭代法,求解线性代数方程组主要有直接法和迭代法两种常见方法。直接法一般适合小型的系数矩阵,为了求解现实当中常见的大型稀疏矩阵,下面我们将重点介绍迭代法。它是一种不断套用一个迭代公式,逐步逼近方程的解的方法。将讨论两类主要方法,一类是逐步逼近法,另一类是下降法,包括最速下降法和共轭梯度法。,为了对线性方程组数值解的精确程度,以及方程组本身的性态进行分析,需要对向量和矩阵的“大小”引进某种度量,范数就是一种度量尺度,向量和矩阵的范数在线性方程组数值方法的研究中起着重要的作用。,2.1 向量、矩阵范数与谱半径,(2)齐次性:对任何实数和向量x|kx|k|x|,(3)三角不等
2、式:对任何向量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,由此例可见,向量不同范数的值不一定相同,但这并不影响对
3、向量大小做定性的描述,因为不同范数之间存在如下等价关系。,例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 设
4、 为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的特征值,解得,因此,则它的特征方程为:,在线性方程组的研究中,经常遇到矩阵与向量的乘积运算,若将矩阵范数与向量范数关联起来,将
5、给问题的分析带来许多方便。设|是一种向量范数,由此范数派生的矩阵范数定义为,注意,此式左端|A|表示矩阵范数,而右端是向量Ax 和 x 的范数,利用向量范数所具有的性质不难验证,由上式定义的矩阵范数满足矩阵范数的条件。,通常将满足上式的矩阵范数称相容范数。,由向量范数|x|p派生出的矩阵范数:,通过向量范数定义的矩阵范数,满足不等式关系:,称之为矩阵A的算子范数,其中 p1,2或。,定理2.2 由上式所定义的矩阵范数为相容范数。,证明:,当x=0时,(1)式显然成立。,2.1.3 矩阵的谱半径,矩阵范数同矩阵特征值之间有密切的联系,设是矩阵A相应于特征向量x的特征值,即 Axx,于是利用,向量
6、-矩阵范数的相容性,得到,|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)式
7、的简单迭代法。,若迭代序列 收敛,则称此迭代法是收敛的。,两式相减,知误差向量 满足下列迭代关系:,由此递推:,引理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)式所定义的序列 满足如下估计式:,现在讨论使误差减少初始误差的 倍
8、所需的最少迭代次数。,若要求,则,两边取对数得:,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迭代法解下列方程组,已知方程组得精确解
9、为 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次的精度一致,说
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性代数 方程组 迭代法 ppt 课件
链接地址:https://www.31ppt.com/p-2104287.html