线性方程组求解的数值方法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Ch3,线性方程组求解的数值方法,Numerical Solutions of Systems of Linear Equations,Ch3 线性方程组求解的数值方法Numerical Solu,1,3.0 Introduction,线性方程组,工程问题,（电子网络，船体放样等）,自然科学,（实验数据的最小二乘法曲线拟合）,解非线性方程组,解常/偏微分方程组,（差分法，有限元法）,3.0 Introduction线性方程组工程问题（电子网,2,3.0 Introduction,线性方程组的,系数矩阵,：,（1）低价稠密矩阵（阶数,L,U,P=lu(A),其中,【,作业,】,P.67 题1,2,3.1.2 矩阵的LU分解（LU Decomposition,15,3.1.3,选主元消去法,/*Pivoting Strategies*/,例：,单精度解方程组,/*精确解为 和 */,8个,8个,用Gaussian Elimination计算：,8,个,小主元,/*Small pivot element*/,可能导致计算失败。,3.1 Gaussian Elimination and LU Decomposition,3.1.3 选主元消去法/*Pivoting Stra,16,全主元消去法,/*Complete Pivoting*/,每一步选绝对值最大的元素为主元素，保证 。,Step,k,:,选取,If,i,k,k,then 交换第,k,行与第,i,k,行;,If,j,k,k,then 交换第,k,列与第,j,k,列;,消元,注,：,列交换改变了,x,i,的顺序，须记录,交换次序,，解完后再换回来。,列主元消去法,/*Partial Pivoting,or,maximal column pivoting,*/,省去换列的步骤，每次仅选一列中最大的元。,3.1 Gaussian Elimination and LU Decomposition,全主元消去法/*Complete Pivoting,17,例：,注,：,列主元法没有全主元法稳定。,例：,注意：这两个方程组在数学上,严格等价,。,标度化列主元消去法,/*Scaled Partial Pivoting*/,对每一行计算 。为省时间，,s,i,只在初始时计算一次。以后每一步考虑子列 中 最大的,a,ik,为主元。,注,：,稳定性介于列主元法和全主元法之间。,3.1 Gaussian Elimination and LU Decomposition,例：注：列主元法没有全主元法稳定。例：注意：这两个方程组在,18,实际应用中直接调用,Gauss Elimination,解3阶线性方程组的结果：,结合全主元消去后的结果：,3.1 Gaussian Elimination and LU Decomposition,实际应用中直接调用Gauss Elimination 解3阶,19,3.2 Cholesky,分解,【,Matlab,】,设A是,对称正定,矩阵，则,A,有以下形式的LU分解：,A,=,P,T,P,（3.2.1）,其中P是一个上三角矩阵,上式称为A的,Cholesky分解,(Choleskian decomposition).,P=chol(A),定理,【,作业,】,P.68 题4,3.2 Cholesky分解【Matlab】设A是对称正定,20,3.3,向量范数与矩阵范数,误差的度量,3.3.1,向量范数,(,vector norms,),常用向量范数：,这些范数满足：,一般范数：,3.3 向量范数与矩阵范数 误差的度量3.3.1 向量范,21,如，设,向量,x,=(2,-4,-1),T,则,3.,3 向量范数与矩阵范数,【,Matlab,】,x=(1:4)/5,N1=norm(x,1),N2=norm(x),N7=norm(x,7),Ninf=norm(x,inf),x=,0.2000 0.4000 0.6000 0.8000,N1=,2,N2=,1.0954,N7=,0.8153,Ninf=,0.8000,如，设向量 x=(2,-4,-1)T,则 3.3 向,22,定义,矩阵,A,的范数定义为,3.,3 向量范数与矩阵范数,3.3.2,矩阵范数,(,matrix norms,),命题：,矩阵的常用范数：,其中，,1,n,是,的特征值，,称为 的,谱半径,。,定义 矩阵A的范数定义为3.3 向量范数与矩阵范数3.3.,23,例,设矩阵,3.,3 向量范数与矩阵范数,则,可以证明,，矩阵范数满足：,例 设矩阵3.3 向量范数与矩阵范数则可以证明，矩阵范数满,24,3.4,经典迭代法,Jacobi迭代法与Gauss-Seidel迭代法,3.4.1Jacobi迭代法,设有,n,阶方程组,(3.4.1),3.4 经典迭代法Jacobi迭代法与Gauss-Sei,25,若系数矩阵非奇异，且,(,i,=1,2,n,)，,将方程组,（4.1）,改写成,3.4,经典迭代法,若系数矩阵非奇异，且 (,26,然后写成迭代格式,（3.4.2）,（3.4.2）,式也可以简单地写为,（3.4.3）,3.4,经典迭代法,然后写成迭代格式（3.4.2）（3.4.2）式也可以简单地写,27,写成,矩阵形式,：,A,=,L,U,D,B,Jacobi 迭代阵,(3.4.6),3.4,经典迭代法,写成矩阵形式：A=LUDBJacobi 迭代阵(3.4.6,28,只存一组向量即可。,写成,矩阵形式,：,B,Gauss-Seidel,迭代阵,3.4.2 Gauss-Seidel迭代法,(3.4.7),3.4,经典迭代法,只存一组向量即可。写成矩阵形,29,定理,3.1,对任意初始向量,X,(0),及常向量,F,，,迭代格式,(3.5.1),(3.5.1),推论,：,若迭代矩阵,的,某种范数,，,则,（,3.5.1,）,收敛的充分必要条件是迭代矩阵,B,的谱半径,(,B,)1)（此时矩阵也称为“病态矩阵”）的线性方程组,Ax,=,b,是病态的；反之，系数矩阵的条件数很小的线性方程组,Ax,=,b,是良态的。,A=hilb(n);,c=cond(A),Example:,著名的Hilbert 矩阵是病态的。,【,Matlab,】,3.,7,条件数、病态方程组与算法的稳定性,3.7.2 条件数与方程组病态性 定义 设A 是一个非,38,定理,3.6,(,条件数的性质,),设,A,是一个非奇异矩阵.,(1)cond(A),1,cond(A)=cond(A,-1,),con(,a,A)=cond(,A,),a,0.,(2)如果 Q是正交矩阵，则,cond,2,(Q)=1,cond,2,(A)=cond,2,(QA)=cond,2,(AQ),其中cond,2,(A)=|A,-1,|,2,|A|,2,.,3.,7,条件数、病态方程组与算法的稳定性,定理3.6(条件数的性质)设A 是一个非奇异矩阵,39,3.8,稀疏矩阵的计算,例,（,比较,稀疏矩阵算法,与,普通矩阵算法,：机器时间与占用空间,）,考虑线性方程组,3.8 稀疏矩阵的计算例（比较稀疏矩阵算法与普通矩阵算法,40,%sparse and full matrix,n=100;,row=2:n;col=1:n-1;,val=ones(1,n-1);,offd=sparse(row,col,val,n,n);,a=sparse(1:n,1:n.4*ones(1,n),n,n);,b=full(a);,rh=1:n;,tic;x=a/rh;t1=toc,tic;y=b/rh;t2=toc,【实验要求】逐步增大,n,的值,，观察发生的现象。,3.8,稀疏矩阵的计算,%sparse and full matrix【实验要求】,41,