9 Maneras de implemetar el metodo binomial en matlab

SIAM REVIEW Vol. 44, No. 4, pp. 661–677

c 2002 Society for Industrial and Applied Mathematics

Nine Ways to Implement the Binomial Method for Option Valuation in MATLAB∗
Desmond J. Higham†
Abstract. In the context of a real-life application that is of interest to many students, we illustrate how the choices made in translating an algorithm into a high-level computer code can affect theexecution time. More precisely, we give nine MATLAB programs that implement the binomial method for valuing a European put option. The first program is a straightforward translation of the pseudocode in Figure 10.4 of The Mathematics of Financial Derivatives, by P. Wilmott, S. Howison, and J. Dewynne, Cambridge University Press, 1995. Four variants of this program are then presented that improve theefficiency by avoiding redundant computation, vectorizing, and accessing subarrays via MATLAB’s colon notation. We then consider reformulating the problem via a binomial coefficient expansion. Here, a straightforward implementation is seen to be improved by vectorizing, avoiding overflow and underflow, and exploiting sparsity. Overall, the fastest of the binomial method programs has an execution time thatis within a factor 2 of direct evaluation of the Black–Scholes formula. One of the vectorized versions is then used as the basis for a program that values an American put option. The programs show how execution times in MATLAB can be dramatically reduced by using high-level operations on arrays rather than computing with individual components, a principle that applies in many scientific computingenvironments. The relevant files are downloadable from the World Wide Web. Key words. algorithm, American option, Black–Scholes, European option, optimization, overflow, underflow, vectorization AMS subject classifications. 65-01, 65Y20 PII. S0036144501393266

1. Introduction. This paper is about the efficient implementation of algorithms. We use a case study based around the binomial method for valuingfinancial options. This gives a compact framework in which to illustrate that (a) computations can often be organized in a number of ways and (b) the overall execution time of a program may depend crucially on the choices made. Our example programs use the MATLAB language. In describing these programs we assume that the reader has some familiarity with scientific computing, and we focus onexplaining features specific to MATLAB. For the sake of brevity our description of MATLAB commands is highly selective, and we refer the reader to [4, 7] or MATLAB’s on-line help facilities for further details. The programs can be downloaded from http://www.maths.strath.ac.uk/∼ aas96106/algfiles.html
∗ Received by the editors August 1, 2001; accepted for publication (in revised form) May 28, 2002;published electronically October 30, 2002. http://www.siam.org/journals/sirev/44-4/39326.html † Department of Mathematics, University of Strathclyde, Glasgow, G1 1XH, UK (djh@maths. strath.ac.uk).

661

662

DESMOND J. HIGHAM

Timings quoted were obtained by averaging over 1000 runs with MATLAB Version 6 (R12) on an IBM H70 server. Comparable results were obtained on two other machines. Two ofthe techniques that we illustrate, removing redundant computation and reformulating the mathematical problem, are generally applicable. Others are closely tied to the nature of MATLAB. Indeed, some of the MATLAB-specific tinkering that goes on in sections 3 and 4 might appear a little mysterious to those students who are not familiar with MATLAB’s “interpretive” nature. For this reason, we pause hereto outline some of the principles that we use. The bulk of scientific computing is done by programs written in a high-level language and compiled into machine code. Compilers generally proceed through four stages: 1. Parsing and semantic analysis. 2. Intermediate code generation. 3. Optimization of the intermediate code. 4. Generation of machine code from the optimized intermediate code....