Thursday, January 10, 2013

Better Finite Difference Boundaries with a Tridiagonal Solver

In Pricing Financial Instruments - The Finite Difference Method, Tavella and Randall explain that boundary conditions using a higher order discretization (for example their "BC2" boundary condition) can not be solved in one pass with a simple tridiagonal solver, and suggest the use of SOR or some conjugate gradient based solver.

It is actually very simple to reduce the system to a tridiagonal system. The more advanced boundary conditions only use 3 adjacent values, just 1 value makes it non tridiagonal, the one in bold is the following matrix representation
x x x
x x x
   x x x
       ......
         x x x
            x x x
            x x x
One just needs to replace the first line by a simple linear combination of the first 2 lines to remove the extra x and similarly for the last 2 lines. This amounts to ver little computational work. Then one can use a standard tridiagonal solver. This is how I implemented it in a past post about boundary conditions of a bond in the CIR model. It is very surprising that they did not propose that simple solution in an otherwise very good book.

No comments :

Post a Comment