第三章 线性方程组的数值解法

n阶线性代数方程组的一般形式为：nnnnxnnnnxnnxbxaxaxabxaxaxabxaxaxa21122221211112111第三章线性方程组的数值解法问题的提出：写成矩阵-向量形式bAx若矩阵非奇异，即的行列式，根据克莱姆（Gramer）法则，方程组有唯一解：AA0detADDxiini,,2,1nnnnaaaaA1111nxxx1nbbb1Axb其中为系数矩阵，为解向量，为右端常向量。其中表示，表示中第列换成后所得的行列式。ibiDDAdetD线性代数方程组的计算机解法常用方法：直接法迭代法当阶数较高时用这种方法求解是不现实的。阶行列式有项，每项又是个数的乘积。对较大的，其计算量之大，是一般计算机难以完成的。而且，这时的舍入误差对计算结果的影响也较大。n!nnn消去法矩阵三角分解法–直接法：经过有限步算术运算，可求得方程组的精确解的方法（若在计算过程中没有舍入误差）–迭代法：用某种极限过程去逐步逼近线性方程组精确解的方法–迭代法具有占存储单元少，程序设计简单，原始系数矩阵在迭代过程中不变等优点，但存在收敛性及收敛速度等问题3.1消去法消去法的基本思想：是通过将一个方程乘或除以某个常数，以及将两个方程相加减，逐步减少方程中的变元数，最终使每个方程只含一个变元，从而得出所求的解。消去法在线性代数中已有详细的讨论，在此只给出一些说明以及算法的具体描述。消去法常用方法：高斯消去法选主元消去法高斯－约旦消去法高斯消去法属于直接法，一般由“消元过程”和“回代过程”两部分组成。先举几个简单实例，再对一般n阶方程组说明高斯消去法的基本思想。消去法3.1高斯消去法——按自然顺序进行的消元法例1用高斯消元法求解方程组52213614282321321321xxxxxxxxx解用第一个方程削去后两个方程中的得,1x9962214282232321xxxxxx再用第1个方程消去第2个方程中的得,2x18962214282332321xxxxxx最后，经过会代求得原方程组的解为52281412262918321323xxxxxx例2解方程组02115472321321321xxxxxxxxx解：消元01211115471123235.2rr6200333071125.35.05.203330711231212124rrrr回代得,3263x,233332xx127321xxx消去法下面讨论一般n阶线性方程组的高斯消去法。记为，和的元素分别记为和，，系数上标代表第1次消元之前的状态。第1次消元时，设对每行计算乘数1ijabAx11bxA1A1b1ibnji,,2,1,10111aniaamii,,3,2,111111用乘以第1个方程，加到第个方程，消去第2个方程到第个方程的未知数，得即:i1imn1x22bxA22211212222222211112111nnnnnnnbbbxxxaaaaaaanjibmbbamaaiiijiijij,,3,2,1111211112其中：第次消元时，设第次消元已完成，即有其中：设，计算乘数k12nk1kkkbxAknnknkkknkkknnkaaaaaaaaaaA2222322211112111knkkkbbbbb22110kkkankiaamkkkkikik,,1,只要，消元过程就可以进行下去，直到经过消元之后，消元过程结束，得也即0kkka1nnnbxAnnnnnnnnbbbxxxaaaaaa2211212222211112111这是一个与原方程组等价的上三角形方程组。把经过n-1次消元将线性方程组化为上三角形方程组的计算过程称为消元过程。当时，对上三角形方程组自下而上逐步回代解方程组，计算,即,称为各次消元的主元素，主元素所在的行称为主行。0nnna11,,,xxxnn1,2,,1,1niaxabxabxiiinijjiijiiinnnnnnnkakkk,,2,1,高斯消去法的计算步骤为：1〉消元过程设，对，计算2〉回代过程0kkka1,,2,1nknkkjibmbbamaaaamkkikkikikkjikkijkijkkkkikik,,2,1,11)()(1,2,,1,1niaxabxabxiiinijjiijiiinnnnnn综上所述，高斯消去法的框图如图3-1所示。从中可看出高斯消去法的计算机运算和存储方式的特点：1〉按消元规则进行运算后，对角线以下元素为0。故对于对角线以下元素不用作计算，减小了计算量。nkkiaaaikkkik,,2,1,2〉对角线以下元素对回代求解无影响，故可将乘数放在该处，即以节省存储单元。3〉对角线以上元素和常数变换后的元素仍放在原来的位置以节省存储单元。nkkjibbabaaaaijikiijkjikij,,2,1,4〉回代后的数值仍放在常数项存储单元这时单元中存放的就是输出值1,2,,11nibaxabbabiiinijjijinnnnnbbb,,,21nxxx,,,21定理2Ax=b可用高斯消元法求解的充分必要条件是：系数矩阵A的各阶顺序主子式均不为零。高斯消元法的条件定理1如果在消元过程中A的主元素(k=1,2,…,n),则可通过高斯消元法求出Ax=b的解。0)(kkka1110Da11110,2,3,,kkkkkaaDknaa引理A的主元素(k=1,2,…,n)的充要条件是矩阵A的各阶顺序主子式不为零，即0)(kkka定理：高斯消去法求解阶线性方程组共需乘除法次数近似为。证明：见书P6433n高斯消去法的计算量讨论：在求解线性方程组时其系数矩阵绝大部分都是非奇异的，但可能出现主元素消去法无法进行；或|akk(k)|1时，带来舍入误差的扩散。如何处理？0)(kkka例1解方程组0000.10000.10000.10001.20000.30003.02121xxxx0.66660.99990001.20000.30003.0221xxx解法一用高斯消元法求解（取5位有效数字），用第一个方程消去第二个方程中的,1x3.1.2高斯主元素消元法因而再回代，得00003.006667.0000.30001.206667.0.99990.666612xx而精确值为显然该解与精确值相差太远，为了控制误差，采用另一种消元过程。32,3121xx解法二为了避免绝对值很小的元素作为主元，先交换两个方程，得到0001.20000.30003.00000.10000.10000.12121xxxx消去第二个方程中的得,1x9998.19997.20000.10000.10000.1221xxx再回代，解得3333.06667.00000.10000.16667.09997.29998.112xx结果与准确解非常接近。这个例子告诉我们，在采用高斯消元法解方程组时，用做除法的小主元素可能使舍入误差增加，主元素的绝对值越小，则舍入误差影响越大。固应避免采用绝对值小的主元素，同时选主元素尽量的大，可使该法具有较好的数值稳定性。为避免上述错误，可在每一次消元之前增加一个选主元的过程，将绝对值大的元素交换到主对角线的位置。根据交换的方法可分成全选主元和列选主元两种方法。列主元素消元法列选主元是当变换到第k步时，从k列的及以下的各元素中选取绝对值最大的元素，然后通过行交换将其交换到的位置上。交换系数矩阵中的两行（包括常数项），相当于两个方程的位置交换了。kkakka例：求解线性方程组000.3000.2000.1643.5072.1000.2623.4712.3000.1000.3000.2001.0321xxx解法一：用列主元素消元法，方程组增广矩阵为：000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0~A交换1、3行（列选主）002.1003.3001.20500.0801.1176.30000.3643.5072.1000.2000.1000.3000.2001.0000.2623.4712.3000.1000.3643.5072.1000.2687.0868.100500.0801.1176.30000.3643.5072.1000.2消元消元回代计算解为Tx3678.0,05113.0,4990.0*选主元全选主元素消元法全选主元是当变换到第k步时，从右下角n-k+1阶子阵中选取绝对值大的元素，然后通过行交换与列交换将其交换到akk的位置上，并且保留交换的信息，以供后面调整解向量中分量的次序时使用。解法二用完全主元素消元法求解0123000.1001.0000.2000.3000.2000.1712.3623.4000.3000.2072.1643.50321000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0IA解法二用完全主元素消元法求解0123000.1001.0000.2000.3000.2000.1712.3623.4000.3000.2072.1643.50321000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0IA交换1、3行交换1、3列解法二用完全主元素消元法求解0123000.1001.0000.2000.3000.2000.1712.3623.4000.3000.2072.1643.50321000.3643.5072.1000.2000.2623.4712.3000.1000.1000.3000.2001.0IA解法二用完全主元素消元法求解0123000.1001.0000.2000.3000.2000.1712.3623.4000.3000.2072.1643.50321000.3643.5072.