×

Orthogonal basis functions in discrete least-squares rational approximation. (English) Zbl 1046.93010

Summary: We consider a problem that arises in the field of frequency domain system identification. If a discrete-time system has an input-output relation \(Y(z)=G(z)U(z)\), with transfer function \(G\), then the problem is to find a rational approximation \(\hat G_n\) for \(G\). The data given are measurements of input and output spectra in the frequency points \(z_k: \{U(z_k),Y(z_k)\}_{k=1}^N\) together with some weight. The approximation criterion is to minimize the weighted discrete least squares norm of the vector obtained by evaluating \(G-\hat G_n\) in the measurement points.
If the poles of the system are fixed, then the problem reduces to a linear least-squares problem in two possible ways: by multiplying out the denominators and hide these in the weight, which leads to the construction of orthogonal vector polynomials, or the problem can be solved directly using an orthogonal basis of rational functions. The orthogonality of the basis is important because if the transfer function \(\hat G_n\) is represented with respect to a nonorthogonal basis, then this least-squares problem can be very ill conditioned. Even if an orthogonal basis is used, but with respect to the wrong inner product (e.g., the Lebesgue measure on the unit circle) numerical instability can be fatal in practice.
We show that both approaches lead to an inverse eigenvalue problem, which forms the common framework in which fast and numerically stable algorithms can be designed for the computation of the orthonormal basis.

MSC:

93B30 System identification
41A20 Approximation by rational functions
65F18 Numerical solutions to inverse eigenvalue problems
42C15 General harmonic expansions, frames
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Akçay, H.; Ninness, B., Rational basis functions for robust identification from frequency and time domain measurements, Automatica, 34, 9, 1101-1117 (1998) · Zbl 0959.93012
[2] Baratchart, L., Rational and meromorphic approximation in \(L^p\) of the circle: system-theoretic motivations, critical points and error rates, (Papamichael, N., Proceedings of the Third CMFT Conference on Computational Methods and Function Theory 1997, Nicosia, Cyprus, October 13-17, 1997. Proceedings of the Third CMFT Conference on Computational Methods and Function Theory 1997, Nicosia, Cyprus, October 13-17, 1997, Approximate Decomposition, Vol. 11 (1999), World Scientific: World Scientific Singapore), 45-78 · Zbl 0935.41011
[3] Baratchart, L.; Leblond, J.; Partington, J. R.; Torkhani, N., Robust identification in the disc algebra from band-limited data, IEEE Trans. Automat. Control, 42, 9, 318-1325 (1997) · Zbl 0889.93014
[4] Bultheel, A.; González-Vera, P.; Hendriksen, E.; Njåstad, O., Orthogonal Rational Functions, Cambridge Monographs on Applied and Computational Mathematics, Vol. 5 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1014.42017
[5] Bultheel, A.; González-Vera, P.; Hendriksen, E.; Njåstad, O., Orthogonal Rational Functions and Tridiagonal Matrices, J. Comput. Appl. Math., 153, 1-2, 89-97 (2001) · Zbl 1014.42017
[6] Bultheel, A.; Van Barel, M., Vector orthogonal polynomials and least squares approximation, SIAM J. Matrix Anal. Appl., 16, 3, 863-885 (1995) · Zbl 0824.41016
[7] A. Bultheel, M. Van Barel, Y. Rolain, J. Schoukens, Numerically robust rational approximation for identification, in: IEEE (Ed.), 40th IEEE Conference on Decision and Control, Orlando FL, December 4-7, 2001, IEEE, New York, Paper PrP06-4, 2001, pp. 4770-4775.; A. Bultheel, M. Van Barel, Y. Rolain, J. Schoukens, Numerically robust rational approximation for identification, in: IEEE (Ed.), 40th IEEE Conference on Decision and Control, Orlando FL, December 4-7, 2001, IEEE, New York, Paper PrP06-4, 2001, pp. 4770-4775.
[8] S. Chandrasekaran, M. Gu, Fast and stable algorithms for banded plus semiseparable systems of linear equations, SIAM J. Matrix Anal. Appl. (2001), to appear.; S. Chandrasekaran, M. Gu, Fast and stable algorithms for banded plus semiseparable systems of linear equations, SIAM J. Matrix Anal. Appl. (2001), to appear. · Zbl 1050.65023
[9] Clement, P. R., Laguerre functions in signal analysis and parameter identification, J. Franklin Inst., 313, 2, 85-95 (1982) · Zbl 0481.93025
[10] T.J. de Hoog, Rational orthonormal bases and related transforms in linear system modeling, Ph.D. Thesis, T.U. Delft, 2001.; T.J. de Hoog, Rational orthonormal bases and related transforms in linear system modeling, Ph.D. Thesis, T.U. Delft, 2001.
[11] T.J. de Hoog, P.S.C. Hueberger, P.M.J. Van den Hof, A general transform theory of rational orthonormal basis function expansion, in: Proceedings of the 39th IEEE Conference on Decision and Control, Sydney, Australia, 2000, pp. 4649-4654.; T.J. de Hoog, P.S.C. Hueberger, P.M.J. Van den Hof, A general transform theory of rational orthonormal basis function expansion, in: Proceedings of the 39th IEEE Conference on Decision and Control, Sydney, Australia, 2000, pp. 4649-4654.
[12] de Vries, D. K.; van den Hof, P., Frequency domain identification with generalized orthonormal basis functions, IEEE Trans. Automat. Control, AC-43, 5, 656-669 (1998) · Zbl 0915.93020
[13] Eidelman, Y.; Gohberg, I., Inversion formulas and linear complexity, Comput. Math. Appl., 33, 69-79 (1997) · Zbl 0870.65020
[14] D. Fasino, N. Mastronardi, M. Van Barel, Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form, Technical Report IRMA 3/2002, I.R.M.A.-C.N.R., Bari, Italy, 2002.; D. Fasino, N. Mastronardi, M. Van Barel, Fast and stable algorithms for reducing diagonal plus semiseparable matrices to tridiagonal and bidiagonal form, Technical Report IRMA 3/2002, I.R.M.A.-C.N.R., Bari, Italy, 2002. · Zbl 1039.65033
[15] Forsythe, G. E., Generation and use of orthogonal polynomials for data fitting with a digital computer, J. SIAM, 5, 74-88 (1957) · Zbl 0083.35503
[16] Gantmacher, F. R.; Kreı̆n, M. G., Oszillationsmatrizen, Oszillationskerne und kleine Schwingungen mechanischer Systeme (1960), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0088.25103
[17] P.S.C. Hueberger, On approximate system identification with system based orthonormal functions, Ph.D. Thesis, TU Delft, The Netherlands, 1991.; P.S.C. Hueberger, On approximate system identification with system based orthonormal functions, Ph.D. Thesis, TU Delft, The Netherlands, 1991.
[18] Heuberger, P. S.C.; Van den Hof, P. M.J., The Hambo transforma signal and system transform induced by generalized orthonormal basis functions, Select. Top. Identification Model. Control, 8, 85-94 (1995)
[19] Heuberger, P. S.C.; Van den Hof, P. M.J.; Bosgra, O., A generalized orthogonal basis for linear dynamical systems, IEEE Trans. Automat. Control, 40, 451-465 (1995) · Zbl 0835.93011
[20] Lee, Y. W., Synthesis of electrical networks by means of the Fourier transforms of Laguerre functions, J. Math. Phys., 11, 83-113 (1933) · Zbl 0005.04509
[21] Lee, Y. W., Statistical Theory of Communication (1960), Wiley: Wiley New York · Zbl 0091.14002
[22] Ljung, L., System Identification: Theory for the User, Information and System Sciences Series (1999), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ
[23] F. Malmquist, Sur la détermination d’une classe de fonctions analytiques par leurs valeurs dans un ensemble donné de poits, in: C.R. 6ième Cong. Math. Scand. (Kopenhagen, 1925), Copenhagen, Gjellerups, 1926, pp. 253-259.; F. Malmquist, Sur la détermination d’une classe de fonctions analytiques par leurs valeurs dans un ensemble donné de poits, in: C.R. 6ième Cong. Math. Scand. (Kopenhagen, 1925), Copenhagen, Gjellerups, 1926, pp. 253-259.
[24] Mastronardi, N.; Chandrasekaran, S.; Van Huffel, S., Fast and stable two-way algorithm for diagonal plus semi-separable systems of linear equations, Numer. Linear Algebra Appl., 8, 1, 1-12 (2001) · Zbl 1051.65021
[25] B. Ninness, Frequency domain estimation using orthonormal bases, in: Proceedings of the 13th IFAC World Congress, San Francisco 1996, Vol. 8, 1996, pp. 381-386.; B. Ninness, Frequency domain estimation using orthonormal bases, in: Proceedings of the 13th IFAC World Congress, San Francisco 1996, Vol. 8, 1996, pp. 381-386.
[26] Ninness, B.; Gustafsson, F., A unified construction of orthogonal bases for system identification, IEEE Trans. Automat. Control, 42, 515-522 (1997)
[27] Ninness, B.; Hjalmarsson, H.; Gustafsson, F., The fundamental role of general orthogonal bases in system identification, IEEE Trans. Automat. Control, 44, 7, 1384-1407 (1999) · Zbl 0963.93021
[28] Nurges, Y.; Yaaksoo, Y., Laguerre state equations for a multivariable discrete system, Automat. Remote Control, 42, 1601-1606 (1981) · Zbl 0501.93040
[29] R. Pintelon, Y. Rolain, A. Bultheel, M. Van Barel, Numerically robust frequency domain identification of multivariable systems, in: P. Sas, B. Van Hal (Eds.), Proceedings of the 2002 International Conference on Modal Analysis, Noise and Vibration Engineering, Leuven 2002, September 16-18, 2002, pp. 1316-1321.; R. Pintelon, Y. Rolain, A. Bultheel, M. Van Barel, Numerically robust frequency domain identification of multivariable systems, in: P. Sas, B. Van Hal (Eds.), Proceedings of the 2002 International Conference on Modal Analysis, Noise and Vibration Engineering, Leuven 2002, September 16-18, 2002, pp. 1316-1321.
[30] Pintelon, R.; Schoukens, J., System Identification: A Frequency Domain Approach (2001), IEEE Press: IEEE Press Piscataway · Zbl 0970.93514
[31] Sanathanan, C. K.; Koerner, J., Transfer function synthesis as a ratio of two complex polynomials, IEEE Trans. Automat. Control, 9, 1, 56-58 (1963)
[32] Szabó, Z.; Bokor, J.; Schipp, F., Identification of rational approximate models in \(H_∞\) using generalized orthogonal basis, IEEE Trans. Automat. Control, 44, 1, 153-158 (1999) · Zbl 1056.93528
[33] Takenaka, S., On the orthogonal functions and a new formula of interpolation, Jpn. J. Math., 2, 129-145 (1925) · JFM 52.0313.01
[34] Van Barel, M.; Bultheel, A., A parallel algorithm for discrete least squares rational approximation, Numer. Math., 63, 99-121 (1992) · Zbl 0762.41016
[35] Van Barel, M.; Bultheel, A., Discrete linearized least squares approximation on the unit circle, J. Comput. Appl. Math., 50, 545-563 (1994) · Zbl 0810.65011
[36] Van Barel, M.; Bultheel, A., Orthogonal polynomial vectors and least squares approximation for a discrete inner product, Electron. Trans. Numer. Anal., 3, 1-23 (1995) · Zbl 0857.42013
[37] Van Barel, M.; Fasino, D.; Gemignani, L.; Mastronardi, N., Orthogonal rational functions and diagonal-plus-semiseparable matrices, (Luk, F. T., Advanced Signal Processing Algorithms, Architectures, and Implementations XII. Advanced Signal Processing Algorithms, Architectures, and Implementations XII, Proceedings of SPIE, Vol. 4791 (2002), SPIE, Bellingham, WA), 162-170
[38] Van den Hof, P. M.J.; Heuberger, P. S.C.; Bokor, J., System identification with generalized orthogonal basis functions, Automatica, 31, 1821-1834 (1995) · Zbl 0848.93013
[39] P. Van gucht, A. Bultheel, Computing orthogonal rational functions analytic outside the unit disc, Technical Report TW312, Department of Computer Science, K.U. Leuven, September 2000.; P. Van gucht, A. Bultheel, Computing orthogonal rational functions analytic outside the unit disc, Technical Report TW312, Department of Computer Science, K.U. Leuven, September 2000. · Zbl 0969.42012
[40] Van gucht, P.; Bultheel, A., State space representation for arbitrary orthogonal rational functions, Systems Control Lett., 49, 2, 91-98 (2003) · Zbl 1157.93359
[41] Wahlberg, B., System identification using Laguerre models, IEEE Trans. Automat. Control, AC-36, 5, 551-562 (1991) · Zbl 0738.93078
[42] Wahlberg, B., System identification using Kautz models, IEEE Trans. Automat. Control, AC-39, 6, 1276-1282 (1994) · Zbl 0807.93065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.