A rational approximant of degree five turns a six-by-six problem into a thirty-six-by-thirty-six one, and thirty-six numbers come back. Six are the answer. The rest are exact eigenvalues of the approximant, lying where the function it approximates is not a real number at all.
A rational approximant with five poles turns a 6 × 6 nonlinear eigenvalue problem into a 36 × 36
standard one. Thirty-six numbers come back. Six of them are the answer.
That ratio is not an artefact of a small example. The linearisation has n(m+1) rows by construction,
so the fraction of returned values that mean anything is 1/(m+1) and falls as the approximation
improves. A better approximation returns proportionally more noise. That is the opposite of the
arrangement rank is a decision describes, where a better computation
makes a decision easier; here it makes the sorting problem larger while making the answers better.
Fig. 1 Thirty-six eigenvalues, six of which are answers. The rest are past the branch point.
They are not errors. Every one of the thirty-six is an exact eigenvalue of the matrix that was
factorised, to the rounding level, and the factorisation did nothing wrong. They are eigenvalues of
the approximant, and the approximant is a different function from the one that was asked about.
Of the thirty-six, twelve are real. Six lie in the target set and agree with the closed form to
6·10⁻⁴. The other six lie between −0.53 and −0.84, and the branch point is at −0.4.
Every one of them is past the branch point — to the left of it, where γ√(λ + c) is the square
root of a negative number and is not a real quantity at all. The remaining twenty-four are complex
and are discarded the same way.
So the residual that is useless as a measure of accuracy is decisive as a filter, and it is worth
being precise about the two roles.
Against the approximant, all thirty-six eigenvalues have a residual at rounding. That is the
definition of an eigenvalue and it distinguishes nothing.
Against the original problem T(λ) = A − λI + γ√(λ + c)I, the six wanted values have residuals of
5·10⁻⁶ to 3·10⁻⁵ — small, and tracking the forward error as
the problem the solver was actually given
measures. The six spurious ones do not have a residual. Evaluating T there requires the square
root of a negative number, so the quantity does not exist rather than being large.
That is a stronger separation than a threshold. A filter based on “reject anything whose residual
exceeds ε” needs an ε and gets it wrong near the boundary; a filter based on “reject anything outside
the domain of the function” needs nothing and cannot be marginal. The implementation reports
Infinity with a flag rather than a NaN, because a NaN reaching a figure is a defect and a number
outside a domain is a finding.
It is worth working out, because the location is what makes the filter work and it is not obvious
that it should be that clean.
The approximated problem is det(A + c₀I − λI + Σ αⱼ/(λ − ξⱼ) I) = 0. Multiplying through by
∏(λ − ξⱼ)ⁿ turns it into a polynomial equation of degree n(m+1), which is where the count comes from.
Its roots are the eigenvalues of the linearisation.
The rational function r(λ) matches γ√(λ + c) closely on the target set, so wherever the original
equation has a root, so does the approximated one — those are the six. Away from the target set r is
under no obligation, and in particular on the branch cut, where g does not exist, r is a
perfectly ordinary rational function with poles on the cut and it oscillates between them. Between
two consecutive poles it passes through every real value, including whatever value makes the
approximated equation vanish.
So the extras are trapped between the poles, and the poles are on the cut by construction — because
that is where they were put in order to approximate the singularity. The thing that makes the
approximation good is the thing that puts the spurious eigenvalues somewhere identifiable — the same
kind of accident the circulant that cannot be indefinite
records, where a structure imposed for one reason forbids an outcome for a different one.
That is a piece of luck and it is worth saying so rather than presenting it as design. An approximant
whose poles were somewhere else — in the complex plane, or scattered — would produce spurious
eigenvalues scattered with them, and the filter would have to be a threshold after all.
This field now has three, and they are different in a way worth distinguishing because the word is
the same in each case.
Eigenvalues of a linearisation at infinity, from
an eigenvalue with no value: a singular leading coefficient
sends some of the polynomial’s eigenvalues to infinity, and they are genuine features of the problem
rather than artefacts. The count is a degree, computable exactly, and nothing about them is
spurious — they simply are not finite.
Eigenvalues that are not eigenvalues at all, from
the eigenvalues that are not there: a non-normal
matrix whose computed spectrum moves enormously under a rounding-level perturbation, so the numbers
returned are not close to any eigenvalue of the matrix that was handed over. A failure of the
arithmetic, on the real problem.
Eigenvalues of the approximant, here: numbers that are exactly right about a problem nobody
asked. Not a failure of anything. The arithmetic is correct, the object is correct, and the object
is not the one in question.
The three need to be told apart because the responses differ completely. The first is counted. The
second is a reason to distrust the computation. The third is filtered, cheaply, by asking the
original function a question — and the filter works precisely because nothing went wrong.
A caller who takes all twelve real values as eigenvalues has six extra numbers between −0.53 and
−0.84, in a region a physical problem might well care about. They are stable under refinement — add
poles and there are more of them, in the same place — so they do not look like noise. They are
reproducible across seeds and precisions, so they do not look like rounding. And they have small
residuals against the matrix any diagnostic would naturally check.
Everything about them looks like an answer except the one test nobody runs.
That is the shape this site keeps recording and it is worth the repetition: the failures worth
writing about are the ones where every available check passes. It is
an eigenvalue count that cannot be slightly wrong
turned inside out — there an integer is right or grossly wrong and cannot be subtly wrong; here a
list of numbers is subtly wrong in a way that looks like being right.
There is a second route to the same question and it is worth naming because it comes from a
different part of this field.
A contour integral counts the eigenvalues of T inside a region — the real T, not an approximant —
and the count is an integral that is an integer. It needs no approximation, no linearisation and no
filter; it needs the ability to solve with T(z) at points on a contour, which is available whenever
T can be evaluated. A problem with infinitely many eigenvalues
is that construction, and
a ceiling with a knob on it is what it took to make it
return the eigenvalues themselves rather than only how many there are.
So the two halves of this field answer the same question by opposite routes. Approximate-then-solve
returns everything and requires a filter; count-then-extract returns only what is inside a region and
requires a region. Neither is strictly better, and the useful observation is that the filter and
the contour are the same test: both ask the original function about a candidate, and both work
because the original function is available even though it cannot be linearised.
The filter above works because this problem’s difficulty is a branch cut on the real axis and the
approximant’s poles are on it. A general implementation cannot rely on that, and it is worth setting
out what it does rely on, because the weaker version is still usable.
The weakest usable test is the residual against T, with a threshold. For a candidate λ and its
vector x, compute ‖T(λ)x‖ / (‖A‖ + |λ| + |g(λ)|), which is a backward error for the original problem,
and reject anything above a multiple of the approximation error ‖g − r‖. That threshold is available:
it is the term the fit already measured, and a genuine eigenvalue’s residual is of that size by the
tracking measured in
the problem the solver was actually given, while
a spurious one’s is of the size of the function itself.
The gap between those two is orders here — 3·10⁻⁵ against numbers of order one — so the threshold is
not delicate, and the measurement that makes it safe is one this field already produces for a
different reason. That is worth noticing: the quantity that says how accurate the answer is and the
quantity that says which returned numbers are answers turn out to be the same quantity, used twice.
What the general test costs is one evaluation of g and one matrix–vector product per candidate,
against n(m+1) candidates. On the example here that is thirty-six evaluations of a square root,
which is nothing against the factorisation that produced them.
The two failure modes of the threshold version are worth stating. A candidate very close to a pole of
the approximant can have a small residual against T by accident, because T(λ) is being evaluated
where r is enormous and the comparison is dominated by scale — which is why the denominator carries
|g(λ)| rather than being a fixed norm. And a genuine eigenvalue that the approximation moved a long
way can be rejected, which is the same failure in the other direction and is a symptom that the
target set was wrong rather than that the filter was.
An implementation that returns n(m+1) numbers has told its caller almost nothing. What it should
return is the numbers that survived the filter, the count that did not, and the residual against T
for each survivor.
The count matters as much as the list. Six wanted values out of twelve real ones is an ordinary
outcome; six out of twenty would say the approximant has poles somewhere unexpected, and six out of
seven would say the target set is admitting spurious values into its own window — which is what
happens on a target set that reaches too close to the cut, — which is what a rank decision has to do when the gap
closes, as the cheap rank and what it cannot see
records — and is why the sweeps in
an error committed before the arithmetic stop
where they do.
None of those three numbers costs anything beyond what has already been computed. All three are
thrown away by an interface that returns a list of eigenvalues.
The count of extras, as a diagnostic in its own right #
The number of returned values that survive the filter is worth watching across a sweep rather than at
one setting, because how it changes says something the individual counts do not.
At two poles, eighteen eigenvalues come back and six survive. At five poles, thirty-six come back and
six survive. At eight, fifty-four come back and six survive. The survivor count is constant while
the total grows linearly, which is exactly the behaviour a correct construction should have: the
problem has six eigenvalues in the region and the approximation degree does not change that.
A survivor count that grows with the degree is a signal, and it means one of two things. Either the
target set is admitting spurious values into its own window — which happens when the region reaches
close enough to the branch point that the poles and the region overlap, and is the reason the sweeps
in a neighbouring essay stop where they do. Or the filter’s threshold is too loose and is passing
near-poles, which the scaled denominator is there to prevent.
A survivor count that falls with the degree is the other signal and it is worse: it means genuine
eigenvalues are being rejected, which happens when the approximation has moved one so far that its
residual against T exceeds the threshold. That is the case where the target set is wrong rather than
the filter, and adding poles is the fix rather than loosening the test.
So three numbers — the total, the survivors, and how the survivors move with the degree — give a
diagnosis of which part of the chain is misconfigured, at no cost beyond a count. It is a small thing
and it is the sort of small thing that turns an opaque failure into a legible one, which is what
every measurement in this collection is ultimately for.
Why this does not happen in the rest of the field #
Worth one closing note, because a reader who has come through the polynomial field in order will
not have met this before and might reasonably wonder what changed.
A linearisation of a matrix polynomial returns dn eigenvalues for a degree-d polynomial of size n,
and every one of them is an eigenvalue of the polynomial. That is what the word linearisation
means: the pencil’s elementary divisors match the polynomial’s, so nothing extra appears and nothing
is lost. The quadratic field’s 2n numbers are all answers.
Here the object being linearised is not the problem. It is an approximation to it, chosen by the
caller, and the extras belong to the approximation rather than to the construction. So the count
n(m+1) is honest — that is genuinely how many eigenvalues T̃ has — and the mismatch is between T̃ and
T rather than between the linearisation and T̃.
That is the same distinction the whole field turns on, arriving in the form of a list of numbers
rather than of an error term, and it is perhaps the most concrete way to see it: a reader who has
been told that the approximation is a separate error source can now count it.
Fig. 2 Two poles: eighteen eigenvalues, six answers, and the extras already on the cut.Fig. 3 Three, and the answers have moved closer to the closed form.Fig. 4 Four, where the crowd to the left has grown with the matrix.Fig. 5 Six, and the ratio of noise to answer is now six to one.Fig. 6 Eight, which is where the fit stops determining its own coefficients.Fig. 7 The residual that filters them, and the two that do not.Fig. 8 The approximation whose poles decide where the extras go.Fig. 9 And the other basis, which produces the same problem at nd rather than n(m+1).Fig. 10 A pencil with no infinite eigenvalues.Fig. 11 And one with four, which are genuine rather than spurious.Fig. 12 The count of infinite eigenvalues, as a degree.Fig. 13 Eigenvalues that move enormously under a rounding-level perturbation.Fig. 14 And the region they can be found in.Fig. 15 A count that is exact because it is a degree.Fig. 16 A count that is exact because it is an integral of an integer.Fig. 17 And what it took to turn that count into the eigenvalues themselves.Fig. 18 The other route, which returns nothing it was not asked for.Fig. 19 An infinite spectrum, where returning everything is not an option.Fig. 20 Deciding whether a matrix is singular, which is what an eigenvalue test is.Fig. 21 A certificate that passes on a case it should refuse.Fig. 22 And the choice between refusing and answering wrongly.Fig. 23 A verdict that can be “do not know”, in the interval field.Fig. 24 The field’s opening picture, where every returned value was an answer.Fig. 25 Six exact linearisations, none of which returns anything spurious.Fig. 26 A class whose spectrum is real by theorem, so nothing has to be filtered.Fig. 27 A structure that says where the eigenvalues must be.Fig. 28 A threshold-based filter, for contrast with a domain-based one.Fig. 29 An estimate with a spread, where a threshold has to be chosen.Fig. 30 The hero again, beside the residuals that sort it.