线性代数方程组的数值解法ne.ppt

上页上页下页下页第第3章章 线性方程组的数值解法线性方程组的数值解法3.1 引言与预备知识引言与预备知识3.2 高斯消去法高斯消去法3.3矩阵三角分解法矩阵三角分解法3.4向量和矩阵的范数误差分析向量和矩阵的范数误差分析3.5迭代方法迭代方法上页上页下页下页 这一章讨论线性方程组这一章讨论线性方程组3.1 引言与预备知识引言与预备知识的数值解法的数值解法.上页上页下页下页 在自然科学和工程技术中在自然科学和工程技术中,很多问题归结为很多问题归结为解解线性方程组线性方程组.例如电学中的网络问题，船体数学放例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小二乘法求实验样中建立三次样条函数问题，用最小二乘法求实验数据的曲线拟合问题，解非线性方程组问题，用差数据的曲线拟合问题，解非线性方程组问题，用差分法或者有限元方法解常微分方程、偏微分方程边分法或者有限元方法解常微分方程、偏微分方程边值问题等都导致求解线性方程组，而这些值问题等都导致求解线性方程组，而这些方程组的方程组的系数矩阵大致分为两种系数矩阵大致分为两种，一种是低阶稠密矩阵一种是低阶稠密矩阵(例例如，阶数不超过如，阶数不超过150).150).另另一种是大型稀疏矩阵一种是大型稀疏矩阵(即即矩阵阶数高且零元素较多矩阵阶数高且零元素较多).).3.1.1 引言引言上页上页下页下页 有有的的问问题题的的数数学学模模型型中中虽虽不不直直接接表表现现为为含含线线性性方方程程组组,但但它它的的数数值值解解法法中中将将问问题题“离离散散化化”或或“线线性性化化”为为线线性性方方程程组组.因因此此线线性性方方程程组组的的求求解解是是数值分析课程中最基本的内容之一数值分析课程中最基本的内容之一.关于线性方程组的解法一般有两大类：关于线性方程组的解法一般有两大类：上页上页下页下页 但但实实际际计计算算中中由由于于舍舍入入误误差差的的存存在在和和影影响响，这这种种方方法法也也只只能能求求得得线线性性方方程程组组的的近近似似解解.本本章章将将阐阐述述这这类类算算法法中中最最基基本本的的和和具具有有代代表表性性的的算算法法就就是是高高斯斯消消元元法法,以以及及它它的的某某些些变变形形和和应应用用.这这类类方方法法是是解解低低阶阶稠稠密密矩矩阵阵方方程程组组及及某某些些大大型型稀稀疏疏矩矩阵阵方方程程组组(例例如，大型带状方程组如，大型带状方程组)的有效方法的有效方法.1.直接法直接法 经经过过有有限限次次的的算算术术运运算算,可可以以求求得得方方程程组组的的精精确确解解(假假定定计计算算过过程程没没有有舍舍入入误误差差).).如如线线性性代代数数课课程程中中提提到到的的克克莱莱姆姆算算法法就就是是一一种种直直接接法法.但但该该法法对对高高阶阶方方程组计算量太大程组计算量太大,不是一种实用的算法不是一种实用的算法.上页上页下页下页 就就是是用用某某种种极极限限过过程程去去逐逐步步逼逼近近方方程程组组精精确确解解的的方方法法.迭迭代代法法具具有有计计算算机机的的存存储储单单元元较较少少、程程序序设设计计简简单单、原原始始系系数数矩矩阵阵在在计计算算过过程程中中始始终终不不变变等等优优点点，但但存存在在收收敛敛条条件件和和收收敛敛速速度度问问题题.迭迭代代法法是是解解大大型型稀稀疏疏矩矩阵阵方方程程组组(尤尤其其是是由由微微分分方方程程离离散散后后得得到到的的大大型型方程组方程组)的重要方法的重要方法.为为了了讨讨论论线线性性方方程程组组数数值值解解法法，需需复复习习一一些些基基本本的矩阵代数知识的矩阵代数知识.2.迭代法迭代法上页上页下页下页3.1.2 向量和矩阵向量和矩阵 基本概念基本概念：用用Rmn表示全部表示全部mn实矩阵的向量空间；实矩阵的向量空间；用用Cmn表示全部表示全部mn复矩阵的向量空间复矩阵的向量空间.(由数排成的矩阵表，称为由数排成的矩阵表，称为m行行n列矩阵列矩阵).上页上页下页下页其中其中aj为为A的第的第j列的列的m维列向量维列向量.同理同理(m维列向量维列向量).其中其中biT为为A的第的第i行的行的n维行向量维行向量.上页上页下页下页 矩阵的基本运算矩阵的基本运算：(1)矩阵加法矩阵加法 (2)矩阵与标量的乘法矩阵与标量的乘法 (3)矩阵与矩阵的乘法矩阵与矩阵的乘法 (4)转置矩阵转置矩阵上页上页下页下页 (5)单位矩阵单位矩阵其中其中 (6)非奇异矩阵非奇异矩阵则称则称B是是A的逆矩阵，记为的逆矩阵，记为A-1，且，且(A-1)T=(AT)-1.如如果果A-1存在，则存在，则A称为非奇异矩阵称为非奇异矩阵.如果如果A、B均为非均为非奇异矩阵，则有奇异矩阵，则有(AB)-1=B-1A-1.上页上页下页下页 (7)矩阵的行列式矩阵的行列式 设设ARnn，则，则A的行列式可按任一行的行列式可按任一行(列列)展开展开,其中其中Aij为为aij的代数余子式，的代数余子式，Aij=(-1)i+jMij，Mij为元素为元素aij的余子式的余子式.行列式性质行列式性质：上页上页下页下页 定理定理1 设设ARnn，则下述命题等价：，则下述命题等价：(1)对任何对任何bRn，方程组，方程组Ax=b有唯一解有唯一解.(2)齐次方程组齐次方程组Ax=0只有唯一解零解只有唯一解零解x=0.(3)det(A)0.(4)A-1存在存在.上页上页下页下页3.2 高斯消去法高斯消去法 本本节节介介绍绍高高斯斯消消去去法法(逐逐次次消消去去法法)及及消消去去法法和和矩矩阵阵三三角角分分解解之之间间的的关关系系.虽虽然然高高斯斯消消去去法法是是一一种种古古老老的的求求解解线线性性方方程程组组的的方方法法(早早在在公公元元前前250250年年我我国国就就掌掌握握了了解解方方程程组组的的消消去去法法)，但但由由它它改改进进、变变形形得得到到的的选选主主元元素素消消去去法法、三三角角分分解解法法仍仍然然是是目目前前计计算算机机上上常常用用的的有有效效方方法法.我我们们在在中中学学学学过过消消去去法法,高高斯斯消消去去法法就就是是它它的的标标准准化化的的、适适合合在在计计算算机机上上自自动计算的一种方法动计算的一种方法.上页上页下页下页3.2.1 高斯消去法高斯消去法 设有线性方程组设有线性方程组或写成矩阵形式或写成矩阵形式简记为简记为Ax=b.上页上页下页下页如如:上三角矩上三角矩阵阵所对应所对应的线性方的线性方程组程组解为解为 当当m=n时，对时，对三角形方程组三角形方程组的解非常容易，如的解非常容易，如上页上页下页下页例如例如:上页上页下页下页下三角矩阵下三角矩阵所对所对应的线性方程组应的线性方程组计算量（乘除法的主要部分）都为计算量（乘除法的主要部分）都为 n2/2.解为解为 因此，我们将一般的线性方程组化成等价的三因此，我们将一般的线性方程组化成等价的三角形方程组来求解角形方程组来求解.上页上页下页下页 首先举一个简单的例子来说明消去法的基本思想首先举一个简单的例子来说明消去法的基本思想.例例1 用消去法解方程组用消去法解方程组 解解 第第1步，将方程步，将方程(2.2)乘上乘上-2加到方程加到方程(2.4)上上去，消去去，消去(2.4)中的未知数中的未知数x1，得到，得到 第第2步，将方程步，将方程(2.3)加到方程加到方程(2.5)上去，消去上去，消去(2.5)中的未知数中的未知数x2，得到与原方程组等价的三角形方，得到与原方程组等价的三角形方程组程组上页上页下页下页显然，方程组是显然，方程组是(2.6)是容易求解的，解为是容易求解的，解为 上述过程相当于对方程的上述过程相当于对方程的增广阵做初等行变换增广阵做初等行变换其中其中ri用表示矩阵的第用表示矩阵的第i行行.上页上页下页下页 由此看出，用消去法解方程组的由此看出，用消去法解方程组的基本思想基本思想是用是用逐次消去未知数的方法把原方程组逐次消去未知数的方法把原方程组Ax=b化为与其等化为与其等价的三角形方程组，而求解三角形方程组可用回代价的三角形方程组，而求解三角形方程组可用回代的方法求解的方法求解.换句话说，上述过程就是用初等行变换换句话说，上述过程就是用初等行变换将原方程组系数矩阵化为简单形式将原方程组系数矩阵化为简单形式(上三角矩阵上三角矩阵)，从，从而求解原方程组而求解原方程组(2.1)的问题转化为求解简单方程组的问题转化为求解简单方程组的问题的问题.或者说，对系数矩阵或者说，对系数矩阵A施行一些行变换施行一些行变换(用一用一些简单矩阵左乘些简单矩阵左乘A)将其约化为上三角矩阵将其约化为上三角矩阵.这就是这就是高高斯消去法斯消去法.上页上页下页下页 下面讨论求解一般线性方程组的高斯消去法下面讨论求解一般线性方程组的高斯消去法.由由上页上页下页下页 将将(2.1)记为记为A(1)x=b(1)，其中，其中上页上页下页下页 (1)第第1步步(k=1).设设a11(1)0，首先计算，首先计算乘数乘数 mi1=ai1(1)/a11(1)(i=2,3,m).用用-mi1乘乘(2.1)的第一个方程，加到第的第一个方程，加到第i个个(i=2,3,m)方程上，消去方程上，消去(2.1)的从第二个方程到第的从第二个方程到第m个方程中的个方程中的未知数未知数x1，得到与，得到与(2.1)等价的方程组等价的方程组(2.7)上页上页下页下页简记为简记为 A(2)x=b(2)，其中其中A(2),b(2)的元素计算公式为的元素计算公式为 (2)第第k次消元次消元(k=1,2,s,s=min(m-1,n).设上述第设上述第1步，步，第，第k-1步消元过程计算已经完步消元过程计算已经完成，即已计算好与成，即已计算好与(2.1)等价的方程组，简记为等价的方程组，简记为A(k)x=b(k)，其中，其中上页上页下页下页 设设akk(k)0，计算，计算乘数乘数 mik=aik(k)/akk(k)(i=k+1,m).用用-mik乘乘(2.8)的第的第k个方程加到第个方程加到第 i个个(i=k+1,m)方方程上，消去从第程上，消去从第k+1个方程到第个方程到第m个方程中的未知数个方程中的未知数xk，得到与，得到与(2.1)等价的方程组等价的方程组A(k+1)x=b(k+1)，上页上页下页下页其中其中A(k+1),b(k+1)的元素计算公式为，的元素计算公式为，显然显然A(k+1)中从第中从第1行到第行到第k行与行与A(k)相同相同.(3)继续上述过程，且设继续上述过程，且设aii(i)0(i=1,2,s)，直到，直到完成第完成第s步消元计算步消元计算.最后得到与原方程组等价的简最后得到与原方程组等价的简单方程组单方程组A(s+1)x=b(s+1)，其中，其中A(s+1)为上阶梯为上阶梯.上页上页下页下页 特别当特别当m=n时，时，与原方程组等价的简单方程组为与原方程组等价的简单方程组为A(n)x=b(n)，即，即由由(2.1)约化为约化为(2.10)的过程称为的过程称为消元过程消元过程.如果如果A是非奇异矩阵，且是非奇异矩阵，且akk(k)0(k=1,2,n-1)，求解三角形方程组求解三角形方程组(2.10)，得到求解公式，得到求解公式(2.10)的求解过程的求解过程(2.11)称为称为回代过程回代过程.上页上页下页下页 注意：设注意：设Ax=b，其中，其中ARnn为非奇异矩阵，如为非奇异矩阵，如果果a11(1)=0，由于，由于A为非奇异矩阵，所以为非奇异矩阵，所以A的第的第1列一定列一定有元素不等于零，例如有元素不等于零，例如al1 0，于是可交换两行元素，于是可交换两行元素(即即r1rl)，将，将al1 调到调到(1,1)位置，然后进行消元计算，位置，然后进行消元计算，这时这时A(2)右下角矩阵为右下角矩阵为n-1阶非奇异矩阵，继续这过程，阶非奇异矩阵，继续这过程，高斯消去法照样可进行计算高斯消去法照样可进行计算.总结上述讨论即有总结上述讨论即有上页上页下页下页 定理定理5 设设Ax=b，其中，其中ARnn.(1)如果如果akk(k)0(k=1,2,n)，则可通过高斯消去，则可通过高斯消去法将法将Ax=b约化为等价的三角形方程组约化为等价的三角形方程组(2.10)，且计算，且计算公式为公式为 (a)消元计算消元计算(k=1,2,n-1)上页上页下页下页 (b)回代计算回代计算 (2)如果如果A为非奇异矩阵，则可通过高斯消去法为非奇异矩阵，则可通过高斯消去法(及交换两行的初等变换及交换两行的初等变换)将方程组将方程组Ax=b约化为等价的约化为等价的三角形方程组三角形方程组(2.10).上页上页下页下页例例2 2 解方程组解方程组解解：消元：消元回代得回代得上页上页下页下页习题:求解下列方程组，(1)(2)上页上页下页下页3.2.2 高斯主元素消元法高斯主元素消元法 由高斯消去法知道由高斯消去法知道,在消元过程中可能有在消元过程中可能有akk(k)0的情况，这时消去法将无法进行；即使主元素的情况，这时消去法将无法进行；即使主元素akk(k)0但很小时，用其作除数，会导致其它元素数量级的严但很小时，用其作除数，会导致其它元素数量级的严重增长和舍入误差的扩散，最后也使得计算解不可靠重增长和舍入误差的扩散，最后也使得计算解不可靠.先看一个例子先看一个例子 高斯消去法也称高斯消去法也称主元素消去法主元素消去法(条件条件det A 0)即即当当akk(k)=0 时，高斯消元法时，高斯消元法无法进行无法进行；或；或|akk(k)|0(i=1,2,n).由矩阵乘法及由矩阵乘法及ljk=0(当当j1时时,aij=0,且且满足如下的对角占优条件满足如下的对角占优条件满足如下的对角占优条件满足如下的对角占优条件:(a)|b1|c1|0;(b)|bi|ai|+|ci|,ai,ci0,(i=2,3,n-1).(c)|bn|an|0.我们利用矩阵的直接三角分解法来推导解三对我们利用矩阵的直接三角分解法来推导解三对角线方程组角线方程组(4.12)的计算公式的计算公式.由系数阵由系数阵A的特点，的特点，可以将可以将A分解为两个三角矩阵的乘积，即分解为两个三角矩阵的乘积，即A=LU,其中取其中取L下三角阵下三角阵,取取U为单位上三角阵为单位上三角阵,这样求解这样求解方程组方程组Ax=f的方法称为的方法称为追赶法追赶法.设设上页上页下页下页其中其中 为待定系数，比较为待定系数，比较(4.13)两边即得两边即得 上页上页下页下页 求解求解Ax=f等价于求解两个三角形方程组等价于求解两个三角形方程组.(1)Ly=f,求求y;(2)Ux=y,求求x.从而得到解三对角线方程组的追赶法从而得到解三对角线方程组的追赶法.上页上页下页下页 我们将计算系数我们将计算系数 及及 的过程称为的过程称为追的过程追的过程,将计算方程组的解将计算方程组的解 的过程称为的过程称为赶的过程赶的过程.合起来就是合起来就是追赶法追赶法.追赶法公式实际上就是把高斯消去法用到求解追赶法公式实际上就是把高斯消去法用到求解三对角线方程组上去的结果三对角线方程组上去的结果.这时由于这时由于A特别简单特别简单,因此使得求解的计算公式非常简单因此使得求解的计算公式非常简单,追赶法的计算量追赶法的计算量比较小的比较小的.上页上页下页下页3.4方程组的性态、条件数方程组的性态、条件数 在在分分析析方方程程组组的的解解的的误误差差及及下下章章中中迭迭代代法法的的收收敛敛性性时时，常常产产生生一一个个问问题题,即即如如何何判判断断向向量量 x 的的“大大小小”，对对矩矩阵阵也也有有类类似似的的问问题题.本本节节介介绍绍n维维向向量量范范数数和和nn矩矩阵阵的的范范数数.向向量量范范数数是是三三维维欧欧氏氏空空间间中中向量长度概念的推广，在数值分析中起着重要作用向量长度概念的推广，在数值分析中起着重要作用.3.4.1 向量与矩阵的范数向量与矩阵的范数上页上页下页下页 首先将向量长度概念推广到首先将向量长度概念推广到Rn(或或Cn)中中.称为向量称为向量x,y的的数量积数量积(内积内积).将非负实数将非负实数称为向量称为向量x的的欧氏范数欧氏范数.定义定义1 设设x=(x1,x2,xn)T,y=(y1,y2,yn)T Rn,将将实数实数上页上页下页下页 下面定理可在线性代数书中找到下面定理可在线性代数书中找到.定理定理13 设设x,y Rn(或或Cn),则则 1.(x,x)=0,当且仅当当且仅当x=0时成立时成立;上页上页下页下页 我我们们还还可可以以用用其其他他办办法法来来度度量量Rn中中向向量量的的“大大小小”.例例如如,对对于于x=(x1,x2)T Rn,可可以以用用一一个个x的的函函数数N(x)=max|xi|来来度度量量 x 的的“大大小小”,而而且且这这种种度度量量 x 的的“大大小小”的的方方法法计计算算起起来来比比欧欧氏氏范范数数方方便便.在在许许多多应应用用中中,对对度度量量x的的“大大小小”的的函函数数N(x)都都要要求求是是正正定定的的、齐齐次次的的且且满满足足三三角角不不等等式式.下下面面我我们们给出向量范数的一般定义给出向量范数的一般定义.上页上页下页下页 (1)|x|0(|x|=0当且仅当当且仅当x=0)(正定性正定性),(2)|x|=|x|,对任何对任何 R(或或 C)(齐次性齐次性),(3)|x+y|x|+|y|(三角不等式三角不等式).则称则称N(x)=|x|是是Rn(或或Cn)上的一个上的一个向量范数向量范数(或或模模).定义定义2(向量的范数向量的范数)如果向量如果向量x Rn(或或Cn)的某个的某个实值函数实值函数N(x)=|x|，满足条件，满足条件:由由(3)可推出不等式可推出不等式.(4)|x|-|y|x-y|.上页上页下页下页 下面给出几种下面给出几种常用的向量范数常用的向量范数,设设x=(x1,x2,xn)T.容易证明前三种范数是的容易证明前三种范数是的p-范数范数特殊情况特殊情况,其中其中向量的向量的-范数范数(最大范数最大范数)向量的向量的1-范数范数向量的向量的p-范数范数(0p+)向量的向量的欧氏欧氏范数范数上页上页下页下页 例例6 计算向量计算向量 x=(1,-2,3)T的各种范数的各种范数.解解 定义定义3 设设x(k)为为Rn中一向量序列中一向量序列,x*Rn,记记x(k)=(x1(k),xn(k)T,x*=(x1*,xn*)T.如果如果则称则称x(k)收敛于收敛于x*.记为记为上页上页下页下页 定理定理14 ,其中其中|为向为向量的任一种范数量的任一种范数.上页上页下页下页 下下面面我我们们将将向向量量范范数数概概念念推推广广到到矩矩阵阵上上去去.可可以以将将Rnn中中的的矩矩阵阵A=(aij)nn当当作作n2维维向向量量,则则由由向向量量的的2-范数可以得到范数可以得到Rnn中矩阵的一种中矩阵的一种范数范数称称为为A的的Frobenius范范数数.|A|F显显然然满满足足正正定定性性、齐齐次次性及三角不等式性及三角不等式.下面我们给出矩阵范数的一般定义下面我们给出矩阵范数的一般定义.上页上页下页下页 定义定义4(矩阵的范数矩阵的范数)如果矩阵如果矩阵A Rnn的某个实值的某个实值函数函数N(A)=|A|，满足条件，满足条件:(1)|A|0(|A|=0当且仅当当且仅当A=0)(正定性正定性)；(2)|cA|=|c|A|,c为为实数实数 (齐次性齐次性)；(3)对任意对任意A,B有有|A+B|A|+|B|(三角不等式三角不等式)(4)对任意对任意A,B有有|AB|A|B|(相容性相容性)；则称则称 N(A)是是Rnn上的一个上的一个矩阵范数矩阵范数(或或模模).上页上页下页下页 上上面面我我们们定定义义的的F(A)=|A|F就就是是Rnn上上的的一一个个矩矩阵范数阵范数.上述条件上述条件(即不等式即不等式)就称为就称为矩阵范数与向量范数矩阵范数与向量范数的相容性条件的相容性条件.由由于于在在大大多多数数与与估估计计有有关关的的问问题题中中,矩矩阵阵和和向向量量会会同同时时参参与与讨讨论论,所所以以希希望望引引进进一一种种矩矩阵阵的的范范数数,它它是是和和向向量量范范数数相相联联系系而而且且和和向向量量范范数数相相容容的的,即即对对任任何何向量向量x Rn及矩阵及矩阵A Rnn都成立都成立|Ax|A|x|.为此我们再引进一种矩阵的范数为此我们再引进一种矩阵的范数.上页上页下页下页 定义定义5(矩阵的算子范数矩阵的算子范数)设设x Rn,A Rnn,给出给出一种向量范数一种向量范数|x|v(如如v=1,2或或),相应地定义一个矩阵相应地定义一个矩阵的非负函数的非负函数可验证可验证|A|v满足满足定义定义4(见下面定理见下面定理),所以所以|A|v是是Rnn上上矩阵的一个范数矩阵的一个范数,称为称为A的的算子范数算子范数.上页上页下页下页 显然这种矩阵的范数显然这种矩阵的范数|A|v依赖于向量范数依赖于向量范数|x|v的的具体含义具体含义.也就是说也就是说,当给出一种具体的向量范数当给出一种具体的向量范数|x|v时时,相应地就得到了一种矩阵范数相应地就得到了一种矩阵范数|A|v.定理定理18 设设x Rn,A=(aij)Rnn,则有则有常用的算子范数常用的算子范数（称为（称为A的的行范数行范数）,（称为（称为A的的列范数列范数）,（称为（称为A的的2-范数范数）.其其中中 max(ATA)表表示示ATA的的最最大大特特征征值值,由由于于矩矩阵阵2-范范数与数与ATA 的特征值有关，所以又称为的特征值有关，所以又称为A的的谱范数谱范数.上页上页下页下页例例7 设设则则求相应的各种范数求相应的各种范数.解解因为因为令令上页上页下页下页得得ATA的特征值的特征值故故可见可见上页上页下页下页 定义定义6 设设A Rnn的特征值为的特征值为 i(i=1,2,n),称称为为A的的谱半径谱半径.例例子子 设设,求求A的谱半径的谱半径.解解得得A的特征值的特征值故得故得A的谱半径为的谱半径为上页上页下页下页 定理定理19(特征值上界特征值上界)设设A Rnn,则则(A)|A|,即即A的谱半径不超过的谱半径不超过A的任何一种算子范数的任何一种算子范数(对对|A|F亦成立亦成立).定理定理20 如果如果A Rnn为对称矩阵为对称矩阵,则则|A|2=(A).上页上页下页下页求求A1,A2,A,(A).例子例子 设设 ,解解:显然显然A1=4,A=4 上页上页下页下页这里这里,我们指出我们指出,对于实对称矩阵对于实对称矩阵A,有有(A)=|A|2.上页上页下页下页习题习题:=,上页上页下页下页3.4.2 误差分析误差分析5.6.1 矩阵的条件数矩阵的条件数 由于由于A(或或b)元素是测量得到的元素是测量得到的,或者是计算的结或者是计算的结果果,在第一种情况在第一种情况A(或或b)常带有某些观测误差常带有某些观测误差,在后在后一种情况一种情况A(或或b)又包含有舍入误差又包含有舍入误差.因此我们处理因此我们处理的实际矩阵是的实际矩阵是A+A(或或b+b),下面我们来研究数下面我们来研究数据据A(或或b)的微小误差对解的影响的微小误差对解的影响.即考虑估计即考虑估计x-y,其中其中y是是(A+A)y=b的解的解.考虑线性方程组考虑线性方程组Ax=b,其中设其中设A为非奇异矩阵为非奇异矩阵,x为方程组的精确解为方程组的精确解.上页上页下页下页 首先考察一个例子首先考察一个例子.例例8 设有方程组设有方程组记为记为Ax=b,它的精确解为它的精确解为x=(2,0)T.现在考虑常数项的微小变化对方程组解的影响现在考虑常数项的微小变化对方程组解的影响,即考察方程组即考察方程组上页上页下页下页也可表示为也可表示为A(x+x)=b+b,其中其中 b=(0,0.0001)T,y=x+x,x为为(6.1)的解的解.显然方程组显然方程组(6.2)的解为的解为x+x=(1,1)T.我们看到我们看到(6.1)的常数项的常数项b的第的第2个分量只有个分量只有1/1000的微小变化的微小变化,方程组的解却变化很大方程组的解却变化很大.这样的方程组这样的方程组称为称为病态方程组病态方程组.定义定义7 如果矩阵如果矩阵A或常数项或常数项b 的微小变化的微小变化(小扰动小扰动),引起方程组引起方程组Ax=b解的巨大变化解的巨大变化,则称此方程组为则称此方程组为“病病态态”方程组方程组,其系数矩阵其系数矩阵 A 称为称为“病态病态”矩阵矩阵(相对于相对于方程组而言方程组而言),否则称方程组为否则称方程组为“良态良态”方程组方程组,A称为称为“良态良态”矩阵矩阵.上页上页下页下页 应该注意应该注意,矩阵的矩阵的“病态病态”性质是矩阵本身的性质是矩阵本身的特特性性,下面我们希望找出刻画矩阵下面我们希望找出刻画矩阵“病态病态”性质的性质的量量.设设有方程组有方程组 Ax=b,(6.3)其中其中A为非奇异矩阵为非奇异矩阵,x为为(6.3)的精确解的精确解.以下我们研以下我们研究方程组的系数矩阵究方程组的系数矩阵A(或或b)的的微小误差微小误差(小扰动小扰动)时对时对解的影响解的影响.上页上页下页下页 (1)现现设设A是是精精确确的的,x为为Ax=b的的精精确确解解，当当方方程程组右端有组右端有误差误差 b,受扰解受扰解为为 x+x,则则 A(x+x)=b+b,Ax=b,x=A-1 b,|x|A-1|b|.(6.4)由由(6.3)有有|b|A|x|.于是由于是由(6.4)及及(6.5),得得上页上页下页下页 定理定理22 设设A是非奇异矩阵是非奇异矩阵,Ax=b00,且且 A(x+x)=b+b,则则 上上式式给给出出了了解解x的的相相对对误误差差的的上上界界,常常数数项项b的的相相对误差在解中放大对误差在解中放大|A-1|A|倍倍.(2)现现设设b是是精精确确的的,x为为Ax=b的的精精确确解解，当当A有有微微小误差小误差(小扰动小扰动)A,受扰解受扰解为为 x+x,则则(A+A)(x+x)=b,(A+A)x=-(A)x.(6.6)上页上页下页下页 如果如果 A不受限制的话不受限制的话,可能可能A+A奇异奇异,而而(A+A)=A(I+A-1 A).由定理由定理21知知,|A-1 A|1时时,(I+A-1 A)-1存在存在.由由(6.6)式式 x=-(I+A-1 A)-1A-1(A)x.因此因此设设|A-1|A|1,即得即得上页上页下页下页 定理定理23 设设A是非奇异矩阵是非奇异矩阵,Ax=b00,且且(A+A)(x+x)=b.如果如果|A-1|A|1,则则(6.7)式成立式成立.如如果果 A充充分分小小,且且在在条条件件|A-1|A|1时时,则则(6.3)是是“病病态态”的的(即即A是是“病病态态”矩矩阵阵,或或者者说说A是是坏坏条条件件的的,相相对对于于方方程程组组),当当A的的条条件件数数相相对对的的小小,则则(6.3)是是“良良态态”的的(或或者者说说A是是好好条条件件的的).注注意意,方方程程组组病病态态性性质质是是方方程程组组本本身身的的特特性性.A的的条条件件数数越越大大,方方程程组组的的病病态态程程度度越越严严重重,也也就就越越难难用用一一般般的的计计算算方方法法求求得得比较准确的解比较准确的解.上页上页下页下页 例如对前面例例如对前面例8的矩阵作分析的矩阵作分析由于条件数由于条件数cond(A)1很大很大,可见矩阵可见矩阵A的病态程度十分的病态程度十分严重严重,故由此方程组的解误差非常大故由此方程组的解误差非常大.计算其条件数计算其条件数上页上页下页下页 通常使用的条件数通常使用的条件数,有有 (1)cond(A)=|A-1|A|;(2)A的谱条件数的谱条件数;当当A为对称矩阵时为对称矩阵时其中其中1,n为为A的绝对值最大和绝对值最小的特征值的绝对值最大和绝对值最小的特征值.上页上页下页下页习题习题上页上页下页下页 条件数的性质条件数的性质:1.对任何非奇异矩阵对任何非奇异矩阵,都有都有cond(A)v v1.事实上事实上 cond(cA)v=cond(A)v.2.设设A为非奇异矩阵且为非奇异矩阵且c0(常数常数),则则 3.如如果果A为为正正交交矩矩阵阵,则则cond(A)2 2=1;如如果果A为为非非奇异矩阵奇异矩阵,R为正交矩阵为正交矩阵,则则 cond(RA)2=cond(AR)2=cond(A)2.上页上页下页下页 由由性性质质1知知,1cond(A),即即cond(A)总总是是大大于于等等于于1的的数数.条条件件数数反反映映了了方方程程组组的的“病病态态程程度度”.条条件件数数越越小小,方方程程组组的的状状态态越越好好,条条件件数数很很大大时时,称称方方程程组组为为病病态态方方程程组组.但但多多大大的的条条件件数数才才算算病病态态则则要要视视具具体体问问题题而而定定,病态的说法只是病态的说法只是相对而言相对而言.条件数的计算是困难的条件数的计算是困难的,这首先在于要算这首先在于要算A-1,而求而求A-1比解比解Ax=b的工作量还大的工作量还大,当当A确实病态时确实病态时,A-1也求也求不准确；其次要求不准确；其次要求范数范数,特别是求特别是求|A|2,|A-1|2又十分又十分困难困难,因此因此实际工作中一般不先去判断方程组的病态实际工作中一般不先去判断方程组的病态.但是必须明白但是必须明白,在解决实际问题的全过程中在解决实际问题的全过程中,发现结果发现结果有问题有问题,同时数学模型中同时数学模型中有线性方程组出现有线性方程组出现,则方程组则方程组的的病态可能是出问题的环节之一病态可能是出问题的环节之一.上页上页下页下页 病态方程组无论选用什么方法去解病态方程组无论选用什么方法去解,都不能根本都不能根本解决原始误差的扩大解决原始误差的扩大,即使采用即使采用全主元消去法全主元消去法也不行也不行.可以试用可以试用加大计算机字长加大计算机字长,比如用比如用双精度字长双精度字长计算计算,或或可使问题相对得到解决可使问题相对得到解决.如仍不行如仍不行,则最好则最好考虑修改数考虑修改数学模型学模型,避开病态方程组避开病态方程组.如拟合问题中出现的如拟合问题中出现的正规方程组正规方程组,就往往就往往呈现病呈现病态态,此时解决问题的此时解决问题的方法之一是避开正规方程组方法之一是避开正规方程组,采用采用正交多项式拟合的方法正交多项式拟合的方法,尽管后者比前者在理论上和尽管后者比前者在理论上和实际计算中都复杂得多实际计算中都复杂得多.上页上页下页下页 例例如如,n阶阶希希尔尔伯伯特特矩矩阵阵,当当n较较大大时时,是是有有名名的的病病态态矩矩阵阵.在在函函数数逼逼近近时时,有有时时得得到到方方程程组组Hnx=b,当当n稍稍大大,用用任任何何方方法法都都难难以以解解出出理理想想的的结结果果.考考查查它它的的条条件件数数表表可可见见Hn在在n稍稍大大时时,即即呈呈严严重重病病态态.下下面面我我们们通通过过例题来考察例题来考察Hn的病态情况的病态情况.上页上页下页下页 例例9 已知希尔伯特已知希尔伯特(Hilbert)矩阵矩阵求条件数求条件数cond(H2)2,cond(H2)1和和cond(H2).解解 因为因为上页上页下页下页上页上页下页下页上页上页下页下页 下面再分析下面再分析H3的情况的情况 (2)考虑方程组考虑方程组 (1)计算计算H3的条件数的条件数cond(H3)|H3|=11/6,|H3-1|=408,所以所以cond(H3)=748.同样可计算同样可计算cond(H6)=2.9107,cond(H7)=9.85108.由此看出当由此看出当n越大时越大时,Hn矩阵病态越严重矩阵病态越严重.H3 x=(11/6,13/12,47/60)T=b,上页上页下页下页设设H3及及b有有微小误差有有微小误差(取取3位有效数字位有效数字)有有简简记记为为(H3+H3)(x+x)=b+b.方方程程组组H3x=b与与(6.8)的精确解分别为的精确解分别为x=(1,1,1)T,x+x=(1.089512538,0.48967062,1.491002798)T.于是于是 x=(0.0895,-0.5120,0.4910)T,上页上页下页下页这这就就是是说说H3与与b相相对对误误差差不不超超过过0.3%,而而引引起起解解的的相相对误差超过对误差超过50%.由由上上面面的的讨讨论论,要要判判别别一一个个矩矩阵阵是是否否病病态态需需要要计计算算条条件件数数cond(A)=|A-1|A|,而而计计算算A-1是是比比较较费费劲劲的的,那么在实际计算中如何发现病态情况呢那么在实际计算中如何发现病态情况呢?(1)如如果果在在A的的三三角角约约化化时时(尤尤其其是是用用主主元元素素消消去去法法解解(6.3)时时)出出现现小小主主元元,对对大大多多数数矩矩阵阵来来说说,A是是病病态态矩矩阵阵,例例如如用用选选主主元元的的直直接接三三角角分分解解法法解解方方程程组组(6.8)(结结果舍入为果舍入为3位浮点数位浮点数),则有则有上页上页下页下页 (2)系系数数矩矩阵阵A的的行行列列式式值值相相对对说说很很小小,或或系系数数矩矩阵某些行近似线性相关阵某些行近似线性相关,这时这时A可能病态可能病态.(3)系系数数矩矩阵阵A的的元元素素间间数数量量级级相相差差很很大大,并并且且无无一定规则一定规则,这时这时A可能病态可能病态.上页上页下页下页 用用选选主主元元素素的的消消去去法法不不能能解解决决病病态态问问题题,对对于于病病态态方方程程组组可可采采用用高高精精度度的的算算术术运运算算(采采用用双双倍倍字字长长进进行行运运算算)或或者者采采用用预预处处理理方方法法,即即将将求求解解Ax=b转转化化为为一一等等价方程组价方程组选择非奇异矩阵选择非奇异矩阵P,Q使使cond(PAQ)cond(A).一般选择一般选择P,Q为对角阵或者三角矩阵为对角阵或者三角矩阵.当当矩矩阵阵A的的元元素素大大小小不不均均时时,对对A的的行行(或或列列)引引进进适适当当的的比比例例因因子子(使使矩矩阵阵A的的所所有有行行或或列列按按-范范数数大大体体上上有有相相同同的的长长度度,使使A的的系系数数均均衡衡),对对A的的条条件件数数是是有影响的有影响的.这种方法不能保证这种方法不能保证A的条件一定得到改善的条件一定得到改善.上页上页下页下页其中其中A为非奇异矩阵为非奇异矩阵,当当A为为低阶稠密矩阵低阶稠密矩阵时时,第第5章讨论的选主元消去法是有效的章讨论的选主元消去法是有效的.但对于但对于大型稀疏大型稀疏矩阵方程组矩阵方程组(A的阶数的阶数n很大，但很大，但零元素较多零元素较多),利用利用迭代法求解是合适的迭代法求解是合适的.本章将介绍迭代法的一些基本理论及本章将介绍迭代法的一些基本理论及雅可比雅可比迭代法迭代法，高斯高斯-赛德尔迭代法赛德尔迭代法，超松弛迭代法超松弛迭代法，而，而超松弛迭代法应用很广泛。超松弛迭代法应用很广泛。下面举简例，以便了解迭代法的思想下面举简例，以便了解迭代法的思想.对线性方程组对线性方程组 Ax=b，(1.1)3.5 解线性方程组的迭代方法解线性方程组的迭代方法上页上页下页下页 例例1 求解方程组求解方程组记为记为Ax=b，其中，其中方程组的精确解是方程组的精确解是x*=(3,2,1)T.现将改写为现将改写为上页上页下页下页或写为或写为x=B0 x+f，其中，其中上页上页下页下页 我们任取初始值，例如取我们任取初始值，例如取x(0)=(0,0,0)T.将这些值将这些值代入代入(1.3)式右边式右边(若若(1.3)式为等式即求得方程组的解，式为等式即求得方程组的解，但一般不满足但一般不满足)，得到新的值，得到新的值x(1)=(x1(1),x2(1),x3(1)T=(3.5,3,3)T，再将，再将x(1)分量代入分量代入(1.3)式右边得到式右边得到 x(2)，反复利用这个计算程序，得到一向量序列和一般的计反复利用这个计算程序，得到一向量序列和一般的计算公式算公式(迭代公式迭代公式)上页上页下页下页简写为简写为 x(k+1)=B0 x(k)+f，其中其中k表示迭代次数表示迭代次数(k=0,1,2,).迭代到