Numerical Methods in Economics

Preface xv I INTRODUCTION 1(52) 1 Introduction 3(26) 1.1 What Economists Can Compute 3(3) 1.2 Roles of Computation in Economic Analysis 6(7) 1.3 Computation in Science 13(2) 1.4 Future of Computing 15(2) 1.5 Objectives and Nature of This Book 17(3) 1.6 Basic Mathematics, Notation, and Terminology 20(5) 1.7 Software and Supplemental Material 25(1) 1.8 Further Reading 26(1) Exercises 27(2) 2 Elementary Concepts in Numerical Analysis 29(24) 2.1 Computer Arithmetic 29(2) 2.2 Computer Processing and Algorithms 31(2) 2.3 Economics of Computation 33(1) 2.4 Efficient Polynomial Evaluation 34(1) 2.5 Efficient Computation of Derivatives 35(4) 2.6 Direct versus Iterative Methods 39(1) 2.7 Error: The Central Problem of Numerical Mathematics 39(2) 2.8 Making Infinite Sequences Finite 41(3) 2.9 Methods of Approximation 44(1) 2.10 Evaluating the Error in the Final Result 45(3) 2.11 Computational Complexity 48(2) 2.12 Further Reading and Summary 50(1) Exercises 50(3) II BASICS FROM NUMERICAL ANALYSIS ON R(n) 53(280) 3 Linear Equations and Iterative Methods 55(38) 3.1 Gaussian Elimination, LU Decomposition 55(3) 3.2 Alternative Methods 58(3) 3.3 Banded Sparse Matrix Methods 61(1) 3.4 General Sparse Matrix Methods 62(4) 3.5 Error Analysis 66(4) 3.6 Iterative Methods 70(5) 3.7 Operator Splitting Approach 75(2) 3.8 Convergence of Iterative Schemes 77(1) 3.9 Acceleration and Stabilization Methods 78(6) 3.10 Calculating A(-1) 84(1) 3.11 Computing Ergodic Distributions 85(3) 3.12 Overidentified Systems 88(1) 3.13 Software 88(1) 3.14 Further Reading and Summary 89(1) Exercises 89(4) 4 Optimization 93(54) 4.1 One-Dimensional Minimization 94(5) 4.2 Multidimensional Optimization: Comparison Methods 99(4) 4.3 Newton's Method for Multivariate Problems 103(6) 4.4 Direction Set Methods 109(8) 4.5 Nonlinear Least Squares 117(3) 4.6 Linear Programming 120(1) 4.7 Constrained Nonlinear Optimization 121(7) 4.8 Incentive Problems 128(5) 4.9 Computing Nash Equilibrium 133(2) 4.10 A Portfolio Problem 135(2) 4.11 A Simple Econometric Example 137(3) 4.12 A Dynamic Optimization Problem 140(2) 4.13 Software 142(1) 4.14 Further Reading and Summary 142(1) Exercises 143(4) 5 Nonlinear Equations 147(48) 5.1 One-Dimensional Problems: Bisection 147(3) 5.2 One-Dimensional Problems: Newton's Method 150(8) 5.3 Special Methods for One-Dimensional Problems 158(1) 5.4 Elementary Methods for Multivariate Nonlinear Equations 159(8) 5.5 Newton's Method for Multivariate Equations 167(4) 5.6 Methods That Enhance Global Convergence 171(3) 5.7 Advantageous Transformations 174(2) 5.8 A Simple Continuation Method 176(3) 5.9 Homotopy Continuation Methods 179(8) 5.10 A Simple CGE Problem 187(4) 5.11 Software 191(1) 5.12 Further Reading and Summary 192(1) Exercises 193(2) 6 Approximation Methods 195(56) 6.1 Local Approximation Methods 195(7) 6.2 Ordinary Regression as Approximation 202(1) 6.3 Orthogonal Polynomials 203(4) 6.4 Least Squares Orthogonal Polynomial Approximation 207(4) 6.5 Uniform Approximation 211(5) 6.6 Interpolation 216(3) 6.7 Approximation through Interpolation and Regression 219(5) 6.8 Piecewise Polynomial Interpolation 224(1) 6.9 Splines 225(3) 6.10 Examples 228(3) 6.11 Shape-Preserving Approximation 231(4) 6.12 Multidimensional Approximation 235(5) 6.13 Finite Element Approximations 240(4) 6.14 Neural Networks 244(3) 6.15 Further Reading and Summary 247(1) Exercises 248(3) 7 Numerical Integration and Differentiation 251(34) 7.1 Newton-Cotes Formulas 251(6) 7.2 Gaussian Formulas 257(10) 7.3 Singular Integrals 267(2) 7.4 Adaptive Quadrature 269(1) 7.5 Multidimensional Quadrature 269(8) 7.6 Example: Portfolio Problems 277(2) 7.7 Numerical Differentiation 279(3) 7.8 Software 282(1) 7.9 Further Reading and Summary 282(1) Exercises 283(2) 8 Monte Carlo and Simulation Methods 285(24) 8.1 Pseudorandom Number Generation 285(6) 8.2 Monte Carlo Integration 291(5) 8.3 Optimization by Stochastic Search 296(5) 8.4 Stochastic Approximation 301(2) 8.5 Standard Optimization Methods with Simulated Objectives 303(2) 8.6 Further Reading and Summary 305(1) Exercises 306(3) 9 Quasi-Monte Carlo Methods 309(24) 9.1 Equidistributed Sequences 311(2) 9.2 Low-Discrepancy Methods 313(8) 9.3 Fourier Analytic Methods 321(4) 9.4 Method of Good-Lattice Points 325(4) 9.5 Estimating Quasi-Monte Carlo Errors 329(1) 9.6 Acceleration Methods and qMC Schemes 330(1) 9.7 Further Reading and Summary 330(1) Exercises 331(2) III NUMERICAL METHODS FOR FUNCTIONAL PROBLEMS 333(112) 10 Finite-Difference Methods 335(34) 10.1 Classification of Ordinary Differential Equations 335(2) 10.2 Solution of Linear Dynamic Systems 337(3) 10.3 Finite-Difference Methods for Initial Value Problems 340(6) 10.4 Economic Examples of IVPs 346(4) 10.5 Boundary Value Problems for ODEs: Shooting 350(1) 10.6 Finite-Horizon Optimal Control Problems 351(4) 10.7 Infinite-Horizon Optimal Control Problems and Reverse Shooting 355(7) 10.8 Integral Equations 362(3) 10.9 Further Reading and Summary 365(1) Exercises 366(3) 11 Projection Methods for Functional Equations 369(30) 11.1 An Ordinary Differential Equation Example 369(6) 11.2 A Partial Differential Equation Example 375(2) 11.3 General Projection Method 377(11) 11.4 Boundary Value Problems 388(4) 11.5 Continuous-Time Growth Problem 392(1) 11.6 Computing Conditional Expectations 393(2) 11.7 Further Reading and Summary 395(1) Exercises 396(3) 12 Numerical Dynamic Programming 399(46) 12.1 Discrete-Time Dynamic Programming Problems 399(7) 12.2 Continuous-Time Dynamic Programming Problems 406(3) 12.3 Finite-State Methods 409(6) 12.4 Acceleration Methods for Infinite-Horizon Problems 415(9) 12.5 Discretization Methods for Continuous-State Problems 424(7) 12.6 Methods for Solving Linear-Quadratic Problems 431(2) 12.7 Continuous Methods for Continuous-State Problems 433(3) 12.8 Parametric Approximations and Simulation Methods 436(1) 12.9 Shape-Preserving Methods 437(3) 12.10 Continuous-Time Problems 440(2) 12.11 Further Reading and Summary 442(1) Exercises 443(2) IV PERTURBATION METHODS 445(90) 13 Regular Perturbations of Simple Systems 447(40) 13.1 Mathematics of Regular Perturbation Methods 448(3) 13.2 Comparative Statics 451(2) 13.3 Perturbing an IVP 453(3) 13.4 Perturbing a BVP: Comparative Perfect Foresight Dynamics 456(6) 13.5 Continuous-Time Deterministic Control 462(9) 13.6 Stochastic Control 471(3) 13.7 Perturbing Discrete-Time Systems 474(6) 13.8 Perturbing Jump Process Control Problems 480(2) 13.9 Global Quality Test for Asymptotic Approximations 482(2) Exercises 484(3) 14 Regular Perturbations in Multidimensional Systems 487(24) 14.1 Multidimensional Comparative Statics and Tensor Notation 487(3) 14.2 Linearization of Multidimensional Dynamic Systems 490(6) 14.3 Locally Asymptotically Stable Multidimensional Control 496(6) 14.4 Perturbations of Discrete-Time Problems 502(2) 14.5 Multisector Stochastic Growth 504(5) 14.6 Further Reading and Summary 509(1) Exercises 509(2) 15 Advanced Asymptotic Methods 511(24) 15.1 Bifurcation Methods 511(2) 15.2 Portfolio Choices for Small Risks 513(3) 15.3 Gauge Functions and Asymptotic Expansions 516(1) 15.4 Method of Undetermined Gauges 517(5) 15.5 Asymptotic Expansions of Integrals 522(6) 15.6 Hybrid Perturbation-Projection Methods 528(4) 15.7 Further Reading and Summary 532(1) Exercises 533(2) V APPLICATIONS TO DYNAMIC EQUILIBRIUM ANALYSIS 535(74) 16 Solution Methods for Perfect Foresight Models 537(36) 16.1 A Simple Autonomous Overlapping Generations Model 538(2) 16.2 Equilibrium in General OLG Models: Time Domain Methods 540(7) 16.3 Fair-Taylor Method 547(2) 16.4 Recursive Models and Dynamic Iteration Methods 549(9) 16.5 Recursive Models with Nonlinear Equation Methods 558(4) 16.6 Accuracy Measures 562(1) 16.7 Tax and Monetary Policy in Dynamic Economies 563(4) 16.8 Recursive Solution of an OLG Model 567(1) 16.9 "Consistent" Capital Income Taxation 568(3) 16.10 Further Reading and Summary 571(1) Exercises 571(2) 17 Solving Rational Expectations Models 573(36) 17.1 Lucas Asset-Pricing Model 574(3) 17.2 Monetary Equilibrium 577(1) 17.3 Information and Asset Markets 578(3) 17.4 Commodity Storage Models 581(7) 17.5 A Simple Stochastic Dynamic Growth Model 588(1) 17.6 Projection Methods with Newton Iteration 589(10) 17.7 Fixed-Point Iteration 599(2) 17.8 Time Iteration 601(1) 17.9 Generalizations 602(3) 17.10 Further Reading and Summary 605(1) Exercises 606(3) References 609(14) Index 623