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

1、Ch3 线性方程组求解的数值方法Numerical Solutions of Systems of Linear Equations 3.0 Introduction线性方程组线性方程组工程问题工程问题（电子网络，船体放样等）（电子网络，船体放样等）自然科学自然科学（实验数据的最小二乘法曲线拟合）（实验数据的最小二乘法曲线拟合）解非线性方程组解非线性方程组解常解常/偏微分方程组偏微分方程组（差分法，有限元法）（差分法，有限元法）3.0 Introduction线性方程组的线性方程组的系数矩阵系数矩阵：（1）低价稠密矩阵（阶数）低价稠密矩阵（阶数 L,U,P=lu(A)其中其中njiaallll

2、lllLjjjjijijnnn,1,1111321323121【作业作业】P.67 题题1,23.1.3 3.1.3 选主元消去法选主元消去法 /*Pivoting Strategies*/例：例：单精度解方程组单精度解方程组 211021219xxxx/*精确解为精确解为 和和 */.1000.00.1101191 x8个个.8999.99.0212 xx8个个用用Gaussian Elimination计算：计算：911212110/aam999212210101010.0.011 ma8个个92121012 mb 9991010011100,112 xx小主元小主元/*Small piv

3、ot element*/可能导致计可能导致计算失败。算失败。3.1 Gaussian Elimination and LU Decomposition 全主元消去法全主元消去法/*Complete Pivoting*/每一步选绝对值最大的元素为主元素，保证每一步选绝对值最大的元素为主元素，保证 。1|ikmStep k:选取选取;0|max|,ijnjikjiaakk If ik k then 交换第交换第 k 行与第行与第 ik 行行;If jk k then 交换第交换第 k 列与第列与第 jk 列列;消元消元列交换改变了列交换改变了 xi 的顺序，须记录的顺序，须记录交换次序交换次序，解

4、完后，解完后再换回来。再换回来。列主元消去法列主元消去法/*Partial Pivoting,or maximal column pivoting*/省去换列的步骤，每次仅选一列中最大的元。省去换列的步骤，每次仅选一列中最大的元。0|max|,iknikkiaak3.1 Gaussian Elimination and LU Decomposition例：例：211111091,112 xx 110211 11102119 列主元法没有全主元法稳定。列主元法没有全主元法稳定。0,112 xx例：例：2111010199 99991010010101注意：这两个方程组注意：这两个方程组在数学上在

5、数学上严格等价严格等价。标度化列主元消去法标度化列主元消去法/*Scaled Partial Pivoting*/对每一行计算对每一行计算 。为省时间，。为省时间，si 只在初始时计只在初始时计算一次。以后每一步考虑子列算一次。以后每一步考虑子列 中中 最大的最大的 aik 为主元。为主元。|max1ijnjias nkkkaa.iiksa稳定性介于列主元法和全主元法之间。稳定性介于列主元法和全主元法之间。3.1 Gaussian Elimination and LU Decomposition实际应用中直接调用实际应用中直接调用Gauss Elimination 解解3 3阶线性方程阶线性方

6、程组的结果：组的结果：结合全主元消去后的结合全主元消去后的结果：结果：3.1 Gaussian Elimination and LU Decomposition3.2 Cholesky分解分解【Matlab】设设A是是对称正定对称正定矩阵，则矩阵，则A有以下形式的有以下形式的LU分解：分解：A=PTP （3.2.1）其中其中P是一个上三角矩阵是一个上三角矩阵,上式称为上式称为A的的Cholesky分解分解(Choleskian decomposition).P=chol(A)定理定理【作业作业】P.68 题题43.3 向量范数与矩阵范数向量范数与矩阵范数 误差的度量误差的度量3.3.1 向量范

7、数向量范数 (vector norms)常用向量范数：常用向量范数：,|11nixx,|2/1122nixx.|max1inixx这些范数满足：这些范数满足：;0 ifonly and if 1 and ,0 )1(xxx;constantany is ,)2(xx.)3(yxyx|limxxpp一般范数：一般范数：如，设如，设向量向量 x=(2,-4,-1)T,则则,21|2/1122nixx,7|11nixx.4|max1inixx3.3 3 向量范数与矩阵范数向量范数与矩阵范数【Matlab】x=(1:4)/5N1=norm(x,1)N2=norm(x)N7=norm(x,7)Ninf=

8、norm(x,inf)x=0.2000 0.4000 0.6000 0.8000N1=2N2=1.0954N7=0.8153Ninf=0.8000定义定义 矩阵矩阵A A的范数定义为的范数定义为3.3 3 向量范数与矩阵范数向量范数与矩阵范数3.3.2 矩阵范数矩阵范数 (matrix norms).max0 xAxAx 命题：命题：矩阵的常用范数：矩阵的常用范数：;|max )1(111niijnjaA;|max )2(11njijniaA,)(max )3(12AAATini其中，其中，1,n是是AAT的特征值，的特征值，iniTAA1max:)(称为称为 的的谱半径谱半径。AAT例例 设

9、矩阵设矩阵3.3 3 向量范数与矩阵范数向量范数与矩阵范数,4321A;6|max )1(111niijnjaA;7|max )2(11njijniaA.46.522115)(max )3(12AAATini则则可以证明可以证明，矩阵范数满足：，矩阵范数满足：;0 ifonly and if 0;0 (1)AAA;|c|(2)AcA;(3)BABA(4).ABAB3.4 经典迭代法经典迭代法Jacobi迭代法与迭代法与Gauss-Seidel迭代法迭代法3.4.1Jacobi迭代法迭代法设有设有n阶方程组阶方程组nnnnnnnnnnbxaxaxabxaxaxabxaxaxa2211222221

10、2111212111(3.4.1)若系数矩阵非奇异，且若系数矩阵非奇异，且 (i=1,2,n)，将方程组将方程组0iia11,221112323121222213132121111111nnnnnnnnnnnnnxaxaxabaxxaxaxabaxxaxaxabax（4.1）改写成改写成3.4 经典迭代法经典迭代法然后写成迭代格式然后写成迭代格式)(11,)(22)(11)1()(2)(323)(121122)1(2)(1)(313)(212111)1(1111knnnknknnnnknknnkkkknnkkkxaxaxabaxxaxaxabaxxaxaxabax（3.4.2）（3.4.2）式

11、也可以简单地写为式也可以简单地写为),2,1(1)(1)1(nixabaxkjnijjijiiiki（3.4.3）3.4 经典迭代法经典迭代法写成写成矩阵形式矩阵形式：A=LUDBfJacobi 迭代阵迭代阵bDxULDxkk1)(1)1()(3.4.6)bxULxDbxULDbxA )()(bDxULDx11)(3.4 经典迭代法经典迭代法)(11)(1)(414)(313)(21211)1(1bxaxaxaxaaxknnkkkk )(12)(2)(424)(323)1(12122)1(2bxaxaxaxaaxknnkkkk )(13)(3)(434)1(232)1(13133)1(3bxa

12、xaxaxaaxknnkkkk )(1)1(11)1(33)1(22)1(11)1(nknnnknknknnnknbxaxaxaxaax 只存一组向量即可。只存一组向量即可。写成写成矩阵形式矩阵形式：bDxUxLDxkkk1)()1(1)1()(bxUxLDkk )()1()(bLDxULDxkk1)(1)1()()(BfGauss-Seidel 迭代阵迭代阵3.4.2 Gauss-Seidel迭代法迭代法(3.4.7)3.4 经典迭代法经典迭代法定理定理3.1 对任意初始向量对任意初始向量X(0)及常向量及常向量F，迭代格式迭代格式(3.5.1)FBXXkk)1(3.5.1)推论推论：若迭代

13、矩阵若迭代矩阵的的某种范数某种范数 ，则则（3.5.1）1B收敛的充分必要条件是迭代矩阵收敛的充分必要条件是迭代矩阵B B的谱半径的谱半径(B)1)（此时矩阵也称为“病态矩阵”）的线性方程组Ax=b是病态的；反之，系数矩阵的条件数很小的线性方程组Ax=b是良态的。A=hilb(n);c=cond(A)Example:Example:著名的Hilbert 矩阵是病态的。【Matlab】3.7 7条件数、病态方程组与算法的稳定性条件数、病态方程组与算法的稳定性 定理定理3.6 (条件数的性质条件数的性质)设A 是一个非奇异矩阵.(1)cond(A)1,cond(A)=cond(A-1),con(a

14、A)=cond(A),a 0.(2)如果 Q是正交矩阵，则 cond2(Q)=1,cond2(A)=cond2(QA)=cond2(AQ),其中cond2(A)=|A-1|2|A|2.3.7 7条件数、病态方程组与算法的稳定性条件数、病态方程组与算法的稳定性3.8 稀疏矩阵的计算稀疏矩阵的计算.4114114121121nnbbbMMM例例 （比较比较稀疏矩阵算法稀疏矩阵算法与与普通矩阵算法普通矩阵算法：机器时间与：机器时间与占用空间占用空间）考虑线性方程组考虑线性方程组%sparse and full matrixn=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=toctic;y=b/rh;t2=toc【实验要求】逐步增大n的值，观察发生的现象。3.8 稀疏矩阵的计算稀疏矩阵的计算