NA006a线性方程组求解

•引言/*Introdction*/线性代数方程组出现在工程与科学的许多领域中，而且很多数值求解问题最后也是导致于求解某些线性代数方程组，例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程边值问题等。众多的事实表明，解线性代数方程组的有效方法在计算数学和科学计算中具有特殊的重要性。第六章线性方程组的解法/*MethodforSolvingLinearSystems*/线性方程组的两种数值解法经过有限步算术运算，可求得方程组精确解的方法（若计算过程中没有舍入误差）。用某种极限过程去逐步逼近线性方程组精确解的方法。•迭代法/*IterativeMethods*/直接法是解低阶稠密方程组的有效方法。•特点•特点•直接解法/*DirectMethods*/迭代法是解大型稀疏方程组（尤其是由微分方程离散后得到的大型方程组）的重要方法。Introdction2.RXX,3.YXYX则称是向量Х的范数。)(XN我们用表示n维实向量的空间。nR§1向量与矩阵范数\*NormsofVectorsandMatrices*\如果向量的某个实值函数满足条件nRX||||)(XXN定义§1NormsofVectorsandMatrices（正定性/*positivedefinite*/)(齐次性/*homogeneous*/)（三角不等式/*triangleinequality*/)向量范数/*Vectornorms*/0(0XX当且仅当1.)0X1-范数（最大范数）inixX1max§1NormsofVectorsandMatricesniixX112-1—范数4-p—范数pnipipxX/11)(2/1122niixX3-2—范数（长度）例计算向量的各种范数TX321解：63211X3)3,2,1max(X143)2(12222X几种常用的向量范数向量序列收敛于向量是指对每一个1in都有。}{)(kX*X*)(limikikxx定义可以理解为0||||*)(XXk定义若存在常数C0使得对任意有,则称范数||·||A比范数||·||B强。nRXBAXCX||||||||若范数||·||A比||·||B强，同时||·||B也比||·||A强，即存在常数C1、C20使得，则称||·||A和||·||B等价。BABXCXXC||||||||||||21定义定理Rn上一切范数都等价。可以理解为对任何向量范数都成立。§1NormsofVectorsandMatrices)(0lim*)(*)(kXXXXkkk定理证显然，，)(0lim*)(*)(kXXXXkkk于是又有*)(2*)(*)(1XXCXXXXCkkk)0(00*)(*)(kXXXXkk上任一种范数，由范数的等价性，存在常数使02,1CC而对于Rn§1NormsofVectorsandMatrices§1NormsofVectorsandMatrices矩阵范数/*matrixnorms*/定义Rmn空间的矩阵范数||·||对任意满足：nmRBA,00||||;0||||)1(AAA（正定性/*positivedefinite*/)||||||||||)2(AAC对任意(齐次性/*homogeneous*/)||||||||||||)3(BABA（三角不等式/*triangleinequality*/)(4)*||AB||||A||·||B||（相容/*consistent*/当m=n时)Ingeneral,ifwehave||AB||||A||·||B||,thenthe3normsaresaidtobeconsistent.Ohhaven’tIhadenoughofnewconcepts?WhatdoIneedtheconsistencyfor?WhenyouhavetoanalyzetheerrorboundofAB–imagineyoudoingitwithoutaconsistentmatrixnorm…§1NormsofVectorsandMatrices常用矩阵范数：Frobenius范数ninjijFaA112||||||—向量||·||2的直接推广对方阵以及有nnRAnRx22||||||||||||xAxAF利用Cauchy不等式可证。22||||||||||yxyx算子范数/*operatornorm*/由向量范数||·||p导出关于矩阵ARnn的p范数:pxpppxAxxAApx||||max||||||||max||||10||||pppxAxA||||||||||||特别有：njijaAni1||max||||1（行和范数）niijaAnj11||max||||1（列和范数）)(||||max2AAAT（谱范数/*spectralnorm*/）矩阵ATA的最大特征根/*eigenvalue*/pppxxAA||||||||||||称矩阵范数与向量范数的相容性/*consistent*/§1NormsofVectorsandMatrices注：Frobenius范数不是算子范数。我们只关心有相容性的范数，算子范数总是相容的。即使A中元素全为实数，其特征根和相应特征向量/*eigenvector*/仍可能是复数。将前述定义中绝对值换成复数模均成立。若不然，则必存在某个向量范数||·||v使得对任意A成立。vvFxxAAx||||||||max||||0Counterexample?1||||||||max||||0vvFxxIInx谱半径/*spectralradius*/定义矩阵A的谱半径记为(A)=，其中i为A的特征根。||max1iniReIm(A)§1NormsofVectorsandMatrices定理对任意算子范数||·||有||||)(AA证明：由算子范数的相容性，得到||||||||||||xAxA将任意一个特征根所对应的特征向量代入u||||||||||||uAuA||||||||||uu定理若A对称，则有)(||||2AA证明：)()(||||2maxmax2AAAATA对称若是A的一个特征根，则2必是A2的特征根。又：对称矩阵的特征根为实数，即2(A)为非负实数，故得证。)()(22maxAA对某个A的特征根成立所以2-范数亦称为谱范数。向量使得证明：①若不然，则有非零解，即存在非零0)(xBI0x§1NormsofVectorsandMatrices定理若矩阵B对某个算子范数满足||B||1，则必有①BI可逆；②||||111BBI00xxB1||||||||00xxB1||||BIBIBI1))((②11)()(BIBBI11)()(BIBIBI||)(||||||1||)(||11BIBBIHW:p.202#1,#2,#300xBxB求解bxA§2高斯消元法/*GaussianElimination*/高斯消元法：思路首先将A化为上三角阵/*upper-triangularmatrix*/，再回代求解/*backwardsubstitution*/。=§2GaussianElimination–TheMethodi解第一步，将方程（1）乘上-2加到方程（3）上去，消去（3）中的未知数，得到1x11432xx（4）62546332321xxxxxx中的未知数，得到与原方程组等价的三角形方程组第二步，将方程（2）加到方程（4）上去，消去方程（4）2x§2GaussianElimination–TheMethod例:用消去法解方程组（1）（2）（3）12254632132321xxxxxxxxTx)3,2,1(显然此方程组是容易求解的。ir1114051406111620051406111上述过程相当于112251406111)|(bA332rrr其中为矩阵的第i行。ir§2GaussianElimination–TheMethod331)2(rrr设有线性方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa22112222212111212111或改写为矩阵形式，其中bAX为非奇异阵，nnnnnnaaaaaaaaaA212222111211,nxxxX21nbbbb21一般解阶方程组的Guass消去法n§2GaussianElimination–TheMethod§2GaussianElimination–TheMethod消元记,)()1()1(nnijaAA)1()1(1)1(...nbbbbStep1：设，计算因子0)1(11a)...,,2(/)1(11)1(11niaalii将增广矩阵/*augmentedmatrix*/第i行li1第1行，得到)1(1)1(1)1(12)1(11...baaan)2(A)2(b)...,,2,()1(11)1()2()1(11)1()2(njiblbbalaaiiijiijij其中Stepk：设，计算因子且计算0)(kkka)...,,1(/)()(nkiaalkkkkikik)...,,1,()()()1()()()1(nkjiblbbalaakkikkikikkjikkijkij例：用Gauss消去法解方程组52262342321321321xxxxxxxxx§2GaussianElimination–TheMethod回代)()(/nnnnnnabx)1...,,1()(1)()(niaxabxiiinijjiijiii共进行？步n1)()2(2)1(121)()2(2)2(22)1(1)1(12)1(11..................nnnnnnnnbbbxxxaaaaaa对执行行初等变换)1()1(|bA,23212rrr31321rrr得到32/32/3002/12/104112|)1()1(bA§2GaussianElimination–TheMethod解：对增广矩阵522162134112|)1()1(bA用表示第个方程，及增广矩阵的第行，用表示第个方程（行）乘数加至第个方程（行）.iriiijirarrjai330212142332321xxxxxx111321xxx消去过程完结，然后实现回代过程，得出方程组的解。§2GaussianElimination–TheMethod330002/12/104112|)3()3(bA再进行行初等变换，得3233rrr这样就