线性方程组的数值解法素材.ppt

,n阶线性代数方程组的一般形式为：,第三章线性方程组的数值解法,问题的提出：,写成矩阵-向量形式,若矩阵非奇异，即的行列式，根据克莱姆（Gramer）法则，方程组有唯一解：,其中为系数矩阵，为解向量，为右端常向量。,其中表示，表示中第列换成后所得的行列式。,当阶数较高时用这种方法求解是不现实的。阶行列式有项，每项又是个数的乘积。对较大的，其计算量之大，是一般计算机难以完成的。而且，这时的舍入误差对计算结果的影响也较大。,例如，求解一个20阶线性方程组，用加减消元法需3000次乘法运算，而用克莱姆法则要进行次运算，如用每秒1亿次乘法运算的计算机要30万年。,直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题,3.1消去法,消去法的基本思想：是通过将一个方程乘或除以某个常数，以及将两个方程相加减，逐步减少方程中的变元数，最终使每个方程只含一个变元，从而得出所求的解。,高斯消去法属于直接法，一般由“消元过程”和“回代过程”两部分组成。先举几个简单实例，再对一般n阶方程组说明高斯消去法的基本思想。,消去法,3.1高斯消去法按自然顺序进行的消元法,例1用高斯消元法求解方程组,解用第一个方程削去后两个方程中的得,再用第2个方程消去第3个方程中的得,最后，经过回代求得原方程组的解为,例2解方程组,解：消元,回代得,消去法,下面讨论一般n阶线性方程组的高斯消去法。记为，和的元素分别记为和，系数上标代表第1次消元之前的状态。第1次消元时，设对每行计算乘数,用乘以第1个方程，加到第个方程，消去第2个方程到第个方程的未知数，得即:,其中：,第次消元时，设第次消元已完成，即有其中：设，计算乘数,只要，消元过程就可以进行下去，直到经过消元之后，消元过程结束，得也即,这是一个与原方程组等价的上三角形方程组。把经过n-1次消元将线性方程组化为上三角形方程组的计算过程称为消元过程。,当时，对上三角形方程组自下而上逐步回代解方程组，计算,即,称为各次消元的主元素，主元素所在的行称为主行。,高斯消去法的计算步骤为：1消元过程设，对，计算2回代过程,高斯消去法的计算机运算和存储方式的特点：1按消元规则进行运算后，对角线以下元素为0。故对于对角线以下元素不用作计算，减小了计算量。,3对角线以上元素和常数变换后的元素仍放在原来的位置以节省存储单元。,4回代后的数值仍放在常数项存储单元这时单元中存放的就是输出值,定理2Ax=b可用高斯消元法求解的充分必要条件是：系数矩阵A的各阶顺序主子式均不为零。,高斯消元法的条件,定理1如果在消元过程中A的主元素(k=1,2,n),则可通过高斯消元法求出Ax=b的解。,引理A的主元素(k=1,2,n)的充要条件是矩阵A的各阶顺序主子式不为零，即,定理：高斯消去法求解n阶线性方程组共需乘除法次数近似为。证明：见书P61,高斯消去法的计算量,例1解方程组,解法一用高斯消元法求解（取5位有效数字），用第一个方程消去第二个方程中的,3.1.2高斯主元素消元法,因而再回代，得,而精确值为显然该解与精确值相差太远，为了控制误差，采用另一种消元过程。,解法二为了避免绝对值很小的元素作为主元，先交换两个方程，得到,再回代，解得,结果与准确解非常接近。这个例子告诉我们，在采用高斯消元法解方程组时，用做除法的小主元素可能使舍入误差增加，主元素的绝对值越小，则舍入误差影响越大。固应避免采用绝对值小的主元素，同时选主元素尽量的大，可使该法具有较好的数值稳定性。,为避免上述错误，可在每一次消元之前增加一个选主元的过程，将绝对值大的元素交换到主对角线的位置。根据交换的方法可分成全选主元和列选主元两种方法。,列主元素消元法,列选主元是当变换到第k步时，从k列的及以下的各元素中选取绝对值最大的元素，然后通过行交换将其交换到的位置上。交换系数矩阵中的两行（包括常数项），相当于两个方程的位置交换了。,例：求解线性方程组,解法一：用列主元素消元法，方程组增广矩阵为：,交换1、3行（列选主）,消元,消元,回代计算解为,选主元,全选主元素消元法,全选主元是当变换到第k步时，从右下角n-k+1阶子阵中选取绝对值大的元素，然后通过行交换与列交换将其交换到akk的位置上，并且保留交换的信息，以供后面调整解向量中分量的次序时使用。,交换1、3行交换1、3列,回代计算得,从而原方程的解为,消元,消元,3.1.3高斯-约当(Jordan)消去法消元时将主元上方元素也消为0，最后系数矩阵化为对角矩阵。这种算法只有消元，没有回代，这种方法称做高斯-约当(Jordan)消去法。,比较而言,Gauss顺序消去法条件苛刻,且数值不稳定;Gauss全主元消去法工作量偏大，算法复杂；对于Gauss-Jordan消去法形式上比其他消元法简单，且无回代求解，但计算量大。因此从算法优化的角度考虑，Gauss列主元消去法比较好。,消去法小结,3.2矩阵三角分解法,3.2.1矩阵三角分解原理应用高斯消去法解阶线性方程经过步消去后得出一个等价的上三角形方程组，对上三角形方程组用逐步回代就可以求出解来。这个过程也可通过矩阵分解来实现。将非奇异阵分解成一个下三角阵和上三角阵的乘积：称为对矩阵的三角分解，又称分解。,高斯消去法解线性代数方程组的一种变形解法。,杜里特尔分解：把分解成一个单位下三角阵和一个上三角阵的乘积。克劳特分解:把分解成一个下三角阵和一个单位上三角阵的乘积。,杜里特尔分解A=LU,杜里特尔分解,杜里特尔分解(一般算法),由矩阵乘法规则,即：,由此可得的第一行元素和的第一列元素,当已得出的前行元素和的前列元素，则对于，由,又可得计算的第行元素和的第列元素的公式:,所以,矩阵三角分解算法总结：,有了矩阵A的LU分解计算公式，当求解线性方程组时，等价于求解。这时可归结为利用递推计算相继求解两个三角形方程组（系数矩阵为三角矩阵）。用顺代，由求出，再利用回代，由求出。,3.2.2解线性方程组的三角分解法,用杜里特尔三角分解法解线性方程组的计算方法：,克劳特分解求方程组步骤：略,其它矩阵分解法求解特殊的线性方程组：,平方根法：主要用于求解正定矩阵的线性方程组追赶法：主要用于求解特殊矩阵的三对角方程组见书P78P87,用LU直接分解的方法求解线性方程组的计算量为，和高斯消去法的计算量的数量级基本相同。,消去法和矩阵三角分解法比较,当方程组系数矩阵不变，只有右侧向量b变化时，用LU分解法比消去法速度快。因为右侧向量b的改变不影响LU的变化。,高斯消去法和LU分解法是等价的，其关键是把一般方程组变为三角方程组，只是实现途径不同。,3.4向量与矩阵的范数,问题的提出,向量范数概念是三维欧氏空间中向量长度概念的推广,在数值分析中起着重要作用.,为了研究线性方程组近似解的误差估计和迭代法的收敛性，我们需要对（n维向量空间）中向量及（维矩阵空间）中矩阵的“大小”及“距离”引进某种度量向量与矩阵范数的概念.,平面向量x大小：用距离反映。,3.4向量与矩阵的范数,引入范数的目的：,实数大小：用绝对值反映,复数大小：用模反映,高维空间向量x“大小”用反映？,将度量长度数值的计算方法引入高维空间，用来反映空间向量的大小，就是范数的概念。,为了研究线性方程组近似解的误差估计和迭代法的收敛性等。,3.4.1向量的范数,由定义可知，向量的范数是按一定规律与对应的实数，该实数的值没有确定，但只要满足这三个条件，这个实数就是向量的一种范数。因此定义中的三个条件称为范数公理。,当时，,向量范数有如下性质,证：利用条件，有,证：,它们分别叫做向量的-范数、1-范数、2-范数、p-范数（0p+）。p-范数是以上范数的统一表达形式。,常用的向量范数:满足定义的范数不是唯一的.,设x=(x1,x2,xn)T，常用的向量范数有,对于范数，有当时，有，只有当时，才有对任意实数，因为，所以。对任意向量，有,因此是n维空间的一种范数,例：范数的证明,可以证明这几种范数满足下述关系,事实上，对Rn上任意两种向量范数|x|,|x|，都存在与x无关的正常数c1,c2使,这种性质称为向量范数的等价性。,定理：设Rn上的任意两种范数|x|a,|x|b,都存在与x无关的正常数c1,c2使得,称满足不等式的两种范数|x|a,|x|b是等价的。,推论：有限维Rn上的不同范数是等价的。,向量收敛的定义：,按不同方式规定的范数,其值一般不同。但在各种范数下考虑向量序列收敛性的结论是一致的。即向量序列如对某一种范数收敛则对其它范数也收敛，且有相同的极限。这样，在研究某一具体问题时，可以选择一较易简单的范数。,矩阵范数是用于定义矩阵“大小”的量。由于在大多数与估计误差有关的问题中,矩阵和向量的乘积经常出现,所以希望引进一种矩阵的范数,它与向量范数有某种关系。,3.4.2矩阵的范数,矩阵范数的性质：,且仅当时，；对任意实数，；对同维方阵，有:,相容性条件：由矩阵范数的定义可直接得到，即有，称为相容性条件。即所给的矩阵范数与向量范数是相容的。,证明p92,矩阵范数与向量范数的关系：,证明：,矩阵范数与向量范数的关系：,常用的矩阵范数有（矩阵范数的求取）,它们分别叫做矩阵的-范数、1-范数、谱范数。,（谱范数）,表示,的最大特征值。,解,验证相容性,3.5方程组的性态,3.5.1方程组的性态和矩阵的条件数,例1解方程组其中,现用绝对精确的计算（即不带任何舍入误差的计算）求解，可以看出,此时，我们发现对于两组不同的自由项,它的差只有,而所得解与之差却是,两组不同的右端其分量之差不过是可是解的差高达之1860倍像这样的方程组或矩阵A就叫做病态的,定义1若方程组Ax=b的系数矩阵A或右端向量b的微小变化（小扰动）引起解产生巨大变化,则称此方程组为病态方程组;A称为病态矩阵,否则称为良态方程组,A称为良态矩阵。,定理：设非奇异，且则,为了定量地刻划方程组的“病态”程度，下面就一般方程组进行讨论。首先考察右端项b的扰动对解的影响。,证：设x为Ax=b的准确解，当方程组右端有小扰动b而A准确时,受扰解为x+x,即A(x+x)=b+b因为Ax=b所以x=A-1b,因此,所以,此不等式表明,解的相对误差不超过b的相对误差的|A|A-1|倍.,矩阵的条件数与范数有关，通常使用的条件数有,例求矩阵A的条件数，其中,解：,于是从而,所以A是病态的,由于计算条件数涉及到计算逆矩阵，很麻烦。因此实际计算中一般通过可能产生病态的现象来判断。若在消元过程中出现小主元，则A可能是病态矩阵。但病态矩阵未必一定有这种小主元。若解方程组时出现很大的解，则A可能是病态矩阵。但病态矩阵也可能有一个小解。从矩阵本身看，若元素间数量级相差很大且无一定规律；或者矩阵的某些行或列近似相关，这样的矩阵则有可能是病态矩阵。,3.5.2直接法的精度分析,定理：设是方程组的一个近似解，其精确解记为，为的余量，则有,该定理给出了方程组近似解的相对误差界。即相对误差的事后估计,生成向量序列x(k)，若,迭代法基本思想：,将方程组Ax=b(|A|0)转化为与其等价的方程组,x=Bx+f,3.6迭代法,雅可比迭代法,对线性方程组可以建立不同的迭代格式。下面介绍构造迭代格式的几种常用方法，雅克比迭代法和高斯塞德尔迭代法。,设方程组,分别从上式n个方程中分离出n个变量，如下：,等价方程组,建立迭代格式,称为雅可比(Jacobi)迭代法又称简单迭代法。,高斯塞德尔迭代法,或缩写为,称为高斯塞德尔（GaussSeidel）迭代法。,例1用雅可比迭代法解方程组,雅克比迭代格式,Gauss-Seidel,迭代格式为,例2用GaussSeidel迭代法解上题。,取x(0)=(0,0,0)T计算如下：,以上介绍的两种迭代法，一般地说，高斯塞德尔比雅克比要好，但也不完全是这样。,关于迭代法的一些问题：,为了使迭代法计算加速，可采用松弛法。（略）,迭代法存在收敛性问题。（略）,要求熟练掌握的内容：高斯消去法原理、算法、计算步骤；主元消去法的意义、算法、计算步骤；矩阵三角分解法