计算方法第三章

}第3章线性代数方程组的解法3.1顺序高斯消去法3.2选主元高斯消去法3.3行列式和逆矩阵的计算3.4解三对角线性方程组的追赶法3.5三角分解法3.6线性代数方程组的迭代解法3.7迭代法的收敛性简介矩阵形式:AX=b,其中当A非奇异时，detA≠0，方程组有唯一解。本章解决的问题：线性代数方程组的基本解法。n个未知量n个方程的线性代数方程组}(3.1)}两类解法：直接解法:经过有限步运算就能求得精确解的方法，但实际计算中由于舍入误差的影响，这类方法也只能求得近似解；迭代解法:构造适当的向量序列，用某种极限过程去逐步逼近精确解。例如：高斯消去法、三角分解法等例如：雅可比迭代法、高斯赛德尔迭代法等}高斯消去法的基本思想：先消元，即按一定的规律逐步消去未知量，将方程组化为等价的上三角形方程组；然后进行回代，即由上三角形方程组逐个求出}3.1顺序高斯消去法(消元过程按方程和未知量的自然顺序进行.)3.1.1顺序高斯消去法举例3.1.2一般情况的计算过程}3.1.1顺序高斯消去法举例例用顺序高斯消去法求解方程组解消元过程：[A，b]=对增广矩阵[A，b]做消元计算，}[A，b]=240110220.51.5013-0.55.5012122401100010.751.25240110220.51.5002-0.754.750001.125-1.125消元过程结束，得上三角形方程组0220.51.502-0.754.75}回代过程：求解上三角形方程组所以方程组的解为}基本的顺序高斯消去法,其消元过程遵守如下规则:依从左到右、自上而下的次序将主对角元下方的元素化为零。不作行交换，也不用非零数乘某行。第k列消元（将主对角元下方化零）时，将下面各行分别减去第k行的适当倍数，不作其他变换。}练习：用顺序高斯消去法求解方程组解230111155621123010-1/219/20-3/2217/223010-1/219/200-1-5得上三角形方程组，再回代得x1=–1,x2=1,x3=5}3.1.2一般情况的计算过程为统一公式，把常数项bk换名为akn+1，(k=1,2,…,n)先看4阶的情形第1列消元（设a11≠0），作}化为其中令，则计算公式合写为}第2列消元（设a22（1）≠0），化为其中即}第3列消元（设a33（2）≠0），化为上三角形方程组其中，计算公式写为}对于n阶的一般情形}一般，对于n阶的方程组，需要对前n-1列进行消元。设已进行了第1列至第k–1列消元，将第i行减去第k行的lik倍，(i=k+1,…,n)第k列消元，}}第n-1列消元后得到与原方程组同解的上三角形方程组}若，则一般由第k个方程得消元过程结束。进行回代过程，由上三角形方程组依次求出xn,xn-1,…,x1。点击可显示方程组→顺序高斯消去法的计算步骤：(1)消元过程。对k=1,2,…,n-1计算(2)回代过程。对k=n,n-1,…,1计算①若akk=0,则算法失败,结束计算；否则做下步。②对i=k+1,k+2,…,n计算称为消元过程的主元素。其中}}问题1.消元过程能按顺序进行到底的充要条件是什么？问题2.在原方程组的系数矩阵中如何反映出这个条件呢?答：A的k阶顺序主子矩阵Ak的行列式值是:考察矩阵A的k阶顺序主子矩阵Ak，即A的左上角k行k列的子矩阵，例如：123A=456则A1=(1),A2=12,A3=A78945}定理对于方程组(3.1)，顺序消元过程能进行到底的充要条件是系数矩阵A的顺序主子矩阵Ak(k=1,2,…,n-1)非奇异。方程组(3.1)能用顺序高斯消去法求解的充要条件是系数矩阵的一切顺序主子矩阵均非奇异。}思考：顺序高斯消去法的数值稳定性如何？例用顺序高斯消去法解下面的方程组，用3位有效数字计算（假定机器字长为3）回代求得方程组的准确解是误差：|ε(x1)|=10,解结论：顺序高斯消去法往往是数值不稳定的。-3-1000×2=-2003≈-200040-1000×40.1≈-40100由此产生选主元的思想。|εr(x1)|=2=200%，误差太大！原因：主元0.02绝对值比它下面的元素20小得多。基本思想：每次消元前按一定的范围选取绝对值最大的元素作为主元素。以便减少舍入误差的影响。主要有列主元高斯消去法和全主元高斯消去法.}3.2选主元高斯消去法1、列主元高斯消去法：当k-1列消元后增广矩阵为}第k次消元时，先选列主元素，即在第k列以下的各元素中寻找绝对值最大的元素作为主元素。即确定r，使中之最大者。为}只要detA≠０，就必能找到若rk则交换第k行和第r行，然后进行消元。例用列主元高斯消去法求解方程组(用三位有效数字计算)解选主元选主元}消元过程完成，得到上三角形方程组再作回代可求得}练习：用列主元高斯消去法求解方程组解2301111556211230111155621103/5-4/5-17/50-1/53/514/55621103/5-4/5-17/50-1/53/514/55621103/5-4/5-17/5001/35/356211}得上三角形方程组x1=–1,x2=1,x3=5再回代得}列主元高斯消去法(简称列主元消去法)的计算步骤：(1)消元过程。对k=1,2,…,n-1作下列运算：①按列选主元:确定r，使满足若ark=0，说明系数矩阵奇异，则停止计算并转结束；②行交换:若rk,则交换第r行和第k行，即对j=k,k+1,…,n+1计算}(2)回代过程。若ann＝０，则系数矩阵为奇异，停止计算并转结束；否则计算③消元计算：对i=k+1,k+2,…,n,j=k+1,k+2,…,n+1计算}2、全主元高斯消去法简称全主元消去法，在第k列(k=1,2,…，n-1)消元时，从系数矩阵的右下角(n-k+1)阶子矩阵中，选取绝对值最大的元素作为主元素。}例用全主元高斯消去法求解方程组(用三位有效数字计算)解选主元选主元}得到等价的上三角形方程组回代求得}3.2.2对算法的说明1.系数矩阵为对称正定或是严格对角占优的情形n阶矩阵A为对称正定的充要条件是AT=A且其一切顺序主子式均大于0。n阶矩阵A为严格对角占优矩阵是指其每个主对角元的绝对值大于同一行其他元素绝对值之和，即一阶严格对角占优矩阵指一个非零数。}例如由于第1行所以B是严格对角占优矩阵。C不是严格对角占优矩阵当方程组的系数矩阵为对称正定或严格对角占优矩阵时，可用顺序高斯消去法求解。第2行第3行}2.病态方程组如果一个方程组的系数或者常数项只要有一点微小的误差就会引起解的巨大变化，这样的方程组就称为是病态的。例由于右端系数有误差，方程组变成解就变成解的最大误差达200％。对于病态方程组，前面的算法都可能失效，需要使用一些改进精度的算法。3.3行列式和逆矩阵的计算⒈行列式的计算：}例列主元法的消元过程计算过程有2次行交换，故p=2，主元为5，2.01，1.78detA≈(-1)2×5×2.01×1.78=18.0(准确值detA=17.8325)p为消元过程中交换行（列）的次数。}全主元法的消元过程若A计算过程进行了一次行交换，一次列交换，p=2，则detA≈(-1)2×5×2.10×1.70=17.9}2.逆矩阵的计算：当detA≠0时，A存在逆矩阵，设s=1,2,…,n求A-1就相当于求解n个线性方程组具体计算时，令}同时求解n个方程组,并将解x(s)存入原来es的位置(s=1,2,…,n）。为了求逆方便，消元时可将主元上方也消为0，并将第k行除以akk(k=1,2,…,n)，使主元位置化为1，最后增广矩阵化为这种算法无须回代，称做高斯-约当(Jordan)消去法。=A-13.4解三对角线性方程组的追赶法其系数矩阵为三对角矩阵}三对角线性方程组}定理3.2当三对角矩阵满足条件时，其所有顺序主子矩阵均非奇异。因此，三对角方程组的求解可以直接用顺序高斯消元法而不必选主元。将顺序消元过程略加修改：每次消元前将主元素先化为1，即做“归一化”处理。}}将第k行除以bk,第k+1行减去第k行的ak+1倍。计算公式：第k次消元计算时增广矩阵第k、k+1两行形为}消元结束后，增广矩阵化为一般计算公式为（令cn=0)（追）}消元结束后，增广矩阵化为,得方程组回代计算：（赶）上述计算过程也称为追赶法。}追赶法的计算框图：始开dc,b,a,输入111111/,/bccbddkkkkkkkkkkkkbccbadddacbbnk//)(,,3,211计算对nndx1,,2,11nnkxcdxkkkkx出输束结在计算机上一般用四个一维数组a[],b[],c[],d[]分别存放三对角线元素及方程组右端常数向量，其中令a[1]=0,c[n]=0。}追赶法的优点：（1）大大节省存储空间只需用4n个单元。而一般的方程组需要n2+n个单元。（2）大大减少了计算量一般的高斯消元过程需要O(n3)次乘除法运算,而“追”的过程只用4n次乘除运算.3.5三角分解法3.5.1矩阵的三角分解。·初等行变换和初等矩阵333231232221131211aaaaaaaaaA例如523rr233322322131232221131211555aaaaaaaaaaaa做初等矩阵15001000132L有233322322131232221131211555aaaaaaaaaaaa15001000132AL333231232221131211aaaaaaaaa}。消元过程有,)()1(kikkAlkiA倍行的第行第行第行第令ikikkilL1111则)()1(kkikAAL})1()1(kkkkikkiaal。一般消元过程依次将a21,a31,…,an1,a32,a42,…,an2,…,ann-1化为0，相当于用一系列初等矩阵L21,L31,…,Ln1,L32,…,Ln2,…,Lnn-1依次左乘A,得到上三角阵A(n-1)。,)1(21311nnnAALLL)1(121311)(nnnALLLA}121311)(LLLLnn令。})1(nLAA得)1()1(2)1(22112112121111nnnnnnnaaaaaalll定义设A为n阶矩阵，若A有分解式A=LU其中L为下三角阵，U为上三角阵，则称之为A的LU分解或三角分解。三角分解。}问：任一矩阵是否存在三角分解？若存在，是否惟一？答：不一定存在。若存在，则不惟一。杜利特尔分解(Doolittle)常用的两种三角分解：克劳特分解(Crout)nnnnnnuuuuuulll222112112121111111211221222111nnnnnnuuullllll例如A=，这里有A的两种不同的三角分解，类似可举出很多，一般，若A=LU是一个三角分解，任取与A同阶的非奇异对角矩阵D，则A=（LD）（D-1U）=L1U1也是A的三角分解。503212011432350323201。}定理3.3n阶矩阵A存在唯一的杜利特尔分解和克劳特分解的充要条件是A的顺序主子矩阵Ak(k=1,2,…,n-1)非奇异。推论若定理3.3的条件满足，则A存在唯一的LDU分解式，其中为L单位下三角阵，U为单位上三角阵，D为对角阵。即1111112112212121nnnnnuuudddlll反之也真。A