Inversion error, condition number, and approximate inverses of uncertain matrices. (English) Zbl 0997.65049

The author proposes an approach to rigorously measure, and reduce the effect, of possibly large, structured perturbation in the computation of an inverse matrix. He defines the structured maximal inversion error, that takes into account the structure and not-necessarily small perturbation size. For infinitesimal perturbation he gets a structure condition number. For a wide class of perturbation structures, he shows how to use the convex semidefinte programming to compute bounds on the structured maximal inversion error and structure condition number, and also to compute an approximate inverse. He points out that when the perturbation in unstructured and additive the classical condition number is recovered and the approximate inverse is an operator related to the total least squares.


65F05 Direct numerical methods for linear systems and matrix inversion
65F35 Numerical computation of matrix norms, conditioning, scaling
90C22 Semidefinite programming


Sp; mctoolbox
Full Text: DOI


[1] Abatzoglou, T.J.; Mendel, J.M.; Harada, G.H., The constrained total least squares technique and its applications to harmonic resolution, IEEE trans. signal processing, 39, 1070-1087, (1991) · Zbl 0744.65031
[2] Bartels, S.G.; Higham, D.J., The structured sensitivity of Vandermonde-like systems, Numer. math., 62, 17-33, (1992) · Zbl 0766.65042
[3] Boyd, S.; El Ghaoui, L., Method of centers for minimizing generalized eigenvalues in: numerical linear algebra methods in control, signals and systems (special issue), linear algebra appl., 188, (1993)
[4] S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory, Studies in Applied Mathematics, vol. 15, SIAM, Philadelphia, PA, June 1994 · Zbl 0816.93004
[5] Comon, P., Structured matrices and inverses, Linear algebra for signal processing, IMA,, vol. 69, (1995) · Zbl 0823.15026
[6] Demmel, J., The componentwise distance to the nearest singular matrix, SIAM J. matrix anal. appl., vol. 13, 10-19, (1992) · Zbl 0749.65031
[7] El Ghaoui, L.; Lebret, H., Robust solutions to least-squares problems with uncertain data, SIAM J. matrix anal. appl., 18, 1035-1064, (1997) · Zbl 0891.65039
[8] L. El Ghaoui, R. Nikoukhah, F. Delebecque, LMITOOL: A front-end for LMI optimization, user’s guiide, February 1995. Available via anonymous ftp to ftp.ensta.fr, under /pub/elghaoui/lmitool
[9] Fan, M.K.H.; Tits, A.L.; Doyle, J.C., Robustness in the presence of mixed parametric uncertainty and unmodeled dynamics, IEEE trans. aut. control, 36, 25-38, (1991) · Zbl 0722.93055
[10] Gohberg, I.; Kailath, T.; Olshevsky, V., Fast Gaussian elimination with partial pivoting for matrices with displacement structure, Math. comput., 64, 1557-1576, (1995) · Zbl 0848.65010
[11] Gohberg, I.; Koltracht, I., Structured condition numbers for linear matrix structures, Linear algebra for signal processing, IMA,, vol. 69, (1995) · Zbl 0823.15006
[12] Hagher, W., Condition estimates, SIAM J. sci. statist. comput., 5, 311-316, (1984) · Zbl 0542.65023
[13] Higham, D.J.; Higham, N.J., Backward error and condition of structured linear systems, SIAM J. matrix anal. appl., 13, 162-175, (1992) · Zbl 0747.65028
[14] Higham, N.J., Accuracy and stability of numerical algorithms, (1996), SIAM Philadelphia, PA · Zbl 0847.65010
[15] Moore, R.E., Interval analysis, (1966), Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[16] Moore, R.E., On computing the range of values of a rational function of n variables over a bounded region, Computing, 16, 1-15, (1976) · Zbl 0345.65024
[17] Nemirovsky, A., Several NP-hard problems arising in robust stability analysis, Mcss, 6, 99-105, (1993) · Zbl 0792.93100
[18] Nesterov, Y.; Nemirovskii, A., An interior-point method for generalized linear-fractional problems, Math. programming, ser. B, (1993)
[19] Nesterov, Y.; Nemirovsky, A., Interior point polynomial methods in convex programming: theory and applications, (1994), SIAM Philadelphia, PA
[20] Poljak, S.; Rohn, J., Checking robust nonsingularity is NP-hard, Math. control signals systems, 6, 1-9, (1993) · Zbl 0780.93027
[21] Rohn, J., Systems of linear interval equations, Linear algebra appl., 126, 39-78, (1989) · Zbl 0712.65029
[22] Rohn, J., Nonsingularity under data rounding, Linear algebra appl., 139, 171-174, (1990) · Zbl 0709.65036
[23] Rohn, J., Overestimations in bounding solutions of perturbed linear equations, Linear algebra appl., 262, 55-66, (1997) · Zbl 0880.65018
[24] Rump, S.M., Bounds on the componentwise distance to the nearest singular matrix, SIAM J. matrix anal. appl., 18, 83-103, (1997) · Zbl 0870.65038
[25] Stern, R.J.; Wolkowicz, H., Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations, SIAM J. optim., 5, 286-313, (1995) · Zbl 0846.49017
[26] L. Vandenberghe, S. Boyd, SP, Software for semidefinite programming, user’s guide, December 1994. Available via anonymous ftp to isl.stanford.edu under /pub/boyd/semidef_prog
[27] Vandenberghe, L.; Boyd, S., Semidefinite programming, SIAM rev., 38, 49-95, (1996) · Zbl 0845.65023
[28] Zhou, K.; Doyle, J.; Glover, K., Robust and optimal control, (1995), Prentice-Hall, Englewood Cliffs NJ
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.