回顾 矩阵多项式的特征空间：p(A)v=p()v -A→卫(A) -特征空间{1,2，…，1n}→{p(1),p(2),…,p(n} ·(Cayley-Hamilton)存在n次多项式p(A)使得 p(A)A=I -记q(x)=1-xp(x) -则n次多项式q4(x)=det(A-xI)满足q(A)=0 -非平凡的：注意det(A-x)仅仅为一个数 2
回顾 • 矩阵多项式的特征空间：� � � = �(�)� – � → � � – 特征空间 �!, �", ⋯ , �# → � �! , � �" , ⋯ , � �# • (Cayley-Hamilton)存在n次多项式� � 使得 � � � = � –记� � = � − �� � –则�次多项式�' � = det(� − ��)满足� � = � –非平凡的：注意det(� − ��)仅仅为一个数 2
Cayley-Hamilton 考虑关于x的n次多项式q4(x)=det(A-xI) 定理(Cayley--Hamilton小：q4(A)=0为全零矩阵 注意q4(0)=det(A)丰0 A~1= (-1)n-1 det(A) (An-1+Cn-1An-2+…+C1) A-1=P(A) 如何计算q(x)?高斯消元？ 3
Cayley-Hamilton 考虑关于�的�次多项式�! � = det(� − ��) 定理(Cayley-Hamilton): �� � = �为全零矩阵 注意�! 0 = det � ≠ � �#� = −� �#� det � (��#� + ��#���#� + ⋯ + ���) �#� = �(�) 如何计算 � � ? 高斯消元？ 3
Richardson iteration 个特殊情形：给定实数0<a<1,如何用a表示出a-1b? b b+(1-a)b+(1-a)2b+…=1-(1-a =a-1b 等价于x0=0,xk+1=(1一a)xk+b Richardson iteration(对于对称正定的矩阵A): x0=0 Xk+1=(I-aA)xk+ab=xk-a(Axk-b) 4
Richardson iteration 一个特殊情形: 给定实数0 < � < 1, 如何用 � 表示出�!"�? � + 1 − � � + 1 − � !� + ⋯ = � 1 − 1 − � = �"#� 等价于�� = �, ��%� = (� − �)��+ � Richardson iteration（对于对称正定的矩阵�）: �� = � ��%� = (� − ��)�� + � � = �� − �(��� − �) 4
Richardson iteration 一个特殊情形：给定实数0<a<1,如何用a表示出a~1b? b b+(1-ab+1-02b+=1-1-0=a4b 等价于x0=0,xk+1=(1-a)xk+b Richardson iteration: x0=0 Xk+1=(I-aA)xk+a b=xk-a(Axk-b) 矩阵多项式的视角：特征空间：p(A)v=p()v -A→p(A) -特征空间1,2，…，n}→{p(21),p(22),…,p(2n)} 另一个视角：对于对称的A,这正好是目标函数xAx一bTx的梯度下降方法！ (xAx-bTx)-i(A+4)x-b 5
Richardson iteration 一个特殊情形: 给定实数0 < � < 1, 如何用 � 表示出�!"�? � + 1 − � � + 1 − � !� + ⋯ = � 1 − 1 − � = �"#� 等价于�� = �, ��%� = (� − �)��+ � Richardson iteration: �� = � ��%� = (� − ��)�� + � � = �� − �(��� − �) 矩阵多项式的视角：特征空间：� � � = �(�)� – � → � � – 特征空间 �#, �!, ⋯ , �$ → � �# , � �! , ⋯ , � �$ 另一个视角: 对于对称的 �, 这正好是目标函数� � ���� − ���的梯度下降方法! � � � ���� − ��� = � � � + �� � − � 5
An Optimization Perspective 给定连续可导f:R”→R,最小化f 例子： 最小二乘法：f(x)=‖Ax-b陉 向量投影：fo)=lca- 求伪逆(Pseudoinverse):f(x)=lxll陉，subject to Ax=b 对称矩阵的特征值：f(x)=xTAx,subject to xx=1 线性规划：f(x)=cx,subject to Ax≥b 主成分分析(Principal component analysis)):f(C)=‖X-CCTX‖e,subject to C CT laxd 离散组合优化：、最小生成树，最小割、最大流（网络流），最短路径，最大 匹配；最大独立集、团、支配集，最小覆盖，背包问题，最大割，max-SAT, 旅行商问题，最长路径（哈密顿路径）… 6
An Optimization Perspective 给定连续可导�: ℝ! → ℝ, 最小化� 例子： 最小二乘法：� � = �� − � � � 向量投影： � � = � � − � � � 求伪逆(Pseudoinverse)： � � = � � �, subject to � � = � 对称矩阵的特征值： � � = ��� �, subject to �"� = 1 线性规划： � � = ���, subject to �� ≥ � 主成分分析 (Principal component analysis)： � � = � − ���� � , subject to � �" = �#×# 离散组合优化：最小生成树，最小割、最大流（网络流），最短路径，最大 匹配；最大独立集、团、支配集，最小覆盖，背包问题，最大割，max-SAT， 旅行商问题，最长路径（哈密顿路径）…… 6