Can CG verify that a matrix is p

2016-07-24  本文已影响0人  Esparami

To find a answer, I will use CG and its variants (BiCG/FLR) to solve some linear systems $Hx = b$ with respect to different $H$ and $b$.

The CG(Conjugate gradient method) is

function [x] = conjgrad(A,b,x)
    r = b - A*x;
    p = r;
    rsold = r'*r;

    for i = 1:length(b)
        Ap = A*p;
        alpha = rsold/(p'*Ap);
        x = x + alpha*p;
        r = r - alpha*Ap;
        rsnew = r'*r;
        if sqrt(rsnew) < 1e-10
              break;
        end
        p = r + (rsnew/rsold)*p;
        rsold = rsnew;
    end
end

The following examples are designed:

  • Let $H=diag(1,-1)$, $b = (1, 2)$, and $x_0=(0,0)$, CG converges in two steps.
  • Let $H=diag(1,-1)$, $b = (1, 1)$, and $x_0=(0,0)$, CG breaks down in the first step, since $p^TAp = 0$

Conclusion: The convergece of CG method cannot be used to identify if $H$ is positive definite.

  • Let $H=diag(1,-1)$, $b = (1, 2)$, and $x_0=(0,0)$, then $p^TAp <0$ in second step
  • Let $H=diag(1,-1)$, $b = (1, 0)$, and $x_0=(0,0)$, CG converges in the first step, and $p^TAp = 1 >0$ in the first step, therefore no $p^TAp<0$ is encountered.

Conclusion: The value $p^TAp$ is not sufficient to show if $H$ is positive definite.

上一篇下一篇

猜你喜欢

热点阅读