Is made and the solution vector x can be calculated in 2 simple loops like: The matrixes L and U look like (for a 4*4 matrix): It’s idea is to decompose the matrix A of the equation Ax = b into a lower triangular matrix and an upper triangular matrix and get LUx = b. The LU decomposition is a quite sophisticated approach. Using a LU decomposition by Prescott Durand Crout The Givens transformation is much less weak regarding ceros in the rows and it does not have the disadvantage of the growing or shrinking values in the lower rows. Using this Givens transformation my matrix equation from above looks like this after elimination: After that the matrix equation can be solved by the same procedure as used in the algorithm of Gauss. To an upper diagonal matrix the elements a21, a31 and a32 have to be eliminated and therefore 3 different rotation matrixes have to be calculated and A (and the solution vector Y) must be multiplied by them. A multiplication of the matrix A with this rotation matrix eliminates element a 22. Where p and q are the 2 dimensions of the plane the rotation takes place. In a 5x5 Matrix a rotation matrix looks like: Therefore the a ij elements do not grow or shrink as they do it with the Gaussian algorithm. So the rotation brings the vector into the horizontal direction and eliminates its vertical component which is the element a pp. This vector is rotated by the angle φ and the angle φ is minus the angle of the vector in its 2 dimensional room. The idea of the transformation is basically to take two elements a pq and a qq and regard them as a 2 dimensional vector. In the Givens transformation a rotation matrix is used to eliminate elements. Using a Givens transformation for elimination. There the a ij values have quite a different distribution and impact of pivoting becomes rather negative. I tried it on a polynomial interpolation algorithm. The pivoting does not help in every case. If that’s not possible, the algorithm must be stopped and the equation can’t be solved. In such a case, if possible, rows must be switched. But still the elimination algorithm by Gauss is not too accurate and it is quite weak in case of ceros in the rows. With this pivoting the same matrix equation looks like this after elimination: There are the so called pivoting strategies to improve this behaviour and one of this strategies is to pre-process all the rows first in a way that the sum of all the elements of one row becomes close to 1. With big matrixes that can lead to inaccuracy and in the worst case an overflow. If they are smaller than 1 hey become smaller the lower it goes. The elimination algorithm by Gauss has some disadvantage: If the elements a ij are bigger than 1, after the elimination the elements in the lower rows become the bigger, the lower it goes. First the elimination part and second the solving of the equations for the unknown x values. That’s the basic function of the elimination algorithm by Carl Friedrich Gauss. Now the last equation can be solved for x 3, with x 3 the second equation can be solved for x 2 and with x 2 and x 3 the first equation can be solved for x 1 finally. The classic approach to solve a matrix equation by Gauss is to eliminate all the elements on the left side of the main diagonal in the matrix and to bring (for instance) a 3 * 3 matrix equation like The Householder transformation is a real great thing and works quick and accurate. But now that I know the Householder transformation, I changed my opinion. I take that in advance: As long as I didn’t know the Householder transformation, the Givens transformation was my favourite. In order to do so, I implemented the Algorithm of Gauss, the LU decomposition, elimination by Givens transformation, using the inverse matrix according to Cramer and using Determinants Determinants and then I found the Householder transformation. Some are very elegant (at least in my opinion :-), some are quite sophisticated and finally they all do the same and so, the question came to me: Which one is best? That brought me to the idea to compare the different algorithms. But there are many other quite interesting algorithms to solve such a matrix equation. If it comes to solve a matrix equation, there is always the elimination algorithm by Carl Friedrich Gauss.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |