第3章 解线性方程组的迭代解法

数值分析——第3章解线性方程组的迭代解法解非线性方程：f(x)=0x=(x)令xk+1=(xk)，若xk,则对于线性方程组Ax=b.考虑等价方程组x=Bx+f,为此构造序列：x(k+1)=Bx(k)+f——向量的迭代公式.要考虑向量列的收敛性，误差，向量间的距离.11kkkxxLLx考虑距离3.2基本概念3.2.1向量与矩阵的范数回顾：Rn中向量的范数：性质：①x:||x||0,且||x||=0x=0②kR,x:||kx||=|k|||x||③x,y:||x+y||||x||+||y||3.2基本概念3.2.1向量与矩阵的范数1.向量范数【定义3-1】设V为线性空间，V上的实值函数N(x)=||x||满足：①正定性：xV:||x||0,且||x||=0x=0②正齐性：kR,xV:||kx||=|k|||x||③三角不等式：x,yV:||x+y||||x||+||y||则称N(x)=||x||为V上向量x的范数.3.2基本概念3.2.1向量与矩阵的范数性质：①若x0,②||–x||=||x||③|||x||–||y|||||x–y||1||||xx3.2基本概念3.2.1向量与矩阵的范数线性空间可以定义各种范数.其中最常用的有：x=(x1,x2,…,xn)Rn(Cn)①欧式范数：——又称为2-范数②最大模范数：——又称为-范数③绝对值范数：——又称为1-范数④p范数：niiiniixxxx1122inixx1maxniixx11)1(11pxxpnipip3.2基本概念3.2.1向量与矩阵的范数注：①可以证明上述定义均满足向量的范数定义.②2-范数和1-范数都是p-范数的特例.③-范数也是p-范数的特例.(∵令p，有||x||p||x||)..||max)||max(||||||max1111ipppipnipipixnxnxxx3.2基本概念3.2.1向量与矩阵的范数【例3-3】视mn矩阵为mn维向量,Amn:——称为A的F范数.FminjijAaA||||||||11223.2基本概念3.2.1向量与矩阵的范数2.矩阵范数——只考虑Rn中的方阵【定义3-2】若Ann.对应一个实数||A||，满足：①||A||0,且||A||=0A=0②||kA||=|k|||A||③||A+B||||A||+||B||④||AB||||A||||B||则称||A||为方阵的范数——矩阵范数.例如为矩阵范数.minjijFaA1123.2基本概念3.2.1向量与矩阵的范数2.矩阵范数——只考虑Rn中的方阵注：矩阵理化及运算常要考虑矩阵与向量的乘积，希望范数||Ax||||A||||x||.【定义3-3】设||||为向量范数，||||M为矩阵范数.若ARnn，xRn||Ax||||A||M||x||.则称||A||M为与向量范数||||相容的矩阵范数.注：||A||F与||||1不相容，如.20,4141xA3.2基本概念3.2.1向量与矩阵的范数2.矩阵范数——只考虑Rn中的方阵【定义3-4】设ARnn，||||为向量范数.称为矩阵A的算子范数.(诱导范数).注：①②可以证明算子范数满足矩阵范数的4个条件.故为矩阵范数.③矩阵范数不一定都是算子范数，如F-范数.||||||||max0xAxAxRxn.||||max||||1||||AxAx3.2基本概念3.2.1向量与矩阵的范数2.矩阵范数——只考虑Rn中的方阵④算子范数与向量范数相容.(∵),||||||||max||||xAxA.||||||||||||||||||||||||xAxxAxAx3.2基本概念3.2.1向量与矩阵的范数2.矩阵范数——只考虑Rn中的方阵常见的算子范数有：①②③——2范数.其中max(ATA)为矩阵ATA的绝对值最大特征值..||max||||max||||111||||njijnixaAxA行范数(每行相加,取最大)列范数(每列相加,取最大).max||||max||||1111||||1niijnjxaAxA.)(||||max||||max21||||2AAAxATx3.2基本概念3.2.1向量与矩阵的范数【例3-7】设则||A||1=max{2,5,2}=5(列范数)||A||=max{3,4,2}=43–132+38–25=0,,110121021A0211190102211190102AAIAATT3.2基本概念3.2.1向量与矩阵的范数【例3-7】设则||A||1=max{2,5,2}=5(列范数)||A||=max{3,4,2}=41=9.1428，2=2.9211，3=0.9331.即注：||A||2不易计算但有用.,110121021A.0237.31428.9||||2A3.2基本概念3.2.1向量与矩阵的范数【定义3-5】设i(i=1,2,…,n)为ARnn的n个特征值,称(1.2)为A的谱半径.注：(A)||A||p(1.3)(∵Ax=x(x0),则||||x||p=||x||=||Ax||p||A||p||x||||||||A||p(A)=max||||A||p——用来估计特征值的上界).iniA1max)(不超过任何一种矩阵算子范数3.2基本概念3.2.1向量与矩阵的范数【定理3-1】若||A||1，则I+A可逆.且证明：①∵||A||1，∴(A)11不是A的特征值.故I+A可逆..11)(1AAI3.2基本概念3.2.1向量与矩阵的范数【定理3-1】若||A||1，则I+A可逆.且证明：②令D=(I+A)-1，则1=||I||=||(I+A)D||=||D+AD||||D||–||AD||||D||–||A||||D||=||D||(1–||A||)∵1–||A||0即□.11)(1AAI.11AD.11)(1AAI3.2基本概念3.2.2误差分析介绍1.问题设有方程组解得若有小误差解得注：初始数据A，b的微小变化引起解的巨大变化.——病态方程组.,220001.111121xx,0221xx,9999.129999.011121xx.1121xx3.2基本概念3.2.2误差分析介绍2.分析设Ax=b+b有解A可逆,b0则A(x+x)=b+bAx+Ax=b+bAx=bx=A-1b||x||||A-1||||b||另一方面:||b||=||Ax||||A||||x||(1.8).~xxxAx=b.||||||||||||1bAx.||||||||||||||||||||||||1bbAAxx3.2基本概念3.2.2误差分析介绍2.分析设Ax=b+b有解A可逆,b0则(1.8)同理，若(A+A)(x+x)=b可得(1.11).~xxx.||||||||||||||||||||||||1bbAAxx.||||||||||||||||1||||||||||||||||||||||||11AAAAAAAAxxx3.2基本概念3.2.2误差分析介绍2.分析(1.8)(1.11)注:解的相对误差不超过初始数据相对误差的||A||||A–1||倍,即||A||||A–1||刻画了方程组的形态..||||||||||||||||||||||||1bbAAxx.||||||||||||||||1||||||||||||||||||||||||11AAAAAAAAxxx3.2基本概念3.2.2误差分析介绍3.条件数【定义3-3】设A非奇异，||||为算子范数，则称Cond(A)=||A||||A–1||(1.12)为矩阵A的条件数.注：①Cond(A)=||A|||A–1||||AA–1||=||I||=10②条件数的值与范数的类型有关Cond(A)=||A||||A–1||(行模)3.2基本概念3.2.2误差分析介绍3.条件数【定义3-3】设A非奇异，||||为算子范数，则称Cond(A)=||A||||A–1||(1.12)为矩阵A的条件数.注：②条件数的值与范数的类型有关Cond(A)=||A||||A–1||(行模)(谱模)其中max、min分别是ATA的最大，最小模特征值..)cond(minmax2122AAA3.2基本概念3.2.2误差分析介绍3.条件数【定义3-3】设A非奇异，||||为算子范数，则称Cond(A)=||A||||A–1||(1.12)为矩阵A的条件数.【定义3-7】设A非奇异.若Cond(A)1，则称Ax=b为病态方程组.若Cond(A)相对较小，则称Ax=b为良态方程组.3.2基本概念3.2.2误差分析介绍3.条件数【定义3-7】设A非奇异.若Cond(A)1，则称Ax=b为病态方程组.若Cond(A)相对较小，则称Ax=b为良态方程组.注：本节开始时的方程组中，系数矩阵Cond(A)=||A||||A-1||=2.00012000140004所以Ax=b为病态.10000100001000010001,0001.11111AA3.2基本概念3.2.2误差分析介绍4.病态方程组——理论上有条件数，但标准很难定，且||A–1||很难求..(1)判断方法——直观判断①用主元消去法求解时出现小主元；②某些行、列几乎线性相关③A的元素间数量级很大，且无规律若方程组出现上述情况之一，方程组有可能“病态”。0001.1111A如3.2基本概念3.2.2误差分析介绍4.病态方程组(2)处理措施对于“病态”方程组的求解，需要采用特殊处理或专用方法：①提高原始数据和运算的精度，如原始数据和运算采用双精度等。②用适当方法改善原始模型的性态，如对矩阵进行“预处理”以降低其条件数。3.2基本概念3.2.2误差分析介绍4.病态方程组【例3-8】设线性方程组试计算Cond(A)，并取3位有效数字求解。解：(1)直接计算Cond(A)，并求解。210111017217xx11101110111101110177771A7727110110)110(||||||||)(AAACond3.2基本概念3.2.2误差分析介绍4.病态方程组的判断【例3-8】设线性方程组试计算Cond(A)，并取3位有效数字求解。解：(1)直接计算Cond(A)，并求解。Cond(A)107，使用列主元素消去法求解：回代：x2=1，代入x1+107x2=107，解得x1=0210111017217xx7777771010010101211101013.2基本概念3.2.2误差分析介绍4.病态方程组的判断【例3-8】设线性方程组试计算Cond(A)，并取3位有效数字求解。解：(2)对A做预处理。在方程组两边左乘矩阵即210111017217xx