Description

In this stage, the problem becomes more difficult. You should generalize the solution for any amount of variables. The important part is to understand that in most cases if the number of equations equals the number of variables there is only one solution. We will consider special cases in the next stage.

Such multiple linear equations connected together are called a system of linear equations.

One of the most popular ways to solve it is Gauss-Jordan Elimination. Here and here you can find the detailed explanations of how to do it with 3 variables.

You can see an example of the general system of linear equations below. The variables are named $x_1, x_2, ..., x_n$. The coefficients are named $a_{i1}, a_{i2}, ... a_{in}$ for the $i$-th row. And the constants are named $b_1, b_2, ... b_n$.

$\begin{cases} \begin{aligned} a_{11}x_1 & + a_{12}x_2+... +a_{1n}x_n = b_1 \\ a_{21}x_1 & + a_{22}x_2 +... + a_{2n}x_n = b_2 \\ &... \\ a_{n1}x_1 & + a_{n2}x_2 +... + a_{nn}x_n = b_n \\ \end{aligned} \end{cases}$

Like in the video, firstly, the algorithm should null the first column of coefficients except for the first coefficient, which should be equal to 1. Notice letters c and d instead of a and b. It means that through some calculations these coefficients became other coefficients and thus we cannot use letters a and b since they refer to the initial coefficients.

$\begin{cases} \begin{aligned} x_1 & + c_{12}x_2+... +c_{1n}x_n = d_1 \\ 0 & + c_{22}x_2 +... + c_{2n}x_n = d_2 \\ 0 & +... \\ 0 & + c_{n2}x_2 +... + c_{nn}x_n = d_n \\ \end{aligned} \end{cases}$

After that, you need to null the second column all the way from the third row. The second row should contain the coefficient equal to 1.

$\begin{cases} \begin{alignedat}{2} x_1 & \>+\> & c_{12}x_2 & +... +c_{1n}x_n = d_1 \\ 0 & \>+\> & x_2 & +... + e_{2n}x_n = f_2 \\ 0 & \>+\> & 0 & + ... \\ 0 & \>+\> & 0 & +... + e_{nn}x_n = f_n \\ \end{alignedat} \end{cases}$

The same goes for the rest of the columns. In the end, you should get something like that:

$\begin{cases} \begin{alignedat}{4} x_1 & \>+\> & c_{12}x_2 & + ... & \>+\> & c_{1n}x_n & = d_1 \\ 0 & \>+\> & x_2 & +... & \>+\>& e_{2n}x_n & = f_2 \\ & ... \\ 0 & \>+\> & 0 & +... + 0 & \>+\> & \>\>\>\>\>\> x_n & = g_n \\ \end{alignedat} \end{cases}$

The second part of the algorithm is to iterate rows from the last to the first and null the top part of the linear system. In the end, there should be only diagonal elements of the linear system.

$\begin{cases} \begin{alignedat}{4} x_1 & \>+\> & 0 & + ... & \>+\> & \>\>0 & = k_1 \\ 0 & \>+\> & x_2 & + 0+ ... & \>+\>& \>\>0 & = f_2 \\ & ... \\ 0 & \>+\> & 0 & +... + 0 & \>+\> & x_n & = g_n \\ \end{alignedat} \end{cases}$

And the right part of the system is the solution to this system.

In this stage, you need to write a program that reads coefficients from a file, solves the system of linear equations, and writes the answer to another file. You should pass paths to files using command-line arguments. Write to the file only answers separated by \n. Output all the steps only to the console, not in the file.

The first line of the file should contain the number N, a number of variables and also a number of equations. Every other N lines contain N+1 numbers, i.e. N coefficients of the current row and a constant as the last number in this line. The program also should output all rows manipulation it is doing when solving a system of linear equations.

Try to create various classes like Matrix, Row, LinearEquation so the code would be more readable and easier to program.

Example

The greater-than symbol followed by a space (> ) represents the user input. Note that it's not part of the input.

Suppose you have a file named in.txt with the following content:

3
1 1 2 9
2 4 -3 1
3 6 -5 0

Which corresponds to the following equation:

$\begin{cases} 1*x_1 + 1*x_2 + 2*x_3 = 9 \\ 2*x_1 +4*x_2 - 3*x_3 = 1 \\ 3* x_1 + 6*x_2 - 5*x_3 = 0 \\ \end{cases}$

Below is how your program might work. The console output is not checked by the tests, so use it to debug your program. The tests only check the output file.

> java Solver -in in.txt -out out.txt
Start solving the equation.
-2 * R1 + R2 -> R2
-3 * R1 + R3 -> R3
0.5 * R2 -> R2
-3 * R2 + R3 -> R3
-2 * R3 -> R3
3.5 * R3 + R2 -> R2
-2 * R3 + R1 -> R1
-1 * R2 + R1 -> R1
The solution is: (1.0, 2.0, 3.0)
Saved to file out.txt

Theout.txt file should look like this (each answer on a separate line without any excess symbols).

1.0
2.0
3.0