当前课程知识点：数值分析 > 第三章 解线性方程组的迭代法 > 3.3 误差分析 > 误差分析
上一节我们介绍的是迭代法收敛充要条件
迭代法收敛的充要条件是
迭代矩阵的谱半径要严格的小于1
计算迭代矩阵的谱半径就需要
计算矩阵的特征值
实际上
矩阵的特征值计算
也是一件非常困难的事
所以我们今天来介绍
两个比较好用的充分条件
可以直接根据
系数矩阵的特点来判断
迭代法的收敛性
我们先给一个概念
叫严格对角占优阵
对于一个n阶方阵a
如果它是严格对角占优的
我们指的就是
在这个矩阵里边
对角线上的元素的绝对值
严格大于非对角线上
元素绝对值的和
也就是说在同一行里
边我们算对角线上面的元素的绝对值
然后再把非对角线上的元素的绝对值相加
如果对角线上
元素的绝对值严格大于
其他元素绝对值的和
我们就说这个矩阵是严格对角占优的
那如果
线性方程组的系数矩阵是严格对角占优的
我们就说这个线性方程组
是严格对角占优线性方程组
我们下面给了两个矩阵
A矩阵和B矩阵
大家可以根据我们刚刚给的
严格对角占优矩阵来判断一下
它们是不是属于严格对角占优的
显然A矩阵是严格对角占优的
但B矩阵就不是了
第2行第2列的元素是6
跟6在同一行上的元素
-1、2、5显然它们绝对值的和是8
这就不是严格对角占优的
我们给出的两个比较好用的迭代法
收敛性判别的充分条件
就用到了这个概念
第1个充分条件就是
如果系数矩阵是严格对角占优的
那么求解线性方程组Ax=b的
Jacobi迭代和Gauss-Seidel迭代法
就一定都是收敛的
大家想这个结论非常好用
因为你不需要去计算迭代矩阵的特征值
只需要观察一下
系数矩阵是不是严格对角占优的
我们给的第2个结论是
如果系数矩阵是对称正定的
那么求解线性方程组
Ax=b的Gauss-Seidel迭代法
就一定是收敛的
大家可以看到这两个结论
非常的好用
只需要对系数矩阵
去做判别就可以
只需要观察系数矩阵的特点
而不需要去
写迭代法的迭代矩阵
如果能用这个充分条件进行做判别的时候
我们一般就不用充要条件
显然充分条件用起来的时候更加的方便
比方说我们给了下面的这个线性方程组
我们给出系数矩阵
大家稍微观察一下就可以看出来
系数矩阵是严格对角占优的
所以不论你用Jacobi迭代
还是Gauss-Seidel迭代法它都是收敛的
那如果给出的线性方程组
它不满足严格对角占优的
你总可以通过
调换方程组里边方程的次序
然后了使得调换以后的线性方程组
系数矩阵严格对角占优
比方说我们下面给出来的A矩阵
是一个2×2的系数矩阵
显然它不是严格对角占优的
那如果我把第1行和第2行做一个交换
它就变成严格对角占优了
把第1行第2行做个交换
本质上就是把两个方程的位置调换一下
并不影响原来方程组的解
但是这样
设计迭代法的时候就会有很好的性质
无论你用Jacobi迭代
还是Gauss-Seidel迭代
它都能保证收敛性
我们下面再看一个例子
这个线性方程组是一个三元一次线性方程组
它的系数矩阵是A
观察一下
它现在不是严格对角占优
因为第二行它的对角线的元素是2
非对角线元素值之和也是2
所以不是严格对角占优
但是它是对称的
对称性大家是一眼就能看出来的
然后了我们再去验证它的正定性
验证正定性有很多方便的方法
比方说大家可以通过计算各阶的顺序的主子式
是很容易能够判断它是否是正定的
在这里大家做个验证就可以知道
这个矩阵A是对称正定的
所以Gauss-Seidel迭代肯定是收敛的
那么对于Jacobi迭代法它是否收敛呢
我们不能通过系数矩阵的特点来判别
所以如果用Jacobi迭代法去计算
看它是不是收敛的话
我们需要再求助一些充要条件
就是去计算迭代矩阵的谱半径
我们下面再看一个例子
比方说这个矩阵A是线性方程组
Ax=b的的系数矩阵
让你讨论两种常用的迭代方法
Jacobi迭代和Gauss-Seidel迭代法
是不是都是收敛的
显然它是对称的
我们也可以验证它也是正定的
所以Gauss-Seidel迭代法它是收敛的
但是它不是严格对角占优的
所以我们在判断
Jacobi迭代法是不是收敛的时候
就要求助于充要条件
去写出这这个线性方程组
Jacobi迭代法的迭代矩阵
通过计算我们可以得到
它迭代矩阵的特征方程
把特征方程求出以后
我们可以得到特征值
发现它有特征值等1的情况
所以迭代矩阵的谱半径是等一的
它不严格小一
所以说用Jacobi迭代它一定会发散的
下面我们再介绍一个关于误差估计的结论
我们先把结论的具体形式给出来
如果由迭代格式X（k+1）
也就是（k+1）步的迭代值
是由k步的迭代值
通过m乘k步的迭代值加上g得到
如果迭代矩阵的
范数是小1的
那么由这个迭代格式产生的迭代序列
一定是收敛的
并且有下面的三个估计式
我们观察一下这三个估计式的特点
第1个给出来的是迭代到第K步的时候
迭代出来的向量和x*之间的距离
跟x（0）跟x*之间的距离的关系
也就是说第1个给出来的实际上
是收敛性的结果
同时也可以看出它的收敛速度
是由什么来决定的
是由迭代矩阵的范数来决定的
因为它收敛速度了
是由M的范数的K次方来决定的
所以就由M的范数决定的
第2个式子它给出来的
是第K次迭代结果
跟准确值之间的距离
跟初值和第1次迭代结果之间的关系
那么通过这个关系
我们仍然可以看出
它的收敛性是跟M的范数有关
同时我们也可以借助
这个表达式来先验的
估计一下至少
需要迭代多少次才能
得到满足精度要求的解
那第3个表达式给出来的
是EKP的迭代结果
跟准确值之间的距离
跟第K步迭代结果
跟第K减一步迭代结果之间的关系
第3个结论非常的有用
因为我们之前在做迭代法
计算的时候来判断迭代停止的条件
就用到了这个
我们都是用相邻两次迭代值之间的距离
来判断是不是足够小
来判断迭代是否停止
我们下边来分析一下
这三个不等式它的正确性
最主要了就是
用到我们之前介绍的
范数的运算关系
我们先来看第1个
因为迭代矩阵的范数是小于的
所以说它的普半径一定小于一
收敛性是一定满足的
我们把收敛的极限记成 x*
x*就一定是x=mx+g的解
我们用迭代这个等式
左右两边分别相减
就可以得到
xk-x*跟
xk-1-x*之间的一个递推关系
把这个递推关系递推到x(0)-x*
就可以得到我们要的第1个不等式
通过第1个不等式我们可以看出
xk趋近于x*的
速度是由M的范数来决定的
接下来我们分析后边
两个不等式的正确性
为了分析后边两个不等式的正确性
我们需要知道
迭代的相邻两步的迭代值之间的距离
和第k步的迭代值
跟准确值之间距离的关系
这里边我们用到一个稍微小的一个技巧
就是在xk+1-xk之间
我们加一个x*再减去x*
这样利用三角不等式
它是大于等于x*-xk的范数
再去减去x*-xk+1的范数
然后再利用
M的范数是小1的
我就可以知道
x*-xk+1的范数
它是小于等于M的范数倍的
x*-xk的范数
利用这个结果我们就可以给出
xk+1-xk的范数是
大于等于1-M的范数倍的
x*-xk的范数
通过这个结论我们很容易给出
第2个不等式
也可以很容易给出第3个不等式
第3个不等式给出来的是
x*-跟xk之间的距离
它是小于等于M的范数
比上1-M的范数乘上xk-xk+1
根据上面的这个结论
我们可以得出x*-xk小于=1-M
的范数分之一倍的xk+1减去xk
我们再根据xk+1-xk的范数
跟xk-xk-1的递推关系
就可以很容易证明第3个不等式
第3个不等式也是我们要的重要结论
这也是我们经常
在进行迭代法计算的时候
用了停机准则的理论
如果我要求误差是要小于ε
那么我们只需要让相邻两项
之间的距离小于
M的范数分之1-M的范数倍的ε就可以
实际当中计算的时候
如果M不是太接近于1
我们可以把这个系数忽略
可以直接让
相邻两项之间的距离
小于ε作为停机准则
如果我想事先估计出迭代的次数
我们就可以利用第2个不等式
因为迭代一次以后你就可以算出x1
所以x1和x0之间的范数
x1减x0的范数很容易算出来
然后
我再用M的范数的
K次方比上1减M
的范数乘上x1和x0差的范数
去让它小于
我给事先给定的精度ε
就可以分析出K要满足的不等式
这样就可以知道
至少要迭代多少次才能
得到满足精度要求的解
通过这一部分的介绍
我们可以看到迭代法
收敛性的判别准则有两种
一种是充要条件
一种是充分条件
充要条件就是通过
迭代矩阵的谱半径来判别
计算迭代矩阵的谱半径来判别
需要迭代矩阵的谱半径严格小1
充分条件
就是通过系数矩阵的特点
系数矩阵如果是严格对角占优的
那么用Jacobi迭代
和Gauss-Seidel迭代都是收敛的
如果系数矩阵是对称正定的
那么Gauss-Seidel迭代法就一定是收敛的
迭代法的收敛速度
是由迭代矩阵的范数来决定的
关于迭代法的收敛性
我们就介绍到这
-1.1 误差的概念
--误差的概念
-1.2 误差的传播
--误差的传播
-第一章 习题
--第一章 习题
-2.1 Gauss消去法
--Gauss消去法
-2.2 矩阵的三角分解
--矩阵的三角分解
-2.3 直接三角分解法
--直接三角分解法
-2.4 平方根法和改进的平方根法
-2.5 误差分析（1）向量和矩阵范数
-2.6 误差分析（2）条件数
-第二章 习题
--第二章 习题
-3.1 Jacobi迭代法和Gauss-Seidel 迭代法
-3.2 迭代法收敛性的判别
-3.3 误差分析
--误差分析
-第三章 习题
--第三章 习题
-4.1 幂法
--幂法
-4.2 反幂法
--反幂法
-第四章 习题
--第四章 习题
-5.1 多项式插值理论
--多项式插值理论
-5.2 Lagrange 插值多项式
-5.3 Newton 插值多项式（1）差商型
-5.4 Newton 插值多项式（2）差分型
-5.5 分段线性插值
--分段线性插值
-5.6 Hermite 插值
-第五章 习题
--第五章 习题
-6.1 数据拟合的最小二乘法（1）多项式拟合
-6.2 数据拟合的最小二乘法（2）其他函数拟合
-6.3 正交多项式
--正交多项式
-6.4 函数的最佳平方逼近
-第六章 习题
--第六章 习题
-7.1 数值微分
--数值微分
-7.2 Newton－Cotes求积公式（1）数值积分的基本思想、Newton－Cotes公式
--Newton－Cotes求积公式（1）数值积分的基本思想、Newton－Cotes公式
-7.3 Newton－Cotes求积公式（2）误差估计
-7.4 复化求积公式
--复化求积公式
-7.5 Romberg求积公式、Gauss型求积公式
-第七章 习题
--第七章 习题
-8.1 Romberg求积公式、Gauss型求积公式
-8.2 简单迭代法的加速、牛顿法与弦截法
-第八章 习题
--第八章 习题
-9.1 常微分方程数值解法概述
-9.2 Euler方法及其改进方法
-第九章 习题
--第九章 习题
