5线性方程组迭代法1.ppt

1、第二章第二章 解线性方程组的迭代法解线性方程组的迭代法/*Iterative Techniques for Solving Linear Systems*/求解求解bxA 思思路路与解与解 f(x)=0 的不动点迭代相似的不动点迭代相似，将，将 等价等价bxA 改写为改写为 形式，建立迭代形式，建立迭代 。从初值从初值 出发，得到序列出发，得到序列 。fxBx fxBxkk )()1()0(x)(kx计算精度可控，特别适用于求解系数为大型稀疏计算精度可控，特别适用于求解系数为大型稀疏矩阵矩阵/*sparse matrices*/的方程组。的方程组。研究研究 内容：内容：如何建立迭代格式？如何建

2、立迭代格式？收敛速度？收敛速度？向量序列的收敛条件？向量序列的收敛条件？误差估计？误差估计？1 向量和矩阵范数向量和矩阵范数/*Norms of Vectors and Matrices*/为了误差的度量为了误差的度量 向量范数向量范数 /*vector norms*/定义定义Rn空间的空间的向量范数向量范数|对任意对任意 满足下列条件：满足下列条件：nRyx,00|;0|)1(xxx（正定性正定性/*positive definite*/)|)2(xx C 对任意对任意(齐次性齐次性/*homogeneous*/)|)3(yxyx （三角不等式三角不等式 /*triangle inequal

3、ity*/)常用向量范数：常用向量范数：niixx11|niixx122|pnipipxx/11|max|1inixx|limxxpp1 Norms of Vectors and Matrices Vector Norms定义定义向量序列向量序列 收敛收敛于向量于向量 是指对每一个是指对每一个 1 i n 都都有有 。)(kx*x*)(limikikxx 可以理解为可以理解为0|*|)(xxk定义定义若存在常数若存在常数C 0 使得对任意使得对任意 有有 ,则则称称范数范数|A 比范数比范数|B 强强。nRx BAxCx|定义定义若范数若范数|A 比比|B 强，同时强，同时|B 也比也比|A

4、强，即强，即存在常数存在常数 C1、C2 0 使得使得 ，则称，则称|A 和和|B 等价等价。BABxCxxC|21 定理定理Rn 上一切范数都等价。上一切范数都等价。可以理解为对任何可以理解为对任何向量范数都成立。向量范数都成立。HW:p.62#6,#71 Norms of Vectors and Matrices Matrix Norms 矩阵范数矩阵范数 /*matrix norms*/定义定义Rm n空间的空间的矩阵范数矩阵范数|对任意对任意 满足：满足：nmRBA ,00|;0|)1(AAA（正定性正定性/*positive definite*/)|)2(AA C 对任意对任意(齐次

5、性齐次性/*homogeneous*/)|)3(BABA （三角不等式三角不等式 /*triangle inequality*/)(4)*|AB|A|B|（相容相容 /*consistent*/当当 m=n 时时)In general,if we have|AB|A|B|,thenthe 3 norms are said to be consistent.Oh havent I had enough of new concepts?What do I need the consistency for?When you have to analyze the error bound of AB

6、imagine you doing it without a consistent matrix norm1 Norms of Vectors and Matrices Matrix Norms常用矩阵范数：常用矩阵范数：Frobenius 范数范数 ninjijFaA112|向量向量|2的直接推广的直接推广 对方阵对方阵 以及以及 有有nnRA nRx 22|xAxAF 利用利用Cauchy 不等式不等式 可证。可证。22|yxyx 算子算子范数范数/*operator norm*/由向量范数由向量范数|p 导出关于矩阵导出关于矩阵 A Rn n 的的 p 范数范数:pxpppxAxxAAp

7、x|max|max|10|则则ppppppxAxABAAB|特别有：特别有：njijaAni1|max|1（行和范数行和范数）niijaAnj11|max|1（列和范数列和范数）)(|max2AAAT （谱范数谱范数/*spectral norm*/）矩阵矩阵 ATA 的最大的最大特征根特征根/*eigenvalue*/HW:p.62#2,#4,#51 Norms of Vectors and Matrices Matrix Norms注：注：Frobenius 范数范数不是不是算子范数。算子范数。我们只关心有相容性的范数，我们只关心有相容性的范数，算子范数算子范数总是相容的。总是相容的。即使

8、即使 A中元素全为实数，其特征根和相应特征向量中元素全为实数，其特征根和相应特征向量/*eigenvector*/仍可能是复数。将上述定义中绝对值换仍可能是复数。将上述定义中绝对值换成成复数模复数模均成立。均成立。若不然，则必存在某个向量范数若不然，则必存在某个向量范数|v 使得使得 对任意对任意A 成立。成立。vvFxxAAx|max|0 Counterexample?1|max|0 vvFxxIInx 谱半径谱半径 /*spectral radius*/定义定义矩阵矩阵A的的谱半径谱半径记为记为 (A)=，其中，其中 i 为为 A 的特征根。的特征根。|max1ini ReIm (A)1

9、Norms of Vectors and Matrices Spectral Radius定理定理对任意算子范数对任意算子范数|有有|)(AA 证明：证明：由算子范数的相容性，得到由算子范数的相容性，得到|xAxA 将任意一个特征根将任意一个特征根 所对应的特征向量所对应的特征向量 代入代入u|uAuA|uu 定理定理若若A对称，则有对称，则有)(|2AA 证明：证明：)()(|2maxmax2AAAAT A对称对称若若 是是 A 的一个特征根，则的一个特征根，则 2 必是必是 A2 的特征根。的特征根。又：对称矩阵的特征根为实数，即又：对称矩阵的特征根为实数，即 2(A)为非负实数，为非负实数，故得证。故得证。)()(22maxAA 对某个对某个 A 的特征根的特征根 成立成立所以所以2-范数亦称为范数亦称为谱范数谱范数。1 Norms of Vectors and Matrices Spectral Radius定理定理若矩阵若矩阵 B 对某个算子范数满足对某个算子范数满足|B|1，则必有，则必有BI 可逆；可逆；|111BBI 证明：证明：若不然，则若不然，则 有非零解，即存在非零向有非零解，即存在非零向量量 使得使得 0)(xBI0 x00 xxB 1|00 xxB1|B IBIBI 1)(11)()(BIBBI11)()(BIBIBI|)(|1|)(|11 BIBBI