美文网首页
Can CG verify that a matrix is p

Can CG verify that a matrix is p

作者: Esparami | 来源:发表于2016-07-24 22:13 被阅读0次

    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.

    相关文章

      网友评论

          本文标题:Can CG verify that a matrix is p

          本文链接:https://www.haomeiwen.com/subject/swumjttx.html