Heath - Scientific Computing (523150), страница 49
Текст из файла (страница 49)
Each of the functions g1 and g2 listed nextgives a fixed-point problem that is equivalentto the equation f (x) = 0. For each of thesefunctions, determine whether the corresponding fixed-point iteration scheme xk+1 = gi (xk )√is locally convergent to y if y = 3. Explainyour reasoning in each case.(a) g1 (x) = y + x − x2 .(b) g2 (x) = 1 + x − x2 /y.(c) What is the fixed-point iteration functiongiven by Newton’s method for this particularproblem?5.7 The gamma function has√ the followingknown values:Γ(0.5)=π, Γ(1) = 1,√Γ(0.75) = π/2. From these three values,determine the approximate value x for whichΓ(x) = 1.5, using one step of each of the following methods.(a) Quadratic interpolation(b) Inverse quadratic interpolation(c) Linear fractional interpolation5.8 Express the Newton iteration for solving each of the following systems of nonlinearequations.(a)x21 + x22x21 − x25.5 (a) Show that the iterative methodxk+1 =xk−1 f (xk ) − xk f (xk−1 )f (xk ) − f (xk−1 )is mathematically equivalent to the secantmethod for solving a scalar nonlinear equationf (x) = 0.= 1,= 0.(b)x21 + x1 x323x21 x2 − x32= 9,= 4.COMPUTER PROBLEMS177(c)x21x1 + x2 − 2x1 x2+ x22 − 2x1 + 2x2derivative with a constant value d, that is, weuse the iteration scheme= 0,= −1.xk+1 = xk − f (xk )/d.(d )x31 − x22x1 + x21 x2==(a) Under what condition on the value of d willthis scheme be locally convergent?0,2.(b) What will be the convergence rate, in general?(e)2 sin(x1 ) + cos(x2 ) − 5x14 cos(x1 ) + 2 sin(x2 ) − 5x2==0,0.5.9 Carry out one iteration of Newton’smethod applied to the system of nonlinearequationsx21 − x222x1 x2==0,1,Twith starting value x0 = [ 0 1 ] .(c) Is there any value for d that would stillyield quadratic convergence?5.12 Consider the system of equationsx1 − 1 = 0,x1 x2 − 1 = 0.For what starting point or points, if any, willNewton’s method for solving this system fail?Why?5.10 Suppose you are using the secantmethod to find a root x∗ of a nonlinear equation f (x) = 0.
Show that if at any iteration ithappens to be the case that either xk = x∗ orxk−1 = x∗ (but not both), then it will also betrue that xk+1 = x∗ .5.13 Supply the details of a proof that if x∗ isa fixed point of the smooth function g: R → R,and g 0 (x∗ ) = 0, then the convergence rate ofthe fixed-point iteration scheme xk+1 = g(xk )is at least quadratic if started close enough tox∗ .5.11 Newton’s method for solving a scalarnonlinear equation f (x) = 0 requires computation of the derivative of f at each iteration.
Suppose that we instead replace the true5.14 Verify the formula given in Section 5.2.6for the change h in c when using linear fractional interpolation to find a zero of a nonlinear function.Computer Problems5.1 For the equationf (x) = x2 − x − 2 = 0,each of the following functions yields an equivalent fixed-point problem:g1 (x) =g2 (x) =g3 (x) =g4 (x) =x2 − 2,√x + 2,1 + 2/x,(x2 + 2)/(2x − 1).(a) Analyze the convergence properties ofeach of the corresponding fixed-point iterationschemes for the root x = 2 by considering|gi0 (2)|.(b) Confirm your analysis by implementingeach of the schemes and verifying its convergence (or lack thereof) and approximate convergence rate.5.2 Implement the bisection, Newton, andsecant methods for solving nonlinear equationsin one dimension, and test your implementations by finding at least one root for each of thefollowing equations. What termination criterion should you use? What convergence rate isachieved in each case? Compare your results(solutions and convergence rates) with those178CHAPTER 5.
NONLINEAR EQUATIONSfor a library routine for solving nonlinear equations.then implement the method to confirm yourresults.(a) x3 − 2x − 5 = 0.(a) xk+1 = arccos(−1/(1 + e−2xk )).(b) e−x = x.(b) xk+1 = 0.5 log(−1/(1 + 1/ cos(xk ))).(c) x sin(x) = 1.(c) Newton’s method.(d ) x3 − 3x2 + 3x − 1 = 0.5.3 Repeat the previous exercise, this timeimplementing the inverse quadratic interpolation and linear fractional interpolation methods, and answer the same questions as before.5.4 Consider the functionf (x) = (((x − 0.5) + x) − 0.5) + x,evaluated as indicated (i.e., without any simplification).
On your computer, is there anyfloating-point value x such that f (x) is exactlyzero? If you use a zero-finding routine on thisfunction, what result is returned, and what isthe value of f for this argument? Experimentwith the error tolerance to determine its effecton the results obtained.5.5 Compute the first several iterations ofNewton’s method for solving each of the following equations, starting with the given initial guess.(a) x2 − 1 = 0,(b) (x − 1)4 = 0,x0 = 106 .x0 = 10.For each equation, answer the following questions: What is the apparent convergencerate of the sequence initially? What shouldthe asymptotic convergence rate of Newton’smethod be for this equation? How many iterations are required before the asymptotic rangeis reached? Give an analytical explanation ofthe behavior you observe empirically.5.6 Consider the problem of finding thesmallest positive root of the nonlinear equationcos(x) + 1/(1 + e−2x ) = 0.Investigate, both theoretically and empirically,the following iterative schemes for solving thisproblem using the starting point x0 = 3.
Foreach scheme, you should show that it is indeed an equivalent fixed-point problem, determine analytically whether it is locally convergent and its expected convergence rate, and5.7 In celestial mechanics, Kepler’s equationM = E − e sin(E)relates the mean anomaly M to the eccentricanomaly E of an elliptical orbit of eccentricitye, where 0 < e < 1.(a) Prove that fixed-point iteration using theiteration functiong(E) = M + e sin(E)is locally convergent.(b) Use the fixed-point iteration scheme in parta to solve Kepler’s equation for the eccentricanomaly E corresponding to a mean anomalyof M = 1 (radians) and an eccentricity ofe = 0.5.(c) Use Newton’s method to solve the sameproblem.(d ) Use a library zero finder to solve the sameproblem.5.8 In neutron transport theory, the criticallength of a fuel rod is determined by the rootsof the equationcot(x) = (x2 − 1)/(2x).Use a zero finder to determine the smallestpositive root of this equation.5.9 The natural frequencies of vibration of auniform beam of unit length, clamped on oneend and free on the other, satisfy the equationtan(x) tanh(x) = −1.Use a zero finder to determine the smallestpositive root of this equation.5.10 The vertical distance y that aparachutist falls before opening the parachuteis given by the equationpy = log(cosh(t gk ))/k,COMPUTER PROBLEMSwhere t is the elapsed time in seconds, g =9.8065 m/s2 is the acceleration due to gravity,and k = 0.00341 m−1 is a constant related toair resistance.
Use a zero finder to determinethe elapsed time required to fall a distance of1 km.5.11 If an amount a is borrowed at interestrate r for n years, then the total amount to berepaid is given bya(1 + r)n .Yearly payments of p each would reduce thisamount byn−1X0p(1 + r)i = p(1 + r)n − 1.rThe loan will be repaid when these two quantities are equal.(a) For a loan of a = $100,000 and yearly payments of p = $10,000, how long will it take topay off the loan if the interest rate is 6 percent,i.e., r = 0.06?1795.13 Write a program to solve the system ofnonlinear equations16x4 + 16y 4 + z 4x2 + y 2 + z 2x3 − yusing Newton’s method.
You may solve the resulting linear system at each iteration either bya library routine or by a linear system solverof your own design. As starting guess, youmay take each variable to be 1. In addition,try nonlinear solvers from a subroutine library,based on both Newton and secant updatingmethods, and compare the solutions obtainedand the convergence rates with those for yourprogram.5.14 The derivation of a two-point Gaussianquadrature rule (which we will consider inSection 8.3) on the interval [−1, 1] using themethod of undetermined coefficients leads tothe following system of nonlinear equations forthe nodes x1 , x2 and weights w1 , w2 :(b) For a loan of a = $100,000 and yearlypayments of p = $10,000, what interest rater would be required for the loan to be paid offin n = 20 years?w1 + w2w1 x1 + w2 x2(c) For a loan of a = $100,000, how large mustthe yearly payments p be for the loan to bepaid off in n = 20 years at 6 percent interest?w1 x31 + w2 x32You may use any method you like to solve thegiven equation in each case.
For the purposeof this problem, we will treat n as a continuousvariable (i.e., it can have fractional values).5.12 (a) Write a program using Newton’smethod to compute the nth root of a givennumber y, that is, to solve the nonlinear equation f (x) = xn − y = 0 for x, given y and n.Since we want to be able to compute any nthroot, your routine should work for complex aswell as real roots. Test your program by computing the complex cube root of 3 lying in theupper left quadrant of the complex plane, using x0 = −1 + i as starting guess.(b) Repeat part a, but this time use Muller’smethod (i.e., successive quadratic polynomialinterpolation). For this method, you will needtwo additional starting guesses.= 16,= 3,= 0w1 x21 + w2 x22= 2,= 0,2,=3= 0.Solve this system for x1 , x2 , w1 , and w2 usinga library routine or one of your own design.How many different solutions can you find?5.15 Use a library routine, or one of your owndesign, to solve the following system of nonlinear equations:sin(x) + y 2 + log(z) = 3,3x + 2y − z 3 = 0,x2 + y 2 + z 3 = 6.Try to find as many different solutions as youcan.
You should find at least four.5.16 Each of the following systems of nonlinear equations may present some difficultyin computing a solution. Use a library routine, or one of your own design, to solve eachof the systems from the given starting point.180CHAPTER 5.