《数值分析与算法》 第三讲-线性方程组的直接解法

1、数数 值值 分分 析析 (3)Numerical AnalysisWenjian Yu2第三章第三章 线性方程组的直接解法线性方程组的直接解法n线性方程组求解是一个基本的数学问题线性方程组求解是一个基本的数学问题新的挑战新的挑战: 方程的规模大，例如变量数方程的规模大，例如变量数106困难困难: 存储、计算速度、舍入误差存储、计算速度、舍入误差是是数值线性代数数值线性代数的基础的基础 (我们分两章讨论我们分两章讨论)n本章内容本章内容基本概念与问题敏感性基本概念与问题敏感性高斯消去法高斯消去法矩阵的矩阵的LU分解分解选主元技术与算法稳定性选主元技术与算法稳定性对称正定矩阵与带状矩阵解法对称正定

2、矩阵与带状矩阵解法稀疏矩阵与实用技术稀疏矩阵与实用技术 (选学选学)直接解法直接解法，就是理论上，就是理论上经过有限步计算能得到经过有限步计算能得到准确解的方法。准确解的方法。Wenjian Yu3基本概念基本概念Wenjian Yu4线性方程组与矩阵的基本概念线性方程组与矩阵的基本概念复习复习: 线性空间线性空间, 线性相关线性相关(无关无关), 基基, 维数维数, 内积内积； 非奇异矩阵非奇异矩阵, 线性方程组解的线性方程组解的存在性与唯一性存在性与唯一性Wenjian Yu5线性方程组与矩阵的基本概念线性方程组与矩阵的基本概念n表示表示稀疏矩阵稀疏矩阵的的Wilkinson图图Wenji

3、an Yu6向量的范数向量的范数n(正定条件正定条件)(三角不等式三角不等式)Wenjian Yu7向量的范数向量的范数n(曼哈顿范数曼哈顿范数)(“最大最大”范数范数)(欧氏范数欧氏范数=内积范数内积范数)观看演示观看演示3.1Wenjian Yu8向量有关的定理向量有关的定理n(Hint: 利用利用 范数范数，课后思考课后思考)Wenjian Yu9矩阵的范数矩阵的范数n(不满足交换律不满足交换律)Wenjian Yu10矩阵的范数矩阵的范数n思考思考:0 1如何证明？如何证明？后面只考虑后面只考虑算子范数算子范数Wenjian Yu11矩阵的范数矩阵的范数nWenjian Yu12问题的

4、敏感性问题的敏感性Wenjian Yu13线性方程组求解问题的敏感性线性方程组求解问题的敏感性nWenjian Yu14矩阵的条件数矩阵的条件数nWenjian Yu15矩阵的条件数矩阵的条件数n符合上界的意义符合上界的意义Wenjian Yu16矩阵的条件数矩阵的条件数n良态问题！良态问题！见见pp. 68Wenjian Yu17矩阵条件数的性质矩阵条件数的性质n0 1(演示演示3.2)Wenjian Yu18矩阵条件数的性质矩阵条件数的性质np-范数下等号成立范数下等号成立!正交变换不改条件数正交变换不改条件数!Wenjian Yu19高斯消去法高斯消去法Wenjian Yu20高斯消去法

5、高斯消去法n(此小节不要求此小节不要求)行倍乘变换行倍乘变换行倍加变换行倍加变换Wenjian Yu21高斯消去法高斯消去法n算法算法3.1 解解线性方程组的高斯消去过程线性方程组的高斯消去过程111213121222323132333123nnnnnnnnaaaaaaaaaaaaaaaa Wenjian Yu22矩阵的矩阵的LU分解分解Wenjian Yu23高斯消去法高斯消去法nWenjian Yu24矩阵的矩阵的LU分解分解n高斯消去过程对矩阵高斯消去过程对矩阵A的变换的变换 (3阶矩阵为例阶矩阵为例)等价等价于左乘于左乘消去矩阵消去矩阵:行倍加变换行倍加变换两次倍加变换两次倍加变换单位

6、下三角阵单位下三角阵乘子乘子Wenjian Yu25矩阵的矩阵的LU分解分解n第第2步消去步消去等价于左乘等价于左乘消去矩阵消去矩阵行倍加变换行倍加变换一次倍加变换一次倍加变换Wenjian Yu26矩阵的矩阵的LU分解分解n逆矩阵也是消逆矩阵也是消去矩阵去矩阵注注: 矩阵的下标指矩阵的下标指示了消去矩阵的示了消去矩阵的类型数类型数(定义定义3.12)定理定理3.13Wenjian Yu27矩阵的矩阵的LU分解分解n(充要条件充要条件)Wenjian Yu28矩阵的矩阵的LU分解分解n算法算法3.5 用用高斯高斯消去消去过程过程做做LU分解分解乘子的相反数乘子的相反数Wenjian Yu29矩

7、阵的矩阵的LU分解分解nWenjian Yu30直接直接LU分解算法分解算法 (算法算法3.6) 数学上等价算法数学上等价算法3.5 算法描述不同，存算法描述不同，存取、计算的顺序不同取、计算的顺序不同 对于稠密矩阵对于稠密矩阵(二维二维数组数组)计算效率一样，计算效率一样，但对于但对于稀疏矩阵稀疏矩阵(特殊特殊数据结构数据结构)，效率可能，效率可能有较大差别有较大差别lulluuWenjian Yu31LU分解的用途分解的用途n也可求矩阵的逆也可求矩阵的逆Wenjian Yu32选主元技术与稳定性选主元技术与稳定性Wenjian Yu33主元为零的可能性主元为零的可能性n单位下三角阵单位下三

8、角阵Wenjian Yu34主元为零的可能性主元为零的可能性n无无LU分解分解无穷多无穷多LU分解分解高斯消去中断高斯消去中断矩阵奇异矩阵奇异矩阵不可矩阵不可LU分解分解思考思考：这三条性质：这三条性质可以互相推出吗？可以互相推出吗？Wenjian Yu35如何解决主元为零的问题如何解决主元为零的问题n定理定理3.16Wenjian Yu36使用部分主元技术的使用部分主元技术的LU分解分解nWenjian Yu37使用部分主元技术的使用部分主元技术的LU分解分解nWenjian Yu38使用部分主元技术的使用部分主元技术的LU分解分解nWenjian Yu39使用部分主元技术的使用部分主元技术

9、的LU分解分解n行交换行交换消去消去消去消去行交换行交换验证验证(见演示3.4)Wenjian Yu40采用部分主元的采用部分主元的LU分解算法分解算法 (算法算法3.7)(Matlab命令命令: lu)Wenjian Yu41部分主元技术部分主元技术与其他主元技术与其他主元技术n(见演示3.5)Wenjian Yu42算法的稳定性算法的稳定性n(思考题思考题)Wenjian Yu43对称正定矩阵的对称正定矩阵的Cholesky分解分解Wenjian Yu44应用实例应用实例n1R5R3R4R2R1V2V3Vs1i0112300sVViV 11R21R21R21R21R31R41R41R41R

10、41R51R00Wenjian Yu45对称矩阵的对称矩阵的LU分解分解n希望快速求解对称希望快速求解对称 或对称正定矩阵或对称正定矩阵Wenjian Yu46对称矩阵的对称矩阵的LU分解分解nWenjian Yu47Cholesky分解算法分解算法n也叫也叫平方根法平方根法. 下面按直接下面按直接LU分解思想推导算法分解思想推导算法算法算法3.10 (按从按从1到到n的顺序的顺序逐列逐列算出算出L的元素值的元素值)n nn nnnnnnnnnnnnnl llllllllllllllll lllllll 1111211222212212000000LLLOMMOOMMMOLL=For j =1

11、 to n For i = j+1 to n EndEnd1 12 21 1j jj jj jj jj jj jk kk ka aa aa a 1 11 1( () )/ /j ji ij ji ij ji ik kj jk kj jj jk ka aa aa a a aa a 对角元对角元当前列当前列22221 1jjjjjjjjjjallallLWenjian Yu48Cholesky分解算法分解算法nTTTTAL UL DDLL LAL UL DDLL L11112222000000T TUDLUDL 1 12 2T TUL DUL D 1 12 2增长因子增长因子 ()()T Tiji

12、jm ax Ui,jm ax Ui,jm axam axa 1 1 2 2ijijm ax lm ax l ijijm axam axa ij jjij jjm axl lm axl l iiiim ax am ax a(Matlab演示)Wenjian Yu49带状矩阵解法与带状矩阵解法与稀疏矩阵简介稀疏矩阵简介Wenjian Yu50带状线性方程组带状线性方程组nWenjian Yu51带状线性方程组带状线性方程组n计算量计算量: M.D.= 2n-2Wenjian Yu52带状线性方程组带状线性方程组n且至少有一个不等且至少有一个不等号号严格成立严格成立Wenjian Yu53带状线性方

13、程组带状线性方程组nWenjian Yu54稀疏矩阵稀疏矩阵n非零元非零元分布图分布图Wenjian Yu55稀疏矩阵稀疏矩阵n存储稀疏矩阵的数据结构存储稀疏矩阵的数据结构三元组三元组 (COO格式格式)n非零元在数组中顺序可以任意非零元在数组中顺序可以任意n有点冗余有点冗余: 一些一些连续存储连续存储单元可能单元可能有有相同的相同的行行(列列)编号编号压缩稀疏行压缩稀疏行 (CSR格式格式)n非零元按第非零元按第1行行, 第第2行行, , 第第n行的顺序存储行的顺序存储nprow为各行在数组中的开始位置为各行在数组中的开始位置aa12345678910 11row11222333445col

14a12345678910 11corow136911 12 如何得每行非零元数目如何得每行非零元数目?Wenjian Yu56稀疏矩阵稀疏矩阵n广泛用于广泛用于非结非结构化稀疏阵构化稀疏阵Wenjian Yu57稀疏矩阵稀疏矩阵n思考思考: 按稀疏矩阵存按稀疏矩阵存储格式写相应程序储格式写相应程序XXXXXX000XX0X000XXXXXXXXXXWenjian Yu58Matlab中的相关技术中的相关技术Wenjian Yu59Matlab中的矩阵中的矩阵n存储方式存储方式稠密矩阵稠密矩阵(二维数组二维数组) 、稀疏矩阵、稀疏矩阵(压缩稀疏列

15、压缩稀疏列)以相同的方式以相同的方式支持一般的矩阵操作支持一般的矩阵操作/运算运算; 通过通过whos命令看两者区别命令看两者区别n稠密矩阵的命令稠密矩阵的命令生成矩阵生成矩阵: ones(m,n), zeros(m,n), eye(m,n), rand(m,n)矩阵维数等矩阵维数等: size(A), diag(A)/diag(v), tril(A), triu(A)载入载入/导出数据文件导出数据文件 (ascii或或binary格式格式): load, saven稀疏矩阵稀疏矩阵的常用命令的常用命令生成与转换生成与转换: sparse(X) or sparse(i,j,s,m,n), X

16、= full(A)非零元的信息非零元的信息: nnz(A), spy(A), find(A)Wenjian Yu60Matlab中的矩阵中的矩阵nWenjian Yu61Matlab“”的内部算法的内部算法矩阵矩阵A (按如下顺序按如下顺序)求解算法求解算法稀疏的对角阵稀疏的对角阵右端项元素除以矩阵对角元右端项元素除以矩阵对角元较稠密的带状方阵较稠密的带状方阵部分主元的带状矩阵部分主元的带状矩阵LU分解分解 (LAPACK软件包软件包)上三角或下三角矩阵上三角或下三角矩阵回代法或前代法回代法或前代法对三角矩阵作对三角矩阵作行排列行排列形形成的矩阵成的矩阵重排序后用回代或前代法重排序后用回代或前代法对称矩阵对称矩阵, 且对角线元且对角线元素大于零素大于零尝试尝试Cholesky分解算法分解算法(稠密矩阵稠密矩阵: LAPACK, 稀稀疏矩阵疏矩阵: CHOLMOD), 若稠密、且不正定使用若稠密、且不正定使用选主元的对称矩阵求解算法选主元的对称矩阵求解算法(LAPACK)稠密上稠密上Hessenberg矩阵矩阵 消为上三角矩阵再回代求解消为上三角矩阵再回代求解一般的稀疏方阵一般的稀疏方阵针对稀疏矩阵的直接解法针对稀疏矩阵的直接解法(UMFPACK)一般的稠密方阵一般的稠密方阵部分主元部分主元LU分解分解(LAPACK