Problem 1

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

(a)对能量式进行化简

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

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

(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);
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);
drawnow;
pause(.1);
end

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

(a)定义

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