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

这次回顾作业1。

Problem 1

最小化$f(x)$等价于求$f’(x)=0$的根,所以

(a)向前误差:

(b)向后误差:

(c)条件数:

Problem 2

(a)$\epsilon $相当于相对误差,相比于$(x \Diamond y) +\epsilon $的形式,$(1+\epsilon )(x \Diamond y) $可以更方便的比较不同测量值的误差大小。

(b)证明:存在性是显然的,所以我们只需证明

左边的不等号显然,只需考虑右边的不等号,利用反证法,假设

如果$\epsilon \ge \epsilon_{\max}$,那么

所以必存在$\epsilon_j $,使得

这就产生了矛盾,因此$\epsilon \ge \epsilon_{\max}$不可能发生。

如果$\epsilon \le -\epsilon_{\max}$,那么

所以必存在$\epsilon_j $,使得

这就产生了矛盾,因此$\epsilon \le -\epsilon_{\max}$不可能发生。

所以

(c)这里要注意一点,我们的运算也会产生误差,所以

(i)

其中$0\le |\epsilon| <\epsilon_{\max}$,第二个等号是因为(b)。由上式可得,我们的误差上界为

(ii)

其中$0\le |\epsilon| <\epsilon_{\max}$,第三个等号是因为(b)。有上式可得,我们的误差上界为

(d)注意到

计算相对误差可得:

如果$x,y$非常接近,那么不难看出上式趋于无穷大,因此减法的相对误差无法估计。

(e)考虑带误差的递推式:

对大括号的式子进行估计:

计算相对误差可得

(f)考虑带误差的递推式:

因为

所以相对误差的上界约等于

Kahan求和的方法比较复杂,可以参考计算机程序设计艺术(第2卷)中文版第235页和598页,这里只给出结果:

这个结果说明Kahan求和产生的误差和计算次数无关。

Problem 3

(a)假设$A,B \in \mathbb R^{n\times n}$是上三角矩阵,即

记$C=AB$,考虑$b_{ij}(i>j)$

对前一项来说,因为$i>j \ge k$,所以$a_{ik}=0$;对于后一项来说,$k>j$,所以$b_{kj}=0$,因此对于$i>j$,我们有

这说明$C=AB$是上三角矩阵。

(b)直接计算特征多项式即可:

所以上三角阵的特征值为其对角元。

下面证明$\{ \vec v_1,…,\vec v_k\} $线性无关,假设

两边左乘$U^m$可得

对$m=0,…,k-1$,将这些等式写成矩阵形式可得:

$A$的行列式为范德蒙行列式,因为$u_{ii}$互不相同,所以$|A|\neq 0$,从而$A$可逆,因此

所以

因为$\vec v_i \neq 0$,所以$\alpha_i= 0$,从而$\{ \vec v_1,…,\vec v_k\} $线性无关。

(c)假设$A\in \mathbb R^{n\times n}$是下三角矩阵,即

假设$B\in \mathbb R^{n\times n}$是$A$的逆,即

下面证明$B$是下三角矩阵,首先由$A$可逆,我们知道$A$的对角元$a_{ii}\neq 0 ,i=1,…,n$,接着考虑$AB$第$i$行$i+1$列到第$n$列的元素,由$AB=I_n$可知,这些元素都为$0$。

首先考虑$AB$的第$1$行

所以

接下来用数学归纳法证明$b_{ij}=0,j=i+1,…,n$,我们对$i$做数学归纳法,基本情形$i=1$已证明,假设$i=k$时结论成立,我们来推出$i=k+1$时结论也成立。

考虑$AB=I_n$的第$k+1$行第$j$个元素,其中$j\ge k+2$,显然该元素为$0$,所以

因为$j\ge k+2$,所以由归纳假设

其次当$s\ge k+2$时,由下三角矩阵的定义可知

因此

因为$a_{k+1,k+1}\neq 0$,所以

因此$i=k+1$时结论也成立。综上

所以$B$是下三角矩阵。