第二章数值代数

第二章数值代数

§2.1Gauss消去法§2.2直接三角分解法

§2.3范数和误差分析

引言

快速、高效地求解线性方程组是数值线性代数研究中的核心问题，也是目前科学计算中的重大研究课题之一。各种各样的科学和工程问题，往往最终都要归结为求解一个线性方程组。线性方程组的数值解法有：直接法和迭代法。直接法：在假定没有舍入误差的情况下，经过有限次运算可以求得方程组的精确解；迭代法：从一个初始向量出发，按照一定的迭代格式，构造出一个趋向于真解的无穷序列。引例：Cramer法则不可行Cramer法则n>20时，计算量太大，现实上不可行.Cramer法则数学理论上很重要，但计算上无价值问题：可以用x=A-1b来求解吗？§2.1Gauss消去法（GaussEliminationMethod）

1理论基础

2顺序Gauss消去法

3选主元技术

（Pivoting）4追赶法

（Tridiagonalmatrixalgorithm）10德国马克的纸币1.理论基础引理2.1同解2.顺序高斯(Gauss)消去法顺序高斯消去法的主要思路：将增广阵[A|b]中的系数矩阵A化为上三角矩阵，然后回代求解。分为消元过程(elimination)和回代过程(backwardsubstitution)考虑n阶线性方程组：矩阵形式=增广阵形式举例（一）解：消元过程：例：用顺序高斯消去法求解回代过程:不要化简！消元过程(第1步)用矩阵初等行变换化系数矩阵为上三角形消元过程(第2步)消元过程(第k步)编程用计算公式消元过程(结果)上三角方程组回代回代过程计算量(乘除法次数)消元

回代

总和计算量主要在消元比较Cramer法则，Gauss消去法快很多3.选列主元高斯消去法

顺序高斯消去法有效的条件是：主元如果某个主元为0，则导致高斯消去法求解失败。选列主元高斯消去法：在第k步消元时①先选取列主元（Pivoting）

：②ifik

k

then交换第k行和第ik行；列主元高斯消去法比顺序高斯消去法要多一些比较运算，但比顺序高斯消去法稳定。③消元全主元高斯消去法全主元高斯消去法：第k步消元时选A(k)中绝对值最大的元素为主元，即①先选取全主元：ifik

k

then交换第k行和第ik

行；

ifjk

k

then交换第k列和第jk

列；③消元列交换改变了

xi

的顺序，须记录交换次序，解完后再换回来。全主元高斯消去法具有很好的稳定性，但选全主元比较费时，故在实际计算中很少使用。例(选列主元素Gauss消去法)回代:举例（二）解：

例：取8位有效数字，分别用Gauss消去法和列主元Gauss消去法求解线性方程组:精确解为，8个08个9顺序Gauss消去法：9个0小主元可能导致计算失败。举例（二）续列主元Gauss消去法：例：但列主元高斯消去法有时也会导致求解失败。4追赶法

（Tridiagonalmatrixalgorithm）三对角方程组

Gauss消去法应用于三对角线性方程组得到所谓追赶法，其中消元过程为“追”，回代过程为“赶”。4追赶法增广阵：4追赶法追

k=2,,n

赶

k=n-1,,1如果不令则有6n-5次乘除法计算量追赶法不对零元素计算，只有5n-4次乘除法计算量放假通知劳动节：2013年4月29日至5月1日放假调休，共3天。4月27日(星期六)上第10周4月29日（星期一）的课程。4月28日(星期日)上第10周4月30日（星期二）的课程。

双周的数值分析课被放假。端午节：2013年6月10日至12日放假调休，共3天。6月8日(星期六)上第16周6月10日（星期一）的课程。6月9日(星期日)上第16周6月12日（星期三）的课程。

§2.2直接三角分解法高斯消去法的矩阵表示LU分解法(LUDecomposition)平方根法(CholeskyDecomposition)改进的平方根法矩阵三角分解

将一个矩阵分解成结构简单的三角形矩阵的乘积称为矩阵的三角分解。顺序高斯消去法其实就是一个矩阵的三角分解过程。LU分解A=LU(Doolittle分解)用LU分解求解方程组先求解y再求解x则A(k)

与A(k+1)之间的关系式可以表示为：其中：(i=k+1,…,n),将Gauss消去过程中第k-1步消元后的系数矩阵记为：(k=1,…,n-1)LU分解记：，则其中：L---单位下三角矩阵，U---上三角矩阵LU分解于是有：容易验证：(k=1,…,n-1)(杜利脱尔Doolittle分解)LU

分解的存在唯一性LU分解存在顺序高斯消去法不被中断?定理

顺序高斯消去法求解方程组Ax=b时，所有主元

的充要条件是：A的所有顺序主子式不为零。定理若A的所有顺序主子式不等于0，则A存在唯一的LU分解。(LU分解的唯一性

)证：存在性由上面的定理可得；唯一性可用反证法证明。类似分解定理若A的所有顺序主子式不等于0,则(1)A存在唯一的LDR

分解：A=LDR，其中：L

是单位下三角矩阵，D

是对角矩阵，R

是单位上三角矩阵(2)A存在唯一的克洛脱(Crout)分解：

，其中：L

是下三角矩阵，U

是单位上三角矩阵LU分解紧凑方式直接利用矩阵乘法来计算LU分解(待定系数法)比较等式两边的第一行得：u1j=a1j比较等式两边的第一列得：比较等式两边的第二行得：比较等式两边的第二列得：(j=1,…,n)(i=2,…,n)(j=2,…,n)(i=3,…,n)U的第一行L的第一列U的第二行L的第二列LU分解计算顺序

待定系数法LU分解紧凑算法（续）第k

步：此时U的前k-1行和L的前k-1列已经求出比较等式两边的第k行得：比较等式两边的第k列得：直到第n

步，便可求出矩阵L和U的所有元素。(j=k,…,n

)(i=k+1,…,n

)LU分解紧凑算法（续）LU分解的算法：Fork=1,2,...,nEndForj=k,…,ni=k+1,…,n为了节省存储空间，通常用A的绝对下三角部分来存放L(对角线元素无需存储)，用A的上三角部分来存放U。运算量：(n3-n)/3Crout分解的紧凑算法Crout分解的算法：Fork=1,2,...,nEndFori=k,…,nj=k+1,…,n运算量：(n3-n)/3平方根法(SPD的Cholesky分解)

A=LLT(Cholesky分解)(其中)解法：求A=LLT用待定系数法为什么对称正定矩阵有这样的分解呢？平方根法(SPD的Cholesky分解)

若A是对称正定矩阵(SymmetricPositiveDefinite)AT=A

LDR分解唯一设D=diag(d1,,dn)A对称正定：di>0，(i=1,…,n)

令SPD的Cholesky分解设Cholesky分解几点说明：(1)L

为对角线元素全为正的下三角矩阵；(2)只有对称正定矩阵(SPD)才存在Cholesky分解；书上P24利用顺序主子式先求对角元素好吗？只适合于手算！实际上，数值计算行列式用LU分解。定理对称正定矩阵的Cholesky分解存在，且满足的解唯一。Cholesky分解实现算法直接利用矩阵乘法来计算分解(待定系数法)Fork=1,2,...,n算法5.3：(Cholesky

分解，按列)EndFori=k+1,…,n运算量：n3/6

+n2/2+n/3

改进的平方根法A=LDLT,据此可逐行计算

运用这种矩阵分解方法,方程组Ax=b可归结为求解两个三角方程组即:和其计算公式分别为:

和上述算法称为改进的平方根法。这种方法总的计算量约为，即仅为高斯消去法计算量的一半。改进在哪里？(1)避免了开方运算;(2)计算的可行性条件减弱为A对称非奇异。有可能某个改进的平方根法§2.3范数和误差分析1范数和条件数

(NormandConditionNumber)2数据扰动分析(PerturbationAnalysis)1范数和条件数引例

病态方程组：数据小扰动解大误差。注意：两组解都是相应方程组的精确解，没有计算误差二元病态方程组的几何意义在二元情况下，“求两条直线的交点”的问题是否不稳定，取决于这两条直线是否接近于平行(系数矩阵A的行向量线性相关)。良态方程组病态方程组向量范数

(VectorNorms)

定义：Rn上实值函数||.||,对于任意满足正定性||x||0,且||x||=0x=0齐次性||x||=||||x||三角不等式

||x+y||||x||+||y||常用向量范数矩阵范数

(MatrixNorms)定义：Rn×n上实值函数||.||,对于任意满足正定性||A||0,且||A||=0A=0齐次性||A||=||||A||三角不等式

||A+B||||A||+||B||相容性||AB||

||A||||B||与向量范数相容||Ax||

||A||||x||常用矩阵范数

相容性：

||Ax||v

||A||v

||x||v,v=1,2,||Ax||2

||A||F

||x||2范数的等价性

|