回顾与补充：解线性方程的迭代方法 通知：下周四的作业将作为take-home midterm 回顾送代方程xk+1=Axk十b 令x为其中一个不动点 ·Xk+1-X*=A(xk-x*) ·xk-X=Ak(x0-x*) 什么时候收敛？ 对任意初始值xo,迭代方程xk+1=Axk+b都收敛到唯一的不动点 ·台Ak→0 ·台p(A)<1 也可能是因为x0选得好，使得xo一x,落在一个好的线性子空间里面 2
回顾与补充 ：解线性方程的迭代方法 通知：下周四的作业将作为take-home midterm 回顾迭代方程��"� = ��� + � 令�∗为其中一个不动点 • ��"� − �∗ = �(�� − �∗) • �� − �∗ = ��(�� − �∗) 什么时候收敛？ 对任意初始值��，迭代方程��#� = ��� + � 都收敛到唯一的不动点 • ⇔ �� → � • ⇔ � � < 1 也可能是因为��选得好，使得�� − �∗落在一个好的线性子空间里面 2
回顾与补充：解线性方程的迭代方法 考虑迭代方程xk+1=Axk+b 令x为其中一个不动点 ·Xk+1-X*=A(k-X*) ·Xk-X*=AK(x0-X*) 为什么Ak→0（即p(A)<1)的时候对任意初始值都收敛？ ·Ilxk-xl=Ak(xo-x)‖≤‖Alxo-x.川 ·xk=Axk-1+b=A(Axk-2+b)+b=… ·xk=Akx0+(Ak-1+Ak-2+…+）b =Akxo+(IA)-1(I-Ak)b 存在唯一的不动点：x*=Ax*十b→x*=(I-A)一1b 3
回顾与补充：解线性方程的迭代方法 考虑迭代方程��"� = ��� + � 令�∗为其中一个不动点 • ��"� − �∗ = �(�� − �∗) • �� − �∗ = ��(�� − �∗) 为什么�� → � （即� � < 1）的时候对任意初始值都收敛？ • �� − �∗ = ��(�� − �∗) ≤ �� �� − �∗ • �� = ���*� + � = � ���*� + � + � = ⋯ • �� = ���� + ��*� + ��*� + ⋯ + � � = ���� + � − � *� � − �� � • 存在唯一的不动点：�∗ = ��∗ + � ⇒ �∗ = � − � *�� 3
回顾与补充：解线性方程的迭代方法 考虑迭代方程xk+1=Axk+b 令x为其中一个不动点 ·Xk+1-X*=A(xk-x*) ·Xk-X*=Ak(x0-X*) 反过来，如果对任意初始值都收敛，为什么Ak→0（即p(A)<1)? 。 对任意初始值都收敛，即Vxo,xk-x*=Ak(x0一x*)→0 。 由于x0是任意的，x0一x*可以取到任意的向量 如果二个矩阵乘上任意一个向量，都是可以任意接近0的，则矩 阵必须是零矩阵 4
回顾与补充：解线性方程的迭代方法 考虑迭代方程��-� = ��� + � 令�∗为其中一个不动点 • ��-� − �∗ = �(�� − �∗) • �� − �∗ = ��(�� − �∗) 反过来，如果对任意初始值都收敛，为什么�� → � （即� � < 1）？ • 对任意初始值都收敛，即∀��, �� − �∗ = ��(�� − �∗) → � • 由于 ��是任意的， �� − �∗可以取到任意的向量 • 如果一个矩阵乘上任意一个向量，都是可以任意接近0的，则矩 阵必须是零矩阵 4
(对称)正定矩阵 如果对所有向量x≠0，xTAx>0,则称A为正定矩阵(positive definite matrix)。亦记为A>0 如果对所有向量x≠0，xTAx≥0，则称A为半正定矩阵(positive semidefinite matrix,.PSD matrix)。亦记为A≥0 要解Ax=b,理论上可以转化为解ATAx=ATb ·ATA≥0 ATA是对称的 如果A可逆，则ATA也可逆 但是条件数可能会变坏：2-条件数会变为原来的平方 定理：实数对称矩阵A是正定的，当且仅当其所有特征值为正 定理：实数对称矩阵A是半正定的，当且仅当其所有特征值为非负 5
（对称）正定矩阵 如果对所有向量� ≠ 0，�.�� > 0，则称�为正定矩阵(positive definite matrix)。亦记为� ≻ 0 如果对所有向量� ≠ 0，�.�� ≥ 0，则称�为半正定矩阵(positive semidefinite matrix，PSD matrix) 。亦记为� ≽ 0 要解�� = �，理论上可以转化为解�!�� = �!� • �!� ≽ 0 • �!�是对称的 • 如果�可逆，则�!�也可逆 • 但是条件数可能会变坏：2-条件数会变为原来的平方 定理：实数对称矩阵�是正定的，当且仅当其所有特征值为正 定理：实数对称矩阵�是半正定的，当且仅当其所有特征值为非负 5
正定矩阵与高斯消元 回顾：如果对矩阵一行一行地进行高斯消元，则存在 是下三角阵L,上三角阵U使得 A=LU L-1A=U 如果A是对称的话：对矩阵的行进行消元的每一步操作，对 矩阵的列也同样可以消元！ L-1A(L-1)T=? 若进一步假设A是正定的，则存在Cholesky2分解： A=CTC 其中C为上三角矩阵（对角线元素非零） 6
正定矩阵与高斯消元 回顾：如果对矩阵一行一行地进行高斯消元，则存在 是下三角阵�，上三角阵�使得 � = �� �'(� = � 如果�是对称的话：对矩阵的行进行消元的每一步操作，对 矩阵的列也同样可以消元！ �'(� �'( ) =? 若进一步假设�是正定的，则存在Cholesky分解： � = �)� 其中 �为上三角矩阵 （对角线元素非零） 6
正定矩阵与特征值 定理： 实数对称矩阵A是正定的，当且仅当其所有特征值为正。 证明： (=>)设λ∈R和非零向量满足A=λv,则由正定性， vTAv=λmv>0 又因为vv>0,因此λ>0。 (0 因此A是正定的。 7
正定矩阵与特征值 定理：实数对称矩阵�是正定的，当且仅当其所有特征值为正。 证明： (=>) 设 � ∈ �和非零向量�满足�� = ��，则由正定性， ���� = ���� > � 又因为��� > �，因此 � > �。 ( � 因此 �是正定的。 7
Loewner order 对于同样大小的实数对称矩阵A,B,如果A一 B≥0，也记为A≥B 个充分条件：A的最小特征值也比B的最大特征 值要大（或者一样天） 如果它们拥有同样的特征向量，则每个对应的特 征值都是大于等于的关系 注意：这仅仅是一个偏序(partial order) 8
Loewner order 对于同样大小的实数对称矩阵�, �，如果� − � ≽ 0，也记为� ≽ � 一个充分条件： �的最小特征值也比 �的最大特征 值要大（或者一样大） 如果它们拥有同样的特征向量，则每个对应的特 征值都是大于等于的关系 注意：这仅仅是一个偏序（partial order） 8
特征值特征向量 Av=Av 。 v为A的特征向量(eigenvector) λ为对应于特征向量v的特征值(eigenvalue) A的特征多项式(characteristic polynomial)为det(A-xI) det(A一xI)=0的零点是A的所有特征值 特征值的代数重数，algebraic multiplicity:作为重根出现的次数 特征值的几何重数，geometric multiplicity:对应的特征空间的维度 对于可对角化的矩阵，代数重数=几何重数 定理.令A为n×n实数对称矩阵.则存在正规正交(orthonormal)特征向量，它 们能张成R”,且所有特征值均为实数 9
特征值特征向量 �� = �� • �为�的特征向量 (eigenvector) • �为对应于特征向量�的特征值(eigenvalue) • �的特征多项式（characteristic polynomial ）为det � − �� • det � − �� = 0 的零点是�的所有特征值 特征值�的代数重数， algebraic multiplicity : �作为重根出现的次数 特征值�的几何重数， geometric multiplicity : �对应的特征空间的维度 对于可对角化的矩阵， 代数重数=几何重数 定理. 令 � 为�×�实数对称矩阵. 则存在正规正交（orthonormal）特征向量，它 们能张成��，且所有特征值均为实数 9
实数对称矩阵的谱分解 令A为m×m实数对称矩阵，V为正规正交 (orthonormal)的特征向量组成的矩阵 注意到VTV=I Av:=;y:→AV=VD→A=VDVT 10
实数对称矩阵的谱分解 令 � 为�×�实数对称矩阵， �为正规正交 （orthonormal）的特征向量组成的矩阵 注意到�6� = � ��7 = �7�7 ⇒ �� = �� ⇒ � = ���6 10
实数对称矩阵的谱分解 任意一个向量都可以表示成一组正规正交基{v}的线性组合 1-4呀 A:=→A=》时 A1=∑时， if A-1 exists. At=∑左明 i:入≠0 11
实数对称矩阵的谱分解 任意一个向量都可以表示成一组正规正交基 {�1} 的线性组合 � = ' 1 �1�1 2 ��1 = �1�1 ⇒ � = ' 1 �1�1�1 2 �34 = ' 1 �1 34�1�1 2 , �� �34 ������. �5 = ' 1:7#89 �1 34�1�1 2 11