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

这次回顾作业6。

Problem 1

(备注,这题没有讲明,但是从后面的讨论中可以推出这里为无向图)

假设$|V_0|=m$,并且

记$B​$为邻接矩阵,即

将其记为如下分块形式:

其中

记$1_k\in \mathbb R^k$表示全$1$的$k$维列向量,假设

那么记

(a)对能量式进行化简

$\forall 1\le k \le n-m$,我们有

令上式为$\vec 0​$得到

写成矩阵形式为

那么将上式写为分量形式得到

最后验证$A$为对称正定矩阵,对称性显然,下证正定性,首先记

$\forall \vec y=(y_1 ,\ldots, y_{n-m})^T$,计算$\vec y ^T A\vec y$:

因为$B_{ij}\in \{0,1\}$,所以

因此

当且仅当$y_i=0$时等号成立,所以$A$对称正定。

(b)(i)将之前讨论的部分实现即可,代码如下

B = zeros(totalVertices);
[m, n] = size(edges);
for i = 1:m
    x = edges(i, 1);
    y = edges(i, 2);
    B(x, y) = 1;
    B(y, x) = 1;
end

B1 = B(unconstrainedVertices, unconstrainedVertices);
B2 = B(unconstrainedVertices, constrainedVertices);
B3 = B2';
B4 = B(constrainedVertices, constrainedVertices);

A = sparse(diag(([B1, B2] + [B1; B3]') * ones(totalVertices, 1)) - B1 - B1');
rhs = (B2 + B3') * constraints;

(ii)算法如下:

所以对应代码如下:

for i=1:maxIters
    % TODO:  Update curX
    d = rhs - A * curX;
    a1 = sum(d .* d, 1);
    a2 = diag(d' * A * d)';
    
    alpha = a1 / a2;
    curX = curX + alpha * d;
    
    
    % Display the current iterate
    curResult(unconstrainedVertices,:) = curX;
    plotGraph(curResult, edges, f);
    title(sprintf('Gradient descent iteration %d',i));
    drawnow;
    pause(.1);
end

(iii)算法如下:

代码如下:

%初始化
r = rhs - A * curX;
v = zeros(size(r)) + 1e-3;

for i=1:maxIters
    % TODO:  Update curX
    r1 = diag(r' * A * v)';
    v1 = diag(v' * A * v)';
    v = r - r1 ./ v1 .* v;
    alpha = diag(v' * r) ./ diag(v' * A * v);
    curX = curX + alpha' .* v;
    r = r - alpha' .* (A * v);

    % Display the current iterate
    curResult(unconstrainedVertices,:) = curX;
    plotGraph(curResult, edges, f);
    title(sprintf('Conjugate gradients iteration %d',i));
    drawnow;
    pause(.1);
end

(iv)共轭梯度法很快就收敛了。

Problem 2

(a)定义

下面考虑$\vec e_k$和$\vec e_{k-1}$的递推关系:

注意

所以由(1)可得

因此

递推可得

假设$G$的特征值为$\lambda_1, \ldots ,\lambda_n$,对应的特征向量为$\vec v_1,\ldots ,\vec v_n$,记

题目假设$\vec v_1,\ldots ,\vec v_n$张成$\mathbb R^n$,那么

因为$\lambda_i <1$,所以

因此

(b)利用圆盘定理即可:

圆盘定理

假设$A\in \mathbb R^{n\times n}$为$n$阶矩阵,令

那么$A$的特征值$z$在如下圆盘中

证明:任取$A$的特征值$\lambda_0$,对应的特征向量为$\vec x$,那么

写成方程形式为

那么

于是

但是显然$| x_r|>0 $,所以

回到原题,我们有

而$g_{ii}=0$,所以$G​$的特征值满足

因此收敛。

Problem 3

如果

左乘$\vec x_k^TA,k=1,\ldots,n$可得

由$A​$正交的定义可得

所以(1)即为

如果$A$正定,$\vec x_k$非零,那么

此时$\vec x_i$线性无关。

如果$A$半正定,那么因为$\vec x_k^TA\vec x_k$可能为$0$,所以无法判断$a_k$,即此时无法推出$\vec x_i$线性无关。