Brennan-Schwartz Back-Substitution for American Option Pricing
Summary
The document discusses the Brennan-Schwartz algorithm for the linear complementarity problem (LCP) that arises when finite differences are used to price American options under Black-Scholes. Its central question is whether the algorithm's modified back-substitution solves that LCP exactly, and why some texts instead present projected successive over-relaxation (PSOR).
The accepted answer clarifies that the cited work presents modified back-substitution as a valid LCP-solving algorithm, not as an exact solution free of numerical error. Because the optimal exercise boundary may lie between grid points, an error can occur near that boundary; the answer relates its order to the spatial discretization. Brennan-Schwartz also has a narrower application: a monotonicity condition must hold, making it suitable for vanilla American puts or calls but not necessarily for an American butterfly. PSOR is more general, while the document gives no proof or benchmark beyond these explanations.
Key ideas
- Finite-difference pricing of American options leads to a linear complementarity problem.
- Modified back-substitution is described as a valid algorithm for that problem, not as an exact solution without numerical error.
- A grid that misses the optimal exercise boundary can introduce error near that boundary.
- The Brennan-Schwartz method requires a monotonicity condition and may not apply to an American butterfly.
- PSOR is presented as a more general alternative.
Tags
Full text
# Brennan-Schwartz algorithm for pricing American options # Brennan-Schwartz algorithm for pricing American options I'm reading Pricing American Options using LU decomposition by Ikonen and Toivanen (IT). They reference The valuation of American put options by Brennan and Schwartz, and cast it as method that uses LU decomposition to solve the linear complementarity problem (LCP) arising in the discretisation of the Black-Scholes "PDI" for American options. On page 9, IT write: "It is obvious that the use of the max-function in the backward substitution is possible because of the form of the solution of the option pricing problem." Does this mean that the Brennan-Schwartz method of modified back substitution exactly the LCP exactly? If so, I don't think this is obvious. Is there a proof of it anywhere? And on a related note, if Brennan-Schwartz solves the LCP exactly then why doesn't Wilmott use it in his "The Mathematics of Financial Derivatives"? He uses Projected Successive Over-relaxation (PSOR) exclusively, which is shown by IT to be a lot slower than using LU decomposition. ## Answer by jherek (score 6, accepted) https://quant.stackexchange.com/a/47155 Ikonen and Toivanen don't say that the LCP is solved exactly, they simply say that the modified back-substitution is a valid algorithm to solve the LCP. A numerical error may arise around the location of optimal exercise, since it does not fall directly on the finite difference grid. I think that however, the error is of the same order as the discretization in space. Incidentally, PSOR and the modified back-substitution are both presented in Elliot and Ockendon Weak and Variational Methods for Free Moving Boundary Problems, which is referenced by Ikonen and Toivanen. The interest of PSOR is to be more general: there is some monotonicity condition that must be verified in order to apply the Brennan-Schwartz algorithm. So it is perfectly fine for a vanilla American put or call, but not for an American butterfly.
Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.