线性方程组求解的数值方法省名师优质课赛课获奖课件市赛课一等奖课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。感谢您,Ch3,线性方程组求解数值方法,Numerical Solutions of Systems of Linear Equations,第1页,3.0 Introduction,线性方程组,工程问题,（电子网络，船体放样等）,自然科学,（试验数据最小二乘法曲线拟合）,解非线性方程组,解常/偏微分方程组,（差分法，有限元法）,第2页,3.0 Introduction,线性方程组,系数矩阵,：,（1）低价稠密矩阵（阶数,L,U,P=lu(A),其中,【,作业,】,P.67 题1,2,第15页,3.1.3,选主元消去法,/*Pivoting Strategies*/,例：,单精度解方程组,/*准确解为 和 */,8个,8个,用Gaussian Elimination计算：,8,个,小主元,/*Small pivot element*/,可能造成计算失败。,3.1 Gaussian Elimination and LU Decomposition,第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,第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,第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,第20页,3.3,向量范数与矩阵范数,误差度量,3.3.1,向量范数,(,vector norms,),惯用向量范数：,这些范数满足：,普通范数：,第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.0.4000 0.6000 0.8000,N1=,2,N2=,1.0954,N7=,0.8153,Ninf=,0.8000,第22页,定义,矩阵,A,范数定义为,3.,3 向量范数与矩阵范数,3.3.2,矩阵范数,(,matrix norms,),命题：,矩阵惯用范数：,其中，,1,n,是,特征值，,称为,谱半径,。,第23页,例,设矩阵,3.,3 向量范数与矩阵范数,则,能够证实,，矩阵范数满足：,第24页,3.4,经典迭代法,Jacobi迭代法与Gauss-Seidel迭代法,3.4.1Jacobi迭代法,设有,n,阶方程组,(3.4.1),第25页,若系数矩阵非奇异，且,(,i,=1,2,n,)，,将方程组,（4.1）,改写成,3.4,经典迭代法,第26页,然后写成迭代格式,（3.4.2）,（3.4.2）,式也能够简单地写为,（3.4.3）,3.4,经典迭代法,第27页,写成,矩阵形式,：,A,=,L,U,D,B,Jacobi 迭代阵,(3.4.6),3.4,经典迭代法,第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,条件数、病态方程组与算法稳定性,第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,条件数、病态方程组与算法稳定性,第39页,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,稀疏矩阵计算,第41页,