## Choosing a Solution Method

Numerical analysts have special terms that they use to classify the rates at which iterative routines converge. Specifically, a sequence of iterates x(k) is said to converge to x* at a rate of order p if there is constant C > 0 such that x(fc+1) - x* < C x(k) - x* p for sufficiently large k. In particular, the rate of convergence is said to be linear if C < 1 and p 1, superlinear if 1 < p < 2, and quadratic if p 2. The asymptotic rates of convergence of the nonlinear equation solution...

## [Txrk4fTx0[additional parameters

The inputs are the name of a problem file that returns the function f, the vector of time values T and the initial conditions, xo. The fourth input is an empty matrix to make the calling syntax for rk4 compatible with the CompEcon ODE solvers. The two outputs are the vector of time values (this makes rk4 compatible with Matlab's ODE solvers) and the solution values. Unlike the suite of ODE solvers provided by Matlab, rk4 is designed to be able to compute solutions for multiple initial values....

## Government Price Controls

To solve the government price controls of Section 8.6.3 (page 8.6.3) we again use the general solver for rational expectations models, remsolve. Recall that the equilibrium is characterized by the functional complementarity condition SEyP(x(s) + y - x(x(s) + y)) - P(s - x(s)) - c(x(s)) 0 x(s) > 0, p* > P(s x(s)), x(s) > 0 p* P(s x(s)). In the notation of the general model the state variable is (s, y), the response variable is (x, a), and the shock is y. The expectation function is with a...

## [vx valmaxvfPdelta if normvvold

And a MATLAB script that performs policy iteration for the infinite horizon model is v,x valmax v,f,P,delta pstarfstar valpol x,f,P v speye n -delta pstar fstar if norm v-vold lt tol, return, end In these implementations, maxit and tol are the maximum iterations allowed and the convergence tolerance, respectively, which have specified default values that may be overridden with the routine optset as suggested by the following examples The CompEcon Toolbox also provides two utilities for...

## Industry Entry and Exit

Consider the industry entry-exit model of Section 8.3.2 page 205 assuming that the short-run profit n is an exogenous Markov process nt 1 g nt,et 1 n j nt n et 1 where et is i.i.d. normal 0, a2 , n 0, y 0.7, and a 1. Further assume an exit cost KQ 5, entry cost K1 10, and discount factor 8 0.9. The collocation method calls for the analyst to select n basis functions faj and n collocation nodes ni,di , and form the value function approximant V n,d YTj 1 cj4 gt j n,d whose coefficients Cj solve...

## Bellman Equation Collocation Methods

In order to describe the collocation method for continuous state Markov decision models, we limit our discussion to infinite-horizon models with one-dimensional state and action spaces and univariate shocks. The presentation generalizes to models with higher dimensional states, actions, and shocks, but at the expense of cumbersome additional notation required to track the different dimensions.i Consider, then, the Bellman equation for an infinite horizon discrete time continuous state dynamic...

## K ca2S f 2c pSK2 f

Which can be solved for any initial fish stock S and industry size K . To use the rk4 solver a function returning the time derivatives for the system must be supplied. function dx fdif03 t,x,flag,beta,f,del s x 1, k x 2, temp 1 beta s. k ds 1-s . s-s. k. temp dk del s. temp.2 -2 f dx ds dk As previously mentioned, the flag variable is not used but is supplied to make rk4 compatible with the ODE solvers provided by Matlab. The solver itself is called using where x0 is a matrix of starting...

## Line Search Methods

Just as was the case with rootfinding problems, it is not always best to take a full Newton step. In fact, it may be better to either stop short or move past the Newton step. If we view the Newton step as defining a search direction, performing a one-dimensional search in that direction will generally produce improved results. In practice, it is not necessary to perform a thorough search for the best point in the Newton direction. Typically, it is sufficient to assure that successive...

## Implementation of the Collocation Method

Let us now consider the practical steps that must be taken to implement the collocation method in a computer programming environment. Below, we outline the key operations using the Matlab vector processing language, presuming access to the function approximation and numerical quadrature routines contained in the COM-PECON library. The necessary steps can be implemented in virtually any other vector processing or high-level algebraic programming language, with a level of difficulty that will...

## Constrained Optimization

The simplest constrained optimization problem involves the maximization of an objective function subject to simple bounds on the choice variable According to the Karush-Kuhn-Tucker theorem, if f is differentiable on a, b , then x is a constrained maximum for f only if it solves the complementarity problem CP f', a, b 5 Conversely, if f is concave and differentiable on a,b and x solves the complementarity problem CP f ' x , a,b , then x is a constrained maximum of f if additionally f is strictly...

## Discrete Time Continuous State Dynamic Models Theory Examples

We now turn our attention to discrete time dynamic economic models whose state variables may assume a continuum of values. Three classes of discrete time continuous state dynamic economic models are examined. One class includes models of centralized decision making by individuals, firms, or institutions that may involve either discrete or continuous choices. Examples of continuous state dynamic decision models involving discrete choices include a financial investor deciding when to exercise a...

## Piecewise Polynomial Splines

Piecewise polynomial splines, or simply splines for short, are a rich, flexible class of functions that may be used instead of high degree polynomials to approximate a real-valued function over a bounded interval. Generally, an order k spline consists of a series of kth order polynomial segments spliced together so as to preserve continuity of derivatives of order k 1 or less. The points at which the polynomial pieces are spliced together, v1 lt v2 lt lt vp, are called the breakpoints of the...

## Broyden S Method Inverse Jacobian Update Formula

J K ' x k - x k-1 This yields the iteration rule x x f x k - f x k-1 f x . Unlike the Newton method, the secant method requires two, rather than one starting value. The secant method is graphically illustrated in Figure 3.4. The algorithm begins with the analyst supplying two distinct guesses x 0 and x 1 for the root of f. The function f is approximated using the secant line passing through x 0 ,f x 0 and x 1 , f x 1 , whose root x 2 is accepted as an improved estimate for the root of f. The...

## Fspace fundefnbastypenaborder

Here, on input, bastype is string referencing the basis function family, which can take the values 'cheb' for Chebychev polynomial basis, 'spli' for spline basis, or 'lin' for a linear spline basis with finite difference derivatives n is the vector containing the degree of approximation along each dimension a is the vector of left endpoints of interpolation intervals in each dimension b is the vector of right Figure 6.9 Approximation of 1 25x2 1 Figure 6.9 Approximation of 1 25x2 1 endpoints of...

## Quasi Monte Carlo Integration

Although Monte-Carlo integration methods originated using insights from probability theory, recent extensions have severed that connection and, in the process, demonstrated ways in which the methods can be improved. Quasi-Monte Carlo methods rely on sequences xj, with the property that without regard to whether the sequences passes standard tests of randomness. Any sequence that satisfies this condition for arbitrary Riemann integrable functions can be used to approximate an integral on a, b ....

## End end

Here, the routine getindex is used to find the index of the following period's state. Fifth, specifies the terminal value function vterm. Upon reaching period T 1, if the energy stock is positive the animal procreates with probability 1 if the stock is zero, however, the animal procreates with probability 0 vterm ones n,1 vterm 1 0 Sixth, one packs the model structure. Here, model is a structured variable whose fields contain the reward matrix, transition probability matrix, time horizon,...

## Economic Examples

A discrete Markov decision model is composed of several elements the state space, the action space, the reward function, the state transition function or state transition probabilities, the discount factor 6, the time horizon T, and, if the model has finite horizon, the terminal value function VT 1. This section provides six economic examples that illustrate how these elements are specified and how the Bellman equation is formulated. A mine operator must decide how much ore to extract from a...

## Exercises

How many Gauss-Jacobi and Gauss-Seidel iterations are required to get answers that agree with the L-U decomposition solution to four significant digits 2.2. Use the matlab function randn to generate a random 100 by 100 matrix A and a random 100-vector b. Then use the Matlab functions tic and toc compute the time needed to solve the linear equation Ax b 1, 10, and 50 times for each of the following algorithms b x U L b , computing the L-U factors of A only once using the Matlab function lu. c x...

## Numerical Differentiation

The most natural way to approximate the derivative of a univariate real-valued function f at a point x is choose a small non-zero number h and compute a one-sided f x lim f x h f x . J w h o h Thus, at least in theory, one can compute an arbitrarily accurate approximation by taking h sufficiently small. We will take up the question of how small h should be in practice, but first we address the issue of how large an error is produced using a finite difference approximant. An error bound for the...

## Newtons Method

In practice, most nonlinear problems are solved using Newton's method or one of its variants. Newton's method is based on the principle of successive linearization. Successive linearization calls for a hard nonlinear problem to be replaced with a sequence of simpler linear problems whose solutions converge to the solution of the nonlinear problem. Newton's method is typically formulated as a rootfinding technique, but may be used to solve a fixed-point problem x g x by recasting it as the...

## Complementarity Methods

Although the complementarity problem appears quite different from the ordinary rootfinding problem, it actually can be reformulated as one. In particular, x solves the complementarity problem CP , a, b if and only if it solves the rootfinding problem x min max x ,a x ,b x 0 where min and max are applied row-wise. A formal proof of the equivalence between the complementarity problem CP f, a,b and its 'minmax' rootfinding formulation x 0 is straightforward, but requires a somewhat tedious...

## Contents

1.1 Some Apparently Simple 1.2 An Alternative Analytic 2 Computer Basics and Linear Equations 8 2.1 L-U 2.2 Gaussian 2.3 Rounding 2.4 1ll 2.5 Special Linear 2.6 Iterative Appendix A Computer Appendix B Data Bibliographic 3.1 Bisection 3.2 Function 3.3 Newton's 3.4 Quasi-Newton 3.5 Problems With Newton Methods 3.6 Choosing a Solution 3.7 Complementarity Problems 3.8 Complementarity Bibliographic 4 Finite-Dimensional Optimization 64 4.1 Derivative-Free 4.2 Newton-Raphson Method 4.3 Quasi-Newton...

## Function Iteration

Function iteration is a relatively simple technique that may be used to compute a fixed-point x g x of a function from n to n. The technique is also applicable to a rootfinding problem f x 0 by recasting it as the equivalent fixed-point problem x x f x . Function iteration begins with the analyst supplying a guess x 0 for the fixed-point of g. Subsequent iterates are generated using the simple iteration rule Since g is continuous, if the iterates converge, they converge to a fixed-point of g....

## Solve Bellman Functional Equation

Many interesting economic models cannot be solved analytically using the standard mathematical techniques of Algebra and Calculus. This is often true of applied economic models that attempt to capture the complexities inherent in real-world economic behavior. For example, to be useful in applied economic analysis, the conventional Marshallian partial static equilibrium model of supply and demand must often be generalized to allow for multiple goods, interegional trade, intertemporal storage,...

## Glossary of Matlab Terms

A list of Matlab terms used in this text. For a complete list, see Matlab documentation. chol computes the Cholesky decomposition of symmetric positive definite matrix diag returns diagonal elements of matrix as a vector or creates a diagonal matrix from a vector disp displays results on screen eps machine precision largest number that, added to 1, returns 1 eye returns order n identity matrix In eye n feval evaluates function referred to by name feval f,x,y find produces index of values...