数值分析9(迭代法收敛性证明)ppt课件.ppt
1/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人迭代法收敛性条件迭代法收敛性条件迭代误差估计定理迭代误差估计定理数值分析 92023/5/152/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人总结总结:矩阵范数矩阵范数算子范数算子范数 算子范数算子范数 矩阵矩阵1范数范数,矩阵无穷范数矩阵无穷范数,矩阵矩阵2范数范数3/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人例例4 设设|.|为为Rnn 上任意一种矩阵范数上任意一种矩阵范数,则对则对任意的任意的A Rnn,有有证明证明:例例5 设设|.|为为Rnn 上任意一种矩阵范数上任意一种矩阵范数,则对则对4/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人A X=b (MN)X=b M X=N X+b记记 (k)=X(k)X*(k=0,1,2,)则有则有 (k+1)=B (k)(k=0,1,2,)迭代格式迭代格式:X(k+1)=B X(k)+f (B=M-1N,f=M-1b)X(k+1)X*=B(X(k)X*)设方程组的精确解设方程组的精确解为为 X*,则有则有X*=B X*+f|(k+1)|=|B(k)|B|.|(k)|(k=0,1,2,)2023/5/155/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人迭代法构造迭代法构造收敛条件收敛条件中止准则中止准则2023/5/156/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人引理引理1 参考参考:P.832023/5/157/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人引理引理2 引理引理3 2023/5/158/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人证证:必要性必要性,设迭代法产生的序列设迭代法产生的序列X(k)收敛收敛,记记X*是该序列的极限点是该序列的极限点,则则X*=B X*+f。定理定理4.1 对对任意的任意的f和和任意的初始向量任意的初始向量X(0)迭代法迭代法 X(k+1)=B X(k)+f 收敛的收敛的充分必要充分必要条件是条件是由由X(0)的任意性知的任意性知 2023/5/159/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人充分性充分性 2023/5/1510/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 谱半径小于谱半径小于1是迭代收敛的充要条件是迭代收敛的充要条件,但它不但它不易计算易计算,所以在实际使用中通常并不好用所以在实际使用中通常并不好用。推论推论4.1 若若|B|1,则对任意的则对任意的f和任意的初始向量和任意的初始向量X(0)迭代法迭代法 X(k+1)=B X(k)+f 收敛。收敛。2023/5/1511/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人定理定理4.2 设设X*为方程组为方程组 AX=b 的解若的解若|B|0,记记 xTLTx=a,则有则有xTAx=xT(D L LT)x=p a a=p 2a 0设设 为为BGS的任一特征值的任一特征值,x 为其特征向量为其特征向量,则则2023/5/1520/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人所以迭代矩阵所以迭代矩阵 BGS 的谱半径的谱半径 (BGS)1,从而当从而当A 是实对称正定矩阵时是实对称正定矩阵时,Gauss-Seidel迭代法收敛。迭代法收敛。定理定理 方程组方程组 Ax=b 中中,若若 A 是实对称正定矩阵是实对称正定矩阵,则则Jacobi迭法收敛？迭法收敛？(反例反例)2023/5/1521/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人定理定理4.5 设设BJ元素均非负元素均非负,则下列关系有且则下列关系有且只有一个成立只有一个成立:参考文献参考文献:P.Stein,R.L.Rosenberg,On the solution of linear simultaneous equations by iteration,J.London Math.Soc.2023/5/1522/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人迭代法构造迭代法构造收敛条件收敛条件(局部局部vs全局全局)中止准则中止准则统一的不动点框架统一的不动点框架2023/5/1523/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人直接法直接法vs迭代法迭代法 基于高斯消元法的直接方法提供了基于高斯消元法的直接方法提供了有限步有限步内内就可以得到解的方法。就可以得到解的方法。寻求迭代方法的理由是什么呢？寻求迭代方法的理由是什么呢？十阶十阶 百阶百阶 万阶万阶 百万阶百万阶 亿阶亿阶 小小 不大不大 较大较大 大大 超大超大2023/5/1524/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人迭代法优势迭代法优势1:直接法运行一个完整直接法运行一个完整LU分解才能得到解分解才能得到解,迭迭代法从初始解开始每步对其加工改善使其更加代法从初始解开始每步对其加工改善使其更加精确。问题是在用户容忍的范围内需要多少步精确。问题是在用户容忍的范围内需要多少步才能得到收敛性才能得到收敛性？注释注释:运行一个完整运行一个完整LU分解花费分解花费O(n3)阶运算阶运算,一一般地般地,迭代法每次迭代花费迭代法每次迭代花费O(n2)阶运算阶运算,即即每次每次迭代仅需要完整迭代仅需要完整LU分解花费的一部分。分解花费的一部分。2023/5/1525/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人迭代法优势迭代法优势2:求解稀疏方程组是使用迭代法的主要理由。求解稀疏方程组是使用迭代法的主要理由。注释注释:系数矩阵稀疏度为系数矩阵稀疏度为n,则求解稀疏方程组则求解稀疏方程组迭代法每步迭代花费迭代法每步迭代花费O(n)阶阶运算。求解特殊结运算。求解特殊结构方程组构方程组(如如Toeplitz)迭代法每步迭代花费迭代法每步迭代花费O(nlogn)阶阶运算。运算。2023/5/1526/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人Poisson方程方程:令令 h=1/(n+1),xi=ih(i=0,1,n+1)记记 ui=u(xi),(i =0,1,n+1)迭代计算格式迭代计算格式:差分格式差分格式:27/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人n=10000;e=ones(n,1);A=spdiags(e-2*e e,-1:1,n,n),spy(A)28/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 HB矩阵稀疏模式矩阵稀疏模式来源来源 The original Harwell-Boeing collection来源来源:The University of Florida Sparse Matrix Collection29/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 FreeFieldTechnologies矩阵稀疏模式矩阵稀疏模式来源来源3D vibro-acoustic problem,aircraft engine nacelle30/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 vanHeukelum矩阵稀疏模式矩阵稀疏模式 来源来源DNA electrophoresis31/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 garon2矩阵稀疏模式矩阵稀疏模式 2D FEM,Navier-Stokes,CFD32/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 n=10000;e=ones(n,1);n2=n/2;a=spdiags(-e 3*e-e,-1:1,n,n);c=spdiags(e/2,0,n,n);c=fliplr(c);a=a+c;a(n2+1,n2)=-1;a(n2,n2+1)=-1;b=zeros(n,1);b(1)=2.5;b(n)=2.5;b(2:n-1)=1.5;b(n2:n2+1)=1;%Jacobi Method(Iterative Method)ticd=diag(a);%extract diagonal of ar=a-diag(d);%r is the remainderx=zeros(n,1);%initialize vector xfor j=1:50%loop for Jacobi iterationx=(b-r*x)./d;endt1=toctic,x=full(a)b,t2=toc%Back Slash(Direct Method)Demo133/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 help sparfunMatlab与大数据处理与大数据处理Elementary sparse matrices(例如例如spdiags)Full to sparse conversion(例如例如sparse)Working with sparse matrice(例如例如nnz,spy)Linear algebra(例如例如svds,ilu,eigs)Linear equations(iterative methods)(例如例如pcg)2023/5/1534/34烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人烧伤病人的治疗通常是取烧伤病人的健康皮肤进行自体移植，但对于大面积烧伤病人来讲，健康皮肤很有限，请同学们想一想如何来治疗该病人 The Curse of DimensionalityThe Blessing of Sparsity2023/5/15
