Heath - Scientific Computing (523150), страница 59
Текст из файла (страница 59)
For areasonable error tolerance, does your routineterminate in at most n steps for a quadraticfunction of n variables?6.13 Using a library routine or one of yourown design, find least squares solutions to thefollowing overdetermined systems of nonlinearequations:(a)x21 + x22(x1 − 2)2 + x22(x1 − 1)2 + x22===2,2,9.(b)x21 + x22 + x1 x2 = 0,sin2 (x1 ) = 0,cos2 (x2 ) = 0.6.14 The concentration of a drug in thebloodstream is expected to diminish exponentially with time.
We will fit the model functiony = f (t, x) = x1 ex2 tto the following data:tyty0.56.802.50.481.03.003.00.251.51.503.50.202.00.754.00.15(a) Perform the exponential fit using nonlinearleast squares. You may use a library routineor one of your own design, perhaps using theGauss-Newton method.(b) Taking the logarithm of the model function gives log(x1 ) + x2 t, which is now linearin x2 . Thus, an exponential fit can also bedone using linear least squares, assuming thatwe also take logarithms of the data points yi .Use a linear least squares routine, or one ofyour own design, to compute x1 and x2 in thismanner. Do the values obtained agree withthose determined in part a? Why?6.15 A bacterial population P grows according to the geometric progressionPk = rPk−1 ,where r is the growth rate. The following population counts (in billions) are observed:kPkkPk10.1952.520.3664.730.6978.541.3814(a) Perform a nonlinear least squares fit of thegrowth function to these data to estimate theinitial population P0 and the growth rate r.(b) By using logarithms, a fit to these datacan also be done by linear least squares (seeprevious exercise).
Perform such a linear leastsquares fit to obtain estimates for P0 and r,and compare your results with those for thenonlinear fit.6.16 The Michaelis-Menten equation describes the chemical kinetics of enzyme reactions. According to this equation, if v0 is theinitial velocity, V is the maximum velocity, Kmis the Michaelis constant, and S is the substrate concentration, thenv0 =V.1 + Km /S216CHAPTER 6. OPTIMIZATIONIn a typical experiment, v0 is measured as Sis varied, and then V and Km are to be determined from the resulting data.(a) Given the measured data,Sv0Sv02.50.02415.00.0605.00.03620.00.064f (t, x) = x1 + x2 t + x3 t2 + x4 ex5 tto the following data:10.00.053determine V and Km by performing a nonlinear least squares fit of v0 as a function of S.You may use a library routine or one of yourown design, perhaps using the Gauss-Newtonmethod.(b) To avoid a nonlinear fit, a number ofresearchers have rearranged the MichaelisMenten equation so that a linear least squaresfit will suffice.
For example, Lineweaver andBurk used the rearrangement11Km 1=+·voVVSand performed a linear fit of 1/vo as a function of 1/S to determine 1/V and Km /V , fromwhich the values of V and Km can then bederived. Similarly, Dixon used the rearrangementKm1S=+ ·Sv0VVand performed a linear fit of S/v0 as a function of S to determine Km /V and 1/V , fromwhich the values of V and Km can then bederived. Finally, Eadie and Hofstee used therearrangementv0 = V − Km ·6.17 We wish to fit the model functionv0Sand performed a linear fit of v0 as a functionof v0 /S to determine V and Km .Verify the algebraic validity of each of theserearrangements.
Perform the indicated linearleast squares fit in each case, using the samedata as in part a, and determine the resulting values for V and Km . Compare the results with those obtained in part a. Why dothey differ? For which of these linear fits arethe resulting parameter values closest to thosedetermined by the true nonlinear fit for thesedata?tytyty0.0020.000.7575.461.5054.730.2551.581.0074.361.7537.980.5068.731.2567.092.0017.28We must determine the values for the five parameters xi that best fit the data in the leastsquares sense. The model function is linear inthe first four parameters, but it is a nonlinearfunction of the fifth parameter, x5 .
We willsolve this problem in five different ways:(a) Use a general multidimensional unconstrained minimization routine with g(x) =1 T2 r (x)r(x) as objective function, where ris the residual function defined by ri (x) =yi − f (ti , x). This method will determine allfive parameters (i.e., the five components of x)simultaneously.(b) Use a multidimensional nonlinear equationsolver to solve the system of nonlinear equations ∇g(x) = 0.(c) Given a value for x5 , the best values forthe remaining four parameters can be determined by linear least squares.
Thus, we canview the problem as a one-dimensional nonlinear minimization problem with an objectivefunction whose input is x5 and whose outputis the residual sum of squares of the resulting linear least squares problem. Use a onedimensional minimization routine to solve theproblem in this manner. (Hint: Your routinefor computing the objective function will inturn call a linear least squares routine.)(d ) Solve the problem in the same manner as c,except use a one-dimensional nonlinear equation solver to find a zero of the derivative ofthe objective function in part c.(e) Use the Gauss-Newton method for nonlinear least squares to solve the problem. Youwill need to call a linear least squares routineto solve the linear least squares subproblem ateach iteration.COMPUTER PROBLEMS217In each of the five methods, you may computeany derivatives required either analytically orby finite differences.
You may need to dosome experimentation to find a suitable starting value for which each method converges. Ofcourse, after you have solved the problem once,you will know the correct answer, but try touse “fair” starting guesses for the remainingmethods. You may need to use global variables in MATLAB or C, or common blocks inFortran, to pass information to subroutines insome cases.+(x4 − 1)2 + (x5 − 1)2subject tox1 + 3x2x3 + x4 − 2x5x2 − x5= 0,= 0,= 0.(b) Quadratic objective function and nonlinearconstraints:min f (x) = 4x21 + 2x22 + 2x23x6.18 Use a library routine for linear programming to solve the following problem:−33x1 + 16x2 − 24x3subject tomax f (x) = 2x1 + 4x2 + x3 + x4x3x1 − 2x224x1 − x23subject to the constraintsx1 + 3x2 + x42x1 + x2x2 + 4x3 + x4≤ 4≤ 3≤ 3= 7,= 11.(c) Nonquadratic objective function and nonlinear constraints:min f (x) = (x1 − 1)2 + (x1 − x2 )2andxxi ≥ 0,i = 1, 2, 3, 4.6.19 Use the method of Lagrange multipliersto solve each of the following constrained optimization problems.
To solve the resulting system of nonlinear equations, you may use a library routine or one of your own design. Onceyou find a critical point of the Lagrangian function, remember to check it for optimality, either by sampling the objective at nearby feasible points, or using the second-order optimality condition. You may also wish to compareyour results with those of a library routine designed for constrained optimization.(a) Quadratic objective function and linearconstraints:min f (x) = (4x1 − x2 )2 + (x2 + x3 − 2)2x+(x2 − x3 )2 + (x3 − x4 )4 + (x4 − x5 )4subject tox1 + x22 + x33=x2 − x23 + x4x1 x5==√3 2 + 2,√2 2 − 2,2.6.20 Use the method of Lagrange multipliers to find the radius and height of a cylinderhaving minimum surface area subject to theconstraint that its volume is one liter (1000cc).
See Example 6.1. How does the resultingshape compare with that of one-liter cans orbottles you see in a grocery store? How doesthe resulting surface area compare with thatof a sphere having the same volume?218CHAPTER 6. OPTIMIZATIONChapter 7Interpolation7.1InterpolationInterpolation simply means fitting some function to given data so that the function has thesame values as the given data. We have already seen several instances of interpolation invarious numerical methods, such as linear interpolation in the secant method for nonlinearequations and successive parabolic interpolation for minimization.
We will now make amore general and systematic study of interpolation.In general, the simplest interpolation problem in one dimension is of the following form:for given data(ti , yi ), i = 1, . . . , n,with t1 < t2 < · · · < tn , we seek a function f such thatf (ti ) = yi ,i = 1, . . . , n.We call f an interpolating function, or simply an interpolant, for the given data. It isoften desirable for f (t) to have “reasonable” values for t between the data points, but sucha requirement may be difficult to quantify. In more complicated interpolation problems,additional data might be prescribed, such as the slope of the interpolant at given points,or additional constraints might be imposed on the interpolant, such as monotonicity, convexity, or the degree of smoothness required.
One could also consider higher-dimensionalinterpolation in which f is a function of more than one variable, but we will not do so inthis book.7.1.1Purposes for InterpolationInterpolation problems arise from many different sources and may have many differentpurposes. Some of these include:• Plotting a smooth curve through discrete data points• Quick and easy evaluation of a mathematical function219220CHAPTER 7. INTERPOLATION• Replacing a “difficult” function by an “easy” one• “Reading between the lines” of a table• Differentiating or integrating tabular data7.1.2Interpolation versus ApproximationBy definition, an interpolating function fits the given data points exactly.
Interpolation isusually not appropriate if the data points are subject to experimental errors or other sourcesof significant error. It is usually preferable to smooth out such noisy data by a techniquesuch as least squares approximation (see Chapter 3).Another context in which approximation is generally more appropriate than interpolation is in the design of library routines for computing special functions, such as those usuallysupplied by the Fortran and C math libraries. In this case, it is important that the approximating function be close to the exact underlying mathematical function for argumentsthroughout some domain, but it is not essential that the function values match exactly atany particular points. An appropriate type of approximation in this case is to minimize themaximum deviation between the given function and the approximating function over someinterval.
This approach is variously known as uniform, Chebyshev, or minimax approximation. A general study of approximation theory and algorithms is beyond the scope of thisbook, however, and we will confine our attention to interpolation.7.1.3Choice of Interpolating FunctionIt is important to realize that there is some arbitrariness in most interpolation problems.There are arbitrarily many functions that interpolate a given set of data points. Simplyrequiring that some mathematical function fit the data points exactly leaves open suchquestions as:• What form should the function have? There may be relevant mathematical or physicalconsiderations that suggest a particular form of interpolant.• How should the function behave between data points?• Should the function inherit properties of the data, such as monotonicity, convexity, orperiodicity?• If the function and data are plotted, should the results be visually pleasing?• Are we interested primarily in the values of the parameters that define the interpolatingfunction, or simply in evaluating the function at various points for plotting or otherpurposes?The choice of interpolating function depends on the answers to these questions as well asthe data to be fit.The selection of a function for interpolation is usually based on:• How easy the function is to work with (determining its parameters from the data, evaluating the function at a given point, differentiating or integrating the function, etc.)• How well the properties of the function match the properties of the data to be fit (smoothness, monotonicity, convexity, periodicity, etc.)7.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
