扰动误差分析

第2章 线性代数方程组数值解法I：直接法考虑方程组 (非奇异， 且 ) (2.6.1)设有误差 有误差，则因此引起解有误差，即有扰动方程组 现在来研究如何通过和对的影响作出估计。定理2.6.1 设 方程组(2.6.1)中分别有扰动，因而解向量有误差;又足够小，使得 ，则有误差估计式 证明 由 两边取范数有得到 得到 又注意到有 从而得到 ，故上述不等式左边乘以，右边圆括号第一项乘以，第二项乘以，并从括号中提出，则得(2.6.3)定理的结果实际包含两种特殊情形：(1) A精确，即 ，有扰动，从而 (2) 有扰动，精确，即，这时 当很小时，上式可近似表示为 2条件数与病态方程组定义 2.6.1 设为非奇异矩阵，称数 即 为矩阵的条件数。矩阵的条件数的一些基本性质：(1) 任何非奇异矩阵，对任一算子范数均有 (2) 根据定义 ,可得 (3) 若 为正交阵，即，则 又非奇异，则(4)设 与为按模最大和最小的特征值，则 特别地，若（即A对称），则 若对称正定，则 证明 略定理 2.6.2 （事后误差估计）设方程组 ,非奇异，是精确解，是近似解，剩余向量 ,则有估计式 证明： 因，得 ，从而，于是，又由 ，于是得估计式右端 类似地，由上述 ，得，或 ，由 得，综合两式得估计式两端 例 2.6.13事后误差估计定理 2.6.2 设 方程组，非奇异，非奇异，是精确解，是近似解，剩余向量 ,则 有估计式 例题讲解2例题2.1 对方程组Ax=b, A非奇异不一定能作顺序Gauss消去过程，或者说，A非奇异不一定有LU分解。证 这类命题只需举一个反例即可。反例要尽可能简单，这里可考虑2阶、元素为1或0。构造反例一般要经过多次“失败-修正”过程。考虑A= ，易见A非奇异。显然，顺序Gauss消去过程的第1步就不能进行。从LU分解来看，设有A=LU分解，则有=于是有b=0和ab=1同时成立，这就自相矛盾了。例题2.2 设方程组 =试手算（或辅以计算器）分别用 （1）顺序Guass消去法 （2）列主元Gauss消去法（3）直接三角分解法求解，要求计算中取4位有效数字，最后结果舍入成3位有效数字。上述方程组用4位浮点数进行计算而舍入为3位有效数字的精确解为： 解 （1）顺序Gauss消去过程计算有 第1步消元 第2步消元 回代过程求解并舍入得 （2）列主元Gauss消去过程计算有 选主元换行 第1步消元 选主元，仍为 第2步消元 回代过程求解并舍入 （3）令A=LU，用Doolittle分解计算得 由Ly=b 解得 有Ux=y 解得 与精确解比较可见，列主元Gauss消去法的解精确度最高；其他两种方法的解精确度较差，但彼此接近（这正好符合两种方法实质是一样的情况）。例题2.3 Gauss消去法的一种自然而又简单的改进是所谓Gauss-Jordan消去法。先考虑顺序Gauss消去法过程的情形。它只是把a这一列中a下面的元素消为0，而Gauss-Jordan消去过程则把a这一列元素的a以外全部消去为0，并且约化a=1。为此，需进行n步消元，第n列也消为只剩下一个元素1，其余均为0（因此，0在这里也是必要的）。这样一来，不用回代过程，方程组的解就在b的位置上。现在依据上述导引，做（1） 试用Gauss-Jordan消去法解方程组 =（2） 试给出Gauss-Jordan算法的核心部分。（3） 由上述两点能得出什么思考？解（1）用增广矩阵的演变来描述求解过程于是有x=（2，2，3）。 （2）Gauss-Jordan消去法算法的核心部分为： 对k=1,2,，n，做 a(j=k，k+1，n，n+1) 对k=1，2，nik,做 a a-aa(j=k+1,n,n+1) 输出解x=a(i=1,2,n)（4） 从上述做法可引发如下思考：Gauss-Jordan消去过程自然也可考虑加上选主元和换行的技巧；就计算量而言，Gauss-Jordan消去过程显然要大（可推导其乘除运算次数为级，而顺序Gauss消去过程乘除运算次数为级）。因此，用Gauss-Jordan消去法解方程组并不经济。但它有什么用途呢？这又引出一个新的思考。例题2.4设LR为非奇异下三角阵，试（） 写出求解方程组Lx=的计算公式；（） 统计上述求解过程的乘除法次数；（） 给出求L的计算公式。解（）这是解下三角方程组的递推公式：（）乘除法运算，第一式有次，第二次=2时有2次，=时有n次，故上述公式的乘除运算次数有=/2 (次)（）因L非奇异，存在，且由矩阵知识知也为下三角阵，记由，即考虑I的对角线元素，显然有于是得。考虑I对角线以下的元素，即对，则有于是得例题2.5设A=（aij）Rn*n 对称，其顺序主子式i0(i=1,2,n),试（1） 证明分解A=LDLT存在唯一，其中L为单位下三角阵，D为对角阵；（2） 写出利用此分解求解方程组Ax=b的步骤（这称为改进的平方根法）；（3） 用改进的平方跟法解方程组解 （1）由A的顺序主子式不为零，故存在唯一分解式A=LU，L为单位下三角阵，U为上三角阵。改写A=LU=LDU0 ，D为对角阵，U0为单位上三角阵。由A对称，有A=AT=（LDU0）T=（DLT），又由分解的唯一性即得=L或U0=LT，于是代入可得A=LU=LDU0=LDLT存在唯一。（2）将A=LDLT代入Ax=b得LDLTx=b，令DLTx=y（即LTx=D-1y），则Ly=b，改进平方根法如下：1） 将A直接分解为A=LDLT，即求出L，D；2） 求解下三角方程组Ly=b，得y；3） 求解上三角方程组LTx=D-1y，得x。（3）令A=LDLT由矩阵乘法并对比等式两边得 d3=2/3解Ly=b即 得y=解LTx=D-1y即得x=（1，-1，2）T可见改进平方根法比原始平方根法避免了开方运算；另一方面，改进平方根法对满足LU分解条件的对称矩阵（不一定要正定）都适用。例题2.6 已知方程组Ax=b的系数矩阵形如：A=其中A的n-1阶、主子距阵，*为其实数，。试设计一个求解上述方程组基于追赶的解决方案解 把A记为A=其中Bn-1为A的n-1阶（对三角型）主子距阵，V，UR. 对用追赶法可作三角分解=P-Q再对A作三角分解，A=其中ZR(N-1)由下三角方程组Pz=v求出，WR(N-1)由方程组Q=uT(即下三角方程组QtW=U)求出， 由+=算出。由此，求解上述方程组的解决方案如下：（1）对用追赶法求出P，Q；（2）解下三角方程组Pz=v,求出z；（3）解下三角方程组QtW=U求出W；（4）计算=-z;（5）前推解下三角方程组y=b求出y;（6）回代解上三角方程组x=y求出x；例题2.7 设三对角方程组Ax=b,其中A= x= d=(1) 试建立A的顺序主子式(k=1,2,n)的逆推公式。(2) 试设计求解上述三对角方程组的另一种有别于一般追赶法(基于LU分解)的新算法。解 补充记=1，则显然有 = =一般地，猜想 =(k=3,4,n)用归纳法证明：当k=2时，上式成立。现假设有=则由=可知上述猜想成立。综上所述，可得递推公式：(2)由Ax=d的第一个方程可得 (1)即得由表示的关系式。将它代入第二个方程，又可得由表示的关系式如此继续代入，直到第个方程，于是有如下形式的关系式 (k=2,3, ) (2)其中和待定。现将形式如(2)的关系式代入Ax=d的第k(k=2,3, )个方程，则有 整理可得 (k=2,3, ) (3)与关系式(2)比较得 (k=2,3, ) (4)注意到方程组中的记号，令，。由(4)中取k=1,可得，代入(1)得，可见(2)式对k=1也成立；又由(4)中取k=n,则可得，而由于方程组Ax=d的第n个方程可以写成，其中，从而上述的代入可直至第n个方程，也就是说(2)和(3)式对也成立，于是有。综上所述，可得解三对角方程组的新算法如下：例题2.8 证明下列两个命题(其中均为算子范数)：(1) 设B且，则 IB非奇异； 。(2)设非奇异，奇异，则 证明 (1)这个命题通常被作为矩阵范数和谱半径理论中的一个通用定理，它与本章2.6节提供的定理2.61和定理2.62组成最基本的3个定理。现用反证法证明命题(1)。若IB奇异，则齐次方程组(IB)x=0 有非零解，且，于是有和。即有。这与假设矛盾，可知非奇异。关于(2)，由移项整理由假设及注意到,于是可得(2) 对需要证明的不等式，自然与上述提及