How to solve this system with conjugate gradient algorithm in matlab

Question

CG Algorithm https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!386&v=3

System of equations, the question and the example https://skydrive.live.com/redir?resid=E0ED7271C68BE47C!387&v=3

% below result is only accurate at decimal 0.1, but not the tolerate, why? 
% is the conjugate gradient algorithm only for square matrix A's system?
% about the lambda1 + lambda2 = 1, how embedded this in algorithm?
% below is Matlab Code

w = CGResult(1);
lambda1 = CGResult(2);
lambda2 = CGResult(3);
(w+13/35*lambda1+47/140*lambda2) >= 2/5
(w+57/140*lambda1+61/140*lambda2) >= 2/5
(w+31/140*lambda1+8/35*lambda2) >= 1/5


A = [1, 13/35, 47/140; 
1, 57/140, 61/140;
1, 31/140, 8/35;];
b = [2/5;2/5;1/5;];
tol = 0.0000000000001;
Max = 10000;
x2 = [0.5;0.5;0.5];
n2 = 3;
MartinCG(x2, A, b, Max, tol, n2);

% Why only for Square Matrix, How about Non Square Matrix A

function CGResult = MartinCG(x2, A, b, Max, tol, n3)
r = zeros(n3);
x = zeros(n3,Max-1);
x(:,1) = x2;
r = zeros(n3,Max-1);
v = zeros(n3,Max-1);
t = zeros(n3,Max-1);
dum = zeros(n,n);
r(:,1) = b - A*x(:,1);
v(:,1) = r(:,1);
for k=1:1:Max-3
    k
    testnorm = norm(v(:,k))
    if (norm(v(:,k)) == 0)
        break;
    end 
    t(:,k) = (r(:,k).*r(:,k))./(v(:,k).*(A*v(:,k)));
    x(:,k+1) = x(:,k) + (t(:,k).*v(:,k));
    r(:,k+1) = r(:,k) - t(:,k).*(A*v(:,k));
    testnorm2 = norm(r(:,k+1))
    if (norm(r(:,k+1)) < tol)
        break;
    end
    v(:,k+1) = r(:,k+1) + (r(:,k+1).*r(:,k+1))./(r(:,k).*r(:,k)).*v(:,k);
end
CGResult = x(:,k+1);
end

%%%%%%%%%%%%%%%%%%%%%%%%%%%

when really to calculate the example, my code do not work for 6*3 Matrix A

A = [1, 13/35, 47/140; 
1, -13/35, -47/140;
1, 57/140, 61/140;
-2/5, -57/140, -61/140;
1/5, 31/140, 8/35;
-1/5, -31/140, -8/35;];
b = [2/5;-2/5;2/5;-2/5;1/5;-1/5;];

score 3 · Accepted Answer · answered Sep 09 '13 at 06:15

3

A cursory glance at Wikipedia's page on the conjugate gradient (CG) method will indicate why CG won't work on your particular system of linear equations: CG is designed to solve the system $Ax = b$ where $A$ is symmetric and positive-definite.

These two conditions naturally also require that $A$ is square. Since your linear system satisfies none of these conditions, there is no reason that conjugate gradient should converge to a valid solution for arbitrary nonsquare matrices with arbitrary right-hand sides.

answered Sep 09 '13 at 06:15

Geoff Oxberry

30,394
9
64
127

To solve this non-square system, which method can be used? – Ho Yeung Lee Sep 09 '13 at 08:12
That all depends. For starters, if $b$ isn't a linear combination of the columns of $A$, there isn't a solution to your linear system. If there is a solution, $A$ has a nullspace of at least dimension 3, so there will be an infinite number of solutions, and you'll have to provide some additional information if you want a particular solution (like you want the solution with the smallest L2 norm, or the solution with the fewest nonzero entries). – Geoff Oxberry Sep 09 '13 at 08:31
In fact, it's not just that the CG method may not converge, it is that the formulas simply make no sense at all since you can't take scalar products between vectors of size 3 and 6. You need to read up on over- and underdetermined systems. – Wolfgang Bangerth Sep 10 '13 at 03:57
as i see there are other part of question i haven't captured in photo, maybe i upload later, what kind of additional information needed? – Ho Yeung Lee Sep 10 '13 at 05:48
1

@boy: Your photo depicts an optimization problem rather than a system of equations, in which case you should be forming some square system of equations related to the KKT conditions and then solving it, possibly using a preconditioned conjugate gradient method. As it stands, your question is totally misleading because a lot of people aren't even going to look at your links, and they're going to assume based on the material you've posted that you're asking about systems of linear equations. – Geoff Oxberry Sep 11 '13 at 05:50

score 2 · Answer 2 · answered Sep 09 '13 at 11:58

Your question does not contain enough details to understand what it is you are doing and what you want to do. But, if I understand your right, then you are trying to apply the conjugate gradient method to a linear system $Ax=b$ where your matrix $A$ is not square. This can not work -- CG can only deal with square matrices. Furthermore, if $A$ is not square, you need to think about what exactly it is you mean when you ask for the "solution" of such a system because there are, in general, either infinitely many (underdetermined) or none (overdetermine).

How to solve this system with conjugate gradient algorithm in matlab

2 Answers2