# Shifted QR II

Dhillon: In [136,p.329], Wilkinson notes that
‘The extreme sensitivity of the computed eigenvector to very small
changes in λ [σ in our notation] may be turned to practical advantage
and used to obtain independent eigenvectors corresponding to coincident
or pathologically close eigenvalues’.
Wilkinson proposed that such nearby eigenvalues be ‘artificially separated’ by a tiny amount.

# Shifted QR Submission

## 1 Introduction
Numerical analysis, dynamical systems.
Beta example
Two principles: transients, symmetry breaking.

## 2 Rapid deflation for GW (?) in exact arithmetic

The k-shift strategy decouples rapidly on matrices with $\kappa_V\le 2^k$.

OR

**improve $k^2$ to $O(k)$?**

already mostly written

**need some optimization to choose net size**
(clean up net writeup)

## 3 Analyis of deflation (exact arithmetic, assuming some invariant)

Need one more invariant: gap.

Gap + kappa_V -> preserved under deflation at scale delta'< delta

## 4 Shattering

## 5 Finite arithmetic

Blackbox: Hessenberg, rootfinding, QR step, implicit Q storage, charpoly

**What kind of error is required for the Ritz values?**
Error analysis of Hessenberg, bulge-chasing (QR step).
Some kind of blackbox lemma about error of approximate QR step (used in all three cases).

How do numerical analysts compute the determinant?

Decide which solver to use for Ritz values.

Blackbox schur form of tiny matrices.

## 6 Optimization of shattering bounds (later)

## Bibliography

* Francis original papers: The QR transformation a unitary analogue to the LR transformation—Part 1, The QR transformation—part 2
* Computing one Francis step: A Multishift QR Iteration without Computation ofthe Shifts, Dubrulle and Golub.