Background

    In applications, it is often the case that systems of equations arise where the coefficient matrix has a special structure.  Sparse matrices which contain a majority of zeros occur are often encountered.  It is usually more efficient to solve these systems using a taylor-made algorithm which takes advantage of the special structure.  Important examples are band matrices, and the most common cases are the tridiagonal matrices.  

Definition (Tridiagonal Matrix).  An  n×n  matrix A is called a tridiagonal matrix if    whenever .  A tridiagonal matrix has the for

    
(1)    .

Theorem  Suppose that the tri-diagonal linear system    has    and   for .  If   ,  and    ,  and  , then there exists a unique solution.  

Proof  Tri-Diagonal Matrices  Tri-Diagonal Matrices  

    The enumeration scheme for the elements in (1) do not take advantage of the overwhelming number of zeros.  If the two subscripts were retained the computer would reserve storage for   elements.  Since practical applications involve large values of  , it is important to devise a more efficient way to label only those elements that will be used and conceptualize the existence of all those off diagonal zeros.  The idea that is often used is to call elements of the main diagonal , subdiagonal elements   are directly below the main diagonal, and the superdiagonal elements    are directly above the main diagonal.  Taking advantage of the single subscripts on we can reduce the storage requirement to merely   elements.  This bizarre way of looking at a tridiagonal matrix is  

    .

Observe that A does not have the usual alphabetical connection with its new elements named  , and that the length of the subdiagonal and superdiagonal is n-1.

Definition (tri-diagonal system).  If A is tridiagonal, then a tridiagonal system is

(2)    

A tri-diagonal linear system    can be written in the form    

(3)    

								=
								=
								=
								=
								=

    

Goals

To understand the "Gaussian elimination process."  
To understand solutions to"large matrices" that are contain mostly zero elements, called "sparse matrices."  
To be aware of the uses for advanced topics in numerical analysis:  
(i)    Used in the construction of cubic splines,
(ii)   Used in the Finite difference solution of boundary value problems,  
(iii)  Used in the solution of parabolic P.D.E.'s.

Algorithm (tridiagonal linear system).  Solve a tri-diagonal system    given in (2-3).  
Below diagonal elements:       
Main diagonal elements:       
Above diagonal elements:       
Column vector elements:        

Computer Programs  Tri-Diagonal Matrices  Tri-Diagonal Matrices  

Mathematica Subroutine (tri-diagonal linear system).

Example 1.  Create a 31 by 31 tridiagonal matrix A where the main diagonal elements are all "2" and all elements of the subdiagonal and superdiagonal elements are "1."  Then solve the linear system    where  .  Compute the solution using decimal arithmetic and rational arithmetic.  
Solution 1 (a).
Solution 1 (b).

Observation.  The 31×31 matrix A in Example 1 has 961 elements, 870 of which are zeros.  This is an example of a "sparse" matrix.   Do those zeros contribute to the solution ?  Since the matrix is tri-diagonal and diagonally dominant, there are other algorithms which can be used to compute the solution.  Our tri-diagonal subroutine will work, and it requires only  12.3%  as much space to save the necessary information to solve the problem.  In larger matrices the savings will be even more.  It is more efficient to use vectors instead of matrices when you have sparse matrices that are tri-diagonal.  

Example 2.  Solve the 31 by 31 system    in Example 1 using our TriDiagonal[a,d,c,b] subroutine.  Compute the solution using decimal arithmetic and rational arithmetic.  
Solution 2 (a).
Solution 2 (b).

Example 3.  Solve the 31 by 31 system    in Example 1 using Mathematica's built in TridiagonalSolve[a,d,c,b] procedure.    Compute the solution using decimal arithmetic and rational arithmetic.  
Solution 3 (a).
Solution 3 (b).

Conclusion.  If the matrix   is tri-diagonal this structure should be considered because the stored zeros do not contribute to the accuracy of the solution and just waste space in the computer. Since tri-diagonal systems occur in the solution of boundary value differential equations, practical problems could easily involve tri-diagonal matrices of dimension 1000 x 1000.  This would involve 1,000,000 entries if a square matrix was used but only 2998 entries if the vector form of the tri-diagonal matrix is used.

Example 4.  Solve the 31 by 31 system    in Example 1 using the inverse matrix and the computation  .  
Solution 4 (a).
Solution 4 (b).

Research Experience for Undergraduates

Tri-Diagonal Matrices  Tri-Diagonal Matrices  Internet hyperlinks to web sites and a bibliography of articles.  

Download this Mathematica Notebook Tri-Diagonal Linear Systems

Return to Numerical Methods - Numerical Analysis

(c) John H. Mathews 2004