Quantitative Methods and Applications in GIS - Chapter 11 (end)

11 Solving a System of Linear Equations and Application in Simulating Urban Structure This chapter introduces the method for solving a system of linear equations. The technique is used in many applications, including the popular input–output analysis (e.g., Hewings, 1985; see Appendix 11A for a brief introduction). Here, the method is illustrated in solving the Garin–Lowry model, a model widely used by urban planners and geographers for analyzing urban land use structure. A case study using a hypothetical city shows how the distributions of population and employment interact with each other and how the patterns can be affected by the transportation network. The GIS usage in the case study involves the computation of a travel time matrix and other data preparation tasks. The method is fundamental in numerical analysis (NA) and is often used as a building block in many NA tasks, such as solving a system of nonlinear equations and the eigenvalue problem. Appendix 11B shows how the task of solving a system of linear equations is also imbedded in the method of solving a system of nonlinear equations. 11.1 SOLVING A SYSTEM OF LINEAR EQUATIONS A system of n linear equations with n unknowns x1, x2, …, xn is written as a11x1 + a12 x2 +...+ a1n xn = b1 a21x1 + a22 x2 +...+ a2n xn = b2 ...... an1x1 + an2 x2 +...+ ann xn = bn In the matrix form, it is a11 a12 L a1n x1 b1 a21 a22 L a2n x2 = b2 M M O M M M an1 an2 L ann xn bn 219 © 2006 by Taylor & Francis Group, LLC 220 Quantitative Methods and Applications in GIS or simply Ax = b (11.1) If matrix A has a diagonal structure, Equation 11.1 becomes a11 0 L 0 x1 b1 0 a22 L 0 x2 = b2 M M O M M M 0 0 L ann xn bn The solution is simple: xi = bi / aii If aii = 0 and bi = 0, xi can be any real number, and if aii = 0 and bi ¹ 0, there is no solution for the system. There are two other simple systems with easy solutions. If matrix A has a lower triangular structure (i.e., all elements above the main diagonal are 0), Equation 11.1 becomes a11 0 L 0 x1 b1 a21 a22 L 0 x2 = b2 M M O M M M an1 an2 L ann xn bn Assuming aii ¹ 0 for all i, the forward-substitution algorithm is used to solve the system by obtaining x1 from the first equation, substituting x1 in the second equation to obtain x2, and so on. Similarly, if matrix A has an upper triangular structure (i.e., all elements below the main diagonal are 0), Equation 11.1 becomes a11 a12 L a1n x1 b1 0 a22 L a2n x2 = b2 M M O M M M 0 0 L ann xn bn The back-substitution algorithm is used to solve the system. By converting Equation 11.1 to the simple systems as discussed above, one may obtain the solution for a general system of linear equations. Thus, if matrix A can © 2006 by Taylor & Francis Group, LLC Solving a System of Linear Equations and Application in Urban Structure 221 be factored into the product of a lower triangular matrix L and an upper triangular matrix U, such as A = LU, Equation 11.1 can be solved in two stages: 1. Lz = b solve for z 2. Ux = z solve for x The first one can be solved by the forward-substitution algorithm, and the second one by the back-substitution algorithm. Among various algorithms for deriving the LU factorization (or LU decomposi-tion) of A, one called Gaussian elimination with scaled row pivoting is used widely as an effective method. The algorithm consists of two steps: a factorization (or forward-elimination) phase and a solution (involving updating and back-substitution) phase (Kincaid and Cheney, 1991, p. 145). Computation routines for the algorithm of Gaussian elimination with scaled row pivoting can be found in various computer languages, such as FORTRAN (Press et al., 1992a), C (Press et al., 1992b), and C++ (Press et al., 2002). In the program SimuCity.for (see Appendix 11C), the FORTRAN subroutine LUDCOMP implements the first phase and the subroutine LUSOLVE implements the second phase. The two subroutines also call for two other simple routines, SCAL and AXPY. Free FORTRAN compilers can be downloaded from the website http://www.thefreecountry.com/compilers/fortran.shtml and others. The author used a free FORTRAN compiler g77 (free for downloading at http://www.gnu.org/software/fortran/fortran.html) for test running the programs. Section 11.3 discusses how the programs are utilized to solve the Garin–Lowry model. One may also use commercial software MATLAB (www.mathworks.com) or Mathematica (www.wolfram.com) for the task of solving a system of linear equations. 11.2 THE GARIN–LOWRY MODEL 11.2.1 BASIC VS. NONBASIC ECONOMIC ACTIVITIES An interesting debate on the relation between population and employment distribu-tions in a city is whether population follows employment (i.e., workers find resi-dences near their workplaces to save commuting time) or vice versa (i.e., businesses locate near residents for recruiting workforce or providing services). The Garin–Lowry model (Lowry, 1964; Garin, 1966) argues that population and employ-ment distributions interact with each other and are interdependent. However, different types of employment play different roles. The distribution of basic employment is independent of the population distribution pattern and may be considered exogenous. Service (nonbasic) employment follows population. On the other side, the population distribution is determined by the distribution patterns of both basic and service employment. See Figure 11.1 for illustration. The interactions between employment and population decline with distances, which are defined by a transportation network. Unlike the urban economic model built on the assumption of monocentric employ-ment (see the Mills–Muth Economic Model in Appendix 6A), the Garin–Lowry model has the flexibility of simulating a population distribution pattern correspond-ing to any given basic employment pattern, and thus can be used to examine the © 2006 by Taylor & Francis Group, LLC 222 Quantitative Methods and Applications in GIS Basic employment Employment Nonbasic employment Population FIGURE 11.1 Interaction between population and employment distributions in a city. impact of basic employment distribution on population as well as that of transpor-tation network. The binary division of employment into basic and service employment is based on the concept of basic and nonbasic activities. A local economy (a city or a region) can be divided into two sectors: basic sector and nonbasic sector. The basic sector refers to goods or services that are produced within the area but sold outside of the area. It is the export or surplus that is independent of the local economy. The nonbasic sector refers to goods or services that are produced within the area and also sold within the area. It is local or dependent and serves the local economy. By extension, basic employment refers to workers in the basic sector, and service employment refers to those in the nonbasic sector. The concept of basic and nonbasic activities is useful for several reasons (Wheeler et al., 1998, p. 140). It identifies the economic activities that are most important to a city’s viability. Expansion or recession of the basic sector leads to economic repercus-sions throughout the city and affects the nonbasic sector. City and regional planners forecast the overall economic growth based on anticipated or predicted changes in the basic activities. A common approach to determine employment in basic and nonbasic sectors is the minimum requirements approach by Ullman and Dacey (1962). The method examines many cities of approximately the same population size and computes the percentage of workers in a particular industry for each of the cities. If the lowest percentage represents the minimum requirements for that industry in a city of a given population-size range, that portion of the employment is engaged in the nonbasic or city-serving activities. Any portion beyond the minimum requirements is then classified as basic activity. Classifications of basic and nonbasic sectors can be also made by analyzing export data (Stabler and St. Louis, 1990). 11.2.2 THE MODEL’S FORMULATION In the Garin–Lowry model, an urban area is composed of n tracts. The population in any tract j is affected by employment (including both the basic and service employment) in all n tracts, and the service employment in any tract i is determined by population in all n tracts. The degree of interaction declines with distance mea-sured by a gravity kernel. Given a basic employment pattern and a distance matrix, the model computes the population and service employment at various locations. First, the service employment in any tract i, Si, is generated by the population in all tracts k (k = 1, 2, …, n), Pk, through a gravity kernel tik, with © 2006 by Taylor & Francis Group, LLC Solving a System of Linear Equations and Application in Urban Structure 223 Si = eå(P tik ) = eå[P (d−a / åd−a )] (11.2) k=1 k=1 j=1 where e is the service employment/population ratio (a simple scalar uniform across all tracts), dik the distance between tracts i and k, and a the distance friction coefficient characterizing shopping (resident-to-service) behavior. The gravity kernel tik repre-sents the proportion of service employment in tract i owing to the influence of population in tract k, out of its impacts on all tracts. In other words, the service employment at i is a result of summed influences of population at all tracts k (k = 1, 2, …, n), each of which is only a fraction of its influences on all tracts j (j = 1, 2, …, n). Second, the population in any tract j, Pj, is determined by the employment in all tracts i (i = 1, 2, …, n), Ei, through a gravity kernel gij, with P = hå(Eigij ) = hå[(B + Si)(dij b / åd−b)] (11.3) i=1 i=1 k=1 where h is the population/employment ratio (also a scalar uniform across all tracts) and b the distance friction coefficient characterizing commuting (resident-to-work-place) behavior. Note that employment Ei includes both service employment Si and basic employment Bi, i.e., Ei = Si+Bi. Similarly, the gravity kernel gij represents the proportion of population in tract j owing to the influence of employment in tract i, out of its impacts on all tracts k (k = 1, 2, …, n). Let P, S, and B be the vectors defined by the elements Pj, Si, and Bi, respectively, and G and T the matrices defined by gij (with the constant h) and tik (with the constant e), respectively. Equations 11.2 and 11.3 become S = TP (11.4) P = GS + GB (11.5) Combining Equations 11.4 and 11.5 and rearranging, we have (I – GT)P = GB (11.6) where I is the n ´ n identity matrix. Equation 11.6 in the matrix form is a system of linear equations with the population vector P unknown. Four parameters (the distance friction coefficients a and b, the population/employment ratio h, and the service employment/population ratio e) are given; the distance matrix d is derived from a road network, and the basic employment B is predefined. Plugging the solution P back to Equation 11.4 yields the service employment vector S. For more detailed discussion of the model, see Batty (1983). The following subsection offers a simple example to illustrate the model. © 2006 by Taylor & Francis Group, LLC ... - tailieumienphi.vn