Measure seven times - cut once, or use the saying in practice

I sat on the Coursera course. The course was aimed at beginners in Java, and in one of the video tutorials the topic 7 Steps for Solving Problems was raised .

I, with a clear conscience, listened to the video tutorial, thought to myself, this business has gone far and for a long time.

The rest of the course was easy, relaxed. But, on one of the subjects at the university, namely in the so-called “Scientific Programming”, the following task appeared:

Solve a system of linear equations $$$Ax=b$using the following matrix expansion $$$A$:

$$

$$A = LU,$$

Where $$$L$Is the lower triangular matrix, and $$$U$Is the upper triangular matrix.

The topic of linear algebra, which we took on the 1st course. Frankly, I remembered the general principles of operations with matrices, vectors, and the holy of holies - the Gauss method. If you think it over with brains, then we did not study any LU decomposition, but the Google method always helps. Rescued, up to this point.

I found a general algorithm for finding matrices $$$L$and $$$U$, but at half past three in the morning no coffee gave me the opportunity to properly implement it (given that we coded there on Octave). In the end, I freaked out, and decided to nevertheless listen to the cleverly named proverb.

1. Describe the problem by hand

All that you lack in life is to understand what the problem really is. Let's take an example of the above problem and write it on a piece of paper. In a good way, the following conditions for the existence of matrices must be satisfied$$$L$ and $$$U$:

- the inverse matrix must exist$$$A$, I mean $$$\exists{A^{-1}}$;
- all major minors should not be degenerate, that is$$$\Delta_{(1,...,n)}\neq{0}$

Well, that’s why we at least need a “fool test”, because there are surely smart people who want to use the matrix that is not suitable for us. But for now, let’s omit it.

The problem is clear to us: find matrices$$$L$ and $$$U$that will fall under the above conditions. Having tried to google the methods of solution, it is unlikely that you will be able to correctly implement the algorithm the first time (if you are not good at linear algebra). After going through tons of attempts, we most likely will develop some sequence of actions to solve our problem, and then we proceed to step 2.

2. Describe what you did

Take the matrix as an example

$$

$$A = \begin{pmatrix} 1&2&3 \newline 0&-2&4 \newline 1&-1&0 \end{pmatrix}.$$

Now we apply our Gauss method to it and get rid of the extra elements in line 3, by subtracting the first line from it, multiplied by the ratio of the first element of 3 lines to the first element of 1 line:

$$

$$a_3=a_3-a_1 \cdot\frac { {a_3}_1 }{ {a_1}_1 }.$$

Now, get rid of the second element of the 3 line with a similar action:

$$

$$a_3=a_3-a_2 \cdot\frac { {a_3}_2 }{ {a_2}_2 }.$$

As a result, we obtain the matrix

$$

$$A = \begin{pmatrix} 1&2&3 \newline 0&-2&4 \newline 0&0&0 \end{pmatrix}=U.$$

And now, the coefficients we found (the result of the ratio of elements $$$\frac{{a_i}_j}{{a_j}_j}$) take the values ​​of the matrix $$$L$, and get

$$

$$L = \begin{pmatrix} 1&0&0 \newline 0&1&0 \newline 1&\frac{1}{2}&1 \end{pmatrix}.$$

Looking through the template, is not it?

3. Finding patterns

At this stage, most likely, you will return to step 1 and 2, because the template you did not always find will be true for all cases. But nothing, since it didn’t work out, it will happen next.

So, based on the example, we can form the following algorithm / solution template:

1. Define the square matrix$$$A, n$th order;
2. Set the matrix$$$L = I$where $$$I$- identity matrix $$$n$th order;
3. Set the matrix$$$U = A$;
4. We apply the following successive transformations to the matrices, provided that$$$\begin{cases} i=2,\ldots, n \newline j=1,\ldots,i \end{cases}$

$$

$$\begin{array}{c} {l_i}_j=\frac{{u_i}_j}{{u_j}_j} \newline u_i = u_i-u_j\cdot{{{l_i}_j}} \end{array},$$

At $$$n = 3$we get:

$$

$$L = \begin{pmatrix} 1&0&0 \newline {l_2}_1&1&0 \newline {l_3}_1&{l_3}_2&1 \end{pmatrix},\quad U = \begin{pmatrix} {u_1}_1&{u_1}_2&{u_1}_3 \newline 0&{u_2}_2&{u_2}_3 \newline 0&0&{u_3}_3 \end{pmatrix}$$

4. Checking the template / algorithm

There is an algorithm - there are millions of matrices to test it! You can not worry about this template, it is obviously true (personally tested on the most non-degenerate of the possible matrices). But remember: hurry up - you make people laugh . So always check the templates you created so that you don’t continue to jump like a damn to the very beginning.

5. Translation of the algorithm into code

The obvious step, everything you need is often already in the syntax of the language, and if not, no one bothers you to create classes and functions to solve this problem, then you have an algorithm. Since I implemented this algorithm as part of an educational university program, I could only use Octave for implementation, so all the code I present to you is in its syntax (it is very similar to Python, so I will use its highlight for formatting):

A = input("Enter the matrix A: ")
numOfRows = size(A, 1)
numOfCols = size(A, 2)

if numOfRows ~= numOfCols
    disp("Wrong matrix.")
else
    n = numOfCols
    disp("----------------")
    L = eye(3)
    disp("Making U = A")
    U = A
    disp("----------------")

    for i=2:n
        disp("Step "), disp(i-1)
        for j=1:i-1
            L(i,j) = U(i,j)/U(j,j)
            U(i,:) = U(i,:) - U(j,:)*L(i,j)
        end
        disp("----------------")
    end

    disp("Check the answer of L*U: "), disp(L*U)
end

6. Search for failed tests

You should always try to “break” your code. Here (obviously) there is no complete “protection from the fool”, but I took as the basis the assumption that the initially correct matrix will be introduced.

At this step, you should find all possible errors, inaccuracies in your code, as a result of which the bias of the constructed algorithm may also be revealed. Therefore, here you should try out as many omissions that could have been made.

7. Debug failed tests

The most logical, and probably expected of the steps. The code must be biased and the algorithm corrected. There is nothing more to be added here.

Conclusion

I can say that it is unlikely that I would ever seriously take this approach to solving problems, if not for my sleepy state. But it is worth paying attention to this method - it is short, and all its laboriousness consists only in the fact that it must be used.

Note

Thanks to the linear algebra textbooks for the material for solving the problem.