A spectral radius that grows first

A rate that is known in advance measured the three classical stationary iterations against their spectral radii, on the model problem where those radii are known in closed form, and found the rates exact. Jacobi’s ρ is 0.99211 at n = 24 and the residual falls by 0.99211 a step, and the site checked it against a formula rather than against a fit.

That worked because the model problem’s iteration matrix is symmetric. This essay is about what the spectral radius promises when it is not.

ρ(A) < 1   ⟹   Aᵏ → 0

is true for every matrix, and it is the whole of what the spectral radius guarantees. It is a statement about a limit. It says nothing at all about the first hundred steps.

What is being drawn #

The matrix is the one from the eigenvalues that are not there: ρ = 0.8 on the diagonal, m above it, everything else zero. Its spectrum is {0.8} with multiplicity six, at every m.

At m = 0 it is normal, and ‖Aᵏ‖ = 0.8ᵏ exactly — asserted as an equality, and asserted to be monotone at every one of the first sixty steps. There is no transient, and that is the control.

At m = 2 the norm rises by four orders of magnitude first.

The eigenvalues are the same. The characteristic polynomial is the same. Every quantity a spectrum can offer is the same, and the behaviour is not.

Where the growth comes from #

Aᵏ for this matrix has a closed form. Write A = 0.8·I + m·N with N the shift; N is nilpotent with N⁶ = 0, and the identity commutes with N, so the binomial theorem applies and terminates:

Aᵏ  =  Σ(j = 0…5)  C(k, j) · 0.8ᵏ⁻ʲ · mʲ · Nʲ

The largest term is the last: C(k,5)·0.8ᵏ⁻⁵·m⁵, a polynomial of degree 5 in k multiplied by a geometric decay — the shape an accumulation that is not a walk would have if its errors were aligned. A polynomial times a decaying exponential rises and then falls, and the turning point is at about k = (n − 1)/(1 − ρ), which for n = 6 and ρ = 0.8 is 25. The measured peak is at step 24.

So the transient is not a numerical artefact and it is not a subtlety about norms. It is the binomial coefficients, and there are n − 1 of them — which is what a defective eigenvalue costs showing up in the powers rather than in the eigenvectors.

The one step, which is not a rounding #

Twenty-five against twenty-four is the kind of discrepancy an approximation is allowed, and it is worth checking whether it is one. Measured over five sizes and five spectral radii, the quoted formula is high in every cell, never low, and by a whole step in most of them:

   n     ρ      peak     (n − 1)/(1 − ρ)     ⌈(n − 2 + ρ)/(1 − ρ)⌉
   4    0.50      5            6.0                    5
   6    0.70     16           16.67                  16
   6    0.80     24           25.0                   24
   8    0.70     23           23.33                  23
  10    0.90     89           90.0                   89
  12    0.95    219          220.0                  219

A one-sided error in every one of twenty-five cells is not an approximation being approximate. The exact statement is available from the same closed form, and it is the ratio of successive terms rather than a derivative: C(k+1, n−1)ρᵏ⁺¹⁻ⁿ⁺¹ / C(k, n−1)ρᵏ⁻ⁿ⁺¹ is ((k+1)/(k−n+2))·ρ, and it falls below one exactly when k(1 − ρ) > n − 2 + ρ. So the peak is at

k*  =  ⌈ (n − 2 + ρ) ⁄ (1 − ρ) ⌉

and the quantity inside the ceiling is exactly one less than the formula the essay quotes. The approximation is therefore always an overstatement, by a full step whenever (n − 2 + ρ)/(1 − ρ) is an integer — which it is in twenty-two of the twenty-five cells, including the hero’s — and by less than a step otherwise. At n = 6, ρ = 0.8: 4.8/0.2 = 24, exactly.

Nothing about the essay’s argument changes; the mechanism is still the binomial coefficients and the scaling in n and in 1/(1 − ρ) is unaltered. What changes is that the position is a formula rather than an estimate, which is what a closed form should give.

The corrected formula can be checked against the figure rather than against the table, which is worth doing because the table and the drawing are different computations.

At four, six and ten variables the drawn peaks are at steps 14, 24 and 44 against a formula giving 14, 24 and 44. The peak height over the same three is 252.6, 1.98·10⁴ and 1.5·10⁸ — five and a half orders of magnitude for a factor of 2.5 in the size, because the largest binomial coefficient is C(k, n−1) and both of its arguments grow.

Along the whole slider — m = 0, 1, 2, 3, 4 — the peak reads 1, 637.4, 1.98·10⁴, 1.5·10⁵ and 6.3·10⁵ and the Kreiss constant reads 0.9998, 221.3, 6,757, 50,880 and 2.1·10⁵. Their ratio reads 1.00, 2.88, 2.93, 2.95 and 3.00, so the constant that bounds the peak from below is off by very nearly a factor of three at every non-normal setting and by nothing at all at the normal one. The theorem’s upper bound e·n·K sits at 16.31·K, so the true peak is 3.0·K and the bracket around it is [1, 16.3] — a factor of sixteen wide, with the answer at a fifth of the way up it and staying there.

That ratio is not constant in the size, which is the other half of it: at four, six and ten variables the peak divided by K reads 2.36, 2.93 and 3.95, while e·n·K divided by the peak reads 4.61, 5.56 and 6.67. So the lower bound loosens and the upper bound loosens, both slowly, and the bracket widens from a factor of eleven to a factor of twenty-six across that range.

And the transient is still being paid for long after it is over. ‖A¹⁶⁰‖ reads 3.12·10⁻¹⁶, 7.82·10⁻⁷, 2.5·10⁻⁵, 1.9·10⁻⁴ and 8·10⁻⁴ across the five superdiagonals — at step 160, six times past the peak, the m = 4 matrix is twelve orders above the normal one with the same spectrum. The powers do go to zero, as the spectral radius promises; where they have got to by any particular step is a different question and the radius does not answer it.

Two routes to the peak #

The peak is a fact about the powers. There is a second quantity that bounds it, computed from somewhere else entirely.

The Kreiss constant is

K  =  sup(|z| > 1)  (|z| − 1) · ‖(zI − A)⁻¹‖₂

— a supremum over the region outside the unit circle of how large the resolvent gets, weighted by the distance from the circle. It is exactly the quantity the pseudospectrum picture is a plot of, integrated in a particular way, and it never multiplies two matrices together.

The Kreiss matrix theorem brackets the peak with it:

K   ≤   supₖ ‖Aᵏ‖   ≤   e · n · K

Measured here: K = 6.76·10³, peak = 1.98·10⁴, and e·n·K = 1.10·10⁵. Both inequalities hold, the lower one with a factor of 2.9 and the upper one with a factor of 5.6.

Two routes to one number, one through the complex plane and one through repeated multiplication, sharing no arithmetic — the habit a rate that is known in advance applies to a convergence factor, applied here to a peak. That is the site’s oldest habit, applied to a quantity nobody thinks of as having two routes.

What the sampling can and cannot break #

The supremum in K is over an unbounded region and the computation samples it: circles of radius 1 + δ for δ over six decades, and forty-eight angles on each.

So what is computed is a lower bound on a supremum, and the direction matters. K ≤ peak is the half the sampling cannot break — a sampled K is smaller than the true K, so if the true one is below the peak the sampled one certainly is. The other half, peak ≤ e·n·K, is the theorem, and a sampled K makes it harder to satisfy rather than easier.

One detail of that sampling is worth recording because it looked like a finding and was not. For a normal matrix the ratio δ/(δ + dist) climbs to 1 only as δ → ∞, so a grid stopping at δ = 2 returns 0.909 for a constant that is exactly 1. The first version of this computation did stop there and reported 0.909 as the normal matrix’s Kreiss constant. It is an artefact of the grid and not of the matrix, and it is the one place in this essay where the control could have been read as a result — the same shape as a small residual read as an accuracy, one level up.

And the transient has no ceiling #

One matrix with a transient is an example. What makes it a statement is that the peak has no bound in terms of the spectrum.

assertTheTransientHasNoCeiling measures the peak at m = 1 to 5 and finds 637, 1.98·10⁴, 1.50·10⁵, 6.29·10⁵ and 1.95·10⁶ — a factor of three thousand across a sweep in which the spectral radius is asserted to be 0.8 at every point.

The peak position does not move: step 24 at every m, because the turning point has no m in it. So the parameter changes how high the excursion goes and not how long it lasts, which is the separation the closed form above predicts.

That holds in twenty-two of the twenty-five cells measured and slips by exactly one step in three of them — n = 8 at ρ = 0.7, n = 10 and n = 12 at ρ = 0.5 — all at m = 1, and all where ρ is small and n is large. The reason is in the closed form rather than in the arithmetic: the m-independence comes from the last binomial term dominating, and at m = 1 the terms carry no m at all, so the second-last one is still comparable and the sum turns a step earlier. The claim is about the regime the figure draws and not about every corner of the family.

Read together, the two corrections say the same thing about what a closed form is worth. The essay derived the shape of the transient from Aᵏ’s binomial expansion and then estimated two of its features — where the peak is, and what it does not depend on — by looking at the dominant term and arguing informally about it. Both estimates are right to within a step and neither is exactly right, and in both cases the exact answer was already in the expansion, one line further down: the ratio of successive terms gives the position, and the size of the second-last term relative to the last gives the condition under which m drops out.

That is a small instance of the habit the whole site is built on. A closed form is not a result until it has been evaluated against the thing it describes, because the step from a formula to a statement about the formula is where the approximations get made, and they are invisible from inside the derivation.

Which norm, and why it does not matter #

A reader’s first objection to a transient is that a norm is a choice, and a different norm might not show one. It is a good objection and the answer is precise.

For any matrix with ρ(A) < 1 there is a norm in which ‖A‖ < 1, so the powers decay monotonically in it. The construction is standard: diagonalise where that is possible and use the eigenvector basis, or take ‖x‖_S = ‖S⁻¹x‖₂ for a suitable S.

The catch is what S costs. The norm in which this matrix contracts is one whose unit ball is enormously elongated, and the equivalence constants between it and the Euclidean norm are exactly the size of the transient — κ(S) ≈ 10⁴ here. So the statement “there is a norm in which it decays” is true and buys nothing: converting a bound in that norm back into a statement about the quantity anybody measures multiplies it by κ(S), and κ(S) is the peak.

This is the same trade as diagonalising a non-normal matrix at all. Bauer–Fike bounds eigenvalue movement by κ(V)·‖E‖, and κ(V) is infinite for a defective matrix, which is why the spectrum predicts nothing there and a pseudospectrum is needed instead. Here κ(S) is finite and is the answer to the question, which is a slightly better situation and not a different one.

The transient is basis-dependent and its size is exactly the price of the basis change that removes it. That is not a way out; it is the same number written twice.

The continuous version, which is where it is famous #

Everything above is about Aᵏ. The analogue for eᵗᴬ is the same phenomenon with the unit circle replaced by the imaginary axis, and it is where the subject is usually met.

eᵗᴬ → 0 if every eigenvalue has negative real part. The transient is bounded below by the continuous Kreiss constant

K  =  sup(Re z > 0)  Re(z) · ‖(zI − A)⁻¹‖₂

and above by e·n·K, the same bracket with the same constant. The matrix here is a discrete example because the powers are cheap to compute exactly and the picture has integers on its horizontal axis; nothing about the mechanism is discrete.

The best-known instance is fluid: the linearised Navier–Stokes operator for plane Couette flow has every eigenvalue in the stable half plane at every Reynolds number, and the flow becomes turbulent anyway. The transient growth of eᵗᴬ reaches a factor proportional to Re², which is large enough at any interesting Reynolds number for a disturbance to leave the linear regime — so the eigenvalue analysis is correct and predicts the wrong thing, which is the site’s wrong-blame verdict applied to a whole literature.

What it costs in practice #

Three consequences, and they are the reason this is not a curiosity about matrix powers.

A stopping rule fires early. An iteration xₖ₊₁ = Axₖ + b monitored by its residual, stopped when the residual has fallen by a factor of 10⁻⁶, will not stop during the transient — it will stop after it, having spent twenty-four steps going backwards. Worse, an iteration monitored by the change between iterates can be told to stop at the peak, where consecutive iterates are large and close.

A linearised stability analysis is wrong about the physics. A flow whose linearised operator has every eigenvalue in the left half plane is asymptotically stable, and the transient growth of eᵗᴬ is what lets a small disturbance grow by a factor of a thousand first — long enough for nonlinear terms to take over and for the flow to become turbulent. That is the standard modern explanation for subcritical transition in shear flows, and it is this figure with eᵗᴬ in place of Aᵏ.

And an error bound built on the radius is not a bound. ‖Aᵏ‖ ≤ Cρᵏ is true for every matrix with some C, and C for this matrix at m = 4 is above 10⁶. A statement of that form with the constant left unnamed is not a statement about anything.

The relationship to the previous essay #

The pseudospectrum and the transient are the same object measured two ways, and the Kreiss constant is the bridge.

If Λ_ε(A) sticks out past the unit circle by an amount d, then K ≥ d/ε — because there is a point z outside the circle with ‖(zI − A)⁻¹‖ ≥ 1/ε and |z| − 1 ≥ d. So a picture that reaches outside the circle is a picture of a lower bound on the transient, readable by eye.

That is why the two essays are the same anchor. One draws the region; the other draws what the region costs.

What to measure instead #

If the spectral radius does not answer the question, something has to, and there are three candidates with different costs.

The norm of the first few powers. Directly measured, exactly right, and costs a matrix multiplication per power. On a small matrix that is the answer; on a large one it is the simulation the analysis was supposed to replace.

The numerical abscissa or its discrete analogue. ‖A‖₂ itself bounds the first step, and the largest eigenvalue of (A + Aᵀ)/2 gives the initial slope of the continuous version. Cheap, and it describes only the beginning: it says whether the growth starts, not how far it goes.

The Kreiss constant. Expensive relative to the abscissa and far cheaper than the powers on a large matrix, because a resolvent norm at one point is one linear solve rather than a product of k matrices, and the number of points needed does not grow with n.

The three answer different questions and a reader deciding between them is deciding how much of the curve they need. The spectral radius describes the right-hand end, the abscissa the left-hand end, and the Kreiss constant the peak between them — which is the part with the transient in it.

Why this is not a small-matrix curiosity #

The matrices in this essay are 6×6, which invites the reading that a real problem would be better behaved. The opposite is true, and the closed form says why.

The peak is set by the binomial coefficients up to C(k, n−1), so it grows with the size of the Jordan structure, and it turns over at (n − 1)/(1 − ρ), so it lasts longer the larger that structure is and the closer ρ is to one. A discretisation refined by a factor of two has a larger n and a ρ closer to 1, and both push in the same direction.

What is small here is n, which makes the transient smaller and shorter than a realistic one. A 6×6 reaching a factor of twenty thousand is the conservative version of the phenomenon rather than an exaggeration of it.

The stopping rule this breaks #

Worth spelling out, because it is the failure a reader is most likely to meet.

An iterative solver monitored by the relative change between iterates stops when ‖xₖ₊₁ − xₖ‖ ≤ tol·‖xₖ‖. During a transient the iterates are large and the differences between them are a small fraction of that largeness, so the test can fire at the top of the excursion — with the error at its worst — and the solver reports success.

A solver monitored by the residual does not have that failure and has a different one: the residual grows during the transient, so a run that would eventually converge looks like a run that is diverging, and a code that aborts on a rising residual aborts on a problem it would have solved.

Both are defensible rules and both are wrong here for the same reason: they read a local property of the sequence as a statement about where it is going, and for a non-normal operator the local property does not carry that information for the first (n − 1)/(1 − ρ) steps.

What is worth carrying #

ρ(A) < 1 is a statement about a limit and this site’s asymptotic verdict exists for exactly this shape of claim. The powers decay in the end, and “in the end” is doing all the work.

The growth is the binomial coefficients, so its height is set by how far the matrix is from normal and its duration by (n − 1)/(1 − ρ). Neither is visible in the spectrum.

And the peak is bracketed by a quantity computed in the complex plane, which is worth having because it is the only thing in this essay that can be computed without multiplying the matrix by itself twenty-four times — and on a large matrix that is the difference between a diagnostic and a simulation.

The continuous-time twin #

The powers of a matrix with spectral radius below one grow before they decay. The exponential of a matrix with every eigenvalue negative does the same thing, and its peak is at a time the closed form names exactly.