线性方程组的直接方法迭代法省公共课一等奖全国赛课获奖课件.pptx

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