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

数值分析第三章解线性方程组的迭代法1第1页，课件共49页，创作于2023年2月迭代法概述等价线性方程组取初始向量x(0)Rn,构造如下单步定常线性迭代公式以此来产生近似向量序列x(1),x(2),...当k充分大时，基本思想等价变形如何做收敛性条件M:迭代矩阵2第2页，课件共49页，创作于2023年2月定义对于Rn中的向量序列{x(k)},如果则称向量序列{x(k)}收敛于Rn中的向量x.定义对于n阶方阵序列{A(k)},如果则称方阵序列{A(k)}收敛于n阶方阵A.上面两式通常表示成向量序列与矩阵序列的收敛概念3第3页，课件共49页，创作于2023年2月定理

Rn中的向量序列{x(k)}收敛于Rn中的向量x的充分必要条件是其中xj(k)和xj分别表示x(k)和x中的第j个分量.定理n阶方阵序列{A(k)}收敛于n阶方阵A的充分必要条件是向量序列与矩阵序列收敛的充分必要条件向量序列和矩阵序列的收敛可归结为对应分量或对应元素序列的收敛性.4第4页，课件共49页，创作于2023年2月若由迭代公式产生的向量序列{x(k)}收敛于向量x，则即向量x是方程Ax=b的解.单步定常线性迭代法产生的向量序列若收敛则必收敛到原线性方程组的解.5第5页，课件共49页，创作于2023年2月

n=4的Jacobi迭代法把方程组改写成如下等价形式6第6页，课件共49页，创作于2023年2月

n=4的Jacobi迭代法计算公式已知用上述迭代公式可算得7第7页，课件共49页，创作于2023年2月

n=4的Jacobi迭代法矩阵表示8第8页，课件共49页，创作于2023年2月

Jacobi迭代法(k)(k)(k)(k)(k+1)

9第9页，课件共49页，创作于2023年2月设D为由A的对角线元素构成的对角矩阵Jacobi迭代公式

Jacobi迭代法的矩阵表示迭代矩阵10第10页，课件共49页，创作于2023年2月例用Jacobi迭代法求解线性方程组解将方程组改写成如下等价形式11第11页，课件共49页，创作于2023年2月Jacobi迭代法计算公式为假设初始向量取x(0)=(0,0,0)T.第一次迭代第二次迭代12第12页，课件共49页，创作于2023年2月实际计算时，迭代法中止条件其中为给定的要求精度.13第13页，课件共49页，创作于2023年2月

n=4的Gauss-Seidel迭代法把方程组改写成如下等价形式14第14页，课件共49页，创作于2023年2月

n=4的Gauss-Seidel迭代法15第15页，课件共49页，创作于2023年2月

Gauss-Seidel迭代法(k)(k)(k+1)(k+1)(k+1)

16第16页，课件共49页，创作于2023年2月在迭代的每一步设定计算顺序并且，在计算迭代值充分利用它前面的新信息这样设计出来的迭代公式称为高斯—塞德尔迭代公式.

Gauss-Seidel迭代法17第17页，课件共49页，创作于2023年2月

Gauss-Seidel迭代法的矩阵表示设将系数矩阵A分裂为其中D为对角阵,L和U分别为严格下三角和严格上三角阵.迭代矩阵Gauss—Seidel迭代公式18第18页，课件共49页，创作于2023年2月例用Gauss-Seidel迭代法求解线性方程组解将方程组改写成如下等价形式19第19页，课件共49页，创作于2023年2月Gauss-Seidel迭代法计算公式为假设初始向量取x(0)=(0,0,0)T.第一次迭代20第20页，课件共49页，创作于2023年2月第二次迭代Gauss-Seidel迭代法计算公式为假设初始向量取x(0)=(0,0,0)T.21第21页，课件共49页，创作于2023年2月Jacobi迭代法：x(k+1)分量的计算可以同时进行，无先后次序Gauss-Seidel迭代法：x(k+1)分量的计算有先后次序，必须先计算x(k+1)前面的分量然后再计算下一分量.22第22页，课件共49页，创作于2023年2月Jacobi迭代法与Gauss-Seidel迭代法的计算效果哪一种更好？前例计算结果表明,用Gauss-Seidel迭代法比用Jacobi迭代法效果好.但对一般情形,有些问题Gauss-Seidel迭代法确实比Jacobi迭代法收敛得快,但也有Gauss-Seidel迭代法比Jacobi迭代法收敛得慢,甚至还有Jacobi迭代法收敛,但Gauss-Seidel迭代法发散的情形.23第23页，课件共49页，创作于2023年2月迭代法的收敛条件定义(谱半径)设n阶方阵A的特征值为i

(i=1,2,…,n)，则称为矩阵A的谱半径.Ak的特征值为故24第24页，课件共49页，创作于2023年2月矩阵范数和谱半径有如下关系设A的任一特征值为i,

对应的特征向量为ui,则由的任意性可知结论成立.矩阵A的谱半径不超过它的任何一种由向量范数诱导出的范数，即||A||是A的特征值的上界.证故从而25第25页，课件共49页，创作于2023年2月设A为n阶方阵，则由于2-范数具有上面的关系式，所以称||A||2为谱范数.26第26页，课件共49页，创作于2023年2月定理设A是任意n阶方阵，由A的各次幂所组成的矩阵序列收敛于零矩阵，即的充分必要条件是27第27页，课件共49页，创作于2023年2月定理对任何初始向量x(0)和右端项g，由迭代公式

x(k+1)=Mx(k)+g(k=0,1,2,…)产生的向量序列{x(k)}收敛的充分必要条件是(M)<1其中(M)是迭代矩阵M的谱半径.迭代法收敛的充分必要条件迭代法的收敛性只与迭代矩阵的谱半径有关,而迭代矩阵是由A演变来的,因此迭代法是否收敛只与系数矩阵A以及演变的方式有关,与常数项和初始向量的选择无关.28第28页，课件共49页，创作于2023年2月证明必要性.设序列{x(k)}收敛于x*，则有迭代法收敛的充分必要条件任意收敛故由于x(0)为任意n维向量,即29第29页，课件共49页，创作于2023年2月迭代法收敛的充分必要条件任意收敛充分性.若(M)<1,则=1不是M的特征值,故方程(I－M)x=g有唯一解,记为x*,即又且故对任意初始向量x(0),均有证明30第30页，课件共49页，创作于2023年2月推论1若迭代矩阵M满足||M||<1,则下列迭代公式对任意初始向量x(0)收敛31第31页，课件共49页，创作于2023年2月例解方程组讨论Jacobi迭代法与Gauss-Seidel迭代法的收敛性.解迭代法是否收敛等价于迭代矩阵的谱半径是否小于1，故先求迭代矩阵32第32页，课件共49页，创作于2023年2月Jacobi迭代法的迭代矩阵为其特征方程为特征值谱半径故Jacobi迭代法收敛.33第33页，课件共49页，创作于2023年2月Gauss-Seidel迭代法的迭代矩阵为34第34页，课件共49页，创作于2023年2月其特征方程为特征值谱半径故Gauss-Seidel迭代法发散.35第35页，课件共49页，创作于2023年2月一般来说,计算矩阵的谱半径比较困难,故用迭代法收敛的充分必要条件来判断迭代法是否收敛往往不太容易,以下介绍用其他方法判别迭代法收敛的充分条件.36第36页，课件共49页，创作于2023年2月定义(严格对角占优阵)称n阶方阵是严格对角占优的，如果其主对角线元素的绝对值大于同行其它元素绝对值之和：若线性方程组的系数矩阵为严格对角占优阵，则称这个线性方程组为严格对角占优方程组.37第37页，课件共49页，创作于2023年2月迭代法收敛的充分条件定理若A为严格对角占优阵,则求解Ax=b的Jacobi迭代法和Gauss-Seidel迭代法均收敛.定理若A为对称正定阵,则求解Ax=b的Gauss-Seidel迭代法收敛.38第38页，课件共49页，创作于2023年2月例方程组Ax=b的系数矩阵为严格对角占优阵.故Jacobi迭代法与Gauss-Sidel迭代法均收敛.39第39页，课件共49页，创作于2023年2月例方程组Ax=b的系数矩阵为非对角占优阵交换两个方程的次序，得原方程组的同解方程组它是一个严格对角占优方程组，对此方程组Jacobi迭代法和Gauss-Seidel迭代法均收敛.当所给的方程组不满足迭代法的收敛条件时,适当调整方程组中方程的次序,有时可得到满足迭代法收敛条件的同解方程组.40第40页，课件共49页，创作于2023年2月例方程组Ax=b的系数矩阵为但A为对称正定矩阵，Gauss-Seidel迭代法收敛.非严格对角占优41第41页，课件共49页，创作于2023年2月例设有方程组Ax=b,其中讨论用两种迭代法求解的收敛性.解A是对称正定阵故Gauss-Seidel迭代法收敛.A不是严格对角占优阵42第42页，课件共49页，创作于2023年2月Jacobi迭代法的迭代矩阵为其特征方程为特征值为故迭代矩阵的谱半径为由迭代法收敛的充分必要条件知Jacobi迭代法发散.43第43页，课件共49页，创作于2023年2月误差估计定理设由迭代格式x(k+1)=Mx(k)+g,若||M||<1,则{x(k)}收敛于x*,且有误差估计式44第44页，课件共49页，创作于2023年2月证明由以上两式得故45第45页，课件共49页，创作于2023年2月证明