CS205A HW2

课程主页:https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾作业2。

Problem 1

(a)$\forall A,B \in \mathbb R^{n\times n}$,以及满足$||\vec x||=1 $的$\vec x $,我们有

其中最后一个不等号是由$||A||$的定义。

所以

(b)利用等价定义:

那么显然有

任取$\vec x \in \mathbb R^n$,我们有

所以

对左边取最大值可得:

(c)原不等式等价于

对$A$的特征值$\lambda_i$,取对应的特征向量$\vec x_i \in \mathbb R^n$,我们有

所以

因此对任意特征值$\lambda_i $,我们有

(d)我们假设$||\vec x||_1 =1$,即

计算$||A\vec x||_1$可得:

所以我们有

补充题:

由(c)可得,对任意特征值$\lambda_i$,我们有

所以

接下来证明另一个方向的不等式,证明参考维基百科

注意到对于任意矩阵$A$,假设其特征值为

那么$\frac A k $的特征为

所以$\forall \epsilon > 0$,构造如下矩阵

由之前叙述可得

所以

所以由极限的定义可得,存在$N_+$,当$k\ge N_+$时,我们有

从而

结合之前的结果可得

令$\epsilon \to 0$,我们有

Problem 2

(a)对于固定的$k$,记

我们计算$E_{c_1,s} E_{c_2,s}$

注意到forward substitution等价于左乘矩阵$E_{c,l}, l>k$,结合上述事实,我们有

第一部分结论得证。接着验证

事实上,我们有

注意到$\vec e_k$的第$k$个元素为$1$,$\vec m_k$第$k$个元素为$0$,所以

因此

(b)

因为$\vec e_k^TP^{(ij)}$的作用是交换$\vec e_k^T$的第$i,j $列,而$\vec e_k^T $的第$i,j$列均为$0$,$k\neq i,j$,所以

注意到我们显然有

所以

(c)令

我们的目标是证明

所以关于$k$做数学归纳法即可。当$k=n-2$时,

所以

因此$k=n-2$时结论成立。假设$k=s$时结论,现在证明$k=s-1$时结论也成立,此时有

由定义,我们有

利用(b)计算$P_s L_s P_{s+1}…P_{n-1}$可得

注意到$P_{s+1}\vec m_s$的特点依然为$i\le s$的元素为$0$,所以仍然可以使用(b)的性质,即

所以

从而

因此$k=s-1 $时结论也成立。

(d)首先考虑

由$\vec m_k ,\vec e_k$的性质可得,只有当$i \ge k+1$且$j=k$时,$(S_k)_{ij}\neq 0$,所以当$i <j $时,我们必然有

所以$S_k$是下三角阵,注意到作用$P_{n-1}….P_{k+1}$只会交换位于$i \ge k+1$且$j=k$位置上的元素的相对位置,所以我们依然有$P_{n-1}….P_{k+1}S_k$是下三角阵,所以

是下三角阵,因此

是下三角阵。

Problem 3

(a)令$e_1,…,e_n$为$\mathbb R^n $上标准正交积,那么

所以

那么

注意到

当且仅当$\vec x = \vec 0$时等号成立,所以$A$是正定矩阵,因此存在对称矩阵$M$,使得

所以

(b)利用(a),不难得到如下等价定义:

其中$A​$是正定矩阵。

(c)记

我们可以将问题描述如下,找到矩阵$A$,使得

达到最小值。对上述函数化简可得

由于我们要比较距离的接近程度,所以这里增加如下约束条件:

所以可以将原问题转化为熟悉的形式。

Problem 4

备注,题目中虽然没有讲,但我推断这里默认Tikhonov regularization为

否则有些内容无法讨论。

(a)加上Tikhonov regularization,我们的目标是最小化

定义

那么上述问题可以转化为最小化

关于$\vec a$求梯度可得

令上式为$0$可得正规方程。

(b)将$\vec a$分解为

其中

所以

不难发现我们有

利用$\Gamma =I$的事实,所以

从而

当且仅当

等号成立。所以我们只需要考虑

的情形。

(c)记

那么

带入正规方程可得

注意这里我们有

(d)注意到

如果使用特征转换,不妨设

那么

所以

补充题,直接利用泰勒展开即可:

所以

本文标题:CS205A HW2

文章作者:Doraemonzzz

发布时间:2019年03月31日 - 10:56:00

最后更新:2019年03月31日 - 11:43:35

原始链接:http://doraemonzzz.com/2019/03/31/CS205A HW2/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。