南京大学：《计算方法 Numerical method》课程教学资源（课件讲稿）计算方法7

回顾 矩阵多项式的特征空间：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

Optimality notion 给定连续可导f:R”→R,最小化f x是一个全局最优解Global minimum),如果f(x)≥ f(x;),Vx x,是一个局部最优解Local minimum),如果6> 0,x:lx-x*<6,均有f(x)≥f(x*) 7

Optimality notion 给定连续可导�: ℝ' → ℝ, 最小化� �∗是一个全局最优解(Global minimum)，如果� � ≥ � �∗ , ∀� �∗是一个局部最优解(Local minimum)，如果∃� > 0, ∀�: � − �∗ < �, 均有� � ≥ � �∗ 7

Optimality condition from calculus 给定连续可导f:R”→R,和一个点xo r=( ofof ∂f f(x)≈f(xo)+f(xo)·(x-xo), x 特别地， 可以选取x-x,=a(f(xo) f(xo+a(vf(xo)))-f(xo)=allvf(xo)Il 当a足够小的时候，的符号决定f局部的增减性 当Vf(xo)=0,则点xo为驻点(stationary point) 此时需要看二阶导数 8

Optimality condition from calculus 给定连续可导�: ℝ: → ℝ, 和一个点 �; ∇� � ≔ �� ��# , �� ��! , … , �� ��: � � ≈ � �; + ∇� �; ⋅ � − �; , ∀� 特别地，可以选取� − �; = � ∇� �; < � �; + � ∇� �; < − � �; ≈ � ∇� �; ! ! 当�足够小的时候，�的符号决定�局部的增减性 当 ∇� �; = 0，则点 �;为驻点(stationary point) 此时需要看二阶导数 8

Optimality condition from calculus 给定连续可导f:R”→R 82f of 82f Oa 0x18x2 Ox1 6xn of 82f 82f Hf二 0x20x1 0z号 8x20n 82f 8f 82f 82n Ox1 0xn∂x2 0r品 通常也把Hessian?矩阵Hr记作V2f 9

Optimality condition from calculus 给定连续可导�: ℝ' → ℝ 通常也把Hessian矩阵�)记作 ∇*� 9

Optimality condition from calculus 给定连续可导f:R”→R,x f(x)≈f(xo)+Vf(xo)·(x-xo) +(x-x0)T H(xo)(x-xo) 如果Vf(xo)=0 H(xo)>0:局部最小 Hr(xo)<0:局部最大 Hr(xo)同时有正的和负的特征值：saddle point Hr(xo)不可逆：不一定是局部极值(Morse theory) 10

Optimality condition from calculus 给定连续可导�: ℝ' → ℝ, ∀� � � ≈ � �+ + ∇� �+ ⋅ � − �+ + 1 2 � − �+ , �) �+ (� − �+) 如果 ∇� �+ = 0 �) �+ ≻ 0: 局部最小 �) �+ ≺ 0: 局部最大 �) �+ 同时有正的和负的特征值：saddle point �) �+ 不可逆：不一定是局部极值 (Morse theory) 10

Convexity 如果给定的不仅仅是一个点上的导数，而是一个邻域上导数 的信息，那么判断标准可以有所简化。 例子：凸函数(convex function) 1.0 0.5 0.8 0.6 0.4 0.2 -0.5 11

Convexity 如果给定的不仅仅是一个点上的导数，而是一个邻域上导数 的信息，那么判断标准可以有所简化。 例子：凸函数(convex function) 11