IE523 Homework 4- Computing the General Solution to Ax = ySolved

Description

I want you to write a generic solver for a set of simultaneous equations Ax = y, where A is a known n × m matrix and y is a known n × 1 vector. You may wish to look at lesson 2 of my notes for the relevant theory. This assignment can take some time, please get started on it ASAP. Here are the components your code:

1. Check if there is a solution to Ax = y by testing if rank([A | y]) = rank(A).
2. If there is no solution – report it as such. If there is a solution, then present the general solution to Ax = y.

You will need NEWMAT for this programming exercise. You might wish to look at linear algebra1.cpp, linear algebra2.cpp and linear algebra3.cpp on Compass to get started on this exercise. As you will see when you do this assignment (or, if you attended class regularly and listened attentively), you will need to pick rank(B)-many columns from a matrix B, at various instants. For this, you may wish to look at the C++ code provided with this assignment that computes n-take-k combinations of a set of n objects (where 1 ≤ k ≤ n).

If there is a solution to Ax = y, you will have to compute all possible basic solutions, where you pick rank(A)-many columns of A (call this matrix X; rank(X) = rank(A)) and then compute z according to equation 1 of lesson 2 of my notes. You then have to insert zeros into z at appropriate locations (depending on which columns of A where chosen to be in X). This augmentedversion of z becomes one basic solution (you have several more, depending on how many candidates for X you have in any given case). Following this, you stack all basic solutions into one large matrix S and pick rank(S)-many columns of S (call this matrix T; rank(T) = rank(S)) and present the affine combination of these columns as the general solution to Ax = y.

The input to your code should be read on command-line through a file. For example, the file input1 on Compass, which is shown in figure 1 presents the relevant details for the instance shown in equation 2 in page 4 of lesson 2 of my notes. The first (second) entry in the file is the number of rows (columns) of A. Following this, each element of A is a presented in a row-by-row fashion. Finally, the entries of y are presented in a row-by-row manner. The format of the input file should be obvious with the example from equation 1 in page 4 of lesson 2 of my notes and what is shown in figure 1 . I am looking for an output along the lines of what is shown in figure 2 for this example. Note that the output in figure 2 says the general solution has the form

 .                           (1)

I am also including a file called input2 on Compass that presents the relevant input for the problem in section 3.1 of lesson 2 of my notes. Figure 4 shows the sample output when my C++ code is run on input2. The output in figure 4 says the general solution has the form

 28   37   28                                                                     −7   35γ1 + 44γ2 + 35γ3 − 7 

_ 14 _  14 _  0 _                                                        0 _                                     14γ₁ + 14γ₂ 

 0   0   −7                                               0                                            −7γ3 

 γ1 15 +γ2 0 +γ3 15 +(1−γ1−γ2−γ3) 15  =          15 − 15γ2 .

 0   −3   0                                               0                                            −3γ2 



 0   0   7                                                0                                              7γ₃ 



0                        0                        0                                                 7                           7 − 7γ₂ − 7γ₃ − 7γ₁

(2)

The input file shown in figure 5 describes the equation that is just below equation 2 in page 4 of lesson 2 of my notes. Figure 6 shows the result when my code is run on this input file.

Some Questions/thoughts…

Question: How do you reconcile the fact that while equation 1 looks similar to the general solution presented in page 7 of lesson 2 of my notes, equation 2 looks different from equation 6 in page 10 of lesson 2.

Figure 1: The format of the input file that describes the problem of equation 2

in page 4 of lesson 2 of my notes.

References

Figure 2: Sample output when the file shown in figure 1 is presented as input. The general solution is presented as the affine combination of the two solution vectors shown in the screen.

Figure 3: The format of the input file that describes the problem of section 3.1 of lesson 2 of my notes.

Figure 4: Sample output when the file shown in figure 3 is presented as input. The general solution is presented as the affine combination of the four solution vectors shown in the screen.

Figure 5: The format of the input file that describes the problem just below equation 2 in page 4 of lesson 2 of my notes.

Figure 6: Sample output when the file shown in figure 5 is presented