Approximate polynomial decomposition

Abstract

In this paper we establish a framework for the decomposition of approximate polynomials. We consider approximately known polynomials f(z) 2 C [z] or f(z) 2 R[z] and examine the problem of functional decomposition. That is, given f, we wish to compute polynomials g and h such that (f +f) (z) = (g h)(z) = g(h(z)); where deg g < deg f, deg h < deg f, degf deg f and f is \\small " with respect to the 2-norm of the vector of coecients. In practice if kfk denotes the 2-norm of f, then we compute g and h such that kfk is a local minimum with respect to variations in g and h. This problem has been studied for exact polynomials and rational functions by several authors [1, 2, 5, 7, 9, 10]. There are several reasons why approximate polynomial decomposition interests us: Decomposition is a fundamental operation on polynomials. Posing a natural, well-dened interpretation of approximate polynomial decomposition and presenting an algorithm for its computation further advances the program to develop a full collection of symbolic-numeric algorithms for polynomials. Sometimes one knows a priori from the problem domain that polynomials should be compositions. This can occur when modelling a phenomenon which comprises a number of sequential algebraic steps, for example, the positions of a multiply articulated robot arm.