《数值分析课件第七章线性方程组的直接解法》由会员分享，可在线阅读，更多相关《数值分析课件第七章线性方程组的直接解法（80页珍藏版）》请在金锄头文库上搜索。
1、西安电子科技大学理学院 主讲: 王卫卫,第七章 线性方程组的直接解法 /* Direct methods for the solution of linear systems */,线性方程组：,矩阵形式,西安电子科技大学理学院 主讲: 王卫卫,Homogeneous term,Coefficient matrix,or,Unknown variables,线性方程组由增广矩阵唯一确定,西安电子科技大学理学院 主讲: 王卫卫,通过某种迭代系统（公式）求得近似解，优点：编程简单 缺点：存在收敛性和收敛速度问题,How to get the solution？,Coefficient matrix
2、 A 低阶稠密阵 高阶稀疏阵 small dense matrix large sparse matrix,Direct methods,Iteration methods,Gaussian elimination 列/行/完全主元素(pivoting)消去法 Gauss-Jordan elimination Square root/improved square root methods 追赶法,Jaccobi iteration Gauss-Sidel iteration SOR,Existence and uniqueness of the solution？,Cramer rule:
3、Computation cost: (n+1)!,上万阶，零元素很多，非零元素很少,非零元素较多，零元素较少,经过有限步算术运算直接求得精确解（在没有舍入误差的情况下），但实际上机器总存在舍入误差，因此求得的是近似解,西安电子科技大学理学院 主讲: 王卫卫,Gaussian elimination -通过初等变换将原方程组化成三角方程租来求解,西安电子科技大学理学院 主讲: 王卫卫,Step 1. Denote Ax=b as,西安电子科技大学理学院 主讲: 王卫卫,初等行变换,相当于左乘初等行变换矩阵,formulae,Directly replace with 0,Leave alone,
4、Need to be updated,Convenient in using Matlab,Mathmatica,Maple,第i行第1列,西安电子科技大学理学院 主讲: 王卫卫,Step k. After k-1 eliminations, we have,西安电子科技大学理学院 主讲: 王卫卫,初等行变换,相当于左乘初等行变换矩阵,Leave alone,Need to be updated,Directly replace with 0,第i行第k列,西安电子科技大学理学院 主讲: 王卫卫,formulae,k=1,n-1,Convenient in using Matlab,Mathm
5、atica,Maple,k=1,n-1,消 元 过 程,西安电子科技大学理学院 主讲: 王卫卫,对角线元素全为1，非对角线上除第i行第k列元素为lik外其余元素全为0,西安电子科技大学理学院 主讲: 王卫卫,要使Gauss消去法能够进行下去，必须有约化后的主对角元素非零，即 矩阵A在什么条件下能够保证此条件成立？,西安电子科技大学理学院 主讲: 王卫卫,(n-k) k,kk,det=Di,kk,det=1,kk,det=,0k(n-k),证明要点,西安电子科技大学理学院 主讲: 王卫卫,Inference,西安电子科技大学理学院 主讲: 王卫卫,In Gaussian elimination,
6、 if a certain diagonal element vanishes, then you cant continue eliminating.,Choose column/row/overall main element!,Right. Even if it is very small, you cant do that because it will cause error Expand and the scale increase dramatically,then what should we do?,西安电子科技大学理学院 主讲: 王卫卫,Gauss column/row/c
7、omplete pivoting,西安电子科技大学理学院 主讲: 王卫卫,Solution: 消元,回代求解：,西安电子科技大学理学院 主讲: 王卫卫,Gauss-Jordan消去法无回代过程的列主元消去法：Gauss列主元消去法只消去对角线下方的元素， Gauss-Jordan消去法同时消去对角线下方和上方的元素,设已经过k-1步G-J消元，得到,G-J消元过程k=1,n,西安电子科技大学理学院 主讲: 王卫卫,西安电子科技大学理学院 主讲: 王卫卫,Gauss-Jordan消去法能够进行下去的条件和前面一样！ 计算量高于Gauss列主元 消去法，通常用G-J消去法求矩阵的逆(初等行变换),
8、西安电子科技大学理学院 主讲: 王卫卫,Solution: 消元,西安电子科技大学理学院 主讲: 王卫卫,solution,西安电子科技大学理学院 主讲: 王卫卫,Computation cost,西安电子科技大学理学院 主讲: 王卫卫,detLk=1, Lk invertible, k=1,2, n-1,矩阵的直接三角分解(LU分解，不选主元),k=1,2, n-1,上三角阵,西安电子科技大学理学院 主讲: 王卫卫,单位下三角阵,单位下三角阵,上三角阵,西安电子科技大学理学院 主讲: 王卫卫,LU分解定理,A的各阶顺序主子式,单位下三角阵,上三角阵,证明要点,存在性不必证,见前面的分析,仅证
9、唯一性(采用反正法),单位下三角,上三角阵,西安电子科技大学理学院 主讲: 王卫卫,矩阵的直接三角分解(LU分解)对解线性方程组有什么帮助？,三角方程组，易于求解,西安电子科技大学理学院 主讲: 王卫卫,矩阵直接三角分解(LU分解)中如何求L和U的元素？ 矩阵乘法,A的第一行,U的第一行,A的第一列,L的第一列,西安电子科技大学理学院 主讲: 王卫卫,Lrk=0, k=r+1, n; Lrr=1,A的第r行,U的第r行,Ukr=0, k=r+1, n;,A的第r列,L的第r列,LU factorization r=2, n -Doolittle factorization,西安电子科技大学理学
10、院 主讲: 王卫卫,A,24,solution,1 2 3 4,1 1 1,2 6 12,3 7,6 24,6,U,L,西安电子科技大学理学院 主讲: 王卫卫,平方根法和改进的平方根法A对称正定,D,U0,A symmetric and positive definite,单位下三角,diagonal,单位上三角,西安电子科技大学理学院 主讲: 王卫卫,单位下三角,上三角,单位下三角,上三角,Cholesky factorization,西安电子科技大学理学院 主讲: 王卫卫,用直接分解法确定 的元素的递推公式,Obviously, if j i, then lij=0,Else ji,if
11、k j, then ljk=0,西安电子科技大学理学院 主讲: 王卫卫,Given Ax=b, where A is symmetric and positive definite, what does Cholesky factorization to do with solution of Ax=b,三角方程组，易于求解,对系数矩阵为对称正定的线性方程组，先对A作Chloesky分解，然后将方程组化成两个三角方程组求解的方法称为解线性方程组的平方根法，计算量是n3/6,是Gauss法的一半，只要存储下半个三角即可,Given Ax=b, where A is symmetric and p
12、ositive definite, what does Cholesky factorization to do with solution of Ax=b,西安电子科技大学理学院 主讲: 王卫卫,solution,A 对称正定,西安电子科技大学理学院 主讲: 王卫卫,diagonal,改进的平方根法避免平方根法中的开方运算,单位下三角,Obviously, if j i, then lij=0 and ljj=1; else ji,西安电子科技大学理学院 主讲: 王卫卫,三角方程组，易于求解,西安电子科技大学理学院 主讲: 王卫卫,三对角方程组,追赶法求解三对角方程组,三对角矩阵,西安电子科
13、技大学理学院 主讲: 王卫卫,Theorem 4 若三对角矩阵A为弱对角占优，即满足,则它可唯一分解成单位下二对角阵L和上二对角阵U的乘积,追赶法的代数基础,西安电子科技大学理学院 主讲: 王卫卫,三角方程组，易于求解,追,赶,西安电子科技大学理学院 主讲: 王卫卫,summary,西安电子科技大学理学院 主讲: 王卫卫,review,Set X:具有一定性质的对象的全体，元素无大小，元素间无代数结构和拓扑结构,集合上定义距离:x,yX, 对应实数p(x,y)R,满足距离公理: p(x,y) 0(非负性), p(x, y)= p(y, x)(对称性)、 p(x, y) p(x, z)+ p(z
14、, y) (三角不等式）,集合上定义线性代数结构(线性运算最基本的运算): x,yX 加法封闭(且满足交换律、结合律、存在零元素、逆(负)元素): x+y=y+x X; x+(y+z)=(x+y)+z X;0 X,x+0=x; -xX,x+(-x)=0; 数乘封闭(且满足结合律、数的分配律): a,bK a(bx)=(ab)x; 1x=x, 0x=0; (a+b)x=ax+bx; a(x+y)=ax+ay,线性空间上定义范数: xX, 对应非负实数x ,满足范数公理: x =0x=0 (非负性)； ax = a x (齐性); x+ y x + y ,(三角不等式）,线性空间上定义内积: x,
15、yX, 对应!数(x,y) K,满足内积公理: (x,x)0, (x,x)=0x=0 (正定性) (ax+by,z)=a(x,z)+b(y,z) (线性)； (x, y)= (共轭对称性),分析的对象,西安电子科技大学理学院 主讲: 王卫卫,赋范线性空间,算子,数空间,泛函,函数,微积分,抽象函数,泛函分析研究空间、算子的普遍规律。以各种学科为具体背景，把客观世界中的研究对象抽象为元素和空间，对象间的关系抽象为算子。从而把表面不相关的学科统一在它的普遍规律和共同框架之下。具有高度的抽象性和广泛的应用性。是数值分析的基础。,西安电子科技大学理学院 主讲: 王卫卫,向量范数与矩阵范数,Vector,matrix,西安电子科技大学理学院 主讲: 王卫卫,常用的向量范数,例,西安电子科技大学理学院 主讲: 王卫卫,向量范数的性质,设 为Rn中一向量序列，,为Rn中任一两种向量范数，若const. a,b,
