MATLAB - Gaussian Elimination with Partial Pivoting

[azdang]

Homework Statement

Let A be the nxn matrix with elements a_ij = -1 for i > j, a_ii = a_in = 1, 1 <= i <= n, and zero everywhere else. Let b be a random vector. Solve the linear system Ax = b by Gaussian Elimination with partial pivoting.

Use tril, eye, and ones to generate A,
Generate b with rand.
No loops

Homework Equations

The Attempt at a Solution

I'm not sure if this is the correct place to post this, but I figured someone in Computer Science might know MATLAB and be able to help. For one, I am HORRIBLE with MATLAB. I never seem to be able to do it exactly the way my teacher expects it. First off, I'm having trouble generating A. So far, I've used G = eye(n,n) to get a matrix with 1's on the diagonal, and C = tril(-ones(n,n),-1) to get a matrix with -1's where I think they should be. However, I still need a way to get 1's in the last column. Also, I'm not sure how to put these three matrixes together in MATLAB to construct A.

Another thing, I know for G.E.P.P. we need to factor A = PLU. I am assuming for this particular matrix, those will be obvious? Maybe I am wrong. Then, I guess I just have to solve Ly = P^Tb and Ux = y.

I'm really just not good with MATLAB, as this is the first class I've ever had to use it for. I've tried reading up on it, and although I generally get the desired outcome, my method never seems to be correct. It would be greatly appreciated if someone could give me some guidance on this problem. Thank you so much.

 

[kreil]

I doubt this question is still active, but I'll post a reply for posterity at least!

Let A be the nxn matrix with elements aij = -1 for i > j, aii = ain = 1, 1 <= i <= n, and zero everywhere else. Let b be a random vector. Solve the linear system Ax = b by Gaussian Elimination with partial pivoting.

Conceptually, to construct A you want to create several different matrices with nonzero values in different locations, and then add the matrices together. If the nonzero values are in different locations then this has the effect of combining all of the information about where the nonzeros are into one matrix. Here is how to generate each of those pieces:

• aij = -1 for i > j is a matrix with -1's below the main diagonal. You can generate this matrix by first generating a matrix of all -1's with -1*ones(n). Then, use TRIL to make that matrix lower triangular, e.g. tril(-1*ones(n),-1).
• aii = ain = 1 is a matrix with ones along the main diagonal as well as in the final column. You can generate the identity matrix easily with eye(n), and then you can add the final column of ones with indexing.

Finally, a function that accepts the matrix order N as an input and generates A using these pieces is:

function A = generateA(N)
A1 = tril(-1*ones(N),-1);
A2 = eye(n);
A2(:,end) = 1;
A = A1+A2;
end

Some sample output from this function is

>> generateA(4)

ans =

     1     0     0     1
    -1     1     0     1
    -1    -1     1     1
    -1    -1    -1     1

Next, generating b as a random vector is a straightforward use of the RAND function:

b = rand(n,1);

Finally, solving using Gaussian elimination with partial pivoting is simply a matter of performing LU factorization:

[L,U] = lu(A);
x = U\(L\b)

You can check the results by comparing against x = A\b.