Can CG verify that a matrix is positive definite?

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.

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 我明白我穷其一生 也不过一成不变 我选择就此沉沦 做垂死的飞鸟 好过挣扎无果的麻雀 。 从前我轰轰烈烈孤注一掷 只...
    空酒阅读 1,501评论 2 7
  • 到达西塘已是下午三点。 下车后找到一家客栈,在景区北大门出门左拐,再往一条小道进去。掌柜的是个姑娘,二...
    雪衣先生阅读 3,269评论 7 9
  • 开学两个多星期了,前两个星期可谓是战战兢兢地度过,心里最怕的是看到班群里有人说 xxx出成绩了!每次一看到首先是眉...
    若荷_阅读 1,514评论 0 0