Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 38
Текст из файла (страница 38)
Further, if also the second partial derivatives of the component functions of f are continuous, thenfor some constant c and all sufficiently large m. In other words, Newton’smethod converges quadratically (see Example 5.6).Examplc 5.4 Determine numbers 0 < ξ1 < ξ2 < · · · < &, < l so thatwith ξ0 - 0 and ξn+1 = l, and G(x) = x 3 .This requires solution of the systemorwithCorrespondingly, the Jacobian matrix f´(x) is tridiagonal, of the formHence, in solving the Newton equationf´(x)b = -f(x)for the correction h to x, one would employ Algorithm 4.3 for the solution of a linearsystem with tridiagonal coefficient matrix.It can be shown that this problem has exactly one solution.
Note that the Jacobianmatrix f´(ξ)(ξ) at any solution ξ with ξ1 < · · · < ξn is strictly diagonally dominant (seeExercise 5.2-2), hence f´(ξ) is invertible. We would therefore expect quadratic convergence if the initial guess x (0) is chosen sufficiently close to ξ.218*SYSTEMS OF EQUATIONS AND UNCONSTRAINED OPTIMIZATIONWe try it with x(0) = [l 2 · · · n ] T /( n + 1) and n = 3, and get the followingiterates and errors.x( m )m012340.25000000.35833330.33862430.33791800.3379171||f( x(0.50000000.60000000.58569490.58529010.58528960.75000000.80833330.80180150.80163470.80163450.1880.3400.1090.1570.284m )||1||h|| 1+ 0- 1- 2- 5- 110.8890.1350.4260.5120.823-113612The quadratic convergence is evident, both in the decrease of the size of the residualerror f(x( m ) ) and in the decrease of the size of the Newton correction h for x (m).
Thecalculations were run on a UNIVAC 1110, in double precision (approximately 17decimal digits).Use of Newton’s method brings with it certain difficulties not apparentin the above simple example. Chiefly, there are two major difficulties: (1)lack of convergence because of a poor initial guess, and (2) the expense ofconstructing correctly and then solving the Newton equation for thecorrection h.
We will now discuss both of these in turn.Two ideas have been used with some success to force, or at leastencourage, convergence, viz., continuation or imbedding, and damping. Incontinuation, one views the problem of solving f(ξ)(ξ) = 0 appropriately as thelast one in a continuous one-parameter family of problemsg(ξ, t) = 0withg(x, 1) = f(x)and g(x, 0) a function for which there is no difficulty in solvingg(ξ, 0) = 0Having found ξ(0) so that g(ξ (0), 0) = 0, one chooses a sequence 0 = to < t1<· · · < tN = 1 and solves the equationg (ξ(i), ti ) = 0by Newton’s method for i = 1, 2, . .
. , N, using as a first guess the vectorξ ( i - 1) or, perhaps, even the extrapolated vector(if i > 1). The hope is that the neighboring problems g(ξ,ξ, ti) = 0 andg (ξ,ξ, ti - 1) = 0 are close enough to each other so that a good solution to oneprovides a good enough first guess for the solution of the other. Customarychoice for g are*5.2NEWTON’S METHOD219In the damped Newton’s method, one refuses to accept the nextNewton iterate x( m +1) = x( m ) + h if this leads to an increase in the residualerror, i.e., if ||f(x(m + 1 ))||2 > ||f(x(m ) )||2.
In such a case, one looks at thevectors x ( m ) + h/2i for i = 1, 2, . . . , and takes x ( m +1) to be the first suchvector for which the residual error is less than ||f(x( m ) )||2 .Algorithm 5.4: Damped Newton’s method for a system Given thesystem f(ξ)(ξ) = 0 of n equations in n unknowns, with f a vector-valuedfunction having smooth component functions, and a first guess x(0) fora solution ξ of the system.For m = 0, 1, 2, . . . until satisfied, do:It is not clear, offhand, whether Step * can always be carried out.
For ito be defined, it is necessary and sufficient that the Newton direction h bea descent direction at x = x( m ) for the functionSinceby (5.5) and (5.6), h is a descent direction for F at x if and only ifOn the other hand, h = -f´(x)- 1 f(x).ThereforeThis shows that the Newton direction is, indeed, a descent direction forF(x) =hence the integer i in Step * is well defined.In practice, though, one would replace Step * bywith jmaxIF i is not defined, THEN FAILURE EXITELSEchosen a priori, for example, jmax = 10.Example 55 The system f(ξ)(ξ) = 0 withhas several solutions. For that reason, the initial guess has to be picked carefully toensure convergence to a particular solution, or, to ensure convergence at all.The Newton equations are220*SYSTEMS OF EQUATIONS AND UNCONSTRAINED OPTIMIZATIONStarting with the initial guess x(0) - [2 2] T .
we obtain the following sequence ofiterates.Clearly, the iteration is not settling down at all. But now we employ the dampedNewton’s method, starting with the same first guess.We have listed here also, for each iteration, the integer i determined in Step * ofAlgorithm 5.4. Initially, the proposed steps h are rather large and are damped by asmuch asCorrespondingly, the size ||f(x( m ) )||2 of the residual error barelydecreases from step to step. But, eventually, the full Newton step is taken and theiteration converges quadratically, as it should.
(It is actually a thrilling experience towatch such an iteration on a computer terminal, One feels like cheering when thequadratic convergence sets in eventually.)The calculations were run in single precision on a UNIVAC 1110. The error||f(x (14))||2 is therefore at noise level.The second difficulty in the use of Newton’s method lies with theconstruction and solution of the Newton equation for the correction h.*5.2NEWTON’S METHOD221Already the construction of the Jacobian matrix is difficult if f is of anycomplexity, because it offers so many opportunities for making mistakes,both in the derivation and in the coding of the entries of f’. Consequenceof such mistakes is usually loss of quadratic convergence, or, in extremecases, loss of convergence.
Some computing centers now offer programsfor the symbolic differentiation of expressions, and even of functions givenby a subroutine. Such programs are of tremendous help in the constructionof Jacobian matrices. If such programs are not available, then one mighttest one’s coded Jacobian f´(x) by comparing it at some point x withsimple-minded numerical approximations to its entries, of the form(5.8)or(5.9)familiar from calculus (see Chap. 7).Alternatively, one might be content to code only the functionsf 1 , .
. . , f n , and then use formula (5.8) or (5.9) to construct a suitableapproximation J to f´(x). This requires proper choice of the step size ε (seeSec. 7.1).Let Jm be the Jacobian f´(x( m ) ) or a suitable approximation for it. OnceJm has been constructed, one must solve the systemJ m h = -f(x( m ) )for the correction h. In general, Jm is a full matrix of order n, so thatoperations are required to obtain h. On the other hand, if there isconvergence and f´(x) depends continuously on x, then f´(x( m + k ) ) will differlittle from f(x( m ) ).
It is then reasonable to use f´(x ( m ) ) in place of f´(x( m + k ) )for a saving in work, since, having once factored f´(x( m ) ), we can solve foradditional right sides at a cost ofonly. This is the modified Newtonmethod, in which Jm+k = f´(x( m ) ) for k = 0, 1, 2, . . . until or unless aslowdown in convergence signals that Jm+k be taken as a more recentJacobian matrix.A more extreme departure from Newton’s method is proposed in theso-called matrix-updating methods, in which Jm+1 is obtained from Jm byaddition of a matrix of rank one or two which depends on Jm, x ( m ), h,f(x( m ) ), and f(x( m +1)). The idea is to choose Jm+1 in such a way that, withandone getsThis is reasonable because there should be approximate equality here incase Jm+1 = f´(x) for x near x( m ) .222*SYSTEMS OF EQUATIONS AND UNCONSTRAINED OPTIMIZATIONIf the matrix added to Jm has rank one or two, then it is possible toexpress the resulting change in K m = J m -1 as addition of some easilycalculable matrix.
Thus, by keeping track of Km rather than Jm , one canavoid the need to factor the J m ‘s. A popular scheme of this type isBroyden’s method. Here, one calculates initially K0 = f´(x ( 0 ))-1, and thenforms Km+1 , from Km by(5.10)with(5.11)The corresponding Jm = Km-1 satisfieswhilefor all z perpendicular to δxIn practice, one would use damping in this iterative scheme, too.EXERCISES5.2-l Use Newton’s method to find solutions of the systemwith F the function ofExercise 5.1-1. Compare your effort with that required in Exercise 5.1-2.5.2-2 Prove: If G´(c) - G[a,b] and a < c < b, and G´´(x), G´´´(x) are both positive on [a, b],then c > (a + b)/2. [Hint: Let = (a + b)/2 and show that< G[a,b] by expandingeverything in a Taylor series aroundElse, use (7.8) directly.]Conclude that the Jacobian matrix f´(ξ) of Example 5.4 is strictly diagonally dominant,hence invertible.5.23 Use Newton’s method to find a solution of the following somewhat complicated systemin 0 < x, y < 1.(The arguments of the trigonometric functions here are meant to be measured in radians, ofcourse.)If you fail to get quadratic convergence, check your coding of the Jacobian matrix, byusing (5.8) or (5.9).5.2-4 Apply damped Newton’s method to the solution of the problem discussed in Example5.5 starting with x(0) = [2 1] T .5.2-5 Try to solve the problem in Example 5.5 by continuation, starting with x(0) = [2 1] T ,and using to, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
