Financial Instrument Pricing Using C++, 2nd Edition

CHAPTER 13Numerical Linear Algebra: Tridiagonal Systems and Applications

13.1 Introduction and Objectives

In this chapter we introduce a number of fundamental algorithms related to numerical linear algebra. In particular, we discuss efficient algorithms to solve linear systems of equations. Some of the objectives are:

• Designing algorithms and mapping them to C++ code.
• Using the classes in this chapter as a lightweight alternative to open source matrix libraries such as Eigen, for example.
• Porting legacy code from Duffy (2004B) to C++11.
• Hands-on experience in understanding, writing and debugging C++ code.

We focus on producing efficient code that we use in applications. We define a seamless mapping between an algorithm and the C++ code that implements it. This makes debugging easier and results in maintainable code, especially if it is clearly documented.

This chapter is useful for readers who wish to learn the essentials of the finite difference method.

13.2 Solving Tridiagonal Matrix Systems

A band matrix A = (a_ij) is a square matrix of size n and width 2K + 1 such that a_ij = 0 when |i − j| > K, where K is a non-negative integer. All non-zero elements are positioned on the main diagonal and on the first K diagonals directly above and below it. Some special band matrices are:

• A diagonal matrix is a band matrix with K = 0.
• A Toeplitz matrix is a band matrix in which each diagonal consists of a single identical element but different diagonals may contain different elements. ...