数值分析第三章解线性方程组的迭代法.ppt

《数值分析第三章解线性方程组的迭代法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章解线性方程组的迭代法Jacobi迭代法Gauss-Seidel迭代法迭代法的收敛条件(充要条件,充分条件)求迭代法概述1迭代法概述等价线性方程组取初始向量x(0)Rn,构造如下单步定常线性迭代公式以此来产生近似向量序列x(1),x(2),...当k充分大时，基本思想等价变形如何做收敛性条件M:迭代矩阵2定义对于Rn中的向量序列{x(k)},如果则称向量序列{x(k)}收敛于Rn中的向量x.定义对于n阶方阵序列{A(k)},如果则称方阵序列{A(k)}收敛于n阶方阵A.上面两式通常表示成向量序列与矩阵序列的收敛概念3

2、定理Rn中的向量序列{x(k)}收敛于Rn中的向量x的充分必要条件是其中xj(k)和xj分别表示x(k)和x中的第j个分量.定理n阶方阵序列{A(k)}收敛于n阶方阵A的充分必要条件是向量序列与矩阵序列收敛的充分必要条件向量序列和矩阵序列的收敛可归结为对应分量或对应元素序列的收敛性.4若由迭代公式产生的向量序列{x(k)}收敛于向量x，则即向量x是方程Ax=b的解.单步定常线性迭代法产生的向量序列若收敛则必收敛到原线性方程组的解.5n=4的Jacobi迭代法把方程组改写成如下等价形式6n=4的Jacobi迭代法计算公式已知用上

3、述迭代公式可算得7n=4的Jacobi迭代法矩阵表示8Jacobi迭代法(k)(k)(k)(k)(k+1)9设D为由A的对角线元素构成的对角矩阵Jacobi迭代公式Jacobi迭代法的矩阵表示迭代矩阵10例用Jacobi迭代法求解线性方程组解将方程组改写成如下等价形式11Jacobi迭代法计算公式为假设初始向量取x(0)=(0,0,0)T.第一次迭代第二次迭代12实际计算时，迭代法中止条件其中为给定的要求精度.13n=4的Gauss-Seidel迭代法把方程组改写成如下等价形式14n=4的Gauss-Seidel迭代法1

4、5Gauss-Seidel迭代法(k)(k)(k+1)(k+1)(k+1)16在迭代的每一步设定计算顺序并且，在计算迭代值充分利用它前面的新信息这样设计出来的迭代公式称为高斯—塞德尔迭代公式.Gauss-Seidel迭代法17Gauss-Seidel迭代法的矩阵表示设将系数矩阵A分裂为其中D为对角阵,L和U分别为严格下三角和严格上三角阵.迭代矩阵Gauss—Seidel迭代公式18例用Gauss-Seidel迭代法求解线性方程组解将方程组改写成如下等价形式19Gauss-Seidel迭代法计算公式为假设初始向量取x(0)=(0,

5、0,0)T.第一次迭代20第二次迭代Gauss-Seidel迭代法计算公式为假设初始向量取x(0)=(0,0,0)T.21Jacobi迭代法：x(k+1)分量的计算可以同时进行，无先后次序Gauss-Seidel迭代法：x(k+1)分量的计算有先后次序，必须先计算x(k+1)前面的分量然后再计算下一分量.22Jacobi迭代法与Gauss-Seidel迭代法的计算效果哪一种更好？前例计算结果表明,用Gauss-Seidel迭代法比用Jacobi迭代法效果好.但对一般情形,有些问题Gauss-Seidel迭代法确实比Jacobi迭

6、代法收敛得快,但也有Gauss-Seidel迭代法比Jacobi迭代法收敛得慢,甚至还有Jacobi迭代法收敛,但Gauss-Seidel迭代法发散的情形.23迭代法的收敛条件定义(谱半径)设n阶方阵A的特征值为i(i=1,2,…,n)，则称为矩阵A的谱半径.Ak的特征值为故24矩阵范数和谱半径有如下关系设A的任一特征值为i,对应的特征向量为ui,则由的任意性可知结论成立.矩阵A的谱半径不超过它的任何一种由向量范数诱导出的范数，即

7、

8、A

9、

10、是A的特征值的上界.证故从而25设A为n阶方阵，则由于2-范数具有上面的关系式，所

11、以称

12、

13、A

14、

15、2为谱范数.26定理设A是任意n阶方阵，由A的各次幂所组成的矩阵序列收敛于零矩阵，即的充分必要条件是27定理对任何初始向量x(0)和右端项g，由迭代公式x(k+1)=Mx(k)+g(k=0,1,2,…)产生的向量序列{x(k)}收敛的充分必要条件是(M)<1其中(M)是迭代矩阵M的谱半径.迭代法收敛的充分必要条件迭代法的收敛性只与迭代矩阵的谱半径有关,而迭代矩阵是由A演变来的,因此迭代法是否收敛只与系数矩阵A以及演变的方式有关,与常数项和初始向量的选择无关.28证明必要性.设序列{x(k)}收敛于x*，则有迭代法收

16、敛的充分必要条件任意收敛故由于x(0)为任意n维向量,即29迭代法收敛的充分必要条件任意收敛充分性.若(M)<1,则=1不是M的特征值,故方程(I－M)x=g有唯一解,记为x*,即又且故