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
1
output in figure 2 says the general solution has the form
λ
1
−2
3
0
+ (1 − λ)
3
−3
0
1
=
3 − 2λ
λ − 3
−3λ
λ − 1
. (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
γ1
28
14
0
15
0
0
0
+γ2
37
14
0
0
−3
0
0
+γ3
28
0
−7
15
0
7
0
+(1−γ1−γ2−γ3)
−7
0
0
15
0
0
7
=
35γ1 + 44γ2 + 35γ3 − 7
14γ1 + 14γ2
−7γ3
15 − 15γ2
−3γ2
7γ3
7 − 7γ2 − 7γ3 − 7γ1
.
(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
2
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.
3
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.
4
Figure 6: Sample output when the file shown in figure 5 is presented as input.
5
