# zbMATH — the first resource for mathematics

Computing a nearest symmetric positive semidefinite matrix. (English) Zbl 0649.65026
The problem of computing a nearest positive semidefinite matrix (notation used $$X\geq 0)$$ to an arbitrary real matrix A is considered. The criterion of approximation is the distance $$\delta (A)=\min_{X=X^ T\geq 0}\| A-X\|$$ where the norm is chosen to be either Frobenius or 2-norm. The paper consists of two parts. In the first part the author proves that the nearest unique positive approximant $$X_ F$$ of A in the Frobenius norm is $$X_ F=(B+H)/2,$$ where $$B=(A+A^ T)/2$$ and H is the symmetric polar factor of B, and the corresponding distance from A is $$\delta^ 2_ F(A)=\sum_{\lambda_ i(B)<0}\lambda^ 2_ i(B)+\| C\|_ F^ 2,$$ where $$C=(A-A^ T)/2.$$
In the second part the problem is studied in 2-norm. Examining from a computational view point the famous Halmos formula for the distance $$\delta_ 2(A)$$ the author proposes two algorithms to estimate $$\delta_ 2(A)$$ as well as the positive approximant (which is not unique in general): (i) an efficient bisection algorithm of low accuracy that is $$\alpha \geq \delta_ 2(A)\leq \alpha +2\max \{f\alpha,tol\},$$ where f is a relative error tolerance and tol is an absolute error tolerance; (ii) a hybrid Newton-bisection type algorithm for high accuracy computations. The problem of computational testing for positive definiteness as well as some details concerning the implementation of algorithm (ii) are discussed. Numerical examples are presented.
Reviewer: V.G.Rumchev

##### MSC:
 65F30 Other matrix algorithms (MSC2010) 15A60 Norms of matrices, numerical range, applications of functional analysis to matrix theory 15B48 Positive matrices and their generalizations; cones of matrices 65K05 Numerical mathematical programming methods 90C25 Convex programming
LINPACK
Full Text:
##### References:
  Bouldin, R., Positive approximants, Trans. amer. math. soc., 177, 391-403, (1973) · Zbl 0264.47020  Bouldin, R., Operators with a unique positive near-approximant, Indiana univ. math. J., 23, 421-427, (1973) · Zbl 0269.47010  Byers, R., A bisection method for measuring the distance of a stable matrix to the unstable matrices, (1986), Dept. of Mathematics, North Carolina State Univ Raleigh, Manuscript  Cybenko, G.; Van Loan, C.F., Computing the minimum eigenvalue of a symmetric positive definite Toeplitz matrix, SIAM J. sci. statist. comput., 7, 123-131, (1986) · Zbl 0626.65030  Demmel, J.W., On condition numbers and the distance to the nearest III-posed problem, Numer. math., 51, 251-289, (1987) · Zbl 0597.65036  Dongarra, J.J.; Bunch, J.R.; Moler, C.B.; Stewart, G.W., {\sclinpack} users’ guide, (1979), SIAM Publ Philadelphia · Zbl 0476.68025  Fan, K.; Hoffman, A.J., Some metric inequalities in the space of matrice, Proc. amer. math. soc., 6, 111-116, (1955) · Zbl 0064.01402  Fletcher, R., Semi-definite matrix constraints in optimization, SIAM J. control optim., 23, 493-513, (1985) · Zbl 0567.90088  Friedland, S.; Nocedal, J.; Overton, M.L., The formulation and analysis of numerical methods for inverse eigenvalue problems, SIAM J. numer. anal., 24, 634-667, (1987) · Zbl 0622.65030  Gil, P.E.; Murray, W.; Wright, M.H., Practical optimization, (1981), Academic London  Golub, G.H.; Van Loan, C.F., Matrix computations, (1983), Johns Hopkins U.P Baltimore · Zbl 0559.65011  Halmos, P.R., Positive approximants of operators, Indiana univ. math. J., 21, 951-960, (1972) · Zbl 0263.47018  Higham, N.J., Computing the polar decomposition—with applications, SIAM J. sci. statist. comput., 7, 1160-1174, (1986) · Zbl 0607.65014  N.J. Higham, The symmetric procrusters problem, BIT, to appear.  Meinguet, J., Refined error analyses of Cholesky factorization, SIAM J. numer. anal., 20, 1243-1250, (1983) · Zbl 0528.65014  Parlett, B.N., Progress in numerical analysis, SIAM rev., 20, 443-456, (1978) · Zbl 0408.65002  Parlett, B.N., The symmetric eigenvalue problem, (1980), Prentice-Hall Englewood Cliffs, N.J · Zbl 0431.65016  Press, W.H.; Flannery, B.P.; Teukolsky, S.A.; Vetterling, W.T., Numerical recipes: the art of scientific computing, (1986), Cambridge U.P Cambridge · Zbl 0587.65003  Strang, G., Introduction to applied mathematics, (1986), Wellesley-Cambridge Press Wellesley, Mass · Zbl 0618.00015  Van Loan, C.F.; Datta, B.N., How near is a stable matrix to an unstable matrix?, Linear algebra and its role in systems theory, Vol. 47, 465-478, (1985), Amer. Math. Soc.  Wilkinson, J.H., A priori error analysis of algebraic processes, (), 629-640, Moscow · Zbl 0197.13301
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.