An algorithm for solving a special class of tridiagonal systems of linear equations

ABSTRACT

An algorithm is presented for solving a system of linear equations Bu = k where B is tridiagonal and of a special form. This form arises when discretizing the equation - d/dx (p(x) du/dx) = k(x) (with appropriate boundary conditions) using central differences. It is shown that this algorithm is almost twice as fast as the Gaussian elimination method usually suggested for solving such systems. In addition, explicit formulas for the inverse and determinant of the matrix B are given.

REFERENCES

• 1: FORT, TOMLINSON. Finite Differences and Difference Equations in the Real Domain. Oxford U. Press, Oxford, England, 1948.
• 2: HARARr, F. Graphs and matrices. SIAM Rev. 9 (1967), 83-90.
• 3: HENRICI, P. Discrete Variable Methods in Ordinary Differential Equations. Wiley, New York, 1962.
• 4: TODD, J. The condition of certain matrices, II. Arch. Math. 5 (1954), 249-257.
• 5: VARGA, R. S. Matrix Iterative Analysis. Prentice-Hall, Englewood Cliffs, N. J., 1962.
• 6: PARLETT, B. N. Private communication.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Design, Theory, Verification

Keywords:
Gaussian elimination, central difference, tridiagonal