ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

Contributed talks on Eigenvalue Algorithms and Pseudospectra

Mon 15:00–15:30, Room AV 03.12, Chair: Kensuke Aishima
A quasi-Newton method for inverse eigenvalue problems
Kensuke Aishima (The University of Tokyo)

Inverse eigenvalue problems arise from a variety of applications. We focus on the following inverse eigenvalue problem. Let $A_{0},A_{1},\ldots ,A_{n}$ be $n\times n$ real symmetric matrices. For any real vector ${c}=(c_{1},\ldots ,c_{n})^{T}$, we define $A({c})=A_{0}+c_{1}A_{1}+\cdots +c_{n}A_{n}$. Also, we denote the eigenvalues of $A({c})$ by $\lambda_{1}({c})\le \cdots \le \lambda_{n}({c})$. For $n$ real numbers $\lambda_{1}^{*}\le \cdots \le \lambda_{n}^{*}$, our aim is to find a real vector ${c}$ such that $\lambda_{k}({c})=\lambda_{k}^{*}$ for $k=1,\ldots ,n$.

We propose a new quasi-newton method for such an inverse eigenvalue problem and prove quadratic convergence whenever $\lambda_{1}^{*}< \cdots < \lambda_{n}^{*}$. The proposed method is viewed as an improved version of a typical quasi-newton method by Friedland, Nocedal, and Overton [1, Method III]. This existing method requires the Cayley transform, which takes $O(n^{3})$ operations, to ensure the orthogonality of the iterative matrices. The proposed method can refine the orthogonality without the Cayley transform. As a result, if the approximate Jacobian matrix is formed in $O(n^{3})$ time, the proposed method is significantly faster than any quasi-Newton method using the Cayley transform.

  1. S. Friedland, J. Nocedal, and M. Overton, The formulation and analysis of numerical methods for inverse eigenvalue problems, SIAM Journal on Numerical Analysis, 24(3) (1987), pp. 634–667.