Matrix Computations and Semiseparable Matrices: Eigenvalue and Singular Value Methods

Chapter 13 Orthonormal polynomial vectors

Chapter 13 Orthonormal polynomial vectors In the previous chapter we have studied orthonormal polynomials and least squares polynomial approximants with respect to a discrete inner product. In this chapter, we investigate the generalization into orthonormal polynomial vectors. In this case the parameters of the recurrence relation are contained in a matrix with a structure that generalizes the upper Hessenberg structure. The details of the structure of the (extended) matrix determine the degree structure of the sequence of orthonormal polynomial vectors. The chapter is organized as follows. In Section 13.1, we introduce the concept of a polynomial vector approximant with respect to a discrete norm. It will turn out that this approximant is a polynomial vector orthogonal to all the polynomial vectors of ‘smaller degree’. In Section 13.2, we first study the case when the degrees of the polynomial elements of the vector approximant are equal. Section 13.3 handles the general case. Section 13.4 investigates when the recurrence relation for the sequence of orthonormal polynomial vectors breaks down. ✎ Mastering the content of this chapter is not important to understand the following chapter of the book. The essential ideas of this chapter are the following. Orthonormal polynomial vectors satisfy the orthonormality relations (13.5). These polynomial vectors satisfy a recurrence relation. The coefficients of the recurrence relation of orthonormal polynomial vectors can be summarized into a generalization of a Hessenberg matrix, see Subsection 13.3.2. In the beginning of this subsection, it is described how this general Hessenberg matrix can be recovered by solving an inverse eigenvalue problem. This problem can be solved an order of magnitude faster when the points of the inner product are lying all on the real line or all on the unit circle. 13.1 Vector approximants In this section, we will generalize the polynomial least squares approximation problem into a least squares problem involving multiple polynomials. In Section 12.4 of 429 430 Chapter 13. Orthonormal polynomial vectors the previous chapter, we have studied the polynomial least squares approximation problem: find the polynomial p ∈ Pn of degree at most n ≤ m that minimizes the error m $ i=0|wi(f(zi) − p(zi))|2 . (13.1) This can be generalized into the following approximation problem: find two polynomials p0 ∈ Pd0 and p1 ∈ Pd1 minimizing the error: m $ i=0|w0,if0,ip0(zi) − w1,if1,ip1(zi)|2 . (13.2) The solution having the error as small as possible is the zero solution [p0, p1] = [0, 0]. To avoid this trivial solution, we normalize the polynomial vector [p0, p1], e.g., by putting the extra condition, that p0 has to be monic and of strict degree d0. Note that when we take w0,if0,i = wif(zi), w1,if1,i = wi, and p0 monic of strict degree 0, we get the same error as in (13.1). Instead of considering two polynomials, the previous situation of polynomial approximation can be generalized as follows. Given {zi; f0i, . . . , fαi; w0i, . . . , wαi}m i=0, find polynomials pk ∈ Pdk , k = 0, . . . , α, such that m $ i=0|w0if0ip0(zi) + · · · + wαifαipα(zi)|2 is minimized. Now it doesn’t really matter whether the wji are positive or not, since the products wjifji will now play the role of the weights and the fji are arbitrary complex numbers. Thus, to simplify the notation, we could as well write wji instead of wjifji since these numbers will always appear as products. Thus the problem is to minimize m $ i=0|w0ip0(zi) + · · · + wαipα(zi)|2 . Setting d = [d0, . . . , dα]T , Pd = [Pd0 , . . . , Pdα ]T , wi = [w0i, . . . , wαi]T , p(z) = [p0(z), . . . , pα(z)]T ∈ Pd, we can write this as min m $ i=0|wH i p(zi)|2 , p ∈ Pd. Of course, this problem has the trivial solution p = 0, unless we require at least one of the pi(z) to be of strict degree di, e.g., by making it monic. This, or any other normalization condition, could be imposed for that matter. We require in this chapter that pα is monic of degree dα, and rephrase this as pα ∈ PM dα . To explain the general idea, we restrict ourselves to α = 1, the case of a general α being a straightforward generalization which would only increase the notational 13.2. Equal degrees 431 burden. Thus we consider the problem min m $ i=0|w0ip0(zi) + w1ip1(zi...