Source author record

Ricardo S. Leite

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NA math.SP math.DS

Catalog footprint

Research overview

4works

3topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

The geometry of spectral interlacing

We provide a detailed description of the maps associated with spectral interlacing, for rank one perturbations and bordering of symmetric and Hermitian matrices. The arguments rely on standard techniques of nonlinear analysis.

preprint2011arXiv

Dynamics of the symmetric eigenvalue problem with shift strategies

A common algorithm for the computation of eigenvalues of real symmetric tridiagonal matrices is the iteration of certain special maps $F_σ$ called shifted $QR$ steps. Such maps preserve spectrum and a natural common domain is ${\cal T}_Λ$ , the manifold of real symmetric tridiagonal matrices conjugate to the diagonal matrix $Λ$ . More precisely, a (generic) shift $s \in \RR$ defines a map $F_s: {\cal T}_Λ\to {\cal T}_Λ$ . A strategy $σ: {\cal T}_Λ\to \RR$ specifies the shift to be applied at $T$ so that $F_σ(T) = F_{σ(T)}(T)$ . Good shift strategies should lead to fast deflation: some off-diagonal coordinate tends to zero, allowing for reducing of the problem to submatrices. For topological reasons, continuous shift strategies do not obtain fast deflation; many standard strategies are indeed discontinuous. Practical implementation only gives rise systematically to bottom deflation, convergence to zero of the lowest off-diagonal entry $b(T)$ . For most shift strategies, convergence to zero of $b(T)$ is cubic, $|b(F_σ(T))| = Θ(|b(T)|^k)$ for $k = 3$ . The existence of arithmetic progressions in the spectrum of $T$ sometimes implies instead quadratic convergence, $k = 2$ . The complete integrability of the Toda lattice and the dynamics at non-smooth points are central to our discussion. The text does not assume knowledge of numerical linear algebra.

preprint2010arXiv

Convergence rates to deflation of simple shift strategies

The computation of eigenvalues of real symmetric tridiagonal matrices frequently proceeds by a sequence of QR steps with shifts. We introduce simple shift strategies, functions sigma satisfying natural conditions, taking each n x n matrix T to a real number sigma(T). The strategy specifies the shift to be applied by the QR step at T. Rayleigh and Wilkinson's are examples of simple shift strategies. We show that if sigma is continuous then there exist initial conditions for which deflation does not occur, i.e., subdiagonal entries do not tend to zero. In case of deflation, we consider the rate of convergence to zero of the (n, n-1) entry: for simple shift strategies this is always at least quadratic. If the function sigma is smooth in a suitable region and the spectrum of T does not include three consecutive eigenvalues in arithmetic progression then convergence is cubic. This implies cubic convergence to deflation of Wilkinson's shift for generic spectra. The study of the algorithm near deflation uses tubular coordinates, under which QR steps with shifts are given by a simple formula.

preprint2008arXiv

The Asymptotics of Wilkinson's Iteration: Loss of Cubic Convergence

One of the most widely used methods for eigenvalue computation is the $QR$ iteration with Wilkinson's shift: here the shift $s$ is the eigenvalue of the bottom $2\times 2$ principal minor closest to the corner entry. It has been a long-standing conjecture that the rate of convergence of the algorithm is cubic. In contrast, we show that there exist matrices for which the rate of convergence is strictly quadratic. More precisely, let $T_X$ be the $3 \times 3$ matrix having only two nonzero entries $(T_X)_{12} = (T_X)_{21} = 1$ and let $T_L$ be the set of real, symmetric tridiagonal matrices with the same spectrum as $T_X$ . There exists a neighborhood $U \subset T_L$ of $T_X$ which is invariant under Wilkinson's shift strategy with the following properties. For $T_0 \in U$ , the sequence of iterates $(T_k)$ exhibits either strictly quadratic or strictly cubic convergence to zero of the entry $(T_k)_{23}$ . In fact, quadratic convergence occurs exactly when $\lim T_k = T_X$ . Let $X$ be the union of such quadratically convergent sequences $(T_k)$ : the set $X$ has Hausdorff dimension 1 and is a union of disjoint arcs $X^σ$ meeting at $T_X$ , where $σ$ ranges over a Cantor set.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.