数值分析PPT.PPTVIP

* * 3.2.2高斯消去法 利用上面回代过程求解， 利用矩阵初等变换将其转为上三角矩阵。 举例,求解方程组： 12x1－3x2+3x3=15 18x1－3x2+ x3=15 －x1－2x2+ x3=6 可解得x1=1 x2=2 x3=3 高斯消去法一般过程： 记增广矩阵 其中 第一步消元：将 第一列对角线一下元素消为0. 设 ,将 的第1行乘上 再加到第i行上得: 其中 上式可写成两矩阵相乘 其中 ：下三角矩阵 如此重复操作可得： 其中 为上三角矩阵， 为下三角矩阵,具体为: 可将 合在一起，记 可得 其中 , 例如: 可计算求出 下三角矩阵 原矩阵可分解为下三角和上三角矩阵之积. 此过程为消元过程. 接下来分析计算量: 考虑第k步消元 k=1,2,…，n-1（即共n-1次消元） 乘除法： ①计算 （i=k+1，… ，n） 需（n-k）次 ②计算 （i，j=k+1，… ，n） 需 次 ③计算 （i=k+1，…,n） 需（n-k）次 第k步需 加减法 只在②和③中用到 第k步 需 总共需 加法总共需: 将消元和回代过程合在一起，计算量分别为 乘除法： 加减法： 高斯消去法需注意： 若 =0, (k=1.2 …n) 可通过行交换方式，与第 k 行下面的行交换，再消元；但并不是所有系数矩阵都可使用高斯消去法。 另一方面还需考虑误差传播的影响: 3.2.3 列主元高斯消去法 要求 . 定理: (k=1.2 …n) 的充要条件是A的顺序 主子式不为0, 即 第k 步消元时，需将 的第k行 再加到第i行(i=k+1,…n) 若第k行元素 , … 有误差 则误差传播为 ∴若 较小，则 较大，误差传播较大. ∴应使 取较大值，可减小误差传播。 解决方法：（列主消元法）在第k步消元之前，选出第k列中对角线以下元素绝对值较大者的这一行与第k行交换再消元. 例： 作业：使用列主元法求解 3.2.4 追赶法 对一些特殊方程组（样条函数构造，微分方程数值求解），对角占优方程组，三对角方程组。 其中系数ai, ,bi ,ci需满足一定的条件（确保能使用高斯消去法） 在使用高斯消去法计算量可降低（因为每一步消元只消去一个元素，回代过程计算量也相应减少） 消元时：记 , , 则： ， ， 其增广矩阵可表示为： 其回代过程可写成： , ， 计算量分析： 乘除法：第i步消元时计算： 1次 1次 1次 共有n-1步， 共3（n-1）次 回代时： 共 次 总共 次， 加减法：第i步消元： 2次， 1次 ，∴所以共 回代：(n-1)次 总共：2n-2+n-1=3n-3次 共3次 1次 3.3 矩阵的直接分解（三角分解）法 3.3.1矩阵的紧凑格式 U L:下三角矩阵 ；U:上三角矩阵 高斯法的消元过程：利用矩阵初等变换. 这里利用A的自身元素之间关系和递归关系（利用矩阵相乘），求解L和U的元素，减少计算量 其每个元素可看成： L的对应行元素*U的对应列元素： A=L 利用矩阵乘法：先看第一行 a1j = u1j (j =1﹑2﹑3﹑…﹑n) ∴ u1j = a1j (j =1﹑2﹑3﹑…﹑n) 再看第一列： ai1 = li1 * u11 (i =2﹑3﹑…﹑n) (i =2﹑3﹑…﹑n) ∴ 第一行和第一列可由ai1 求出 对第k行，有: (j =k﹑k+1﹑…﹑n) ∴ (例如a23 ) 对第k列，有： (i =k+1﹑k+2﹑…﹑n) ∴ (i =k+1﹑k+2﹑…﹑n) ∴ 可由aij 求出。 (例如a32 ) 对增广矩阵： ，b的计算与 一样, 可合在一起计算，即： (j=n+1) ∴ (j =k﹑k+1﹑…﹑n+1) (3). U中的ukj = akj－ (ukj左边L的同行元素lkq *上面U的同列元素uqj) (4). L中的lik =[ aik- ( lik左边同行元素*上面u同列元素)] /对角元素ukk 具体过程如下图所示： 具体的计算步骤为： (1). 由u1j = a1j 得到u的第1行元素与A的第1行相同. (2). 由