解线性方程组的直接法.ppt

第二章 解线性方程组的直接法 §2.1 高斯消去法 线性代数方程组的求解问题： 各种各样的科学与工程问题往往最终都要归结为一个线性方程组的求解问题，例如结构分析、网络分析、大地测量、数据分析、最优化及非线性方程组和微分方程组数值解等，常遇到线性方程组的求解问题. 高斯消去法的思路：系数矩阵的消元和回代 通过系数矩阵 A 的 LU三角分解（高斯变换）转化为 较容易求解的三角形矩阵 二. 高斯-约当消去法 三. 高斯消去法的计算工作量 (略)教材34页 四. 消去法进行到底的条件 【定理2.1】 当系数矩阵的各阶顺序主子式不为零时,高斯消去法能进行到底. § 2.2 高斯主元消去法 选主元法的思路： 为减小方程组求解误差可通过置换 A 来选主元方法使 A 的 LU 三角分解没有太大的元素. 全选主元法 作 业 P70 习题 1 (1) , 8 重要的matlab函数 [L,U,P,Q]=lu(A) (LU分解，可返回四个参量)； cond(A, p) (条件数)，rcond(A) (条件数倒数)； A\ b (Ax=b的解，=inv(A)*b)； hilb(n) (n阶Hilbert矩阵)。 * 主要内容： 高斯消去法； 高斯主元消去法； 直接三角分解法； 解对称正定方程组的平方根法； 行列式和矩阵的求逆运算； 方程组的状态和条件数. 求解线性方程组的数值方法大体上可分为直接法和迭代法两大类，其中直接法是指在没有舍入误差的情况下经过有限次运算可求得精确解；而迭代法则是从一个初始向量出发按照一定的计算格式逐次逼近精确解. 解 第1步：将方程（2.1）乘上（-3/2）加到方程（2.2） 将方程（2.1）乘上（-1/2）加到方程（2.3） 则得到与原方程等价的方程组 （2.1） （2.3） （2.2） 　　高斯消去法是一个古老的求解线性方程组的方法，但由它改进得到的选主元的高斯消去法则是目前计算机上常用的解低阶稠密矩阵方程组的有效方法． 例1 用加减消 元法解方程组 一、高斯消去法 高斯消去法就是加减消元法, 将给定方程组通过 加减消元化为较容易求解的上三角形方程组. n 阶线性代数方程组的一般形式为 到此原方程组化为 (1) 到此原方程组化为 (n-1) 原方程组化为 以上为消元过程. (上三角方程组) (n) 回代求解公式 是回代过程. 高斯--约当消去法 就是将给定方程组通过加减消元化为对角形方程组的方法. 是无回代的消去法,所进行的乘除运算次数比高斯消去法(有回代的消去法)多. 解 第1步：将方程（2.1）乘上（-3/2）加到方程（2.2） 将方程（2.1）乘上（-1/2）加到方程（2.3） 则得到与原方程等价的方程组 （2.1） （2.3） （2.2） 用高斯--约当消去法解方程组 （2.4） （2.5） （2.6） 例2 第2 步：消去（2.4）和（2.6）式中未知数 x2 ，得到等价的方程组 不用回代，即可求得原方程组的解为： 第3 步：消去（2.7）和（2.8）式中未知数 x3 ，得等价的对角形方程组 （2.7） （2.8） 高斯—约当消去法 消元过程中总的乘除法次数约为 算法的时间复杂度: 高斯消去法 消元和回代过程中 总的乘除法次数约为 总的加减法次数约为 　高斯消去法解 20 阶方程组大约需做 3060 次乘除法. 克莱姆（Cramer）法则大约需做 5×1019 次乘法． 若用矩阵来描述消去法的约化过程，即为 　　高斯消去法解方程组的基本思想是用矩阵的初等变换将系数矩阵约化为具有简单形式的矩阵（上三角矩阵，单位矩阵等），从而容易求解. (略)教材35页 算法的稳定性: 当 |A(k,k)| =0 时，运算就会中断； 当 |A(k,k)| ? 0 但很小时，损失精度和计算溢出. 主元：消元过程中的 若 ,则可利用高斯消元法. 例3 设有方程组 解 精确解为 [方法1] 得到 　　回代求解 ．对于用具有舍入的3位浮点数进行运算，这是一个很好的计算结果． [方法2] 用具有行交换的高斯消去法(避免小主元)．