Birkhoff-hermite_ dvi

COMMUNICATIONS IN INFORMATION AND SYSTEMS c 24 International Press Vol. 4, No. 1, pp. 89-12, September 24 5 A REGULARIZED SOLUTION TO THE BIRKHOFF INTERPOLATION PROBLEM Y. ZHOU AND C. F. MARTIN Dedicated to Sanjoy Mitter on the occasion of his 7th birthday. Abstract. In this paper a relationship between the Birkhoff interpolation problem and the problem of control theoretic splines is established. It is shown that the Birkhoff interpolation problem has a solution if and only if a certain cost function remains bounded under perturbation of a suitably chosen variable. Keywords: Birkhoff Interpolation, optimal control systems, control theoretic splines 1. Introduction. In 196 G. Birkhoff published a paper, [2], that introduced a problem that has remained unsolved for almost one hundred years. The problem that was later restated by Polya, [11], is the following. Given a differential equation u (n) (t) = what combination of initial and terminal values suffice to construct a unique solution. This generalizes the concepts of interpolation that were then current. Lagrange interpolation (more properly Warring interpolation, [15, 6]), and the most general Hermite interpolation are special cases if only two time points are considered. See [3] for the most readable account of several different interpolation schemes. The most notable thing about the problem posed by Birkhoff is that there is not always a solution. For example, if n = 2 and we are given u () = 1 and u (1) = 2 then there is no solution. The most general version of the problem, as posed by Birkhoff, is the following: Let =t <t 1 < <t N = 1. What combination of n functional values and higher derivatives at the points t i suffices to give a unique solution to the problem. It is this problem that has been studied in the literature for almost one hundred years. Primary references are [12, 8]. Another problem that has been studied and will be shown to be related to Birkhoff interpolation is the study of optimal digital to analog conversion using linear system theory. Two versions of this have been studied, interpolation and smoothing, but Accepted for publication on March 22, 24. The work of the first author is supported in part by the Swedish Research Council (VR), The Magnusson Foundation through Swedish Royal Academy of Sciences and SEB Bergvall s Foundation. The work of the second author was supported in part by NSF Grants ECS 972357 and ECS 975312. The support of KTH in the spring of 23 is gratefully acknowledged. The second author wishes to thank the Mittag-Leffler Institute for support during the spring of 23 and the Wenner-Gren foundation for support during the summer of 23. Stockholm University, Stockholm, Sweden, E-mail: yishao@math.su.se Texas Tech University, Lubbock, Texas, USA, E-mail: martin@math.ttu.edu 89

9 Y. ZHOU AND C. F. MARTIN in this paper we restrict attention to interpolation. following. Given a set of data points The simplest problem is the D = {(t i,α i ): i =1,,N}, and a linear control system ẋ = Ax + bu, y = cx, x() = x, find a control u that drives the output y(t) through the data points at the required times and that uses minimal control energy. To state the problem precisely, min u 2 (t)dt u subject to the constraints y(t i )=α i. This problem can be generalized to include Birkhoff type constraints. See, for example, the papers [16, 14] for additional references and results. In Section 2 a brief recap of linear control theory is presented. The material that is presented is what is needed to read this paper. In Section 3 the theory of digital to analog (D-A) conversion using optimal linear control is presented. This material can be found in a series of papers by Martin and his coauthors but sufficient references and background occur in [14]. These functional approximations need have continuous derivatives of all possible orders. The spline is different than that used by Melkman, [1]. In Section 4 we begin the formulation of the main problem of this paper. We recast the D A conversion in terms of polynomials and consider several special cases. This will demonstrate the method and will provide at least one new example. In Section 5 we obtain the main theorem of the paper; an equivalence between the Birkhoff interpolation problem and a sequence of problems from linear optimal control. 2. Linear control theory. In this section a few facts about linear controlled systems are established. We consider the following system. Let (1) (2) ẋ = Ax + bu, x() = x y = cx, where A is n n, b is n 1andcis 1 n. The system is said to be controllable if and only if for each initial point x and each terminal point x T there exists a control u(t) such that x T = x(t )=e AT x + e A(T s) bu(s)ds.

A REGULARIZED SOLUTION TO THE BIRKHOFF INTERPOLATION PROBLEM 91 The following theorem gives two equivalent criteria for controllability. Theorem 2.1. The linear system given by equation (1) is controllable if and only if either of the following two conditions apply (3) rank[b, Ab, A 2 b,,a n 1 b]=n, (4) rank e As bb e A s ds = n, where stands for the transpose of a matrix. The proof of the theorem is elementary and can be found in any book on control theory. Another key concept is observability. The system (1) and (2) is observable if and only if knowing y(t) on any open interval allows the reconstruction of x(t) onthe interval [,T]. The following theorem is classical. Theorem 2.2. The system (1) and (2) is observable if and only if either of the following conditions hold c ca (5) rank. ca n 1 = n, (6) the system ẋ = A x + c u is controllable. In this paper we will be concerned with optimal control of an elementary sort. The following theorem is useful. Theorem 2.3. Consider the problem of finding a control input u( ) to steer the system (1) from x toaprescribedx 1 so as to minimize the cost functional Let K = u 2 (t)dt. e As bb e A s ds. Assuming K is nonsingular, there is a unique continuous solution to this problem which is given by u (s) =b e A s K 1 (e AT x 1 x ). This theorem can be extended in a number of ways including to provide a closed form expression for the cost in terms of x and x 1 and also so as to be directly applicable to the cost functional used in this paper, λx x + u 2 (t)dt.

92 Y. ZHOU AND C. F. MARTIN 3. Control theoretic splines and interpolation. In this section we consider the basic optimization routine that results in control theoretic splines and we consider basic interpolation results using linear control systems. For the material on splines, the history and basic results are found in [16, 14]. Again consider the system defined by (1) and (2). Since our interest is in smooth approximation and not in control theory we make the following assumptions on the form of the system matrices. 1 1. A =.... (7).,.. 1 (8) (9) γ 1 γ n. b =., 1 c =(1,,, ). Note that this implies (1) cb = cab = = ca n 2 b =. Also assume that there is a given set of data points (11) D = {(t i,α i ): <t 1 < <t N T }. We further assume that the control u L 2 [,T]. We also assume that x R n and that R n is equipped with the norm x 2 = λx x with λ>. We define a set of functions that are basic to the problem. Let ce A(ti s) b, t i s>, (12) l i (s) =, otherwise. It is important to note that by equation (1) l i (t) isn 2 times continuously differentiable. Let H = R n L 2 [,T]

A REGULARIZED SOLUTION TO THE BIRKHOFF INTERPOLATION PROBLEM 93 be the Hilbert space with inner product and the reduced norm (x, u), (z,v) = λx z + u(t)v(t)dt. (x, u) 2 H = x 2 + u 2 = λx x + We now prove the following theorem. Theorem 3.1. Let and J(x,u)= x 2 + u 2 y(t) =ce At x + t u 2 (t)dt. ce A(t s) bu(s)ds. Then there exists a unique pair (x,u ) that has the following two properties. 1. for all (x, u) H, J(x,u ) J(x,u) 2. for i =1,,N, α i = ce Ati x + Furthermore the optimal solution is l i (s)u (s)ds. where (x,u )= τ i (λ 1 (ce Ati ),l i (t)), τ i = e i (λ 1 G + H) 1 α, {e i } N is the standard basis in RN,andthematricesG and H are defined by g ij = ce A t i e Atj c and h ij = l i(s)l j (s)ds. We call the matrix G and H the grammians associated with the constraints, and the matrix λ 1 G + H the grammian for the set S. The following lemma is important in the proof of the theorem. Lemma 3.2. The set S = {((ce Ati ),l i ): i =1,,N} is linearly independent in H. Proof. Suppose that there exists a set of numbers ρ i such that for all t [,T] that is, ρ i ((ce Ati ),l i (t)) =, ρ i ce Ati = and ρ i l i (t) = for all t [,T].

94 Y. ZHOU AND C. F. MARTIN We want to show that all ρ i s are zero. Now by definition we have that for t N 1 <t< t N, l j (t) = for all j N 1. Thus we have that ρ N l N (t) = for all t (t N 1,t N ]. So we must have that ρ N =. Continuing in this manner we conclude that each ρ i is. Note that λ 1 G + H is the grammian for the set S and since the elements of S are linearly independent we have (λ 1 G + H) 1 exists for all λ [, ). We state, for future reference, this as a corollary to the lemma. Corollary 3.3. (λ 1 G + H) 1 exists for all λ (, ]. Proof of Theorem 3.1. Recall that J(x,u)= (x,u) 2 H. Now let W = {(x,u): Forevery i, α i = y(t i )=ce Ati x + l i (s)u(s)ds}. Thus the optimization problem is just the problem of finding a point of minimum norm on an affine subvariety. Now by the projection theorem in Hilbert Space [9] the point of minimum norm is the unique point in (span S) W. Thus we see that the optimal point (x,u (t)) has the representation (13) (x,u (t)) = τ i (λ 1 (ce Ati ),l i (t)), due to Lemma 3.2. It remains to calculate the τ i. To do so we substitute this representation into the equation in item 2 of the theorem and after a bit of calculation we see that we have e i (λ 1 G + H)τ = α i, and then note that this is just the ith row of the equation (λ 1 G + H)τ = α, and hence τ i = e i (λg + H) 1 α, by Corollary 3.3.

A REGULARIZED SOLUTION TO THE BIRKHOFF INTERPOLATION PROBLEM 95 4. The polynomial case. In this section we restrict attention to the case when A is nilpotent. Then e At is a matrix of polynomials and hence the spline and interpolation problem both reduce to well understood cases of polynomial interpolation and polynomial splines. The assumptions that were made on the form of system matrices assure that these are classical forms. The problem of non-lagrange (or more precisely non-waring) interpolation has not been considered from the viewpoint of systems theory. In this section we consider the relatively simple problem of osculatory splines and interpolation. Let our data set be given as D = {(t i,α i,β i ): i =1,,N}. We ask again to minimize the cost functional J(u, x )=λx x + u 2 (t)dt subject to the constraints ti (14) α i = ce Ati x + ce A(ti s) bu(s)ds, and (15) β i = cae Ati x + ti cae A(ti s) bu(s)ds. We begin by defining two sets of functions: the first is just new nomenclature for the l i s defined in the previous section and the second is the derivatives of those functions: (16) l (i,) (s) =l i (s), and { (17) l (i,1) (s) = cae A(ti s) b, t i s>,, otherwise. Note that for l (i,1) (s) toben 3 continuously differentiable it is required that n>2. To use the projection theorem we construct the affine subvariety (18) W = {(x,u(t)) : for every <i N, equations (14) and (15) hold }. Controllability guarantees that the set is nonempty and hence there exists a linear subspace W parallel to W. We construct the orthogonal complement of W.Asimple calculation shows that (19) W =span({(λ 1 (ce Ati ),l (i,) (s)), (λ 1 (cae Ati ),l (i,1) (s)) : i =1, 2,..., N}).

96 Y. ZHOU AND C. F. MARTIN Thus if the elements of this subspace are linearly independent we are guaranteed a unique solution. Proposition 4.1. The set N S = {(λ 1 (ce Ai ),l (i,) (s)), (λ 1 (cae Ai ),l (i,1) (s))} is linearly independent provided that n>2. Proof. Suppose that for a set of numbers ρ (i,) and ρ (i,1), i =1,..., N, ρ (i,) ((ce Ati ),l (i,) (t)) + ρ (i,1) ((cae Ati ),l (i,1) (t)) =, for all t [,T]. That is, (ρ (i,) (ce Ati ) + ρ (i,1) (cae Ati ) )=, and for all t [,T], (ρ (i,) l (i,) (t)+ρ (i,1) l (i,1) (t)) =. Then for t [t N 1,t N ]wehavethat ρ (N,) l (N,) (t)+ρ (N,1) l (N,1) (t) = since l (j,) (t)) = and l (j,1) (t)) = for all j N 1. Hence, we have on the interval [t N 1,t N ], ρ (N,) ce A(tN t) b + ρ (N,1) cae A(tN t) b =. This implies, by the controllability, that ρ (N,) c + ρ (N,1) ca =. It is clear that ρ (N,) = ρ (N,1) =,sincecand ca are linearly independent. Continuing in this manner we can prove that all ρ (i,) and ρ (i,1) are zero, and hence the proposition follows. By the projection theorem there exists a unique point in W W and hence the point must be of the form (2) (x,u (t)) = (τ (i,) (λ 1 (ce Ati ),l (i,) (t)) + τ (i,1) (λ 1 (cae Ati ),l (i,1) (s))),

A REGULARIZED SOLUTION TO THE BIRKHOFF INTERPOLATION PROBLEM 97 where the τ s are chosen to satisfy the constraints. We order the elements of S with the lexicographic order as follows: Let S 1 = {λ 1 (ce At1 ),λ 1 (cae At1 ),λ 1 (ce At2 ),,λ 1 (cae AtN ) }, and S 2 = {l (1,),l (1,1),l (2,),,l (N,1) }. It is clear that S = S 1 S 2, and the grammian of S is of the form λ 1 G + H where G is the grammian of the ordered set S 1 and H is the grammian of the ordered set S 2. We have proved that λ 1 G + H is invertible by above proposition, but note that G is not necessarily invertible. In fact G is clearly not invertible unless n 2N. As before it is seen after a bit of manipulation that the optimal τ =(τ (1,),τ (1,1),τ (2,),,τ (n,1) ) is the solution of (λ 1 G + H)τ = α where α is the vector of data given by (α 1,β 1,α 2,,β N ). Note that this statement is true for every λ (, ). If we go back to the proof of the proposition we see that the same method of proof can be used to prove that H is invertible. We now make the assumption that n =2N and note the following theorem. Also note that if λ = then this is just the the osculatory interpolation problem that is known to be solvable, [3]. Theorem 4.2. If n = 2N and N > 1 then λ 1 G + H is invertible for all λ [, ]. It is a fairly routine extension of this section to construct the general Hermite interpolation and spline problem in the polynomial case. It is important to examine the differentiability of the control and the resulting spline in this case. The basis element l (i,1) is the culprit. Recall that l (i,1) (t) =cae A(ti t) b if t i >tand otherwise. Thus we can continuously differentiate l (i,1) only n 3 times. Calculating y(t) wesee that y is only 2n 2 times continuously differentiable. The matrix H is invertible and basically the same proof holds as for G + λh. 5. Birkhoff-Hermite interpolation and splines. In this section we construct controls and initial values that solve a mixed version of the classical Birkhoff interpolation and Birkhoff spline problems.

98 Y. ZHOU AND C. F. MARTIN 5.1. Statement of Problem. We first assume that the system given by equations (1) and (2) is of dimension n, that the matrix A is nilpotent, and the system matrices are in the form given above. This insures that the optimal controls are polynomial. We assume as given an incidence matrix J that is n n and whose entries consist of s and 1s. The number of 1s is assumed to be exactly n. Let E = {(i, j) : e ije j =1} and further assume that E is equipped with the lexicographic order. We define the data set D, (21) D = {(t i,α (i,j) ): forevery (i, j) E, t 1 <t 2 < <t n T }. We now extend the definition of the basis functions from the previous section to the following: for every (i, j) E, ca j 1 e A(ti s) b, t i s>, (22) l (i,j) (s) =, otherwise Let the cost function be given, as before, as J(x,u)=λx x + t u 2 (t)dt. As before we assume that (x,u) H. We define n constraints: for (i, j) E, (23) α (i,j) = ca j 1 e Ati x + l (i,j) (s)u(s)ds. We can state the problem as Problem 1. min (x,u) H J(x,u) subject to the n constraints of equation (23). 5.2. The optimal solution. We again will appeal to the Hilbert Projection Theorem. We will carefully define the affine subvariety, the orthogonal complement of the parallel linear sbspace and their intersection, thus finding the unique point that minimizes the cost.

A REGULARIZED SOLUTION TO THE BIRKHOFF INTERPOLATION PROBLEM 99 First recall that H = R n L 2 [,T] with inner product Let (x, u), (z,v) = λx z + u(t)v(t)dt. (24) W = {(x,u) H: for all (i, j) E equation (23) holds}. Note that W is not empty by controllability. Let W denote the linear subspace parallel to W. Now an easy calculation shows that (25) W = span ( {λ 1 (ca j 1 e Ati ),l (i,j) ): (i, j) E}). The key proposition is the following. Proposition 5.1. The set S 1 = {(λ 1 (ca j 1 e Ati ),l (i,j) ): (i, j) E} is linearly independent. In order to prove this proposition, we prove, as before, the following lemma, which is an analogue to the first part of the proof to Proposition 4.1. Lemma 5.2. Let the set S 2 be S 2 = {l (i,j) : (i, j) E}. Then, the set S 2 is linearly independent. Proof. The idea of the proof is similar to the above. We first isolate the last block of functions and then prove that the functions in that block are linearly independent. Suppose that there exist numbers ρ ij such that ρ ij l (i,j) (t) = (i,j) E for all t [,T]. Let (k 1,j k1 ) be the maximal element in E and let (k 2,j k2 )be the largest element less than all elements of the form (k 1,j)forj. Then for every t (t k2,t k1 ) this sum reduces to ρ k1jl (k1,j)(t) = (k 1,j) E for all t (t k2,t k1 ), or rewriting the sum we have ρ k1jca j 1 e A(t k s) 1 b =. (k 1,j) E

1 Y. ZHOU AND C. F. MARTIN Thus we have by controllability ρ k1jca j 1 =. (k 1,j) E this is just a set of distinct rows of the identity matrix and hence we have that the set {l k1,j :(k 1,j) E} is linearly independent. Thus we have that ρ k1j =forall (k 1,j) E. The proof is finished by conitinuing this way backwards. Proof of Proposition 5.1: Suppose that there exist constants ρ (i,j) with (i, j) E such that ρ (i,j) (λ 1 (ca j 1 e Ati ),l (i,j) (t)) =, (i,j) E which is equivalent to and ρ (i,j) λ 1 (ca j 1 e Ati ) =, (i,j) E ρ (i,j) l (i,j) (t) =. (i,j) E Since the functions l (i,j) for (i, j) E are linearly independent, (by Lemma 5.2), we can conclude that all numbers ρ (i,j) s are zero. The proof is complete. Let (26) S 3 = {λ 1 (ca j 1 e Ati ) : (i, j) E} and note the following: S 3 is linearly independent if and only if the corresponding Birkhoff interpolation problem is solvable. Thus there exists a unique control of the form (27) u (t) = τ (i,j) l (i,j) (t), (i,j) E and an initial value (28) x = τ (i,j) e A t i (A j 1 ) c (i,j) E that minimizes the cost function and satisfies the constraints. To determine the the values of the τs we substitute the optimal control and initial value into the constraints. Let the sets S i be ordered by the ordering induced from E. If we let G be the Grammian of the set S 3, H the grammian of the set S 2 then after some manipulation we have the following important fact. The grammian of the set S 1 is (29) λ 1 G + H,

A REGULARIZED SOLUTION TO THE BIRKHOFF INTERPOLATION PROBLEM 11 and the optimal τs is the solution of (3) (λ 1 G + H)τ = α. Thus we have that the interpolation problem is regularized by the optimal spline problem and we have a new necessary and sufficient condition for the existence of a polynomial that solves the Birkhoff interpolation problem. Recall the cost function J(x,u)=λx x + u 2 (t)dt. When λ = we have that all of the cost is on the control. Thus if there is a solution x to the Birkhoff interpolation problem the cost function is minimized by setting u =. Letting λ = is equivalent to using the cost function J(x,u)=x x. There is no penalty for using large control and thus if the spline interpolation problem is solvable for arbitrary initial data the the optimal cost is obtained by setting x =. Now assume that the Birkhoff problem is solvable with initial data x and consider the pair (x, ) and cost function J λ (x,u)=λx x + u 2 (t)dt, and let (x # λ,u# λ ) be the optimal point. Then we have that for all λ (, ) that (31) J λ (x # λ,u# λ ) J(x, ). On the other hand suppose that there is no solution to the Birkhoff interpolation problem and consider the equivalent cost function J β (x,u)=x x + β u 2 (t)dt. Let (x β,u β ) be the optimal solution for β (, ). As β becomes large, either u2 (t)dt becomes unbounded, or it is bounded away from since there is no solution to the Birkhoff interpolation problem. Thus we have that lim J β(x β,u β )=. β We have proven the following theorem. Theorem 5.3. Birkhoff interpolation problem with incidence matrix J has a solution if and only if there exists a positive constant M so that for ever λ (,T) with optimal solution (x # λ,u# λ ) J λ (x # λ,u# λ ) M.

12 Y. ZHOU AND C. F. MARTIN REFERENCES [1] G. Ammar, W. Dayawansa, and C. Martin, Exponential interpolation and numerical algorithms, Appl. Math. Comp., 41(1991), pp. 189-232. [2] G. Birkhoff, General mean value theorems with applications to mechanical differentiation and quadrature, Tran. Amer. Math. Soc. 7(196), pp. 17-136. [3] P. Davis, Interpolation and Approximation, Dover Pub. Co. 1975. [4] R. de Prony, Essai expérimental et analytique, J.École Polytech. (Paris)1(1795), pp. 24 76. [5] F. B. Hildebrand, Introduction to Numerical Analysis, Dover Publishig Co. 1983. [6] J-L. Lagrange, Memoire sur la Méthod d Interpolation, Nouveaux Mémores de l Academie Royale des Sciences ar Belle-Lettres de Berlin années 1792-1793 in Serret, J-A (ed) Oeuvres de LaGrange vol 5. Paris: Gauthiers-Villers, 187. [7] S. Karlin and J. M. Karon, On Hermite-Birkhoff interpolation, J. of Approx. Theory, 6(1972), pp. 9 115. [8] G. G. Lorentz, K. Jetter, and S. D. Riemenschneider, Birkhoff Interpolation, Encyclopedia of Mathematics and its Applications, 19, Addison Wesley Publishing Company, Reading, MA, 1983. [9] D. Luenberger, Optimization by Vector Space Methods, John Wiley and Sons, Inc., 1968. [1] A. A. Melkman, Hermite-Birkhoff interpolation by splines, J. Approximation Theory, 19(1977), pp. 259 279 [11] G. Polya, Bemerkungen zur Interpolation und der Naherungstheorie der Balkenbiegung, Z. Angew. Math. Mech. 11(1931), pp. 445 449. [12] A. Sharma, Some poised and nonpoised problems of interpolation, SIAM Review, 14(1972), pp. 129 151. [13] J. Smith and C. Martin, Approximation, interpolation and sampling, in: Differentialgeometry: the interface between pure and applied mathematics, pp. 227 252, Cont. Math. Amer. Math. Soc. 1997. [14] S. Sun, M. Egerstedt, and C.Martin, Control theoretic smoothing splines, IEEE Tran. Auto. Cont., 45(2), pp. 2271 2279. [15] E. Waring, Problems concerning interpolation, Philosophical Transactions of the Royal Society of London, Vol 69, 1779, pp. 59 67. [16] Z. Zhang, J.Tomlinson, and C. Martin, Splines and linear control theory, Acta. Appl.Math., 49(1997), pp. 1 34.