计算方法课件：第2章-线性方程组的数值解法

1、第二章 线性方程组的数值解法,2.1 消去法 2.2 矩阵分解法 2.3 向量与矩阵范数 2.4 经典迭代法,给定一个线性方程组,A为系数矩阵,b为右端向量，x为需求解的未知向量。,直接法：按求精确解的方法运算求解， 有Gauss消去法及修正（矩阵分解法）等。 迭代法：给一个初始近似解,按一定法则逐步求更精确的近似解的过程; 有经典与现代迭代法.,解线性方程组数值解法有两类：,2.1 Gauss消去法 (Elimination Method),2.1.1 三角形方程组的解法,三角形方程组是最容易求解的,而Gauss消去法是把一般线性方程组化成两个三角形方程组来求解的。现在考虑上三角形方程组,(

2、2.1.1),2.1.1 三角形方程组的解法,由于主对角元 , 所以（2.1.1）的解是唯一的。由第i个方程得,(2.1.2),同理对于下三角形方程组,(2.1.3),(2.1.4),2.1.2 Gauss消去法,初始增广矩阵为,(2.1.6),第一步消元过程: 假设 , 把第1列第2-n个元素变成0.,(2.1.7),计算公式为,第2步消元过程: 假设 , 把第2列的后n-2个元素变成0.,第k步消元过程：假设 前面k-1步消元得到如下形式,计算公式 (2.1.10)与(2.1.11),第n-1步消元过程完得到：,经过上述消元过程后，原方程组化为一个和它完全等价的上三角形方程组，用公式（2.

3、1.2）得,例2.1 试用高斯消去法求解线性方程组,消元过程为,解,即把原方程组等价约化为,通过回代解得,2.1.3 列主元Gauss消去法,在消元过程中，常出现主对角元绝对值较小或为0的情况，克服这一困难的办法是列主元消去法。 列主元消去法的思想：每次消元过程先在当前变换的列元素中选绝对值最大的为主元，并根据需要交换相关的行，然后再消元。,例 2.2 试用列主元消去法解线性方程组,解. 用列主元高斯消去法,回代解得,2.2 矩阵分解法,2.2.1、 三角分解法,对于给定的线性方程组,矩阵Crout分解法的基本思想是：,（1） 分解,(2). 化成两个三角方程组,用2.1.1节公式先求y后解x

4、.,设已求出U的第1到k-1行于L到第1到k-1列元素,比较两 边第k列与第k行的元素,用待定系数法,通过比较A=LU的两端得求解公式. 比较等式两边第1列和第1行元素得,比较第k列, j=k,k+1,n,比较第k行, i=k+1,n,再解Ux = y,先解Ly = b,例 2.4 试用Crout分解法解线性方程组,解,2.2.2 对称正定矩阵分解法,若A 为对称正定矩阵，则容易证明存在下三角矩阵L，使得 。这称为矩阵的乔里斯基（Cholesky）分解。,同样存在一个单位下三角矩阵L和对角矩阵D 使得,推导Cholesky分解法的计算公式,由此得递推计算公式如下：j =1,2,n,应用于解方程

5、组，则把 Ax=b 化为等价方程,相应的求解公式为,为了去掉平方根运算，考虑 分解得,从而可建立分解法的递推计算公式，对于 j=1,2,n 依次计算,把分解法应用于解方程组，则 Ax=b 化为等价方程,相应的求解公式为,例 2.5 试用 分解法求对称线性方程组,解,由此，可先由上三角形线性方程组,再由下三角形线性方程组,例 试用Cholesky分解法求对称线性方程组,解,由此，可先由上三角形线性方程组,再由下三角形线性方程组,2.3 向量范数与矩阵范数,定义2.1 从向量到实数的实值函数满足下列3个条件称为向量范数：,三个常用向量范数：,定义2.2 设|是Rn上向量范数， A为Rnn中的矩阵，

6、 称 矩阵范数。,三个常用矩阵范数为,三个常用矩阵范数的计算公式为,例2.6 设,求常用的向量与矩阵范数。 解：,2.4 经典迭代法(Classic Iterative Methods),迭代法思想：,2.4.1 Jacobi迭代法 (以对角元为分母),将上述过程一般化,建立迭代格式,将初值 代入后迭代得,以分量表示方程组得,对角元对应的量 移到左边，其它 量在右边便得 ：,从而可建立迭代格式,雅可比迭代格式（2.4.2）可用矩阵表示为,迭代法的矩阵表示,2.4.2、Guass-Seidali迭代法(及时更新计算值),将例2.7中对Jacobi迭代格式修改得,将上述过程一般化,用矩阵表示为,例

7、 2.7与2.8 用Jacobi迭代法和Gauss-Seidel迭代法求解 线性方程组,解,Gauss-Seidel迭代,Jacobi迭代,令 取四位小数迭代计算,由Jacobi迭代得,由Gauss-Seidel迭代得,相应的迭代公式为,2.4.3 一般 迭代法的收敛性,定义3.2 设 , 其精确解为 x*,相应的迭代格式为,如果存在某个向量范数使得,则称由（2.4.9）确立的迭代法收敛, 否则称发散.,定理 2.1 设方程组Ax=b的精确解为x*。如果存在一个矩阵范数使得（2.4.9）中的迭代矩阵满足条件,则由(2.4.9)确立的迭代任何初始向量均收敛。且,证,定理得证。,迭代式相减取范数得,进一步递推得,则由(2.4.9)确立的迭代法收敛。,推论 2.1 若(2.4.9)迭代矩阵 满足条件,推论 2.2 若Jacobi（Gauss-Seidel）迭代法的迭代矩阵 满足条件,利用定理2.1很容易