第2章-线性方程组的数值解法.ppt

《第2章-线性方程组的数值解法.ppt》由会员分享，可在线阅读，更多相关《第2章-线性方程组的数值解法.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 线性方程组的数值解法线性方程组的数值解法 2.1 消去法消去法2.2 矩阵分解法矩阵分解法2.3 向量与矩阵范数向量与矩阵范数2.4 经典迭代法经典迭代法给定一个线性方程组给定一个线性方程组A A为系数矩阵为系数矩阵,b,b为右端向量，为右端向量，x x为需为需求解的未知向量。求解的未知向量。直接法直接法：按求精确解的方法运算求解，：按求精确解的方法运算求解，有有GaussGauss消去法及修正（矩阵分解法）等。消去法及修正（矩阵分解法）等。迭代法迭代法：给一个初始近似解：给一个初始近似解,按一定法则按一定法则逐步求更精确的近似解的过程逐步求更精确的近似解的过程;有经典与有经典与

2、现代迭代法现代迭代法.解线性方程组数值解法有两类：解线性方程组数值解法有两类：2.1 Gauss2.1 Gauss消去法消去法 (Elimination Method)2.1.1 2.1.1 三角形方程组的解法三角形方程组的解法 三角形方程组是最容易求解的三角形方程组是最容易求解的,而而GaussGauss消去法消去法是把一般线性方程组化成两个三角形方程组来是把一般线性方程组化成两个三角形方程组来求解的。现在考虑上三角形方程组求解的。现在考虑上三角形方程组(2.1.1)(2.1.1)2.1.1 2.1.1 三角形方程组的解法三角形方程组的解法 由于主对角元由于主对角元 ,所以所以（2.1.12

3、.1.1）的解是唯一的。由第）的解是唯一的。由第i i个方程得个方程得(2.1.2)(2.1.2)同理对于下三角形方程组同理对于下三角形方程组 (2.1.3)(2.1.3)(2.1.4)(2.1.4)2.1.2 Gauss2.1.2 Gauss消去法消去法初始增广矩阵为初始增广矩阵为(2.1.6)第一步消元过程第一步消元过程:假设假设 ,把第把第1 1列列第第2-n2-n个元素变成个元素变成0 0.(2.1.7)计算公式为计算公式为第第2 2步消元过程步消元过程:假设假设 ,把第把第2 2列的后列的后n-2n-2个元素变成个元素变成0 0.第第k k步消元过程步消元过程：假设：假设 前面前面k

4、-1k-1步消元得到如下形式步消元得到如下形式计算公式计算公式 (2.1.10)(2.1.10)与与(2.1.11)(2.1.11)第第n-1n-1步消元过程完得到步消元过程完得到：经过上述消元过程后，原方程组化为一个和它完全等价的经过上述消元过程后，原方程组化为一个和它完全等价的上三角形方程组，用公式（上三角形方程组，用公式（2.1.22.1.2）得）得 例例2.1 2.1 试用高斯消去法求解线性方程组试用高斯消去法求解线性方程组 消元过程为消元过程为 解解即把原方程组等价约化为即把原方程组等价约化为 通过回代解得通过回代解得2.1.3 2.1.3 列主元列主元GaussGauss消去法消去

5、法 在消元过程中，常出现主对角元绝对值较小或为在消元过程中，常出现主对角元绝对值较小或为0 0的情况，克服这的情况，克服这一困难的办法是一困难的办法是列主元消去法列主元消去法。列主元消去法的思想：每次消元过程先在当前变换的列元素中选绝列主元消去法的思想：每次消元过程先在当前变换的列元素中选绝对值最大的为主元，并根据需要交换相关的行，然后再消元。对值最大的为主元，并根据需要交换相关的行，然后再消元。例例 2.2 2.2 试用列主元消去法解线性方程组试用列主元消去法解线性方程组 解解.用列主元高斯消去法用列主元高斯消去法 回代解得回代解得 2.2 2.2 矩阵分解法矩阵分解法 2.2.12.2.1

6、、三角分解法三角分解法 对于给定的线性方程组对于给定的线性方程组 矩阵矩阵Crout分解法的基本思想是分解法的基本思想是：（1 1）分解分解可逆下三角矩阵可逆下三角矩阵可逆单位上三角矩阵可逆单位上三角矩阵(2).(2).化成两个三角方程组化成两个三角方程组用用2.1.12.1.1节公式先求节公式先求y y后解后解x.x.设已求出设已求出U的第的第1到到k-1行于行于L到第到第1到到k-1列元素列元素,比较两比较两边第边第k列与第列与第k行的元素行的元素用待定系数法用待定系数法,通过比较通过比较A=LUA=LU的两端得求解公式的两端得求解公式.比较等式两边第比较等式两边第1 1列和第列和第1 1

7、行元素得行元素得比较第比较第k k列列,j=k,k+1,n,j=k,k+1,n比较第比较第k k行行,i=k+1,n,i=k+1,n再解再解Ux=y先解先解Ly=b 例例 2.4 2.4 试用试用CroutCrout分解法解线性方程组分解法解线性方程组 解解 2.2.2 对称正定矩阵分解法对称正定矩阵分解法 若若A A 为对称正定矩阵，则容易证明存在下三角为对称正定矩阵，则容易证明存在下三角矩阵矩阵L L，使得，使得 。这称为矩阵的乔里斯。这称为矩阵的乔里斯基（基（CholeskyCholesky）分解。）分解。同样存在一个单位下三角矩阵同样存在一个单位下三角矩阵L和对角矩阵和对角矩阵D 使得

8、使得 推导推导Cholesky分解法的计算公式分解法的计算公式 由此得递推计算公式如下：由此得递推计算公式如下：j=1,2,n 应用于解方程组，则把应用于解方程组，则把 Ax=b 化为等价方程化为等价方程 相应的求解公式为相应的求解公式为 为了去掉平方根运算，考虑为了去掉平方根运算，考虑 分解得分解得 从而可建立分解法的递推计算公式，从而可建立分解法的递推计算公式，对于对于 j=1,2,n 依次计算依次计算把分解法应用于解方程组，则把分解法应用于解方程组，则 Ax=b 化为等价方程化为等价方程 相应的求解公式为相应的求解公式为 例例 2.5 试用试用 分解法求对称线性方程组分解法求对称线性方程

9、组 解解由此，可先由上三角形线性方程组由此，可先由上三角形线性方程组 再由下三角形线性方程组再由下三角形线性方程组例例 试用试用CholeskyCholesky分解法求对称线性方程组分解法求对称线性方程组 解解由此，可先由上三角形线性方程组由此，可先由上三角形线性方程组 再由下三角形线性方程组再由下三角形线性方程组2.3 2.3 向量范数与矩阵范数向量范数与矩阵范数定义定义2.12.1 从向量到实数的实值函数满足下列从向量到实数的实值函数满足下列3 3个条件称为个条件称为向量范数向量范数：三个常用向量范数：三个常用向量范数：定义定义2.22.2 设设|是是Rn上向量范数，上向量范数，A为为Rn

10、n中的矩阵，中的矩阵，称称 矩阵范数矩阵范数。三个常用矩阵范数为三个常用矩阵范数为三个常用矩阵范数的计算公式为三个常用矩阵范数的计算公式为例例2.6 2.6 设设 求常用的向量与矩阵范数。求常用的向量与矩阵范数。解：解：2.4 2.4 经典迭代法经典迭代法(Classic Iterative Methods)迭代法思想：迭代法思想：2.4.1 2.4.1 JacobiJacobi迭代法迭代法 (以对角元为分母以对角元为分母)将上述过程一般化将上述过程一般化建立迭代格式建立迭代格式将初值将初值 代代入后迭代得入后迭代得以分量表示方程组得以分量表示方程组得 对角元对应的量对角元对应的量移到左边，其

11、它移到左边，其它量在右边量在右边便得便得：Jacobi迭代迭代 从而可建立迭代格式从而可建立迭代格式雅可比迭代格式（雅可比迭代格式（2.4.22.4.2）可用矩阵表示为）可用矩阵表示为 MJf J迭代法的矩阵表示迭代法的矩阵表示 2.4.2、Guass-SeidaliGuass-Seidali迭代法迭代法(及时更新计算值及时更新计算值)将例将例2.7中对中对Jacobi迭代格式修改得迭代格式修改得将上述过程一般化将上述过程一般化用矩阵表示为用矩阵表示为 Gauss-Seidel迭代迭代 f GMG例例 2.7与与2.8 用用JacobiJacobi迭代法和迭代法和Gauss-SeidelGau

12、ss-Seidel迭代法求解迭代法求解线性方程组线性方程组 解解Gauss-Seidel迭代迭代Jacobi迭代迭代令令 取四位小数迭代计算取四位小数迭代计算 由由Jacobi迭代得迭代得 由由Gauss-SeidelGauss-Seidel迭代得迭代得 相应的迭代公式相应的迭代公式为为 2.4.3 一般一般 迭代法的收敛性迭代法的收敛性 定义定义3.2 3.2 设设 ,其精确解为其精确解为 x*,相应的迭代格式为相应的迭代格式为 如果存在某个向量范数使得如果存在某个向量范数使得则称由（则称由（2.4.92.4.9）确立的迭代法收敛）确立的迭代法收敛,否则称发散否则称发散.定理定理 2.12.

13、1 设方程组设方程组Ax=b的精确解为的精确解为x*。如果存在一。如果存在一个矩阵范数使得（个矩阵范数使得（2.4.92.4.9）中的迭代矩阵满足条件）中的迭代矩阵满足条件 则由则由(2.4.9)(2.4.9)确立的迭代任何初始向量均收敛确立的迭代任何初始向量均收敛。且。且 证证 定理得证。定理得证。迭代式相减取范数得迭代式相减取范数得 进一步递推得进一步递推得则由则由(2.4.9)(2.4.9)确立的迭代法收敛确立的迭代法收敛。推论推论 2.12.1 若若(2.4.9)(2.4.9)迭代矩阵迭代矩阵 满足条件满足条件推论推论 2.2 2.2 若若JacobiJacobi（Gauss-SeidelGauss-Seidel）迭代法的迭代矩阵）迭代法的迭代矩阵 满足条件满足条件利用定理利用定理2.1很容易判别迭代法的收敛性。以常用矩很容易判别迭代法的收敛性。以常用矩阵范数为例，有下列结论。阵范数为例，有下列结论。则则JacobiJacobi（Gauss-SeidelGauss-Seidel）迭代法对任何初始向量均收敛。）迭代法对任何初始向量均收敛。定理定理 2.22.2 迭代格式迭代格式 确定的迭代法确定的迭代法 对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱半径小于半径小于1 1，即，即