Backward Error Analysis For Structured Unitary Matrix Eigenvalue Problems

Structured matrix eigenvalue problems are numerical algebra problems which have been extensively studied in the last ten years. They appear in many scientific and engineering applications. For structured matrix eigenvalue problems, the key problem of computational mathematics is to develop structure-preserving algorithms. Structured backward error analysis may be done to test the strong stability of a numerical algorithm.In this paper, backward errors for seven kinds of structured unitary matrix eigenvalue problems are discussed. All the problems are open questions raised by Tisseur[8]. We give expressions or upper and lower bounds of the normwise backward errors for six kinds of problems. These bounds can be easily computed. We also show that the other one is a singly structured problem for which the backward error analysis has been essentially solved by Sun[1] and Tisseur[8]. All the results can be regarded as positive answers to several open questions raised by Tisseur [8].We also compare structured backward errors with non-structured backward errors for some kinds of structured unitary matrix eigenvalue problems. Significant difference can be shown by numerical tests.This paper is composed of five parts.In the first part, we sunmarize the historical development of backward error analysis and structured eigenvalue problems , introduce the present progress of the research on structured eigenvalue problems. Furthermore, we show the purpose of this paper.The second part consists of seven sections. In this part, we discuss the backward errors for seven kinds of structured unitary matrix eigenvalue problems.In the third part, we compare structured backward errors with non-structured backward errors for some kinds of structured unitary matrix eigenvalue problems discussed in part two.In the forth part, we present some results of numerical tests , and show the difference between structured and non-structured backward errors.Finally, in the fifth part, we give some remarks on the main results in this paper.