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

第1页共38页第2章解线性方程组的迭代法开场白求解线性方程组是研究中经常遇到的问题，n阶线性方程组的一般形式：nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111矩阵形式：bAx其中nnnnnnaaaaaaaaaA212222111211（系数矩阵），nxxxx21，nbbbb21。本章介绍n个方程n个未知量构成的线性方程组（即n元或n阶线性方程组）的间接求解方法——迭代解法。§1迭代法的一般理论一、向量范数和矩阵范数1、向量范数设x是一个实数，则其绝对值||x是一个非负实数，具有以下三个性质：（1）,0||x等号当且仅当0x时成立；（2）对任意数，有|;|||||xx（3）.||||||yxyx推广到向量上得到向量的范数的概念：定义设,nRx若对应的非负实数||||x满足条件：（1）,0||||x,0||||x当且仅当0x时成立；（2）对任意数，有||;||||||||xx（3）.||,||||||||||nRyyxyx则称||||x为向量x的范数。即Rxx||||，事实上是多元函数。第2页共38页例如，||||xx：x的模。是一种范数。定义了范数的线性空间称为赋范线性空间。若范数是向量的模，则为欧氏空间。常用的向量范数有：设,),,,(21Tnxxxx（1）||||||||||||2111nniixxxxx，1－范数（2）22221122),(||||nniixxxxxxx2-范数（向量的模）（3）|}|,|,||,max{|||max||||211ninixxxxx无穷范数其中),(yx是x和y的内积。设,),,,(,),,,(2121TnTnyyyyxxxx定义x和y的内积niiiTyxyxyx1),(（即对应分量相乘再相加，几何中称为向量的点乘积或数量积）例如，设,))1(,,3,2,1(1Tnnx则（1）.21||||||11nxxnii（2）2212221),(||||nxxxxnii（3）nxxini||max||||1可以用向量范数来表示向量误差。定义设x是方程组的精确解向量，*x是近似解向量，（1）称pxx||*||是*x的关于p范数的绝对误差。（2）称ppxxx||||||*||是*x的关于p范数的相对误差。不同的向量范数有不同的绝对误差和相对误差的定义。第3页共38页2、矩阵范数定义设A是nm矩阵，若对应一个非负实数，满足条件（1）,0||||A,0||||A当且仅当0A时成立；（2）对任意数，有||;||||||||AA（3）对任意的nm矩阵BA,，有.||||||||||||BABA则称||||A为矩阵A的范数。例如，（1）minjijFaA112||||F范数定义对于给定nR上的一种向量范数||||x和nmR上的一种矩阵范数||||A，若对任意的向量x及矩阵A，有||||||||||||xAAx则称矩阵范数和向量范数是相容的。由向容性可从向量范数诱导出矩阵范数：称||||max||||||||max||||1||||0AxxAxAxx为矩阵A的相容性范数说明（1）设||||A为矩阵A的相容性范数，则对任意的nm矩阵BA,，有.||||||||||||max||||||||||||max||||max||||1||||1||||1||||BABxABxAABxABxxx即.||||||||||||BAAB（此不等式也称为矩阵范数的相容性）（2）设I为n阶单位阵，则.1||||max||||max||||1||||1||||xIxIxx（或按照习惯单位阵也记作E，.1||||E）相应于3种向量范数，可诱导出3种矩阵的常用相容性范数：（1）miijnjaA111||max||||——列和范数（2）)(||||max2AAAT——谱范数第4页共38页（3）njijmiaA11||max||||——行和范数其中)(maxAAT表示矩阵AAT（为n阶对称阵）的最大特征值。证明：0)(maxAAT证明设是AAT的任一特征值，是相应的特征向量，则,0且)(AAT等式两边同乘以T得TTTAA)(即).()()(TTAA由,0知,0T而.0)()(AAT所以，.0在了矩阵范数，可以描述矩阵误差：设A~是A的近似阵，（1）称AA~为A~的残差阵。（2）称pAA||~||为A~的关于p范数的绝对误差。（3）称ppAAA||||||~||为A~的关于p范数的相对误差。第5页共38页（以下为讲课教案，上面的教案需要明年再改）3、谱半径定义设A是n阶方阵，特征值为,,,,21n称||max)(1iniA为矩阵A的谱半径。说明（1）由于特征值也有可能是复数，因此，若i是实数，||i表示特征值的绝对值；若i是实数，||i表示特征值的模。从而，谱半径从几何上来讲指离坐标原点O最远的i的模。（图）（2）由于TA与A具有相同的特征值，所以，).()(AAT（3）.)()(kkAA分析设,,,,21n是A的特征值，则,,,,21knkk是kA的特征值，因此，.)(|)|max(||max||max)(111kkinikinikinikAA（3）.)()(||||max2AAAAATT而)(maxAAT是非负数，所以，等于其绝对值。（4）谱半径只是一个矩阵函数，不是矩阵范数。（5）当A为对称阵时，).(||||2AA分析当A为对称阵时，.AAT所以，.)()(||||2maxmax2AAAAT而考虑2A的特征值，只需考虑A的特征值。若)(A是A的特征根中绝对值（实对称矩阵的特征值必为实数）最大的那个特征值，则).()(22maxAA从而，).(|)(|)(||||22AAAA第6页共38页定理设A是n阶方阵，则A的谱半径不超过A的任何相容性范数。即.||||)(AA证明设是A的一个特征值，且||)(A，u是A的对应于的特征向量，则uAu因此，.||||||||||||||uuAu从而，.||||||||||||max||||||||||)(0AxAxuAuAx说明此结果在估计A的特征值的上限时很有用处，因为，一般说来特征值不易计算，而范数是容易计算的。定理设A是n阶方阵，则,0存在某种矩阵范数||||A，使得.)(||||AA定理若,1||||A则（1）AI可逆；（2）.||||11||)(||1AAI分析（1）证明方阵可逆的常用方法：1）利用方阵可逆的充要条件定理A可逆0||A。0Ax仅有零解。nAr)(sPPPA21，其中iP是初等矩阵0不是A的特征值。2）反证法。（2）为了证明.||||11||)(||1AAI先要出现.)(1AI由可逆矩阵的定义知，若矩阵A可逆，则.11IAAAA证明（1）反证法：设AI不可逆，则.0||AI从而方程组0)(xAI有非零解，即存在向量00x，使得.0)(0xAI变形得.000xIxAx第7页共38页两边同时取范数||,||||||00xAx而||,||||||||||00xAAx因此，.1||||A矛盾。因此，AI可逆。（2）由IAIAI1))((知，,)()(11IAIAAII整理得,)()(11AIAIAI从而，||)(||||||||||||)(||||)(||111AIAIAIAIAI||)(||||||11AIA整理得.||||11||)(||1AAI二、迭代格式的构造迭代法的思路：将bAx等价地改写成fMxx的形式，建立迭代格式：.)()1(fMxxkk从初始值)0(x出发，得到序列}.{)(kx若}{)(kx收敛于*x，即*,lim)(xxkk则将*x作为方程组bAx的解x的近似值。需要考虑的问题：（1）如何建立迭代格式？（2）向量序列是否收敛？（3）收敛速度如何？（4）误差如何估计？此后的内容将沿着这一思路建立不同的迭代格式，讨论几类迭代格式的这4个问题。第8页共38页设有方程组bAx，其中A可逆，则方程组有唯一解。找解的迭代格式，只需寻找方程).(xx想要方程两边都有x，可将bAx的系数矩阵A分裂：PNA，其中N可逆。（一定可以有这样的分裂，比如取.,AEPEN）此时，方程组可变形为bxPN)(即bPxNx，（若想将左侧x露出来，要求N可逆。）两边同乘以1N：.11bNPxNx即.fMxx这是bAx的等价形式。其中.,11bNfPNM因此，构造迭代公式：.)()1(fMxxkk（1）称M为上述迭代格式的迭代矩阵。取1NQ，则.,)(1QbfQAIANQQPPNM一般地，若存在可逆矩阵Q，使得QbfQAIM,则称Q为分裂矩阵。因此，想要构造迭代格式（1），只需将矩阵A进行分裂，不同的分裂方法将会构造出不同的M，从而，得到不同的迭代格式。由（1）式产生的序列若收敛，则其极限是否为方程组的解呢？选定解的一个初始近似,)0(x由（1）式产生一个向量序列},{)(kx若序列收敛，设*,lim)(xxkk则*x是否为方程组bAx的解，只需验证bAx*或fMxx**是否成立即可。对（1）式两边同时取极限得.**fMxx所以，*x是方程组bAx的解。此时，称迭代格式（1）与方程组bAx是相容的。第9页共38页三、迭代的收敛性分析误差向量：*)()(xxekk迭代格式收敛).(0||||)(kek由fMxx**及fMxxkk)1()(知，*)(*)()0()0()2(2)1()1()(xxMeMeMMexxMekkkkkk两边同时取范数||||||||||||||||||||||||)0()0()0()(eMeMeMekkkk若,1||||M则),(0||||kMk从而，),(0||||)(kek即迭代格式收敛。反之，若迭代fMxxkk)()1(收敛，即),(0||||)(kek或),(0)(kek则?kM定义设,)(,)()(nnkijknnijaAaA若.lim)(ijkijkaa),1(nji则称当k时，kA的极限为,A记作.limAAkk注.0||||limlimAAAAkkkk特别地，.0||||limlimkkkkAOA分析利用矩阵范数的连续性可得。矩阵范数的连续性证明过程略。第10页共38页定理设fMxx存在唯一解，则从任意)0(x出发，迭代fMxxkk)()1(收敛.0limkkM证明)(0||||0limkMMkkk.0),(0||||xkxMk（“”设)(0||||kMk，则0x，有.0),(0||||||||||||xkxMxMkk“”取,)0,,1,,0()(Tiix则)(0)(kxMMikki即0limkkM，从而)(0||||kMk）.0),(0xkxMk)(0)0()(