Application of second order inhomogeneous linear recurrences to solving a tridiagonal system
Jolanta Borowska
,Lena Łacińska
Journal of Applied Mathematics and Computational Mechanics |
Download Full Text |
View in HTML format |
Export citation |
@article{Borowska_2016, doi = {10.17512/jamcm.2016.2.01}, url = {https://doi.org/10.17512/jamcm.2016.2.01}, year = 2016, publisher = {The Publishing Office of Czestochowa University of Technology}, volume = {15}, number = {2}, pages = {5--10}, author = {Jolanta Borowska and Lena Łacińska}, title = {Application of second order inhomogeneous linear recurrences to solving a tridiagonal system}, journal = {Journal of Applied Mathematics and Computational Mechanics} }
TY - JOUR DO - 10.17512/jamcm.2016.2.01 UR - https://doi.org/10.17512/jamcm.2016.2.01 TI - Application of second order inhomogeneous linear recurrences to solving a tridiagonal system T2 - Journal of Applied Mathematics and Computational Mechanics JA - J Appl Math Comput Mech AU - Borowska, Jolanta AU - Łacińska, Lena PY - 2016 PB - The Publishing Office of Czestochowa University of Technology SP - 5 EP - 10 IS - 2 VL - 15 SN - 2299-9965 SN - 2353-0588 ER -
Borowska, J., & Łacińska, L. (2016). Application of second order inhomogeneous linear recurrences to solving a tridiagonal system. Journal of Applied Mathematics and Computational Mechanics, 15(2), 5-10. doi:10.17512/jamcm.2016.2.01
Borowska, J. & Łacińska, L., 2016. Application of second order inhomogeneous linear recurrences to solving a tridiagonal system. Journal of Applied Mathematics and Computational Mechanics, 15(2), pp.5-10. Available at: https://doi.org/10.17512/jamcm.2016.2.01
[1]J. Borowska and L. Łacińska, "Application of second order inhomogeneous linear recurrences to solving a tridiagonal system," Journal of Applied Mathematics and Computational Mechanics, vol. 15, no. 2, pp. 5-10, 2016.
Borowska, Jolanta, and Lena Łacińska. "Application of second order inhomogeneous linear recurrences to solving a tridiagonal system." Journal of Applied Mathematics and Computational Mechanics 15.2 (2016): 5-10. CrossRef. Web.
1. Borowska J, Łacińska L. Application of second order inhomogeneous linear recurrences to solving a tridiagonal system. Journal of Applied Mathematics and Computational Mechanics. The Publishing Office of Czestochowa University of Technology; 2016;15(2):5-10. Available from: https://doi.org/10.17512/jamcm.2016.2.01
Borowska, Jolanta, and Lena Łacińska. "Application of second order inhomogeneous linear recurrences to solving a tridiagonal system." Journal of Applied Mathematics and Computational Mechanics 15, no. 2 (2016): 5-10. doi:10.17512/jamcm.2016.2.01
APPLICATION OF SECOND ORDER INHOMOGENEOUS LINEAR RECURRENCES TO SOLVING A TRIDIAGONAL SYSTEM
Jolanta Borowska, Lena Łacińska
Institute of Mathematics, Czestochowa University of
Technology
Częstochowa, Poland
jolanta.borowska@im.pcz.pl, lena.lacinska@im.pcz.pl
Abstract. In this paper we consider a linear system of algebraic equations of a tridiagonal type. We show that the solution of such a system can be represented by a corresponding second order inhomogeneous linear recurrence equation. This approach enables us to represent the solution to the tridiagonal Toeplitz linear system of equations in a closed form.
Keywords: tridiagonal system, linear recurrence equations
1. Introduction
The subject of considerations is a tridiagonal linear system of algebraic equations. Such a system comes up in a variety of scientific topics, see for example [1, 2]. The literature related to algorithms for solving tridiagonal linear systems is very wide. The most known are those based on the Thomas method. The new symbolic algorithm and the review of the literature on this subject can be found in [3].
The aim of this paper is to show that the solution to a tridiagonal linear system of algebraic equations can be represented by a corresponding second order inhomogeneous linear recurrence equation with variable coefficients. This approach enables us to obtain a closed form of solution in the case of Toeplitz tridiagonal system.
A linear algebraic tridiagonal system for n unknowns can be represented by a matrix equation of the form
(1) |
where
, , | (2) |
Let us observe that equation (1) may be written as
(3) |
where and .
In this paper it will be assumed that the matrix is nonsingular. This means that linear system (1) has a unique solution.
2. Main results
Let us denote a determinant of matrix by . In the subsequent considerations it will be assumed that . The linear recurrence equation that represents determinant was shown for example in [4]. Bearing in mind these results, we have
(4) |
By we denote a determinant of a matrix obtained from matrix by replacing its first column by the vector , meaning
(5) |
In order to calculate determinant we apply the Laplace expansion with respect to the last column. Hence
(6) |
where
For the above determinant we apply the Laplace expansion with respect to the last column and we get
(7) |
where
Let us observe that using the Laplace expansion with respect to the last row of determinant we obtain
(8) |
Bearing in mind relations (6), (7) and (8), we obtain a second order nonhomogeneous linear recurrence equation of the form
(9) |
Let us observe that
, | (10) |
Hence, in order to obtain determinant we must take into account the recurrence equation (9) together with initial conditions (10).
Now, we focus on the algebraic linear system of equations (2). Firstly, we calculate unknown . For this purpose we use the Cramer formulae
(11) |
At the same time from first equation of system (2) we get unknown
(12) |
Let us observe that from k-th, k = 3,…,n, equation of system (2) we have
(13) |
Hence we get to the second order nonhomogeneous linear recurrence equation for unknown .
Thusly, the solution to the algebraic system of equations (2) comes down to resolving the linear recurrence equation (13) with initial conditions (11) and (12).
Remark 1.
If the main matrix of system (2) has the Toeplitz structure, i.e. , then the recurrence equation (13) has constant coefficients, so we can obtain the explicit solution to the system of equations (2).
3. Special case
In this section we consider a linear algebraic system, which is a special case of (2) under the assumption that , , , , , , , , . So, we consider the system of the form
(14) |
Let us observe that the main matrix of system (14) has the form
(15) |
From (4) we have the recurrence equation for determinant of matrix | (15) |
(16) |
and initial conditions |
(17) |
Following [5], we conclude that the particular solution of recurrence equation (16) satisfying the initial conditions (17) has the form
(18) |
Now, we are to calculate the determinant of the matrix obtained from matrix (15) by replacing its first column by the vector of constant terms of equations (14). Bearing in mind (9), we have second order nonhomogeneous linear recurrence equation for
(19) |
At the same time from (10) we have the initial conditions for equation (19)
, | (20) |
In order to solve nonhomogeneous linear recurrence equation (19) with initial conditions (20), the method of variation of parameters can be applied [5]. As a result we obtain
(21) |
Substituting (20) and (21) into (11), we get |
(22) |
Now, from the first equation of the system (14) we calculate the unknown |
(23) |
Bearing in mind k-th, k = 3,…,n, equation of system (14) we obtain
(24) |
Hence, in order to obtain the solution to the algebraic system of equations (14) we have to solve the nonhomogeneous linear recurrence equation (24) with initial conditions (22) and (23). After applying the method of variation of parameters, [5], we obtain
(25) |
where .
4. Conclusions
It was shown that the solution to the tridiagonal linear system of algebraic equations can be represented by a corresponding second order inhomogeneous linear recurrence equation. The general results were illustrated on the example of a special system in which the main matrix has the Toeplitz tridiagonal structure. As a result, the closed form of solution was obtained.
References
[1] Mazilu I., Mazilu D.A., Williams H.T., Applications of tridiagonal matrices in non-equilibrium statistical physics, Electronic Journal of Linear Algebra 2012, 24, 7-17.
[2] Soujanya G.B.S.L., Reddy Y.N., Computational method for singularly perturbed delay differential equations with layer or oscillatory behaviour, Applied Mathematics and Information Sciences 2016, 10(2), 527-536.
[3] El-Mikkawy M., Atlan F., Algorithms for solving linear systems of equations of tridiagonal type via transformations, Applied Mathematics 2014, 5, 413-422.
[4] Borowska J., Łacińska L., Rychlewska J., Application of difference equation to certain tridiagonal matrices, Scientific Research of the Institute of Mathematics and Computer Science 2012, 3(11), 15-20.
[5] Elaydi S., An Introduction to Difference Equations, Springer, 2005.