Can QR algorithm find repeat eigenvalues (https://en.wikipedia.org/wiki/QR_algorithm) ? I.e. Does it support the case when not all N eigen value for real matrix N x N are distinct?
How extend QR algorithm to support finding complex eigenvalues?
Can QR algorithm find repeat eigenvalues (https://en.wikipedia.org/wiki/QR_algorithm) ? I.e. Does it support the case when not all N eigen value for real matrix N x N are distinct?
How extend QR algorithm to support finding complex eigenvalues?
In principle yes. It will work if the eigenvalues are really all eigenvalues, i.e., the algebraic and geometric multiplicity are the same.
If the multiple eigenvalue occurs in an Jordan-block of size
s
, then the unavoidable floating point error during the iteration will almost surely result in a star-shaped perturbation into an eigenvalue cluster with relative error of sizemu^(1/s)
wheremu
is the machine constant of the floating point data type.The reason this happens is that on the irreducible invariant subspace corresponding to a Jordan block of size
s
the characteristic polynomial of the reduction of the linear operator to this subspace has is(λ-λ[j])^s
. During the computation this gets perturbed to(λ-λ[j])^s+μq(λ)
which in first approximation has roots close toλ[j]+μ^(1/s)*z[k]
, wherez[k]
denotes thes
roots of0=z^s+q(λ[k])
. What the perturbation functionq
is is quite random, accumulated floating point truncation errors, and depends on details of the method.