数值分析-北交大-王兵团-3 线性方程组解法

讲授：

大型线性方程组计算机求解的常用方法的构造和原理；

重点论述:

Jacobi迭代法、Seidel迭代法、Guass消元法及LU分解法的原理、构造、收敛性等。第三章线性方程组解法§3.2基本概念第3章线性方程组解法*线性方程组的行列式解法对于n

个方程的n元线性方程组其系数矩阵则方程组Ax=b

有唯一解如果|A|≠0，*线性方程组的解对于n

个方程的n元线性方程组直接法

用计算公式直接计算出线性方程组的解的方法。在数值计算中，迭代法

用迭代公式来求满足精度要求的近似解的方法。

迭代法是一种逐次逼近线性方程组解的方法。解线性方程组的方法有直接法和迭代法两大类。§3.3线性方程组的迭代解法第3章线性方程组解法一、基本思想

将线性方程组Ax=b等价变形为x=Bx+g,然后构造向量迭代公式二、构造原理1、Jacobi方法的构造模式2、Seidel方法的构造模式3、Sor方法的构造模式方法：

1）将

Jacobi

迭代法：等价变形不动点方程组2）写成迭代格式Jacobi迭代格式3）取定初始向量可逐次算出向量序列

Seldel迭代法Seidel迭代格式Seidel迭代并不能取代Jacobi迭代!

Sor法得到Sor法迭代格式Sor法是Seidel迭代法的推广!例：写出如下程组的3种迭代格式解：先写出不动点方程组：Jacobi迭代格式：Seidel迭代格式：Sor迭代格式：三、迭代分析及向量收敛1、三种迭代法的向量迭格式则有

解出向量x得不动点方程组由此得Jacobi迭代的向量迭代格式：记：（*）式可以写为：同理，有Seidel向量迭代格式：Sor法向量迭代格式：上面三种向量迭代格式可以写成一种：2、向量收敛定义3、范数定义及常用范数定义3.2设L是数域K上的一个线性空间，如果定义在L上的实值函数

P(x)满足:则称P(.)是L上的一个范数，称

P(x)为x的一个范数。比较线性运算定义：

数值分析中常用的线性空间

式中向量

数值分析中常用的范数

例如

数值分析中常用的范数

矩阵范数要满足如上四条！

对比一下向量范数。定义3.3矩阵A的算子范数为：例：证明范数不等式证明：（反证法）假设I+B不可逆，易知对应齐次方程组两边取范数，并利用范数定义矛盾！故I+B可逆。两边取范数，并利用算子范数定义

数值分析中常用的范数

F范数不是算子范数，其他3个是算子范数。例如

3、范数等价与向量极限

4、谱半径及其与范数的关系矩阵A的谱半径：定理3.3证明四、迭代法的收敛条件与误差估计1、收敛条件定理证明：必要性定理证明：充分性2、收敛的判别条件（充分条件）判别条件I判别条件II判别条件III定理3.7

Sor法收敛的必要条件是松弛因子

满足0<

<2证明定理3.8设矩阵B的某种矩阵范数

2、误差估计证明参照非线性方程求根定理的证明，将：绝对值换成范数、函数换成矩阵，注意范数关系的使用，例3.1用Jacobi迭代法解线性方程组解Jacobi迭代收敛！故所求近似解为准确解：例3.2：已知方程组1、写出Jacobi和Seidel迭代格式；2、判别两种迭代格式的收敛性。解：1、2、得特征值得特征值§3.4线性方程组的直接解法第3章线性方程组解法

直接方法描述

解线性方程组的直接法有Gauss消元法，LU分解法及一些特殊线性方程组的解法等，其中Gauss消元法是直接法的基础。本章的重点是在一般公式推导上，要注意学习和体会。一、Gauss消元法

1、基本思想

先将线性方程组通过消元方法化为同解的上三角方程组，然后从该三角方程组中按第n个方程、第n-1个方程、…、第1个方程的顺序，逐步回代求出线性方程组的解。

2、构造原理

Gauss消元法的求解过程分为两个:“消元”：把原方程组化为上三角方程组；“回代”：求上三角方程组的解。1）记原方程组为

Gauss消元法构造过程：消元：第i个方程变为方程组（1）变为计算公式：完成了第一步消元！对方程组（2）的后n-1元线性方程组做同样的处理：

Gauss消元法构造过程：方程组（2）变为：第二步消元2）Gauss消元公式系数计算公式：

顺序做了n-1次消元后，方程组（1）变为如下上三角方程组：3）回代

Gauss消元法构造过程：再从后向前依次解出：,计算公式为4）Gauss消元公式系数计算公式：5）

Gauss消元法计算公式3、分析1）Gauss消元法的计算量计算量3、分析2）Gauss消元法矩阵解释2）Gauss消元法矩阵解释第1步消元第n-1步消元后，有L是下三角阵，U是上三角阵。A=D-L-U?3）Gauss消元法可使用的条件4）Gauss消元法的改进缺点2：在使用Gauss消元法进行计算机求解时，人们发现有时求出的解是错误的。例：研究线性方程组的Gauss消元法求解结果，假设计算在4位浮点十进制数的计算机上求解。解：用Gauss消元法得用Gauss消元法求解得其准确解为可以接受。主元:消元法中用作分母的数;主方程:主元所在的方程。列主元消元法、全主元消元法例：用列主元与全主元方法解方程组解：1）列主元法解：2）全主元法回代得到解Gauss消元法例见书

1、基本思想二、LU分解法

2、构造原理

1）

Doolittle分解2）Grout分解3）

LDU分解都称为三角分解！1）由A=LU及矩阵乘积和相等概念，有

Doolittle分解法的构造过程：得出L的第一列和U的第一行元素！2）同理，有

Doolittle分解法的构造过程：Doolittle分解计算公式：

Doolittle分解算法

计算出Doolittle分解的L和U矩阵上述过程求解

的方法称为Doolittle分解方法或三角分解法。1)A可以进行Doolittle分解的条件定理1、

非奇异矩阵A的Doolittle分解是唯一的。定理2、

若A的各阶顺序主子式不为零

，则A有唯一的Doolittle分解。易知：能进行Gauss消元法就能做Doolittle分解。？3、分析3、分析2）Doolittle分解的紧凑格式例：用LU分解法求解线性方程组解：因为没有指定用哪种LU分解，这里使用Doolittle分解法做之。用紧凑格式计算。

1、基本思想三、特殊线性方程组解法

利用系数矩阵的特殊性消除无效的零元计算来构造求解公式以提高效率。

1）追赶法

三对角方程组

三对角矩阵带状矩阵带状矩阵的三角分解三对角矩阵的LU分解仿照Doolittle方法，有2）追赶法构造过程：2）追赶法构造过程：

追赶法求解公式为：用追赶法来求解三对角线性方程组，计算量只是5n-4，这比Gauss消元法的计算量要小很多。

追赶法算法用上述过程求解

的方法称为追赶法解法。§3.5线性方程组解对系数的敏感性第3章线性方程组解法

概念描述解对系数的敏感性是指方程中由于系数的变化（扰动）导致所求解的变化