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
    testnorm = norm(v(:,k))
    if (norm(v(:,k)) == 0)
    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)
    v(:,k+1) = r(:,k+1) + (r(:,k+1).*r(:,k+1))./(r(:,k).*r(:,k)).*v(:,k);
CGResult = x(:,k+1);


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;];

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.

  • $\begingroup$ To solve this non-square system, which method can be used? $\endgroup$
    – boy
    Sep 9 '13 at 8:12
  • $\begingroup$ 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). $\endgroup$ Sep 9 '13 at 8:31
  • $\begingroup$ 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. $\endgroup$ Sep 10 '13 at 3:57
  • $\begingroup$ 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? $\endgroup$
    – boy
    Sep 10 '13 at 5:48
  • $\begingroup$ @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. $\endgroup$ Sep 11 '13 at 5:50

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.