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...

K ca2S f 2c pSK2 f

Phase Diagram Trajectory Fishery

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

Plot Armijo Line Search

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...

Piecewise Polynomial Splines

Polynomial Basis Functions

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...

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...

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,...

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...

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

Matlab Fixpoint Floating

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....

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...