Module for Tri-Diagonal Linear Systems

Check out the new Numerical Analysis Projects page.

Definition (tri-diagonal system).  A tri-diagonal linear system    has the form    

								=
								=
								=
								=
								=

    

Purposes.
1. To understand the "Gaussian elimination process."  
2. To understand solutions to "large matrices" that are contain mostly zero elements, called "sparse matrices."  
3. 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.

Program (tri-diagonal linear system).  Solve a tri-diagonal system  .  

       

Mathematica Subroutine (tri-diagonal linear system).

Example 1.  Enter the following 20 by 20 system    into Mathematica and compute the solution.
The matrix A is to have 2's on the main diagonal and 1's on the sub- and super- diagonals.   The vector B is  
B ={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 }.  
Solution 1.

Observation.  The above matrix has 400 elements, 342 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.  Since the tri-diagonal subroutine will work, we it takes only can save  14.5  as much space to save the necessary information to solve the problem.  In larger matrices the savings will be even more.  So use vectors instead of matrices when you have sparse matrices that are tri-diagonal.  The penta-diagonal matrices are also useful.

Example 2.  Solve the 20 by 20 system    in example 1 using our TriDiagonal[a,d,c,b] subroutine.  
Solution 2.

Example 3.  Solve the 20 by 20 system    in example 1 using our Mathematica's built in TridiagonalSolve[a,d,c,b] procedure.  
Solution 3.

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.

Research Experience for Undergraduates

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

Downloads (Tri-Diagonal System Tri-Diagonal System).  
Download this Mathematica notebook.  

(c) John H. Mathews 2003