Higham, Nicholas J. Computing a nearest symmetric positive semidefinite matrix. (English) Zbl 0649.65026 Linear Algebra Appl. 103, 103-118 (1988). 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 Cited in 2 ReviewsCited in 137 Documents 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 Keywords:nearest positive semidefinite matrix; 2-norm; Frobenius norm; bisection algorithm; positive definiteness; Numerical examples Software:LINPACK PDF BibTeX XML Cite \textit{N. J. Higham}, Linear Algebra Appl. 103, 103--118 (1988; Zbl 0649.65026) Full Text: DOI OpenURL References: [1] Bouldin, R., Positive approximants, Trans. amer. math. soc., 177, 391-403, (1973) · Zbl 0264.47020 [2] Bouldin, R., Operators with a unique positive near-approximant, Indiana univ. math. J., 23, 421-427, (1973) · Zbl 0269.47010 [3] 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 [4] 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 [5] Demmel, J.W., On condition numbers and the distance to the nearest III-posed problem, Numer. math., 51, 251-289, (1987) · Zbl 0597.65036 [6] Dongarra, J.J.; Bunch, J.R.; Moler, C.B.; Stewart, G.W., {\sclinpack} users’ guide, (1979), SIAM Publ Philadelphia · Zbl 0476.68025 [7] Fan, K.; Hoffman, A.J., Some metric inequalities in the space of matrice, Proc. amer. math. soc., 6, 111-116, (1955) · Zbl 0064.01402 [8] Fletcher, R., Semi-definite matrix constraints in optimization, SIAM J. control optim., 23, 493-513, (1985) · Zbl 0567.90088 [9] 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 [10] Gil, P.E.; Murray, W.; Wright, M.H., Practical optimization, (1981), Academic London [11] Golub, G.H.; Van Loan, C.F., Matrix computations, (1983), Johns Hopkins U.P Baltimore · Zbl 0559.65011 [12] Halmos, P.R., Positive approximants of operators, Indiana univ. math. J., 21, 951-960, (1972) · Zbl 0263.47018 [13] Higham, N.J., Computing the polar decomposition—with applications, SIAM J. sci. statist. comput., 7, 1160-1174, (1986) · Zbl 0607.65014 [14] N.J. Higham, The symmetric procrusters problem, BIT, to appear. [15] Meinguet, J., Refined error analyses of Cholesky factorization, SIAM J. numer. anal., 20, 1243-1250, (1983) · Zbl 0528.65014 [16] Parlett, B.N., Progress in numerical analysis, SIAM rev., 20, 443-456, (1978) · Zbl 0408.65002 [17] Parlett, B.N., The symmetric eigenvalue problem, (1980), Prentice-Hall Englewood Cliffs, N.J · Zbl 0431.65016 [18] 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 [19] Strang, G., Introduction to applied mathematics, (1986), Wellesley-Cambridge Press Wellesley, Mass · Zbl 0618.00015 [20] 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. [21] 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.