南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法8

回顾与补充 Richardson iteration 一两个视角:矩阵多项式、梯度最速下降 一思考:如果换作其它范数下面的最速下降? - 收敛性:当且仅当p(I-aA)=max{1-a元1l,|1-anl}<1 -记xk=pk(A)b∈Span{b,Ab,A2b,,Ak-1b}:Krylov子空间 -x.-xk=(I-pk(A)A)x.=qk(A)x. 一收敛所需迭代次数正比于条件数 Conjugate gradients(共轭梯度方法) -记Krylov-子空间K0={0,K:=span{b,Ab,.Ai-1b} -xi=arg minx∈K,lx-x*l☑,其中x满足Ax*=b C6的收敛所需选代次数正比于层依然取决于条件数 - 精确数值:最多迭代+1次;有限精度:也需要选择合适的停止条件 对稀疏矩阵,或者有好的初始猜测时,迭代比高斯消元更加适合 2
回顾与补充 • Richardson iteration – 两个视角:矩阵多项式、梯度最速下降 – 思考:如果换作其它范数下面的最速下降? – 收敛性:当且仅当� � − �� = max{ 1 − ��! , 1 − ��" } < � – 记�� = �� � � ∈ ���� �,��,���, … ,��#�� ;Krylov子空间 – �∗ − �� = � − �� � � �∗ = �� � �∗ – 收敛所需迭代次数正比于条件数�� �� • Conjugate gradients (共轭梯度方法) – 记Krylov子空间�� = � , �� = ���� �, ��, … ��#�� – �� = ��� ����∈�� � − �∗ � � ,其中�∗满足��∗ = � – CG的收敛所需迭代次数正比于 �� �� ,依然取决于条件数 – 精确数值:最多迭代n+1次;有限精度:也需要选择合适的停止条件 • 对稀疏矩阵,或者有好的初始猜测时,迭代比高斯消元更加适合 2

预条件Preconditioning) 要解Ax=b,选取矩阵M,改为解M-1Ax=M-1b comd(M-1A)≠cond(A) 注意:Richardson iteration和cG都需要正定矩阵 M-1A可能不再是正定的,甚至可能不是对称的 假设M是对称正定,则有Cholesky分解:M=EET,并且 cond(M-1A)=cond(E-1AE-T) 3
预条件(Preconditioning) 要解�� = �,选取矩阵�,改为解�!"�� = �!"� ���� �!"� ≠ ���� � 注意:Richardson iteration和CG都需要正定矩阵 �!"�可能不再是正定的,甚至可能不是对称的 假设�是对称正定,则有Cholesky分解: � = ���,并且 ���� �!"� = ���� �!"��!$ 3

预条件(Preconditioning) 假设M是对称正定,则有Cholesky2分解:M=EET,并且 cond(M-1A)=cond(E-1AE-T) 证明:E-1AE-T是对称正定的,有完整的特征基,因此只 需要证明M1A和E一1AE-T有着一样的特征值即可。任取 E-1AE-T的特征向量和特征值 E-1AE-Tv=1v→E-TE-1AE-Tv=λE-Tv→M-1Ay ly 因为它们的奇异值一样,它们的条件数也是一样的 因此,可以先解E-1AE-Ty=E-1b,这是对称正定的系统 然后解得x=E-Ty 4
预条件(Preconditioning) 假设�是对称正定,则有Cholesky分解: � = ���,并且 ���� �34� = ���� �34��35 证明: �34��35是对称正定的,有完整的特征基,因此只 需要证明�34�和 �34��35有着一样的特征值即可。任取 �34��35的特征向量和特征值 �34��35� = �� ⇒ �35�34��35� = ��35� ⇒ �34�� = �� 因为它们的奇异值一样,它们的条件数也是一样的 因此,可以先解�34��35� = �34�,这是对称正定的系统 然后解得� = �35� 4

计算特征值与特征向量 最小化f(x)=xrAx,subject to xx=1 det(xl-A):关于x的多项式 ·n个根,A的特征值 可能不稳定:多项式(x-1)(x-2).(x-20) 注:det(几I一A)非常接近0并不意味着是一个近似特征值 。 牛顿法求根:需要导数 截弦法求根:也需要计算det(xl-A) 迭代法? ·解Ax=b:写出不动点方程,使用不动点迭代 解Ax=x:同时有两个变量:λ和x 5
计算特征值与特征向量 最小化� � = ��� �, subject to �5� = 1 det(�� − �):关于�的多项式 • n个根, �的特征值 • 可能不稳定:多项式 � − � � − � . . (� − ��) • 注:��� �� − � 非常接近0并不意味着�是一个近似特征值 • 牛顿法求根:需要导数 • 截弦法求根:也需要计算det(�� − �) 迭代法? • 解�� = �:写出不动点方程,使用不动点迭代 • 解�� = ��:同时有两个变量: �和� 5

对特征值的估计 Gershgorin circle theorem ·令A为nxn矩阵,Ri=∑itiai 则A的所有特征值都在复平面上的某个圆盘D(αi,R) 之中 证明:任取A的一个特征值对应特征向量v,设i使得v:为 v中绝对值最大的元素。 由Av=λv→∑jajy;=1v1→∑iziaijVi=(⑦-ai)vi 因此 I(a-a)I= 2=s= ii 6
对特征值的估计 Gershgorin circle theorem • 令 �为�×�矩阵, �� ≔ ∑�#� ��� • 则 �的所有特征值都在复平面上的某个圆盘 �(���,��) 之中 证明:任取�的一个特征值�对应特征向量�,设�使得�6为 � 中绝对值最大的元素。 由�� = �� ⇒ ∑7 �67 �7 = ��6 ⇒ ∑786 �67�7 = � − �66 �6 因此 � − �66 = B 786 �67�7 �6 ≤ B 786 �67�7 �6 ≤ B 786 �67 = �6 6

幂迭代Power method 青可个特征低:食设爸毫製鞋先头锅 满足24>22l≥123≥…≥ ·21被称为占优特征值(dominating eigenvalue) ·v1:占优特征向量 考虑任意向量x∈R”,,由于v1,v2,,vn是线性无关的,所以可以展开 x=a1v1+2v2+…+anVn Ax=Ala1v1+A2a2v2 +.Ananvn A2x=Aja1v1+zazv2+..+AnanVn A3x=11v1+12a22+…+13anvn Akx=afa1vi+afa2v2 ++akanvn = 格 1v1+ 2++ anVn 随着k→0,Akx→a11,如果1≠0 7
幂迭代 Power method 考虑可对角化的方阵�. 假设�有�个特征值��, ��, … , ��满足 �� > �� ≥ �� ≥ ⋯ ≥ �� 。记它们对应的特征向量为��, ��, … , ��。假设它们是线性无关的。 • ��被称为占优特征值 (dominating eigenvalue) • ��:占优特征向量 考虑任意向量� ∈ ��,由于��, ��, … , ��是线性无关的,所以可以展开 � = ���� + ���� + ⋯ + ���� �� = ������ + ������ + ⋯ + ������ ��� = �� ����� + �� ����� + ⋯ + �� ����� ��� = �� ����� + �� ����� + ⋯ + �� ����� ⋮ ��� = �� ����� + �� ����� + ⋯ + �� ����� = �� � ���� + �� � �� � ���� + ⋯ + �� � �� � ���� 随着� → ∞, ��� → �� �����,如果�� ≠ � 7

幂迭代Power method Akx=afaivi+akazv2 +..akanvn = a41+2+…+蓉 随着k→o,Akx→a1v1,如果x1≠0 收敛速度:22l/21 可能导致浮点数上溢或下溢:如果21l>1,Akx→o;如果|1l<1,Akx→0 解决办法:每次迭代都进行归一化 Wk+1=Axk, Xk+1= Wk+1 llwk+1ll 思考:归一化可以使用什么样的范数?为什么不除上进行归一化? 8
幂迭代 Power method ��� = �� ����� + �� ����� + ⋯ + �� ����� = �� � ���� + �� � �� � ���� + ⋯ + �� � �� � ���� 随着� → ∞, ��� → �� �����,如果�� ≠ � 收敛速度: �� / �� 可能导致浮点数上溢或下溢:如果|��| > �, ��� → ∞; 如果 �� < � , ��� → � 解决办法:每次迭代都进行归一化 ��&� = � �� , ��&� = ��&� ��&� . 思考:归一化可以使用什么样的范数?为什么不除上�� �进行归一化? 8

Power method Akx afa1vi+asa2v2 +.+ahanvn 选 =(a41+++好 随着k→∞,Akx→a1v1 随着幂迭代的进行,得到了一个近似的特征向量方向之后,如何求解近似的 特征值? 即,给定A和近似特征向量x,求使得Ax≈λx 最小二乘法:求以最小化lAx-x|陉 IlAx-x陉=I‖lAxl陉+λ2Ilx2-2xTAx 法线方程)=xTAx/xrx,Rayleigh quotient! 练习:使用扰动方法,从Ax-(L+62)x陉≥‖Ax-1x2,H62∈R推导
Power method ��� = �� ����� + �� ����� + ⋯ + �� ����� = �� � ���� + �� � �� � ���� + ⋯ + �� � �� � ���� 随着� → ∞,��� → �� ����� 随着幂迭代的进行,得到了一个近似的特征向量方向之后,如何求解近似的 特征值? 即,给定�和近似特征向量�,求�使得�� ≈ �� 最小二乘法: 求�以最小化 �� − �� � � �� − �� � � = �� � � + �� � � � − ������ 法线方程� = ����/���, Rayleigh quotient! 练习:使用扰动方法,从 �� − (� + ��)� � � ≥ �� − �� � � , ∀�� ∈ �推导 9

Power method 最小二乘法:求以最小化Ax-x匠 IAx-1xl匠=|Ax匠+22Ix匠-2xAx 法线方程=xTAx/xTx,Rayleigh quotient! 定理:对于实数对称矩阵A,假设近似特征向量x满足lxl2=1,并且实数1满足IAx-xl2‖Ax-xl2≥mim1ssn- 10
Power method 最小二乘法: 求�以最小化 �� − �� � � �� − �� � � = �� � � + �� � � � − ������ 法线方程� = ����/���, Rayleigh quotient! 定理:对于实数对称矩阵�,假设近似特征向量�满足 � � = �,并且实数�满足 �� − �� � �� − �� � ≥ ����$�$� �� − � 10

Inverse Power method 幂迭代告诉我们如何找到1与1 其它特征值和特征向量呢? 给定方阵A.假设A有n个特征值1,几2,.,入和线性无关的特征向量 为1,)2,…,Vn A-1的特征值? 11 1 特征向量? )1,02,…,Vn 迭代需要使用到A一1?只需要解线性方程:U分解 11
Inverse Power method 幂迭代告诉我们如何找到��与�� 其它特征值和特征向量呢? 给定方阵�. 假设�有�个特征值��, ��, … , ��和线性无关的特征向量 为��, ��, … , �� �$�的特征值? � �� , � �� , … , � �� 特征向量? ��, ��, … , �� 迭代需要使用到�3�?只需要解线性方程:LU分解 11
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法7.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)正定矩阵、Courant-Fischer特征值的min-max刻画、矩阵的多项式.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)解线性方程组的直接和迭代方法、条件数、算子范数(operator norm).pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)傅里页变换、三角插值.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)Chebyshev多项式插值、函数逼近与正交多项式、最小二乘法与最佳平方逼近.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)牛顿法、插值.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)浮点数、求解方程的根(主讲:刘景铖).pdf
- 南京大学:《概率论与数理统计 Probability and Statistics》课程教学资源(试卷习题)2017-2018学年第一学期(A卷).pdf
- 南京大学:《概率论与数理统计 Probability and Statistics》课程教学资源(试卷习题)2016-2017学年第一学期(A卷).pdf
- 深圳大学:《数理方程与特殊函数》课程教学资源(参考资料)专业名词术语.pdf
- 深圳大学:《数理方程与特殊函数》课程教学资源(教学大纲)Physical-Mathematical Equations and Special Functions.pdf
- 上饶师范学院:《概率论与数理统计》课程教学资源(学习指导)疑难分析与例题解析(主讲:李永明).doc
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第八章 方差分析和回归分析 §8.2 线性回归分析的数学模型.ppt
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第八章 方差分析和回归分析 §8.1 方差分析.ppt
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第七章 假设检验 §7.4 非参数假设检验.ppt
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第七章 假设检验 §7.3 正态母体参数的置信区间.ppt
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第七章 假设检验 §7.2 参数假设检验.ppt
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第七章 假设检验 §7.1 假设检验的基本思想和概念.ppt
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第六章 点估计 §6.5 罗—勃拉克维尔定理和一致最小方差无偏估计.ppt
- 上饶师范学院:《概率论与数理统计》课程教学资源(PPT课件)第六章 点估计 §6.4 充分统计量.ppt
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法10.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法9.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法11.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法12.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法13.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法14.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法15.pdf
- 南京大学:《计算方法 Numerical method》课程教学资源(课件讲稿)计算方法16.pdf
- 西安电子科技大学:《线性代数》课程教学资源(教学大纲)Linear Algebra(主讲:李仁先).docx
- 西安电子科技大学:《线性代数》课程教学资源(课件讲义)线性代数讲义(第1-3章).pdf
- 西安电子科技大学:《线性代数》课程教学资源(课件讲义)线性代数讲义(第4-8章).pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)集合论——第7章 集合的基数.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)计数与离散概率——第10章 基本计数技术.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)集合论——第9章 归纳与递归.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)关系——第12章 关系及其运算.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)集合论——第8章 数论初步.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)计数与离散概率——第11章 离散概率.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)代数系统——第15章 代数系统.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)关系——第13章 关系的闭包、等价关系.pdf
- 南京大学:《离散数学 Discrete Mathmatics》课程教学资源(课件讲稿,2018)代数系统——第16章 群论导引.pdf