北京交通大学(数字分析研究生课程)3线性方程组解法

35第3章线性方程组的解法本章讨论线性方程组11112211211222221122nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb的求解问题.线性方程组的矩阵表示Axb式中A称为系数矩阵，b称为右端项。36数值分析中，线性方程组的数值解法主要分为直接法和迭代法两大类。直接法是用有限次计算就能求出线性方程组“准确解”的方法（不考虑舍入误差）；迭代法是由线性方程组构造出迭代计算公式，然后以一个猜测的向量作为迭代计算的初始向量逐步迭代计算，来获得满足精度要求的近似解。迭代法是一种逐次逼近的方法。371线性方程组的迭代解法线性方程组迭代解法有Jocobi迭代法、Gauss-Seidel迭代法及Sor法等基本思想（与简单迭代法类比）将线性方程组Axb等价变形为38xBxg以构造向量迭代格式1kkxBxg用算出的向量迭代序列12,,xx去逼近解。391.构造原理（1）Jacobi迭代法将线性方程组的第i个变元ix用其他n-1个变元表出，可得11122133111222112332221122111()1()1()nnnnnnnnnnnnnxbaxaxaxaxbaxaxaxaxbaxaxaxa……40Jacobi迭代格式:41(1)()()()11122133111(1)()()()22211233222(1)()()()1122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxbaxaxaxaxbaxaxaxaxbaxaxaxa…-…-………-（3.6）（3）取定初始向量000012,,,Tnxxxx，代入，可逐次算出向量序列12,,,kxxx，这里12,,,Tkkkknxxxx。42（2）Gauss-Seidel迭代法Seidel迭代格式:(1)()()()11122133111(1)(1)()()22211233222(1)(1)(1)(1)1122111()1()1()kkkknnkkkknnkkkknnnnnnnnnxbaxaxaxaxbaxaxaxaxbaxaxaxa…-…-………-例1对线性方程组43123123123+22=1+=22+2=3xxxxxxxxx写出Jacobi迭代格式和Gauss-Seidel迭代格式.3）SOR法SOR法的迭代格式1111,1,2,,inkkkkiiiijjijjjjiiixxbaxaxina44式中参数称为松弛因子，当=1时，SOR法就是Seidel迭代法.2.迭代分析及向量收敛1）三种迭代法的向量迭格式对Ax=b，将系数矩阵A作如下分解ADLU45112212121212,00000000,0000nnnnnnaaDaaaaaLUaa则Ax=b可以写成DLUxbJacobi迭代的向量迭代格式1kkJJxBxg1()JBDLU，1JgDb.JB为Jacobi迭代法的迭代矩阵.Seidel向量迭代格式1kkSSxBxg1SBDLU，1SgDLb.sB为Seidel迭代法的迭代矩阵.46SOR法的向量迭代格式1kkxBxg11BDLDU，1gDLb.B为超松弛迭代法的迭代矩阵。三种迭代格式可写成迭代格式1kkxBxg472）向量收敛定义定义1设向量序列12,,,Tkkkknxxxx及向量****12,,,Tnxxxx都是nR中的向量，如果有*lim,1,2,,kiikxxin成立,则称()kx收敛于*x.简记为*limkkxx。483）范数定义与科学计算中的常用范数定义2设L是数域K上的一个线性空间，如果定义在L上的实值函数()Px满足491)xL，有()0Px,且()00Pxx；2),xLK，有()PxPx；3),xyL，有()PxyPxPy,则称()P是L上的一个范数，称()Px为x的一个范数。50范数的定义很象绝对值函数，故常用P或表示范数，而范数()Px常记为Px或x。这样，上面范数定义中的3个条件常写为1）xL，有0x,且00xx；2）,xLK，有xx；3）,xyL，有xyxy将其与绝对值比较，是否很象？实际上，很多有关绝对值的运算和结论可以平行引进到有关范数的运算和证明问题中。51数值分析中常用的线性空间有n维向量空间12|,,,,nnkRaaaaaaR矩阵空间|,mnmnmnijijmnRAAaaR52连续函数空间,|[,]Cabfxfxab在上连续函数空间,Cab是由闭区间,ab上所有连续函数组成的集合，其线性运算定义为加法:fgfgxfxgx数乘:ffxfx，为数53在这些空间上，数值分析中常用的范数有(1)nR的向量范数1)11nkkxx2)221nkkxx3)1maxkknxx式中向量12,,,Tnxxxx.例2计算向量1,2,3Tx的各种范数.54(2)nnR的矩阵范数矩阵范数要满足如下四条1）nnAR，有0A,且00AA；2）,nnARK，有AA；3）,nnABR，有ABAB；554）,nnABR，有ABAB.56由于线性方程组求解问题中，系数矩阵总是与向量联系在一起的，为描述这种联系，引入如下的算子范数概念.定义3设矩阵nnAR，称0maxnPPxRpxAxAx为矩阵A的算子范数。容易证明，矩阵A的算子范数也是矩阵范数，且满足不等式关系PPPAxAx.57例3设为矩阵的算子范数，证明若1B，则IB为非奇异矩阵，且111IBB证：用反证法。若IB为奇异矩阵，则其对应的方程组0IBx58有非零解x，即有0x，使0IBx，得出Bxx两边取范数并作范数运算BxBxxx5901xB，矛盾，得IB非奇异。1111111IBIBIIBIBIBIBIBIBBIB111IBB60常用的矩阵范数有如下4种1）列范数：111maxnijjniAa2）行范数：11maxnijinjAa3）F范数：2,1nijFijAa4）2范数：max2A，max是TAA最大特征值。61以上4个矩阵范数中，12,,AAA是算子范数，FA不是算子范数。例4计算矩阵1234A的各种范数.623）范数等价与向量极限定义4设,pq是线性空间L上的两个范数，若存在正常数m和M，成立,pqpmxxMxxL则称范数,pq是等价范数。定理1nR上的所有范数都是等价的。定理2**limlim0kkkkxxxx。式中是nR上任何一种范数。634）谱半径及其与范数的关系64定义5设nnAR，,1,2,,kkn是A的n个特征值，则称实数1maxkknA为矩阵A的谱半径。注意k如果是复数，k表示复数模。65定理3设A为任意算子范数，则有AA引理4设nnAR，则lim01kkAA663.迭代法的收敛条件与误差估计1）收敛条件定理5：线性迭代格式1kkxBxg对任意初始向量0x都收敛的充要条件是迭代矩阵谱半径()1B.证明必要性67设*limkkxx，在1kkxBxg中令k，得**xBxg,于是有12**2*0*kkkkxxBxxBxxBxx由*limkkxx及0x的任意性，有lim0kkB.再由引理，可得()1B.68充分性因为()1B，则有I-B非奇异（这里I为单位矩阵），从而线性方程组IBxg有唯一解*x，即有*IBxg展开有**xBxg.类似必要性处理，有0**kkxxBxx由引理，由()1B有lim0kkB，上式取极限，得*limkkxx.69判别条件Ⅰ若1B，则迭代格式1kkxBxg对任意初始向量0x都收敛于线性方程组xBxg的唯一解.B是矩阵B的某种算子范数.定义6设nnAR，1）如果A的主对角元素满足701,1,2,,nkkkjjjkaakn则称矩阵A是严格行对角占优阵；2）如果A的主对角元素满足1,1,2,,nkkikiikaakn则称矩阵A是严格列对角占优.严格行对角占优阵和严格列对角占优阵统称为严格对角占优阵.定理严格对角占优阵是非奇异矩阵。证明不妨设矩阵ijnnAa是严格行对角占优阵.用反证法证明.71若A是奇异的，则由矩阵理论可知，齐次线性方程组0Ax有非零解*x，即存在****12,,,0Tnxxxx，满足*0Ax.记**mxx，有***0,,1,2,,mmkxxxkn将*0Ax的第m个等式*10nmkkkax写为**1nmmmmkkkkmaxax等式两边取绝对值有*****111nnnmmmmmmmkkmkkmkkkkkkmkmkmaxaxaxaxax因为*0mx，上式同除*mx，有**11/nnmmmkkmmkkkkmkmaaxxa此与A是严格行对角占优阵矛盾.故若A是非奇异的.72判别条件Ⅱ设矩阵A是严格对角占优阵，则线性方程组Axb的Jacobi迭代和Seidel迭代对任意初始向量0x都收敛.证明只对A是行对角占优情况证之.设矩阵A是严格行对角占优阵，则有1,1,2,,nkkkjjjkaakn，111,1,2,,nkjjkkjkaknaJacobi迭代矩阵1JBIDA，故有11111max=max1nnkjJkjknknjjkkkkjkjkaBaaa由判别条件Ⅰ，可得Jacobi迭代的收敛性.73对Seidel迭代，其迭代矩阵1SBDLU，设k是矩阵SB的任一特征值，则有特征方程1detdetdet0kSkIBDLDLU因1det0DL，故矩阵sB的特征方程变为det0kDLU这个行列式方程对应的矩阵111212122212knkknSkknknknnaaaaaaBDLUaaa如果1k，利用矩阵A的行对角占优定义，可以得出如下不等式741111,1,2,,nkkkkkkkkjjjkknkkjkjjjkaaaaakn这说明矩阵SB也是行严格对角占优阵，由定理，有det0SB,矛盾，故应有1k成立.由k的任意性有谱半径1SB，于是可得Seidel迭代的收敛性.定理7SOR法收敛的必要条件是松弛因子满足02.证明因为SOR法的迭代矩阵为11BDLDU