东北农业大学《数值分析》课件-第六章（隋老师）.pptx

东北农业大学 数值分析 第六章 第六章.线性代数方程组的数值解 Gauss 消去法 矩阵三角分解法 对称矩阵的平方根法 三对角方程组的追赶法 向量与矩阵范数及方程组的性态 解线性方程组的迭代法 分快迭代法 1.引言 n阶线性方程组：可以表示成矩阵形式：11112211211222221122 nnnnnnnnnna x a xa xba x a xa xba x a xa xb AXb ,X,11Tijn nTA nn,),)(x(bxbab35 det()0,det()(1,2,)det()1(1)!30,2.38 10iiAAxinnAnnnnnn每个如果线性方程组的系数行列式不为零，即则该方程组有唯一解。由克莱姆(Cramer)法则，其解为这种方法需要计算个 阶行列式并作 次除法，而阶行列式计算需作次乘法，计算量十分惊人。如需31 29 30!=次乘法。可见其n在理论上是绝对正确，但在 较大时，在实际计算中确实不可行的。解线性方程组的两类方法：直接法:经过有限次运算后可求得方程组精确解的方法(不计舍入误差!）迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。（一般有限步内得不到精确解)2.Gauss 消去法 简单消去法 Gauss顺序消去法的可行性及计算量 矩阵的三角分解法 主元素消去法 Gauss-Jordan列主元消去法 一、简单消去法一、简单消去法 将将n阶线性方程组阶线性方程组转化为等价（或同解）的转化为等价（或同解）的 三角形方程组三角形方程组 1111221122222 nnnnnnnngb x b xb xgb xb xgb x11,nnx xx的过程称为消元过程，逐次求出的过程称为消元过程，逐次求出 的步骤称为回代过程。的步骤称为回代过程。Gauss 消去法计算过程:统一记号 原方程为 相当于第i个方程-第一个方程数新的第i方程同解！第一方程不动！112111()()()aa第二行（第一行）新第二行Step1Step1 假设假设 上述消元过程除第一个方程不变以外,第2第n个方程全消去了变量 1，而系数和常数项全得到新值：得到同解方程组为 其中 111111iilaa(2)220 aStep2.若 ，保留方程组中第一及第二个方程，消去其余方程中变量x3,得同解方程组 记作 ，其中 (2)(2)2222iilaa系数矩阵与常数项：()()nnA，b计算出 的过程为消元过程。消去过程算法消去过程算法 1 k i,jn kkkkikiklaa回代过程算法回代过程算法 1,2,1inn对于 13241234242532431737xxxxxxxxxx例例1.1.用消去法解方程组用消去法解方程组 解：用增广矩阵表示求解过程解：用增广矩阵表示求解过程 1020501013|12431701037A b331 110205010130223 1201037rl r332 2442 210205010130021600024rl rrl r4/210205010130021600012r102050100100204000121020501001001020001210001010010010200012二、二、GaussGauss顺序消去法的可行性及计算量顺序消去法的可行性及计算量 GaussGauss消去和回代过程都要求元素消去和回代过程都要求元素 0(1,2,)kkkakn 0kkka称之为主元素。若称之为主元素。若 ，则计算无法，则计算无法 进行。但在系数矩阵保持一定条件时，则进行。但在系数矩阵保持一定条件时，则 可保证主元素非零，使可保证主元素非零，使GaussGauss顺序消去法在顺序消去法在 计算机上顺利执行。计算机上顺利执行。定理定理1 若矩阵若矩阵A的各阶顺序主子式均不为的各阶顺序主子式均不为零，即零，即 ，则，则 定理定理2 若矩阵若矩阵A对称正定对称正定，则则 det0kkDA 01,2,kkkakn定理定理3 若矩阵若矩阵A严格对角占优严格对角占优，则则 01,2,kkkakn 01,2,kkkakn矩阵矩阵 严格对角占优，若严格对角占优，若 ijn nAa1,1,2,niiijjj iaain消去第一列的 n-1 个系数要计算(n-1)+n*(n-1）次乘法。Gauss消去法乘法计算量消去法乘法计算量 消去第二列的 n-2 个系数要计算(n-2)+(n-1）*(n-2）次乘法。乘法计算量乘法计算量 回代过程总计算量 Gauss消去法乘除法总运算量为 三、矩阵三角分解法(2)(1)(2)(1)11 ,bbAL AL11211111311111012 3001L()()iin i,nllaall其中 每一步消去过程相当于左乘初等变换矩阵Lk，记 依此类推，得矩阵的LU分解形式 其中 111213122232333000 000nnnnnuuuuuuuuuu(1)(1)(1)(1)1112131(2)(2)(2)22232(3)(3)333()0 00000nnnnnnUaaaaaaaaaaLUxb方程组可写成方程组可写成 若令若令 Ly byUx则则上式变成上式变成 则求解原方程组Ax=b便转化为便转化为 LyUxyb上述矩阵分解法称为Doolittle分解,计算公式为 1111,(2,3,)iiiikkkybinybl y1,(1,2,1)/nnnnniiikkiik ixyuinnxyu xu 其中其中 1111111,2,/2,3,iiiiuainlaain1111,1,/,1,2,rririrkkikriririkkrrrkual uir rnlal uuirrn rn()()(1,2,1;1,)kikikkkkalknikna 得得 3132421,2,1,lll 其余全为0。例2：对于例1，由增广矩阵表示消元过程，有 故有 102011020010101101124312121010301012A1234150131211701017yyLyyy12345364yyyy 123410205101321624xxUxxx 12341122xxxx 123123142521831520100123210014.351 0024(14,18,20)(14,10,72),(14,10,72)(1,2,3).TTTTxxxALULyyUxx 例3：用LU三角分解法解解：用分解计算公式得求解 高斯主元素消去法高斯主元素消去法()()00kkkkkkaa在高斯法消元过程中可能出现的情况，这时消去法将无法进行；即使主元素但很小，用其作除数，也会导致其他元素数量级的严重增长和舍入误差的扩散。例1 在只取小数点后四位数字的条件下，用Gauss顺序消去法解方程组 12120.00033.00002.00011xxxx解：2111100000.00033l1220.00033.00002.000199996666xxx由第二个方程可求出 266660.66679999x 代入第一个方程可求出 12.0001 0.6667 3/0.00030 x 120.3333,0.6667xx而方程组的准确解为 设,1,2iiixxi由第一个方程知 因此 11220.00033.00002.0001xx120.00033.00000120.00033.00002.0001xx而 于是，有 41210小主元素是算法不稳定的主要原因。123*0.0012.0003.0001.0001.0003.7124.6232.0002.0001.0725.6433.000(0.4904,0.05104,0.3675)Txxxx 例：3阶方程组四位有效数字精确解为 解：1 高斯消去法321.9970.0012.0003.0001.00002004300510020400160062003l0.0012.0003.0001.0000200430051002005.0002.0000.4000.099890.4000 x 2131100020000.0012.0003.0001.000|1.0003.7124.6232.0002.0001.0725.643 3.0 00 llA b 2（）交换行，避免绝对值小的主元（列主元作除数。素法）21310.50000.00050.0012.0003.0001.000|1.0003.7124.6232.0001.0725.6433.0001.0725.6433.0001.0003.7124.6232.0000.0012.0003.0001.002.002.00000llA b 2.000 1.0725.6433.00003.1761.8010.500001.8680.687(0.4900,0.05113,0.3678)Tx 320.62972.0005/3.17602.0001.0725.6433.00001.80150.502.00053.0028 1.00153.1760l .,det.1.det1 1,2,172 max.3.0,det0,4.5 (,kkkijiji kikki ni kkkji jAxbAmaxbknaaaikaajk 算法：（列主元素消去法）设消元结果冲掉乘数冲掉计算解冲掉常数项行列式值存放在对于做到第 步。.按列选主元素如果则计算停止。如果则转，否则换行：1,),detdetkkiknbb。15.:/(1,)(1)6.(,1,)(1,)7.detdet.8./;()/(1,2,1).9.ikikikikkkikijijikkjiiikkkknnnnniiijiij imamaaiknmaam ai jknbbm biknabbabbaainn 计算乘数消元计算：回代求解：detdet.nna 在LU分解法中，若 时，计算无法 进行，或者 绝对值很小时，按分解公式 0iiu iiu计算时可能会引起舍入误差的增大，因此，与Gauss消去法一样，为了保证运算能顺利 进行以及方法的稳定性，三角分解一般采用 选列主元的技术，并称之为Crout分解。Gauss-Jordan消去法 3 2GaussJordanAn消去对角线下方和上方的元素，此方法称消去法。G-J方法将 约化为单位矩阵，计算解就在常数项得到，无需回代求解。计算量大约需次乘除法，要比高斯消去法大。G-J方法主要用途是求一个矩阵的逆矩阵。11232453 5 G-J.56AA例：用法求的逆矩阵123 100356001|2450102450105600112310 30nA I解：5/32001/301012/301/31101/32/1301/205/2203/203/21001/211/20111111.0013200331|00210nIACrammer法则 Gauss顺序消去法 Gauss-Jordan LU分解法 11!nnn321133nnn3232nO n313On运算量比较 3 矩阵的LU分解 矩阵的LU分解 对称矩阵的平方根法 改进的平方根法 解三对角方程组的追赶法 二、平方根法二、平方根法 工程实际计算中，线性方程组的系数矩阵常常具有对称正定性，即其各阶顺序主子式及全部特征值均大于零。矩阵的这一特性使它的三角分解也有更简单的形式，从而导出一些特殊的解法，如平方根法与改进的平方根法。,AL TALLL定理：设 是对称正定矩阵，则存在唯一的非奇异下三角阵使得且 的对角元素皆为正。证明证明1；证明证明2。定理证明（1）11221111112111211111,1,212 1(,1),nnnnnnnnnnnnuuuAuuALLUDdiag uuPD UuuuuUuuUPuuu证：因 对称正定，其各阶顺序主子式均大于零，故有其中 为单位下三角矩阵，为上三角阵。令则 为单位上三角阵。TTTTTALULDPAP DLAP DDPPPLLU故由分唯一性解的定理证明（2）1111110,/0(2,3,)(,(),)iiiiTnTnTTTTTuDuDDinDdiagDDPuuDD DAALDP