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