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

1、,第三章 线性代数方程组的数 值解法,3.1 引言 3.2 解线性方程组的消去法 3.3 解线性方程组的矩阵分解法 3.4 解线性方程组的迭代法,3.1 引言,给定一个线性方程组,求解向量 x。,第一类是直接法。即按求精确 解的方法运算求解。 第二类是迭代法。其思想是首先把线性方程组(3-1)等价变换为如下形式的方程组：,数值解法主要有两大类：,然后构造迭代格式,这称为一阶定常迭代格式，M 称为迭代矩阵。,3.2 解线性方程组的消去法,3.2.1 高斯消去法与高斯若当消去法,例1,第一步：先将方程（1）中未知数 的系数2 除（1）的两 边，得到下列方程组：,解：1、消元过程,再将第二个方程减去

2、第一个方程的4倍，第三个方程减去 第一个方程的2倍。,第二步：将方程 中第二个方程的两边除以 的系数4,将第三个方程减去第二个方程：,第三步：为了一致起见，将第三个方程中的 系数变为1，,2、回代过程：,下面我们来讨论一般的解n 阶方程组的高斯消去法，且 就矩阵的形式来介绍这种新的过程：,一、高斯消去法,高斯消去法： （1）消元过程： 对k=1,2, , n 依次计算,(2) 回代过程：,例3.1 试用高斯消去法求解线性方程组,消元过程为,解,即把原方程组等价约化为,据之回代解得,为了避免回代的计算，我们可在消元过程中直接把系数矩阵A约化为单位矩阵I，从而得到解，即,这一无回代的消去法称为高斯

3、-若当（Jordan）消去法,二、高斯-若当（Jordan）消去法,解,消元,消元,例 2 试用高斯-若当消去法求解例3.1的线性方程组。,因为,解,高斯-若当（Jordan）消去法 一般公式：,高斯约当消去法是一个具有消去过程而无回代过程的算法。 以上两种消去法都是沿系数矩阵的主对角线元素 进行的，即第k次消元是用经过前k-1次消元之后的系数阵位于（k,k)位置的元素作除数，这时的(k,k)位置上的元素可能为0或非常小，这就可能引起过程中断或溢出停机。,3.2.2 消去法的可行性和计算工作量,推论 若系数矩阵严格对角占优，即有,定理 3.2 求解 n 阶线性方程组 (3-1) 的高斯消去法的

4、乘除工作量约为 ，加减工作量约为 ；而高斯-若当消去法的乘除工作量约为 ，加减工作量约为 。,注意：高斯-若当消去法求解矩阵方程和求矩阵的逆矩阵,其中X是矩阵,3.2.3 选主元素的消去法,主元素的选取通常采用两种方法： 一种是全主元消去法；另一种是列主元消去法。,下面以例介绍选主元的算法思想,例 3.4 试用选主元消去法解线性方程组,（1）用全主元高斯消去法,回代解出：,还原得：,解,故得解为,（2）用全主元高斯-若当消去法,（3）用列主元高斯消去法,回代解得,3.3 解线性方程组的矩阵分解法,一、 非对称矩阵的三角分解法,解两个三角形方程组。,定理3.3,矩阵的Crout分解的计算公式,(

5、3-12),Crout分解的计算公式,Crout 分解的 计算公 式的记 忆方法,注：,例1. 试用克洛特分解法 解线性方程组,0,例3.5 试用克洛特分解法解线性方程组,解,3.3.3 对称正定矩阵的三角分解,定义 3.1 若n 阶方矩阵 A 具有性质 且对任何n 维向量 成立 ，则称 A 为对称正定矩阵。,定理3.4 若A 为对称正定矩阵，则 (1) A的k阶顺序主子式 (2)有且仅有一个单位下三角矩阵L和对角矩阵D 使得 （3-16） 这称为矩阵的乔里斯基（Cholesky）分解。 (3)有且仅有一个下三角矩阵 ，使 （3-17） 这称为分解矩阵的平方根法。,（1）首先由A 对称正定知,

6、且对任何k维非零向量,故 为 k 阶对称正定矩阵，所以,由惟一性得,证,把平方根法应用于解方程组，则把 Ax=b 化为等价方程,相应的求解公式为,把乔里斯基分解法应用于解方程组，则 Ax=b 化为等价方程,相应的求解公式为,由此可建立平方根法的递推计算公式如下：,注：,平方根法的递推计算记忆法,例3.8 试用平方根法求解对称线性方程组,解,由此，可先由上三角形线性方程组,再由下三角形线性方程组,类似地，由 得,从而可建立乔里斯基分解法的递推计算公式为,对于 依次计算,例 3.7 用乔里斯基分解法分解矩阵,解,由式(3-9),例3.9 试用乔里斯基分解法解线性方程组,解,3.4 解线性方程组的迭

7、代法,迭代法思想: (1)Ax=b ( 3-1),3.4.1 雅可比迭代法与高斯-塞德尔迭代法,约化便得,从而可建立迭代格式,对 （3-23）,以分量表示即,一、Jacob迭代法,则雅可比迭代格式（3-24）可用矩阵表示为,-雅可比迭代,例如,解：,-高斯-塞德尔迭代,用矩阵表示为,对雅可比迭代格式修改得,二、Gauss-Seidel迭代法,例3.10 分别用雅可比迭代法和高斯-塞德尔迭代法求解 线性方程组,解,相应的迭代公式为,雅可比迭代,高斯-塞德尔迭代,令 取四位小数迭代计算,由雅可比迭代得,由高斯-塞德尔迭代得,3.4.2 迭代法的收敛性,定理 3.5 若一阶定常迭代格式（3-26）的迭代矩阵 满足条件,则该迭代格式对任何初始向量 均收敛。,定理 3.7 若雅可比迭代法的迭代矩阵 满足条件（3-28）或（3-29），则雅可比迭代法与相应的高斯-塞德尔迭代法对任何初始向量 均收敛。,定理 3.8 一阶定常迭代格式 对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱半径小于1，即,这里 为 M 的特征值,定理 3.9 若线性方程组（3-1）的系数矩阵A对称正定，则相应的高斯-塞德尔迭代法必收敛。,3.4.3 迭代法的应用说明,(1) 若系数矩阵非严格对角