求解线方程组的数值解法市公开课一等奖百校联赛特等奖课件

第三章求解线性方程组数值解法泰山学院信息科学技术系第1页解线性方程组两类方法:直接法:经过有限次运算后可求得方程组准确解方法(不计舍入误差!)迭代法：从解某个近似值出发，经过结构一个无穷序列去迫近准确解方法(普通有限步内得不到准确解)第2页§3.1解线性方程组直接法

一、高斯消去法思绪首先将方程组Ax=b

化为上三角方程组，此过程称为消去过程，再求解上三角方程组，此过程称为回代过程.§3.1.1高斯消去法和选主元高斯消去法第3页将增广矩阵第i行+li1

第1行，得到：消去过程：第一步：设，计算因子其中第4页第k步：设，计算因子且计算共进行n

1步，得到第5页定理：若A全部次序主子式均不为0，则高斯消去法能次序进行消元，得到唯一解。回代过程：第6页二、选主元消去法为防止这种情况发生,可经过交换方程次序，选取绝对值大元素作主元.基于这种思想导出了主元素法在高斯消去法消去过程中可能出现情况，这时高斯消去法将无法进行；即使主原因但很小，其作除数，也会造成其它元素数量级严重增加和舍误差扩散第7页

列主元消去法在第k步消元前，在系数矩阵第k列对角线以下元素中找出绝对值最大元。若p≠k，交换第k个与第p个方程后，再继续消去计算.

这种方法称为列主元Gauss消去法。

列主元Gauss消去法确保了｜lik｜≤1(i=k+1,k+2,…，n).第8页

全主元消去法在第k步消去前，在系数矩阵右下角n-k+1阶主子阵中，选绝对值最大元素作为主元素。(1)

Ifp

k

then交换第k行与第p行;

Ifq

k

then交换第k列与第q列;(2)消元注：列交换改变了xi

次序，须统计交换次序，解完后再换回来。第9页

运算量

（AmountofComputation）（1）用克莱姆（Cramer）法则求解n阶线性方程组

每个行列式由n!项相加，而每项包含了n个因子相乘，乘法运算次数为(n-1)n!次.

仅考虑乘(除)法运算,计算解向量包含计算n+1个行列式和n次除法运算,乘(除)法运算次数N=(n+1)(n-1)n!+n.第10页（2）

高斯消去法:

在第1个消去步，计算li1(i=2,3，…，n)，有n-1次除法运算.使aij(1)变为aij(2)

以及使bi(1)变为bi(2)有n(n-1)次乘法运算和n(n-1)次加(减)法运算.

在第k个消去步，有n-k次除法运算、(n-k+1)(n-k)次乘法运算和相同加(减)法运算.首先统计乘法运算总次数.将每个消去步乘法运算次数相加，有n(n-1)+(n-1)(n-2)+…+3.2+2.1=n(n-1)(n+1)/3加(减)法运算次数总计也为n(n-1)(n+1)/3.除法运算总次数为n+(n-1)+…+1=n(n-1)/2第11页回代过程计算除法运算次数为n次.乘法运算和加法运算总次数都为n+(n-1)+…+1=n(n-1)/2次Gauss消去法除法运算次数为:n(n-1)/2+n=n(n+1)/2，乘法运算次数为:n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6，加(减)法运算次数为:n(n-1)(2n+5)/6通常也说Gauss消去法运算次数与n3同阶，记为O(n3)第12页全主远消去法:比高斯消去法多出比较，确保稳定，但费时。

列主元消去法:

比高斯消去法只多出比较，略省时。第13页§2.1.2

三角分解法

高斯消元法矩阵形式

每一步消去过程相当于左乘初等变换矩阵Lk第14页第15页A

LU

分解(LUfactorization)第16页定理2.1.4：若A全部次序主子式均不为0，则A

LU

分解唯一（其中L

为单位下三角阵）。证实：由§1中定理可知，LU分解存在。下面证实唯一性。若不唯一，则可设A=L1U1=L2U2，推出上三角矩阵对角线上为1下三角矩阵

注：（1）L

为单位下三角阵而U

为普通上三角阵分解称为Doolittle

分解（2）L

为普通下三角阵而U

为单位上三角阵分解称为Crout分解。

第17页

Doolittle分解法：经过比较法直接导出L和

U计算公式。思绪第18页普通计算公式计算量与Gauss消去法同.第19页LU分解求解线性方程组第20页第21页§2.1.4求解正定方程组Cholesky方法回顾：对称正定阵A几个主要性质（1）A1

亦对称正定，且aii>0（2）A

次序主子阵

Ak

亦对称正定（3）A

特征值

i

>0

（4）A

全部次序主子式

det(Ak

)>0第22页定理2.1.6设矩阵A对称正定，则存在唯一对角元全为正下三角阵G

使得

A＝GGT计算格式为第23页§2.1.5求解三对角方程组追赶法定理：若A

为对角占优三对角阵，且满足