Least Squares and Chebyshev Systems

As readers know, polynomials of degree n, in other words linear combinations of n + 1 monomials 1,…, t n , may have at most n real zeros. A far-reaching generalization of this fact raises a fundamental concept of Chebyshev systems, briefly, T-systems. Those systems are defined as follows. For a set (or system) of functions F = {f 0,…}, a linear combination of a finite number of elements, f = ∑c i f i , is called a polynomial on F (considered nonzero when ∃i: c i ≠ 0). A system of n + 1 function F = {f 0,…,f n } on an interval (or a half-interval, or a non-one-point segment) I ⊆ ℝ is referred to as T-system, when nonzero polynomials on F may have at most n distinct zeros in I (zeros of extensions outside I are not counted). The basic ideas of the theory of T-systems may be understood by readers with relatively limited experience. In this chapter we focus both on these ideas and on some nice applications of this theory such as estimation of numbers of zeros and critical points of functions (in analysis and geometry), a real-life problem in tomography, interpolation theory, approximation theory, and least squares. We provide a comprehensive discussion of the linear least-squares technique and present its analytic, algebraic, and geometric versions. We examine its links to linear algebra and combinatorial analysis (in this connection we discuss some problems, previously considered in “ A Combinatorial Algorithm in Multiexponential Analysis ” and “ Convexity and Related Classic Inequalities ” chapters, from a different point of view). We also discuss some features of the least-squares solutions (e.g., passing through determinate points, asymptotic properties). In addition, we outline the connections between least squares and probability theory and statistics. Finally, we discuss real-life applications to polynomial interpolation (such as finding the best polynomial fitting for two-dimensional surfaces) and signal processing in nuclear magnetic resonance (NMR) technology (such as finding covariance matrices for maximal likelihood estimating parameters).