Some Convalescent Methods for the Solution of Systems of Linear Equations
M. Rafique, Sidra Ayub
Department of Mathematics, Faculty of Science, HITEC University, Taxila, Pakistan
Email address:
To cite this article:
M. Rafique, Sidra Ayub. Some Convalescent Methods for the Solution of Systems of Linear Equations. Applied and Computational Mathematics. Vol. 4, No. 3, 2015, pp. 207-213. doi: 10.11648/j.acm.20150403.23
Abstract: In a variety of problems in the fields of physical sciences, engineering, economics, etc., we are led to systems of linear equations, Ax = b, comprising n linear equations in n unknowns x_{1}, x_{2}, …, x_{n}, where A = [a_{ij}] is an nxn coefficient matrix, and x = [x_{1} x_{2} . . .x_{n}]^{T}, b^{}= [b_{1 }b_{2} . . .b_{n}]^{T} are the column vectors. There are many analytical as well as numerical methods^{1}– 11} to solve such systems of equations, including Gauss elimination method, and its modifications namely Doolittle’s method, Crout’s method and Cholesky’s method, which employ LU-decomposition method, where L = [i_{ij}] and u = [u_{ij}] are the lower and upper triangular matrices respectively. The LU-decomposition method was first introduced by the mathematician Alan M. Turing^{2-11} in 1948. Here, in this paper we have made an effort to modify the existing LU-decomposition methods to solve the above mentioned system Ax = b, with the least possible endeavour. It may be seen that the Gauss elimination method^{1, 2, 3, 4} needs about 2n^{3}/3 operations, while Doolittle’s and Crout’s methods require n^{2} operations. Accordingly, in these methods we are required to evaluate n^{2}number of unknown elements of the L and U matrices. Moreover, Cholesky’s method^{1} requires 2n^{2}/3 operations. Accordingly this method requires evaluation of 2n^{2}/3 number of unknown elements of the L and U matrices But, in contrast, the improved Doolittle’s, Crout’s and Cholesky’s methods presented in this paper require evaluation of only (n–1)^{2} number of unknown elements of the L and U matrices. Moreover, an innovative method is also presented in this paper which requires evaluation of even less number of unknown elements of the L and U matrices. In this method we need to evaluate only (n–2)^{2} number of the said unknown elements. Thus, by employing these methods, the computational time and effort required for the purpose can substantially be reduced.
Keywords: System of Equations, Matrix, Column Vector, Decomposition, Doolittle’s Method, Crout’s Method, Cholesky’s Method
1. Introduction
There are numerous analytical and numerical methods for the solution of a linear system, Ax = b, including Gauss elimination method, and its modifications namely Doolittle’s, Crout's and Cholesky’s methods. In the Doolittle’s method LU-decomposition of an nxn matrix A is of the form A = LU, which is given as under,
= .
In the case of Crout’s method this decomposition is given as,
=
It may be mentioned that both the above quoted decompositions lead to the same solution of any linear system of equations.
For a symmetric and positive definite coefficient matrix, the LU-decomposition by the Cholesky’s method is carried out as under,
=
The above mentioned usual LU-decomposition methods are well discussed in the books on numerical linear algebra. In these methods the coefficient matrix A is decomposed as A = LU, so that the linear system of equations Ax = b can be written as LUx = b. This equation may further be written as, Ly = b, where, Ux = y. First we solve the former equation for y by forward substitution and then solve the latter for x by backward substitution. Accordingly, we obtain the solution to the given system of linear equations.
For numerical stability, pivoting is very essential unless the coefficient matrix is diagonally dominant or symmetric and positive definite. Therefore, in all the methods discussed in this paper, pivoting has been implemented before carrying out further steps.
2. Improved Doolittle’s Method
The usual Doolittle’s method, mentioned above, was devised by the American mathematician Myrick Hascall Doolittle (1830-1913)^{1, 3, 7–12}, which appeared in U.S. Coast and Geodetic Survey in 1878. Here, in our improved method, we consider a linear system of n equations in n unknowns, Ax = b. To start with pivoting is done to ensure numerical stability. Thereafter, the system of linear equations is transcribed in such a way that the pivot equation is made to have the pivot element as unity, i.e., a_{11} = 1. For this purpose, if required, we may have to select the requisite equation and divide it throughout by the coefficient of x_{1} for the needful, and make it the pivot equation. Following these steps, the main considerations for the decomposition of the coefficient matrix A, as A = LU, are as under:
(i) The first column of the matrix L = [l_{ij}] is kept the same as that of matrix A, i.e., l_{i}_{1} = a_{i}_{1}, for all i.
(ii) The first row of the matrix U = [u_{ij}] is also kept the same as that of the matrix A, i.e., u_{1j} = a_{1j}, for all j.
(iii) The diagonal elements of the matrix L= [l_{ij}] are kept as unity, i.e., l_{ii} = 1 for all i.
Accordingly, we decompose the coefficient matrix A = LU as,
=
Here all a_{i}_{j} are known while l_{i}_{j }and u_{i}_{j} are unknown which are to be evaluated. For this purpose we multiply the right hand side matrices L and U, and equate the corresponding elements on both sides, i.e., set a_{i}_{j }= (lu)_{i}_{j} . This correspondence enables us to evaluate all the unknown elements l_{i}_{j }and u_{i}_{j}. Here we see that for an nxn order coefficient matrix A, it is required to evaluate only (n–1)^{2} number of unknown elements l_{i}_{j}, and u_{i}_{j} of the L and U matrices respectively. It may be appreciated that by following the above mentioned scheme of LU-decomposition, the computational effort is substantially reduced. As described above, after having carried out the above mentioned decomposition, we solve Ly = b for y, followed by solution of Ux = y for x, to get the required solution to the given system of equations. Here we discuss few examples to illustrate the above mentioned method.
2.1. Solution of a System of Three Equations in Three Unknowns
We consider the following system of equations,
5x_{1} + x_{2} + 2x_{3} = 19
6x_{1} + 24x_{2} – 12x_{3} = –12
2x_{1} + 3x_{2} + 8x_{3} = 39
We interchange 1^{st} and 2^{nd} equations and then divide the pivot equation by 6 so as to have a_{11} = 1, as required by the method explained above. Then we decompose the coefficient matrix as A = LU, according to the scheme described above. Here the coefficient matrix A is of order 3x3, so we need to find only (3–1)^{2} = 4 number of unknown elements of the L and U matrices, which turn out as, l_{32} = 0.26, u_{22} = –19, u_{23} = 12, u_{33} = 8.84. Thus the coefficient matrix gets decomposed as A = LU,
=
Having carried out the above decomposition, we solve Ly = b and obtain y = [–2 29 35.37]^{T}. Next solving Ux = y we get the solution to the given system of equations as,
x = [2 1 4]^{T}
2.2. Solution of a System of Five Equations in Five Unknowns
We consider the following system of linear equations,
5x_{1} + 10x_{2} + 15x_{3} – 20x_{4} + 5x_{5} = – 20
2x_{1} + x_{2} + 5x_{3} + 3x_{4} + 2x_{5} = –2
3x_{1} + 4x_{2} + x_{3} + 2x_{4} + 4x_{5} = 4
4x_{1} + x_{2} + 3x_{3} + 5x_{4} + x_{5} = 6
2x_{1} + 4x_{2} – x_{3} + 2x_{4} + 5x_{5} = 3
We divide the pivot equation by 5 in order to make a_{11} = 1, and then decompose the coefficient matrix as described above and obtain (5–1)^{2} = 16 unknown elements of the L and U matrices as, l_{32 }= 0.67, l_{42 }= 2.33, l_{32 }= 0, l_{43 }= 0.91, l_{53 }= 0.95, l_{54 }= – 0.34, and, u_{22} =–3, u_{23} = –1, u_{24} = 11, u_{25} = 0, u_{33} = – 7.33, u_{34} = 6.67, u_{35} = 1, u_{44} = – 10.73, u_{45} = – 3.91, u_{55} = 0.72. Accordingly, we obtain,
= x
After having carried out the above mentioned decomposition, we solve Ly = b for y, where, y = [y_{1} y_{2} y_{3} y_{4} y_{5}]^{T}, and b = [– 4 –2 4 6 3]^{T}. Thus we obtain, y = [–4 6 12 –2.91 – 1.44]^{T}. Thereafter, solving Ux = y for x, we get the solution to the given system of equations as, x = [1 2 –1 1 2]^{T}.
3. Improved Crout’s Method
The standard Crout’s method was formulated by the American mathematician Prescott Durand Crout (1907 – 1984)^{6}^{–12} . As in the case of improved Doolittle’s method, here also, after having carried out pivoting, the pivot equation is divided by the coefficient of x_{1. }Thereafter, the main idea is to write out the system Ax = b in such a way that the pivot equation has its pivot element a_{11} = 1. Furthermore, the main considerations for the decomposition of the coefficient matrix A, as A = LU, are as under:
(i) As in the case of improved Doolittle’s method, we keep l_{i}_{1} = a_{i}_{1}, for all i.
(ii) Same as in the case of improved Doolittle’s method we retain u_{1j} = a_{1j}, for all j.
(iii) The diagonal elements of the matrix U are kept as unity, i.e., u_{ii} = 1 for all i.
Accordingly, we decompose the coefficient matrix A = LU as,
=
Here all a_{i}_{j} are known while l_{i}_{j }and u_{i}_{j} are unknown which are to be evaluated. For this purpose we multiply the right hand side matrices L and U, and equate the corresponding elements on both sides, i.e., set a_{i}_{j }= (lu)_{i}_{j} . This correspondence enables us to evaluate all the unknown elements l_{i}_{j }and u_{i}_{j}.
We see that for an nxn order coefficient matrix A, it is required to evaluate only (n–1)^{2} unknown elements l_{i}_{j}, and u_{i}_{j} of the L and U matrices respectively. It may be appreciated that by following the above mentioned scheme of LU-decomposition, the number of operations are substantially reduced. As described above, after having carried out the above mentioned decomposition, we solve Ly = b for y, followed by Ux = y for x, to obtain the required solution to the given system of linear equations. Here we discuss few examples to illustrate the above mentioned method.
3.1. Solution of a System of Four Equations in Four Unknowns
We consider the following system of equations,
5x_{1} + 10x_{2} + 15x_{3} – 20x_{4} = –10
2x_{1} + x_{2} + 5x_{3} + 3x_{4} = 2
3x_{1} + 4x_{2} + x_{3} + 2x_{4} = 12
4x_{1} + x_{2} + 3x_{3} + 5x_{4} = 8
We divide the pivot equation by 5 to make a_{11} = 1, and then decompose the coefficient matrix, as illustrated above. Thus we obtain a total of (n–1)^{2} =(4–1)^{2} = 9 unknown elements of the L and U matrices as, l_{22} = –3,_{ }l_{32 }= –2, l_{42 }= –7, l_{33 }= –7.33, l_{43} = –0.33, l_{44} = –10.73, u_{23} = 0.33, u_{24 }= – 3.67, u_{33} = 9, u_{34} = –0.91. Thus the decomposition A = LU, is obtained as,
= x
Next, solving Ly = b, where b is the column vector, [–2 2 12 8]^{T} we obtain, y = [–2 –2 –1.91 1]^{T}, and then solving Ux = y, we get the solution to above system as x = [1 2 –1 1]^{T}.
3.2. Solution of a System of Five Equations in Five Unknowns
We consider the following system of equations,
16x_{1} – 8x_{2} + 8x_{3} + 16x_{4} + 24x_{5} = 40
3x_{1} + 2x_{2} + 2x_{3} + 2x_{4} + 4x_{5} = 9
3x_{1} + 3x_{2} – 3x_{3} + 2x_{4} – 4x_{5} = 7
5x_{1} – x_{2} – 1x_{3} + 3x_{4} – 7x_{5} = 1
7x_{1} + x_{2} + 3x_{3} + 5x_{4} – 5x_{5} = 5
We divide the pivot equation throughout by 16, to make a_{11} = 1, and then decompose the coefficient matrix as enunciated above. Thus we obtain (n – 1)^{2}= (5 – 1)^{2} = 16 unknown terms of the L and U matrices as: l_{22} = 3.5, l_{32} = 4.5, l_{42} = 1.5, l_{52} = 4.5, l_{33} = – 5.14, l_{43} = 3.71, l_{53} = 1.14, l_{44} = –1.78, l_{54} = – 0.78 l_{55} = – 9.34, u_{23} = 0.14, u_{24} = – 0.29, u_{34} = 0.056, u_{25} = – 0.14, u_{35} = 1.53, and, u_{45} = 4.84. Accordingly, we get the desired LU decomposition of the coefficient matrix as,
x
Having carried out the above mentioned decomposition, we first solve Ly = b, where b = [2.5 9 7 1 5]^{T}. It gives y = [2.5 0.43 0.47 5.84 1]^{T}. Next, we solve Ux = y, and obtain the solution to the given system of equations as, x = [1 1 – 1 1 1]^{T}.
4. Improved Cholesky’s Method
The usual Cholesky’s method for symmetric and positive definite coefficient matrix was developed by French military officer, geodesist and mathematician Andre-Louis Cholesky (1876–1918)^{1, 12} . As discussed above, for all practical algorithms pivoting is necessary unless the matrix is diagonally dominant, or symmetric and positive definite. Here, in our improved method we follow the same scheme as in the case of improved Doolittle’s method. Accordingly, we decompose the coefficient matrix A = LU as,
=
Here all a_{i}_{j} are known while c_{i}_{j }are unknown, which are to be evaluated. For this purpose we multiply the right hand side matrices L and U, and equate the corresponding elements on both sides. This correspondence enables us to evaluate all the unknown elements c_{i}_{j}.
We see that for an nxn order coefficient matrix A, we have to evaluate only (n–1)^{2} unknown elements c_{i}_{j} of the L and U matrices respectively. It may be appreciated that by following the above mentioned scheme of LU-decomposition, the number of operations are substantially reduced. As described above, after having carried out the above quoted decomposition, we solve Ly = b for y, followed by Ux = y for x, to obtain the required solution to the given system of linear equations. Here we discuss few examples to illustrate the above mentioned method.
4.1. Solution of a System of Four Equations in Four Unknowns
We consider the following system of equations,
Decomposing the coefficient matrix we obtain (n–1)^{2} =(4–1)^{2} = 9 unknown elements of the L and U matrices as, l_{32 }= – 0.5, l_{42 }= 0, l_{43} = – 0.33, u_{22} = 4, u_{23} = – 2, u_{24 }= 0, , u_{33} = 9, u_{34} = – 3, u_{44} = 16. Thus the decomposition A = LU, is given as,
= x
Next, solving Ly = b, where b is the column vector, [15 –35 94 1]^{T} we obtain, y = [15 –20 39 –16]^{T}, and then solving Ux = y, we get the solution to the given system of equations as x = [2 –3 4 –1]^{T}.
4.2. Solution of a System of Five Equations in Five Unknowns
We consider the following system of equations,
12x_{1} + 18x_{2} + 24x_{3} + 30x_{4} + 12x_{5} = 24
3x_{1} – x_{2} + x_{3} – 2x_{4} + x_{5} = 9
4x_{1} + x_{2} + 2x_{3} + x_{4} – x_{5} = 5
5x_{1} – 2x_{2} + x_{3} + 2x_{4} + x_{5} = 8
2x_{1} + x_{2} – x_{3} + x_{4} + x_{5} = – 1
We divide the pivot equation by 12 to set a_{11} = 1, as required by the method discussed in this paper. Thereafter, we decompose the coefficient matrix as, A = LU, as described above. In this case we need to evaluate (5–1)^{2} = 16 unknown terms of the L and U matrices as, l_{32 }= 0.91, l_{42 }= 1.73, l_{52 }= 0.36, l_{43 }= 0.25, l_{53 }= 2.19, l_{54 }= 0.042, and u_{22} = – 5.5, u_{23} = –5, u_{24} = – 9.5, u_{25} = –2, u_{33} = – 1.45, u_{34} = –0.36, u_{35} = – 3.18, u_{44} = 6, u_{45} = 0.25, u_{55} = 6.68. This decomposition is given as,
= x
After carrying out the above mentioned decomposition, first we solve Ly = b, where b = [2 9 5 8 –1]^{T}, to get y = [2 3 –5.73 –5.75 6.68]^{T}. Thereafter, we solve Ux = y, and obtain the solution to the given system of equations as,
x = [1 –1 2 –1 1]^{T}.
5. An Innovative LU-Decomposition Method
We consider a linear system of n equations in n unknowns, Ax = b, where A is the coefficient matrix of order nxn, while x and b are column vectors of order nx1, each. First of all we carry out pivoting unless the coefficient matrix is diagonally dominant or symmetric and positive definite. This method necessitates to have the coefficients of x_{1} in all the equations as unity, i.e., a_{i}_{1 }= 1 for all i. Any equation not fulfilling this condition may be divided throughout by the coefficient of x_{1} for the needful. Thereafter, we can decompose the coefficient matrix as, A = LU, with the following provisions,
(i) The first column of the lower triangular matrix L = [l_{i}_{j}] is kept the same as that of matrix A, i.e., l_{i}_{1}= a_{i}_{1} = 1, for all i.
(ii) The first row of the upper triangular matrix U = [u_{i}_{j}] is also kept the same as that of matrix A, i.e., u_{1j }= a_{1j}, for j ≥ 2. The elements of the second column of matrix L are transformed as, _{li}_{2 }= _{ai}_{2 }– _{a12},
(iii) for i ≥ 2.
(iv) The diagonal elements of the matrix U are kept as unity, i.e., u_{ii }=1, for all i.
(v) The remaining elements in the second row of matrix U are transcribed as: u2j = for j ≥ 3.
Thus, schematically, LU-decomposition of the coefficient matrix A = LU, is given as under,
= x
After having accomplished the LU-decomposition as described above, we solve the equation Ly = b for y and next solve the equation Ux = b for x, to obtain the solution to the given system of linear equations. Here we consider few examples to elaborate the method discussed above.
5.1. Solution of a System of Three Equations in Three Unknowns
We consider the system of equations,
5x_{1} + x_{2 }+ 2x_{3} = 19
x_{1} + 4x_{2} – 2x_{3} = – 2
2x_{1} + 3x_{2} + 8x_{3} = 39.
We divide the first equation by 5 and the third equation by 2, throughout as required by the method elaborated above to get,
=
Next, the coefficient matrix is decomposed as described above. In this decomposition only (n – 2)^{2} =
(3–2)^{2} = 1 number of unknown, namely l_{33} is required to be evaluated which comes to 4. Accordingly, we obtain the required decomposition A = LU, as,
= .
Further, solving Ly = b, we obtain, y = [3.8 – 1.3 4]^{T}. Thereafter, solving Ux = y, we get, x = ]^{T}, which is the required solution to the given systems of equations.
5.2. Solution of a System of Four Equations in Four Unknowns
We consider the system of equations,
4x_{1} – 4x_{2 }+ 12x_{3} + 8x_{4} = 60
–x_{1} + 5x_{2} – 5x_{3} – 2x_{4} = – 35
3x_{1} – 5x_{2} + 19x_{3} + 3x_{4} = 94
2x_{1} – 2x_{2} + 3x_{3} + 21x_{4} = 1
We divide the pivot equation by 4, multiply the second equation by –1, divide the third equation by 3, and also divide the fourth equation by 2, as discussed above, and transform the given system of equations as Ax = b, where b = [ 15 35 31.33 0.5]. Here we need to evaluate only (n –2)^{2} = (4–2)^{2} = 4 unknown number of elements of the L and U matrices, which are obtained as: l_{33} = 3, l_{43} = – 1.50, l_{44} = 8, and u_{34} = – 0.33. Thus we get A = LU as under,
= x
After having carried out this decomposition, we solve the system Ly = b for y to get y = [15 –5 4.33 1]^{T}. Thereafter, solving the system Ux = y, for x we obtain the solution to the given system of equations as, x = [2 –3 4 –1]^{T}.
By following the method discussed above, we can solve a linear system having any number of equations with the same number of unknowns.
6. Conclusion
The solution of a system of linear equations by means of LU-decomposition of the coefficient matrix is a plausible method that can be employed analytically as well as numerically. It may be seen that for an nxn coefficient matrix, the usual Doolittle's, and Crout's methods require evaluation of a total of n^{2} number of unknown elements of the L and U matrices, and in the case of usual Cholesky’s method we are required to evaluate 2n^{2}/3 number of unknown elements of these matrices. However, the improved Doolittle’s, Crout’s and Cholesky’s methods need evaluation of only (n –1)^{2} number of elements of these matrices, while the Innovative LU-Decomposition method requires evaluation of only (n –2)^{2} number of unknown elements of the L and U matrices. This difference becomes significant for systems of large number of linear equations. As such a considerable amount of computational time and energy can be saved by employing the methods presented in this paper.
References