Solution of the rational interpolation problem via the Hankel polynomial construction

A. Yu. Uteshev ; I. I. Baravy

Vestnik Sankt-Peterburgskogo universiteta. Prikladnaâ matematika, informatika, processy upravleniâ, no. 4 (2016), pp. 31-43

Résumé

The problem of rational interpolant construction is treated as $$ r(x)=p(x)/q(x),~\ \{r(x_j)=y_j\}_{j=1}^N,~ \{x_j,y_j\}_{j=1}^N \subset \mathbb C , \ \{p(x),q(x)\} \subset \mathbb C[x] \, . $$ At the basis of one result by C. Jacobi, the interpolant is represented as a ratio of two Hankel polynomials, i. e. polynomials of the form $ \mathcal H_{K}(x)= \det [c_{i+j-1}-c_{i+j-2}x]_{i,j=1}^{K} $. The generating sequence for these polynomials is selected as $ \{\sum_{j=1}^N x_j^ky_j/W^{\prime}(x_j) \}_{k\in \mathbb N} $ for $ q(x) $ and as $ \{\sum_{j=1}^N x_j^k/(y_jW^{\prime}(x_j)) \}_{k\in \mathbb N} $ for polynomial $ p(x) $; here $ W(x)=\prod_{j=1}^N(x-x_j) $. The conditions for the solubility of the problem and irreducibility of the obtained fraction are also presented. In addition to formal representation of the solution in determinantal form, the present paper is focused also at the effective computational algorithm for the Hankel polynomials. It is based on a little known identity by Jacobi and Joachimsthal connecting a triple of the Hankel polynomials of successive orders: $$ \alpha \mathcal H_K(x)-(x+\beta) \mathcal H_{K-1}(x)+ 1/\alpha \mathcal H_{K-2}(x) \equiv 0 \ , $$ here $ \{\alpha,\beta \} \subset \mathbb C $ are some constants. The proof of this relation is also contained in the paper along with discussion of a degenerate case $ \alpha=0 $. With these results, a procedure for the Hankel polynomial computation can be developed which is recursive in its order. This gives an opportunity not only to compute a single interpolant with specialized degrees for $ p(x) $ and $ q(x) $ but also to compose the whole set of interpolants for an arbitrary combination for the degrees: $ \deg p + \deg q \le N-1 $. The results of the paper can be applied for problems of Approximation Theory, Control Theory (transfer function reconstruction from frequency responses) and for error-correcting coding (Berlekamp–Welch algorithm). Although the presented results are formulated for the case of infinite fields, they are applicable for finite fields as well. Refs 12.

Détail

Mots-clés : rational interpolation
Keywords: Hankel matrices and polynomials, Berlekamp–Massey algorithm.

Bibliographie

[1] Berlekamp E., Welch L., Error correction of algebraic block codes, Patent USA 4633470, 1986

[2] Beckermann B., Labahn G., “Fraction-free computation of matrix rational interpolants and matrix GCD's”, SIAM J. Matrix anal. appl., 22:1 (2000), 114–144 | DOI | MR | Zbl

[3] Berrut J.-P., Baltensperger R., Mittelmann H. D., “Recent developments in barycentric rational interpolation”, Intern. Series of numerical mathematics, 151, Birkhäuser, Basel, 2005, 27–51 | MR | Zbl

[4] von zur Gathen J., Gerhard J., Modern computer algebra, 2nd ed., Cambridge University Press, Cambridge, 2003, 785 pp. | MR | Zbl

[5] Jacobi C. G. J., “Über die Darstellung einer Reihe gegebner Werthe durch eine gebrochne rationale Function”, J. reine angew. Math., 30 (1846), 127–156 | DOI | MR | Zbl

[6] Jacobi C. G. J., “De eliminatione variabilis e duabus aequationibus algebraicis”, J. reine angew. Math., 15 (1836), 101–124 | DOI | MR | Zbl

[7] Joachimsthal F., “Bemerkungen über den Sturm'schen Satz”, J. reine angew. Math., 48 (1854), 386–416 | DOI | MR | Zbl

[8] Uteshev A. Yu., Baravy I., Solution of interpolation problems via the Hankel polynomial construction, 2016, 56 pp., arXiv: cs.SC/1603.08752

[9] Henrici P., Applied and computational complex analysis. Vol. 1. Power series, integration, conformal mapping, location of zeros, Wiley and Sons, Inc., New York–London, 1974, 700 pp. | MR | Zbl

[10] Faddeev D. K., Lectures in Algebra, Nauka Publ., M., 1984, 416 pp. (In Russian)

[11] Blahut R. E., Fast algorithms for signal processing, Cambridge University Press, New York, 1985, 485 pp. | MR

[12] Iohvidov I. S., Hankel and Toeplitz matrices and forms: Algebraic theory, Birkhäuser Press, Boston, 1972, 260 pp. | MR