线性方程组的直接方法迭代法公开课一等奖优质课大赛微课获奖课件.pptx

第1页第1页第2页第2页第3页第3页第4页第4页第5页第5页第6页第6页第7页第7页第8页第8页第9页第9页第10页第10页第11页第11页第12页第12页第13页第13页第14页第14页第15页第15页第16页第16页第17页第17页第18页第18页第19页第19页第20页第20页第21页第21页用Gauss消去法解AX=b时，设A非奇异，但也许出现 这时必须进行行互换Gauss消去法，但在实际计算中即使 但其绝对值很小时，用 作除数，会造成中间结果矩阵 元素数量级严重增长和舍入误差扩散，使最后结果不可靠。例：设有方程组 办法一：用Gauss消去法求解。（用含有舍入3位浮点数进行运算）解：方程组解第22页第22页办法二：用含有行互换Gauss消去法（避免小主元避免小主元）这个解对于含有舍入3位浮点数进行计算，是一个较好结果。回代得解 =1.00 =0.00 ，与准确解比较，这结果很差。这个例子告诉我们，在采用高斯消去法解方程组时，小主元也许造成计算失败，故在消去法中应避免采用绝对值很小主元素在消去法中应避免采用绝对值很小主元素。办法1计算失败原因，是用了一个绝对值很小数作除数，乘数很大，引起约化中间结果数量误差很严重增长，再舍入就使得计算结果不可靠了。第23页第23页 这个例子还告诉我们，对同一个数值问题，用不同计算方法，得到精度大不同，一个计算方法，假如用此方法计算过程中舍入误差得到控制，对计算结果影响较小，称此方法为数值稳定；不然，假如用此计算方法计算过程中舍入误差增加快速，计算结果受舍入误差影响较大，称此方法为数值不稳定。因此，我们解数值问题时，应选择和使用数值稳定计算方法，不然，假如使用数值不稳定计算方法去解数值计算问题，就可能造成计算失败。对普通矩阵方程组，需要引进主元技巧，即在高斯消去法每一步应当选取系数矩阵或消元后低阶矩阵中绝对值最大元素作为主元素，保持乘数 ，以便减少计算过程中舍入误差对计算解影响。第24页第24页第25页第25页第26页第26页（1）选主元素：选取 使于是第k步计算：对于k=1，2，.n-1做到（3）第k步选主元区域第27页第27页（4）回代求解。通过上面过程，即从第1步到第n-1步完毕选主元，交 换两行，交 换两列，消元计算，原方程组约化为：第28页第28页第29页第29页 完全主元素消去法是解低阶稠密矩阵方程组有效办法，但完全主元素办法在选主元时要花费一定期间。现简介一个在实现简介一个在实际计算中惯用部分选主元，（即列主元）消去法。际计算中惯用部分选主元，（即列主元）消去法。列主元消去列主元消去法法，即是每次选主元时，仅依次按列选取绝对值最大元素作为，即是每次选主元时，仅依次按列选取绝对值最大元素作为主元素，且仅互换两行，再进行消元计算。主元素，且仅互换两行，再进行消元计算。第k步选主元区域 设列主元消去法已经完毕第1步到第k-1步按列选主元，互换两行，消元计算得到与原方程组等价方程组：，其中第30页第30页 第k步计算下列：对于k=1，2.，n-1做到（4）（1）按列选主元，即拟定 使（3）假如 ，则互换 第 行第k行元素（2）假如 =0，则A为奇异矩阵，停止计算。（4）消元计算：*第31页第31页解：准确解为（舍入值）：例例：用列主元消去法去解方程组计算解 在常数项内 得到（5）回代计算：第32页第32页 本例是含有舍入4位浮点数进行运算，所得计算解还是比较准确。下面是完全主元素消去法框图（图6-1）第33页第33页图（6-1）stop输入n,A,b,cI(Z)I(I=1,2,.n)k=1,2.n是输出detA=0否互换行是否转下页 第34页第34页消元计算 互换列且接上页否 Stop 第35页第35页第36页第36页*第二步，选4.12为列主元，不需换行，*由*回代求解得：解：第一步，选5.00为主列元，将 对凋位置，第37页第37页 与原方程组准确解 比较，可知，本题用3位有效数字计算列元素法是相称准确。大量实践表明：列主元法为解线性方程组准确办法。完全主元素消去法在选主元素时要花费多机器时间。下面简介另一个惯用办法即列主元素消去法，它仅考虑依次按列选主元素，然后换行使之变到主元素位置上，再进行消元计算。设用列主元素消去法解Ax=b已完毕k-1步计算。即有：第38页第38页第39页第39页列主元素消去法环节：设Ax=b。对于含有行互换列主元素消去法，消元结果冲掉A，乘数mij冲掉aij，计算解X冲掉常数项b,行列式存在det.1,1det,k=1（对k=1n-1 做27步。）3，若aik,k=0,则 0det.计算终止。5，计算乘数mik,mik=aik/akkaik.(i=k+1n)(|mik|1)第40页第40页6,消元计算：aij-mik aij aij (i,j=k+1,n)bi-mik bk bi (i=k+1,n)下面用矩阵运算来描述列主元素法。下面用矩阵运算来描述列主元素法。记 是初等排列阵（由互换单位矩阵I第k行与ik行所得）。则列主元素法为：第41页第41页其中Lk元素满足|mik|1（k=1,2,n-1）,由得：第42页第42页则由排列阵性质（左乘矩阵是对矩阵进行行变换。）这表明：对Ax=b 应用列主元素法相称于对（A|b）先进行一系列行互换后对PAX=Pb再应用Gauss消去法。在实际计算中我们只能在计算过程中做行变换。有结论：定理定理：（列主元素三角分解定理）若A为非奇异性矩阵，则存在排列矩阵P使 PA=LU。其中L为单位下三角阵，U为上三角阵。L存储在A下三角部分，U存储在A上三角部分。由整数型数组IP（n）统计可知P情况。（例子见前）第43页第43页 Gauss消去法总是消去对角线下方元素。现考虑一个修正，即消去对角线下方和上方元素。这即为Gauss-Jordan（G-J）消去法。第44页第44页 在第k步计算时，考虑对上述矩阵第k行上、下都进行消元计算（k=1,2n）2，换行（当ikk）。互换A,b第k行与第ik行元素。3，计算乘数 mik=-aik/akk (i=1n,i k),mkk=1/akk (mik可存储在aik单元中)（|mik|1）第45页第45页上述过程所有执行完后有：这表明用GJ办法将A约化为单位矩阵，计算解就在常数项位置得到，因此用不着回代求解。用GJ办法接方程组计算量大约需要 次乘除法，要比Gauss消去法大些。但用GJ办法求一个矩阵逆矩阵还是比较适当。第46页第46页第47页第47页第48页第48页第49页第49页第50页第50页第51页第51页第52页第52页第53页第53页第54页第54页第55页第55页第56页第56页第57页第57页第58页第58页第59页第59页第60页第60页第61页第61页第62页第62页第63页第63页第64页第64页第65页第65页第66页第66页在一些实际问题中常有解三对角线性方程组Ax=f问题，即：第67页第67页 对于含有条件（2）方程组（1），我们简介下面追赶法求解。追赶法含有计算量少，办法简朴，算法稳定特点。定理定理：设有三对角线性方程组Ax=f，且A满足条件（2），则A为非奇异矩阵。证实：用归纳法证实。显然n=2时，有：第68页第68页 现假设定理对n-1阶满足条件（2）三对角矩阵成立，求证对满足条件（2）n阶三对角矩阵定理亦成立。由条件 ，则利用消元法第1步有：第69页第69页证实：由于A是满足条件（2）n阶三对角阵。因此A任一个顺序主子式 亦满足条件（2）n阶三对角矩阵。由上一个定理第70页第70页依据这一结论以及三角分解定理知，这种矩阵A可进行三角分解：A=LU。在这里尤其有：第71页第71页第72页第72页上面已经验证(5)对i=1成立。现设(5)对i-1成立。求证(5)对i成立。由假设，再由(4)及假设条件(2)有:由(4)可知:可见由A假设条件,我们完全求出了 实现了对ALU分解。从而求解Ax=f 等价于求解两个三角方程组:第73页第73页由此可得求解三对角线性方程组追赶法追赶法:1.计算 递推公式:2.求解 Ly=f 公式:3.求解 Ux=y 公式:第74页第74页 我们将计算 及 过程称为追过程追过程。计算方程组解 过程称为赶过赶过程程。追赶法求解 Ax=f 仅需5n-4次乘除运算。工作量较小。在计算机上，只需用3个一维数组分别存储A系数 以及两个一维数组保留计算中间结果 和 或 .例例:用追赶法求解:解：（1）计算 ：第75页第75页（2）计算 ：对于追赶法，由于已证实:（3）计算 ：因此追赶法中不会出现中间结果快速增长和全入误差产生积累现象。第76页第76页需要对 （n维 列向量空间）中向量及 中矩阵引进某种度量，即引进向量或矩阵范数概念。范数是长度概念推广 为了对方程组计算解进行误差分析，为了讨论迭代法收敛性，定义定义1：（向量范数）第77页第77页|x+y|y|x|第78页第78页 易证实：它们均满足向量范数定义1。且前三种向量范数均为第四种向量范数特例第79页第79页第80页第80页 这就是矩阵Frobenius范数,明显它满足上面定义。在大多数与估算相关问题中，矩阵和向量会同时参与讨论，因此希望引进一个矩阵范数。它和向量范数相联系且和向量范数是相容相容，即：第81页第81页在计算上，（1），（2）比较容易，而（3）比较困难，但（3）在理论分析上十分有用。第82页第82页第83页第83页第84页第84页 由于A(或b)元素是测量得到，或者是计算结果，在第一个情况A（或b）常带一些测量误差。在后一个情况A(或b)又有舍入误差。因此我们处理实际矩是 A+A(或b+b)。Ax=b.A为非奇异阵。设x为方程组准确解。下面考察方程组数据方程组数据A(或或b)微小误差对解影响微小误差对解影响。即预计 x-y。其中 y 为（A+A）y=b 解。例：设有方程组下列，其准确解为 第85页第85页 可见 方程组常数项分量只有微小改变（1%），而方程组解却有较大改变。即方程组解对常数项b很灵敏。这样方程组称为病态方程组病态方程组。定义定义:假如矩阵A或常数项b微小改变引起方程组Ax=b解巨大改变。则称此方程组为“病态病态”方程组，矩阵A称为“病态病态”矩矩阵阵。不然称此方程组为“良态良态”方程组，矩阵A称为“良态良态”矩矩阵阵。现考虑常数项有微小误差 即 bb+b=其中b=.得到一个扰动方程组：.矩阵“病态”性质是矩阵本身特性。下面我们希望找出刻划矩阵“病态”性质量。第86页第86页先考察常数项b微小误差对解影响。设A是准确，且为非奇异矩阵，b有误差（或扰动）b。x为Ax=b 准确解。方程组 解与 x 差记为：从而|x|*|b|即 又 Ax=b0 则|b|A|*|x|即：A(x+x)=b+x，即：A(x)=b.（假设Ax=b0)第87页第87页 式阐明：当b有一定相对误差时，引起解Ax=b解改变相对误差上界由给出。解相对误差是常数项相对误差 倍。由得下面结论:定理定理 (b扰动对解影响)设：1）设Ax=b0，x 为准确解，detA 0；2）且设 A(x+x)=b+b 则有:再考察矩阵 A 扰动对 Ax=b 解 x 影响设A有微小扰动A，即AA+A，b是准确。记（A+A)(x+x)=b第88页第88页 A+A=A(I+)为非奇异性矩阵 且:设 ，则由上一节最后定理可知:定理定理：(A扰动对解影响)设Ax=b,A非奇异矩阵,x 为准确解，且（A+A)(x+x)=b.以及|A|,则由A微小扰动引起解相对误差满足预计式。由 x=-(A+A)-1(A)x，则由 得：由Ax=b0 有：（A+A)x=(A)x 第89页第89页 、均阐明：b或A微小扰动对解相对误差与 相关，因而 数大小刻划了方程组解对数据A(或b)灵敏程度。定义定义：设A为非奇异矩阵，称数为矩阵A条件数条件数，（=1，2或）。可见矩阵条件数与范数相关。A条件数越大，方程组病态就越严重。也就越难得到方程组比较准确解。惯用条件数有：2）A谱条件当A为对称矩阵时，其中1、n为 A 绝对值最大和最小特性值。第90页第90页 条件数性质:对任何非奇异阵A，有：Cond(A)v1 由于:设A为非奇异阵 且c0（常数）,则 Cond(cA)v=Cond(A)v若A为正交矩阵，则Cond(A)2=1，若A为非奇异阵，R为正交矩阵，则Cond(RA)2=Cond(AR)2=Cond(A)2第91页第91页例例：已知Hilbert矩阵：计算H3条件数。解：下面计算H3条件数同样可计算 ，普通Hn矩阵当n越大时，病态越严重。则：第92页第92页再考察方程组设H3与b有微小误差（取3位有效数字）有：第93页第93页 若在A三角约化时（尤其是用元素消去法解Ax=b时）出现小元，对大多数矩阵来说，A是病态矩阵。比如用选主元素直接三角分解法求解方程组(*)(用双精度累加计算aibi,结果舍入为3位浮点数)。则：这表明H3与b相对误差不超出0.2%，而引起解相对误差超出50%。要判断一个矩阵是否病态，需计算矩阵条件数：，而计算 是比较费力。那么在实际中如何发觉病态情况呢？下面分几种情况考虑：第94页第94页 若A最大特性值和最小特性值之比(按照绝对值)较大，则 A 是病态。A特性值：|1|2|n|0 即使：|1|A|，1/|n|因而 。系数矩阵行列式值相对很小，或系数矩阵一些行近似线性相关，这时A也许为病态。系数矩阵A元素间数量级相差很大，而且无一定规则，A可能病态。对于病态方程组，用选主元素法求解难找到准确解。能够考虑迭代改进法。对Ax=b，detA0，若方程组不过度病态。设用Gauss消去法(或部分选主元素法)求得计算解 x1 (精度不变)，我们希望取得方程组高精度解。可采取下述迭代改进法来改进解x1精度。第95页第95页若计算 r1 及 d1 均无误差。则 x2 为方程组 Ax=b 准确解。(Ax2=A(x1+d1)=Ax1+Ad1=Ax1+r1=b)但在实际计算中由于有舍入误差，因此x2仍为一个近似解（要求用双精度计算r），对 x2 再重复上述过程（1）（3），就求得 r2,d2,x3。如此可得一个近似解序列xn。当 Ax=b 不是过度病态时，通常xn能够不久收敛列方程组解 。例例：用迭代法解 第96页第96页因此方程组为病态。则（1）用Gauss消元法Ax=b(用含有舍入4位浮点数进行计算）第97页第97页用Gauss消去法或列主之法求计算解 ，且实现分解（求解两个三角形方程组）；第98页第98页 另外也可采用高精度算术运算技术或者预处理办法来处理病态问题，即将 Ax=b 化为一个等价方程组:即选择非奇异阵 P,Q使 Cond(PAQ)Cond(A)，普通选择P，Q为对角阵或三角阵。当A 元素改变较大时，对A行（或列）引进适当百分比因子（使矩阵A所有行或例按 范数大体上有相同长度，使A系数均衡），对A条件数是有影响，这种办法不能确保A条件数一定得到改进。1,A病态。（I）第99页第99页 如用列主元素法解（I）时（三位浮点数）A,b于是得到个很坏结果：设 为Ax=b近似解，于是可计算 剩余向量r=b-A ,当r很小时，是否为Ax=b一个较好近似解呢？下定理推出了回答第100页第100页 在复杂计算中，由浮点运算而引入误差积累而影响结果，因此对任何算法均需进行舍入误差分析，看其是否过度影响所得结果。下面考察采用选主元素Gauss消去法解 Ax=y 计算过程中舍入误差对解影响。设 为用选主元 Gauss 消元法解 Ax=y 计算解 x 为准确解，假如直接计算每一步舍入误差对解影响来取得界 我们采用“向后误差分析办法”，其基本思想是把计算过程中舍入误差对解影响归结为原始数据改变对解影响，即计算 是下述扰动方程组准确解 (A+A)x=b 。其中A为某个“小”矩阵。定理定理（事后误差预计事后误差预计）。设A为非奇异阵，x为准确解第101页第101页 下面这个定理就回答了这个结果。定理：（选主元素Gauss消去法误差分析）。假如：（4）t为计算机字长（指尾数部分），矩阵阶数满足：则有下面结论：（1）用选主元Gauss消去法计算三角阵L、U满足LU=A+E其中（2）用列主元素法（或完全主元素法）解Ax=b.（1）A为n阶非奇异阵。第102页第102页 (2)用选主元Gauss消去法得到计算解 准确满足：（A+A）x=b.其中（3）计算解精度预计（x为Ax=b准确解）上述计算解 精度预计式阐明，相对误差界依赖于矩阵条元素增长因子a，方程组阶数n及计算机字长t。第103页第103页