跳到主要内容

東京工業大学 情報理工学院 数理・計算科学系 2016年8月実施 午前 問A

标签：

Author​

祭音Myyura (co-authored with GPT 5.6 SOL)

Description​

nn 次実対称行列 A∈Rn×nA\in\mathbb R^{n\times n} と b∈Rnb\in\mathbb R^n に対して、

f(x)=12xTAx−bTxf(x)=\frac12x^{\mathsf T}Ax-b^{\mathsf T}x

と定める。ただし、xTx^{\mathsf T} はベクトル xx の転置を表す。

(1) AA が正定値、すなわち任意の x∈Rnx\in\mathbb R^n、x≠0x\ne0 に対して xTAx>0x^{\mathsf T}Ax>0 なら、ff の最小点が存在し、一意であることを示せ。

(2) AA が半正定値、すなわち任意の x∈Rnx\in\mathbb R^n に対して xTAx≥0x^{\mathsf T}Ax\geq0 であり、rank⁡A=k\operatorname{rank}A=k（1≤k<n1\leq k<n）とする。ff の最小点の集合を SS とし、任意の x∗∈Sx^*\in S に対して

Sx∗={s−x∗∣s∈S}S_{x^*}=\{s-x^*\mid s\in S\}

と定める。Sx∗S_{x^*} が Rn\mathbb R^n の線形部分空間であることを示せ。

(3) dim⁡Sx∗\dim S_{x^*} を n,kn,k で表せ。

题目描述​

设 A∈Rn×nA\in\mathbb R^{n\times n} 是 nn 阶实对称矩阵，b∈Rnb\in\mathbb R^n，定义实二次函数

f(x)=12xTAx−bTx.f(x)=\frac12x^{\mathsf T}Ax-b^{\mathsf T}x.

这里 xTx^{\mathsf T} 表示向量 xx 的转置。正定指对任意非零 x∈Rnx\in\mathbb R^n 有 xTAx>0x^{\mathsf T}Ax>0；半正定指对任意 x∈Rnx\in\mathbb R^n 有 xTAx≥0x^{\mathsf T}Ax\geq0。

  1. 若 AA 正定，证明 ff 存在最小点，并且该最小点唯一。
  2. 若 AA 半正定且 rank⁡A=k\operatorname{rank}A=k，其中 1≤k<n1\leq k<n，令 SS 表示 ff 的所有最小点构成的集合。任取 x∗∈Sx^*\in S，再定义
Sx∗={s−x∗∣s∈S}.S_{x^*}=\{s-x^*\mid s\in S\}.

证明集合 Sx∗S_{x^*} 是 Rn\mathbb R^n 的线性子空间。 3. 用 nn、kk 表示该子空间的维数 dim⁡Sx∗\dim S_{x^*}。

Kai​

(1)​

正定値性から AA は可逆である。 x∗=A−1bx^*=A^{-1}b とおき、 y=x−x∗y=x-x^* とすると、 Ax∗=bAx^*=b と AT=AA^{\mathsf T}=A より

f(x)=12(y+x∗)TA(y+x∗)−bT(y+x∗)=12yTAy−12bTA−1b.\begin{aligned} f(x) &=\frac12(y+x^*)^{\mathsf T}A(y+x^*)-b^{\mathsf T}(y+x^*)\\ &=\frac12y^{\mathsf T}Ay-\frac12b^{\mathsf T}A^{-1}b. \end{aligned}

AA は正定値なので y≠0y\neq0 なら yTAy>0y^{\mathsf T}Ay>0 である。したがって ff は

x∗=A−1b\boxed{x^*=A^{-1}b}

でのみ最小値 −12bTA−1b-\frac12b^{\mathsf T}A^{-1}b をとる。

(2)​

ff は微分可能であり、最小点 x∗x^* では

∇f(x∗)=Ax∗−b=0\nabla f(x^*)=Ax^*-b=0

である。任意の xx に対して d=x−x∗d=x-x^* とおけば

f(x)−f(x∗)=12dTAd.f(x)-f(x^*)=\frac12d^{\mathsf T}Ad.

AA は半正定値なので、右辺が 0 になることと Ad=0Ad=0 は同値である。実際、直交行列による対角化 A=QΛQTA=Q\Lambda Q^{\mathsf T} を用いれば、 dTAd=∑iλi(QTd)i2d^{\mathsf T}Ad=\sum_i\lambda_i(Q^{\mathsf T}d)_i^2 であり、正の固有値に対応する成分がすべて 0 になる。

よって

S=x∗+ker⁡A,Sx∗=ker⁡A.S=x^*+\ker A, \qquad S_{x^*}=\ker A.

核 ker⁡A\ker A は線形部分空間であるから、 Sx∗S_{x^*} も線形部分空間である。

(3)​

階数・退化次数定理より

dim⁡Sx∗=dim⁡ker⁡A=n−rank⁡A=n−k.\boxed{\dim S_{x^*}=\dim\ker A=n-\operatorname{rank}A=n-k}.
本页目录