SOME SUCCESSIVE APPROXIMATION METHODS IN CONTROL AND OSCILLATION THEORY
Peter L. Falb Division of Applied Mathematics Brown University Providence, Rhode Island
Jan L. de Jong National Aerospace Laboratory NLR Noordoostpolder, The Netherlands
ACADEMIC PRESS: INC.
ALL RIGHTS RESERVED. N O PART OF THIS BOOK MAY BE REPRODUCED I N ANY FORM, BY PHOTOSTAT, MICROFILM, RETRIEVAL SYSTEM, OR ANY OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM THE PUBLISHERS.
ACADEMIC PRESS, INC. 111 Fifth Avenue, New York, New York 10003
United Kingdom Edition published by ACADEMIC PRESS, INC. (LONDON) LTD. Berkeley Square House, London W1X 6BA
LIBRARY OF CONGRESS CATALOG CARDNUMBER: 73-91420 SUBJECT CLASS~FICATIONS 6562, 9301
Successive approximation methods have been used for the solution of two-point boundary value problems for a number of years. In this book, we examine several of these methods. Noting that two-point boundary value problems can be represented by operator equations, we adopt a functional analytic viewpoint and translate results on such operator theoretic iterative methods as Newton’s method into the two-point boundary value problem context. Our emphasis is on results of potential practical applicability rather than on results of the greatest generality. We owe a significant debt of gratitude to many of our colleagues for their invaluable assistance in the preparation of this book. In particular, we wish to thank Dr. W. E. Bosarge, Jr., of IBM, Professor Elmer Gilbert of the University of Michigan, and Professor Jack Hale of Brown University for their numerous helpful suggestions and comments. We also gratefully acknowledge the support that we have received from the United States Air Force under Grant No. AFOSR 693-67 and Grant No. AFOSR 814-66 and from the National Science Foundation under Grant No. GK-967 and Grant No. GK-2788. Finally, we should like to express our deep appreciation to Miss Kate Nolan for her excellent typing of the manuscript.
PETERL. FALB JANL. DE JONG
IN T R O D UCTlO N 1 .I. Introduction
1.2.
1.3.
2.1.
2.2.
2.3.
2.4.
2.5.
3.1.
3.2.
3.3.
3.4.
3.5.
3.6.
3.7.
3.8.
3.9.
3.11. A Lemma on Equivalence: Discrete Case Appendix. Lipschitz Norms
A P P L I C A T I O N TO C O N T R O L PROBLEMS 4.1.
4.2.
4.3.
4.4.
4.5.
4.6.
Application t o Continuous Problems II: The Modified Contraction Mapping Method
4.7.
4.8.
4.9.
4.10. Application t o Discrete Problems II: The Modified Contraction Mapping Method
4.11. Application t o Discrete Problems 111: Newton’s Method
4.12. Summary
A P P L I C A T I O N TO O S C I L L A T I O N PROBLEMS 5.1.
5.2.
5.3.
S O M E N U M E R I C A L EXAMPLES 6.1.
6.2.
6.3.
6.4.
.
T h e central theme of this book is the study of some iterative methods for the solution of two-point boundary value problems (TPBVP’s) of the form
where F, g, and h are suitable vector valued functions. and c is a constant vector. Such TPBVP’s arise in control and oscillation problems. T h e basic approach which we use is to represent the TPBVP by an operator equation and then apply functional analytic results on the iterative solution of operator equations. I n other words, (1.1) or (1.2) is represented by an equivalent operator equation
on a suitable Banach space and results relating to convergence of algorithms of the form yn,-l = v ( y n ) for the solution of (1.3) are translated into convergence theorems for the iterative solution of (1.1) or (1.2). I n particular, we examine the contraction mapping method, Newton’s method and some multipoint methods. Our goal is to obtain convergence conditions and rates which depend upon the functions F, g, and h and other quantities known a priori. 1
2 1.2.
1.
Optimal control theory has experienced an increasing growth of interest during the past two decades. Reasons for this growing intcrest include the stringent requirements of a rapidly developing space technology and the change in system design philosophy brought about by the high speed electronic computer. One area of control which receives considerable current attention is the numerical computation of optimal controls. This book is, in part, concerned with the theoretical and practical aspects of some closely related computational procedures for the numerical solution of certain classes of control problems. An essential difference between optimal control problems and problems in conventional servomechanism theory is the explicit formulation of the control objective in optimal control problems. These control objectives are most frequently expressed as a functional defined on the set of admissible controls. This fact makes optimal control problems problems of the calculus of variations. T h e growing interest in optimal control therefore stimulated a renewed interest in the calculus of variations and variational techniques in general (see Rerkovitz [B4] and Neustadt “31). One of the new variational techniques considered was based on a geometrical interpretation of optimal control problems. This led to an important contribution to control theory, namely the “maximum principle” of Pontryagin [P3]. At present, the Maximum Principle occupies an important position in control theory. Good surveys of other contributions to optimal control theory (as of 1965 and 1966) have been published by Paiewonski [Pl] and Athans [A3]. Since optimal control problems often cannot be solved analytically, one has to resort to iterative numerical methods. A number of such methods for the computation of optimal controls have been and are being proposed. Loosely speaking, all these methods can be divided into two categories: namely, (1) direct and (2) indirect methods. Direct methods involve the generation of a sequence (or family) of control functions with the property that each successive control function results in a lower value of the cost functional. Indirect methods involve the determination of functions (extremals) which satisfy the necessary conditions for an optimum. Since the application of the Pontryagin principle (or the multiplier rule of the calculus of variations) results in necessary conditions for optimality in the
1.2.
form of a TPBVP, most indirect methods are essentially methods for the solution of these TPBVP’s. An example of a method which can be classified as a direct method is the well known gradient method. This method was first proposed for control problems by Bryson [BlO] and Kelley [K5]. Since then, numerous applications and modifications of it have been reported in the literature. An example of an indirect method is the so-called “shooting method” (Breakwell [B8]). This method consists of the systematic variation of the initial values of solutions of the differential equation until the final values satisfy the terminal conditions. Since the solutions of optimal control problems are often very sensitive to changes in the initial conditions, the “shooting method” has often not been very successful in applications. A second indirect method, which is essentially an improvement of the “shooting method,” is the method of the second variation (Breakwell et al. [B9] and Kelley et al. [K6]). This method is based on the use of linear perturbation equations for the evaluation of the corrections of the initial values. An indirect method which is basically different from the two methods mentioned is the generalized Newton-Raphson method (McGill and Kenneth [K7, M31). This method, which is also known as the quasi-linearization method (Bellman and Kalaba [B3]), is based on the replacement of the nonlinear TPBVP by a sequence of linear problems whose solutions converge to the solution of the original nonlinear TPBVP. Another indirect method based on this general idea is Picard’s method. T h e generalized NewtonRaphson method (which we call Newton’s method) and Picard’s method are two of the basic methods considered here. These methods by no means exhaust the different types of computational procedures for the solution of optimal control problems. An important class of indirect methods which should be mentioned is the class of methods which make use of finite difference techniques (e.g., Van Dine et al. [Vl]). Also, a number of computational procedures have been developed for optimal control problems with special properties (e.g., linearity in the state or in the control). Examples of these methods are the methods proposed by Neustadt “21 and Barr and Gilbert [Bl]. Another class of methods, which can be classified as both direct and indirect involves dynamic programming (Bellman [B2]). I n this case the necessary condition for optimality is a special type of functional equation instead of a TPRVP. As a result of the large computer memory requirements, dynamic
1.
programming is not always effective in the solution of realistic optimal control problems. T h e merits of various iterative procedures can be judged on the basis of such criteria as speed of convergence, sensitivity to numerical errors such as roundoff and truncation errors, computability of error bounds and existence of convergence conditions. These criteria, which are partly practical and partly theoretical in nature, are important in deciding which iterative method is to be used in a particular problem as well as for the comparison of different methods. Knowledge of the factors on which these criteria depend provides considerable insight into a computational procedure. This, in turn, may lead to a better practical utilization of the method. Theoretical aspects of these criteria have been investigated by numerous applied mathematicians, among them the Russian Kantorovich. Kantorovich was one of the first to realize the power of functional analysis methods in the unification and development of a mathematical theory of iterative methods [K2]. As illustrated in his book [K3] as well as in the books by Collatz [C4] and Goldstein [G3] and in the article of Antosiewicz and Rheinboldt [A2], many practical iterative methods can be viewed as special applications in particular function spaces of such basic iterative methods as the method of contraction mappings, the method of conjugate gradients, a n d Newton’s method. Using this point of view, various functional analytic results on the convergence of the basic iterative methods can be translated into practical convergence criteria for particular versions of these iterative methods. A number of examples of such translations for the application of iterative methods to a variety of problems are givcn in the references mentioned. Practical convergence criteria are few for most of the iterative methods used in the solution of optimal control problems. For the iterative methods considered here, some general results have been published previously. T o be specific, practical convergence criteria for the application of Picard’s and Newton’s method to TPBVP’s have been presented by Collatz [C4]. These results, however, pertain primarily to higher order ‘TPBVP’s given by a single differential equation rather than a system of first order differential equations. ‘Therefore, they must be adapted to the usual type of problem arising in optimal control thcory (which involve systems of differential equations). T h e only comparable results in the optimal control literature
1.3.
are the convergence theorems for the application of Newton’s method published by McGill and Kenneth [M2] and Bellman and Kalaba [B3]. These theorems hold only for TPBVP’s which are either of second order with both (linear) boundary conditions relating to the same variable [B3] or which can be expressed as a system of such second order problems. They are, therefore, not generally applicable. Motivated by this apparent lack of general results, we have as our first objective the derivation of generally applicable convergence criteria for the applications of Picard’s and Newton’s methods to the solution of optimal control problems. Of the two methods, only Newton’s method has been applied on a wide scale to problems arising in optimal control theory. Picard’s method, although very old (Picard applied the method already in the year 1890) and well known in the mathematical literature, has not yet been used for the solution of optimal control problems to any appreciable extent. A second objective is therefore the consideration of the feasibility and practicality of the application of Picard’s method to the solution of optimal control problems. Problems with boundary conditions of the form
frequently arise in the study of oscillation problems and are often amenable to the methods which we discuss. Considerable work has been done on oscillation problems from this point of view. Excellent summaries of this work are given by Hale [HI, H2].
1.3.
We begin the actual development with a discussion of operator theoretic iterative methods in Chapter 2. We examine the method of contraction mappings, the modified contraction mapping method, Newton’s method, and some multipoint methods. Our treatment is based on the work of Kantorovich [K3] and is aimed at those results which are amenable to practical use. We consider the problem of developing suitable representations for continuous and discrete TPBVP’s in Chapter 3. Since these representations involve linear TPBVP’s in a critical way, we devote
1.
= c.
If (3.1) or (3.2) always has a unique solution for all f and c, then we call the set of matrices { V ( t ) ,M , N } or {A(j),B ( j ) ,M , N } a “boundarycompatible set.” This notion of boundary compatibility is crucial to us. For example, if { V ( t ) ,M , N } is boundary compatible, then (under suitable assumptions) the TPBVP ( I . 1 ) has the equivalent representation (3.3)
where I I “ M ” ( t ) and G V M ~ ( t s) , are the Green’s matrices associated with (3.1). I n other words, (1.1) is represented by an operator equation (3.3). We discuss these representations, treat some examples, compute and estimate certain operator derivatives, and prove some lemmas on equivalence in the remainder of Chapter 3 . In Chapter 4, we combine the results of Chapters 2 and 3 to obtain convergence theorems for the iterative solution of TPBVP’s of the type that arise in control. We briefly discuss the way in which optimal control problems can be reduced to TPBVP’s using the Pontryagin principle. We then proceed to the main work of the chapter, i.e., the translation and application of the results of Chapters 2 and 3 to these TPBVP’s. We apply the results of Chapters 2 and 3 to several classes of TPHVP’s arising in the study of oscillation problems in the brief Chapter 5. In particular, we examine “almost linear problems” and problems with boundary conditions of the form y(0) = y(1) (socalled “pcriodic” boundary conditions). We also treat some second order examples in detail. Finally, in Chapter 6, we study the numerical solution of some simple problems in order to obtain a better appreciation for the practical aspects of the iterative methods discussed in Chapters 4 a n d 5. We consider two “standard” trajectory optimization problems involving a low-thrust Earth-to-Mars orbital transfer and an oscillation problem for a simple spring with a nonlinear restoring force.
2.1.
A large variety of control and oscillation problems can be reduced to two point boundary value problems (TPBVP’s). We shall show, in Chapter 3, that such boundary value problems can be represented by operator equations of the form (1.1) or of the form
F(Y) =0 where T and F are suitable operators. Since Eqs. (1.1) and (1.2) can frequently be solved using iterative methods, we review several of these methods here. I n particular, we discuss the method of contraction mappings and Newton’s method. Both of these methods are methods of successive approximation in that they are characterized by the fact that each new iterate is obtained by a single transformation of the previous iterate. Our treatment is based on the work of Kantorovich [K3]. However, since our discussion is aimed at the application of the theory to the solution of TPBVP’s, we pay more attention to those results which can be easily evaluated and verified than to those results which, though sharper, are not amenable to practical use.
2.2.
We prove two fundamental theorems on the method of contraction mappings. These theorems lie at the heart of our entire development. We begin with the following. 7
2.
DEFINITION 2.1. Let Y be a topological space and let T map Y i n t o itself. Let y o be an element of Y . The sequence { y n } generated by t h e algorithm (2.2)
...
CM sequence for T based on y o .
DEFINITION 2.3. Let Y be a topological space and let T be a map of 1’ i n t o Y . A subset Q of Y i s T invariant (or simply invariant) if T(Q)C B.
THEOREM 2.4. Let Y be a complete metric space with m e t r i c p and l e t Q be a closed subset o f Y . If 7’ maps Y i n t o Y , if 8 i s 7‘ invariant, and if II’ is a contraction, i.e., if there i s an 01 with I such that 0 1
for all y , y ’ i n Q, then (i) the CM sequence { y p Lfor } T based o n any y o i n Q converges t o t h e unique fixed point y* of T i n Q, and (ii) t h e rate of convergence of { y l l }is given by
1,2, . . . .
Proof. Since Q is T invariant and y o E Q, we have y n It then follows from (2.5) that
for all n. For any intcger p
all n.
2.2.
As a < 1, the sequence {yrL}is Cauchy. Since Q is closed and Y is complete, {y,} converges to an element y* of Q. Now, P(Yn-I1> T ( Y * ) )= P(T(Yn), T ( Y * ) )G 4 Y n , Y * )
and so { y n }also converges to T ( y * ) . Thus, y* If y‘ is another fixed point of T in Q, then
T(y*).
P(Y’,Y*) ==P(T(Y’)?T ( Y * ) )G 4 Y ’ , Y * ) .
a < I , we have y’ = y*. T h e inequality (2.6) is an Since 0 immediate consequence of (2.7) and (2.8). Thus, the proof is complete. Theorem 2.4 is a fixed point theorem. Its form is quite simple. A more general fixed point theorem applies to contraction mappings in pseudometric spaces where the value of the metric is no longer an element of the real line, but rather an element of a partially ordered space (see Collatz [C4]). A completely different form of fixed point theorem is Schauder’s theorem in which the operator T is no longer a contraction but rather is a continuous mapping of a compact, convex set into itself [K3]. For our purposes, the present theorem is adequate. I n fact, since our applications involve Banach spaces, we use a slightly weaker result in the sequel (Corollary 2.10).
DEFINITION 2.9. Let Y be a Banach space with 11 Ij as norm. Let Q be a closed subset of Y and l e t T map Y i n t o Y . The Lipschitz n o r m of T on Q, i n symbols: 0 T O n , i s given by
(note that 0 T On may be infinite). If T i s Frechet differentiable on Q, then t h e derivative norm of T o n Q, i n symbols: 0 T On’ is given by
0 T On’ = S U€DP II Ti,, I1 . Y
We now have the following.
2.
COROLLARY 2.10. Let Y be a Banach space and l e t S : S ( y o , ~ be ) t h e closed sphere i n Y with center yo and radius Y. Let T map Y i n t o Y and suppose t h a t (i) T i s defined o n S(yo,Y), and (ii) t h e r e are real numbers 7 and 01 with 7 3 0 1 such t h a t and 0 < llY1 -YyoII
w h e r e y1 T ( y o ) .Then t h e CM sequence { y n } for T based o n y o converges to t h e unique fixed p o i n t y* of T i n S and t h e r a t e :
Proof. In view of the proof of the theorem, it will be enough to 75 show that y n E for all n. Now, [I T(y,) - y o 11 = 11 y1 - y o /I [ 1 /( 1 %)IT Y so that y1 E S. Assuming that y o ,y1 , . . . ,y n are in S and noting that 11 T ( U )- T(u)ll 01 I/ u - u 11 for all u, u in by virtue of (2.1 l), we deduce that -
+ . . + I/ Y1 -Yo *
+ iI T(yn-J T(Yn-2) I1 + . . . + < (a" + d-' + . . . + 1 ) l l Y l -Yo11 -
s.
, E Thus, y n E S for all n by induction and the corollary is established. Corollary 2.10 suffers from the drawback of requiring a direct
2.2.
estimate of 0 T . Kantorovich [K2], using the idea of a “majorant,” derived a more “practical” convergence theorem for the case where T has a continuous Frechet derivative. We give the definition of a majorant and state and prove this theorem. Following that, we discuss its <‘practical” consequences. D E F I N I T I O N 2.12 (Kantorovich [K3]). A real-valued function +(t) defined o n t h e interval [ t o ,t’] (t’ = to + Y) i s a majorant for an o p e r a t o r T defined o n t h e closed sphere S = S ( y o ,Y) of t h e Banach space Y if
< Y.
We then have the following.
THEOREM 2.13 (Kantorovich [K3, Theorems XVIII 1.1 and XVIII 1.21). Let Y be a Banach space and suppose t h a t (i) T maps S = S ( y , , Y) i n t o Y and is continuously (Frechet) differentiable o n S, and (ii) +(t) i s a differentiable majorant for 7’ o n S which has a unique fixed p o i n t t* in [ t o , t’] and w h i c h satisfies t h e inequality $(t’)
+ Y.
Then t h e CM sequence {y,} for T based o n y o converges t o t h e unique fixed p o i n t y* of T i n S and t h e rate o f convergence of t h e sequence {y,} is given by IIy* -ynIl
w h e r e t, is t h e nth element of t h e CM sequence {tlL}f o r on to.
T h e proof of this theorem requires the following basic lemma on majorants.
LEMMA 2.14 (Kantorovich [K3]). L e t Y be a Banach space, and l e t T and +(t)be t h e o p e r a t o r and majorant, respectively, given
2.
i n Theorem 2.13. Let t h e segments [r;9 4-d y ] and [t,t At] belong t o S and [to, t'], respectively. If Ily - y o 11 t - to and /I d y I/ A t , t h e n /I T ( y i4)- T(y)ll $(f A t ) - $(t).
Proof. Using the Riemann integral for Banach space valued functions, we have
here 1 h I = max j(sI, - s,)I and uIbE , s / & + ~ ) . Since T;g) is continuous on the segment [ 7 , Ay] ~ C S , the integral exists. We next consider the norm
In view of the mean value theorem for differentiable operators ([K3], of Dieudonnk [DI]), we have
Ilcnce, since T:!])is continuous on [ y , y 4-d y ] C s ( y o, Y), we find that (2.15)
T(Y).
2.2.
Using this together with (2.15) and the properties of the integral, we obtain the inequality
$(t).
Thus, the proof of the lemma is complete. We are now prepared to prove Theorem 2.13. Proof of Theorem 2.13. We give the proof of the theorem in four steps. First, we show that the CM sequence {t,} for based on to exists and converges to the unique fixed point t* of 4. Next, we use Lemma 2.14 to show that the CM sequence for T based on y o exists and that the norms IIy, - y o 11 are bounded from above by the difference t* - t o . This, in turn, implies that the sequence {y,} converges to a fixed point y* of T. I n the third step, we show that this fixed point y* is unique. I n the final step, we prove the desired rate of convergence inequality. T o prove the existence and convergence of the CM sequence {tn},we first note that +’(t) 3 0 for t in [to, t’]. This implies that +(t) is monotonically nondecreasing on [ t o ,t’]. We use this to show that the CM sequence {t,} for based on to is contained in [ t o , t’] and is also monotonically nondecreasing. I n particular, we prove by induction that
0,1,2,. . .
where the last inequality follows immediately from the assumption that t* E [ t o ,t’]. I n view of (i) of Definition 2.12, we have t, - to = +(to) - to 3 11 T ( y o )- y o 11 0 and by the monotonicity of + ( t ) , t , = + ( t o ) +(t*) = t* t’. Hence, for k = 0, to t, t* t’. Assuming that (2.16) has been proved for all k < n, the monotonicity of + ( t ) implies that to t,, = +(tvLpl) +(t,) = t,+, + ( t * ) = t* t’. By induction, it follows then that {tvL}is indeed a monotonically nondecreasing sequence of real numbers which is bounded from above and hence that {tlL}converges to its least upper bound. I n view of the fact that +(t) is continuous, the
2.
limit to which {tn}converges must be a solution of t = +(t).Since t* is the unique fixed point of in [to , t’],we have limn+mt, = t*. In precisely the same way, we can show that, for the CM sequence {Z18} for based on Z,, = t’, we have
k = O , 1 , 2 ,....
This is so because Z, = +(t’) t’, and, by the monotonicity of +(t), t* -- +(t*) +(t’) = tl . Hence, for k = 0, t* Zl t’. Assuming that (2.17) has been proved for all k < n, it follows from the monotonicity of +(t), that
< t’.
Induction then yields, as before, that the CM sequence { f n } for q4 based on t’ exists as a monotonically nonincreasing sequence whicl, is bounded from below. Hence, since +(t) is continuous, we have lim,,.+T,t,, t*. We shall make use of the sequence {Z,} for the proof of the uniqueness of the fixed p o i n t y * of T in the third step. For the proof of the existence and the convergence of the C M sequence we compare the partial sums -
tkPl).
s.
Since t,, t’ by (2.16), (2.19) implies that yk E Thus, {y,} is defi n ed . Fork l,wehaveIly,-y(,Il =I1 T(y,)-ynII <+(t,)-t,= t , - t , . ‘Therefore, both (2.18) and (2.19) hold for k = 1. Assuming that (2.18) and (2.19) have been proved for all k n, we have -
.
2.2.
By induction, (2.18) and (2.19) hold for any k 3 1. It follows that, for an arbitrary positive integer p , (2.20) I/ yn+z,- Yn II
+ . . . + /lYn+1-Yn II
+ . . + tn+1 *
and hence that {yn>is a Cauchy sequence (as {tn>is). Since y n is an element of S for each n, the sequence converges to an element y * of S. T h e continuity of T on implies that y * is a fixed point of T. We prove the uniqueness of the fixed point y* by showing that every CM sequence {Yn>for T based on an element Yo of S converges to the fixed pointy". T o do so, we prove (by induction) that
where the f, are the elements of the CM sequence for based on t'. For k = 0, we have, I/ yo ~ y ,/I , Y = t' - to since yo E S. Assuming that both (2.21) and (2.22) are satisfied for all k n, we deduce from (2.21) and (2.17) that yn E S. I n addition, we have
2.
By induction, both (2.21) and (2.22) hold for all k >, 0. Since both ( t l l ) and {t,,}converge to the same limit, we have limTl,(* I tvt- t,, 1 = 0. Therefore, any CM lini,z-,7( 1 j,, yrr/ / sccpence [jl,} for T based on in S converges t o y * . T h e uniqueness of y* follows by considering the CM sequence {y} where 9 is any fixed point of T in S. ‘I’he desired rate of Convergence inequality follows from (2.20). ’l’hus, the theorem is established. Theorem 2.13 is not yet in a useful form for our purposes. Before the theorern can be applied, a majorant +(t) has to be determined. One approach to deriving practical convergence conditions from ‘l’heorem 2.13 is to assume a certain functional form for +(t) and to invcstigate what conditions have to be satisfied in order that +(t) be a majorant for the (given) operator T. Such conditions constitute the first part of the practical convergence conditions; the second part folloms from the conditions relating 4 and 7’ given in the theorem. In principle, many choices for the functional form of +(t)are possible; honever, only a few of these result in simple and practical convergence conditions. We discuss two such simple choices. As our first selection we let +(t) be a linear function of t , i.e., ~
+ at.
I n order that this + ( t ) be a majorant for a differentiable operator T , both inequalities of Definition 2.12 must be satisfied. This leads to the conditions
2.2.
Theorem (2.13) requires that #J(t)be differentiable, have a unique fixed point in [to,t ’ ] , and satisfy the inequality #J(t’) t’ = to Y = Y (as to = 0 here). Clearly, the differentiability of +(t)is assured, and # J ( t= ) t will have a unique solution if a < 1. T h e inequality #J(t’) t’ will be satisfied in Y = t’ 3 [l/( l - .)].I. If these conditions are satisfied, then Theorem 2.13 guarantees the convergence of the C M sequence {y,} for T based on y o to the fixed point y*. T h e nth term of the C M sequence for based on to is, in the present case, 1 - an t,, = 1 - a 7,
Yo I / .
I n summary, we have found that if there are numbers a, 71 with and 0 01 < 1 such that (2.24) and (2.25) are satisfied and (1 - 01)y 3 7, then the C M sequence for T based on y o converges to the unique fixed point y* of T in = s ( y , ,, r ) . Evidently, this is precisely Corollary 2.10 for the case where T has a continuous Frechet derivative. Thus, our first choice for # J ( t )(2.23) yields no new convergence conditions although it does show that Corollary 2.10 for a differentiable T is a consequence of Theorem 2.13. A second choice for #J(t)is the quadratic function
-t2.
t In view of the equality sign in (2.24), inequality (2.26) holds for 7 = j j y1 - yo II . I t follows that an increase in 7, and hence, an increase in r , cannot result in a decrease of OL. Since the fraction in (2.26) is a monotone increasing function of OL, we may, therefore, replace 7 by I/ y1 - y o /I without having to make the same change everywhere in the derivation.
2.
This function is a majorant for T if the conditions of Definition 2.12 are satisfied. This leads to the requirements
for all y with /I y - y o 11 t . If Tiv) is differentiable, or equivalently if T is twice differentiable, the last condition can be simplified by invoking the mean value theorem for differentiable operators. This yields
From this we deduce that (2.30) may be replaced by the inequalities I/ 6 and supytS 11 T:u) Ij K. [These inequalities imply
'Theorem 2. I3 requires that + ( t ) be differentiable, have a unique fixed point t* in [O, t ' ] , and satisfy the inequality+(t') t' = t,+r = r (as t,, 0). T h e differentiability of + ( t ) is clear. Since the roots of the quadratic equation t = $ ( t ) = 7 4-6t (K/2)t2are given by
Satisfaction of the inequality + ( t ' ) t' is assured by (2.32). If (2.29)-(2.32) hold, then Theorem 2.13 guarantees the con-
2.2.
vergence of the CM sequence {y,} (for T based on yo) to the fixed point y*. In addition, the convergence rate satisfies the desired inequality, /I y* - y n Ij t* - t, . We translate these inequalities in terms of 7 , K , and h. For our choice of a quadratic q5(t), the evaluation of the sequence {tn}is rather complicated. Instead of evaluating the difference (t* - t,) exactly, we give an estimate
- tnpl).
Evidently, (2.33) holds for all n b 1. Since t* -
2h].
T h e choice of a quadratic function for +(t)thus leads to interesting convergence conditions; we summarize these in the following “practical” corollary of Theorem 2.13.
2.
COROLLARY 2.34. Suppose t h a t T i s t w i c e differentiable o n S ( y o , ~and ) t h a t t h e r e are real numbers v, 8, and K with '0, 0 6 1, and K 3 0 such t h a t
w h e r e Iz Kq/(l - S ) 2 & . Then t h e CM sequence {y,} for T based o n yo converges t o t h e unique fixed p o i n t y * of T i n S and t h e rate of convergence i s given by ~~
Corollary 2.34 and Corollary 2. I0 display several similarities. A direct comparison to determine which of these corollaries is preferable in practice is impossible because of the sensitivity of thc convergence conditions to the operator T . Intuitively, we may view Corollary 2.10 as a linear contraction mapping theorem and Chwllary 2.34 a s a contraction mapping theorem for quadratic functions. It is to be expected that the conditions of either corollary k v i l l bc bcst if the functional rclationship between the norm of the opcrator 'I' and the norms, 11 yTl- yo 11, is of the same form as the corresponding majorant function. If the norm of the Frechet derivative of 7' is approsimately constant ovcr S , then most likely Corollary 2.10 will yield the best convergence conditions. On the other hand, if thc norm of T('!,) is almost zero for y - y o and increases with - J ' ~11,, then most likely Corollary 2.34 will yield the best convergence conditions. I t may he remarked that ~ v ewill encounter operators of the latter type later on in this chapter when we discuss convergence conditions for both the modified and pure Newton's method. 1:or those cases, Corollary 2.34 yiclds the best convergence conditions .
2.3.
2.3. The Modified Contraction Mapping Method Direct application of the contraction mapping method often does not lead to a convergent sequence of approximations. Frequently, it is possible to modify T in such a way as to lead to a convergent sequence of approximations. With this objective in mind, we have the following.
LEMMA 3.1. Let T and V be maps of Y i n t o Y . Suppose t h a t V i s invertible and l e t P be t h e map of Y i n t o itself given by
VI-l W Y ) - V ( Y ) l .
Then y * is a fixed p o i n t of T if and only if y * i s a fixed p o i n t o f P.
If y* = T(y*), then y* - V(y*) = T(y*) - V(y*) and y* = [I - V]pl[T(y*) - V(y*)] = P(y*). Conversely, if y* = P ( y * ) ,then [Z - V](y*) = T(y*) - V ( y * )so thaty* = T ( y * ) . This simple lemma leads us to consider the application of the contraction mapping method to the modified equation so
Proof.
where V is an operator with the property that [I - V] is invertible. In other words, we consider the selection of an initial approximate solution yo and the generation of a sequence {y,} by one of the following three algorithms
[where V is assumed linear in (3.4)]. We call any one of these algorithms a modified contraction mapping method and we call the sequence { yn} generated by such an algorithm, a modijied contraction mapping (or MCM) sequence for T based on y o and V . We observe that the MCM sequence for T based on yo and V coincides with the CNI sequence for P based on y o . Thus, we can translate results of the previous section into the present context. I n particular, we have the following.
2. OPERATOR
PROPOSITION 3.5. Suppose t h a t P i s differentiable o n : S ( y , , Y) and t h a t t h e r e are real numbers 7, 01 with 7 3 0 and 1 such t h a t 0 Y
Then t h e MCM sequence {y,> for T based o n yo and V converges T i n S and t h e rate of convergence i s given by
llYl - Y o I / .
C O R O L L A R Y 3.8. If V is a linear o p e r a t o r w i t h I - V i n v e r t ible, if 7' i s differentiable o n S , and if
t h e n t h e MCM sequence {yTL} converges to t h e unique fixed p o i n t y * of T i n S and t h e rate of convergence i s given by (3.7).
PROPOSITION 3.10. Suppose t h a t P i s t w i c e differentiable o n = S(y,, Y) and t h a t t h e r e are real numbers 7, 6, and K with 0, 0 S <- 1, and K 3 0 such t h a t
$ . Then t h e MCM sequence {y,} w h e r e Iz = ( K 7 / ( l for T based o n yo and V converges t o t h e unique fixed p o i n t y * of 7' i n S and t h e rate of convergence i s given by ~
2.3.
COROLLARY 3.14. If V i s a linear operator w i t h I invertible, if T i s twice differentiable o n S , if
and if (3.12) is satisfied, then t h e MCM sequence {y,} converges to t h e unique fixed p o i n t y * of T i n S and t h e r a t e of convergence i s given by (3.1 3). T h e significance of these propositions and corollaries lies in the fact that they extend the range of applicability of the contraction mapping method to fixed point problems for operators T that are not contraction mappings. The essence of the modified contraction mapping method is the application of the method of contraction mappings to an equivalent fixed point problem. I n particular, it is possible to treat fixed point problems with operators T for which
Piv, be suitably small on S. Alternatively, if
for some linear operator V with I - V invertible, then we can anticipate convergence. Corollaries (3.8) and (3.14) do not specify the linear operator V any further than requiring the norm SUP YES
to be small. More information on the selection of V can be garnered from a consideration of the difference between two successive approximations.
2.
‘I’hc convergcnce of the MCM sequence {y,} will be most rapid if the lincar operator V is chosen in such a way that the expressions
are as small as possible. Evidently, a number of choice for V are possible. We discuss some of the more common selections. From the expression (3.16) we can see that if we were allowed to select a different linear operator at each step of the iteration, then the choice
\vould yield one of the best possible convergence rates. T h e iteration method based on this choice is known as Newton’s method. This method is not a modified contraction mapping method because of the change in the linearization. We shall discuss Newton’s method in the next section. If we restrict ourselves to a fixed linear operator V and take into account the fact that the elements y , are unknown beforehand, then an obvious choice for V is V = T;,o,. T h e iteration method based on this selection of V is called the modijied Newton’s method. T h e modified Newton’s method is the best known version of the modified contraction mapping method. Both corollaries apply to this method. In fact, a nice simplification arises in Corollary 3.14 in that we may take 6 = 0. We will not treat the modified Newton’s method as a special method, but rather consider it a particular case of the modified contraction mapping method. For one particular class of fixed point problems, a simple choice of V may lead to very simple computational procedures which may offset a possible loss in convergence rate. This particular class is the
2.3.
class of almost linear fixedpoint problems. These are given by equations of the form Y
where Wis linear, E is a possibly nonlinear operator, and E is a "small" number. T h e simple choice V = W may be advantageous in such a problem. This choice for V makes the convergence conditions depend on E . For example, the main convergence condition of the contraction mapping theorem becomes
We discuss the application of these ideas to the iterative solution of almost linear two-point boundary value problems in Chapters 4 and 5. As a final and trivial choice for V , we have V = 0. It is clear that this choice results in the original method of contraction mappings discussed in the previous section. T h e original method of contraction mappings can thus be considered a special case of the modified contraction mapping method. We can also consider the modified contraction mapping method from another point of view. Suppose that we attempt to solve the equation y = T(y ) by improving successive iterates by corrections which are linear functions of the error. An algorithm for such a procedure is Yn+1 = Y n
where A is a nonsingular linear operator. An iterative procedure converges rapidly if the ratio of the norms of the differences between the successive iterates is small. We have
in the present case. It follows that the convergence will be improved if the expression supYEs11 I - AII - T6,]11 becomes smaller. I n this light, we see that a good choice for the nonsingular operator A is given by A = [I - V]-l where V is a linear operator for which SUPya.9 I/ I - [I - V]-"I - T;Y,lll = SUP,,S 11[I- VI-l[T;,, - Vlll is small. Since this leads to an algorithm of the modified contraction mapping method, we have made our point.
26 2.4.
2. OPERATOR
V , say V,), at each iteration, then we would obtain a more rapidly convergent algorithm. T h e particular choice, V, = T;,,, , leads to
which is called Newton’s method. We mill first consider Newton’s method as a special case of the method of contraction mappings and apply the contraction mapping theorem to it. Next, we show that the convergence conditions can be relaxed if the special relationship between successive elements of the iteration is taken into account. This leads to the theorem of hlysovskikh, which guarantees the convergence of the sequence of approximate solutions but not the uniqueness of the limiting solution. Finally, we prove the classic theorem of Kantorovich on the convergence of Newton’s method for operator equations. T h e proof shou s that by taking into account the special relationship between the successive elements of the sequence and by slightly narrowing the conditions of Mysovskikh’s theorem, it is possible to let the convergence conditions for Newton’s method depend almost exclusively on the initial approximate solution and to prove, in addition, the uniqueness of the limiting solution. We now have the following.
DEFINITION 4.2. Let T map Y i n t o itself and l e t y o be an element of Y . Let V , be a sequence of elements of 2(Y,Y ) . The sequence {y,] generated by any one of t h e following algorithms
for n == 0, 1,. . . , is called t h e Newton’s m e t h o d or NM sequence for 7‘ based o n y o and { V J . If V , = Ti,?,,, t h e n { y n } i s called t h e Newton’s m e t h o d or N M sequence for T based o n y o .
2.4. We observe that if V, the sense that
(provided that the indicated derivatives and inverses exist). This observation allows us to view the application of Newton's method to the solution of y = T ( y )as equivalent to the application of the contraction mapping method to the solution of the equation y = Q ( y ) . More precisely, we have the following. PROPOSITION 4.8 [K2]. Suppose that (i) T i s t w i c e con= y ) , (ii) [I - T ; J 1 exists and tinuously differentiable o n is linear f o r y i n S, (iii) [I - T;J1 and T:J)are (uniformly) bounded (i.% sup,,s{I/[I Il} co and supl,Es{/IT;),)Ill on M < a),and (iv) there are real numbers q and N with q 3 0 and 0 N < 1 such that
Then t h e NM sequence {y,} f o r T based o n yo converges t o t h e unique fixed point y* of T i n S and t h e rate of convergence i s given by
Proof. We first observe that, in view of Corollary 2.10 and the lemma following the proposition, {y,} converges to the unique fixed and the rate of convergence is given by (4.1 1). point y* of Q in it is clear that any However, since [I - T ; J 1 exists for all y in fixed point of T in is a fixed point of Q and conversely. Thus, the
t Note that Tiy,E -Y(Y , Y (Y , Y ) ) .
2.
proposition will be established once we have verified the following lemma. LEMMA 4.12. Let Q be t h e map of Y i n t o itself given by (4.7) w h e r e T satisfies t h e conditions of t h e proposition. Then t h e Frechet derivative, Q;,, , of Q i s given by (4.13)
f o r y i n S. Proof.
2.4.
u1-1 [ I - qY)]-l.
Letting D and M be positive real numbers as in (iii) of the proposition so that sup,,s{II[I - T,'&' II} D and sup,,s{lI T(y,Ill M , we have, in view of the mean value theorem for differentiable operators,
+ d y ] . Choosing dy so that
It then follows that [I - U]-l exists and can be written in the form [ I - U]-1 = I U U* * . . . Substitution of (4.16) into (4.15) yields
+ u + u2+ . . .][I
2.
2.4.
Denoting the bound on the norm (4.15) given by (4.20) by A ( d y ) we see that (4.21)
which proves the lemma. It is of interest to note that the convergence conditions of Proposition 4.8 have a special property that is not shared by the other results discussed in this section, namely, the conditions of Proposition 4.8 guarantee not only the convergence of the NIL2 sequence based on yo but also the convergence of the N M sequence based on yofor any [I /( 1 - C L ) ] ~More . precisely, element y,, of S for which 11 yo - y o I/ we have the following.
COROLLARY 4.22. Suppose t h a t t h e conditions of Proposit i o n 4.8 are satisfied and t h a t yo i s an element of S = S ( y , , T ) for which 11 yo - y o I/ yo = qi(l - a). Then t h e NM sequence for T based o n yo converges t o y * , t h e unique fixed p o i n t of T i n 3.
Proof. T h e conditions of Proposition4.8 guarantee that Q is a contraction on 3. We shall show that Q maps So = S ( y O y,o ) into Soand that limn+r: lip, - y * 11 = 0. T o begin with, if y+ E So,then II y+ - yo II ro = 11/(1 - 4 and
Po is in , it follows from (4.23) that for all n by an induction argument. as y1 = Q ( y o ) .Since
2.
for all lz >- 1. T o see this, we simply note that I/ p,+l - y* /I = I/ Q ( j i , ) - Q(y*)/j< a 11 j l l - y* 11 and then use induction. Since 01 < 1, it follows that limn+m11 j j l t - y * 11 0 and so, the corollary ~~
is proved. We now present two additional theorems on the convergence of Newton's method in the case where V, = T;Y,) and defer our considcration of the general case until later on. T h e proofs of these two theorems are based on an important relationship involving the norms of the differences between successive iterates. We derive this relationship in the following. LEMMA 4.25. Suppose t h a t T is t w i c e continuously differentiable and t h a t {yl&} i s an NM sequence for T based o n y o . Then (4.26) I/ Y n + 1
Proof.
1,2,.. . . First observe that
by virtue of the properties of twice differentiable maps (see Iiantorovich and Akilov [K3]). Newton's method is often said to exhibit "quadratic convergence" in reference to the inequality (4.26). In other words, the norm of the difference between successive iterates is smaller than a number which is proportional to the square of the preceding difference.
2.4.
Our first theorem based on Lemma4.25 is that of Mysovskikh. This theorem involves convergence conditions which are considerably weaker than those of Proposition 4.8. However, the theorem does not guarantee uniqueness of the fixed point. We have the following. THEOREM 4.27 (Mysovskikh [K3]). Suppose t h a t (i) T i s t w i c e differentiable o n S = S ( y , , r ) , (ii) [I - TiJ-l exists and i s linear for all y i n S, (iii) t h e r e i s an M > 0 such t h a t
- Y’ ) I +M. I/ y - y’ 112 for y , y’ i n S,+ and (iv) t h e r e are real numbers q , K , and h with q 3 0, K 3 0, and h = Kq < 2 such t h a t
(4.30) Then t h e N M sequence {y,} for T based o n yo converges t o a fixed p o i n t y* of T i n S and t h e rate of convergence is given b y
0, 1,. . . .
Proof. We give the proof in three steps. We first prove that y, E S for all a. Next we show that {y,) is a Cauchy sequence and hence converges. Finally, we use the inequalities derived during the course of the proof to establish (4.31). Let q n and h, be given by (4.32)
(4.33) t Note that (iii) is satisfied if take M = S U P ~ ~{I1S TI,Ill.
T&,is uniformly bounded on s. In that
2.
0, 1, . . . . We now show by induction that
for k = 0, 1, . . . . For k = 0, (4.34) is a direct consequence of the hypotheses. Now, assuming that (4.34) holds for k n - 1, we have
for h = n. Moreover, it follows from the definitions (4.32) and (4.33) of q n and h, that (4.35)
for all n. Using (4.35), we find that
and so the induction argument is complete. Thus, y n E S for all n. Letting rn be a positive integer, we have
Since h = ho < 2, we deduce that limn+m11 yn+m- yn 11 = 0. T h e sequence { Y , ~ is } thus a Cauchy sequence in the closed sphere S of
2.4.
the Banach space Y and hence converges to an element y* of S. We claim that y* is a fixed point of T. T o see this, we observe that
by virtue of (iii). Since T is continuous and { y n } converges to y*, we deduce that
and so our claim is valid. T h e rate of convergence inequality (4.31) follows from (4.37) by letting m approach infinity and noting that the development remains valid for rlo = I/ y1 - y o 11. Thus, the theorem is established. T h e next theorem to be presented here is the well-known theorem of Kantorovich on the convergence of Newton’s method. This theorem does not require the verification of the existence of the Instead, the inverse need only inverse of [ I - Tiu)]for all y in exist for the initial approximate solution. This constitutes a practical improvement which is made possible by placing additional restrictions on the remaining conditions. T h e second main difference lies in the fact that the theorem of Kantorovich guarantees the uniqueness of the limiting solution. T o prove this uniqueness, Corollary 2.34 on the convergence of the modified Newton’s method (i.e., the modified contraction mapping method for 6 = 0) is used. This is possible because the convergence conditions for the NM sequence are identical to those of the MCM sequence. Except for these differences, both theorems are closely related and both proofs are based on an examination of a particular sequence rather than on contraction properties of the operator.
s.
THEOREM 4.38 (Kantorovich [ K 3 ] ) . Suppose that (i) T is twice continuously differentiable on S = S ( y o ,r ) , (ii) [I - Tiu0)]-l exists and is linear, and (iii) t h e r e are real numbers 7, K , and h with 3 0, K 3 0, and h = Kq such that
2.
and (4.41) Then, t h e NM sequence {y,} for T based on yo converges t o t h e unique fixed pointy* of T in S, t h e rate o f convergence is given by
Proof (Antosiewicz [All). We give the proof in several stages as in Theorem 4.27. We first prove that [I - T : J 1 exists and that y n E S for every n. Next we show that {y,} is a Cauchy sequence and so converges to an element y* of S. We then establish that y* = T (y * ) and that the fixed point is unique. Finally, we prove (4.42) and (4.43). Let y n , K, , h, , and r, be given by 170 = 79
for n = 0, 1, . . . . Since h, ,< i , we have h, Moreover, in view of (4.44) we also have
0, 1 , 2 , . . . .
2.4.
for k = 0, 1 , 2, . . . . For k = 0, (4.46)-(4.49) are direct consequences of the hypotheses. Now assume that (4.46)-(4.49) hold for all k n - 1. Then, for k = n, we have
< o%;~l(IIII T(yn-l)lT&n-l+o(t+,-,n-l)) It) /I Y n < Kn-lTn-l = hnpl G 8 . -
Hence, by the well-known theorem of Banach on the inverse of the sum of the identity and a small operator, the inverse of the operator I - [I - T;Yn-l,]-l[T;Yn)- TiYn-l)]exists, is linear, and is, in view of (4.52), bounded by 1 (4.53) II { I - [ I - TiYn-l)l-l m y n ) - T L ) l l - l l l G 1 - hnpl
2.
I t follows from (4.51) and the induction hypothesis that [I - Tivn)]-l exists and is given by
for n 1 3 p > q 3 0. This proves (4.46)-(4.49) for k = a. By induction, these relations hold for all k. I n view of (4.50) we have also shown that all the yn are contained in S.
2.4. Since hnPl qualities
0, 1, . . . . Repeated use of these inequalities yields
for any m. Letting n increase indefinitely, we find that liillYn+m -YnII = O
and hence that {y,} is a Cauchy sequence. Thus, {y,} converges to We claim that y* is a fixed point of T . T o see an element y* of this, we observe that
s.
2. OPERATOR
where M 3 K/lj[l- 7';u0,]-11/. Since T is continuous and { y J converges to y*, we deduce that
and so, our claim is valid. Now comparison of the hypotheses of the theorem and those of Corollary 2.34 shows that these conditions are identical for the case 6 = 0. Thus, we can generate an MCM sequence for T based on yo and T:go,which will converge to the unique fixed point of T in S. As y* is a fixed point of T in S, it must ( u fortiori) be unique. Letting m approach infinity in (4.58), we find that
(4.42) is satisfied. As for (4.43), we note that
2.4.
by letting n approach infinity. Since we may replace qo by 11 y1 - y o 11 in (4.61), (4.43) is established and the proof of the theorem is complete. We note, at this point, that the convergence factor h in Theorem 4.27 was allowed to have a value as great as 2 while the convergence factor h in Theorem 4.38 could only have a value as great as & . Thus, the “price” paid for the convenience of having convergence conditions determined almost exclusively by the initial approximation and for being certain of uniqueness, may amount to a worsening of the convergence conditions by a factor of 4. However, we shall see, in the sequel, that the practical advantages of Theorem 4.38 are usually sufficient to insure that it is preferable to Theorem 4.27. We now turn our attention to a consideration of Newton’s method for T based on y o and { V,}. We prove two theorems. T h e first theorem essentially involves a modification of the contraction mapping method while the second theorem may be viewed as a generalization of the modified Newton’s method. We have the following. THEOREM 4.62. Suppose that (i) T is continuous on S = s ( y , , , r ) , (ii) {Vn} is a sequence of elements o f 9(Y,Y ) such that I - V , is invertible and I/ Vnll < M for every n, (iii) Qn = [I - V,]-l [T - V,] maps S into itself, and (iv) there are sequences {a,} and {pa} w i t h an >, 0 and 3/, 3 0 such that
2,3,.
. . and 6,
pl.
2.
o n y o and {VrL}converges t o a fixed p o i n t y* of T i n rate o f convergence i s given by
Proof.
for p = 1, 2, . . . . It follows, in view of (4.65) and (4.66), that { y m } is a Cauchy sequence in S and so converges to an element y* of S. Since Y , + ~- T ( y , ) = V,(y,+, - y,) and T is continuous, we have ln+m i m I I y n + 1 - T(yn)Ii = I I Y *
which shows that y* is a fixed point of T . T h e rate of convergence inequality (4.68) follows from (4.70) by letting p approach infinity. Thus, the theorem is established. THEOREM 4.71 (cf. Antosiewicz [All). Suppose t h a t (i) T is continuously differentiable o n S = S ( y , , r ) , (ii) {V,} i s a sequence of elements of 2(Y,Y ) such t h a t I - V , i s invertible for every n, (iii) ( I - T;,>-l exists and i s bounded, and (iv) t h e r e are real num-
2.4.
for all n. Then the NM sequence for T based on y o and (Vn} converges t o the unique fixed point y* of T in S and the rate of convergence is given by
(4.75) for n = 1 , 2 , . . . . Proof.
+ 6).
2.
so that y1 E S. Let us suppose that y l ,
. . . ,y n are in S. T h e n
vnl-l [I - T;olll . l l [ l IIYn -Yn-1
by virtue of (4.73) and (4.74). It follows that (4.80)
so that yn+l E S. By induction, we have y n in S for every n. Now, we deduce from (4.80) that (4.82)
for p = 1, 2, . . . . Since ( a p)/( 1 - a ) < 1, it follows that { yn} is a Cauchy sequence in S and therefore converges to an element y* of S. Moreover, letting p approach infinity, we see that (4.75) is valid.
2.5.
T o show that T ( y * ) = y*, we need only let n approach infinity in (4.79) as T is continuous. Finally, for the uniqueness, we simply note that if T ( 9 ) = 9, then
8<1.
Thus, the theorem is established. A particularly useful choice of a, 8, and 7 is given by 7 a = S/3, and 8 = S / 3 where 0 < 6 < 1 [A2].
2.5.
and ybo( y ) = y . We prove several convergence theorems for the entire class. T h e first theorem involves the order of convergence of the algorithms. I n the second theorem, we give conditions under which the iterations (5.1) converge to a unique zero of F. T h e final theorem consists of practical convergence conditions analogous to Kantorovich’s theorem on Newton’s method [K3] and represents a natural generalization of Theorem 4.38. We note that fixed point problems are also covered in our development. More precisely, if T maps Y into itself and if we let F = I - T , then the equations
t This section was written with the cooperation of W. E. Bosarge, Jr. and is based on Bosarge and Falb [B7].
2.
are equivalent. T h e formulations (5.3) and (5.4) are used interchangeably in the sequel. For example, in the case of (5.4), we have
is easily proved by induction. If the mapping
3 1. We now have the following.
DEFINITION 5.9. Let y o be an element of Y . The sequence {y,} generated by t h e algorithm (5.1) is called a multipoint or M sequence for F based o n y o . DEFINITION 5.10. Let $(.) map Y i n t o i t s e l f and suppose that t h e algorithm ylL+l= +(y,) converges t o a fixed point y* of T. Then t h e convergence i s of o r d e r p >, 1 if (5.1 I ) where C is a constant.
A basic result on order of convergence is the following. THEOREM 5.12. Suppose that (i) T i s twice continuously differentiable on = ). where y* is a fixed point o f T ; (ii) [I - T2/']-1exists and is uniformly bounded o n S with
2.5.
Tj. Ill
BK<3.
Then, for an initial guess yo in S , the M sequence {$,(yn)} lies 1. Moreover, in S and converges t o y* with order at least 01 the rate of convergence is given by
> 2.
Proof. a =
1 . Since y o E S,
a.
Since Y < 1, #l(yo)E S. Now assume that yn an identical argument, we deduce that
#l(yn-l) E 3. By
2.
0. Repeated and hence, that yn+l E S. Thus, $l(yn) E S for all n r2nf1 application of (5.20) shows that Ijy* -yn+l 11 cyfl IJy*-yo112nf 1 and so, limn-,;o11 y * - yn (1 = 0. Thus, the theorem is true for 01 = 1 . Suppose that the theorem holds for all m 01. We shall show that 1. Since yoE S and &(yo)E S, it then holds for 01
Yo Ila+2.
Since c,+~ 1,' y1 =- $a+l(yo) E S. Suppose that y o , . . . ,yn are in S. Then $,(yn) E S by the induction hypothesis and we have II &+l(yn)- y * /I c,+1 II y* - Yn lla+2 [by an argument exactly the same as that used to derive (5.21) and (5.22)]. It follows that yntl = t,!~,+~(y~J E S for all n. Repeated application of the inequality I/ $,+l(yn)- y* 11 c, 11 y * - yn lla+2 allows us to conclude that the M sequence {$a,-l( yn)} converges to y * with rate of convergence given by (5.16). T h e theorem is now established. We now turn our attention to convergence theorems for the multipoint algorithms beginning with some simple lemmas.
LEMMA 5.23. Suppose t h a t T i s differentiable and t h a t exists for all y i n a subset S of Y . Then y* E S is a fixed p o i n t of T if and only ify" i s a fixed p o i n t of t,ha for all 01 3 1.
Proof. If y * = T(y*), then and so y * = [(I - Ti*)-I(T that $o(y*) = y * for P 01, Q(y*, y * ) = $ ~ ~ ( y= * )y*, and induction.
- Th.,(y*)= T ( y * ) - Th,(y*), T;,)](y*)= t,hl(y*). If we assume then $a+l(~*) = NY*,&(Y*)) = so Pa(y*) = y* for all 01 3 1 by
< (1 + j)BKc,-, < 1.
2.5.
Conversely, if &(y*) = y * , then (I- Ti,)y* T(y*) - T&(y*) a n d y * is a fixed point of T .
LEMMA 5.24. Suppose that (i) T i s twice continuously differentiable o n S = S ( y 6 , Y); (ii) [I - TY']-lexists and i s uniformly bounded o n S w i t h
(5.26) Then t h e mapping Q(x,y) of (5.6) has partial derivatives Q2(x,y)(.) w i t h respect t o x and y , respectively, and (5.27)
f o r all x , y i n S. Proof. Let x, y be elements of S and let h, k be increments in x and y, respectively, with x h and y k in S. Then
( T - TO')y.
2. OPERATOR
provided that (I- U)-l exists. Now (i), (ii), and (iii) together imply D M I/ h I/ and so ( I - U)-l will exist for all h with that /I U /I 11 h /I 6/DM where 6 < 1 . Moreover, we then have ( I - U)-l = . . . We also note that I U U2
TZ’)-’ jl < D . It follows that
(I+ u + u2+ . * .)[U{(Z- Tz’)-l ( T - T i ) - I>lY
. .)(I - Tz’)-l ( T - I ) y
and hence that the partial derivative of Q with respect to x exists and is given by (5.27). As for the partial derivative with respect to y , we have (5.33)
It follows that the partial derivative of Q with respect to y exists and is given by (5.28).
2.5.
COROLLARY 5.35. Suppose that conditions (i),(ii),and (iii) of t h e lemma are satisfied. If y is an element of S such that #,-l(.) i s differentiable at y and #,-l(y) i s i n S, then t,ba(.) i s differentiable at y and
Simply apply the lemma and the chain rule for Frechet derivatives. We now have the following. Proof.
THEOREM 5.37. Suppose that (i) T i s twice continuously differentiable o n S = S ( y , , r ) ; (ii) ( 2 - T2/')-lexists and is uniformly bounded o n S w i t h (5.38)
17.
where h, = a ( B 2 K M )< 1 f o r all o( 8. Then t h e M sequence {t,boL(yn)} based o n y o converges t o t h e unique fixed point y * of T i n S and t h e rate of convergence is given by (5.43)
< < 2. 01
2.
Proof. We first show that
Ol. Suppose that for all 01 S (as $o( y ) = I y ) and
1. Then $,(.) is differentiable on
by virtue of Corollary 5.35 and the hypotheses of the theorem. Since II $ d Y ) - Yo I/ /I $ d Y ) - $1(Yo)ll II $l(YO) - Yo II, it follows from the mean value theorem (DieudonnC [Dl]) that 11 $ l ( y ) - y o 11 h,r (1 - h,)r = r . Thus, C Now assume that y!~~(.) is differentiable on S , C S, and that (5.44) holds if p 01 < OZ. Then $ E , l ( . ) is differentiable on S and
$,(s) s.
Thus, (5.44) holds for all 01 Ol by induction and C S. I t now follows from Corollary 2.10 that {$m( y,)} converges to the unique fixed point yn* of $, in However, the proof of Lemma 5.23 shows that yl* = y * is a fixed point of T and, hence, y* = ye* for all 01. T h e rate of convergence inequality follows from Corollary 2.10 and the theorem is established. We now state and prove a basic convergence theorem for the multipoint algorithm (5.1). We write yn,, to indicate that we are considcring a particular element of the class of algorithms (5.1).
s.
2.5.
THEOREM 5.48. Suppose that (i) F is twice continuously differentiable o n s, = r,); (ii) (Fio,a)-l exists and ll(Fio.J1 11 Bo,,j (iii) ll(Fi0,)-'I1 II F(Y,,~)II do,, ; (iv) F i is uniformly bounded on S, w i t h
for CY = 1,2,. . . . Then t h e M sequence {$a(yn,a)) converges t o a zero ya* of F i n S, and t h e rate o f convergence i s given by (5.54)
fora = 1,2,.
...
< 3 (*).
Proof. We give the proof in three steps. We first show that all Next we the inverses (Fhn.J1 exist and that all the yn,a are in and hence has a limit prove that {yn,,) is a Cauchy sequence in y,* in S, . Finally we show that F(y,*) = 0 and that (5.54) holds. For each 01 3 1, we define B n , a ,d n , a , q n , , , and hn,a, recursively, by setting
4 . a =2
s,.
2.
2 1. We now prove by induction that
for n = 0, 1 , 2,.. . . For n = 0, (5.59)-(5.61) and (5.63) are hypotheses and (5.64) will follow from (5.52) and (5.62). Thus, we need only show that /I y1.. - Y o p II d To,, . We begin by showing that $i(yo,a) is an element of S, for 1<j a - 1. This is done by induction on 01. For a = 2, we have 11 YO,^) : II = ll(~~o,m)-l~(yo,a)ll do,a qo,, < ra so that $ l ( ~ o , ~E) S, . By expanding F ( $ d y 0 J ) about yo,,, we find that
l l ~ ~ # l ~ Y o . c J ~ lK,d,2>, l
2.5. for 1
< j < a - 1. I t follows that
11 yl,a - yo,a11
-
1. Since yl,.
-
YO,^ =
-zZ ( F ~ ~ ,F(+j(yo,a)), ~)F~
<.q0,. and so (5.62) holds for n = 0. We now examine the transition from n = 0 to n = 1. Since yl,a and
are in the convex set s a II Fh0,= - F;l,aII 6 K, II y1,. It follows that 11 Fho,a11 - 11 Fh1,.11 Kaqo,aand hence
Y0,a
<
9
11.
-
But (5.69) implies that (Fh1.a)-l exists and satisfies B0.a
ll(F;l,a)-l II G
(5.70)
- B1.a
= 1. T o verify (5.61) for n we expand F ( Y , , ~ about ) +a-l(yo,a)to obtain
so that (5.59) and (5.60) hold for n (5.71)
II F(Y1.a) - F ( ? L l ( Y O . J )
+
a-2
(5.74)
I/Y2.a
- Y1.a
=
1,
~ ~ a ~ l ~ ~ o . a ~ ~ ~ ~ o ~ a ~ - l ~ ~ ~ a - l ~ Y ~ . a ~ ~
<2 so that (5.61) holds for n n = 1, we show that
=
a
h0,aTo.a = d1,a
1. Now to verify that (5.62) holds for
/I = II ! u Y l . J
- Y1.a
(a) II G Y1.a d1.a
56
2.
where yi::
=
OPERATOR THEORETIC ITERATIVE METHODS
1 and y:$ is given by
for 2 < j < 01. We note that < y:!: < 2 for a l l j < CY (by a simple calculation). Assuming for the moment that (5.74) holds, we have
, Since dl,n = P-21~$,n~0,a (5.77)
/I Y2.a
-
so that (5.62) holds for n that
Y1.a 11 G =
+
2=h;.a7Osa
== 171,a
1. We now establish (5.74). We observe
and hence, that (5.74) will hold if (5.79)
<
i < a - 1 . Now (5.79) can be established in exactly the for 1 same way as (5.68) once we .have shown that 1 , 5 ~ ( y E ~ , ~ ) for 1 < j < a - 1. Rut this is done by induction on a. For 01 = 2, '
sa
2.5.
57
MULTIPOINT METHODS
Thus, #2(yl,a)E S, . T h e argument can be repeated to show that $i(yl,a) E S, for j 01 - 1 since 72; $ [see Eq. (5.76)]. I t follows that (5.62) holds for n = 1. As for (5.63), we have
<
(5.80)
<
KaB0.m
5
h1.a = KmB1.a7l,n = ___ 16 2 m h ~ s C i ~ o , U
1
- h0.a
< 8 2%h;t1< 8 hoe,< 3
Now,
II Y2.a - Y o , % /I < II Y 2 . m
-Y1.a
II
+ 1lYl.a
-Y0.a
II
and so (5.64) holds for n = 1. If we now assume that (5.59)-(5.64) hold for m < n - 1, then we can show by exactly the same arguments used in going from n = 0 to n = 1 that (5.59)-(5.64) are satisfied for n. Thus, by induction, the relations (5.59)-(5.64) hold for all n 2 0. Now, it follows from (5.57) and (5.63) that qn,, < (+6)nqo,a and qn,a is convergent. Since hence that the series
xn=o W
(5.81)
IlYn+m,a
- Y n , a II
< c 7n+i,a m-1 j=O
we conclude that {ynl,} is a Cauchy sequence in S, and so converges to an element ya* of S, .
2.
58
OPERATOR THEORETIC ITERATIVE METHODS
We claim that ya* is a zero of F. I n view of the analog of (5.72) for arbitrary n, we have (a) II F(Yn+1,a)il < Ka%Z1 4a+1a 2a--2Yn,u
(5.82)
[using the analog of (5.74)]. It follows that limn+oo11 F(yn,J1= = 0 as F is continuous. All that remains is the establishment of the rate of convergence inequality (5.54). But, since
I( F( ya*)ll
IlYa* - Y n . a
11 <
(5.54)
will follow from the estimate
(5.83)
7n.a
and the fact that relations (5.84) (5.85)
< (&In
c m
7n+j.a
9
j=O
(2h0,a)(a+l)n--l 70.a
< 4..But (5.83) is a direct consequence of the 7n.a =
5
(2hn--l,n)u %-La
< ;(2h0,Ja+l)"
which follow from the definitions of qn,a and h,,a of the theorem is complete. We use this theorem in Chapters 4 and 5.
.* Thus, the proof
CHAPTER 3
REPRESENTATION O F B O U N D A R Y V A L U E PROBLEMS
3.1.
Introduction
We noted in Chapter 2 that two-point boundary value problems (TPBVP’s) can be represented by operator equations. Here, we shall examine, in detail, the problem of developing suitable representations for continuous and discrete TPBVP’s. More precisely, we consider TPBVP’s of the form
or of the form
where F , g , and h are suitable vector valued functions and c is a constant vector. We note that (1.1) and (1.2) are normalized with respect to time. We show that (1.1) can be represented by a variety of integral equations and that (1.2) can be represented by a variety of “summation equations.” These representations involve linear TPBVP’s in a crucial way. Thus, we devote some attention to linear TPBVP’s, i.e., to problems of the form
or of the form
59
60
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
where V ( t ) ,f ( t ) , AQ), B ( j ) , and f(j) are suitable vector and matrix valued functions, M and N are matrices, and c is a constant vector. We use the results of this chapter throughout the sequel.
3.2.
Continuous Linear Two-Point Boundary Value Problems
IYe consider a linear TPBVP of the form (2.1 )
j,
=
MY(O)i ~ y ( i = )
r y t ) y -i-f(t),
where V ( t ) ,M , and N are p x p matrices andf(t) and c a r e p vectors. IYc suppose that V ( t )andf(t) are defined and measurable on an open interval I containing [0, 11 and that there is a (Lebesgue) integrable function m(t) on I such that 11 V(t)li m ( t ) and Ilf(t)ll m(t). We then have the following.
<
<
DEFINITION 2.2. A p vector valued function $ ( t ) i s called a solution o f (2.1) if (i) $ ( t ) i s absolutely continuous, (ii) $(t) = I - ( t )$ ( t ) j ( t ) for almost all t , and (iii) MJr(0) N$(l) = c.
+
LEMMA 2.3. Let 9 denote the s e t of all solutions of (2.1). Then Y i s nonempty if and only if c - N Oy(l, s ) f ( s ) ds = 5 is an element of the range of M N O y ( l ,0) where Ov(t,s) is t h e fundamental matrix of the linear system j = V(t)y. Moreover, if y is any p vector with [izl -t N O y ( l , O)] y = 5, then 9’i s “isomorphic with” y ,A-(M 1- N O Y ( I ,0)) where M ( M N Q Y ( l ,0)) i s the null space of lli‘ N Q V ( l ,0).
+
+
Jt
+
+
Proof. By virtue of the standard existence and uniqueness theorem for initial value problems [C4], we can write the unique solution of i. V ( t ) y+ f ( t ) for a given initial value y(0) as ~
(2.4)
For t
1, this solution will pass through the point
3.2.
CONTINUOUS LINEAR TWO-POINT BOUNDARY VALUE PROBLEMS
61
Thus, y ( t ) [as given by (2.4)] will be a solution of (2.1) if and only if My(0)
(2.5)
+ NQY(1 , O ) [y(0) + 1:@yo,s ) f ( s ) ds1
=c
i.e., if and only if (2.6)
[ M + N @ Y ( l , O ) ] y ( 0 ) = c - N ~0 l @ V ( l , s ) f ( s ) d s = ~
or, equivalently, if and only if 4 is an element of the range of M + N O Y ( l , 0). Finally, if y is a n y p vector with [M+NOY(l, O)]y = 5 and $(t) is any element of 9, then $(O) - y is an element of N ( M NOV(I,0)) and the lemma is established.
+
+
COROLLARY 2.7. If det([M NOV(I,O)]) # 0, then (2.1) has a unique solution $ ( t ) which can be expressed in t h e following form (2.8)
+ ( t ) = H v M N ( tc)
+-
1' 0
GVMN(t, s ) f ( s ) ds
where t h e Green's matrices H v ~ ~ (and t ) G v ~ ~ ( t are , s ) given by
(2.9)
HVyt)
and
(2.10) GVMN(t, S) =
i
-
=q
t , O)[M 4-N@V(1,O)l-l
+ @"(t, O)[M + @V(t,
O)[M
N @ V ( l , O)]-1
M@V(O,s),
N@V(l,O)]-l
N@V(1, s),
<s < t t <s < 1
0
respectively. Proof. By virtue of Lemma 2.3, (2.1) has a unique solution $(t) which is given by
(2.11)
+ N@"(I, c - @"(t, O)[M + NOV(l, O)]-l NQV(1, 0) 1' @"(O, + W ( t , O)[M + 1,0)]-' [ M + N@V(1 , O)]
# ( t ) = @"(t, O)[M
O)]-1
0
N@V(
x [@"(t, O)]-1 q t , 0) J t @yo,s ) f ( s ) ds. 0
s ) f ( s ) ds
62
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Cancellation of the terms @"(t, O)[M
+ N@"(l,0)l-I N@"(1,0 ) 1'@"(O,
s ) f ( s ) ds
in (2.1 1) yields the desired result. Thus, the corollary is proved. I n order to avoid needless repetition of the conditions of existence and uniqueness, we introduce the following. DEFINITION 2.12. Let V(t), M , and N be p x p matrices. Then the s e t { V ( t ) ,M , N } will be called boundary compatible if (i) V ( t ) i s measurable with /I V(t)li m(t) f o r an integrable m ( t ) , and (ii) det(M NW'(1, 0)) # 0 where W ( t , s) is t h e fundamental matrix of j = V(t)y;or, equivalently, if (2.1) has a unique solution for allf(t) and c.
<
+
I n the sequel we shall often be given two boundary related matrices M and N and will be required to determine a matrix V ( t )so that the set { V ( t ) ,M , N } is boundary compatible. With a view toward making such a determination, we prove the following simple lemma which gives a necessary and sufficient condition for the existence of a matrix V ( t )such that { V ( t ) M , , N } is boundary compatible. LEMMA 2.13. Let M and N b e p x p matrices. A necessary and sufficient condition that there be a V ( t )w i t h {V(t),M , N } boundary compatible is that the p x 2p matrix [ M N ] have full rank p . Proof. We prove the lemma with some well known results from linear algebra (see, for example, Nering "11). If [ M N ] is of rank less than p , say of rank r, then there are only r linearly independent columns in [ M N ] . These r columns (column vectors) span an Y dimensional subspace D, of R P . Any column obtained by adding a column of M to a linear combination of columns of N lies in this subspace D,. Therefore, for any V(t)and corresponding fundamental matrix @"(1, 0), all columns of the matrix ( M N@"(l,0)) belong to D , . This implies that ( M NQV(1,0)) has at most r(
+
det(M
+
+ N@"(l,0))= 0
for all V(t).It follows that there is no matrix V ( t )which is boundary compatible with M and N in view of Definition 2.12. This proves necessity.
3.3.
DISCRETE LINEAR TWO-POINT BOUNDARY VALUE PROBLEMS
63
If [ M N ] is of rank p , then there are p linearly independent columns in [ M N ] . Let M have q ( G p )linearly independent columns; then N has p - q columns which are linearly independent of the columns of M . By postmultiplication of N by a product of elementary matrices Q([Nl]), we can assure that: ( 1 ) the p - q columns of N , which are linearly independent of the columns of M , have the same position in the matrix NQ as the linearly dependent columns in the matrix M , and (2) the remaining q columns of NQ are multiples of the original columns of N. I n this manner we find that the sum M NQ has p linearly independent columns, or equivalently, that
+
det(M
+ NQ) f 0.
Since any product of elementary matrices is nonsingular, Q is nonsingular and hence the logarithm of Q exists [GI, p. 2391. If we choose (2.14)
V ( t )= V
= log Q,
then, in view of the expression for the fundamental matrix of a timeinvariant system, we have @"(t,s)
ev(t-s)
and
@v(l, 0) = ev
elogQ =
Q
so that
(2.15)
det(M
+ iWv(1,0)) = det(M + NQ) # 0
which proves that {V,M , N } is boundary compatible. Thus, the lemma is established. We shall use the results of this section to obtain integral representations for continuous TPBVP's of the form (1.1) in Section 4.
3.3.
Discrete Linear Two-Point Boundary Value Problems
We consider a discrete linear TPBVP of the form
3.
64
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
matrices and f(j) and c are p vectors. We suppose that A(j), B ( j ) , and f ( j ) are defined for j E (0, 1, . . . , q - I } and that det(Z
(3.2)
~
A ( j ) )# 0
for j E (0, 1, . . . , q - l}, i.e., that I W’e thcn h a w the following.
-
A ( j ) is nonsingular for all j .
DEFINITION 3.3. A p vector valued function $ ( j )i s called a solu1) B ( j )$ ( j ) +f(j) t i o n of (3.1) i f (i) $ ( j 1) - $ ( j ) = A ( j )$ ( j for j = 0, 1, . . . , q - 1, and (ii) M$(O) N$(q) = c.
+
+
+ +
LEMMA 3.4. Let Y denote t h e set of all solutions of (3.1). Then ,Yi s nonempty if and only if
+
i s an element of the range o f M NQVY(q,0) where W ( j ,i) i s t h e transition matrix o f t h e linear system y ( j 1) - y ( j ) = V ( j ) y ( j ) with V ( j ) = [ I - A(j)]-l[ A ( j ) B(j)].* Moreover, if y i s any p vector w i t h [ M -1 NQV(q,O)] y = 6,then Y i s “isomorphic with” y -C $-(hi‘ N@”(q,0)) where N ( M N@”(q,0)) i s t h e null space of M N@“(q,0).
+
+
+ +
I
+
Proof. By virtue of the standard existence and uniqueness theorems for discrete initial value problems [P4], we can write the unique solution of y ( j 1) - y ( j ) = V ( j ) y ( j ) f(j) for a given initial value y(0) as
+
(3.5) Forj
y(j) =
* The
=
W ( j ,0 )y(0)
+
+ k1 W ( j ,i + l)[f z=n
-
lI(i)]4f(q.
q, this solution will pass through the point
transition matrix W(j, i) is given by
W ( j ,i)
[I + V ( j
=
~
I)]
... [ I + V ( i ) ] ,
j
> i 4-1
. = a..
3.3.
DISCRETE LINEAR TWO-POINT BOUNDARY VALUE PROBLEMS
65
Thus, y ( j ) [as given by (3.5)] will be a solution of (3.1) if and only if
+ N@%, O ) Y ( O ) + N c
Q-1
(3.6)
My(0)
@Y(q,
i=o
i
+ 1)[1
-
1
A(i)]-lf(Z)= c
i.e., if and only if (3.7) [ M
+ N @ V ( Q , O)] y(0)
=c -
N
or, equivalently, if and only if ( is an element of the range of M+NOV(q, 0). Finally, if y is a n y p vector with [M+NOY(q,O)]y = ( and $ ( j ) is any element of 9, then $(O) - y is an element of N(M NOy(q,0)) and the lemma is established.
+
+
COROLLARY 3.8. If det([M NOV(q,O)]) # 0, then (3.1) has a unique solution + ( j )which can be expressed in the following form (3.9)
# ( j ) = H V M N ( jc)
n -1
+1
GYMN(j,
i-0
i)f(i)
where t h e Green's matrices H % N ( ~and ) G Y ~ ~i)( are j , given by (3.10)
HY"(j)
and
(3.1 1 ) GVMN(j, i) =
respectively.
I
=q
j , O)[M
+ N@V(q,0)I-l
- H V M N ( j ) N@"(q,i
+ @'(j,i + 1)[1
+ 1)[1
-
-HYMN(j)
N@Y(q,i
-
4i)l-l
A(i)]-l,
+ 1)[1
-
o
A(i)]-1,j
-
1
Proof. By virtue of Lemma 3.4, (3.1) has a unique solution $ ( j ) which is given by
3.
66
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
;y W ( q , i + l)[I
x
i=O
- A(i),-lf(i)I
+
@Y(j, i=O
i + 1)[1- A(i)]-lf(i)
and so the corollary is proved. COROLLARY 3.13. If, in addition t o the assumptions of Corollary 3.8, it i s assumed that the matrix I V ( j )= [I - 4 j ) I - l [I B ( j ) ]is nonsingular f o r j E (0, 1, . . . , q - I}, then (3.1) has a unique solution # ( j ) which can be expressed i n the form $ ( j ) = H ~ M Nc ( ~ ) G Y ~ ~i )( f j( i, ) where H ' M N ( ~is) given by (3.10)and G V ~ ~i)( ijs ,given by
+
+
+
(3.14) G v M N (i)j , =
I
~~~~
HYMN(j) -HVMN(j)
+ 1 ) [ 1A(i)]-l, ~ 0
M@V(O,i
-
Proof. By virtue of the additional assumption, we have @ v ( i , j ) = @Y(i, k) @ v ( k , j ) and @ v ( j , i) = [ @ Y ( i , j ) ] - l . It follows that,
for 0
(3.15)
-
1,
+ 1)[1- 4i)I-l + @'(j,i + l ) [ I - 4i)l-l W ( j ,O)[M + N W ( q , O)]-1 N@V(q,i + 1)[I - A@)]-1
H Y M N ( jN@'(q, ) i =
-
+ q j ,0" + N@v(q,O)lkl
x M@Y(O,j)W ( j ,i + 1)[1 - A(i)]-l
+ @V,0" + N@%, 0)l-l x N@'(q, 0) aV(O, j ) @"(j,i
=HVMN(j)
M@"(O,i
+ l)[I
-
+ 1)[1
-
4i)l-l
4i)l-l
and hence, by (3.1 I ) , that the corollary is valid. We now have the following.
DEFINITION 3.16. Let A ( j ) ,B ( j ) ,M , and N b e p x p matrices. , ( j ) ,M , N } i s called boundary compatible Then the set { A ( j ) B if (i) [I - A ( j ) ] i s nonsingular for j E (0, 1 , . . . , q - I}, and (ii)
3.4. det(M
CONTINUOUS TWO-POINT BOUNDARY VALUE PROBLEMS
67
+ NQy(g,0)) # 0 where W ( j ,i) is t h e transition matrix of
t h e linear system y ( j
+ 1) - y ( j ) = V ( j ) y ( j )with
or, equivalently, if (3.1) has a unique solution for all f(j) and c.
By analogy with Lemma 2.13, we have the following simple lemma which gives a necessary and sufficient condition for the existence of matrices A ( j ) and B ( j ) such that {A(j),B(j),M , N ) is boundary compatible.
LEMMA 3.17. Let M and N be p x p matrices. A necessary and sufficient condition that there be matrices A ( j ) and B ( j ) with {A(j),B ( j ) ,M , N ) boundary compatible i s that the p x 2p matrix [ M N ] have full r a n k p . Proof. T h e proof of necessity is exactly the same as the proof of necessity in Lemma 2.13. As for sufficiency, we again determine NQ) f 0. T h e n the logarithm a nonsingular matrix Q with det(M of Q, logQ, exists and the matrix S = (logQ)/q has the property es, then that (eS)Q = Q. If we let A ( j ) = 0 and B ( j ) = --I V ( j )= --I es and Q y ( g , 0) = [I V(q - I)] . . * [I V(O)]= (e”)* = Q. It follows that det(M NQy(q,0)) = det(M NQ) f 0 and thus the lemma is established. We shall use the results of this section to obtain summation representations for discrete TPBVP’s of the form ( I .2) in Section 5. We observe that there is considerable similarity between the results of this section and the results of Section 2. This is no accident. I n fact, similar results can be derived in a very general context for abstract linear boundary value problems in Banach spaces (see, for example, Conti [CS]). Such a generalization is particularly useful in the treatment of boundary value problems for distributed systems.
+
+
3.4.
+
+
+ + +
Representation of Continuous Two-Point Boundary Value Problems
We now develop integral equation representations for TPBVP’s of the form ( I .l) using the results of Section 2. T h e equivalence between differential equation and integral equation representations of
68
3.
REFRESENTATION OF BOUNDARY VALUE PROBLEMS
'1'PHIT''s has been known for a long time. I n fact, Picard [P2] used this equivalence to prove the convergence of various iterative methods for the solution of nonlinear TPBVP's. We now have the following. THEOREM 4.1. Let D be an open set i n Ii, and l e t I be an open set i n R containing [0, I]. Suppose t h a t (i) F ( y , t ) i s a map of I) x I i n t o D which is measurable i n t for each fixed y and continuous i n y for each fixed t ; (ii) t h e r e i s an integrable function m ( t ) such t h a t liF(y, t)l: m ( t ) o n D s I ; (iii) g ( y ) and h ( y ) are maps of D into D ; and (iv) ( V ( t ) ,M , N ) is a boundary-compatible set of dimension p . Then t h e boundary value p r o b l e m
<
has t h e equivalent representation
1-
1' 0
G Y M N (s){F(y(s), t, s)
~
1 ( s ) y ( s ) } ds
where t h e Green's functions W ' M N and ( ~ )V'MN s) (are ~ , given by
and
w h e r e Ov(t,s) i s t h e fundamental m a t r i x of t h e linear system I -(t)y.
q
~~
Proof. \Ye must show that a solution of (4.2) is also a solution of (4.3) and, conversely, that an absolutely continuous solution of thc integral equation (4.3) is a solution of the TPBVP (4.2). 1,ct $ ( t ) hc a solution of (4.2). 'l'hen $ ( t ) is also a solution of the linear 'lTH\'P
3.4. CONTINUOUS
TWO-POINT BOUNDARY VALUE PROBLEMS
69
where
SinceF(y, t ) satisfies (i) and (ii) and V(t)is measurable and dominated by an integrable function, f ( t ) is measurable and dominated by an integrable function. Moreover, det(M N@"(l,0)) # 0 in view of (iv). Thus, all the conditions of Corollary 2.7 are satisfied for the linear TPBVP (4.6).It follows that the solution of (4.6)is unique and is given by
+
(4.8)
+(t) = H V M N ( t ) d
+ j' G Y M N ( t , s ) f ( s ) ds 0
where H " M N ( ~ and ) G " M Ns)( ~ are , given by (4.4)and (4.5).From (4.7) and (4.8), we then deduce that
which shows that # ( t )is also a solution of the integral equation (4.3). Conversely, let +(t) be an absolutely continuous function which satisfies the integral equation (4.3).In view of (4.4)and (4.5)we see that (4.10) 4(t) = @"(t, O)[M
+ N@v(l,O)]-l
70
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Straightforward substitution gives
= c - g[d(O)l - h")l
and so
+ MdJ(0)+ W(1)
+4 " 1
= c.
This shows that +(t) satisfies the boundary conditions of (4.2). Differentiation of both sides of the expression (4.10) for +(t) (which is possible a.e. because +(t)is absolutely continuous) leads to
+ N@V(l,O)]-1 x {c -g[C(O)l -g[C(1)1 + M+P)+ N+(I)J -t V ( t )@"(t, O)[M + N@V(l,O)]-l
+ ( t ) = V ( t )@"(t, O)[M
3.5.
71
DISCRETE TWO-POINT BOUNDARY VALUE PROBLEM
- V(t)@“(t, O)[M
+ N @ Y ( l ,O)]-’
x ~ @ v ( l0), J 1 @ T O , W ( + ( S ) ,
4 - V(’(s) +(4)ds
+ @.(t, O)[M + N @ V ,0)l-l MGV(0,t){F(+(t),t ) v(t)+(t): + DV(t,O)[M + NQV(l,0)l-’ ~ @ v ( l , o ) @ v (t){F(+(t), o, t) - W+(t>> w +(t> + F(+(t), t ) W )+ ( t ) -
=
-
= F(+(t),t )
and so +(t)satisfies the differential equation of (4.2). This completes the proof of the theorem. We observe that Theorem4.1 remains true if the hypothesis (i) is replaced by the following hypothesis: (i’) F ( y , t ) is a map of D x I into D which is Bore1 measurable in the pair ( y , t). 3.5.
Representation of Discrete Two-Point Boundary Value Problem
We now develop summation equation representation for TPBVP’s of the form (1.2) using the results of Section 3. T h e development is entirely analogous to that of Section4. I n particular, we have the following. THEOREM 5.1. Let D be a subset of Rp and let Q’ = (0, 1, . . . , q - I}. Suppose that (i)F(u, v,j) i s a map of D x D x Q‘
i n t o D ; (ii) g ( y ) and h ( y ) are maps of D i n t o D ; and (iii) {A(j),B(j),M , N } is a boundary-compatible set of dimension p. Then t h e boundary value problem (5.2) Y ( i
+ 1) - Y ( i )
=F(y(i
+ l ) > Y ( i ) ? d > g ( y ( 0 ) )+ h ( Y ( d )
has the equivalent representation
(5.3) Y ( i >= HVM””(i){c- g ( A 0 ) ) - h ( Y ( d )
+ MY@) + NY(d1
=c
72
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
j = 0, 1,. . . , q where t h e Green's functions H v ~ ~ (and j) G v ~ ~ k() jare , given by
for
(5.4)
HVMN(j)
~~
@"(j,O)[M
+ NQY(q,0)I-l
and
(5.5) G
where
r(i -1-
Proof. We must show that if a sequence $(O), . . . , $(q) satisfies (5.2),then it also satisfies (5.3) and, conversely, that a solution of the
summation equation (5.3) is also a solution of the TPBVP (5.2). Now let $(O), . . . , $(q) be a solution of (5.2). Then $(O), . . . , $(q) is also a solution of the linear TPBVP
where
Since f(j)is defined for all j in Q' and since { A ( j ) ,B b ) , M , N ) is a boundary-compatible set, all the conditions of Corollary 3.8 are satisfied by the linear TPBVP (5.6). It follows that $(O), . . . , $(q) is the unique solution of (5.6) and hence, can be written in the form
(5.8)
$ ( j ) = HVMN(j) d -1-
5' Gv MN (j,k ) f ( k ) k=O
where Z P M N ( ~ and ) G v ~ . v (Kj ), are given by (5.4) and (5.5), respectively. From (5.7) and (5.8), we then deduce that $(O), . . . , $(q) is a solution of the summation equation (5.3).
3.5.
DISCRETE TWO-POINT BOUNDARY VALUE PROBLEM
Conversely, let us suppose that +(O), Then, for any k in Q',
. . . ,+(q)
+ 5' [GYMN(k+ 1, 1 )
-
73
is a solution of (5.3).
GvMN(k, l)]fb(l)
1=0
where
I n view of (5.4), we can see that (5.11)
+
HVMN(k 1)
-
H'MN(k)
=
[@'(k
+ 1,O)
x [M
+ 1 , I)
for k in Q'. Now, for k 3 I, @'(k (since W ( j ,i) = [I V ( j - l)] @.(j, i) = I if j = i). Thus,
+
* * *
-
@'(k,
+ N W q , 0)l-1
O)]
- @ '(k, I ) = V ( k )@'(k, I ) [I + V ( i ) ] if j 3 i + 1 and
for k in Q'. Similarly, we deduce from (5.5) that G'MN(k
+ 1, 1 )
-
GVMN(k, I)
is given by the following formulas:
+
(5.13) GVMN(k 1 , 1 )
-
GVMN(k, 1)
+ 1) - HYMN(k)] N@'(q, 1 + 1)[1 A(Z)]-l + [ W ( k + I , 1 + 1) @'(k, I + l)][I - A ( 4 - l = V(k) N@'(q, I + l)[I A(41-1 + V(k)W ( k , I + l)[I 4 4 - 1 =
- [H'MN(k
-
-
-
-
HYMN(k)
-
=
V(k)GYMN(k, I)
3.
74
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
+
(5.14) GvMN(k 1 , Z )
ifk < l (5.15)
-
GYMN(k, I)
+ 1)
=
- [HYMN(k
=
V ( k )GvMN(k, I)
-
H54N(k)] N@"(q,I
+ 1)[1
-
A(1)I-l
1;and
+
GYMN(k 1,Z) - GVMN(k, 1)
+ 1) HvMyk)] N@"(q,z + 1)[1 + + 1, I + 1)[1 A(Z)]-1 = V(k)GYMN(k, I ) + [ I A(I)]-' =
- [HYMN@
-
@V(k
-
A(q1-1
-
-
if k
=
(5.16)
1. Substitution of (5.12) and (5.13)-(5.15) into (5.9) leads to
+@ + 1) - 4 w
=
W+(4 + [ I - A(k)I-lf,@)
or, equivalently,
for any k in Q'. Thus, d(O), . . . ,+(q) satisfies the difference equation (5.2). The proof that +(O), . . . , +(q) satisfies the boundary condition of (5.2) proceeds along similar lines. We observe that (5.19)
M+(O)
+ N+(g) = [MHVMN(0) + NHvMN(q)]d,
75 where
and Since (5.20)
by virtue of (5.4) and since
I) + NGvMN(q,1 ) (5.21) MGYMN(O, =
-
[MHV""(O)
+ N H Y y q ) ] N@Y(q,I + 1)[I
+ N@"(q,1 + 1"
-
-
A(1)I-l
44-l
=o
Thus, the proof of the theorem is complete.
3.6.
A Continuous Example
We illustrate the results of Sections 2 and 4 with a simple example. We proceed as follows. First, we illustrate Lemma 2.13 by the choice of a matrix V which is boundary compatible with the matrices M and N of the example. Then we use Corollary2.7 to determine an expression for the linear TPBVP corresponding to the boundarycompatible set { V , M , N } . Finally, we use Theorem 4.1 to obtain an integral equation which is equivalent to the original TPBVP.
76
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
We consider the nonlinear TPRVP
with
E
> 0.
Obvious choices for M and N are given by
and the matrix [ M N ]has rank 2. I t follows from Lemma 2.13 that there is a matrix V ( t ) such that { V ( t ) M , , N } forms a boundarycompatible set. We first try the simplest matrix V = 0. T h e n @"(t,s) = eo(t-s) = I and dct(M -4- ArDy(1,0)) = det(ill N I ) = 0. Thus, the choice V 0 docs not result in a boundary compatible set. This shows that not cvcry matrix of the proper dimension leads to a boundarycompatible set. We next try the matrix
+
~
(6.3)
'l'hcn
for all t , s and so
is nonsingular. It follows that { V , ill, V}is a boundary-compatible set.
3.6. Since [ M
+ N@y(l,O)]-lis given by [M
+ N@Y(l,O)]-1
=
[
-1
we have (6.7)
H Y M N ( t= ) @'(t, O)[M
G v M N ( t , S) = H V M N ( tM@"(O, ) S) =
for 0
< s < t, and
(6.9)
GYMN(t, S)
il:
()N@V(l,s)=
= - HYMN t
1 01
+ N@'(l,0)I-l =
and (6.8)
77
A CONTINUOUS EXAMPLE
- ( l - - lSs
[I; -41 -t(l ~
for t
< s < 1. It follows that
is given by
I
(1
~
s)
the solution of the linear TPBVP
78
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
for t in [0, I]. We note that if fl(t) = 0, then (6.12) reduces to the well-known solution [All of the linear TPBVP y l ( t ) = f 2 ( t ) ,yl(0) = cl, Y d l ) = c2. Using (6.1 1) and Theorem 4.1, we find that the original nonlinear TPBVP (6.1) is equivalent to the following integral equation:
+I: [[
1- t
-
-1
+s
+i:I[-I -
t
(1
- t(1
-
1
t)s
- s)
-(l-s)l
< <
with E > 0 and 0 t 1. This type of integral representation will play an important role in the sequel.
3.7.
79
A DISCRETE EXAMPLE
3.7. A Discrete Example T o illustrate the results of Scctions 3 and 5 we discuss a simple discrete example which is very similar to the continuous example of Section 6. Our approach is also very similar. First, we illustrate Lemma 3.4 by the choice of two matrices A ( j ) and B ( j ) [which determine the matrix VG)] which are boundary compatible with the matrices M and N of the example. Then, we determine the expression for the solution of the linear TPBVP corresponding to the boundary-compatible set {A(j),B ( j ) ,M , N } with the aid of Corollary 3.8. Finally, we use Theorem 5.1 to obtain a summation equation which is equivalent to the original discrete TPBVP. We consider the nonlinear discrete TPBVP (7.1
,
Obvious choices for the matrices M and N are
which results in a matrix [ M N ] with rank 2. Lemma 3.17 then implies the existence of matrices A ( j ) and B ( j ) which form a boundary-compatible set with these matrices M and N . Just as in the continuous case, we first try the simple matrices A ( j ) = 0 and B ( j ) = 0. This choice results in a matrix V ( j )= [ I - A(j)]-'[A(j)+BG)]= 0, W ( j ,k) = I , and det(M+NW'(q, 0)) = 0. T h e resulting set { A ( j ) ,B ( j ) ,M , N } is thus not boundary compatible, which shows that not every set of matrices of the proper dimension is boundary compatible. We next try the matrices (7.3)
A=[;
3
,1
B = [ ,0 0
80
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
This choice leads to (7.4)
and
Sincc det(M -4- NQV(q,0)) = -q, the last matrix is nonsingular. 'This implies that the choicc (7.3) results in a boundary-compatible set. \I.'ith [ M -1- N@(q,0)I-l given by
[ M k LV@(Q,O)]-1
(7.7)
=
\vc have (7.8)
H Y M N ( j )= @'(j, O)[M -1- N@'(g, 0)I-l
=
and with Corollary 3.13 being applicable
(7.9)
i)
GVMN(~,
1
forO
MGV(O,i
( J' )
= HYMN
-
jq-l
+ 1)[1- 4i)l-l
( I -jq-l)i
],and
G"MN(j,i)
-=
- H'MN
=I -
jq-l 4-1
( j )N@'(q, i jq-l(q
-
- q--l(q-
1
+ ])[I i)
1
i)
-
4i)l-l
3.7.
A DISCRETE EXAMPLE
81
< <
i q. According to Corollary 3.8, the solution of the discrete forj linear TPBVP
is now given by (7.12)
q-I
- *-I
Using this result, (7.12), and Theorem 5.1, we find tha t the original nonlinear, discrete TPBVP (7.1) is equivalent to the summation equation
82
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Summation equation representations of this type play the same role in the discrete case as the integral equation representations play in the continuous case.
3.8.
Computation of Derivatives: Continuous Case
We have seen that if the conditions of Theorem 4.1 are satisfied, then the TPBVP (8.1)
Y =F(Yt
%
AY(0))
+ h(Y(1)) = c
is equivalent to the integral equation (8.2)
Y ( t >= H"""(t){c
+
-
s1
+ MY(0) + N Y U ) )
d Y ( 0 ) l - "(111
G"""(t, W ( Y ( S ) ,S)
-
W Y ( S ) )dS
where H"""(t) and G Y ~ " (s) t , are the Green's matrices of the linear TPBVP corresponding to the boundary-compatible set J = { V ( t ) ,M , N } . Assuming that the conditions of Theorem 4.1 are satisfied, we can define a mapping TJ of the Banach space Y = %?([O, 11, Rp)into itself by setting
(8.3)
+ MdO)+ N d l ) )
TJ(v)(t)= H J ( W - '&" - 4 d ) l
+ where y(
0
)
E
s1 0
GJ(kS){F(dS),4
-
V(S)d s ) > ds
%'([0, 11, R p )and HJ(t ) = H " M y t ) ,
GJ(t,S )
>.*
= GYM" (t ? s
Then (8.2) is equivalent to the fixed-point problem (8.4)
Y
=
WY)
* TJ(v)(.)is continuous in view of (4.4) and (4.5) and the continuity of
@"(t, 0).
3.8.
COMPUTATION OF DERIVATIVES: CONTINUOUS CASE
83
on V([O, 11, R,) and we can apply the various algorithms of Chapter 2 to (8.4). We shall actually make this application in Chapter 4. However, in order to interpret the theorems and algorithms of Chapter 2 explicitly in terms of F, g, and h, we require the (Frechet) derivatives of the operator TJ and estimates on the norms of these derivatives. We obtain the required derivatives and estimates in this section. We begin with the following. LEMMA 8.5. Let D be an open set i n R, and l e t I be an open set i n R containing [0, 11. Suppose that (i) K ( t , y , s) is a map of I x D x I i n t o R, which is measurable i n s for each fixed y and t and continuous i n y f o r each fixed s and t ; (ii) (aK/ay)(t,y,s) i s a map of I x D x I i n t o &(I?,, R,)* which is measurable i n s for each fixed y and t and continuous i n y f o r each fixed s and t ; (iii) t h e r e is an integrable function m(t, s) o f s w i t h sup t
fm(t,
s) ds
< co
o
II K ( t ,y , s)ll < m(t, s) and Il(aK/ay)(t,y, s)ll < m(t, s) o n x D x I; and (iv) lim,,,, Ji I/ K ( t ,y(s), s) - K(t',y(s), s)ll ds = 0,
such that
I
Ji
and lirn,+,, Il(aK/ay)(t,y(s), s) - (aK/ay)(t', y(s), s)ll ds = 0 for all t , t' i n [0, 11 and y ( * ) i n V([O, 11, D).Then t h e mapping T given by T(u)(t)=
s1 n
K ( t ,u(s), s) ds
i s a differentiable mapping of V([O, 13, derivative
D) i n t o V([O, 11, RP)w i t h
(8.7) where u ( - ) i s i n V([O, 11, D). Proof. We first observe that the mappings T and T,' carry %?([O, I], D) into V([O, 11, R,) in view of (i), (ii), and (iv) [BO]. Now let u(.) be an element of V([O, 11, D ) and let w ( * ) be any element of V([O, 11, R,) with the segment u ( - ) Ow(.), 0 < O < 1, in V([O, 11, D).
+
* The set of p
x p matrices.
84
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Then
<
2 11 w(s)ll m(t, s) in view of (iii). and hence, that 11 $(t, s, w(s))ll This implies that ( 1 1 $(t, s, w(s))ll/ll w(-)ll) 2m(t, s). Since m ( t , s) is integrable,
<
by the Lebesque dominated-convergence theorem. Thus, the lemma is established.* We observe that the lemma remains true if the hypotheses (i) and/or (ii) are replaced by the conditions: (i)' K ( t ,y , s) is a map of I x D x I into D which is Bore1 measurable in the pair ( y , s) for each t ; and (ii)' (aK/Zy)(t,y , s) is a map of I x D x I into 4 ( R , , R,) which is Bore1 measurable in the pair ( y , s) for each t. We now have the following. C O R O L L A R Y 8.9.
Suppose th a t t h e function K ( t , y , s) = V(s)y}satisfies t h e conditions of Lemma 8.5 and thatg, h a r e differentiable. Then t h e o p e ra t o r TJ i s differentiable and
GJ(t,s ) ( F ( y ,s) * Note that
-
ri I( #(t, s, w(s)) 11 ds is continuous in t by virtue of (iv).
3.8.
COMPUTATION OF DERIVATIVES:
where q(*)E %([O, 11,
CONTINUOUS CASE
85
D).
[ N o t e that, for example, Fil(y(s),s) is the three-entry matrix with elements (a2Fj/ax,axl)(q(s),s).]
* As regards ( a K / a y ) ( t , y , s), the hypothesis (ii) becomes the following: ( a 2 K / a y 2 ) ( t ,y, s) is a map of I x D x I into B(R, , R,) which is measurable in s for each fixed y and t-and continuous in y for each fixed s and t where B(R,, R,) is the space of bilinear forms on R , @ R, .
86
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
We can obtain estimates of the norms of the operators (TqJ)‘and
(ToJ)” from Corollaries 8.9 and 8.11. We recall first of all that if
4.)E W O ,
11, Rp), then
II w(.)ll
(8.16)
= SUP SUP
i e l t€[0,1]
I 4t>I
is the norm of w(-)where 9 = {1,2, . . . ,p } and mi(*)is the ith component of w( Noting that I]( ToJ)’ 11 = supllull~l{I[( TmJ)’uI/} and letting H J ( t ) = [H$(t)], GJ(t,s) = [G&(t,s)], M = [mjk], N = [njk], V(s)= [vjk(s)], we have 0 ) .
(8.17)
ll(T4J)’ll =
SUP{/I(T~~)’ u II>
3.8.
COMPUTATION OF DERIVATIVES: CONTINUOUS CASE
87
Since the actual estimate (a) and the somewhat coarser estimate (b) are often difficult to evaluate in practice, we frequently use the coarse estimate (c). Similarly, since the norm of the bilinear operator ( TaJ)”(u,u ) is given by II(TaJ)”II
we have
=
suP{II(T,J)” (% 7 4 l >,
Ilull
88
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Again the actual estimate (a) and the somewhat coarser estimate (b) are often difficult to evaluate in practice and so the coarse estimate (c) is frequently used. We use the estimates (8.17) and (8.18) quite often in the sequel. T o avoid repetition of these cumbersome formulas, we write [I( TmJ)' li( TmJ)'jl(,,) , and /I( TW5)' Il(c) in place of the right-hand sides of (8.17), (a), (b), and (c), respectively, and ll(TmJ)" II(d II(TmJ)" Il(1,) and li( TaJ)"Il(r) in place of the right-hand sides of (8.18), (a), (b), and (c), respectively. Thus, for example, ll(TmJ)' 6 means that the right-hand side of (8.17) (c) is no greater than 6. 9
9
<
3.9.
Computation of Derivatives: Discrete Case
We have seen that if the conditions of Theorem 5.1 are satisfied, then the TPBVP
is equivalent to the summation equation
where H " M N ( and ~ ) G v ~ ~k) ( jare , the Green's matrices of the linear TPBVP corresponding to the boundary-compatible set
1= {4), W )M , , w. Assuming then that the conditions of Theorem 5.1 are satisfied and letting Q = {0, 1, . . . , q}, we can define a mapping TJ of the Banach space Y = 9 ( Q , R1,)into itself by setting (9.3)
TJ(P))(i) =I
W { C - g[dO)I - h
[Ml
+ M d O ) + NdqN
3.9.
COMPUTATION OF DERIVATIVES: DISCRETE CASE
89
where E Y(Q, R,) and H J ( j ) = H v ~ ~ ( jGJCj, ) , k) = G ” M N (k). ~, Then, (9.2) is equivalent to the fixed-point problem ~
(
0
)
(9.4)
Y
=
TJ(Y)
on Y(Q,R p )and we can apply the various algorithms of Chapter 2 to (9.4).We shall actually make this application in Chapter 4. However, in order to interpret the theorems and algorithms of Chapter 2 explicitly in terms of F, g, and h, we require the (Frechet) derivatives of the operator TJ and estimates on the norms of these derivatives. We obtain the required derivatives and estimates in this section. We begin with the following.
LEMMA 9.5. Let D be an open s e t i n R, and l e t Q = (0, 1, . . . , q} and Q‘ = (0, 1 , . . . , q - l}. Suppose that (i) K ( j , x , y , k) i s a map of Q x D x D x Q‘ i n t o R, ; (ii) (aK/ax)(j,x , y , k) and (aK/ay)(j,x , y , k) are maps of Q x D x D x Q’ i n t o &(I?,, R,) w i t h (say) (aK/ay)(j,x , y , k) continuous i n x for fixed j , y , and k*; and (iii) there i s a function m ( j , k) such that
/I K ( j , x, Y , 411 < m ( j , 4 , and
on Q
x D x D x Q’. Then
the mapping T given by
1 K ( j ,u(k + 11, u ( 4 , k )
n-1
(9-6)
T ( u ) ( i )=
k=O
is a differentiable mapping of Y(Q,D) i n t o Y(Q,R,) w i t h derivative
+ aY
( j , u(k
+ I), u(k), k) v(k)j
where u ( - ) is i n Y(Q,0).
* Or with ( a K / a x ) ( j , x, y , k ) continuous in y
for fixed j , x, and k .
90
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Proof. It is obvious that the mappings T and T,' carry Y(Q,D) into Y ( Q ,I?!,). Now let u(.)be an element of Y(Q,0)and let w(.)be O 1, any element of Y(Q,R,) with the segment u(-) Ow(.), 0 in Y(Q,0). Then
+
".P I1 T(u I
+ w)(j)
-
< <
W ( j ) - (L'4(j)ll
where
and #.Aj,k , 44) =-
I: ~
-
+ 1) + w(k + 11, UP),k ) aK -- ( j ,u(k + l ) , u ( k ) ,k ) / 44. aY (j,
Application of the mean-value theorem and the hypothesis (iii) R, w(k)ll 2m(j, k) 11 w(k)II and leads to the estimates 11 t+hl(j, /I &,(j, k, w(k))ll 2m(j, k) I/ w(k)ll. Moreover, it follows directly 2m0', k) II w(k)II. Let II w(*)llm = from 6;;) that I/ t+h3(j,k, w(k))ll supl 11 w(Z)ll. Then /I $&, k, w(k))il/llw(.)llm 0 pointwise in k as 11 w(.)ilCn+ 0 for i = 1, 2, 3 since I( w(.)llm >, 11 w(k)ll, aK/ax and aK/ay are defined, and aK/ay is continuous in x. Since Ckm(j, k) < GO, we have
<
<
<
--j
3.9.
COMPUTATION OF DERIVATIVES: DISCRETE CASE
91
by the Lebesque dominated convergence theorem. * Thus, the lemma is established. We observe that Lemma 9.5 is entirely analogous to Lemma 8.5 and that both can be viewed as special cases of a lemma on Banach space-valued integrals. We now have the following. COROLLARY 9.9. Suppose that t h e function
satisfies t h e conditions of Lemma 9.5 and that g and h are differentiable. Then t h e mapping TJ i s differentiable and
where p(.) E Y ( Q ,0).
COROLLARY 9.11. Suppose that the functions
and
satisfy t h e conditions of Lemma 9.5 and that g and h are twice
* The measure
p on
Q' is given by p(k)
=
1 for k
E
Q and
p(+) =
0.
92
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
differentiable. Then t h e mapping TJ is twice differentiable w i t h (TmJ)’ given by (9.1 0) and ( ToJ)” given by
+
[ N o t e that, for example, FkFU(q(k l), q ( k ) , k) i s the three-entry matrix w i t h elements (aZFi/ax,ay,)(q(k l), q(k),k).]
+
\.lie can obtain estimates of the norms of the operators (ToJ)’ and ( IILJ)’’ from Corollaries (9.9) and (9.1 1). We recall first of all that if 4.)E Y ( Q ,A,,),then (9.13)
is the norm of w(*)where B = (1, 2, . . . , p } and wi(-)is the ith component of zu(*). T h e matrix norm which corresponds to (9.13) is given by (9.14)
* The
notation is the same as in Corollary 8.1 I .
3.9.
COMPUTATION OF DERIVATIVES:
DISCRETE CASE
93
where the various partial derivatives are evaluated at the proper I), y(/3),/3). values of ?(.). For example, aF,/ax, = (aF,/ax,)(@ T h e comments made in Section 8 also apply to these estimates.
+
94
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Similarly, we can obtain analogous estimates for the norm of using the fact that
(TvJ)”
llvlla
We leave this to the reader. Again to avoid repetition of cumbersome formulas, we use the simplijied notation II( TmJ)‘ , ]I( TwJ)’ , II(TQJ)’ lI(c) ll(TQJ)” Il(a) II(TQ”)”lib, and II(TmJ)” I k c ) in the sequel9
3.10.
7
7
A Lemma on Equivalence: Continuous Case
We now prove a lemma which will play a role in our treatment of Newton’s method. This lemma involves the relation between the operators T J and T3 for different boundary-compatible sets J = { V ( t ) ,M , N } and = { U(t),K , L}. We have the following. LEMMA 10.1. Let J = { V ( t ) M , , N ) and J = {U(t),K , L } be boundary-compatible sets. Let F(y, t ) be continuous i n y for each fixed t and measurable i n t for each f i x e d y w i t h IIF(y, t)ll m(t),m ( t ) integrable. Let be t h e linear manifold of absolutely continuous functions i n Y([O,I], I?,,). Let UiL be the operator given by
<
r
(10.2)
( U i L Y ) ( t )= H J ( t ) { - KY(0) - L Y ( l )
+
+ MY(0) + NY(1))
f 1GJ(t,S){U(S)Y ( 4 - V S )
Y ( 4 ) ds
f o r y(.) i n Y([O,11, RP).Then (i) U i L maps Y([O,11, R,) i n t o %‘([O, 13, I?,) and i n t o (ii) t h e operator I - U i L has a bounded linear inverse o n w i t h
r r
(10.3)*
for y ( . ) i n
(10.4)
r;
[ I - U&]-ly
r;(iii) ify(.)
=
[I - VLN]Y
i s i n V([O, I], R J , then
[ I - u;Ll-“TJ(Y)
-
UiL(Y)I
=
T3(Yh
3.10.
A LEMMA ON EQUIVALENCE: CONTINUOUS CASE
95
and (iv) under the assumptions of Corollaries 8.9 and 8.11, (10.5)
[I - U:J1 [(Ti), - UgL] = ( T i ) /
(10.6)
[I - U;J1 (T,J)”= (T,j)”
for all y(.). Proof. We note that (i) is an immediate consequence of the properties of the Green’s matrices H J and GJ.Now let Y = I - U i L . I t is clear that Y is linear and maps Y([O,11, RP)into F([O, 11, Rp) and r into As is well known [V2], Y-l will exist if only if the equation Y u = w has a unique solution u ( - ) in r for all w(.) in r. But, since Y is linear, this is equivalent to the condition that
r.
(10.7)
Y ( u )= [ I
- ULL](U)
=0
has zero as its unique solution. However, by virtue of Corollary2.7 and the definition of U i L ,(10.7) is equivalent to the linear TPBVP zi
Mu(0)
-
V(t)u = [U(t)- V(t)]u,
+ Nu(1) = [ M
-
K ] u(0)
+ [ N -Ll
u(1)
which can be written as (10.8)
zi = U(t)u,
Ku(0) + L u ( l )
= 0.
Since { U(t),K , L} is a boundary-compatible set, it follows that u ( . ) = 0 and hence that Y-l exists on r. T o determine the form of Y-l, we note that Y u = w is equivalent to the equation w = u - q where q = UiL(u)is a solution of the linear TPBVP
Since u - w TPBVP
=
q, it follows that u
[zi - 2.4
K[u(O)- w(O)]
~
-
w is a solution of the linear
U(t)[u- w ] = [up)- V(t)]w,
+L [ u ( l )
-
w(l)]
=
[ M - KI w(0)
+ [N
-
LI w(1)
96
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
and hence by Corollary 2.7, that (10.10)
u(t)
-
W(t) =
-
HJ(t){[K- MI w(0) -k [L - N ] w(1))
1:
GJ(t,s){ V ( S )W(S)
-
U ( S ~) ( s ) )ds
or, equivalently, that (10.1 I )
u
7
[Z
Vi&](w).
-
Since Y u w, we have established (10.3) and since [ I - VLN]is linear and bounded, Y-l is linear and bounded. T h e proof of (10.4), (10.5), and (10.6) is now rather simple. T h e basis for these relations is the equivalence between the integral equation Y u = w and the linear TPBVP for u - w , i.e., the linear TPRVP :
(10.12)
zi
Ku(0)
-
U(t)u = w
+ Lu(1)
-
-
V(t)w,
Mw(0)
+ Nw(1).
In order to prove (10.4), let y ( . ) be an element of V([O,I], R,) and let w(.)= T J ( y ) U",,(y). T h e n ~
(10.13)
s1
~ ( t=) fIJ(t){c - s ( Y ( O ) )
-I
-
+ KY(0) + L Y ( l ) )
h(Y(l))
GJ(t,s){F(y(s),4
-
W ) Y ( S ) )ds
and, by Corollary 2.7, w Mw(0)
If
ZL =
-
V ( t ) w= F ( y ( t ) ,t )
+ NZO(1)
=c
-
-
g(y(0))
U(t)y, -
h(y(1))-t KY(0)
+ LY(1).
Y - l w , then it follows from (10.12) that 2i
-
KU(0)
U(t)u = F ( y ( t ) ,t )
+L U ( l )
and hence, that u
is established.
=c -
-
U(t)y,
g(y(0)) h ( Y ( l ) )-k KY(0) -
+ LYU)
T'(y) by virtue of Corollary 2.7. Thus, (10.4)
Equations (10.5) and (10.6) are established in a similar way. We shall treat (10.5) and shall leave (10.6) to the reader. I n order to
3.11.
A LEMMA ON EQUIVALENCE: DISCRETE CASE
97
by virtue of Corollary 8.9. It follows that w( ) is a solution of the linear TPBVP ZiJ -
If
u = Y-lw,
;[
V ( t ) w=
1
( y ( t ) ,t ) - U ( t ) u,
-
then it follows from (10.12) that
fi - U(t)u =
;[
-( y ( t ) ,
t)
-
1
U ( t ) u,
and hence, that u = (TUJ)'uby virtue of Corollary 2.7. Lemma 10.1 is essentially a confirmation of the fact that for every boundary-compatible set there is a (possibly) different integral representation of the same TPBVP and that these representations are equivalent, with the equivalence given by (10.4). 3.11.
A L e mma on Equivalence: Discrete Case
We now prove a lemma, which is entirely analogous to Lemma 10.1, for the discrete case. We have the following. LEMMA 11.1.
J be
Let
m,M , N )
={A(j),
boundary-compatible
sets.
and
I = {W),w, K,L)
Let F ( x , y , k)
be
defined
on
98
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
+ [W)
-
B(k)IY(k))
for y ( - ) in Y(Q,R,) with Q = (0, 1 , . . . , p). Then (i) U i L maps 9(Q, R,J into Y(Q,R,); (ii) the operator I - U;, has a bounded linear inverse with
( 1 I .3)*
[I -
u;E,1-5 = [I - ~ JM N l Y
for y ( . ) in Y(Q,R J ; (iii) if y ( - ) is in Y(Q, Rp),then (11.4)
[ I - u;l-,l-“TJ(y)
-
UA(Y)l = T J ( y ) ;
and (iv) under t h e assumptions of Corollaries 9.9 and 9.11,
(1 1.5)
[I -
u;,]-’ [(T,J)’
-
(11.6)
U&]
= (T,J)’
[ I - U;J1 ( T i ) ”= (T,J)”
for all y ( . ) . Proof. Assertion (i) is obvious. Now let Y = I - U i L . I t is clear that Y maps Y(Q,R.) into itself and that Y is linear. Again, Y-l will exist if and only if Y u = w has a unique solution for all Since Y is linear, this is equivalent to the condition that ~
(11.7)
9%
=
J [ I - U,,].
(
9
)
.
=0
has zero as its unique solution. However, by virtue of Theorem 5.1
3.11.
A LEMMA ON EQUIVALENCE: DISCRETE CASE
and the definition of l&, (11.8)
.(j
+ 1)
Ku(0)
+
(11.7) is equivalent to the linear TPBVP
u ( j ) = C ( j )u ( j Lu(q) = 0.
-
99
+ 1 ) + W j )u ( j ) ,
Since {C(j),D ( j ) ,K , L} is a boundary compatible set, it follows that u(.)= 0 and hence, that Y-l exists. T o determine the form of Y-l, we note that, when written out, Y u = w becomes
(1 1.9)
+
~ ( j=) ~ ( j-) f f J ( j ) { [ M- K] ~ ( 0 ) [ N - L] u(q))
After some rearrangement and addition, this TPBVP can be written as
It follows from Corollary 3.8 that the solution of this TPBVP is given by (11.10)
u(j)- w(j) = ffJ(j){[M - KI 4 0 )
+"
~
LI 4 q ) )
100
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
or, equivalcntly, that (1 1.1 1 )
u =
[ I - VL,](w)
Since Y u = w , we have established ( I 1.3) and since [I - VLN]is linear and bounded, Y-l is linear and bounded. Now the proof of (1 1.4) (1 1.5), and ( 1 1.6) becomes rather simple. T h e basis for these relations is the equivalence between the operator equation Y u = w and the linear TPBVP for u - w , i.e., the linear TPBVP (11.12)
u(j
+ 1)
~
=w(j
KU(0)
If
ZL
~
u(j)
~
C ( j ) u ( j4-1)
-
O(j)u(j)
4-1) - w ( j ) - A ( j )w ( j -1-
+ Lu(q) = Mw(0) + Nw(q).
1)
Y - l w , then it follows from ( 1 1.12) that
and hence that u
~
T'(y). Thus, ( 1 1.4) holds.
-
B ( j )w ( j )
3.11.
A LEMMA O N EQUIVALENCE: DISCRETE CASE
101
Equations (1 1.5) and (11.6) are established in an entirely similar way. We treat (1 1.5) and we leave (1 1.6) to the reader. In order to prove (1 1.5), let y(.) and u(.) be elements of 9 ( Q ,Rp)and set w(.)= [(TVJ)’u- U;iZu].Then, using (9.10), (11.14)
w(j)=HJ(j)
K-$(y(O))]v(O)
102
3.
REPRESENTATION OF BOUNDARY VALUE PROBLEMS
Just as in the continuous case, the lemma is nothing more than a confirmation of the fact that for every boundary-compatible set there is a different summation representation of the same TPBVP and that these representations are equivalent, with the equivalence given by ( 11.4).
Appendix.
Lipschitz Norms
Consider the TPBVP
and let J = {V(t),M , N } be a boundary-compatible set. Assuming that the conditions of Theorem 4.1 are satisfied, we can define a mapping TJof V([O,11, R,) into itself by setting
for ?(-) in %([O, 11, R,]). We computed the Frechet derivatives of the operator T J and estimates of the norms of these derivatives in Section 8. Here, under somewhat weaker smoothness conditions, we shall compute the Lipschitz norm of the operator TJ. We begin with the following.
LEMMA A.3. Let S be a bounded open set i n Y([O,11, R p ) and l e t D be an open s e t in Rp containing t h e range of S. Suppose that (i) K ( t , y , s) i s a map of [0, 11 x D x [0, I] i n t o D which is measurable i n s for each fixed y and t and continuous i n y for each fixed s and t ; (ii) t h e r e i s an integrable function m(t, s) o f s with supl m(t, s) ds = p ,. co such that 11 K ( t , y , s)ll m(t, s) and I1 K(t,yl , s) - W t , y z, ~ ) l l m(t, s)ll y 1 - y z /I on [O, 11 x D x [O, 11; and (iii) lim,,,, I/ K ( t ,y(s),s) - K(t’,y(s),s)li ds = 0 for all t, t’ i n [0, 11 and y ( . ) i n S. Then the mapping T given by
Jt
Ji
<
<
APPENDIX. LIPSCHITZ NORMS
maps %([O, 11, 0) i n t o V([O, I], Rp)and the Lipschitz norm,
satisfies t h e inequality
103
0 T us,
ci TOsGCL.
(A4
Proof. We first observe that T maps V([O, 11, 0 )into q ( [ O , 11, R,) in view of (i) and (iii) [BO]. Now let and v(.) be elements of S. T he n .(a)
II T(u)(t)- T(.)(t)ll
<
s1
It follows that 11 T ( u ) - T(v)lI
COROLLARY A.6.
0
I1 K(t, ~ ( s ) ,s)
< p I/ u
-
v
- K(t, ~ ( s ) ,s)ll ds
11 and hence that
Suppose that the function
q 4Y ,4
=
GJ(t,S){F(Y,4
-
JWY)
satisfies the conditions of Lemma A.3 and that
T h e estimate of Corollary A.6 can often be used in connection with the contraction mapping method. Similar results can be obtained in the discrete case and we leave this to the reader.
CHAPTER 4
APPLICATION TO CONTROL PROBLEMS
4.1.
Introduction
IYe discussed iterative methods for the solution of operator equations in Chapter 2 and we showed how TPBVP’s can be represented by such operator equations in Chapter 3. Here, we shall combine the results of these chapters to obtain convergence theorems for thc iterative solution of TPBVP’s of the type that arise in optimal control problems. \Ve begin with a brief discussion of the way in which optimal control problems can be reduced to TPBVP’s. Continuous control problems are treated in Section 4.2 and discrete control problems are treated in Section 4.4. We then consider the application of the results of Chapters 2 and 3 to these TPBVP’s in Sections 4.5-4.1 1. I n the last section, we summarize the results obtained.
4.2.
Continuous Control Problems
An optimal control problem is a composite concept consisting of four basic elements: (1) a dynamical system, (2) a set of initial states and a set of final states, (3) a set of admissible controls, and (4) a cost functional to be minimized. T h e problem consists of finding the admissible control which transfers the state of the dynamical system from the set of initial states to the set of final states and, in so doing, minimizes the cost functional. I n this section we discuss the way in which optimal control problems may be reduced to TPBVP’s by means of Pontryagin’s principle [P3]. Our discussion will be brief and the details of the theory will be omitted. 104
4.2.
CONTINUOUS CONTROL PROBLEMS
105
DEFINITION 2.1. A n optimal control problem i s the composite concept consisting o f (i) a dynamical system (2.2)
fc
= f(x, 11,
t)
where x is an n vector, called t h e state, and u(t) i s an m vector, called t h e control; (ii) a s e t Soof initial states and a set S, of final states with
(2.3)
so = {(x, t ) : gi(x,t ) = ci ,
i
=
1, . . . , k }
S, = {(x, t ) : h 3 ( x ,t ) = d j ,
j
=
1,
. . . , I}
where both So and S, are smooth manifolds; (iii) a set U of admissible controls w i t h U CL,(R, Q) where Q i s a subset of R, ; (iv) a cost functional
where G, K , L are real-valued functions; and (v) t h e statement, “determine t h e admissible control u(-) which transfers the state of t h e dynamical system from So t o S, and which, in so doing, A solution u*(.) of the optimal minimizes the cost functional I(-).’’ control problem i s called an optimal control.
A common approach to the solution of optimal control problems consists of the following steps: (1) the determination of necessary conditions for optimality; (2) the determination of functions (extremals) which satisfy these necessary conditions and thus qualify as candidates for the solution; and ( 3 ) the determination of those (if any) extremals which are optimal. Necessary conditions for optimality have been derived in a number of ways [B4, CO, H4, N3]. I n general, the derivation involves the assumption of an optimal solution followed by an investigation of the effects of suitable variations. T h e resulting conditions for optimality lead to a TPBVP as we shall see. Let us now suppose that (i) f(x, u, t ) , (af/at)(x,u, t ) , (af/ax)(x,u, t ) , L ( x , u, t ) , (aF/at)(x,u, t ) , and (aL/ax)(x,u, t ) are continuous on R, x 0 x R ; and (ii) G(x, t ) , (aG/at)(x,t ) , (aG/ax)(x, t ) , K ( x , t ) , ( a K / a t ) ( x t, ) , and (aK/ax)(x,t ) are continuous on (neighborhoods of) So and S , , respectively. In that case, we call the control problem smooth. We shall assume from now on that the term “control problem” means “smooth control problem.” We now have the following.
106
4.
APPLICATION TO CONTROL PROBLEMS
DEFINITION 2.5.
The
real-valued function
H ( x , p, u, p , , t )
given by
i s called t h e Hamiltonian of t h e (given) control problem.
THEOREM 2.7 (The Pontryagin principle [P3]). Let u*(-) be an admissible control which transfers t h e state of t h e dynamical system (2.2) from So t o S, and let x*(.) be the corresponding trajectory. Suppose that u*(.)is optimal. Then t h e r e are a vectorvalued function p*(*),a vector a i n R,, a vector p in R l , and a number pO* 3 0 such that t h e following conditions are satisfied: (a)
(p,*,
p*(t)) i s not identically zero;
(b) x*(t) and po*, p*(t) satisfy t h e canonical system of differential equations, i.e.,
(2.8)
aH k*( t ) = -aP
(X*(t)? P*(t), u*(t),P O * ,
t)
= f(x*(t),u*(t),t)
(2.9)
(c)
I;*(t) ==
aH ax (x*(t),P*(t), u*(+
- --
PO*,
t)
x*(.) and po*, p*(-)satisfy t h e boundary conditions
(2.1 1 )
where g, h,c , d are vectors with components g i , h,, c i , and d j , respectively;
4.2. (d)
i.e.,
u*(t) minimizes the Hamiltonian over 9 for (almost) all t,
(2.12)
for all
(4
107
CONTINUOUS CONTROL PROBLEMS
H ( x * ( t ) ,P*(% u*(t),P O * , t ) w
< H(x*(t),P*(t), w,
in 9; and
H*(to) = Po*(aG;/at)(x*(tO), to)
PO*,
+ <(ag/at>(x*(to),to),
= - po*(aK/at>(x*(t,), t f ) - ((ah/at)(x*(tr),ti), f f * ( t ) = H ( x * ( t ) ,P*(t), u*(t),po*, t).
H*(t,)
t)
P>
and where
a>
A proof of Theorem 2.7 is given by Pontryagin et al. [P3]. We now make some comments regarding Theorem 2.7. We first observe that the adjoint equation (2.9) is linear in p*(t) and has a forcing function and boundary conditions proportional to po*. Therefore, the constant po* can be regarded as a scale factor for the adjoint functions. I n theoretical work (if po* # 0) this scale factor is usually assigned the value po* = 1. I n numerical work it may be preferable to carry po* along as a scale factor. We next note that in [P3] po* was chosen nonpositive, rather than nonnegative. With this choice, the Hamiltonian has the opposite sign and, instead of a minimum, has a maximum at the optimal control. Not counting the scale factor po* or the function H*(t), which is fully defined by H * ( t ) = H(x*(t),P*(t), U*(t),
+
PO*,
q,
we have 2n m functions of time to determine; namely, x*(t),p*(t) and u*(t) and two values of the time, to and ti . T o solve for these, we have 2n first-order differential equations, (2.8) and (2.9) with k ( n - k) 1 (n - I) = 2n boundary conditions (assuming the elimination of u and p), rn scalar equations resulting from (2.12) and finally, two equations involving to and ti . Hence, there are enough equations, in theory, to solve for x*(t),p*(t), and u * ( t ) . We can also readily see that the boundary conditions include terminal sets which are fixed points and the case where the terminal state is free. In the case of fixed end points, we have (for example), g(x(to),to) = x(to)= c and h(x(t,), tr) = x(tr) = d. I n this case, there will be no cost functional terms G and K and so p*(to)= u, p*(t,) = p which implies that the values of the adjoint function p*(.) are free at the end points. ) satisfies (a)-(.) Now, Let us call any triple (x(t),p(t), ~ ( t )which of Theorem 2.7, an extremal of the control problem. Since any
+
+ +
I08
4.
APPLICATION TO CONTROL PROBLEMS
optimal control gives rise to an extremal, one frequently used approach to the solution of control problems is to determine all extremals. As is apparent from Theorem 2.7, this involves the simultaneous solution of 2n differential equations, m minimization equations, and 2 algebraic equations. I n general, this is a sizable problem. We examine some aspects of this problem in the remainder of this section. T h e only analytical progress toward the determination of the extremals that usually can be made is the reduction of the set of 2n rn 2 equations to a set of 2n differential and 2 algebraic equations. This reduction is effected by solving the minimization equation (2.12) for the optimal control ut in terms of x, p, and t , i.e.,
+ +
(2.13)
u
= uyx, p,
t).
This reduction is possible if the Hamiltonian is normal [A3]. Substitution of (2.13) into the differential equations (2.8) and (2.9) makes the problem of the determination of the extremals into a nonlinear two-point boundary value problem of the form
with the boundary conditions (2.10) and (2.1 1). For theoretical as well as practical (numerical) reasons, it is often advantageous to standardize the time interval over which the TPBVP (2.14), (2.15) is defined. This standardization is accomplished by the introduction of a new variable. Let (see Long [L2]) (2.16)
t
-
to
+
( f f
-
t,)s
=b
+ as.
Ilere s is the new variable which varies between 0 and 1 ; a (scale factor) and h (initial time) are two generally unknown constants. These constants a and 11 can conveniently be considered as new state variables given by the trivial equations (2.17) I
For simplicity we drop the asterisk (*) for the “optimal” values.
4.2.
CONTINUOUS CONTROL PROBLEMS
109
I n terms of s, a, and b, the TPBVP becomes
(2.18) = 0,
+ +
db -= o ds
+
where H(s) = poL(x,p, b as) (p, +(x,p, b as)). Since the sets Soand S, are smooth manifolds, it is possible (at least in theory) to eliminate the unknown constants a and p in (2.19). Assuming that this has been done and letting (2.20) (2.21) (2.22) (2.23) (2.24)
where (2.19) is replaced by the conditions g(x(O),p(O), 6) = e, h(x(l),p(l), a b) = d, we see that the TPBVP can be written in the standard form
+
I10
4.
APPLICATION TO CONTROL PROBLEMS
We shall apply the results of Chapters 2 and 3 to the TPBVP (2.25) in the sequel.
4.3.
A Continuous Example
Consider the scalar control system
with state variable x and control variable u. Let x(0) = x, and x( 1) = x1 be the initial and final states, respectively. Let U = L,([O, I], R) be the set of admissible controls and let the cost functional J(u) be given by
I(.)
= $ J1 U"T)
n
dT.
T h c control problem can now be stated as follows: determine a u(.) in U which transfers the state of (3.1) from x, to x1 and, at the same time, minimizes (3.2). 'The extremals of this optimal control problem are found with the aid of Pontryagin's principle. T h e first step is the formation of the Hamiltonian (3.3)
H ( x , p , u , pa) = 4pau2
+ pbu
-
PEZ / X
.
T h c corresponding canonical equations (2.8), (2.9) then have the form
(3.4) (3.5)
p = - - =8H +
E
ax
1 -=p. 2dx
Nest, the Hamilton is minimized with respect to u. Since H ( x , p , u, p,) is a parabola in zc and since u is unconstrained, it follows that H(x, p , 21, p,) has (for p,, # 0) an absolute minimum at (3.6)
u"(.,p)
=
-
1
-bp.
Po
4.3.
111
A CONTINUOUS EXAMPLE
Substitution of (3.6) into (3.4) and (3.5) yields a TPBVP given by
X=--P-
(3.7)
Po
with the boundary conditions (3.9)
x(0)
= xo,
x(1)
= x1
I n standard form this TPBVP (see Section 6 of Chapter 3) can be written as
(3.10)
T h e resulting TPBVP is so simple that an analytical solution can be found. T h e two first-order differential equations are converted into a single second-order equation by differentiating the first equation and substituting the second into the result. This yields
yl=-<-
(3.1 1)
1 -yl. -b - E2 -yz.1 2 dYl Po 2 d Y 1
I n view of the first equation b2
(3.12)
- -yz
Po
=yl
+
E
4%.
Hence, by substitution of (3.12) into (3.11) (3.13)
y,
1 =
€--
2
dY1
[j,
+ dZ] E
-E -
1 dxYl
€2
=
2
*
4.
112
APPLICATION TO CONTROL PROBLEMS
+
+
‘The solution of (3.13) is of the form y l ( t ) = (e2/4)t2 C,t C, and the constants C, and C, are derived from the boundary conditions yl(0) C, .yo , yl( 1 ) = (2/4) C, C, = x1 . This example illustrates the n a y in which TPBVP’s arise in control problems. =
4.4.
+ +
~
Discrete Control Problems
JYe now examine the way in which discrete optimal control problems may be reduced to ‘L’PRVP’sby means of the discrete maximum principle [CO, H4].
DEFINITION 4.1. A discrete o p ti m a l c o n t r o l p r o b l e m is t h e composite concept consisting of (i) a discrete dynamical system (4.2) x ( j
+ 1)
~
x(j) = f(x(j),u ( j ) , j ) ,
j E
Q‘ = (0, 1 , . . . , q
-
11
w h e r e x(j) is an n vector, called t h e state, and u(j) i s an m vector, called t h e c o n t r o l ; (ii) a set S,, of i n i ti a l states and a set S, of final states with
(4.3)
S”
S,
~~
{x: gz(x)= c, ,
= {x:
h,(x)
=
d,,
i
=
i
-
1, . . . , k } 1,.
..,I]
w h e r e both S o and S, are s m o o th manifolds; (iii) a set U of admissible c ontro l s with U C Y(Q’, Q) w h e r e Q i s a subset of R,, ; (iv) a cost functional
+ c 4 ” ( j )U?( j ) ? i ) 9-1
(4.4)
l ( u ( . )= ) K(X”(d)
3-0
wher e K and I, are real valued; and (v) t h e statement, “determi ne an admissible c o n t r o l u(.)w h i c h transfers t h e state of t h e dynamical system f r o m S, t o S, and which, i n so doing, minimizes t h e cost functional A s o l u ti o n sequence {u*(O),. . . , u*(g - 1)) is called an opt im a l c o n t r o l sequence.
I(.).”
1,et us now suppose that (i) f ( . , w , j ) , (af/ax)(-,w , j ) , L ( - ,w , j ) , and (hI,/tx)(.,w, j ) are continuous for all w in Q and all j ; (ii) K(x) and (?K/?x)(x) are continuous on (a neighborhood of) S, ; and (iii) the sets {(L(x,w, j ) , f(x, w , j ) ) : w EQ} are convex subsets of for
4.4.
113
DISCRETE CONTROL PROBLEMS
every x in Rn a n d j in Q'. In that case, we call the discrete control problem smooth. We suppose from now on that our discrete control problems are smooth. We now have the following. The real-valued function H ( x , p,u,po, j ) given
DEFINITION 4.5. by
H(x, p, u, Po , j )
(4.6)
= POL(X, u , j ) t- (P,
f(x, U , d >
i s called t h e Hamiltonian of t h e c o n t r o l problem.
THEOREM 4.7 (The Discrete Pontryagin Principle [CO, H31). If {u*(j)} is an optimal c o n t r o l sequence w i t h {x*(j)} as corresponding optimal trajectory, t h e n t h e r e are vectorsp*(O), . . . , p*(q) i n R,, a i n R,, p i n R , , and a number p,* 3 0 such t h a t t h e
following conditions are satisfied :
po*, p*(O), . . . ,p*(q), a, P are n o t all zero; (b) x*(j)and po*, p*(j) satisfy t h e canonical system of difference (a)
equations, i.e.,
x*(j
(4.8)
+ 1)
-
aH x*(j) = -(x*(j),P*(j), aP
U*(j),
Po*,j)
= f(x*(j),u*(j),i)
(4.9)
p*(j
+ 1)
-
P*(j) = =
aH
-
5; (x*(j),P * ( h u * mP"*,i) i3L
-Po*
ax
(x*(j),u * ( j ) , j )
-
af ax (x*(j),u*(i),j)'p*(j
--
forj
=
(c)
0, 1 , . . . , q
-
+ 1)
1;
x*(.) and po*, p*(.) satisfy t h e boundary conditions
(4.10)
g(x*(O)) = C,
(4.11)
h(x(d) = 4
p*(O) =
P*(d
- --
= PO*
ax
aK
(x*(o))a (x*(q))
ah + ax (x*(d) P
I14
4.
APPLICATION TO CONTROL PROBLEMS
where g, h, c , and d are vectors with components g, and d,, , respectively; and (d)
, h,,
ci ,
u * ( j ) minimizes t h e Hamiltonian over Q at j , i.e.,
f o r all w i n Q.
X proof of Theorem 4.7 is given by Canon et al. [CO]. If we call any triple (x(j),p(j),u(j))satisfying (a)-(d) of Theorem 4.7 an extremal of the control problem, then, just as in the continuous case, we attempt to determine all extremals. This leads to a TPBVP for a set of difference equations. More precisely, if the Hamiltonian is normal [A2], then the minimization equation (4.12) can be solved for u in terms of x,p, a n d j , i.e.,
Substitution of this expression into the canonical equations results in a system of difference equations of the form
with the boundary conditions (4.10) and (4.11). Since the sets So and S, are smooth manifolds, it is possible (at least in theory) to eliminate the unknown constants u and p from the n k conditions (4.10) and the n 1 conditions (4.I I), respectively. Assuming that this has been done and letting
+
+
(4.16) (4.17)
(4.18) (4.19) (4.20)
where (4.10)and (4.1 1 ) are replaced by the conditions g(x(0),p(0)) = e
4.5.
115
THE METHOD OF CONTRACTION MAPPINGS
and h(x(q),p(q)) = d, respectively, we can see that the TPBVP can be written in the standard form (4.21)
Y(i
+ 1) -YW
=F(y(j
+ l ) , Y ( j ) > i ) > d Y ( 0 ) )+ h(y(q))
= c.
We apply the results of Chapters 2 and 3 to the TPBVP (4.21) in the sequel.
4.5.
Application t o Continuous Problems I: The Method of Contraction Mappings
We have seen that if the conditions of Theorem 4.1 of Chapter 3 are satisfied, then TPBVP’s, such as (2.25), are equivalent to operator equations of the form (see Section 8.3 in Chapter 3) (5.1)
Y ( t ) = TJ(Y)(t)= HJ(t){c- d Y ( O ) )
-
h ( Y ( l ) )-1 MY@)
+ NY(1))
+ J’GJ(t,s){F(y(s),4 - W Y ( S ) )ds where = {V(t),M , N } is a boundary-compatible set. We shall apply the iterative methods of Chapter 2 to (5.1). Let us begin with the method of contraction mappings. Following the prescription (formally), we select an initial element y o ( * ) in %‘([O, I], R,,)and successively generate a C M sequence {y,(.)) for TJ based on y o ( * )by means of the algorithm yntl = TJ(y,), or, equivalently, by
4.
116
APPLICATION TO CONTROL PROBLEMS
But (5.3) is the solution of the linear TPBVP (5.4)
Yn+l
-_
1 y t ) Yn I1 -tJn(t),
+ NYn+dl)
MYn+1(0)
= GI
Thus, the method of contraction mappings when applied to (5.1) essentially amounts to the successive solution of the linear TPBVP’s (5.5). This is frequently referred to as Picard’s method. We now have the following.
DEFINITION 5.6. (5.7)
The TPBVP
Y = F ( Y , I),
+
‘ d Y ( 0 ) ) h ( Y ( l ) )=
c
is differentiable o n a subset S of V([O,11, R,) if (i) t h e r e i s a boundary-compatible set J = { V ( t ) ,M , N } such that t h e function K ( t ,y , s) = GJ(t,s ) { F ( y ,s) - V(s)y} satisfies t h e conditions of Lemma 8.5 of Chapter 3 on an open s e t D i n R, w i t h t h e range of S contained in D,and (ii)g and h are differentiable. Similarly, t h e TPBVP (5.7) is twice differentiable on S if b o t h K ( t , y ,s) and
( a K / ? y ) ( ty, , s) satisfy t h e conditions of Lemma 8.5 of Chapter 3 and if g and h are twice differentiable. THEOREM 5.8. Let yo(.) be an element of V([O, I], R,) and l e t S = S ( y , , Y). Suppose that (i) J = { V ( t ) ,M , N } i s a boundarycompatible set for which (5.7) i s differentiable on S, and (ii) t h e r e are real numbers 7 and (Y w i t h 7 3 0 and 0 a << 1 such that
<
(5.10)*
(5.1 1 )
* Scc Section 8 of Chapter 3 and note that the theorem remains true if 11 (TvJ)’Ij(a) is replaced b y 11 ( T i ) ’110,) or I1 ( T i ) ’II(?) .
4.5.
117
THE METHOD OF CONTRACTION MAPPINGS
Then t h e C M sequence {y,(.)} f o r t h e TPBVP based on yo and J converges uniformly t o t h e unique solution y*(.) of (5.7) in S and the rate o f convergence i s given by
(5.12)
I/ Y*(.)
- Yn(.)ll
< la I/Yd.1 0111
- Yo(.)II *
Proof. Simply apply Chapter 2, Corollary 2.10 and the estimates of Chapter 3, Section 8. Similarly, we can translate Corollary 2.34 of Chapter 2 to obtain the following. THEOREM 5.13. Suppose that (i) J = {V(t),M , N } i s a boundary-compatible set f o r which (5.7) i s twice differentiable o n s, and (ii) there are real numbers 7, 6, and K w i t h 7 3 0 , 0 6 < 1, and K 3 0 such that
<
(5.14)*
II TJ(Yll)- Yo I! < 79
ll(Go)’ll(a)
<s
(5.15)* and
(5.16)
1-dl-2h h
1
7
-s
~~< 1 + d l - 2 h h
1
7
-s
<
where h = [K7/(1 g. Then t h e C M sequence {y,(-)}for t h e TPBVP based o n y o and J converges uniformly t o the unique solution y * ( * )of (5.7) i n S and the rate of convergence i s given by
x II Yd.1
- Yo(-)ll
.
From Theorems 5.8 and 5.13 we can deduce some guidelines for the choice of the initial guess yo( and the set of boundary-compatible matrices V ( t ) ,M , and N . Before we do so, however, we should sound a word of caution with respect to the interpretation of the conditions given by these two theorems. Both theorems only involve sufficient a)
*Again, the theorem remains true if I1 (TiJ’ll(a) is replaced by I/ (TiJ’ll(b) II (TiJ’ I/(c) or if 11 (TgJ)” ha)is replaced by II (T,J)”ll(b) or ll ( T / ) ”/I(c) .
or
118
4.
APPLICATION TO CONTROL PROBLEMS
conditions. If the conditions are satisfied, then the convergence of the corresponding C M sequence is guaranteed. I n many practical cases, however, the C M sequences will converge while the conditions are not satisfied. Therefore, our conclusions as regards convergence drawn from these conditions should be viewed practically as guidelines rather than strict rules. T h e only explicit requirement for the choice of the initial guess yo(.) is the stipulation that y o ( - )be a continuous p-vector function defined on [0, 11 (or: y o ( *E) V([O, 11, R p ) ) . Implicitly, however, the conditions on the norm of the first step 7,which is strongly dependent on the choice of yo( limit the choice of yo(.) considerably. Assuming that the second Frechet derivative of TJ does not vary much over the sphere S, it follows that the convergence constants (or contraction factors) 01 and h are roughly proportional to 7 . Hence, the smaller 7, the better ( i s . , faster) the convergence. T h e best choice for the initial guess yo(.) is therefore the trajectory which according to the available data is as close (in the sense of the norm) to the actual solution y * ( - ) of the TPHVP as possible. T h e first approximate solution yl(-) will then be close to y*(.) and hence also close to the initial guess. T h e norm of the difference 11 y 1 - y o I/ will then be small. If the initial guess yo(.) is chosen farther away, then 7 will increase and so too will 01 and 11. If yo(.) is chosen too far from y * ( * ) then , a point may be reached where the convergence of the CM sequence is no longer guaranteed by the theorems. T h e convergence conditions given in Theorems 5.8 and 5.13 are, when combined with the estimates (8.17) and (8.18) of Chapter 3, rather explicit with respect to the choice of J . For example, a small convergence factor a will be obtained if supy,s {Il(aF/ay)(y(.), .) - V(.)l\} and SUP ?/ES{illM - (ag/aY)(Y(o))ll II N - ( ~ ~ / ~ Y ) ( Y ( l ) )are l l l small. l I n essence, conditions on the norm of the operator TJ are translated into conditions on the norms of F and its derivatives and on the norms of V ( t ) ,M , and N . If the boundary conditions are linear, then M and N should be chosen “close” to the constant matrices ag/ay and ahlay. I n the control problem case, it may usually be assumed that [ag/ay,ahjay] has maximum rank and so, by Lemma 2.13 of Chapter 2, that a boundary-compatible set can be chosen of the form { V ( t ) ,ag/ay, ahlay}. Under such circumstances, the estimates of derivatives involve only V ( t ) and F ( y , t ) . In a similar vein, it is often effective to choose V ( t ) close to (6F/3y)(yo(t), t). a ) ,
+
4.5.
THE METHOD OF CONTRACTION MAPPINGS
119
We conclude this section with two simple illustrative examples. EXAMPLE 5.18 (Picard). Consider [P2] the TPBVP 2 =f(x,i,t), x(0) = a, x(1) = b which can be written in the standard form
a b
We use the boundary-compatible set (5.20)
V ( t )=
M =
01, 0 0
and we choose as initial guess
r Y"(t) =
1
a
+ (b - a)t b-a
We further assume that there are two real numbers pl such that
0 and pLz 0
for y, j : in some sphere s ( y , , r ) around yo(t). Thus, we have enough data to determine the convergence conditions for Picard's method. In order to determine a value for 01 as defined in Theorem 5.8, we let P(t) = ( p i j ( t ) )be a matrix with entries
and
z = (zi)be a vector with entries
(5.23)
120 where
4.
APPLICATION TO CONTROL PROBLEMS
s = s(y,,
T).
Then,
Now the Green’s matrix is given by
and so (5.25)
P(t) =
2(t
;( t t 2 ) ;- ( t - t 2 )
t2)
~
~
1
I
Assuming that f is differentiable and using the mean value theorem and (5.21), we deduce that (5.26)
z=[
O
and hence that II( T:?/))’(I(c) condition 01 < 1 becomes
]
+ = I-p1 + *pa < a. Thus, the convergence P1
P2
Condition (5.27) is more stringent than the condition given by Picard [P2] (5.28)
;PI
+
4P2
< 1.
T h e reason for the difference between (5.27) and (5.28) lies in the choice of the norm. We investigate this in some detail: both convergence conditions (5.27) and (5.28) are expressions of the requirement that for convergence of the contraction mapping method the
4.5.
T HE METHOD OF CONTRACTION MAPPINGS
121
contraction factor should be smaller than 1. T o determine this contraction factor the norm of the difference of two images of arbitrary elements in the sphere S ( y O , r )is compared with the norm of the difference between the elements. Calling T J ( y )= u
and
T J ( y )= E
( y , y E S ( y o ,Y)),
this amounts to a comparison of the norms of the differences
For the suprema (over t E [0, I]) of the absolute values of these differences we have, in view of (5.21) and (5.25),
and SUP ds
If we choose the uniform norm defined by
II 4.l = te[O,l] SUP SUP{I w,(t>l> itP then, the Lipschitz norm
= SUP{SUP I 4 t ) l
0 TJus is given by
> SUP
Iw>
122
4.
APPLICATION TO CONTROL PROBLEMS
and we obtain our earlier result (5.27)
On the other hand, if we use the special problem oriented norm
then
which is precisely the result of Picard (5.28). I t should be noted that a problem oriented norm of the type (5.29) is feasible, in case the TPBVP is given in the form of an nth order ordinary differential equation. I n cases where the TPBVP is given by a general set of first-order differential equations, this type of norm will seldom be feasiblc.
EXAMPLE 5.30. I n this rather long example we discuss in detail the application of Picard's method to the nonlinear TPBVP considered in Section 3. First, we formally apply Picard's method to the problem and evaluate the first three approximate solutions. We compare these approximations with each other and with the exact solution (3.12) determined in Section 3. Next, having found indications of possible convergence, we determine the convergence conditions as given by both 'Theorems 5.8 and 5.13 in full detail for an assumed set of numerical data. Finally, we compare these convergence conditions. In standard form, the TPBVP considered here has the form
4.5.
123
THE METHOD OF CONTRACTION MAPPINGS
Now we can write (5.31) in the form r
(5.32)
We deduce that a good choice for a boundary-compatible set is given by
In view of the relation (see Section 6 of Chapter 3)
we have det[M
+ NdiV(I , O)] = det =det
)[I :I [::I[; b21i
'11 +
1
~
1
b2
Hence, these matrices satisfy the conditions for boundary com-
124
4.
APPLICATION TO CONTROL PROBLEMS
patibility. A good choice for the initial guess is given by the solution of the linear problem
which corresponds to {V(t),M , N } . T h e solution of this TPBVP is easily found to be 1 (5.35) y i ( t ) = xn ($1 - .yu)t, yz(t) - (XI - xu)
+
Defining d
1
xo , e
=
x1 - xoand using superscripts (in parentheses)
to indicate the number of the iteration, we write yA’’;(t) = d y;o; -( 1 /h2))e and so, we have found our initial guess. ,I
+ et,
~
‘1’0 determine the first approximate solution y ( l ) ( t ) ,we use the algorithm (5.5), i.e., j ( l )-
l r ( t ) y ( l =) F [y‘”(t), tl
My“’(0) + N y ( l ) ( I )= c
-
v(t)Y‘n’(t)>
In view of (5.32) and (5.33), this becomes $1)
(5.36)
+ bZYp) = yP’(0) yp
-
-E
dy” = -
d d
+ et,
d 1 --yy 2 dy:“’
+€-
y ? ) ( l ) =- d
+ e.
=
-
e
2
2b2 2/ dTet’
T h e solution of this linear TPBVP can be found by straightforward integration followed by determination of the integration constants from the boundary conditions. T h e solution obtained in this way has the form 1 E y(’)(t) - d et, (5.37) y 2( 1 )( t ) = - - e ~-- dd et . b2 b2
+
~~
+
4.5.
THE METHOD OF CONTRACTION MAPPINGS
125
Following the same procedure, i.e., by solving the linear TPBVP j,?) + b’ZY(2)= 2
-E
dy:l’ = - E 4-
(5.38)
we find as second approximate solution ~ ( ~ ) ( t ) yp’(t) = d
(5.39) yp’(t) =
+ et + 4
€2 -( t 2 -
1 b
-
d- d + et
t),
€2 - --
4b2 (2t
-
1).
It is of interest to compare the differences between the successive approximate solutions. It follows immediately that y?)(t)
~
yi“’(t) = 0
yt’(t) - y f ’ ( t ) = bz d d E
-
y 1 ( t ) - y?)(t) = 4 ( t 2 (2)
y;’(t)
€2
-
+ et
-
€2
yP)(t) = 4b2 (2t
t)
-
1)
and hence for the uniform norms of the differences between the successive approximations, that
(5.40) -
€2
4b2
if
b
126
4. APPLICATION
TO CONTROL PROBLEMS
Comparison of these norms shows that if 31 ~<42/di-e
if b < 1
then the norms of the differences between the successive approximations decrease (for the first three approximations). Convergence of Picard's method becomes a distinct possibility in that case. We can also compare our approximate solutions with the exact solution determined in Section 3. This solution is given by yl*(t) = d
y2*(t) -
+ et 4--4( t 2
-
€2
1
e
-
-
t),
€2 -( 2 t -
4b2
'4+
1) - b2
d
et
+4
€2 -
(t2 - t )
Such a comparison yields
(5.42)
(n)
y E * ( t )-- y 2 ( t ) =
-
(2/d
-
d
+ et +
€2
+ et + 4
€2
-
(t2- t )
-
dd+rt)
(t2 - t )
-
dd).
Without determining the uniform norms corresponding to these
4.5.
THE METHOD OF CONTRACTION MAPPINGS
127
differences, it is already evident from inspection that (the absolute values of) the differences between the exact solution and the three first approximate solutions decrease. This points definitely towards convergence of this particular application of Picard's method. We investigate this convergence in the light of Theorems 5.8 and 5.13. Since the application of Theorems 5.8 and 5.13 is almost impossible without specific numerical values, we assume the following data: I'<
b
4 ,
=
4 dz,
d=x,=10 e
= x1
-
x,
=
15.
For these numerical values, we find from (5.40) and (5.41) that = 2.5, 11 yP) - y ( l )11 = 3.12 x and similarly that
11 y ( l ) - y(O)11
These numbers show that, at least, the first three approximations exhibit a rather rapid convergence. I n applying Theorems 5.8 and 5.13, we are most interested in the determination of the numbers 01, S, and K. Instead of trying to evaluate the defining expressions for 01, 6, and K directly, we use the same indirect procedure as in the preceding example. That is, we define a matrix P ( t ) and vectors z , z , , and x with elements (components) p i j ( t ) ,zj , xo,j, and xj given by
z j
= sup sup
Y E S t c [ O, l ]
z,,j =
sup
128
4. APPLICATION
TO CONTROL PROBLEMS
I t follows that conservative values of a, 6, and K are given by
We can readily deduce that
for
t
< s < 1.
Integration of the absolute values yields
2(t
~
1 b2
-
t2)
b2 (t 2
-
-t2)
4 - (t - t2)
Next, we deduce formally from (5.31) and (5.33) that
I-
4.5.
129
THE METHOD OF CONTRACTION MAPPINGS
It follows immediately that
In order to determine the supremum over t E [0, 11 and y ( t ) E S(y,, r ) , we must specify the sphere s ( y , , r ) . With the initial guess y(O)(t) given by 1 y f " ( t )= d et = 10 15t, yt'(t) = - --e = - 30,
+
+
b2
s(
we must assume a value for the radius r to completely specify yo , r ) . Now, following Theorem 5.8, this radius must satisfy the condition [1/(1 - a)]q r where 01 is implicitly dependent on r . T h e usual procedure to determine r for given q is to assume a value of r, evaluate 01 for this r , and then adjust the guess for r depending on the difference P / ( l - 4171 - y . As a first guess for r in the present case, we assume that r = 4. This implies that the sphere S ( y o ,r ) contains all continuous twovector functions such that
<
6
+ 15t
-
34
<
-
Hence inf inf
YES t € [ O , l ]
I yl(t)l = 6
sup sup
YES t€[O,l]
I yz(t)i = 34.
Using these extreme values, we find that
0.05 10 0.1955
26.
I30
4.
APPLICATION TO CONTROL PROBLEMS
and hence that
Hence, we may take 01
= 0.1998
< 1.
Next, we check our estimate for r. We had 11 y(l) - y(O)11 = = 2.5 so that [l/(l - a ) ] = ~ 1/(1 - 0.1998) (2.5) = 3.12 < 4. Thus, we find that the CY and 7 which we determined satisfy the main convergence conditions of Theorem 5.8 by an ample margin. If our objective is limited to a proof of convergence of the CM sequence under consideration, then we might stop at this point. (It is easily verified that the other conditions of the theorem hold.) In case we are interested in convergence rates or error bounds, however, we might try to make a smaller by making Y smaller and vice versa. For example, in the present case we might have assumed for Y the value Y = 3.05. This leads to a sphere s ( y , , Y) which contains all continuous 2-vector functions, such that 6.95 -1 1st < yl(t)
< 13.05 + 15t,
-
33.05 < ~
<
2 ( t )
-
T h e extreme values of yl(t) and y z ( t )now become inf inf
YES tE[O,Il
1 yl(t)l = 6.95,
sup sup
y e s tt[O,l]
1 y2(t)l = 33.95.
Using these extreme values, we find for the vector z
r =
8 33.05
1
G
1
-
0.0474
I
0.I604
26.05.
4.5.
THE METHOD OF CONTRACTION MAPPINGS
131
and hence, that
Therefore, we may take 01 = 0.1750 < 1. A check on the radius r now yields [l/(l - a ) ] = ~ 1/(1 - 0.1750) * (2.5) = 3.03 < 3.05. Hence, this second choice for r indeed leads to a different value of 01 which together with 7 satisfies the conditions of Theorem 5.9. The last value of 01 is considerably lower than the one obtained previously and therefore leads to faster convergence rates and sharper error bounds. I n order to compare the application of Theorem5.8 with the application of Theorem 5.13, we next determine 6 and K. In view of the definition of y(O)(*), we immediately find that
Using this estimate, we deduce that
and
II P ( * ) Z O II = "P
li
Hence, we may take 6
2(t
=
-
2
t2)
] /1
4 (t - t2) 4 - (t - t2)
0.1287
< 1.
[.0396] .0990
= 0.1287.
T o determine K , we must
132
4.
APPLICATION TO CONTROL PROBLEMS
again guess a value for the radius Y . We take Y we derive the matrices of second derivatives as
=
3.0. From (5.43)
Using the extreme values of I yl(t)i and I y2(t)l,we find that
and hence
Thus, we may take K = 0.02205. T h e main convergence factor in thcorcm (5.13) is the number h defined by h = Kq/(l - S)2. I n view of our estimates, we see that
Evidently, (5.44) implies that the convergence condition on h of
4.5.
133
THE METHOD OF CONTRACTION MAPPINGS
Theorem 5.13 is satisfied. T o check the radius r, we evaluate the expressions 1-dl-2h h
.-
7
1-8
-
1 - d1 - 0.0727 2.5 0.0727 ( I -0.1287)
-
1
= 2.98
<3
and l + d m 7 h 1 -s a--
+ dl - 0.0727 0.0727
(1
2.5 - = 76.0. 0.1287)
-
Since 2.98 < Y
=3
< 76.0.
it follows that condition (5.16) is also satisfied for our values for
6 , q , and h.
Thus, the conditions of Theorem 5.13 as regards the numbers
q, 6, K , and h are satisfied. Since, in addition, the vector functions
F [ y ( t ) ,t ] ,g[y(O)]= My(O),and h[y(O)]= Ny(0)satisfy the existence and differentiability conditions on the sphere S(y(O),r ) , it follows that Theorem 5.13 applies. T h e C M sequence based on y(O)(t),V(t), M , and N therefore converges to the unique solution y*(t) of the TPBVP. A guaranteed convergence rate for this C M sequence is given by the inequality
< [l - (1
-
0.1287) ~
‘
11 - (
-
d 1 -2(0.0727)
1
~
(2-5)
< (0.1945)” (2.98). This convergence rate is conservative when compared to the actual convergence of the first three approximate solutions.
134 4.6.
4.
APPLICATION TO CONTROL PROBLEMS
Application t o Continuous Problems II: The Modified Contraction Mapping Method
We now examine the modified contraction mapping method as applied to operator equations of the form (5.1). We recall from Section 3 of Chapter 2 that the modified contraction mapping method coincides with the contraction mapping method applied to the operator P = [I - V ] - l [ T - V ] for a suitably chosen V. We limit our discussion here to operators V = U i Lof the form given by (10.2) of Chapter 3. Therefore, let J = { V ( t ) M , , N } and = { U ( t ) ,K , L} be boundary-compatible sets. Then, it follows from Lemma 10.1 that the modified contraction mapping method when applied to the equation TJ(y ) = y with modifying operator V = U i L, is equivalent to the contraction mapping method applied to the equation TJ(y) = y . Having derived convergence conditions for the direct application of the contraction mapping method in Section 5, we focus our attention on the translation of Corollary 3.8 and Proposition 3.10 of Chapter 2. With the aid of Lemma 10.1 of Chapter 3, the translation of the relevant results of Chapter 2 poses no real problems. However, before carrying out this translation, let us consider the advantages and disadvantages of the modified contraction mapping approach. T h e crucial convergence inequality is given by
p
(6.11
sup{ll(~YES
G - l
[(C)’ UiLlIl} < -
01
< 1.
T h e first approach to this inequality is to simply note that (I
-
u ; p [(TY)’- U i L ] = (T,J)’
so that (6.1) becomes
Since this is essentially the condition (5.10), nothing new has been developed. A second approach to (6.1) is to replace the single norm by a product of two norms so that (6.3)
sup{/l(l ytS
GL-l II . ll(T,J)’
-
U i L Ill
< <1 01
becomes the relevant condition. This involves a majorization which
4.6.
THE MODIFIED CONTRACTION MAPPING METHOD
135
results in less sharp convergence conditions. However, there may be offsetting advantages. One such advantage which is often important enough to warrant the loss of accuracy is the simplicity of evaluation of the estimates. As estimates of the form (6.3) rely on maximization over Green’s matrices corresponding to boundary-compatible sets, we try to choose boundary-compatible sets for which this estimation is easy. Now suppose that J is a boundary-compatible set for which the corresponding Green’s matrices are easy to evaluate and estimate. q < 1 so that 11[1- UiL]-lI1 l/(l - q), we Then, if 11 U i L11 can obtain an estimate of (6.3) which involves only the Green’s matrices corresponding to J . This advantage may well offset the loss of accuracy resulting from using (6.3). We now have the following.
<
<
THEOREM 6.4. Let yo(-)be an element of %‘([O, I], R,) and let = S ( y o ,r). Suppose that (i) J = { V ( t ) ,M , N } is a boundarycompatible set for which (5.7) is differentiable on S ; (ii) = { U ( t ) ,K , L } i s a boundary-compatible set; and (iii) there are real numbers 7, q, p, and CY with 7 3 0, 0 q < 1, p 3 0, and 01 = p/(l - q) < 1 such that S
<
(6.5)
II TjcYO) -Yo II = SUP SUP{I W Y o h (4 - Yo,i(t)ll e rl a t
136
4.
APPLICATION TO CONTROL PROBLEMS
Then the MCNI sequence (yl,(.)}for TJ based on y o ( * )and U i L converges uniformly t o t h e unique solution y * ( . ) of (5.7) i n S and the rate of convergence i s given by (6.1 I )
II Y * ( . ) -
G
Y71(.)!I
a”
I1Yd.1 -Yo(.)/( *
Proof. Simply apply Corollary 3.8 of Chapter 2. Similarly, we can translate Corollary 3.14 of Chapter 2 to obtain the following.
THEOREM 6.12. Suppose that (i) J = ( V ( t ) ,M , N } i s a boundary-compatible set for which (5.7) i s twice differentiable on (ii) J ( U ( t ) ,K , L } is a boundary-compatible set; and (iii) there are real numbers 7, q, y , K , 6, and K with 7 3 0,O q < 1, y 3 0, K 0, 8 = y/(l - q ) < 1, and K = ~ / ( l q ) such that
s;
~
>
<
4.7.
NEWTON’S METHOD
137
and --
l-dl-2h h
(6.17)
7j
1-6
< r c
l + d m 7j h 1-6
<
where h = Kv/(l Q. Then the MCM sequence {yn(.)} f o r TJ based on y o ( * and ) U i L converges uniformly t o the unique solution y*(.) o f (5.7) i n S and t h e rate of convergence is given by
Proof.
4.7.
Simply apply Corollary 3.14 of Chapter 2.
Application to Continuous Problems 111: Newton’s Method
We now examine the application of Newton’s method to the integral equation representation of TPBVP’s. We begin our discussion with a formal application of Newton’s method to the integral equation
where J = { V ( t ) ,M , N } is a boundary-compatible set. We find that the corresponding algorithm is equivalent to the solution of successive linearizations of the original TPBVP. Next, we consider the translation of the results of Chapter 2, Section 4. We can follow two approaches: namely, (1) an approach based on the direct application of Lemma 10.1 of Chapter 3; or (2) an approach based on the application of Banach’s theorem on the inverse of an operator. We find that application of the first approach to Proposition 4.8 and Theorem 4.27 of Chapter 2 leads to impractical results since the translated convergence conditions involve the determination of suprema for integral expressions in which the Green’s matrices are variable. As such evaluations are, in general, impossible, we do not apply the first approach. Instead, we only translate Theorem 4.27 using the second approach. We do not encounter such difficulties in applying the first approach to Theorem 4.38 of Chapter 2 and so obtain a practical convergence theorem for Newton’s method, which is an improvement over similar
138
4.
APPLICATION T O CONTROL PROBLEMS
theorems in the literature [B3, M2]. For the sake of completeness, we conclude with a translation of Theorem4.38 based on the second approach. Now, formally applying Newton’s method to (7.1)’ we guess an initial yo(.) and generate the N M sequence based on y o ( * )by the algorithm
+ v:J’(Yn+l
(74
Yn+1 = TJ(Yn)
-
Yn)
or, equivalently, by the algorithm (7.3)
Yn+1 = [ I -
(cn)’l-l [TJ(Yn)
-
(CJYnl
(provided that the indicated inverse exists). Equation (7.2) is equivalent
to the linear TPBVP Yn + l -
(7.4)
IMYn+1(0)
v ( t ) ~ n +=l F ( ~ n ( t ) yt ) - k ’ ( t ) ~ n ( t )
+ NYn+1(1)
:1
+ =c
-( y n ( t ) ,t ) -
-
I+
v(t) (Yn+l(t)- Y n W
g(yn(0)) - h(Yn(1))
MYn(0)
+ NYn(1)
If (7.4) has a solution Y ~ + ~ ( then - ) , Y ~ + ~ is ( * also ) a solution of the TPBVP Yn+1 = F(Yn , t )
(7-5)
dYn(0))
8F +(Yn aY
P
4[Yn+1 - Ynl
+ h(Yn(1))+ agay (Yn(O))[Yn+,(O) Yn(0)l ah +3 (Yn(l))[Yn+1(1)- Yn(1)I = c -
and conversely. T h e iterative method for solving TPBVP’s by replacing the TPBVP be a sequence of linear TPBVP’s of the form (7.4) or (7.5) is called Newton’s method (or quasilinearization) for TPBVP’s. T h e sequence of iterates is called the N M sequence for the TPBVP based on yo(*). This sequence coincides with the N M sequence for TJ based on yo (* ). T h e use of Newton’s method in the solution of TPBVP’s of the type arising in control problems has received much attention as the result
4.7.
NEWTON’S METHOD
139
of the work of Bellman and Kalaba [B3, Kl], who use the name quasilinearization, and the work of McGill and Kenneth [K7, K8, KlO, M l , M2, M3], who call the method, the generalized NewtonRaphson method. As in most other applications of Newton’s method, the convergence of Newton’s method for TPBVP’s is rapid if there is convergence at all. I n order to increase the chance of convergence of the method in practical applications, it is most important that the initial approximate solution be chosen as close (in the sense of the norm) to the actual solution as feasible with the available data. It can be shown that basically any N M sequence converges if the initial approximate solution is chosen close enough to the actual solution (see Collatz [C4]). I n case of linear boundary conditions, the algorithm insures that all successive solutions, except possibly the initial one, satisfy the boundary conditions. As a consequence of the requirement for closeness of the initial guess, it is good practice in the case of linear boundary conditions to select the initial approximation so as to satisfy the boundary conditions. A well-known drawback of any Newton’s method approach is that at each step of the iteration the inverse of an operator must be determined. I n the case of Newton’s method for TPBVP’s this amounts to the requirement that at each stage a diflerent linear TPBVP has to be solved. A considerable simplification can usually be achieved if the operator is inverted only at the first step and the same inverse is used for all succeeding steps. This procedure, which is generally known as the modified Newton’s method, amounts, in the case of TPBVP’s, to using a single boundary-compatible set Jo for all iterations. Instead of having to solve a different linear TPBVP at each stage, we are only required to solve the same linear problem for different forcing functions. Now, let us rewrite (7.5) in the form Yn+1 -
aF ~
ay
(Yn t)yn+1
140
4.
APPLICATION T O CONTROL PROBLEMS
It is then clear that (7.6) corresponds to a linear TPBVP with a set of matrices I:, = KWC?2,)(Y,, 9, (ag/aY)(Y,(o>)l (ah/aY)(Yn(l))l. If y, 1
is a boundary-compatible set, then (7.6) is equivalent to the integral equation y t L i= l TY7~(y,). However, in general, Y, need not be a boundary-compatible set and so we seek conditions on the sequence of iterates which insure the solvability of (7.6) for the particular elements of the sequence. Proposition 4.8 of Chapter 2 followed from a consideration of Newton’s method as a special case of the contraction mapping method. T h e key convergence condition (4.10) here takes the following form: (7.7)
s.p{[llI ),ES
-
(T,J)’I-l (TVJ)” [I - (TvJ)’]-l[TJ(y) -y]Il>
< < 1. 01
1,etting I’ {(W/i.y)(y, t ) , (ag/ay)(y(O)), (ah/ay)(y(l))} and assuming that I’ is boundary compatible, we can use (10.4) and (10.6) of Chapter 3 to write (7.7) in the form 7
in vie\\ of (10.4) and (10.6) of Chapter 3 . But (7.8) involves the evaluation of the Green’s matrices H y ( t ) and Gy(t, s) for a l l y in S. Clearly, this is not very practical. A second approach to (7.7) is to try and niajorize by a product of norms. If J is chosen so that SUP,,,s{II(T,/J)’I l l q 1, then SUP,ES{II[I (~7/”)’111) 1 p - q) and ~e need only estimate /l(T,/J)” II,II TJ(y) - y /I for ally in S. While this can be done, it is clear that the resulting convergence conditions will not be sharp because of the many majorizations involved. Thus, we omit the translation of Proposition 4.8. Now let us consider theorem 4.27 of Chapter 2. Here, the main convergence condition is
<
(7.9)
~
sup(ll[I 1E S
~
<
< K.
(T,J)’]-’ (T2/J)” II}
(7.10)
Clearly, (7.10) is not easily evaluated. T h e second approach, which is
4.7.
141
NEWTON'S METHOD
based on Banach's theorem, does not lead to such difficulties and, in particular, we have the following. THEOREM 7.11. Let yo(*) be an element of %([O, 11, Rp)and let S = S ( y o , r ) . Suppose that (i) J = { V ( t ) M , , N } is a boundarycompatible set for which (5.7) is twice differentiable on S, and (ii) there are real numbers 7, q, K , K , and h with 7 3 0, 0 q < 1, 0, K = ~ / ( l q), and h = Kq such that K
<
(7.13)* (7.14)* (7.15)
h t 2
f( y k - I
(7.16)
7
< Y.
k=O
Then the NM sequence {y,(.)} based on yo(.) converges uniformly to a solution y * ( - ) of (5.7) in S and the rate of convergence is given by
Proof. Simply check that the hypotheses of Theorem4.27 of Chapter 2 are satisfied. T h e Kantorovich theorem (Theorem 4.38 of Chapter 2) can be readily translated into practical terms with the aid of Chapter 3, Lemma 10.1. We have the following. THEOREM 7.18. Let yo(.) be an element of V([O, 11, R,) and let S = S ( y o , r ) . Suppose that (i) J = { V ( t ) ,M , N } is a boundarycompatible set for which (5.7) is twice differentiable on S ; (ii) yo = {(aFiaY)(Yo(t), 9, (ag/ar)(ro(o)),(waY)(Yo(l))) is a boundary-
* Again,
the theorem holds for the coarser estimates I1 (T/)' ll(b) , I1 (Td)' /I(c)
11 (TVJ)''Il(t,) , or II ( T / ) " IIw .
,
142
4.
APPLICATION TO CONTROL PROBLEMS
compatible set; and (iii) there are real numbers 7, K , and h with 7 >, 0, K 3 0, and h = Kq such that
(7.22) Then t h e NM sequence {y,(.)} for (5.7) based o n y o ( * )converges uniformly t o the unique solution y * ( . ) of (5.7) i n S and t h e rate of convergence i s given by
and
I1 Y * ( . ) - Yl(*)ll
< [h/(l
-
h)Ill Y d . )
-
Yo(.)Il*
Proof. Simply verify the assumptions of Theorem 4.38, Chapter 2. Note that since Yo is boundary compatible, [I - (TiO)’]-lexists by virtue of Lemma 10.1, Chapter 3, and that
by virtue of (10.6), Chapter 3. We can also use the approach based on Banach’s theorem to obtain the following. THEOREM 7.24. Let y o ( - )be an element of W([O, 11, Rp)and let S : S ( y , , Y). Suppose that (i) J = {V(t),M , N } is a boundarycompatible s e t for which (5.7) is twice differentiable o n S , and (ii) there are real numbers 7, q, K, K , and h with 7 >, 0, 0 q < 1, ./(I q ) , and h = K7 such that K >, 0, K
<
* Again, 11 ( T 3 ) ”
or
/I (T p )”
may be used.
4.7.
143
NEWTON’S METHOD
(7.26)* (7.27) * (7.28) (7.29) Then t,,e I sequence { y n ( * ) based ) on y o ( - )converges uni.a-rnly t o t h e unique solution y*(.) of (5.7) i n S a n d t h e rate of convergence i s given by
1
II Y * ( ’ ) - Yn(.)ll < 2”-1 (2h)2n-1II Y l ( . ) - Yo(.)II
We note that these theorems are, from a practical standpoint, somewhat better than the results by McGill and Kenneth [M2] and Bellman and Kalaba [B3] since our theorems apply to general TPBVP’s. EXAMPLE 7.30. We consider the simple second-order problem (7.31)
ji= -S~Y+*t2-&t-z
8
?
Y(O) =Y(’)
=’
or in standard form (7.32)
It is easily verified (by substitution) that a solution of this TPBVP is given by (7.33)
y l * ( t ) = 4 ( t - t2),
y2*(t) = 4
-
t.
144
4. APPLICATION
TO CONTROL PROBLEMS
From (7.32), we have
[$j=[n
I]. 0
[$-]=I1 01'
0 0
-Y2
[El=[, u]. 0 0
Using superscripts for the iteration number, the algorithm becomes (7.34)
r
As initial guess, we select the simplest function satisfying the (linear) boundary conditions, namely, (7.35)
yl"'(t)
= 0,
y2 ( 0 )( t ) = 0.
In view of (7.34) and (7.35) the first approximate solution y ( l ) ( t )is the solution of the linear TPBVP
By straightforward integration, we find that
4.7.
145
NEWTON'S METHOD
T h e second approximate solution is then the solution of
-
(f
+i
t3
-
t 2 -
a
YP' t2
+ f t + x)y;) 23
-
1
+ 12.( 6L t 3
-
+
t2
+ 5 t + 2?)2
i
'
T h e solution of this TPBVP is no longer a simple analytic expression. I n order to investigate the convergence, we evaluate the differences between the successive solutions y(O)(t)and y ( l ) ( t )as well as the difference between these approximate solutions and the exact solution. We thus obtain
T h e norms of these differences are
146
4. APPLICATION
TO CONTROL PROBLEMS
T h e first approximate solution y ( l ) ( t )is considerably closer to the exact solution than the initial guess y(O)(t). This points towards convergence of Newton's method. We next consider the application of Theorem 7.11 to check the convergence of the N M sequence. T o do so, we select as boundarycompatible matrices V(t),M , and N , the set (7.38)
T o evaluate q and K , we define a matrix P ( t ) and vectors z and x with elements p i j ( t ) ,zi, and xi given by
We now have the following simple expressions for (conservative values of) the numbers q and K :
4.7.
147
NEWTON'S METHOD
In Example 5.18 we derived the relation (see Eq. (5.25) of this chapter) 2(t
P(t) = [
- t2)
I
*
g (t - t2) -
1
(t - t2)
We have
Hence, in order to determine the vector z, we need to select a radius r for the sphere S(y(O),r). A good choice in this respect is r = 0.58.
.=[
With yio) = 0, we then have
0
0.58
and, in view of (7.39),
Hence, we may select as a conservative value for q, q
it follows that
=
0.29. Since
4.
148
APPLICATION TO CONTROL PROBLEMS
and that
Thus, we may select as a conservative value for these values for 77, q, and K we calculate that h
Kq =
:--
1
K, K
=
0.5. With
0.5 (0.4792) = 0.337 < 2. 1-0.29
-Q'=
Hence, we conclude that the main convergence condition (7.15) of Theorem 7.1 1 is satisfied. T o check the last condition (7.16) of the theorem, we note that for h/2 < 1, we have
f
(+Zk-l
I<=O
1=0
=
1
1
~
( 42) '
It follows then that 9-1
f ($)
1,- 0
rl
1iZ)' < 1-(h
=
1 -0.4792 4 (0.337)
= 0.576 =
0.58
= Y.
Thus, noting that the differentiability assumptions are clearly satisfied, we find that all conditions of Theorem 7.1 1 are fulfilled. Therefore, the conclusions of the theorem hold. First, this implies that the N M sequence is convergent to a (not necessarily unique) solution y*(.) of the 'I'PBVP in s ( y ( " )r, ) . Secondly, this means that a guaranteed convergence rate is given by the expression
Besides showing that the convergence is rapid, this expression also
4.7.
149
NEWTON’S METHOD
implies that the solution y * ( * ) is close to the first approximate solution y ( l ) ( . )For, . for n = 1, we have
‘ 1
(0.169) (0.479) (0.169)2
-
< 0.0832. T o evaluate the convergence conditions given by Theorem 7.18 we define, in addition to the matrix P ( t ) and the vectors z and x another matrix PYo(t)with elements &(t) given by
We then find that a conservative value for the number K is given by the expression
Since the set of matrices Yo coincides with the set V ( t ) ,M , and N considered in the earlier part of this example, it follows that
P y t ) =P(t) =
2(t
~
t2)
4( t
- t2)
4 - (t - t2)
and hence
Thus, we deduce that a conservative value for K is K the value of q given by 0.4792 we find that h
= KT = (0.5)(0.4792) = 0.2396
= 0.5.
With
< $.
Thus, we find that the main convergence condition (7.21) of
150
4. APPLICATION
TO CONTROL PROBLEMS
Theorem 7.18 is satisfied. T o determine a radius r for the sphere S ( y ( " )r,) (since the second derivative is independent of y, we did not have to assume a value for r beforehand to evaluate x), we evaluate the expressions 1 - dl
h
-
2h
rl=
1
~
d1 - 2(0.2396) (0.4792) 0.2396
= 0.5566
and
<
Hence, we may select r as any number satisfying 0.557 r < 3.44. Since the differentiability assumptions are clearly satisfied, it follows that all conditions of Theorem 7.18 hold. This insures that the NM sequence converges to the unique solution y * ( * ) in S(y(O),r). I n addition, Theorem 7.18 guarantees a convergence rate given by (7.23) and an estimate on jl y(l)(.)- y*(*)ll given by
/ / y ( l ) ( . )- y*(.)ll < 4.8.
o,::%(0.4792).
Application to Continuous Problems IV: Multipoint Methods"
We now turn our attention to the application of the multipoint algorithms of Section 5, Chapter 2, to TPBVP's of the form (5.7). Our main result is the following theorem which represents the translation of Theorem 5.48 of Chapter 2 into the TPBVP context. THEOREM 8.1. Let yo,,(*)be an element of V([O, I], R,) and l e t S, S(y,,, , re). Suppose t h a t (i) J = { V ( t ) ,M , N ) is a boundarycompatible set for which (5.7) is tw i c e differentiable o n S,, and ( i i ) t here are real numbers 6,, B o , , , d o , , , K , , and rl0,= w i t h 0 6, < 1 such th a t
<
* See
Bosarge and Falb [B7].
4.8.
MULTIPOINT METHODS
151
(8.4)
(where
yki
is given by (5.50). Chapter 2).
for 01 = 1 , 2 , . . . . Then the M sequence {#OL(yn,a)(-)} converges uniformly t o a solution yo*(*)of (5.7) in S, and the rate of convergence is given by
fora = 1,2,.
...
Proof. We simply verify that the hypotheses of Theorem 5.48, Chapter 2, are satisfied by the mapping FJ = I - TJ.In view of (i), FJ is twice differentiable on 3 , . Moreover, from (8.2) and the fact that 8, < 1, we deduce that (F;o.J’-l= [ I exists and 1/(1 - am). Combining this with (8.3), we find that l/(Fio,a)‘-l11 that ll(Fio,,)’-l11 11 FJ(y0,,)ll dopa. In view of our other assumptions, we see immediately that the hypotheses of Theorem 5.48 hold. T h e basic strength of Theorem 8.1 lies in the possibility of replacing the sequence of operator iterations yn+l,a= &(yn,=)by an equivalent sequence of linear TPBVP’s. T o illustrate what is involved, let us consider the third-order method generated by z+bz. Beginning with an initial guess y o ( - )= y o and proceeding formally, we have
<
<
152
4.
APPLICATION T O CONTROL PROBLEMS
where J == { V ( t ) ,M , N ) is a boundary-compatible set. However, (8.1 1) is equivalent to the pair of equations
But these equations are both linear and of exactly the same form. Now, let
Then it follows from the results of Chapter 3, Section 8, that (8.12a) and (8.12b) are equivalent to the pair of integral equations
However, these integral equations are equivalent to the linear TPBVP's
4.9.
THE METHOD OF CONTRACTION MAPPINGS
+ +
153
+
where c, = c -g(yn(O)) - h(Yn(1)) B,Y,(O) CnYn(1) and d, = c - g(z,(O)) - h(z,(l)) B,z,(O) Cnzn(l).Now, assuming that the conditions of Theorem 8.1 are satisfied, we deduce that (8.11) has a solution and hence that all the pairs (8.12)-(8.14) have solutions. Thus, under the assumptions of the theorem, the multipoint algorithm yn+l = t,b2(yn)is equivalent to the successive solution of the linear TPBVP’s (8.14). Since the Jacobian A,(s) is the same in (8.14a) and (8.14b), we actually are only required to solve the same linear TPBVP at each stage for different forcing functions and so only one integration of the homogeneous equation is needed at each step. Thus, the extra computation required to obtain higher-order convergence is small. This represents the major advantage of the multipoint methods when applied to TPBVP’s.
+
4.9.
Application t o Discrete Problems I: The Method of Contraction Mappings
We have seen that if the conditions of Theorem 5.1 of Chapter 3 are satisfied, then TPBVP’s [such as (4.21)] of the form (9.1)
+ 1) = W ( j + 1),Y(j)dt g ( y ( 0 ) )+ h(Y(!7))= c y(j
are equivalent to summation equations of the form
where J = {A(j),B(j),M , N } is a boundary-compatible set. Now, just as in the continuous case, we view the summation equation as an operator equation and apply the methods of Chapter 2. As the results and ideas are entirely analogous to those of the continuous case, we are more succinct in out treatment of the discrete case. We begin with the method of contraction mappings. Proceeding
154
4.
APPLICATION TO CONTROL PROBLEMS
for,mally, we first select an initial element y o ( - )in 9 ( Q ,Rp). Next We generate the CM sequence {y,(.)} for TJ based on y o by means of the algorithm yn-, = TJ(y,) or, equivalently, by
k=O -
A(k)Yn(k
+ 1)
-
B(k)Yn(k))*
Since the function y,( -) is known, we can write (9.3) in the form (9-4)
where
Yn+1W
c", = c
=W
j )Cn
g(Yn(0)) - h(Y,(d)
+ MYn(0) + NYn(Q)
+ l),Yn(& k) A ( k ) Y n ( k + 1) ever, (9.4) is the solution of the linear TPBVP
fn(9= F(Y,(k (9-5)
Yn+dj
-
-
+ 1) -Yn+dj)
MYn+1(0) -I-
=4 ) Y n + 1 ( j
-
B(k)Y,(k).
+ 1) + W)YTL+l(d
and How-
+fn(i)
NY%+l(d= Cn
and so it follows that the method of contraction mappings essentially amounts to the successive solution of linear TPBVP's. This is often referred to as Picard's method. We now have the following. DEFINITION 9.6. The TPBVP (9.1) i s differentiable on a subset S of Y ( Q ,R p ) is (i) there i s a boundary-compatible set J = { A ( j ) B(j), , M , N } such that the function K ( j , x , y , k) = GJ(j,k){F(x,y , k) - A ( k ) x - B(k)y} satisfies t h e conditions of Lemma 9.5 of Chapter 3 for an open D i n R, w i t h the range of S contained i n D , and (ii) g and h are differentiable. Similarly, the TPBVP (9.1) i s twice differentiable o n S if K ( j , x , y , K), (aK/ax)(j,x , y , k) and (aK/ay)(j,x , y , k) satisfy t h e conditions of Lemma 9.5 o f Chapter 3 and if g and h are twice differentiable. THEOREM 9.7. Let y o be an element of Y ( Q ,R p ) and l e t S ( y , , Y ) . Suppose that (i) J = {A(j),B ( j ) ,M , N } is a boundarycompatible s e t for which (9.1) i s differentiable on S, and, (ii) there S
4.9.
THE METHOD OF CONTRACTION MAPPINGS
are real numbers 7 and a: w i t h 7 3 0 and 0
< a: < 1 such
155 that
II TJ(Yo) -Yo II < rl
(9.8) (9.9)
1
(9.10)
1-01
< r.
Then t h e C M sequence {y,(.)} f o r (9.1) based o n y o and J converges uniformly t o t h e unique solution y*(.) o f (9.1) i n S and the rate of convergence i s given by
(9.1 1)
I~Y*(*)
-Yn(*)Il
< GIIY~(*) 01”
-~o(.)ll
*
We note that I\( TUJ)’ in (9.9) can be replaced by either II( TUJ)‘
or II(TvJ)’Il(c) . As this type of replacement can be done in general, we shall not call attention to it again.
We can also translate Corollary2.34, Chapter 2, to obtain the following. THEOREM 9.12. Suppose that (i) J = {A(j),B ( j ) ,M , N } is a boundary-compatible set f o r which (9.1) i s twice differentiable o n S, and (ii) there are real numbers 7, 6, and K w i t h 7 3 0,
0<6<1, (9.13) (9.14) and
(9.15)
1-dl-2h h
~-
1-8
<
< r c
1+d/1--2h h
7 1-8
3. Then t h e CM sequence {y,(.)} for where h = Kq/(l - S)2 t h e TPBVP (9.1) based o n yo and J converges uniformly t o t h e unique solution y * ( - ) of (9.1) i n S and the rate of convergence i s given by
156
4.
APPLICATION TO CONTROL PROBLEMS
We conclude this section with a simple illustrative example. We apply Picard’s method twice to the discrete TPBVP considered in Section 7 of Chapter 3 . We will see that the first application does not result in convergence no matter how close the initial guess is to the actual solution. T h e second application is convergent. We check the results against the theory by evaluating the relevant estimates. These estimates turn out to be inconclusive and we then discuss the situation in some detail.
EXAMPLE 9.17.
Consider the TPBVP
(9.18)
where j = 0, 1, 2, 3. I n order to apply Picard’s method we must select a set of boundary-compatible matrices {ACj),BCj), M , N } . As a first choice, the set
is selected. With this choice, the application of Picard’s method turns out to be unsuccessful. Next, as a second set of boundary compatible matrices, we take A ( j ) == (9.20)
[;-;] ,
B(j)=
[
O 01 --3 0
T h i s choice produces a successful application of Picard’s method.
4.9.
157
THE METHOD OF CONTRACTION MAPPINGS
Considering Picard's method with the boundary compatible set (9.19), we easily verify that this amounts to the successive solution of the linear problems (9.21)
r?"'(j + 1) - y F ) ( j ) &+l)(j
+ 1) ypl)(j) = -
+ l),
-y?'(j
=
~
~ ~ " (= 0) 3
y1"+1'(4) =
[yp)(j)13,
+ 3.
Taking as a first guess for the solution the sequences yF'(j)
= {-
3,
yP'(j) ={-28.5,
-
1.5,0, -
+ 1.5, + 3.0)
1.5, - 1.5,
-
1.5, - 1.5)
TABLE I
\
1
2
3
- 3.000
- 1SO00
- 3.000
+0.1875 - 1S O 3 3 +0.1986 - 1.5039 +0.2008 - 1.5040
0.0 0.0
1 SO00 -0.1875
O
of Number iterations
0 I 2
- 3.000
3
- 3.000
4
- 3.000
5
- 3.000
6 7 8 9 10
3.000 -3.000 - 3.000 -3.000 - 3.000 -
f0.2012 - 1.5041
+0.2013 - 1.5041
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
+ + 1.5033
- 0.1986
+ 1.5039 - 0.2008
+1.5040 - 0.2012
+ I SO41 - 0.201 3
+ 1SO41
4 t3.000 +3.000 3.000 3.000 3.000 3.000 +3.000 +3.000 $3.000 1-3.000 13.000
+ + + +
we obtain the divergent sequence of iterates given in Table I.* For an initial guess given by yio)(j)= (-3.0, -1.01, 0, +1.01, +3.0}, yiO)(j)= (-28.99, -1.99, - 1.01, - 1.01, - 1.99}, which is very close to the exact solution yl*(j) = (-3.0, -1.0, 0, +1.0, +3.0}, yz*(j)= (-29.0, -2.0, -1.0, -1.0, -2.0}, we again obtain a divergent sequence of iterates (Table 11). After this unsuccessful application of Picard's method, we try the method once more but using the boundary-compatible set (9.20).
* All
tables in this section involve only yl(j).
158
4.
APPLICATION TO CONTROL PROBLEMS
T A B L E I1
\
of Number iterations
0 I 2 3 4 5 6 7 8 9 10
-
-1.0100 -0.9848 - 1.0223 -0.9657 - 1.0497 -0.9216 -1.1086 -0.81 87 - 1.2256 -0.5795 I .4027
3.000
- 3.000 -
2
I
O
\
3.000
- 3.000
3.000 3.000 - 3.000 - 3.000 - 3.000 - 3.000 -3.000
-
0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
-
3
4
+1.0100 +0.9848 1.0223 +0.9657 1.0497 +0.9216 t1.1086 +0.8187 1.2256 t0.5795 1.4027
+3.000 t-3.000 +3.000 +3.000 +3.000 +3.000 +3.000 +3.000 t3.000 t3.000 +3.000
+ +
+ +
T h e algorithm then reduces to the successive solution of the TPBVP's
(9.22)
yi"")(j
+ 1)
y y ( j
+ I)
--
yl""'(j
-y
p y j
+ 1) =
+ 1) =
y1"+1'(4) =
~
-
yfqj
+ l),
3[YF+')(j)
- y?'(j)] -
[ y (n) l (/)I . 3
+ 3.
The sequence of solutions obtained with this algorithm is given in Table 111. T A B L E I11
\
0
1 2 3 4 5
1
O
of Number iterations
-3.000 3.000 - 3.000 3.000 -3.000 - 3.000 -
-
- 1S O 0
-0.8250 -0.9827 -0.9998 -1 -I
.oooo .ooo
2
3
4
0.0 0.0 0.0 0.0 0.0 0.0
+1.5000 +0.8250 +0.9827 +0.998 1.oooo 1.oooo
+3.000 +3.000 t3.000 +3.000 +3.000 +3.000
+ +
4.9.
THE METHOD OF CONTRACTION MAPPINGS
159
This application of Picard’s method is quite successful as the fourth iterate agrees with the exact solution to four significant digits. T h e reason for this fast convergence lies in the fact that the matrix B ( j ) equals the matrix of partial derivatives (aFjay)(j),evaluated at the exact solution at the important points of the interval (j= I , j = 3 ) . This will become clearer in the sequel when the determination of the convergence conditions is discussed. I n order to investigate the practicality of the conditions given in Theorems9.7 and 9.12 on the convergence of Picard’s method, we must estimate the norms ll(T/vJ’11 and lI(Ti))’’/I. I n view of the fact that the original TPBVP (9.18) is linear in the boundary conditions, it follows immediately from (9.15) of Chapter 3 , that the norm W&J’II is given by
while the norm
II( T:,))’’ /I is given by
T h e simplicity of the TPBVP under consideration makes it possible to efficiently evaluate a number of increasingly simpler, though coarser, estimates for the norm:
160
4. APPLICATION
T O CONTROL PROBLEMS
4.9.
THE METHOD OF CONTRACTION MAPPINGS
161
and
For the first application, the Green’s matrix GY(a,p) and the matrices of partial derivatives [aF/ay - B] and [a2F/ay2]are given by
and
162
4.
APPLICATION TO CONTROL PROBLEMS
From Theorem9.7, it follows that convergence can only be Given guaranteed when the norm I]( T:,.,)‘ /I is smaller than 1 .O on (9.34), it is not possible to guarantee convergence for the application of Picard’s method by means of the algorithm (9.21). This result seems to be in line with the observed divergence of this application of Picard’s method (Tables I and 11). However, it should be remarked in this context that the Theorem 9.7 provides only a sufficient condition for convergence. I t is quite possible, as we will see, that Picard’s method converges even though the norm II( T { g ) ) ’11 is much larger than 1.0. For the evaluation of the norms (9.25)-(9.28) and (9.30)-(9.33) which correspond to the application of the algorithm (9.22), we again need the Green’s matrix GY(a,p). Having no simple analytic expression for this matrix, we can generate the matrix by solving the linear TPBVP’s.
s.
(9.37)
+ 1) - Y l m y Z ( j+ 1) y l ( j ) Yl(j
-
=
+ 11, 3yl(j) + W’ B),
-Yz(j
= -
-
Yl(0)= o Yd4) =0
for all /3 in Q’ where S ( j ) is the equivalent of the 8 function in the 1. T h e solution of continuous case, i.e., S ( j ) = 0 if j # 0, S(0) the TPBVP’s (9.36) gives the first columns of the matrix GY(a,p), and those of (9.37) the second columns. T h e matrices of partial derivatives required for the norm determination are almost the same as before and are given by
and
Evaluating these derivatives along the exact solution y* and carrying
4.9.
THE METHOD OF CONTRACTION MAPPINGS
163
out the required numerical computations, we obtain the following estimates of the norms, namely,
T h e numerical values obtained for these norms are all larger than 1.0. This result is at first sight somewhat surprising since the corresponding Picard’s method sequence was found to be convergent (see TableIII). T h e reason for this behavior of the convergence condition norm lies in the large contribution to this norm by the derivative L@’,/ay, = 3y12(/3)at the initial point y,(O) = -3.0. T h e same derivative does not contribute to the ratio
which provides the actual contraction factor of Picard’s method. T h e reason for the derivative not contributing to this ratio lies in the fact that the initial value of y,(O) is kept at its fixed value for all successive iterates. For, if we write out the norm I( TJ(yn+,)- TJ(y,)(l,we find
where according to the mean value theorem y = yn + O( yn+, - yn), 0 < 0 < 1. As y:”+”(O) - yin)(0)= 0 and W,/ay, - b,, = aF,/ay, - b,, = 0 for all successive iterates, it follows that there is indeed no contribution to the sum in (9.40) for /3 = 0. I n the determination of the convergence condition by evaluating the norm
164
4. APPLICATION
x;=o
TO CONTROL PROBLEMS
Il(T(!,J’ /I = SUP. ll GY(%P ) [ ( w a Y ) ( Y * ( P ) l w9111 this fact was not taken into account. Had it been taken into account, then the norms I/( T[,,.,)’ I/ for both Picard’s method applications would have had the values
P)
~
and respectively. I t is clear that these numbers are consistent with the observed divergence and convergence, respectively. Since the norm /I( T&*))’I/ for the second application of Picard’s method is too large for verification of the convergence by means of Theorems 9.7 and 9.12, there is little point in evaluating the remaining convergence conditions given by these theorems. I n view of this, the example given here seems to be of limited value. However, it serves to illustrate several important points. First, the choice of a boundarycompatible set is often of critical significance in obtaining convergence. Second, the theorems are only sufficient conditions and are often quite conservative in practice. Third, a theorem analogous to Theorem 4.71 of Chapter 2 would be quite useful for the contraction mapping method.
4.10.
Application t o Discrete Problems II: The Modified Contraction Mapping Method
Just as in the continuous case, we can view the application of the modified contraction mapping method to (9. I ) as equivalent to thc contraction mapping method applied to the operator P [I V ] p l [ T J V ]for a suitably chosen V . We again limit our discussion to operators V -- tJAL of the form given by (1 1.2) of ( A ( j )B , ( j ) ,M , N ) and = { C ( j ) D , ( j ) ,K , L} Chapter 3 . So, we let J be boundary-compatible sets. We then note that, by virtue of Lemma 1 I . I , the modified contraction mapping method when applied to the equation TJ(y) -- y with modifying operator V = U i L, is equivalent to the contraction mapping method applied to the equation ~ ’ ( 3 ’ ) y. ~
~
~
1
4.10.
THE MODIFIED CONTRACTION MAPPING METHOD
165
Now, with the aid of Lemma 11.1 of Chapter 3, we can translate the relevant results of Chapter 2 with no difficulty. However, as we noted in detail in Section 6, the choice of different approaches did not, in general, lead to simpler or better convergence conditions. Only in those cases where we could use boundary-compatible sets for which the corresponding Green's matrices were easy to evaluate was there any practical advantage to using the modified contraction method. Precisely the same considerations apply in the discrete case. Thus, we do not repeat the discussion here but rather simply state the convergence theorems analogous to Theorems 6.4 and 6.12. THEOREM 10.1.
Let y o be an element of 9 ( Q ,I?],) and let = {A(j)B , ( j ) ,M , N } is a boundarycompatible set for which (9.1) is differentiable on S ; (ii) J = (C(j),D ( j ) ,K , L } is a boundary-compatible set; and (iii) there are real numbers 9, q, /I, and 01 with 9 >, 0, 0 q < 1, /I 3 0, and OL = p/(l - q) < 1 such that
S
=
S ( y o ,r ) . Suppose that (i) J
<
(10.2)
II T-YYO)
YO II
(10.4)
(10.5) where
(10.6)
-7
1
1-LY
< rl
166
4. A P P L I C A T I O N
T O C O N T R O L PROBLEMS
and
Then t h e MCM sequence {y,(-)} for TJ based on y o and U i L converges u n i f o r m l y to t h e unique solution y*(.) of (9.1) i n S and t h e rate of convergence is given b y
Proof. Simply check that the hypotheses of Corollary 3.8, Chapter 2, are satisfied.
THEOREM 10.9. Suppose t h a t (i) J = {A(j),B ( j ) ,M , N } i s a boundary-corn pati ble set for which (9.1) i s t w i c e differentiable o n S; (ii) j = { C ( j ) ,D ( j ) , K , L } is a boundary-compatible set; and (iii) t h e r e are real numbers 7, q, y , K , 6, and K with r] 3 0, 0
such t h a t
( 10.10 ) (10.11) (10.12) (10.13)
4.1 1. NEWTON’S METHOD
167
and
(I 0.14)
1-41-2h h
9
1-8
1+2/1-2h
q
~-
1-8
<8.
where h = Kv/(l - S)z Then t h e MCM sequence {y,(-)} f o r T J based o n y o and UJ,, converges uniformly t o t h e unique solution y * ( * )of (9.1) i n S and t h e rate of convergence i s given by
4.11.
Application t o Discrete Problems 111: Newton’s Method
Just as was the case in previous sections, the remarks made with regard to Newton’s method for continuous problems apply almost verbatim in the discrete case. Therefore, we limit ourselves to a brief discussion of a few details of the application of Newton’s method and to the translation of Theorems 4.27 and 4.38 of Chapter 2. T h e point of departure for our discussion is again the operator equation y = T J ( y ) .T o apply Newton’s method, we guess an initial solution yo and generate an N M sequence by means of the algorithm (11.1)
Ya+1 = TJ(Yn)
+ V;J’(Yn+l
-Yn)
or, equivalently, by (1 1.2)
Yn+1 = [I - (GJl
-l
[TJ(Yn) - V,:,)’Ynl
(provided that the indicated inverse exists). Now, ( 1 1.2) is equivalent to the linear TPBVP
which can be written as
T h e iterative method for solving TPBVP’s by replacing the TPBVP by a sequence of linear TPBVP’s of the form (1 1.3) is called Newton’s method (or quasilinearization) for TPBVP’s. T h e sequence of iterates is called the N M sequence f o r the TPBVP bused on y o (and J ) . This sequence coincides with the N M sequence for TJ based on y o .
4.1 1. NEWTON’S METHOD
169
Now, it is clear that (1 1.3) corresponds to a linear TPBVP with a set of matrices
If Y, is a boundary-compatible set, then (1 1.3) is equivalent to the integral equation Y,+~ = TYm(y,). However, in general, Y, need not be a boundary-compatible set and so, we seek conditions on the sequence of iterates which insure the solvability of (1 1.3) for the particular elements of the sequence. Again, there are two approaches to the translation of the results of Chapter 2; namely, (1) an approach based on the direct application of Lemma 11.1 of Chapter 3; or (2) an approach based on the application of Banach’s theorem on the inverse of an operator. As before, two practical convergence theorems results. T h e first such theorem is the translation of Mysovskikh’s theorem using the second approach and the second such theorem is the translation of Kantorovich’s theorem using Lemma 11.1, Chapter 3. Thus, we have the following. THEOREM 11.4. Let yo(*)be an element of Y ( Q ,R,) and let = S(y,, r). Suppose that (i) J = {A(j),B ( j ) ,M , N } is a boundarycompatible set f o r which (9.1) i s twice differentiable, and (ii) there q < 1, K 3 0, are real numbers q , q, K, K , and h w i t h 7 3 0, 0 K = ~ / ( 1- q), and h = Kq such that
S
<
(11.6) (11.7) (11.8) (11.9)
h<2
2
k=O
(+)2k-1
7
< r.
170
4.
APPLICATION TO CONTROL PROBLEMS
Then the NM sequence { y n ( - ) }based on yo converges uniformly t o a solution y * ( . ) of (9.1) i n S and the rate of convergence is given by (11.10)
llv*(*)-Yn(.)ll
< [l(h/2)2n-1 I/Y4.1 h/2I2" -
-
Yo(-)ll
THEOREM 11.11. Let y o ( * )be an element of Y ( QRp) , and l e i S = S ( y , , r ) . Suppose that (i) J = {A(j),B ( j ) ,M , N } i s a boundary-compatible s e t for which (9.1) i s twice differentiable on S; (ii)
i s a boundary-compatible set; and (iii) there are real numbers 7, K , and h w i t h 7 3 0, K 3 0, and h = Kq such that
Then the NM sequence { y n ( * ) }for (9.1) based o n yo converges uniformly to the unique solution y * ( . ) of (9.1) i n S and t h e r a t e of convergence is given by ( 1 1.16)
I1 Y * ( . )
-
Yn(.)/l
and II Y*(.) - Yl(*)ll G [h/(l
1 < 2n-l [2hI2"-' -
II YA.1
-
Yo(.)ll
h>lllYd.1 - YO(.)II.
Proof. Simply verify that the hypotheses of Theorem 4.38, Chapter 2, are satisfied. Note that since Yo is boundary compatible, [I - ( 7 3 ' 1 - l exists by virtue of Lemma 11.1, Chapter 3, and that
4.12.
171
SUMMARY
~~pg~~{ll(T,yO)” [ \ ( a ) }= supg,~{II[I- (T~,,)’]-’( ‘gJ)” II(a)} be virtue of (1 1.6), Chapter 3. We omit treatment of the application of the multipoint methods to discrete problems as this would simply involve a verbatim repetition of Section 8.
4.12.
Summary
We have combined the results on iterative methods for the solution of operator equations of Chapter 2 and the results on the representation of TPBVP’s by operator equations of Chapter 3 to obtain convergence theorems and algorithms for the iterative solution of TPBVP’s of the type that arise in optimal control problems. We briefly indicated the way in which TPBVP’s arise in optimal control problems with both continuous and discrete time domains. Our translation of the results of Chapter 2 relied heavily on the notion of boundary compatibility and on the estimates of derivatives obtained in Chapter 3. We treated some analytical examples to illustrate some of the ideas involved. I n Chapter 6, we shall examine some numerical examples to indicate the role played by our results in some “practical” problems. Considering TPBVP’s of the form (5.7) or (9.1), and letting J be a boundary-compatible set, we noted that the TPBVP’s could be rewritten as integral or summation equations which could be viewed as an operator equation of the form y = TJ(y). Applying the method of contraction mappings to this operator equation was equivalent to the successive solution of a sequence of linear TPBVP’s of the form (5.5) or (9.5). These linear TPBVP’s formed the basis of the algorithm which we called Picard’s method. Theorems 5.8, 5.13, 9.7, and 9.12 were the resulting convergence theorems for Picard’s method. Next, we considered the application of the modified contraction mapping method. As modifying operator V , we chose the linear operator U& given by (10.2) or (1 1.2) of Chapter 3. We found that this application of the modified contraction mapping method was equivalent to the application of Picard’s method to the original replacing J . I n other TPBVP with the boundary-compatible set words, the operators TJ and [I- UiL]-’[TJ- U i L ] were the same. For theoretical purposes, this is significant as it implies that we can consider Picard’s method for TJ as an application of the contraction
1
172
4.
APPLICATION T O CONTROL PROBLEMS
mapping method or as an application of the modified contraction mapping method. For practical purposes, the distinction between thcse viewpoints was not too important since the operator [ I - UiL]-l made the determination of practical convergence conditions somewhat difficult. However, if 11 U i L/I q < 1 , then the use of Banach’s theorem simplified our task and led to some useful results. We then considered Newton’s method. We found that the corresponding algorithm was equivalent to the successive solution of the linear TPBVP’s (7.3) or (11.3). We used two approaches to the translation of the results of Chapter 2; the first approach was based on a direct application of Lemma 10.1 or Lemma 11.1 of Chapter 3, and the second approach was based on the use of Banach’s theorem on the inverse of an operator. Theorems 7.1 1, 7.18, 7.24, 11.4, and 1 1. I 1 were the main convergence results. Finally, we examined multipoint methods and translated ‘Theorem 5.48, Chapter 2, into the TPBVP context. Theorem 8.1 represented this translation.
<
CHAPTER 5
APPLICATION TO OSCILLATION PROBLEMS
5.1.
Introduction
We now consider the application of the results of Chapters 2 and 3 to several classes of TPBVP’s arising in the study of oscillation problems. I n particular, we examine “almost linear problems” and problems with boundary conditions of the form y(0 ) = y( 1) (so-called “periodic” boundary conditions). “Almost linear problems” occur in both control and oscillation problems and are particularly well suited to the use of the contraction mapping method. Problems with “periodic” boundary conditions are, in effect, problems involving periodic solutions. We begin, in the next section, with a discussion of “almost linear problems,” i.e., TPBVP’s of the form
where E is a parameter. Several convergence theorems are obtained for the application of the contraction mapping method (Picard’s method) to (1.1). Several second-order examples are analyzed in Section 5.3. Considerable research has been done on the application of successive approximation methods to oscillation problems and a good starting point for an account of this area is given by Hale [Hl or H2]. I n this brief chapter, we only scratch the surface of a very large mountain. 173
174
5.2.
5.
APPLICATION TO OSCILLATION PROBLEMS
Almost Linear Problems
Previously we discussed the application of various iterative methods to the solution of general TPBVP’s. Here, we consider some aspects of the use of these methods in the important special case of almost linear TPBVP’s. We begin with the following.
DEFINITION 2.1. The TPBVPY i s an almost linear TPBVP if
where
E
=F(y,
t),g(y(O))
+ h(y(1)) = c
i s a “small” scalar and there i s a constant m such that
11 +(€,Y , t)ll
< me,
I/ O ( E , Y)II
+
for all y and t. If j
<
= F ( y , t ) , g(y(0)) h(y(1))= c i s an almost linear problem, then the linear TPBVP corresponding t o it is
j
~
4 t ) y + f ( t ) , IVY(0)
+W l )
= c.
We observe that if yXt) is a solution of the linear TPBVP corresponding to an almost linear problem, then yZ(t)is an meapproximate solution of the almost linear problem. Almost linear problems occur frequently in connection with oscillations (or perturbations of periodic solutions). However, they are not uncommon in control theory. For example, suppose that we consider a control problem with system (2.4)
k = A(t)x
+ B(t)u + e ( x , u , t ) ,
sets S, and S, of initial and final states given by
so = {u: Kx + &(x)
s,= {x:L s $- d(x) and a cost functional
= =
d,}
d2},
5.2.
175
ALMOST LINEAR PROBLEMS
with C, D,and Q ( t ) positive semidefinite and R(t) positive definite. T h e Hamiltonian for this problem is given by H ( x ,P,% P o , t )
=
+ P O G Q(W
+
(u, W u ) )
+ < P ( t ) ,4 4 4
+ <m,Wb) + .
and the canonical equations are given by
p
aH
= --=
ax
-p,Q(t)x
-
A’(t)p - E -
(;:)‘P*
T h e appropriate boundary conditions are
where the mi and pi are constants. Assuming that the control is unconstrained and that the problem is regular [A2], we can, for p , f 0 and E “small”, write the H-minimal control uo(x,p , p , , t ) in the form uO(x,P,Po , t ) =
1
- --
Po
R-l(t) B ’ ( t ) p
+
EZi(X,
p , Po , t ) .
176
5.
APPLICATION TO OSCILLATION PROBLEMS
It follows that the cvtremals of the control problem are the solutions of thc system 2
2
,q(t)t.
~
(2.8)
P
=
P,Q(t).\
39 ~ - l ( t ~) ' ( t ) p Po -
=I'(t)p - E
E[R(~)
~ ( xp,, p, , t )
3;: (x,P , p, r?e
1
t,
€4r
with the boundary conditions (2.7). If we set
p,,
=
+ e(x, p , p, , t ,
€)I
1 and if we let
and
then we can write (2.8) in the form (2.9)
y
=
tV(t)y
+ € E [ Y ( t ) t, ] .
Elimination of the constants mi and pi from the boundary conditions (2.7) will result in almost linear relations of the form
+ %[.(to), p(t,)l = a1 G2"(t,) + HZP(t,) + %L"(tf), P(t,)l = Gl.4t") -tf f , P ( t " )
a2
where G, and 11, are (n - h) x n matrices, G, and H2 are (n - I) x n matrices, g, and a, (n - K ) vectors and g, and u2 (n - I) vectors, with a , and a2 known constant vectors. Defining 2n x n matrices M and N , a 2n vector c and 2n vector functions m(.) and n(.) by
9
N =
5.2.
ALMOST LINEAR PROBLEMS
177
we can write the boundary conditions (2.7) in the form (2.10)
MY(t0)
+ N Y ( t f )t- 4 Y ( t O ) )+ 4 Y ( b ) ) == c.
T h e TPBVP (2.9)’ (2.10) is thus an almost linear problem. This is a typical way in which almost linear problems arise in control theory. Now let us consider the almost linear TPBVP
Application of the method of contraction mappings (Picard’s method) to (2.1 1) can result in some important simplifications of the procedure. Suppose that J = {A(t),M , N } is a boundary-compatible set. Then the operator TJ is given by (2.12)
T J ( Y ) ( t )= W ) [ c - A€,Y(0))- O ( 5 Y ( l ) ) l
and the corresponding algorithm of Picard’s method can be written in the form
or equivalently as
Thus, only a single linear equation (with changing forcing term)
178
5.
APPLICATION TO OSCILLATION PROBLEMS
needs to be solved. Illoreover, it is not necessary to guess an initial approximate solution since an excellent candidate is the solution of the linear problem (2.15)
y
=
LqqY -kf(t),
MY(0)
+ NY(l)
=
c
which corresponds to (2.1 1). T h e simplifications of the procedure are reflected in the corresponding convergence theorems. I n view of the importance of almost linear problems, we give the two main convergence theorems on the contraction mapping method for this situation. We note that the theorems are essentially the same as Theorems 5.8 and 5.13 of Chapter 4 but that the form of the resulting convergence conditions is of interest. We have the following. THEOREM 2.16. Consider the almost linear TPBVP (2.11). Suppose t h a t J = {A(t),M , N } is a boundary-compatible s e t and l e t yo(.) be the solution of t h e linear problem (2.15) corresponding t o (2.11). Let S = S ( y , , r ) . Suppose further that (i) the function GJ(t,s)[f(s) -t +(c,y,s)] satisfies t h e conditions of Lemma 8.5 of Chapter 3 ; (ii) y ( ~ , y and ) e(c,y) are differentiable with respect t o y ; and (iii) there are real numbers 7 and 01 with 7 2 0 and 0 ,Y : 1 such that
<
(2.19)
1 1 -a
-7
--
Then the C M sequence {y,(.)} for t h e TPBVP based o n yo(*)and
J
5.2.
179
ALMOST LINEAR PROBLEMS
converges uniformly t o the unique solution y * ( * )of (2.11) in and the rate of convergence is given by
I/ Y*(.) - Y,(.>ll
(2.20)
<
a"
S
I/ Y d . ) - Yo(.)Il.
We note that if $(e, y , s) = e$(y, s) O(e,y) = eB(y), then (2.17) becomes
and
Y(E,
y)
=
+(y),
(2.22)
Thus, in this case the convergence estimates essentially depend upon E. For example, if $ ( y , s), y ( y ) , and d(y) are continuously differentiable with respect to y , then there is a nondecreasing function M ( r ) such that (2.23)
T h e estimates then become (2.24) (2.25)
where dY0)
=
I!
+
ffJ(.)[--Y(Y0(O))- B"(YO(W1
s1
GJ(44 $ ( Y O ( S ) ,
4 ds
1;.
These estimates are frequently quite useful in particular problems.
180
5.
APPLICATION TO OSCILLATION PROBLEMS
W e now have as the analog of Theorem 5.13 of Chapter 4, the following.
THEOREM 2.26. Consider t h e almost linear TPBVP (2.11). , , N } i s a boundary-compatible set and Suppose that J = { A ( t ) M l e t y o ( * be ) the solution of t h e linear problem (2.15) corresponding t o (2.11). Let S = ,!?(yo,r ) . Suppose further that (i) t h e functions G-'(t,s)[f(s) 4 ( ~y ,, 41 and G-'(t,s ) [ ( W a y ) (y~,,41 satisfy t h e con) e ( , , ~ ) are twice ditions of Lemma 8.5 of Chapter 3; (ii) y ( € , ~ and differentiable w i t h respect t o y ; and (iii) there are real numbers 7 , 6, and K w i t h 7 >, 0, 0 6 < 1, and K 3 0 such that
+
(2.27)
(2.30)
1
<
II yo) - Y o I/ = H J ( . ) [ - A € , Yo(0))- 0(€,Yo(l))l
l-dl-2h h
) _ 7_
1
-s
<
< r <
l + d m_ _ 7) h
1
-s
where h = K7/(1 + . Then t h e C M sequence {y,(.)} for the TPBVP based on yo(.)and J converges uniformly to t h e unique solution y * ( . ) of (2.11) i n S and t h e r a t e of convergence is given by
5.2.
ALMOST LINEAR PROBLEMS
181
We again note that if + ( E , y , s) = e&y, s), y ( ~y, ) = +(y), and eO(y), then the convergence estimates will essentially depend upon E . Now let us turn our attention to almost linear problems with “periodic” boundary conditions. I n other words, we consider TPBVP’s of the form O(e, y ) =
(2.32)
Y
=
m
(2.33)
y
+fW + $GY , t )
Y ( 0 ) = Y(1h
We note that (2.33) may be written in the form (2.34)
ly(0) - Zy(1) = 0
where I is the identity matrix. Let J = {A(t),I, -I}. If J is a boundary-compatible set, then it is quite natural to apply the contraction mapping method to the operator TJ given by rl
in an effort to solve (2.32), (2.34). If the set {A(t),I, -I} is not boundary compatible, then we may replace (2.32) by the equation 9 = {A(t)- eB(t)} y f ( t ) {+(€, y , t ) €B(t)} and use the boundary-compatible set {A(t)- eB(t),I, -I}. Thus, we shall assume from now on that the set J = { A ( t ) , I ,-I} is boundary compatible and shall investigate Picard’s method for (2.35). Now natural choices for the initial guess y o are the solutions of the linear problems
+ +
(2.36)
=
4 ) Y
Y
=
A(t)y,
or (2.37)
+m
Y
+
Y(0)= y ( l ) Y(0) = Y ( l ) -
Note that y ( t ) = 0 is the solution of (2.37) and that use of (2.37) is particularly appropriate when A(t) is constant, i.e., A(t) = A. T h e operator TJ is given by (2.35) and the corresponding algorithm of Picard’s method can be written in the form (2.38)
182
5.
APPLICATION TO OSCILLATION PROBLEMS
We observe that all the iterates will be periodic, i.e., will satisfy the boundary conditions. This is, of course, an important aspect of the method. We now have the following. THEOREM 2.39. Let y o ( * )be t h e solution o f (2.36) and l e t = S ( y , , Y). Suppose that (i) t h e function GJ(t,s)[f(s) $ ( c , y , s)] satisfies t h e conditions o f Lemma 8.5, Chapter 3 ; and (ii)there are 01 < 1 such that real numbers 7 and 01 w i t h 7 3 0 and 0
+
S
<
(2.42)
-7
1
1
-a
Then the CM sequence { y J . ) } given by Y ~ + ~ = ( - TJ(yn)(.) ) converges uniformly to t h e unique solution y * ( - ) of (2.32). (2.33), in S and the rate of convergence i s given by IIy* (.) -y,J.)II an /I Y L . )
-
<
Yo(.)Il/(l - O1).
THEOREM 2.43. Let yo(.) be the solution o f (2.36) and l e t = S ( y , , r ) . Suppose that (i) t h e functions GJ(t,s ) { f ( s ) +(e,y, s)} and GJ(t,s){(a$/ay)(e,y , s)} satisfy t h e conditions of Lemma 8.5, Chapter 3 ; and (ii) there are real numbers 7, 6 , and K w i t h 7 2 0, 0 6 < 1, and K >, 0 such that
+
S
<
5.2.
183
ALMOST LINEAR PROBLEMS
and
(2.47)
l-dl-2h h
1
7
-s
< r <
1+.\/1-2h
1
7
-s
<
where h = Kv/(l 8 . Then t h e CM sequence {y,(.)j given by Y ~ + ~ = ( . )TJ(y,)(.) converges uniformly t o t h e unique solution y * ( * ) of (2.32), (2.33) i n S and t h e rate of convergence is given by (2.31).
Now let us use the results of the appendix of Chapter 3 to obtain a convergence theorem in the case where $ ( e , y , s) is Lipschitz in y . In particular, we have the following. THEOREM 2.48. Let y o ( - ) be t h e solution of (2.36) and l e t = S ( y o ,r). Suppose that (i) f ( s ) i s integrable in s; (ii) $ ( ~ , ys), i s measurable i n s for each fixed y and continuous i n y for each fixed s; (iii) II $(%Y1 > s) - +(%Y2 > 411 K(E, s)ll Y1 - Y2 II for all y1 , y 2 i n t h e range of S where K ( E s) , is an integrable function of s; (iv) 11 $ ( ~ , ys)ll, m,(s) where mAs) ds < m; and (v) there are real numbers 7 and cy. w i t h 7 3 0 and 0 a < 1 such that
S
<
Ji
<
I1 W Y O ) -Yo I1 =
(2.49)
<
1 1 GJ(C4 9(%Y&), 4 /I G 1
ds
rl
(2.50) 1 7
(2.51)
Then t h e C M sequence {yn(*)jgiven by Y , + ~ ( - )= TJ(y,)(.) converges uniformly t o t h e unique solution y*(.) o f (2.32), (2.33) i n S and t h e rate of convergence is given by
IIY* -Yn II
< a" IIY1
-
Yn
11m
-
4.
Proof. All that we need show is that 0 TJ 0 s is majorized by the left-hand side of (2.50). Now, if u(.) and v(-) are in 3, then
/I T'(u)(t) - TJ(v)(t)ll <
and the result follows.
s' II
GJ(4S){+(%
49,s)-
+(€,
v(4,s) IIldS
184 5.3.
5.
APPLICATION TO OSCILLATION PROBLEMS
Some Second-Order Examples
Here we begin by considering the TPBVP f
(3.1)
+ A x + .f(x) x(0)
*(O)
~
=
0
x(7r) = 0,
- *(T)
=0
where X > 0 and E > 0 are parameters. We note that this is an almost linear type of problem with periodic boundary conditions. We shall use the convergence results of the previous sections to obtain conditions on f(-)which insure the existence of solutions of the TPBVP [i.e., of periodic solutions of (3.1)]. Now, letting and
x1 = x
x2 = kl = k,
we may write (3.1) and (3.2) in the vector form (3.3)
or, in the form
2
= AX
+ Ef(X),
Ix(0) - Ix(77) = 0 where (3.5)
and I is the identity matrix. We let
be the fundamental matrix of the linear system x =
Ax. Then
5.3.
SOME SECOND-ORDER
For convenience, we let A be written as
= v2
with v
EXAMPLES
>0
185
so that W ( t , s) can also
T h e set J will be a boundary-compatible set if and only if det(1 - W(T,0)) # 0 , i.e., if and only if
or, equivalently, if and only if v # 2k or A # 4k2
(3.9)
for k = 0, 1, . . . . If X problem x
=
4k2,then h is an eigenvalue of the linear
+ Ax = 0,
x(0) - x(77) = 0,
k(0) - k ( T ) = 0
+
which has the family of solutions a cos 2kt b sin 2kt. If A is an eigenvalue, then we can rewrite (3.1) in the form
x
+ (A - e)x + . { f ( x ) + x} = 0
and apply the results which we shall soon derive for the case where A is not an eigenvalue. We leave this to the reader and so, shall assume from now on that A( #4k2)is not an eigenvalue of the linear problem. I n other words, J is a boundary-compatible set. Assuming that f(.) is continuous, we deduce from Theorem 4.1 of Chapter 3 that the TPBVP (3.3), (3.4) has the equivalent integral representation
186
5.
APPLICATION TO OSCILLATION PROBLEMS
(3.10)
x(t) =
sw n
GJ(t,s){cf(x(s))}ds
where GJ(t,s) is the Green's matrix corresponding to the boundarycompatible set /. Writing (3.10) in component form, we have
for t in [0, n]. Thus, we need only calculate G;,(t, s) and G;,(t, s) to obtain the estimates required by the convergence theorems. We first note that [I - W ( n ,0)I-l is given by v-l
1 -
It follows that
v
1
1
sin v7r
-
(3.13)
1 2(1 - cos vx)
(
;I
(
2
cos v n
1
cos v7r
W ( t ,O)[I - W(n,0)I-l
sin v n
-
is given by V7r
-2sin v t - - sin2
2v-Isinv
VT
-2vsin v t - - cos-
2
-2sinv
Thus, in order to compute G{,(t, s) and G&(t,s), we need only multiply the second columns of the matrices W ( 0 ,s) and W(r,s) by the matrix (3.13). We find that (3.14) G{,(t,s) = -
sin v(t sin v(t
~ / 2 cos ) v(s - n/2) , v(l - cos vn)
O<s
n/2) cos v(s - 3n/2) , (1 - cos v7r)
t < s < n
-
-
5.3. SOME (3.15) G i 2 ( t ,S)
= -
-
-
sin v(t
187
SECOND-ORDER EXAMPLES -
(1
n/2)sin v(s - n/2) -
cos un)
,
sin v(t - n / 2 )sin v(s - 3n/2) , (1 - cos vn)
O<s
or equivalently that (3.16) G;,(t,
S) =
-
(3.17) Gi,(t, S)
=
-
sin v(t
+s
-
sin v(t
+s
cos v(t
+s +s
-
s)
,
o < s < t
+
- 2n) sin v(t - s - n) , 241 - cos v7r)
2(1
cos v(t
+
sin v(t cos vn)
- n)
241
cos v(t cos un)
77) -
-
-
s)
27i) - cos v(t - s 2(1 - cos)..v
-
O<s
3
- 77)
t < S < T
,
t<s
where v = 6. We are now ready to apply the convergence theorems. To illustrate what is involved, let us first suppose that 0 < h 2 and that we wish to apply the method of contraction mappings. T h e operator TJ is given by
<
and its derivative is given by
(3.19)
188
5.
APPLICATION TO OSCILLATION PROBLEMS
if af/ax is defined and satisfies the conditions of Section 8 of Chapter 3. As our initial guess, we take y ( t ) = 0 and so the estimate for 77 becomes (3.20) But
and so, we may take (3.21) where v
7 = E If(0)I max(1 l/v(l - cos vn)I, 1 l / ( l =
-
cos v n ) l )
l/X. Now, as a (somewhat coarse) estimate for a,we have
(3.22) where (3.23)
m ( v ) = max{l
l/v(1
-
cos v n ) l , I l / ( l
-
cos vn)i}
s
and y(-)is an element of the sphere = s(0,r ) . If af/axis continuous, then, since the values y ( t ) of the elements y(.) of s ( 0 , r )lie in a compact set, there is an M ( r ) such that (3.24) For example, if f(x) = x2/2,then we may take M ( r ) = r . It follows that an estimate for OL is given by (3.25)
01
=
m ( v ) M(r)
and so, we have the following.
THEOREM 3.26. Suppose that f(.)is continuously differentiable
and that
5.3.
Then (3.1) has a unique periodic solution in
For example, if h
2 if
=
1 and f ( x )
<2
and
=
x2/2
S
or, equivalently, if E
<
Er
E
< 2r[(l -
= 2r/(l
+ r”.
Similarly, if h = 1 and f ( x ) = cos x, then 2 a unique periodic solution in s(0, Y ) if E
<2
and
r
=
S(0,r ) .
+ 1, then we deduce that
+ x + 4 x 2 / 2 + 1 ) = 0 has a unique periodic EY
189
SOME SECOND-ORDER EXAMPLES
solution in s(0,r )
E Y ) / ~ ]
+x +
E
cos x
=
0 has
2 4 2 - E).
T h e main point here is not the explicit calculations or estimates but rather the use of the convergence theorems to obtain proofs of the existence of periodic solutions. A similar technique can be applied to obtain periodic solutions “near” any of the “eigensolutions” ak cos 2kt b, sin 2kt. T h e various other convergence theorems (e.g., on Newton’s method) can also be applied to obtain periodic solutions. These applications are left to the reader. A general theorem analogous to Theorem 3.26 is the following.
+
T H E O R E M 3.29. Let yo(.) be an element of V([O, T],R,) and let S = S(yo,Y ) . Suppose thatf(.) is continuously differentiable so that supyESIl(afIax)(yl(~))II M for some M > 0. Let
<
(3.30)
7 = II Y&.)/I
+4
4 ll.f(YO,l(~))Il
where m(v) i s given by (3.23). If
(3.31)
Ern(V)M
<1
and
(3.32) then (3.11, (3.2) has a unique solution y*(.) in S and t h e sequence y,(.) = T J ( y n P l ) (converges -) uniformly to y*(-)(see Theorem 5.8 of Chapter 3).
190
5.
APPLICATION T O OSCILLATION PROBLEMS
We now turn our attention to the forced version of (3.1), (3.2), i.e., to the TPBVP
+ +
(3.33)
i Ax
(3.34)
where h
x(0)
-
x(7r) = 0,
€f(X)
= g(t)
1(0)- k(7.r) = 0
> 0 and E > 0 are parameters. We have the following.
THEOREM 3.35. Let yo(-) be an element o f %([O, T],R,) and S = S(y,, r ) . Suppose that g(.) is continuous and that f(.)i s continuously differentiable so that supyeSIl(af/ax)(yl(s))ll M for some M > 0. If let
<
€rn(V)M < 1
(3.36)
and (3.37)
where m(v) i s given by (3.23), then (3.33), solution y*(-) i n S.
(3.34) has a unique
This is simply a rephrasing of Theorem 5.8 of Chapter 4 with = 4 4 M and 77 = II YO(‘)/I 4 v ) G llf(Y0,1(9)Il II g(*)lll. Note that (TzlJ)’is still given by (3.19) but that TJ is given by Proof.
+
+
rather than by (3.18). As an illustration of the theorem, we letf(x) = x3/x andf(t) = cos 2t. Then af/ax = x2 and M = M ( r ) = r2 for yo = 0. We deduce that if E ~ ( V ) Y< ~ 1 and m(u) r(1 - em(v)r2), then (3.33) has a unique periodic solution in S = s(0,r ) . For example, if X = 9 and r = 1, ex3/3 = cos 2t will have a unique periodic solution then 2 + 9x xd*(t) with I x<*(t)l I if E 1. Moreover, limc+oxc*(t) = (cos 2t)/5 is the periodic solution of 2 9x = cos 2t.
<
+
<
<
+
5.3.
191
SOME SECOND-ORDER EXAMPLES
We again leave the task of interpreting the various other convergence theorems to the reader. Let us now turn our attention to problems of the form
+ +
(3.39) (3.40)
2 Ax Ef(x, t) = g(t) x(0) - x(n) = 0, k(0) - k(n)
=0
where h > 0 and E are parameters. The basic convergence theorem becomes the following.
THEOREM 3.41.
Let yo(.) be an element of %([O, T],R,) Suppose that g(.) is continuous and that IIf(X, 4 1 k ( S ) , ll(af/ax)(x, s)ll P(S) on the range of where p ( ~ds ) = M < 00. If and let
Ji
S
<
=
S(yo,Y).
-Em(v)M < 1
(3.42) and
for v ( . ) in %([O,
<
n ] , R2).
s
192
5.
APPLICATION TO OSCILLATION PROBLEMS
,411 analogous result can be obtained when f(x, s) is Lipschitz in x by using the results of the appendix to Chapter 3. We leave this to the readcr. it'e note also that if yo(.)is a solution of the linear prohlem 2 Ax g(t), x(0) x ( n ) = 0, i ( 0 ) - i ( v ) 0, then the estimate (3.43) will take thc form
+
~
:
~
Now let us examine an explicit example. Consider the TPBVP i-1- w2x
(3.47)
-1
x(0) - .T(Tr)
E
-=
c 0,
i
a,(f)sJ = a cos
k(0)
~
2t
k(7r) = 0
with w 212. We observe that x(t) = 0 is a solution of the linear problem associated with (3.47) [i.e., of 2 02x 0, x(0) = x(n-), i(0) i ( r ) ] .So we let yo(.) = O(.). Then 11 y,,(-)/I= 0 and I1 ao(*)I/. Since ( a f i q x , t ) = 2:=1 a,(t)jxj-l, we have llf(y",J(.), .)I1
+
:
~
(3.48) If
Y
< 1, then we may take
(3.49)
if the aj(.) are integrable. Thus, the estimate (3.42) will be satisfied if (3.50)
and the estimate (3.43) will hold if (3.51)
If (3.50) and (3.51) are satisfied, then (3.47) will have a unique solution
5.3.
SOME SECOND-ORDER EXAMPLES
in the sphere S(0, r). In particular, if a periodic solution if
If
w
a
193
3 0, then we will have
3 1, then m ( w ) = 1/(1 - cos w r ) and (3.51) becomes
and so we will have a periodic solution if 1 - cos wm - a > 0 and is sufficiently small. Suppose now that instead of taking yo(-)= O(-) we take yo,l(-) = [ a / ( w z- 4)] cos 2t and yo,2(.)= -[2a/(w2- 4)] sin 2t so that yo(-)is the solution of the linear problem associated with (3.47). Then E
and we have
if the
a j ( * ) are
integrable. Thus, the estimate (3.42) will be satisfied if
and the estimate (3.46) will be satisfied if
with M ( r ) given by (3.55). For suitable choices of E and r , we can see that the periodic solution obtained will differ from that obtained for the initial guess O(.).
194
5.
APPLICATION TO OSCILLATION PROBLEMS
We conclude with a consideration of problems of the form (3.58)
i
(3.59)
x(0)
-
+ h.*. + €f(X, 8,t ) x(n)
= 0,
8(0)
=g(t) ~
8(Tr) = 0
where h > 0 and E are parameters. T h e basic convergence theorem becomes the following.
THEOREM 3.60. Let yo(*) be an element of %?([O, T], Rz) = S(y,, Y). Suppose that g(-) is continuous and that Ilf(Y1 > Yz 4 G d s ) , lI(?f/aY)(Yl ,y2 4 (CL/2)(s) on t h e range of S where Jip(s) ds = M < m. If and let S 7
?
(3.61)
Ern(V)M
<
and
(3.62) 11 Y"(.)ll 1- 4
V ) G
Ilf(YU,l(.)> Yo,z(.),
*)I1
+ II ,e(.)ll> G (1
-
4 4 M k
where m(v) is given by (3.23). then (3.58), (3.59) has a unique solution y*(.)in S.
An analogous result can be obtained when f(y, , yz , s) is Lipschitz in y l , y 2 using the results of the appendix to Chapter 3. We also note that if yo(.)is a solution of the linear problem x Ax = g ( t ) , x(0) - x ( n ) = 0, i(0) - i ( ~ =) 0, then the estimate (3.62) takes the form
+
(3.64)
r(0)
-
x(7r) ==
0,
k(0) - Q ( T r )
+
=0
with w = (2n l)-l, n 3 1. We let yo(-)be the solution of the forced linear problem associated with (3.64) so that yo,,(t) = A cos 2t and ~ ~ , ~=( -2A t ) sin 2t with A = B/[1/(2n 1)2 - 41. Now
+
5.3.
SOME SECOND-ORDER EXAMPLES
195
and so we may take as an estimate (somewhat crude) (3.65)
M
= M(r) =
(i
bj(2,)(2A
5=0
+
The estimate (3.61) will then be satisfied if
and the estimate (3.63) will be satisfied if (3.67)
Thus, if both (3.66) and (3.67) hold, then (3.64) will have a periodic solution in S.
CHAPTER 6
SOME NUMERICAL EXAMPLES
6.1.
Introduction
We examine the numerical solution of some simple problems in order to obtain a better appreciation for the practical aspects of the iterative methods discussed in Chapters 4 and 5. We consider two “standard” trajectory optimization problems and a simple oscillation problem. Both trajectory problems are concerned with a low-thrust orbital transfer from an Earth to a Mars orbit. T h e oscillation problem is concerncd with a simple spring having a nonlinear restoring force. T h e first trajectory problem is solved by Newton’s method using three different procedures for converting the variable-interval TPBVP into a fixed-interval TPBVP. We compare these procedures and also discuss the effect of different initial guesses and of different grid sizes for the numerical integration routine on the “convergence” of the method. I n addition, we consider the modified Newton method and evaluate the convergence factor K of Kantorovich’s theorem. T h e second trajectory problem is solved by Picard’s method. We examine a procedure for converting this orbital transfer problem into an almost linear rendezvous problem and then apply Picard’s method. T h e oscillation problem is solved by the third-order multipoint method. We discuss the applicability of the main convergence theorem on multipoint methods in the light of this problem. A particular version of the convergence theorem is also given. A final remark concerning the computer programs is in order. T h e programs were designed primarily for illustrative purposes and not necessarily for maximum accuracy and efticiency. Thus, the actual numerical results are not optimally precise but rather are indicative.
196
6.2.
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS ORBITAL TRANSFER
197
Constant Low-Thrust Earth-to-Mars Orbital Transfer
T h e problem considered in this section is probably one of the best known trajectory optimization examples in the literature. It has been treated by various authors using a variety of methods (e.g., Lindorfer and Moyer [Ll], Kelley et al. [K6], McGill and Kenneth [M3], Kopp et al. [KlO], and Handelsman [H5]). T h e problem involves the determination of the thrust angle history for the minimum time transfer from an Earth orbit to a Mars orbit of a low-thrust space vehicle. T h e problem is simplified in that the orbits of both Earth and Mars are assumed to be circular and coplanar. I n addition, the gravitational attractions of the two planets on the space vehicle are neglected. T h e following equations are assumed to govern the transfer [M3] + = u
lj=--+
uv
T~~~ e
Y
m, + m t
Here Y is the distance from the sun, u is the radial velocity, z, is the tangential velocity, p is the gravitational constant, T is the thrust, 0 is the control angle (measured relative to the tangent of the local circular orbit), m, is the initial mass, and m is the propellant consumption rate. (Numerical values for T , m, , and m are given by McGill and Kenneth [M3, p. 17641.) At the beginning of the maneuver the space vehicle is assumed to have a velocity and radial position corresponding to the orbit of the Earth, while at the end, its velocity and radial position correspond to the orbit of Mars. This leads to the boundary conditions (see McGill and Kenneth [M3, p. 17651) 1.000,
r ( t f ) = 1.525
u(t,) = 0.000,
u p f ) = 0.000
~ ( t , )= 1.000,
~ ( t f= ) (1.525)-'/'
Y(t,) =
(2.2)
in dimensionless variables. A gravitational constant p = 1.0 and a time unit equal to the time it takes the Earth to cover one radian (58.18 days) are used. Application of the Pontryagin principle to this minimum-time problem leads to a TPBVP defined on an interval with a free end
198
6.
SOME NUMERICAL EXAMPLES
point. In order to apply any of the iterative methods discussed, it is necessary to convert the TPBVP into a problem defined on a fixed time interval. Several procedures can be used for this conversion. First, there is the procedure followed by McGill and Kenneth [M3], who replace the minimum time problem by a sequence of radius maximization problems and iteratively adjust the final time so that the maximum radius coincides with the required value of the radius at the end of the maneuver. Another procedure is to treat the problem as a regular minimum-time problem and to standardize the resulting TPBVP using Long’s method [L2]. For that purpose, the time variable t is replaced by the product of a variable scale factor “a” and a new independent variable s which varies between 0 and 1, i.e., (2.3)
t = as.
(In the case at hand, we can conveniently set to = 0.) T h e first effect of this change of variable is that all right-hand sides of the differential equations are multiplied by a since dylds = a(dy/dt). A second and more important effect of this change of variable is that the scale factor “a” can be considered a new state variable defined by the trivial differential equation dajds = 0. As pointed out by Long [L2], this leads to a more unified application of the iterative methods than the “mixed” procedure of McGill and Kenneth. A third procedure which differs only slightly from the second consists of the introduction of the change of the time variable before, instead of after, the application of the Pontryagin principle. T h e scale factor a is then treated as an ordinary state variable and the optimization problem consists of the minimization of this new state variable. This leads to still another TPBVP. We discuss the computational aspects of each of these three procedures, which we call, respectively, Procedures A, B, and C, in the sequel. In their procedure for the solution of the problem, McGill and Kenneth start with a guess t,,o for the total flight time and determine (with the aid of the Pontryagin principle and Newton’s method) the maximum radius T , , ~that can be reached in that time. If this radius does not correspond to the radius of the orbit of Mars, then a new guess for the final time is determined from the general algorithm
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS
ORBITAL TRANSFER
199
where tf,-l = 0 and Y ~ , - = ~ 1. T h e actual optimization problem which is (repeatedly) solved in this procedure is thus a maximum radius problem rather than a minimum time problem. Application of the Pontryagin principle to this maximum radius problem proceeds as follows: the Hamiltonian function for the problem is given by (2.5) H
+ A,
= A,u
CL
V2
- - A,
-
r
r2
+ A,
From
~
+
-
A,
uv
7
e + A, m,T cos +
mt
T cos e T sin 0 mo mt - A, rn, mt
aH
+
- =aeO = A ,
and
T sin 0 m, kt
+
T sin I3 rn, kt -
a2H - -A, a02
+
T cos 0 m,
+ mt
it follows that the Hamiltonian has a maximum for 0 = arctan-A, A,
or equivalently, for sin 19 =
A, dAu2
+
x2 ,
,
case =
A, dAu2
+
A,2
*
Substituting this value for 8 back into the equations of motion (2,1), adding the equations for the adjoint variables and employing the change of variables (2.3), where ''u" is now a known scale factor (u = t f ) , we obtain the TPBVP" Y' = a[u]
[ (- f + 2 7 ) a [ A, + A, *I 2v [ . + A, "1
A,'
=
A,'
=
A,'
= a - A, -
CL
a -A -
-
I,
(+ uv
-
Y
Y
* W e use the prime to denote differentiation with respect to s.
6.
200
SOME NUMERICAL EXAMPLES
with boundary conditions r(0) -= 1.000,
r ( 1 ) free
u(0) = 0.000,
u(1) = 0.000
v(0)
=
~ ( 1 )= (1.525)-l/’
1.000,
h,(1) free,
=h
O
aK
-=
j
h u ( l ) = PI
hu(2)
=P2
ar
= 0.8098
h,(-I)
free
T h e Pontryagin principle implies that if A, is nonpositive,* then the solution of this ‘I‘PBVP is a candidate for the solution of the optimal control problem. McGill and Kenneth [M3] make use of a very interesting choice for the scale factor A, . Instead of choosing the “usual” value A, = - 1 which would have led to A,(l) = 1.0, they choose a value for A, which makes h,(O) = 1.0. Practically, this means that they fix the initial value of A, instead of its final value. Th is choice for A, leads to a considerable simplification of the numerical computations as there are now only two final conditions to be satisfied. T h e boundary conditions which have to be satisfied in McGill and Kenneth’s procedure (or Procedure A) now become r(0) = 1.000 (2.10)
u(0) = 0.000,
u(1) = 0.000
~ ( 0=) 1.000,
~ ( 1 )= 0.8098
h,(O)
=
1.000
In Procedure B, the problem is treated as a regular minimumtime problem. T h e Hamiltonian in this case is
-
uv htlr
e + h, m,T cos +
i t
’
As before, the Hamiltonian has a maximum for 0 given by (2.6) or
* In order to be consistent with the literature we follow the convention of Pontryagin { P 3 } and take A, to be nonpositive.
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS ORBITAL TRANSFER
201
(2.7). T h e TPBVP that results from the substitution of (2.7) into the
equations of motion, the addition of the adjoint equations and the introduction of the change of variable (2.3) is given by the same differential equation (2.8) and almost the same boundary conditions. T h e difference in the boundary conditions lies in the conditions for r( 1) and A(, I), which now become (2.12)
~ ( 1 )= 1.525
and
h,(l)
free.
T h e other boundary conditions remain the same. T h e scale factor “a,” which equals the final time, is now considered a variable rather than a given constant. Therefore, the trivial equation a‘ = 0
is added to the set of differential equations (2.9). T h e boundary condition corresponding to this extra state variable follows from the condition that the Hamiltonian at the endpoint equals zero. This yields
or, after substitution of the known values for r( l), u( l), v(l), and p, (2.13)
T h e TPBVP that has to be solved in Procedure B is thus given by the differential equations (2.9) combined with a’ = 0 and the boundary conditions ~ ( 1= ) 1.525 ~ ( 0= ) 1.000, (2.14)
u(0)
= 0.000,
~ ( 0= ) 1.000, ma
u(1)
= 0.000
~ ( 1= ) 0.8098
+1 ma [A,2(1) + Av~(l)l”2= - A o .
6.
202
SOME NUMERICAL EXAMPLES
I n contrast to the boundary conditions for Procedure A, these boundary conditions involve a nonlinear condition. I n addition, there are four conditions to be satisfied at the end point instead of two. On the other hand, the solution of this TPBVP is the actual candidate for the solution of the optimization problem and not an intermediate result as in Procedure A. I n Procedure C, the new state variable a defined by (2.3) is introduced before the application of the Pontryagin principle. This means that instead of the equations of motion (2.11) the system equations are taken to be r‘
= a[.]
U’=a
(2.15)
v’=a
[:- - - + r2 [ “,“+ --
T sin 0 m, mas
+
T cos 8 m, mas
+
a‘ = 0.
1
i
T h e objective now is to minimize the value of a at the terminal point, i.e., K = a(1) = a. T h e Hamiltonian for this minimization problem is (2.16)
If
= X,a[u]
+ X,a
T sin 8 m, mas
+
+ Xvu [- 7+ m, + mas uv
T cos 0
1
As before, this Hamiltonian has a maximum for 6’ given by (2.6) or (2.7). Substitution of this value of 6’ into the equations of motion (2.15) and addition of the adjoint equations leads to a TPBVP given by the set of differential equations (2.8) together with the trivial equation a‘ = 0 and the equation for the adjoint variable A, corresponding to “a”
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS
ORBITAL TRANSFER
203
or (2.17) A,'
= - A,u
-
Au
[ ? ;] --
-
T h e boundary conditions for the TPBVP are given by ~ ( 1= ) 1.525 u(1) = 0.000 ~ ( 1= ) 0.8098
r(0) = 1.000, u(0) = 0.000,
(2.18)
~ ( 0=) 1.000, X,(O)
= 0.000,
A,( 1)
= A,(
GO).
I n comparison with both Procedures A and B, the TPBVP to be solved in Procedure C is of eighth order with four boundary conditions at the initial point and four at the final point. I n contrast with the TPBVP in Procedure B, the boundary conditions are linear and in contrast with Procedure A, the solution of the TPBVP is a candidate for the solution of the minimum-time problem instead of just an intermediate result. T h e nonlinear TPBVP's corresponding to each of the Procedures A, B, and C were numerically solved by means of Newton's method. As initial guess for the trajectory, we chose that used by McGill and Kenneth [M3, p. 1765]), i.e., 1.000 u0(s) = 0.000 Y,(s)
=
+ 0.525s
V o ( S ) = [ro(s)]-'/2
1.000 A,,,(s) = 0.5200 - -0.5000 A,,,(s) = 0.3000 = 0.000 X,,,(s)
=
for
< s < 0.5 < s < 1.0 0 < s < 0.5 0.5 < s < 1.0.* 0
for 0.5 for
for
* These functions are discontinuous at s = 0.5 and so, theoretically, cannot be used as initial guesses. However, they may be used in the computer calculations since the calculations are discrete.
204
6.
SOME NUMERICAL EXAMPLES
For the Procedure C, this guess was supplemented by an initial guess for the adjoint variable given by A,&)
=
-0.2000s.
Different guesses for the total flight time a = (tr) were tried for the TPBVP's of all three procedures. I n addition, an initial guess having the same form as that of McGill and Kenneth but slightly different numerical values was tried for the Procedure C. This guess had the form r0(s) = 1.000 0.525s uo(s) = 0.000
+
v&) A,,,(s)
=
[r0(s)]-1/~
= 0.5000 = 0.5000
==
-0.5000 0.5000 0.5000
=
-0.2000s.
-
A,,,(s) A,(s)
for
-=
< s < 0.5 < s < 1.0 0 < s < 0.5 0.5 < s < 1.0 0
for 0.5 for
for
are integrated by the same method as used for the derivation of the analytical solution of linear TPBVP's in Chapter 3 . Assuming that thc boundary conditions can be split into a set of initial conditions, g l ( y ( 0 ) ) = cl , j I , 2,. . . , m p and a set of final conditions, h,>(y( 1 )) = c, , h = I , 2, . . . , p -- m ,the method proceeds as follows (see McGill and Kenneth [M3]): first, the nonhomogeneous equation
<
Y:l
I1W
= F(Yn(49 s>
I-
2F - (YV(4, s)(Yn +l(S) aY
-
Yn(4
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS ORBITAL TRANSFER
205
is integrated starting from some initial vector 9n+1(0)which satisfies the linearized initial conditions
T h e generated errors in the linearized final conditions
are evaluated and stored. Next, the homogeneous linear equation
is integrated p - m times starting from p - m independent initial vectors Y ~ $ ~ ( Owhich ) satisfy the homogeneous part of the linearized boundary conditions, i.e.,
If the j t h component of y(0) does not appear in the initial conditions, then the vector Y2!1(0) = [O,
* *
. , o , Y 2 l , m >0 ,
* *
. ,01
with yAtl,j = 1.0 is a convenient choice for one of these p - m independent vectors yitI(O). After each integration, the numerical values of the homogeneous parts of the linearized final conditions
are evaluated and stored. Forming the ( p - m) x ( p - m) matrix D of the elements Ad,,, , i.e., D = [Ad,,,], the change Ay(0) to be added to the initial vector $n+l(0)in order to satisfy the terminal boundary conditions is given by a linear combination of the p - m vectors
206
6.
SOME NUMERICAL EXAMPLES
y$il(O), dy(0) = C ~ I ~ b l y ~ ~where l ( 0 )the , coefficient vector b can be found as the solution of the linear equation Db = -de. I n order to have a basis for comparison, the same norm was used for measuring convergence as used by McGill and Kenneth [M3], namely (2.19)
T h e iterative solution of the linearized differential equations was continued until this norm had a value smallert han some prescribed number (usually 1.0 x lop5). As a check on the accuracy of this limit solution, the nonlinear equations were integrated starting from the initial values of the limit solution. Then, the values of this trajectory at the terminal time were determined. T h e maximum absolute value of the difference between these terminal values and the given boundary conditions was taken as the accuracy or quality criterion of the limit solution. For the numerical integration of the differential equations, a modified fourth-order Runge-Kutta method was used. T h e RungeKutta routine requires the value of the right-hand sides of the differential equations at points in between the points for which the routine yields the value of the solution and also at those points where the solution is obtained. I n the present case, the right-hand sides of the differential equations depend on the value of the last-obtained trajectory at those intermediate points. Since these values were not available, they were obtained by linear interpolation. I n the sequel, all points where the right-hand sides of the differential equations are evaluated are called grid points. I n order to limit the computer time, use was made in many of the cases treated of a rather coarse grid of only 20 points on the interval [O, I]. T o check the validity of the results thus obtained, the effect of the grid size on the convergence of Newton’s method TPBVP’s was investigated. Also considered were possible advantages of a procedure in which a coarse grid is used in the beginning and a fine grid at the end. T h e change of grid size occurs as soon as a convergence criterion is satisfied for the coarse grid iteration. Some typical results of the investigation of the effect of initial guesses, grid sizes and procedures on the convergence of the application of Newton’s method to the solution of the problem are given in
6.2.
Procedure
Initial guess for “a”
Number of grid points
A
3.0
20 100 100 2011o o a
B
20
4.0
20 100 20/ 100“
3.0
20
4.0
20 60 100 20/100“
3.0
20
29
+
29 20 20 3 = 32
DIFFERENT PROCEDURES Computer time (sec) 41.4 121 2 121.2 60.6
Accuracy criterion 1.14 2.91 2.91 5.10
x 10-3 x
x
x 10-5
Final value for “ a ” 3.31911373 3.3 1931227 3.31931227 3.31911382
Divergent after first shift of “a” 8 6 8+3=11 11 8 7 7 8+3=11
16.2 50.4 41.4
1.14 x 10-3 2.93 x 2.95 x
3.31911364 3.31931239 3.31936227
21.6
1.14 x 10-3
3.31911382
18.0 40.8 66.6 47.3
1.14 1.97 2.84 2.64
x 10-3
3.31911379 3.31931996 3.31931227 3.31931174
x 10-5 x
x
Divergent
21 5
a Coarse grid of 20 grid points was (after convergence) changed into fine grid of 100 grid points. Total number of iterations is the sum of the iterations for the coarse and the fine grid, respectively.
ORBITAL TRANSFER
C
4.0
Total number of iterations
OF
CONSTANT LOW-THRUST EARTH-TO-MARS
TABLE IV NEWTON’S METHOD:COMPARISON
6.
208
SOME NUMERICAL EXAMPLES
TABLE \’ ~ l < \ \ ’ l ’ O X ’ S\113’fIOD, PItOCEDUl<E
A: BIIEAKDO\VN 01: NUMBER OF
ITiiRATIONS BETWEEN
SIllF7.S 01‘ T H E FINAL ‘rIXil<
1niti;il giic‘ss for ‘ “I ”
3.0 3.0 4.0 4.0 3.06
Number of grid points
20 100
20 100 20
Number of iterations between shifts of the final time ‘‘a”
1 o i 7 i 5 i 4-1 3 = 2 0 7 1 4 l 4 + 3 + 2 = 2 0 24 + co (divergence after 1st shift) 6 j 5 + 4 4 3+2=20 1 0 1 6 1 5 ’ 4 1 2 - 2 7
Comp;irablc data rcportcd by Moyer and Pinkham [ K I O ]
3.06
1 OO( ?)
5 + 3 + 3
12=13
’I’ablcs IV and V and Figs. 6.1-6.4. I n Table IV, criteria for the coniparison of the convergence of the applications of Newton’s niethod are listed for different procedures and grid sizes. T h e criteria arc: the number of iterations, the total computer time required, the absolute value of the maximum violation of the boundary conditions by the solution of the nonlinear equations, and the value of the minimum time found. Table V gives a breakdown of the number of itcrations required in Procedure A. T h e figures show the norms (2.19) plotted on a logarithmic scale versus the number of the corresponding iteration. These figures thus provide an illustration of the convergence rate (see Iiopp et ul. [KlO, Fig. 4, p. 1041). We discuss these results in sonw detail. \Vith regard to the effect of the initial guess on the convergence of Newton’s method, no definite trends were discovered. Of course, in thosc cases where the initial guess was very close to the exact solution, then Convergence occurred. A good example of the unpredictability of the effect of initial guesses is provided by the convergcncc behavior in the case where Procedure C is used: For both sets of initial guesses considered in Figs. 6.1 and 6.2, a guessed value of ( I - - 4.0 lead to a convergent iteration procedure, while the guessed value N -- 3.0, which is actually closer to the correct value a 3.32 (see ‘I’able IV), lead to divergence. It was found that in many of those cases where convergence did not occur, the well-known trick of applying a partial correction
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS ORBITAL TRANSFER
209
provided an answer. T o be more specific, the new approximation of being the solution yk+l of the linearized TPBVP, is determined from the relation j12+1 = PI; - j k ) where q is the correction (or relaxation) factor. Comparison of the convergence behavior of those cases in Figures 6.1 and 6.2 where a correction factor q = 0.5 is used and those cases where q = 1.0 shows clearly the usefulness of this “practical” trick.
5k+l, instead
+
I I
10-7
1
I
1
3
1
1
5
1
1
1
7
1
9
1
1
,
I1
Number of iterations
Fig. 6.1. Newton’s method, Procedure C, 20 grid points. Comparison of different initial guesses for a and of different values for the correction factor q : C1, a = 3.0, q = 1.0; C2, a = 3.0, q = 0.5; C3, a = 3.5, q = 1.0; C4, a = 4.0, q = 1.0; C5, a = 4, q = 0.5. Note: arrow indicates iteration after which correction factor q is changed.
210
6.
10-7
SOME NUMERICAL EXAMPLES
I
I
I
I
I
I
I
I
I
I
I
1 1 %
Fig. 6.2. Newton’s method, Procedure C, 20 grid points. Comparison of different initial guesses for a and of different values for the correction factor q : C1, a = 3.0, q = 1.0; C2. a = 30, q = 0.5; C3, a = 3.0, q = 1.0; C4, a = 4.0, q = 0.5; C5, a = 4, q = 1.0. Note: arrow indicates iteration after which correction factor q is changed.
As shown in Fig. 6.3, we found that of the two grid sizes tried, the fine grid resulted in a faster convergence rate than the coarse grid. T h e difference was particularly noticeable when the actual solution was approached. T h e reason for the faster convergence probably lies in the smaller truncation error for a fine grid. I n fact, it was noted that only in the case of a fine grid did the convergence rate resemble the quadratic convergence rate guaranteed by the
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS ORBITAL TRANSFER
21 1
theorems on Newton’s method. I n the coarse grid case, the rather large truncation error apparently obscured the quadratic character of the convergence of Newton’s method. As follows from Tables IV-VI, the faster convergence rates for a fine grid resulted in a reduction of the total number of iterations of 2 and 1, respectively, for Procedures B and C. For Procedure A, the difference in the total number of iterations was much larger for two reasons. First, Procedure A consists of
I I
I
3
I
I
5
I
I
7
I
I
9
I
Number of iterations
I
II
1
1
I c
13
Fig. 6.3. Newton’s method, Procedures A and C. Comparison of different numbers of grid points. Procedure A: A l , a = 3.0, 20 grid points; A2, a = 3.0, 100 grid points. Procedure C: C1, a = 3.0, 20 grid points; C2, a = 3.0, 20 grid points; C3, a = 4.0, 20 grid points; C4, a
= 4.0,
100 grid points.
212
6.
SOME NUMERICAL EXAMPLES
a sequence of several iterative solutions of radius maximization problems. Each of these solutions required a smaller number of iterations for the fine grid than for the coarse grid; the total number of iterations is thus the sum of these smaller numbers. Second, we found that the convergence rate in Procedure A was more sensitive to the grid size than the convergence rate in Procedures B and C. For the particular initial guess a = 4.0, this sensitivity was very marked (see Table V). I n fact, we found that for a = 4.0 Procedure A was divergent (after the first shift of the time scale factor “ a ” ) for the coarse grid and convergent for the fine grid. A breakdown of the total number of iterations for Procedure A into the sum of the numbers of iterations required in between the successive shifts of the time scale factor a is given in Table IV. It may be remarked that the total number of iterations for Procedure A can be reduced if for the first few radius maximization problems the adjustment of the time scale factor a is effected as soon as the solutions of the linearized problems start to converge instead of after they have converged. As would be expected, the grid size strongly affects the computer time per iteration and hence is one of the major factors determining the total computer time. Table IV shows that the grid size also strongly influences the accuracy of the final result, as indicated by the quality criterion. ‘These effects suggest using a coarse grid for the initial steps and a fine grid for the final steps. T h e listings in Table IV of the cases where this procedure was applied show significant gains in computer time. A comparison of the convergence of Newton’s method following the three different Procedures A, B, and C is given in Fig. 6.4 and Table IV. T h e comparison is slightly complicated by the fact that Procedure A diverged for the initial guess a = 4.0 and a coarse grid, whereas Procedure C diverged for the initial guess a = 3.0 for both a coarse and a fine grid. Only Procedure B converged for both initial guesses for a. Neither of the initial guesses a = 4.0 and a = 3.0, which were used for most of the numerical experiments, could therefore be used as initial guess for all three procedures. As expected, Procedure A required the largest number of iterations. Since there are only two, instead of four, boundary conditions to be satisfied at the end point, each of those iterations take less computer time than the iterations in the other two procedures. Despite this fact, Procedure A took roughly twice as much computer time as the other
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS ORBITAL TRANSFER
I
3
5
7
9
Number of iterations
II
2 13
13
Fig. 6.4. Newton’s method, 20 grid points. Comparison of the different procedures: A l , a = 3.0, Procedure A ; A2, a = 4.0, Procedure A ; B I , a = 3.0, Procedure B; 82, a = 4.0, Procedure 6;C1, a = 3.0, Procedure C; C2, a = 4.0, Procedure C.
two procedures (see Table IV). With regard to Procedures B and C, it follows from both Fig. 6.4 and Table IV that Procedure B is preferable to Procedure C. First, for the initial guess a = 3.0, Procedure B leads to a convergent iteration sequence while Procedure C results in a divergent sequence. Second, comparing computer times, we note that, for the same number of iterations, Procedure B leads to the desired result faster than Procedure C. T h e reason for this difference between the two procedures lies in the fact that there
214
6.
SOME NUMERICAL EXAMPLES
are more differential equations to be solved in Procedure C than in Procedure B. Since the computer program was made most efficient for Procedure C, the comparison between Procedures B and C would be more striking if the program were written to be most efficient for Procedure B. For the nonlinear TPBVP corresponding to Procedure C, the computational aspects of the modified Newton’s method were investigated. T h e algorithm used requires the solution of the linearized TPBVP’s
where, in contrast with the algorithm of Newton’s method, the matrices aF/ay, ag/ay,and ahlay are held fixed. For the numerical solution of this linearized TPBVP, the same procedures (of McGill and Kenneth) can be used. An important simplification arises as the homogeneous differential equation has to be integrated (as many times as there are unsatisfied boundary conditions) only for yo(s) instead of for each y,,(s). I t is clear that this simplification results in a considerable reduction of computer time per iteration. A family of initial guesses for the modified Newton’s method was generated by the application of Newton’s method for the first few iterations. I n this manner the influence of the initial guess on the convergence of the modified Newton’s method could be readily determined. T h e results of this investigation are given in Fig. 6.5 and Table VI. Figure 6.5 provides a good illustration of the importance of the initial guess for the convergence of the modified Newton’s method. T h e data seem to indicate that the initial guess is more critical for the modified Newton method than for Newton’s method. T h e improvement of convergence rate with a better initial guess is very clear in Fig. 6.5. Figure 6.5 also shows the surprising result that, when the change from Newton’s method to the modified Newton method is made at a late stage, the convergence rate increases. One
6.2.
PROCEDURE C: COMPARISON OF NEWTON’S METHOD AND
Newton
Modified Modified Modified Modified
after after after after
3” 4“
Number of grid points
4.0
20 100 20/100
4.0
5“
6” 4.0
Number of iterations
8 7 8+3=11
MODIFIED NEWTON’S METHOD Computer time (sec)
Accuracy criterion
Final value for “a”
18.0 66.6 47.3
1.14 x 2.84 x 2.64 x
3.31911379 3.31931227 3.31931174
20 20 20 20
15 9 7 7
18.6 15.6 13.2 15.0
2.26 9.97 1.16 1.14
x
x x x
3.32129359 3.31911382 3.31908238 3.31911370
100 100
9 7
57.6 55.8
1.27 x 1.21 x
3.31928119 3.31930909
Modified Newton’s method started with the (n - 1)th iterate of Newton’s method as initial guess.
ORBITAL TRANSFER
Modified after 4” Modified after 5”
a
Initial guess for “a”
THE
CONSTANT LOW-THRUST EARTH-TO-MARS
TABLE VI
21 5
216
6.
SOME NUMERICAL EXAMPLES
10’
I00
10.’
10-2
E z lo-‘ Io
-~
10-6
\\
lo-’ I
I
I
3
I
I
5
.
I
M5
I I I 7 9 II Number of iterations
13
Fig. 6.5. Procedure C , 20 grid points. Comparison of Newton’s method and the modified Newton’s method: 0, Newton’s method; M I , modified after 1 ; M2, modified after 2; M3, modified after 3 ; M4, modified after 4; M5, modified after 5; M6, modified after 6.
of the reasons for this strange result may well be a better adjustment
to the truncation errors in the case of the modified Newton method.
No significant improvement in convergence was found when the same cases were recomputed with a grid size of 100 points in the interval [O, 11. Table VI clearly shows the reduction in computer time per iteration. I n fact, the data show that if more than four Newton iterations are used, it is possible to achieve a reduction in overall computer time.
6.2.
CONSTANT LOW-THRUST EARTH-TO-MARS
ORBITAL TRANSFER
217
It should be noted, however, that the quality of the limit solution deterioriates if the modified Newton’s method is used. I n order to evaluate the practicality of the theorems of Chapter 4, an estimate of the convergence factor K was determined for Procedure C. Since the boundary conditions of this TPBVP are linear, K is given by
As noted in the remarks following the theorems in Chapter4, this type of expression is difficult to evaluate. Simpler expressions which provide a majorization of K are
or
These expressions can be computed by first evaluating a matrix P with elements
and a vector x with the components (2.20)
K” is then given by
\
Since it was clear that K” would be rather large, the convergence
218
6.
SOME NUMERICAL EXAMPLES
<
condition Kq will only be satisfied for very small 7. No effort was made to evaluate the supremum over the small sphere &‘(yo, r ) . Instead the second derivatives in (2.20) were evaluated for the limit solution obtained by the application of Newton’s method. T h e elements xj were taken equal to the suprema over t of the sums of the absolute values of these second derivatives. T h e numerical computation of the elements p i j of the matrix P can be carried out by determining, for particular i and j , the function g?(t, s) for all points of a grid in the square [0, I] x [0, 11 of the t-s plane and integrating this function over all lines of constant s and determining the largest of these integrals. This involves integrations which are complicated by the fact that there is a jump in many of the functions g:!(t, s) at the line t = s. T o keep the computation simple no attempt was made to use an elaborate integration scheme for these integrals; instead the average values of the functions I g$(t, s)I at the grid points along lines of constant t are taken as the values of the integrals (the interval of integration has length 1.0). Even with these simplifications, the computer program to determine K” was complicated. All second derivatives (for all t ) and all elements of the Green’s function matrix (for all t and s) had to be evaluated. T h e Green’s function matrix was determined as a matrix product. This product involves both the fundamental matrix and its inverse. These matrices were found, in turn, as the solutions of linear matrix differential equations. As a measure of the complexity of the computer program, it may be mentioned that the total number of computer instructions was comparable to the number of instructions in the original basic program for the application of Newton’s method. T h e actual computation of the number K” was carried out for the TPBVP of Procedure C using a coarse grid (20 divisions). This resulted in an estimate for K given by K“ E 5.3 x lo3. From this estimate, it follows that the practical application of the theorem can be considered as soon as the uniform norm of the difference between two successive iterations is smaller than 7 1/2K” g 9.4 x
<
6.3.
Variable Low-Thrust Earth-to-Mars Orbital Transfer
T h e second example concerns the optimization of the transfer of a low-thrust space vehicle from an orbit of Earth to an orbit of Mars. T h e difference between this and the previous example lies in the
6.3.
VARIABLE LOW-THRUST EARTH-TO-MARS
ORBITAL TRANSFER
219
assumption of a thrust which is variable in both magnitude and direction and in the use of a different optimization criterion. Instead of time, the criterion to be optimized is
where a, and a, are the planar accelerations and T is a fixed total flight time. It has been shown by Irving [Ill that in the case of a power-limited rocket J[u] is monotonically related to the total fuel consumption. Minimization of (3.1) is therefore the same as the minimization of total fuel consumption. T h e variable low-thrust Earth-to-Mars orbital transfer problem has been treated before by several authors (e.g., Melbourne and Sauer [M4, M5], and Van Dine et al. [Vl]) and numerical data have been published. T h e treatment of this problem as an almost linear optimization problem is undertaken here. T o convert the problem into an almost linear optimization problem, the motion of the space vehicle is considered relative to a coordinate system which is fixed to a hypothetical body moving in a circular orbit (around the Sun) between the orbits of the Earth and Mars. Coordinate systems of this type are rather common in studies of rendezvous maneuvers and transfers of space vehicles between neighboring orbits. Under the condition that the distance (and/or the velocity) of the space vehicle relative to the origin of the coordinate system is small in comparison with the radius of the orbit (or the orbital velocity, respectively), the equations of motion may be linearized. T h e resulting linearized transfer problem then becomes a linear optimization problem with a quadratic cost criterion and unconstrained control. This problem can be solved analytically. Solutions for the linear problem have been derived, among others, by Billik [B5] and Gobetz [G2]. Our treatment of the optimal lowthrust Earth-to-Mars orbital transfer can be considered as a nonlinear extension of Gobetz's work. Instead of neglecting the higher-order nonlinear terms, we carry these terms along as small perturbations. Neglecting, as before, the gravitational attraction of the two planets and considering only planar motion, the equations of motion of the space vehicle are
6.
220
SOME NUMERICAL EXAMPLES
Here Y is the distance to the Sun, 6 is the angular position of the space vehicle measured in the direction of the orbital motion, p is the gravitational constant, a, is the tangential thrust acceleration which is taken to be positive in the direction of decreasing 6 (i.e., opposite to the orbital motion), and av is the radial thrust acceleration which is taken to be positive in the direction of increasing r . Employing the usual perturbation procedure consisting of replacing r and 0 by, respectively, (3.3)
Y
= yo
+ dr,
0
=
0" + d0
where Y,, and 6" are the coordinates of the origin of the coordinate system, and substituting the known relations for the circular reference orbit (3.4)
f" = 0,
i" = 0 ,
0" = 0,
8,
=
W",
lr2?
=
WO2YO,
we can write the (3.2) in the form (Of)
(3.5) (08) =
+ 2 w " ~ ~ ( d+d )~"(d8)'-1-
3w02Ar
1
--
rn
+
2 ~ d~(d8) 0 dr(d8)'
[2W"(di) -t 2(41)(48) -1- a,] AT
yO(yo
+
Ay)
[2W"(di.)
+ 2(41)(48)+ a,].
I n terms of the new variables (see Gobetz [G2]) x = --do, y = -dr/ro, = wet, and the dimensionless thrust accelerations Cr = az.~02~o, a",, n,,/wo2r0,the equations of motion (3.5) can be written as a set of first-ordcr equations of the form
T
where the prime denotes differentiation with respect to
T.
6.3.
VARIABLE LOW-THRUST EARTH-TO-MARS ORBITAL TRANSFER
221
If y, ZL, and v are small (i.e., if the radial distance from the reference orbit and the velocities of the space vehicle relative to the origin of the reference orbit are small in comparison with the radius and the orbital velocity of the reference orbit), then the second- and higherorder terms in (3.6) are small in comparison with the first-order terms. Under these conditions, the system of equations is almost linear. (Given the upper and lower limits of y , u,and v, it would be possible in theory to determine a number E and write the equations in the proper form. For practical purposes this is neither necessary, nor desirable.) T h e underlying linear system is x’ = u u’ = 2v
(3.7)
y’
+ d,
=v
21‘ =
-2u
+ 3y + 2,.
T h e boundary conditions for an orbital transfer follow from the condition that the space vehicle at the beginning and at the end of the maneuver should have the velocity and radial position of the corresponding orbit. Assuming both orbits to be circular and coplanar with the reference orbit, the boundary conditions for the optimization problem are
x(0) (3.8)
= 0,
free
~ ( 7 ~ )
u(0) = (1
Y(0)
= YE
v(0) = 0,
1
1,
U(7f) =
(1
Y(Tf>
=YM
V(Tr)
= 0.
+
yM)-3’2
-
1
Here yE and y Mare the radial distances from the reference orbit of the Earth and Mars, respectively. If a new cost criterion (3.9)
which is clearly proportional to the original cost criterion, is introduced, then it follows that the variable low-thrust Earth-to-Mars orbital transfer problem can be formulated as the following almost linear control problem: determine Z J T ) and Z&T) which transfer the state of the almost linear system (3.6) from the initial state, given in
222
6.
SOME NUMERICAL EXAMPLES
(3.8), to the set of final states, given in (3.8), and which in so doing minimizes the cost (3.9). T h e Hamiltonian of the almost linear optimization problem takes the form
M
+ a"$) + p,u + pu [2v + a",
= +po(d,2
+pYv
+
[-zU + 3y -I- zU + ( I
+
-
1
(2VY
~
y)u2
-
zYu
From
+ 2uv + %Y)]
1 (1 +YY
- ____ p Y 2
+ 2y3)].
and
it follows that if p , minimum for
> 0,
then the Hamiltonian has an absolute
Substitution of these expressions into the equations of motion and addition of the adjoint equations with their boundary conditions results in the TPBVP given by x'
=
u) =
(3.10)
u
2v
y'
=
v
v'
=
-2u
P,' p!L'
-
1 [2vy (1 + Y )
Pu
- - - -~
Po
+ 3y
Pv
--
PO
0
-pZ
+
2pV
-1-
PU
+ 2uvl + (1 +1 YY Po [2y + y2] Pu
-
+ (1 + y)u2 ~
A,! = -3Pv - p (1u p y )-2 [2uv 1 +2P, [3Y ( 1 +Y)" ~
Pv'
- -py
-
2PU
2yu
1 [3y2 (1 +YI2
- ___
1 [2Vl - 2 P m (1 + Y )
1
+
-
~
2v] - p u
+ 3Y2 + Y31
+ p, (1 +1 Y ) [2y + 2u] -__-
+ 2y3]
+ Y k -Y1
. pv[u2 - 2u] _
PO(1
+ YI3
6.3.
VARIABLE LOW-THRUST EARTH-TO-MARS
(3.11)
x(0)
= 0,
u(0)
=
(1
Y(O) == YE v(0)= 0,
+ YE)-"'
X(Tf) -
1,
ORBITAL TRANSFER
223
free
u(Tf) = ( 1 $- yM)-3/2- 1
9
Y(.f)
= YM
'U(Tf)
=0
PZ(Tf>
P&f)
=0 =
P*
P,(Tf)
= t%
Pv(Tf>
= P3
I
fret-
T h e Pontryagin principle implies that the solution of the optimization problem satisfies the TPBVP. It may be noted that the differential equation for p , , together with the corresponding boundary condition, result in the trivial solution pZ(T) E
0.
This reduces the order of the TPBVP by one. If it can be assumed that, in addition to the earlier assumptions on y , u,and v, that pu/p, (or Zz)is small, then the TPBVP given by (3.10) and (3.11) can be considered an almost linear problem. I n that case an iterative solution by means of Picard's method, can be considered. T h e numerical solution of the TPBVP given by (3.10) and (3.11) by means of Picard's method was carried out for numerical data corresponding to an Earth to Mars orbital transfer in 160 days. T h e reference orbit was chosen so that the unit of time (i.e., the time in which a body in orbit covers one radian) was equal to 80 days. For this orbit the relation Y / r E = 1.23724 holds. T h e resulting initial and final conditions for the Earth-to-Mars orbital transfer are x(0)
= 0,
4 2 ) free
~ ( 0 ==z ) -0.37620,
42)
y(0)
==
y ( 2 ) = 0.23258
v(0)
= 0,
-0.19175,
= 0.26924
v ( 2 ) = 0.
These numerical data give an idea of the magnitudes of the numbers involved. Since the procedure of Picard's method is quite similar to the procedure of the modified Newton's method, the computer program
224
6.
SOME NUMERICAL EXAMPLES
used was basically the same as the computer program for Newton’s method. T h e numerical results are given in Figs. 6.6 and 6.7. These figures show the total thrust and thrust angle programs, respectively, as found l y solving the linearized version of the TPBVP and the exact nonlinear version using Picard’s method. I n addition, the results published by Melbourne and Sauer [M5] are plotted for comparison. ‘I’he agreement of the results of Picard’s method with the results of Melbourne and Sauer, which were obtained by a method based on the calculation of the orbital elements and computed for an elliptic hlartian orbit, is seen to be poor. T h e reason for the discrepancy may \$ell be the important effect (see Melbourne [M4, p. 17271) of the eccentricity of the Martian orbit on the minimum fuel control history. From a comparison of the solution of the linearized equations with Picard’s solution, the improvement of Picard’s solution over the linear solution is evident. Solution linearized equations
,
R
N
0
% 2.0~10-~
\
E 0 c .-
e
c
-
m
0 c
l 2 n
g
-
0
I.OXIO-~
t“
0
Fig. 6.6.
a
Earth-Mars
160
orbital transfer in 160 days: total thrust acceleration from different solution procedures (Melbourne and Sauer
= ( o r 2 + a y z ) * / zprogram
~51).
80 Flight time, days
6.3.
VARIABLE LOW-THRUST EARTH-TO-MARS
ORBITAL TRANSFER
225
27C
Melbourne and Sauer
,
0
80
Flight time ,days
160
Fig. 6.7. Earth-Mars orbit transfer in 160 days: thrust angle program from different solution procedures (Melbourne and Sauer [MS]).
I n order to check the dependence of the convergence of Picard’s method on the initial conditions, several different conditions were tried for the same program. T h e results of these numerical experiments are given in Table VII. This table shows the grid size, the number of iterations, the total computer time, and the quality criterion for the solution. I t follows immediately from the table that, as the absolute values of the initial conditions increase (which implies that the solution of the linear system becomes a worse approximation to the solution), the number of total iterations increases and the quality of the solutions degrades. This result is in line with the results for the modified Newton method. I t may also be noted from the table that the total computer times in all cases was relatively short. T h e numerical results discussed in this section clearly show the
226
6.
SOME NUMERICAL EXAMPLES
TABLE VII PICARD’S
Algorithm Picard
R/IETHOD:
COMPARISON
OF
DIFFERENT INITIAL
AND
FINAL RADII‘
Initial value Final value Number of Number of Computer Accuracy for y for y grid points iterations time(sec) criterion -0.19175 -0,19175 -0.1975
$0.23258 $0.23258 +0.23258
20 100 20/100
0 -0.1 0 -0.3 0 -- 0.5
-1 0.1 $0.1 -1-0.3 +0.3 -1-0.525 +0.5
20 20 20 20 20 20
13 13 13 9
9.0 26.4 27.2
+
6.0 7 6.0 7 8.4 12 16.8 32 17 10.8 Divergent
1.56 x 6.35 x 6.35 x 3.31 3.07 2.08 4.42 4.25
x x x x x 10-3
Picard’s algorithm throughout.
feasibility of Picard’s method for TPBVP’s for which approximate solutions can be determined from the linearized equations. For that type of problem Picard’s method provides a fast computational scheme for the related nonlinear problem.
6.4.
An Oscillation Problem*
Consider the nonlinear differential equation j(t)
+6~~+ (t)
&‘((t)
+ cos t = 0
which describes an oscillator with a nonlinear restoring force. We wish to determine periodic solutions of (4.1) with period 277 and so we impose the boundary conditions (44
* Sec
Y(0)- A 2 4 Bosargc and Falb [B7].
= 0,
j ( 0 ) -j(277)
= 0.
6.4.
227
AN OSCILLATION PROBLEM
The boundary value problem (4.1), (4.2) can be written in vector form as
(4.3)
where xl(t)
= y ( t ) and
xz(t) = j ( t ) . We now have the following.
<
THEOREM 4.4. Suppose that 0 < ,8 0.5 and that Y = ;-+.lo where .lo = do(l 4.16,8d0/2) and do = 0.2. Then t h e multipoint sequence xnF1 = $2(x,) with x,,(-)= O(.) converges t o a solution x* of (5.3) i n S = S(x, , Y) and t h e rate of convergence i s given by
+
(4.5) where h, =
4.16,8v0< 0.5.
Proof. We simply verify the hypotheses of Theorem 8.1 of Chapter 4. We first observe that
and that
j = 2
Thus, the hypotheses (i), (ii), and (iii) of Theorem 8.1 are satisfied.
6.
228
SOME NUMERICAL EXAMPLES
Moreover, if we let A(t) = (af/ax)(x,,(t)), B = ag/ax,a n d C = %/ax, then the set J {A(t), B, C> is a boundary-compatible set (as is easily checked). Now let 6 = 0. Then the inequality (8.2) holds in our case in view of the definition of J and (4.8). Moreover, the operator TJ is given by
1
211
T J ( x )=
(4.9)
G J ( t ,s)
0
[
-pxl"s)
-
cos s
where GJ(t,s) is the Green's matrix which corresponds to J . Writing (4.9) in component form, we have 277
T J ( x ) l ( f=)
n
(4.10)
~ { ~ S)[-&~(S) (t,
-
cos s] ds
TJ(x),(t)= J211yi2(t, s ) [ - P . ~ ~ ~ ( s) cos s] ds n
where (4.1 1 )
y;&
s)
1
~
= -C
1
~~
(4.12)
J
y2+,(t,s )
=
=
< <
~
C
cos 2(Tr
a . sin a(7r
C
a ~
C
cos a(7r
-
<s
t -1- s),
s
t < s
-
t -1- s),
s < t
< <
"n
t
4-t ) ,
s
~
for 0 s 2 ~0 , t 2n and where a Using (4.7) and the estimates
-\
+ f),
cos a(n - s
=
d6 and c = 22/6 s i n ( r d 6 ) .
2a [5 - cos(7ra)] 1 y & ( f ,s)/ ds .-,
~
0
C
we deduce that (8.4) holds in our case for K : 4.16p. Moreover, in view of the definition of l", we can readily check that (8.3) will be satisfied with d,, = 0.2 since TJ(0),(t)= (cos t ) / 5 and TJ(0),(t)=
6.4.
229
AN OSCILLATION PROBLEM
(sin t ) / 5 . As 8.5) holds by the definition of q o , all that remains is to verify (8.7) and (8.9).
+
<
since /3 0.5. Morevoer, since y6:; = 1 Kd0/2, (8.9) is clearly satisfied here. Thus, the theorem is established. Again an analogous theorem could be proved for any of the multipoint algorithms. T h e pair of linear TPBVP’s (8.14a) and (8.14b) here take the form
(4.13b)
*n+2.2
=
-(6
+ 2bn,l(t))xn+l.l + /%,1(2xn,l(t)
~n+l,l(O)= xn+1,1(2n),
xn+l,s(O)
-
zn.1)
-
cos t
xn+1,2(2~)
1
and Theorem 4.4 insures the convergence of the sequence x,, 1( -) to the solution of (4.3). T h e equations (4.13a) and (4.13b) were integrated numerically using a modified Runge-Kutta method and the results of the computations are indicated in Tables VIII and IX. Table VIII contains the number of iterations required for “convergence”* for TABLE VIII
B Iterations required
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
2
2
3
3
3
3
3
3
3
* Convergence is here
construed to mean that
where the tk are the points in the integration routine.
1.0
4
230
6.
SOME NUMERICAL EXAMPLES
various values of /3, while Table IX contains the actual solutions. We note that the actual computations converge for larger values of p than 0.5. I n other words, the convergence theorem is conservative as was to be expected. TABLE IX
ML-LTIIDOINT MIXHOD SOLErIoN OF OSCILLATION PRomEnc ACTUAL SOLUTIONS VERSUS
hq 0.0 0.271 0.471 0.671 0.871 n
I .2n 1.471 1.671 1.871 2a
0.1
0.2
0.3
0.4
0.5
-0.201338 - 0. I62459 -0.061 336 i 0.062288 -1-0.I6 1 170 +0.198668 +0.161173 -i 0.062295 0.161 173 - 0.162454 -0.201338
-0.202672 -0.163 I24 -0.060884 i 0.062786 -t0.160549 +O. 197334 +O. 160553 10.062793 -0.060876 -0. I631 18 - 0.202672
-0.204007 -0.163804 -0,060445 0.063299 0.159944 0.195999 0. I59947 0.063306 0.060472 - 0.163798 - 0.204007
-0.205343 0. I64500 - 0.060022 +0.063827 $0.1 59352 .194663 0.159355 0.063834 0.060014 -0.164495 -0.205343
-0.206682 -0.16521 2 -0.059614 +0.064369 +0.158775 1-0.193325 -I-0.158778 +0.064376 -0.059606 -0.165206 - 0.206682
0.6
0.7
0.8
0.9
1.o
-
-
-
-
~
0.0
0.271 0.4n 0.671 0.877 n
1.271 1.471 1.671 1.871 2n
-0.208022 -0. I65940 -0.059221 +0.064927 +O. I5821 2 4-0. 19 1984 -1 0.158215 +0.064934 -0.059213 0.165934 --0,208022 -
-0.209365 -0.166685 -0.058844 +0.065499 1~0.157662 1-0.190641 1 0.157665 i 0.065506 -0.058835 -0.166678 - 0.209365
-
0.2107 I2
- 0.167446
- 0.05848 1
+0.066087 +O. 157 126 +0.189296 t0.157129 -1-0,066093 - 0.058473 -0.167440 - 0.210712
-0.21 2062
-0.168224 -0.058135 1-0.066688 +0.156604 -1-0.187946 +0.156607 +0.066695 -0.058126 -0.16821 8 -0.212062
-0.21 3416
- 0.169020
-0.057805 +0.067305 $0.156095 +0.186593 4-0.1 56097 $-0.0673 12 -0.057796 - 0.16901 3 -0.213416
H. A. Antosiewicz, Newton’s method and boundary value problems (to be published). A2. H. A. Antosiewicz and W. C. Rheinboldt, Numerical analysis and functional analysis, Ch. 14 of “Survey of Numerical Analysis” (J. Todd, ed.), Chapter 14. McGraw-Hill, New York, 1962. A3. M. Athans and P. L. Falb, “Optimal Control: An Introduction to the Theory and Its Applications.” McGraw-Hill, New York, 1966. A3. M. Athans, T h e status of optimal control theory and applications for deterministic systems, ZEEE Trans. Autom. Control AC-I 1, 580-596 (1966). BO. S. Banach, “Theorie des Operations Lineaires.” Chelsea, New York, 1955. BI. R. 0. Barr and E. G. Gilbert, Some iterative procedures for computing optimal controls, Proc. I F A C Congress, 3rd, London, 1967. B2. R. E. Bellman, “Dynamic Programming.” Princeton Univ. Press, Princeton, N. J., 1957. B3. R. E. Bellman and R. E. Kalaba, “Quasilinearization and Nonlinear BoundaryValue Problems.” Elsevier, New York, 1965. B4. L. D. Berkovitz, Variational methods in problems of control and programming, J . Math. Anal. Appl. 3, 145-169 (1961). B5. B. H. Billik, Some optimal low-acceleration rendezvous maneuvers, A I A A J . 2, 510-516 (1964). B6. G. A. Bliss, “Lectures on the Calculus of Variations.” Univ. of Chicago Press, Chicago, 1946. B7. W. E. Bosarge, Jr., and P. L. Falb, Infinite dimensional multipoint methods and the solution of boundary value problems (to be published). B8. J. V. Breakwell, T h e optimization of trajectories, J . S Z A M 7, 215-247 (1959). B9. J. V. Breakwell, J. L. Speyer, and A. E. Bryson, Optimization and control of nonlinear systems using the second variation, J. S I A M Control Ser. A 1, 193-223 (1963). B10. A. E. Bryson and W. F. Denham, A steepest-ascent method for solving optimum programming problems, Trans. A S M E Ser. E ; J. Appl. Mech. 29, 241-251 (1962). co. M. Canon, C. Cullum, and E. Polak, Constrained minimization problems in finite dimensional spaces, S Z A M J. Control 4, 528-547 (1967). c1. E. A. Coddington and N. Levinson, “Theory of Ordinary Differential Equations.” McGraw-Hill, New York, 1955. Al.
23 1
232 c2. c3. c4.
c5. D1. GI. G2. G3.
H1. I€2. 143. 114.
H5. 11. 1<1.
Ii2. K3. K4.
K5. K6. K7. 1<8.
REFERENCES
L. Collatz, Einige Anwendungen funktionalanalytischer Mcthoden in der praktischen Analysis, Z. Aiigezu. Math. Phys. 4, 327-357 (1953). L. Collatz, I>as vereinfachte Newtonsche Verfahren bei nicht lineare Randwertaufgahen, Arch. Math. 5, 233-240 (1954). I,. Collatz, “Funktionalanalysis und numerische Mathematik.” Springer, Berlin, 1964; “Functional Analysis and Numerical Mathematics” (English translation by H. Oser). Academic Press, New York, 1966. R. Conti, Recent trends in the theory of boundary value problems for ordinary differential equations, Roll. Un. Mat. Ztal. 22, 135-178 (1967). J . Dieudonni., “Foundations of Modern Analysis.” Academic Press, New York, 1960. 1;. R. G a n t m x h e r , “ T h e Theory of Matrices,” Vol. I. Chelsea, New York, 1959. 12. W.Gobetz, Optimal variable-thrust transfer of a power-limited rocket between neighhoring circular orbits, AIAA J . 2, 339-343 (1964); Errata, AZAA 1. 2, 2237 (1964). A. A. Goldstein, “Constructive Real Analysis.” Harper and Row,. New York, 1967. J . Hale, On differentid equations containing a small parameter, Control. Dzff. Ec/.I , 215-250 (1962). J. I €ale, “Oscillations in Nonlinear Systems.” McGr;iw-Hill, New York, 1963. €1. Ehlkin, A maximum principle of the Pontryagin type for systems described by nonlinear difference equations, S Z A M J . Control 4, 90-11 1 (1966). 11. IIdkin, An abstract framework for the theory of process optimization, Brill. Amcv. Math. SOC.(to be published). hI. H;indelsm:in, Optimal free space fixed thrust trajectories using impulsive trajectories as starting iteratives, AZAA J . 4, 1077-1082 (1966). J. H. Irving, Low-thrust flight: variable exhaust velocity in gravitational fields, iii “Space ‘l’echnology” (H. S.Seifert, ed.), Chapter 10. Wiley, New York, 1959. R. E. Kalaha, On nonlinear differential equations, the maximum operation, and monotonic convergence, J . Math. Mech. 8, 519-575 (1959). L. V. Kantorovich, T h e method of successive approximations for functional equations, Actcz Mat/r. 71, 63-97 (1939). L. V. I
REFERENCES
233
K9. A. N. Kolmogorov and S. V. Fomin, “Elements of the Theory of Functions and Functional Analysis,” Vol. I. Graylock Press, Rochester, New York, 1957. K10. R. E. Kopp, R. McGill, H. G. Moyer, and G. Pinkham, Several trajectory optimization techniques, in “Computing Methods in Optimization Problems” (A. V. Balakrishnan and L. W. Neustadt, eds.). Academic Press, New York, 1964. L l . W. Lindorfer and H. G. Moyer, Application of a low thrust trajectory optimization scheme to planar Earth-Mars transfer, ARS J . 32, 260-262 (1962). L2. R. S. Long, “Newton-Raphson Operator; Problems with Undetermined Endpoints,’’ A I A A J., 3, 1351-1352 (1965). M1. R. McGill, Optimal control, inequality state constaints, and the generalized Newton-Raphson algorithm, J. S I A M Control 3, 291-298 (1 966). M2. R. McGill and P. Kenneth, A convergence theorem on the iterative solution of non-linear two-point boundary-value systems, Proc. Int. Astron. Cong., 14th, Paris, 1963. M3. R. McGill and P. Kenneth, Solution of variational problems by means of a generalized Newton-Raphson operator, A I A A J . 2, 1761-1 766 (1964). M4. W. G. Melbourne, Three-dimensional optimum thrust trajectories for power limited propulsion systems, ARS /. 31, 1723-1728 (1961). M5. W. G. Melbourne and C. G. Sauer, Optimum thrust programs for potver-limited propulsion systems, Astron. Acta 8, 205-226 (1962). N1. E. G. Nering, “Linear Algebra and Matrix Theory.” Wiley, New York, 1963. N2. L. W. Neustadt, Synthesizing time optimal control systems, J. M a t h . Anal. Appl. 1, 484-493 (1960). N3. L. W. Neustadt, An abstract variational theory with applications to a broad class of optimization problems. I. General theory,]. SIAM Control 4, 505-528 (1966). P1. B. Paiewonski, Optimal control: A review of theory and practice, AIAA J. 3, 1985-2006 (1965). P2. E. Picard, “Traite d’Analyse,” 3rd ed., Vol. 111. Gauthiers-Villars, Paris, 1928. P3. L. S. Pontryagin, V. G. Boltyanskii, R. V. Gamkrelidze, and E. F. Mishchenko, “The Mathematical Theory of Optimal Processes.” Wiley, New York, 1962. P4. W. A. Porter, “Modern Foundations of Systems Engineering.” Macmillan, New York, 1966. R1. W. Rudin, “Principles of Mathematical Analysis, 2nd ed. McGraw-Hill, New York, 1964. s1. J. Schroder, Neue Fehlerabschatzungen f u r verschiedene Iterations verfahren, Z. Angew. M a t h . Mech. 36, 168-181 (1956). v 1 . C. P. Van Dine, W. R. Fimple, and T. N . Edelbaum, Application of a finitedifference Newton-Raphson algorithm to problems of low-thrust trajectory optimization, Advan. Astron. Aeronaut. 17 (1966). v 2 . B. S. Vulikh, “Introduction to Functional Analysis for Scientists and Technologists.” Pergamon Press, New York, 1963. w 1 . J. Warga, O n a class of iterative procedures for solving normal systems of ordinary differential equations, J. M a t h . Phys. 31, 223-243 (1953). w 2 . H. Witsenhausen, Note on some iterative methods using partial order for solution of boundary-value problems, Lecture notes, Harvard-MlT-BrownLincoln, 1966.
AUTHOR INDEX
Numbers in parentheses are reference numbers and indicate that an author’s work is referred to, although his name is not cited in the text. Numbers in italics show the page on which the complete reference is listed.
Akilov, G. P., 4(K3), 5(K3), 7(K3), 9(K3), ll(K3), 12(K3), 32(K3), 33(K3), 35(K3), 45(K3), 232 Antosiewicz, H. A., 4(A2), 36(A1), 42(A1), 45(A2), 78(A1), 114(A2), 175(A2), 231 Athans, M., 2(A3), 108(A3), 231
Denham, W. F., 3(B10), 231 DieudonnC, J., 12(D1), 52(D1), 232 Edelhaum, T. N., 3(V1), 219(Vl), 233 Falb, P. L., 2(A3), 45(B7), 108(A3), 150(B7), 226(B7), 231 Fimple, W. R., 3(V1), 219(V1), 233 Fomin, S. V., 233
Banach, S., 83(BO), 103(BO), 231 Barr, R. O., 3(B1), 231 Bellman, R. E., 3(B2, B3), 5(B3), 138(B3), 139(B3), 143(B3), 231 Berkovitz, L. D., 2(B4), 231 Billik, B. H., 219(B5), 231 Bliss, G. A., 231 Boltyanskii, V. G., 2(P3), 104(P3), 106(P3), 107(P3), 233 Bosarge, Jr., W. E., 45(B7), 150(B7), 226(B7), 231 Breakwell, J. V., 3(B8, B9), 213 Bryson, A. E., 3(B9, BlO), 231
Hale, J., 5(H1, H2), 173(H1, H2), 194(H1), 232 Halkin, H., 112(H4), 113(H3), 232 Handelsman, M., 197(H5), 232
Canon, M., 112(CO), 113(CO), 114(CO),
Irving, J. H., 219(11), 232
231
Coddington, E. A., 231 Collatz, L., 4(C4), 9(C4), 60(C4), 139(C4), 232
Conti, R., 67(C5), 232 Cullum, C., 112(CO), 113(CO), 114(CO), 231
Gamkrelidze, R. V., 2(P3), 104(P3), 106(P3), 107(P3), 233 Gantmacher, F. R., 63(G1), 232 Gilbert, E. G., 3(B1), 231 Gobetz, F. W., 219(G2), 220(G2), 232 Goddington, E. A,, 231 Goldstein, A. A., 4(G3), 232
Kalaba, R. E., 3(B3), 5(B3), 138(B3), 139(B3, Kl), 143(B3), 231, 232 Kantorovich, L. V., 4(K2, K3), 5(K3), 7(K3), 9(K3), ll(K2, K3), 12(K3), 27(K2), 32(K3), 33(K3), 35(K3), 45(K3), 232
235
236
AUTHOR INDEX
Kaplan, W., 232 Kelley, H. J., 3(1<5, K6), 197(K6), 232 Kenneth, P., 3(K7, M3), 5(M2), 138(M2), 139(K7, 1'23, M2, M3), 143(M2), l97(M3), I98(M3), 200(M3), 203(M3), 232, 233 2 0 4 ( ~ 3 ) 206(nn), , Kolmogorov, A. N., 233 Kopp, It. E., 3(K6), 139(K10), 197(K6, KIO), 208(K10), 232, 233 Levinson, N., 231 I,indorfer, \V., 197(LI), 233 Long, K. S., 108(1,2), 198(L2), 233
Paiewonski, B., 2(P1), 233 Picard, E., 68(P2), 120(P2), 233 Pinkham, G., 139(K10), 197(K10), 208(KIO), 233 Polak, E., 112(CO), 113(CO), 114(CO), 231 Pontryagin, L. S., 2(P3), 104(P3), 106(P3), 107(P3), 233 Porter, W. A., 64(P4), 233 Rheinboldt, W. C., 4(A2), 114(A2), 175(A2), 231 Rudin, W., 233
MC Gill, R., 3(1<7,M3), 5(M2), 138(M2), 139(K7, KIO, M I , M2, M3), 143(M2), 197(KlO, M3), 198(NI3), 200(M3), 203(M3), 204(M3), 206(M3), 208(K lo), 232, 233 Melbourne, W. G., 219(M4, M5), 224(M4, M5), 225(M5), 233 Mislichenko, E. F., 2(P3), 104(P3), 106(P3), 107(P3), 233 Moycr, H. G., 3(1<6), 139(K10), 197(K6, KIO, Ll), 208(KIO), 232, 233
Sauer, C. G., 219(M5), 225(M5), 233 Schroder, J., 233 Speyer, J. L., 3(B9), 231
Nering, E. G., 62(N1), 233 Neustadt, L. W., 2(N3), 3(N2), 233
Warga, J., 233 Witsenhausen, H., 233
45(A2),
224(M5),
Taylor, G. E., 139(K8), 232 Van Dine, C. P., 3(V1), 219(V1), 233 Vulikh, B. S., 95(V2), 233
SUBJECT INDEX
example of application to continuous TPBVP’S, 119-122, 122-133 of application to discrete TPBVP’s, 1.36-1 64 modification of, 41 as special case of method of modified contraction mapping method, 25 Control, 105, 112, see also Optimal control Convergence criteria, practical, 4 factor, estimate of, 217 order of, 46 Conversion of variable-interval T P B V P into fixed-interval TPBVP, 108, 198 Correction factor, 209 Cost functional, 105, 112 Criteria for comparison of convergence of applications of Newton’s method, 208 of iterative methods, 4
A Accuracy criterion, 206 Almost linear problems, 173-181 control problems, 174-177,219-223 fixed point problems, 2.5 TPBVP’s, 174 Almost linear problems with periodic boundary conditions, 181 application of Picard‘s method to, 181-1 84 second-order cxaniples of, 184-195
B Banach, theorem of, 37 Bilinear operator, norm of, 87 Boundary-compatible set, 6 choice of, 118 definition of, 62, 66 existence of, 62, 67 Uoundcd, uniformly, 27
D
C Canonical system, 106, 113 CM sequence, see Contraction mapping sequence Contraction, 8 Contraction mapping sequence, 8,115, 154 Contraction mapping theorems, see Fixed point theorems Contraction mappings, method of, 7-20, see also Picard’s method application to almost linear TPBVP’s, 177-180 to continuous TPBVP’s, 115-119 to discrete TPBVP’s, 153-156 to operator equations, 7-20
Differentiable mapping, 83,85,89, 91 Differentiable operator, see LXfferentiable mapping Differentiable T P B V P , 116, 154 Direct method, 2 example of, 3 Derivatives, of (equivalent) operator, 85, 91,92 computation of, for continuous TPBVP’S, 82-88 for discrete TPBVP’s, 88-94
E Equivalence of integral equation representations, 94-97
237
238
SUBJECT I N D E X
IGluivalence ( c o i t t . ) of summation equation representations, 97-10? Equivalent operator equation, 1, see also Equivalent fixed point problem Equivalent representation, see Representation of TPBVP’s Existence of pcriodic solutions, conditions for the, 184-195 I‘:stremals, 107, 114
F 1;ixetl point, 8, 21, 48 1;iscd point problem, 45 almost linear, 2.5 equivalent, 82, 89 Fixed point theorem, 8,9, 10, 11,20 1;rechet derivative, 28, 31 Fundamental matrix, 60, 218
G Green’s function, see Green’s matrix Green’s matrix, 6, 61, 65 determination of, 162, 218 Grid points, 206 (;rid ske, effect of, 210
H I ramiltonian, 106, 113 nornial, 108, 114
I Indirect method, 2 examples of, 3 Initial guess, 178 choice of, 118 influence of, on convergence, 208, 214, 335 Tnitial value problem, solution of, 60, 64 Integral equation representation of TPEVP’s, 68, see also Representation of TPBVP’s Invariant mapping, 8 I -
Iterative methods operator theoretic, 7-58 practical aspects of, 1 9 6 2 3 0
K Katitorovich, theorem of, 35,141,170
Lebesquc dominated convergence theorem, 84,91 Lipscliitz norm, 9, 102-103
M A4 sequence, see Multipoint method sequence hiaxitnuin principle, 2, see also Pontryagin’s principle Majorant, 11 choice of functional form of, 16-20 MCM sequence, see Modified contraction mapping sequence Mean value theorem, 12, 18, 24,29, 52, 84, 90, 163 me approximate solution, 174 Modified contraction mapping method, 21-25,134-137, 164-167 advantages of, 134 application to continuous TPBVP’s, 134-137 t o discretc TPBVP’s, 164-167 to operator equations, 21-25 essence of, 23 Modified contraction mapping sequence, 21 Modified Newton’s method, 24, 139 coniputational aspects of, 214 generalization of, 41 Multipoint methods, 45-58, 150-153, 226-230 advantages of, 153 application to continuous TPBVP’s, 150-1 53 to operator equations, 45-58 to oscillation problems, 226230
239
S U B J E C T INDEX
Multipoint method sequence, 46 Mysovskilih, theorem of, 33,141,169
N Newton’s method, 3, 24, 26-45, 137-150, 167-171, 197-218 application to continuous TBPVP’s, 137-143 to discrete TBPVP’s, 167-171 to operator equations, 24,2645 to orbital transfer problem, 197-218 convergence of, 139 criteria for comparison of convergence of, 208 drawback of, 139 example of application of continuous TPBVP’s, 143-150 as special case of contraction mapping method, 27, 140 Newton’s method sequence, 26,138,168 Newton-Raphson method, generalized, 3, 139, see also Newton’s method N M sequence, see Newton’s method sequence Norm, 9 derivative, 9 Lipschitz, 9, 102-103 practical, for measuring convergence, 206 problem-oriented, 122 uniform of bilinear operator, 87 definition of, 86,92,121 of derivative of operator, estimate of, 86,87,93 of matrix, 92
0 Operator equation, equivalent, 1, see also Fixed point problem Operator equation representation, see Representation of TPBVP’s Optimal control, 105 sequence, 112 Optimal control problems, 2,104, 105 continuous, 104-110
discrete, 112-115 example of continuous, 110-112, 197218, 218-226 numerical methods for solving, 2-4 reduction to TPBVP’s of, 107-109, 114-115 Orbital transfer problem, Earth-to-Mars, 197-226 constant low-thrust case, 197-218 variable low-thrust case, 218-226 Order of convergence, 46 Oscillation problems, 173, see also Almost lincar problems with periodic boundary conditions application of multipoint method to, 226-230 conditions for the existence of periodic solutions of. 184-195
P Partial correction, 208-209 Periodic boundary conditions, 6, 173 almost linear problems with, 181-183 examples of almost linear problems with, 184-195 Picard’s method, 3, .5, 116, 154, see also Contraction mapping method application to almost linear TPBVP’s, 177-180 to almost linear problems with periodic boundary conditions, 181-183 example of application to a continuous T P B V P , 119-122,122-133 to a discrete T P B V P , 1.56-164 to an orbital transfer problem, 223-226 Pontryagin’s principle for continuous optimal control problems, 106 for discrete optimal control problems, 113 examples of application of, 110,199, 222 reduction of optimal control problems to TPBVP’s by means of, 107-109, 114-11s
240
SUBJECT INDEX
Quadratic convergence, 32 Quasilitiearization, 3, 138, 139, 169, see cdso Newton’s method
Successive approximation, method of, 7 Summation equation representation of TPBVP’s, 71, see also Representation of T P B V P ’ s
R
T
Q
12entlc/vous maneuver, 219
I
S Schauder’s theorem, 9 Scale factor, 108, 198 Smooth control problem, 105, 113 Standard form, 109, 115 State, 10.5, 112
?‘ invariant, 8 TPBVP’s, see Two-point boundary value problems Transition matrix, 64 Two-point boundary value problems, 1 continuous, differentiability of, 116 representation of, 67-71 continuous linear, analytical solution of, 60-62 discrete, differentiability of, 154 representation of, 71-75 discrete linear, analytical solution of, 6+66 linearized, numerical solution of, 204-206