×

Nearest common root of a set of polynomials: a structured singular value approach. (English) Zbl 1478.93235

Summary: The paper considers the problem of calculating the nearest common root of a polynomial set under perturbations in their coefficients. In particular, we seek the minimum-magnitude perturbation in the coefficients of the polynomial set such that the perturbed polynomials have a common root. It is shown that the problem is equivalent to the solution of a structured singular value \((\mu)\) problem arising in robust control for which numerous techniques are available. It is also shown that the method can be extended to the calculation of an “approximate GCD” of fixed degree by introducing the notion of the generalized structured singular value of a matrix. The work generalizes previous results by the authors involving the calculation of the “approximate GCD” of two polynomials, although the general case considered here is considerably harder and relies on a matrix-dilation approach and several preliminary transformations.

MSC:

93B60 Eigenvalue problems
15A18 Eigenvalues, singular values, and eigenvectors
93B35 Sensitivity (robustness)
93C73 Perturbations in control/observation systems
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Karcanias, N.; Giannakopoulos, C.; Hubbard, M., Almost zeros of a set of polynomials of \(R [s]\), Internat. J. Control, 38, 6, 1213-1238 (1983)
[2] Mitrouli, M.; Karcanias, N., Computation of the GCD of polynomials using Gaussian transformations and shifting, Internat. J. Control, 58, 1, 211-228 (1993) · Zbl 0777.93053
[3] Karcanias, N.; Mitrouli, M., A matrix pencil based numerical method for the computation of the GCD of polynomials, IEEE Trans. Automat. Control, 39, 5, 977-981 (1994) · Zbl 0807.93021
[4] Fatouros, S.; Karcanias, N.; Christou, D.; Papadopoulos, P., Approximate greatest common divisor of many polynomials and pseudo-spectrum, IFAC Proc. Vol., 46, 2, 623-628 (2013)
[5] Halikias, G.; Galanis, G.; Karcanias, N.; Milonidis, E., Nearest common root of polynomials, approximate greatest common divisor and the structured singular value, IMA J. Math. Control Inform., 30, 4, 423-442 (2012) · Zbl 1279.93042
[6] Karcanias, N., The greatest common divisor of a set of polynomials, control theory and approximate algebraic computations, Bull. Greek Math. Soc., 54, 29-46 (2007) · Zbl 1157.93351
[7] Noda, M.-T.; Sasaki, T., Approximate GCD and its application to ill-conditioned equations, J. Comput. Appl. Math., 38, 1-3, 335-351 (1991) · Zbl 0747.65034
[8] Barnett, S., Polynomials and Linear Control Systems (1983), Marcel Dekker, Inc. · Zbl 0528.93003
[9] Barnett, S., Greatest Common Divisor of Several Polynomials, Mathematical Proceedings of the Cambridge Philosophical Society, vol. 70, 263-268 (1971), Cambridge University Press · Zbl 0224.15018
[10] Bitmead, R.; Kung, S.-Y.; Anderson, B.; Kailath, T., Greatest common divisor via generalized Sylvester and Bezout matrices, IEEE Trans. Automat. Control, 23, 6, 1043-1047 (1978) · Zbl 0389.93008
[11] Vardulakis, A. I.; Stoyle, P. N., Generalized resultant theorem, IMA J. Appl. Math., 22, 3, 331-335 (1978) · Zbl 0403.12025
[12] Karcanias, N., Invariance properties, and characterization of the greatest common divisor of a set of polynomials, Internat. J. Control, 46, 5, 1751-1760 (1987) · Zbl 0695.12013
[13] Christou, D.; Karcanias, N.; Mitrouli, M., The eres method for computing the approximate GCD of several polynomials, Appl. Numer. Math., 60, 1-2, 94-114 (2010) · Zbl 1185.12005
[14] Fatouros, S.; Karcanias, N., Resultant properties of GCD of many polynomials and a factorization representation of GCD, Internat. J. Control, 76, 16, 1666-1683 (2003) · Zbl 1043.93017
[15] Karcanias, N.; Mitrouli, M., Normal factorisation of polynomials and computational issues, Comput. Math. Appl., 45, 1-3, 229-245 (2003) · Zbl 1035.65048
[16] Karcanias, N.; Mitrouli, M.; Triantafyllou, D., Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance, Internat. J. Control, 79, 11, 1447-1461 (2006) · Zbl 1125.65041
[17] Karmarkar, N.; Lakshman, Y. N., Approximate polynomial greatest common divisors and nearest singular polynomials, (Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (1996), ACM), 35-39 · Zbl 0928.13017
[18] Rupprecht, D., An algorithm for computing certified approximate GCD of n univariate polynomials, J. Pure Appl. Algebra, 139, 1-3, 255-284 (1999) · Zbl 0964.12007
[19] Winkler, J. R.; Hasan, M.; Lao, X., Two methods for the calculation of the degree of an approximate greatest common divisor of two inexact polynomials, Calcolo, 49, 4, 241-267 (2012) · Zbl 1261.12001
[20] Karcanias, N.; Giannakopoulos, C., Grassmann invariants, almost zeros and the determinantal zero, pole assignment problems of linear multivariable systems, Internat. J. Control, 40, 4, 673-698 (1984) · Zbl 0568.93010
[22] Karcanias, N.; Halikias, G., Approximate zero polynomials of polynomial matrices and linear systems, Linear Algebra Appl., 439, 4, 1091-1103 (2013) · Zbl 1305.15050
[23] Karcanias, N.; Giannakopoulos, C., Necessary and sufficient conditions for zero assignment by constant squaring down, Linear Algebra Appl., 122, 415-446 (1989) · Zbl 0679.93012
[24] Hinrichsen, D.; Pritchard, A. J., Mathematical Systems Theory I: Modelling, State Space Analysis, Stability and Robustness, vol. 48 (2011), Springer Science & Business Media
[25] Packard, A.; Doyle, J., The complex structured singular value, Automatica, 29, 1, 71-109 (1993) · Zbl 0772.93023
[27] Young, P. M.; Doyle, J. C., Computation of \(μ\) with real and complex uncertainties, (29th IEEE Conference on Decision and Control (1990), IEEE), 1230-1235
[28] Karcanias, N.; Mitrouli, M., Approximate algebraic computations of algebraic invariants, IEE Control Eng. Ser., 135-168 (1999)
[29] Balas, G. J.; Doyle, J. C.; Glover, K.; Packard, A.; Smith, R., \(μ\)-Analysis and Synthesis Toolbox (1993), MUSYN Inc. and the MathWorks: MUSYN Inc. and the MathWorks Natick, MA
[30] Braatz, R. P.; Young, P. M.; Doyle, J. C.; Morari, M., Computational complexity of \(μ\) calculation, IEEE Trans. Automat. Control, 39, 5, 1000-1002 (1994) · Zbl 0807.93020
[31] Young, P. M., The rank one mixed \(μ\) problem and “Kharitonov-type” methods, (Proceedings of 32nd IEEE Conference on Decision and Control (1993), IEEE), 523-528
[32] Yamamoto, S.; Kimura, H., On structured singular values of reciprocal matrices, Systems Control Lett., 26, 3, 163-166 (1995) · Zbl 0877.93059
[33] Jaimoukha, I. M.; Halikias, G.; Malik, U.; Gungah, S., On the gap between the complex structured singular value and its convex upper bound, SIAM J. Control Optim., 45, 4, 1251-1278 (2006) · Zbl 1123.93035
[34] Chen, J.; Fan, M. K.; Nett, C. N., Structured singular values and stability analysis of uncertain polynomials, part 2: a missing link, Systems Control Lett., 23, 2, 97-109 (1994) · Zbl 0826.93055
[35] Chen, J.; Fan, M. K.; Nett, C. N., Structured singular values and stability analysis of uncertain polynomials, part 1: the generalized \(μ\), Systems Control Lett., 23, 1, 53-65 (1994) · Zbl 0826.93054
[36] Guglielmi, N.; Rehman, M.-U.; Kressner, D., A novel iterative method to approximate structured singular values, SIAM J. Matrix Anal. Appl., 38, 2, 361-386 (2017) · Zbl 1365.65101
[37] Clarke, F. H., Optimization and Nonsmooth Analysis, vol. 5 (1990), SIAM · Zbl 0696.49002
[38] Hiriart-Urruty, J.-B.; Ye, D., Sensitivity analysis of all eigenvalues of a symmetric matrix, Numer. Math., 70, 1, 45-72 (1995) · Zbl 0816.15016
[39] Gracia, J.-M., Directional derivatives of the singular values of matrices depending on several real parameters, arXiv preprint
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.