第2章解线性方程组的直接法

第2章解线性方程组的直接法2.1GAUSS消元法2.2改进平方根法2.3追赶法2.4LU分解法2.5直接法的稳定性分析2.1GAUSS消元法特点:矩阵的初等变换(是对中学代数中加减消元法、代入消元法的综合利用和升华)2.1.1基本GAUSS消元法问题：求解n阶线性方程组Ax=b的方法?解法：消元法(分2步)1.消元(1)目的：得到系数矩阵为上三角矩阵的方程组(2)方法：加减消元法(3)过程：利用aii消aji(j=i+1,…,n)，其余对应元素和bi作相应变动。2.1GAUSS消元法(4)计算公式推导：假设已进行了i-1轮消元，方程组Ax=b已变成：2.1GAUSS消元法相应要计算和变动的矩阵元素为：2.1GAUSS消元法2.回代求解xi：2.1GAUSS消元法2.1.2基本GAUSS消元法的计算实例[例1-例4]用GAUSS消元法求解方程组2.1GAUSS消元法2.1.3GAUSS列主元法方法要点在GAUSS消元法基础上，第i轮消元前，先选出列主元素，并将列主元素所在行与第i行进行交换。[列主元素]在GAUSS消元法第i轮消元前，中绝对值最大的元素称为列主元素，记为：2.1GAUSS消元法[求解过程]1.消元（找列主元素

交换

消元）(1)确定列主元素所在行(记行号=p)。确定的方法--按列主元素的定义。若列主元素近似为0，则表示选不出。(2)将列主元素所在的第p行与第i行元素交换(3)消元2.1GAUSS消元法2.回代求解xi：2.1GAUSS消元法2.1.4GAUSS列主元法的计算量1.消元过程的计算量(1)找列主元素：比较和绝对值计算(2)交换2行的次数(3)除法的次数：(4)乘法和减法的次数：2.回代过程的计算量除法次数乘法、加法、减法的次数：2.1GAUSS消元法2.1.5GAUSS列主元法的计算步骤1.输入2.输出3.计算：(1)消元，(2)回代2.1.6GAUSS列主元法的计算实例[例]求解方程组2.1GAUSS消元法2.1.7GAUSS全主元素法[全主元素]在GAUSS消元法的第i轮消元前，从子矩阵Ain中按绝对值最大的原则所找到的元素称为全主元素。[全主元消元法]找全主元素

作列和行的交换

消元

回代2.4LU分解法从GAUSS消元法可知，系数矩阵A消元后，形成了一个上三角矩阵和一个下三角矩阵，因此可重点研究系数矩阵A的分解方法。LU分解法：2.4.1LU分解法的算法推导对线性方程组Ax=b，令A=LU，其中2.4LU分解法依据的原理：矩阵的乘积法则2.4LU分解法LU分解公式(计算顺序)的推导：2.4LU分解法2.4.2LU分解法的求解公式由Ax=b及A=LU，有LUx=b

;

令Ux=y，有

Ly=b

,可解得：再由Ux=y可解得：2.4LU分解法2.4.3LU分解法的计算步骤1.输入;2.输出;3.计算过程：作LU分解，计算yi，计算xi2.4.4LU分解法的计算实例[例1]对矩阵A作LU分解[例2]用LU分解法求线性方程组2.2改进平方根法适用情况：系数矩阵A非奇异、是正定矩阵2.2.1正定矩阵的定义和性质正定矩阵的定义设A∈Rn×n，若有：

(1)AT=A,(2)对任意x∈Rn(x≠0)都有xTAx>0则称A是正定对称矩阵。正定矩阵的性质(简记:二个“正定”，三个“>0”)A的各阶主子矩阵也是正定对称矩阵(正定)A非奇异，且A-1也是正定对称矩阵(正定)A的对角线元素aii>0(>0)A的所有特征值>0(>0)A的各阶主子式>0(>0)2.2改进平方根法2.2.2改进平方根法的算式推导方法要点:对矩阵A作A=LDLT分解，再求解算法组成:1.三角分解：A=LDLT2.2改进平方根法[计算顺序的推导]2.2改进平方根法

[计算公式的推导]2.2改进平方根法

[计算公式的推导]2.2改进平方根法2.求解:(1)令Ux=y，

则有Ly=b，可得：(2)令LTx=z，

则有Dz=y，可得：(3)再解LTx=z，可得：2.2改进平方根法2.2.3改进平方根法的计算步骤P21—22页2.2.4改进平方根法的计算实例[例]求解下面线性方程组2.2改进平方根法2.2.5改进平方根法的计算量三角分解的计算量Q1+求解Q2=n3/62.2.6变带宽压缩存储改进平方根法2.2.9追赶法适用情况：系数矩阵A是三对角矩阵[三对角矩阵]只有主对角线和两条次对角线元素不为0的n阶矩阵。2.2.9追赶法1、追赶法的三角分解(Crout分解)[定理]若A是三对角矩阵，且满足：

(1)|b1|>|c1|，|bn|>|cn|(2)|bi|≥|ai|+|ci|,i=2,3,…,n-1则A非奇异，且A可作Crout分解。2.2.9追赶法[三角分解(Crout分解)]2.2.9追赶法按矩阵的乘积法则有：2.2.9追赶法2、方程组Ax=d的求解：(1)令Qx=y，于是有：Py=d，则(2)由Qx=y有：2.2.9追赶法3、追赶法的计算举例[例]求解2.3范数简介引入范数的目的是什么？稳定性分析什么是稳定性分析？扰动对解的影响（或误差的传递和放大问题）2.3范数简介稳定性分析的内容：给系数矩阵A一个小扰动(A+△A)，讨论其对解的影响；给右端项b一个小扰动(b+△b)，讨论其对解的影响。稳定性分析的手段和方法：范数：一个与向量、矩阵相关但又能比较大小的数学量。范数符号：2.3范数简介2.3.1向量范数的定义对任意向量x∈Rn，定义一个实值函数，记为，当满足下列3个条件时：则称是向量x的范数。2.3范数简介2.3.2常用向量范数2.3范数简介2.3.3向量范数的性质2.3范数简介2.3范数简介2.3.4矩阵范数的定义讨论Ax与x之间的关系2.3范数简介矩阵范数的定义2.5直接法的稳定性分析2.3.5矩阵范数的性质2.5直接法的稳定性分析常用的矩阵范数2.5直接法的稳定性分析矩阵的谱半径及定理2.5直接法的稳定性分析2.5直接法的稳定性分析2.4直接法的稳定性分析2.4.1常见稳定性分析数据的测试误差、舍入误差（扰动）等对解均有影响。[示例]2.4直接法的稳定性分析1.右端项扰动对解的影响2.4直接法的稳定性分析2.系数矩阵A的扰动对解的影响2.4直接法的稳定性分析3.当系数矩阵A和右端项b均有扰动时2.4直接法的稳定性分析2.4直接法的稳定性分析条件数不能反映算法的稳定性：[例1]分别用GAUSS消元法、列主元素法和改进平方根法解下面线性方程组。2.4直接法的稳定性分析2.4.2消元法的稳定性分析GAUSS全主元素法消元