Affine iteration 2026-10-25
Iterating an affine map gives . A fixed point exists exactly when is in the image of a linear map . If the spectral radius of is below one, its matrix powers tend to zero and every orbit converges to the unique fixed point .
Affine recurrence Created 2026-09-24 Updated 2026-11-05
An affine recurrence on a finite-dimensional vector space has the form , where is a fixed linear operator and a fixed vector. Induction gives
The sum is empty at . If is invertible, the unique fixed point is , and subtracting it reduces the recurrence to . The sum formula remains valid when is singular, even when no fixed point exists. For example, gives the arithmetic progression . A stable affine recurrence additionally has spectral radius below one and converges to its fixed point.
An algebra homomorphism onto a semisimple Banach algebra is continuous. To see the spectral mechanism, suppose and . For any , choose with and , and set , . Apply the spectral-radius three-circle inequality to . On the outer circle its norm tends uniformly to ; on the circle of radius its spectral radius is bounded by . Hence for every , so . The unit criterion for the Jacobson radical gives , and the closed graph theorem finishes the proof.
A stationary iterative method for a linear system converges to its specified fixed point for every initial vector if and only if its iteration matrix satisfies , where the spectral radius is the largest modulus of an eigenvalue.[ref]
For a diagonalizable matrix, write . Then , so each eigenvector coefficient tends to zero exactly when its eigenvalue has modulus less than one. For a general matrix, the Jordan normal form gives the same result: a Jordan block with a nilpotent matrix of size satisfies
If , every coefficient tends to zero because exponential decay beats any fixed polynomial in ; if , the block vanishes once . Conversely, an eigenvector with provides an initial error that cannot tend to zero. For a real matrix with complex eigenvalues, the same obstruction appears in the real invariant subspace spanned by the real and imaginary parts of an eigenvector.
The words "every initial vector" matter. For example, fails the criterion, but still tends to zero. Here a generic initial error has a nonzero first coordinate and diverges; the exceptional errors lie on the second coordinate axis. With , generic errors oscillate rather than diverge in norm, while the same exceptional axis still converges. Both are valid matrix splittings with and . In general the convergent errors form the direct sum of the generalized eigenspaces for ; if , this is a proper linear subspace.
A small spectral radius describes eventual convergence, but does not imply that the Euclidean norm of the error decreases on every step for a non-normal matrix. An operator norm bound does give the stepwise estimate . For a real symmetric matrix, the matrix 2-norm equals its spectral radius, making this particularly direct.
Let be a real symmetric positive-definite matrix, with diagonal and strictly lower triangular. Put and for . The matrix norm induced by an energy norm reduces the question to . Direct multiplication and give
The left side is positive semidefinite. The matrix following the scalar coefficient on the right is positive-definite, since has positive diagonal and is an invertible matrix. For , every eigenvalue of therefore lies in . Hence its spectral radius is below one and . Iteration errors consequently decay geometrically in the energy norm. The argument proves convergence from every initial vector, without requiring the original iteration matrix to be symmetric.
For the Jacobi iteration for a three-variable tridiagonal system,
An orthonormal eigenbasis is
with eigenvalues , , and , respectively. These are error modes: their shapes persist under the iteration matrix, while their coefficients change. Direct multiplication verifies them, or expansion of the determinant gives . Thus and convergence holds for every starting vector.
With , the initial forward error has coefficients
For ,
The zero mode disappears after one sweep; the negative mode alternates in sign. The Euclidean norm drops by exactly per sweep from onward. The first norm drop is different because includes the zero mode. A starting error proportional to would disappear entirely in one sweep, faster than the spectral radius predicts for generic errors.
Figure 1.
Computed Jacobi method error curves and eigenvector modes for the original three-variable tridiagonal matrix
. Details.
The curves are computed iterates and exact formulas for this linear system. Since , the same eigenvectors have eigenvalues , , and for . They prove that is a positive-definite matrix, and give the condition number used in residual and forward error in a stationary iteration.
The spectral radius of the matrix exponential gives the lower bound through the spectral abscissa . Differentiating the squared Euclidean norm along and bounding its Hermitian quadratic form gives the upper bound through the Euclidean logarithmic norm . A non-normal matrix can have despite , allowing transient growth before its ultimate decay.
For the Gauss-Seidel iteration for a two-variable positive-definite system, define the forward error by and . Subtract the two exact solution equations from the two update equations:
The fresh first coordinate passes the old second-coordinate error through two successive factors. The iteration matrix is therefore
Its eigenvalues are and , as seen from the determinant. The zero eigenvalue explains why the old first-coordinate error disappears completely: the first row overwrites it. After one sweep, every remaining forward error lies on the eigenvector line spanned by .
For this zero start, , so the exact vectors for are
The Euclidean norm of the forward error decreases by exactly per sweep from onward. The first decrease is different because the initial error has not yet reached that eigenvector line. Each row update moves horizontally or vertically in the coordinate plane; sweep endpoints then approach the solution along one straight line.
Figure 1.
Computed row-by-row Gauss-Seidel method trajectory and exact forward error contraction for the original two-variable linear system
. Details.
The linear-system residual is an independent way to check the calculation. Completing a sweep satisfies the second row exactly, but changing disturbs the first row:
Thus a zero residual in the last updated row alone does not certify a solution; inspect the complete linear-system residual.
For the same matrix, the stale schedule of the Jacobi method gives the iteration matrix
Here its eigenvalues are , whereas the fresh schedule gives . This comparison belongs to this particular linear system; it is not a universal relation between the two methods' spectral radii.
Floquet growth rate Created 2026-10-06 Updated 2026-10-14
The Floquet growth rate measures the exponential trend of a periodic linear differential equation over many coefficient periods. A Floquet multiplier measures the factor per period ; the corresponding rate per unit time is
where is a Floquet exponent. Taking the real part removes the ambiguity in the complex logarithm.
For the scalar example under periodic solution, and the Floquet growth rate is , independently of . Indeed,
The instantaneous logarithmic derivative keeps oscillating even though its average over complete periods is exactly . Sampling at the same phase in each period removes the modulation altogether: .
Figure 1.
The multiplier gives a factor per period and its logarithm gives a rate per unit time
. Left: sampling at , , gives ; straight lines on the logarithmic scale have slopes per period. Right: the instantaneous logarithmic derivatives oscillate around the constant long-term rates . Details.
For the general finite-dimensional homogeneous linear differential equation , assume that is continuous on the real line and -periodic, with . Normalize its fundamental matrix by and set . The maximal asymptotic exponential rate, using any induced matrix norm, is
Here is the spectral radius, are the Floquet multipliers, and invertibility gives . This concerns growth of the solution operator; it does not say that every initial condition attains the maximum.[ref]
To prove the formula, write with . Periodicity and uniqueness give
Both and have uniformly bounded matrix norms on a period. Consequently differs from by at most fixed multiplicative factors. The spectral radius formula gives , proving the claimed limit without choosing a matrix logarithm.
For a particular nonzero initial condition , decompose into the generalized eigenspaces of over the complex numbers. The rate of is the largest among components that are nonzero. Generic data have a component in the dominant generalized eigenspaces and attain ; data contained in the sum of the subdominant generalized eigenspaces have a smaller rate. For example, with , the maximal rate is , while decays at rate . These invariant subspaces describe initial data at phase zero. Their transported versions can vary with time and satisfy .
A negative Floquet growth rate allows temporary amplification. For the constant non-normal matrix
the initial condition has Euclidean norm , which rises from to about at before eventually decaying. Its exponential rate is still : the Jordan block contributes a polynomial factor, whose logarithm divided by tends to zero. At a unit-modulus Floquet multiplier, such polynomial growth can even be unbounded with zero exponential rate; gives . Thus zero Floquet growth rate alone proves neither boundedness nor a periodic solution.
A strictly diagonally dominant matrix or a real symmetric positive-definite matrix guarantees convergence of the Gauss-Seidel method from every initial vector. These are sufficient conditions.[ref]
For strict diagonal dominance, put
Induct through a sweep. Old coordinates have absolute error at most ; previously updated coordinates have absolute error at most . The component update and the triangle inequality therefore bound the new error by . This proves , a maximum norm contraction.
For a symmetric positive-definite matrix, write . The Householder-John theorem applies to and , because is a positive-definite matrix. Hence the iteration matrix has spectral radius less than one, which gives the convergence criterion for a stationary iteration.
There is also a geometric reason fresh updates help: the Gauss-Seidel method is exact coordinate descent on the convex quadratic function
Holding the other coordinates fixed, minimizing in coordinate gives the corresponding row update. A change lowers by exactly . Each fresh coordinate is therefore the minimizer for the current vector, and a complete sweep lowers the quadratic form error unless every coordinate already solves its row. This explains the method's beauty without implying monotone decrease in every vector norm.
An invertible matrix and nonzero diagonal entries make the update well defined, but do not guarantee convergence. For the original linear system
the Gauss-Seidel method updates and . Starting at zero gives , then . The second-coordinate forward error is , and the iteration matrix has spectral radius . The linear system has a unique solution while this particular stationary iterative method for a linear system diverges.
Heavy-ball rate for a two-eigenvalue diagonal quadratic Created 2026-09-24 Updated 2026-11-05
Let with , choose , and put and . The two-by-two heavy-ball error propagation matrix for a scalar eigenvalue has characteristic polynomial
At , its middle coefficient is , giving a repeated root . At , the polynomial is , whose roots are complex conjugates with modulus . Thus the full propagation matrix has spectral radius exactly .
The repeated root can produce an error term , so the spectral radius is an asymptotic rate and does not assert a stepwise error bound with one fixed constant times . For , the parameters reduce to , and the identity-matrix problem is solved in one update. Values are outside the displayed rate convention.
Jacobi convergence for a three-by-three equicorrelation matrix Created 2026-09-29 Updated 2026-10-03
For a three-by-three matrix with diagonal entries one and every off-diagonal entry , the Jacobi method iteration matrix has eigenvalue on the all-ones vector and eigenvalue with multiplicity two on its orthogonal complement. Its spectral radius is , so Jacobi iteration converges exactly when .
A strictly diagonally dominant matrix guarantees convergence of the Jacobi method for every initial vector.[ref]
Indeed, using the maximum norm , the induced operator norm is the largest absolute row sum. The Jacobi method has and for , so
This gives a cheap sufficient check without computing any eigenvalues. For the Jacobi iteration for a three-variable tridiagonal system, the absolute row sums of are , giving . The true spectral radius gives a sharper eventual rate.
Strict diagonal dominance is sufficient, not necessary: violates it in the first row, but its Jacobi method has eigenvalues and converges. Conversely, being a positive-definite matrix alone is insufficient: the Jacobi convergence for a three-by-three equicorrelation matrix with has positive eigenvalues for , but spectral radius for its iteration matrix. The extra tridiagonal matrix structure in Jacobi convergence for a symmetric positive-definite tridiagonal matrix is therefore substantive.
Joint spectral radius 2026-10-14
The joint spectral radius measures the worst exponential growth under arbitrary products from a finite family of matrices. Submultiplicativity gives its existence and invariance under changes of the chosen norm. Every fixed-length product satisfies , while the maximum norm of all length- products to the power is an upper bound. A repeated product gives the first inequality; grouping an arbitrary long word into blocks proves the second. The spectral radius of each individual matrix does not control growth of all switched products.
For the five-point Dirichlet Laplacian on an square grid, a block-Jacobi splitting that solves each horizontal line exactly has blocks . Its tensor-product sine modes have angles and the displayed iteration matrix eigenvalues. With , its spectral radius is , so it converges on every fixed grid. However the mode has multiplier . It is highly oscillatory between lines and is barely damped. The undamped method is therefore not a uniformly effective smoother for the multigrid method, even though it converges. Convergence and smoothing test different properties of the error spectrum.
Matrix 2-norm of a normal matrix Created 2026-09-29 Updated 2026-11-05
For every finite-dimensional normal matrix , the matrix 2-norm equals the spectral radius:
This follows by unitary diagonalization of a normal matrix and unitary invariance of the matrix 2-norm.
Multi-type Galton-Watson process Created 2026-10-20 Updated 2026-11-05
A multi-type Galton-Watson process assigns each individual one of finitely many types. A type- individual independently produces a random vector of offspring counts, with a distribution depending only on its type. If is a row vector of generation counts and is the expected number of type- children of a type- parent, then . Vector probability generating functions iterate to give generation laws and extinction probabilities. The spectral radius of replaces the scalar offspring mean in irreducible, nonsingular finite-type extinction criteria; reducible systems need componentwise analysis. This models populations with distinct inherited or changing categories.
Next-generation matrix 2026-10-14
The entry is the expected number of newly infected type- individuals produced by a newly infected type- individual while the population is disease-free. In a compartmental linearization, describes new-infection production and transitions and removal. Provided the infection-lifetime subsystem is transient, its integrated occupation matrix is , yielding . The basic reproduction number is its spectral radius. This construction is described in the original next-generation-matrix derivation.
First give the general definitions and radius facts. The spectrum of a bounded operator is , and the point spectrum is . If , the Neumann series inverts , hence also . Thus is contained in the closed disc of radius and is bounded.
The spectral radius is . The spectral radius formula is
For the left shift , an eigenvector satisfies , so . A nonzero such sequence is in exactly when . Since , its spectrum is contained in the closed unit disc. It contains the open unit disc as point spectrum and therefore its closure by closedness of the spectrum. Hence