回顾与补充 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