Kreiss matrix theorem

Last updated November 21, 2023

In matrix analysis, Kreiss matrix theorem relates the so-called Kreiss constant of a matrix with the power iterates of this matrix. It was originally introduced by Heinz-Otto Kreiss to analyze the stability of finite difference methods for partial difference equations.^[1]^[2]

Kreiss constant of a matrix

Given a matrix A, the Kreiss constant 𝒦(A) (with respect to the closed unit circle) of A is defined as^[3]

${\mathcal {K}}(\mathbf {A} )=\sup _{|z|>1}(|z|-1)\left\|(z-\mathbf {A} )^{-1}\right\|,$

while the Kreiss constant 𝒦_lhp(A) with respect to the left-half plane is given by^[3]

${\mathcal {K}}_{\textrm {lhp}}(\mathbf {A} )=\sup _{\Re (z)>0}(\Re (z))\left\|(z-\mathbf {A} )^{-1}\right\|.$

Properties

For any matrix A, one has that 𝒦(A) ≥ 1 and 𝒦_lhp(A) ≥ 1. In particular, 𝒦(A) (resp. 𝒦_lhp(A)) are finite only if the matrix A is Schur stable (resp. Hurwitz stable).
Kreiss constant can be interpreted as a measure of normality of a matrix.^[4] In particular, for normal matrices A with spectral radius less than 1, one has that 𝒦(A) = 1. Similarly, for normal matrices A that are Hurwitz stable, 𝒦_lhp(A) = 1.
𝒦(A) and 𝒦_lhp(A) have alternative definitions through the pseudospectrum Λ_ε(A):^[5]
- ${\mathcal {K}}(A)=\sup _{\varepsilon >0}{\frac {\rho _{\varepsilon }(A)-1}{\varepsilon }}$ , where p_ε(A) = max{|λ| : λ ∈ Λ_ε(A)},
- ${\mathcal {K}}_{\textrm {lhp}}(A)=\sup _{\varepsilon >0}{\frac {\alpha _{\varepsilon }(A)}{\varepsilon }}$ , where α_ε(A) = max{Re|λ| : λ ∈ Λ_ε(A)}.
𝒦_lhp(A) can be computed through robust control methods.^[6]

Statement of Kreiss matrix theorem

Let A be a square matrix of order n and e be the Euler's number. The modern and sharp version of Kreiss matrix theorem states that the inequality below is tight^[3]^[7]

${\mathcal {K}}(\mathbf {A} )\leq \sup _{k\geq 0}\left\|\mathbf {A} ^{k}\right\|\leq e\,n\,{\mathcal {K}}(\mathbf {A} ),$

and it follows from the application of Spijker's lemma.^[8]

There also exists an analogous result in terms of the Kreiss constant with respect to the left-half plane and the matrix exponential:^[3]^[9]

${\mathcal {K}}_{\mathrm {lhp} }(\mathbf {A} )\leq \sup _{t\geq 0}\left\|\mathrm {e} ^{t\mathbf {A} }\right\|\leq e\,n\,{\mathcal {K}}_{\mathrm {lhp} }(\mathbf {A} )$

Consequences and applications

The value $\sup _{k\geq 0}\left\|\mathbf {A} ^{k}\right\|$ (respectively, $\sup _{t\geq 0}\left\|\mathrm {e} ^{t\mathbf {A} }\right\|$ ) can be interpreted as the maximum transient growth of the discrete-time system $x_{k+1}=Ax_{k}$ (respectively, continuous-time system ${\dot {x}}=Ax$ ).

Thus, the Kreiss matrix theorem gives both upper and lower bounds on the transient behavior of the system with dynamics given by the matrix A: a large (and finite) Kreiss constant indicates that the system will have an accentuated transient phase before decaying to zero.^[5]^[6]

Related Research Articles

In mathematics, the $L p$ spaces are function spaces defined using a natural generalization of the $p$ -norm for finite-dimensional vector spaces. They are sometimes called Lebesgue spaces, named after Henri Lebesgue, although according to the Bourbaki group they were first introduced by Frigyes Riesz.

In the mathematical field of real analysis, the monotone convergence theorem is any of a number of related theorems proving the convergence of monotonic sequences that are also bounded. Informally, the theorems state that if a sequence is increasing and bounded above by a supremum, then the sequence will converge to the supremum; in the same way, if a sequence is decreasing and is bounded below by an infimum, it will converge to the infimum.

In linear algebra, an $n$ -by- $n$ square matrix $A$ is called invertible, if there exists an $n$ -by- $n$ square matrix $B$ such that

Vapnik–Chervonenkis theory was developed during 1960–1990 by Vladimir Vapnik and Alexey Chervonenkis. The theory is a form of computational learning theory, which attempts to explain the learning process from a statistical point of view.

In mathematics, the spectral radius of a square matrix is the maximum of the absolute values of its eigenvalues. More generally, the spectral radius of a bounded linear operator is the supremum of the absolute values of the elements of its spectrum. The spectral radius is often denoted by $ρ(\cdot)$ .

In mathematics, the Cauchy principal value, named after Augustin Louis Cauchy, is a method for assigning values to certain improper integrals which would otherwise be undefined. In this method, a singularity on an integral interval is avoided by limiting the integral interval to the non singular domain.

In mathematics, the Riesz–Thorin theorem, often referred to as the Riesz–Thorin interpolation theorem or the Riesz–Thorin convexity theorem, is a result about interpolation of operators. It is named after Marcel Riesz and his student G. Olof Thorin.

In mathematics, the Riemann–Lebesgue lemma, named after Bernhard Riemann and Henri Lebesgue, states that the Fourier transform or Laplace transform of an L¹ function vanishes at infinity. It is of importance in harmonic analysis and asymptotic analysis.

In mathematics, the pseudospectrum of an operator is a set containing the spectrum of the operator and the numbers that are "almost" eigenvalues. Knowledge of the pseudospectrum can be particularly useful for understanding non-normal operators and their eigenfunctions.

In mathematics, the Lebesgue differentiation theorem is a theorem of real analysis, which states that for almost every point, the value of an integrable function is the limiting average taken around the point. The theorem is named for Henri Lebesgue.

In the mathematical discipline of graph theory, the expander walk sampling theorem intuitively states that sampling vertices in an expander graph by doing relatively short random walk can simulate sampling the vertices independently from a uniform distribution. The earliest version of this theorem is due to Ajtai, Komlós & Szemerédi (1987), and the more general version is typically attributed to Gillman (1998).

In probability theory and theoretical computer science, McDiarmid's inequality is a concentration inequality which bounds the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables. McDiarmid's inequality applies to functions that satisfy a bounded differences property, meaning that replacing a single argument to the function while leaving all other arguments unchanged cannot cause too large of a change in the value of the function.

In mathematics, uniform integrability is an important concept in real analysis, functional analysis and measure theory, and plays a vital role in the theory of martingales.

In mathematics, the Vitali covering lemma is a combinatorial and geometric result commonly used in measure theory of Euclidean spaces. This lemma is an intermediate step, of independent interest, in the proof of the Vitali covering theorem. The covering theorem is credited to the Italian mathematician Giuseppe Vitali. The theorem states that it is possible to cover, up to a Lebesgue-negligible set, a given subset E of R^d by a disjoint family extracted from a Vitali covering of E.

In mathematics, an eigenvalue perturbation problem is that of finding the eigenvectors and eigenvalues of a system $that is perturbed from one with known eigenvectors and eigenvalues . This is useful for studying how sensitive the original system's eigenvectors and eigenvalues are to changes in the system. This type of analysis was popularized by Lord Rayleigh, in his investigation of harmonic vibrations of a string perturbed by small inhomogeneities.$

In mathematics, Schilder's theorem is a generalization of the Laplace method from integrals on $to functional Wiener integration. The theorem is used in the large deviations theory of stochastic processes. Roughly speaking, out of Schilder's theorem one gets an estimate for the probability that a (scaled-down) sample path of Brownian motion will stray far from the mean path. This statement is made precise using rate functions. Schilder's theorem is generalized by the Freidlin-Wentzell theorem for Itō diffusions.$

In mathematics, the logarithmic norm is a real-valued functional on operators, and is derived from either an inner product, a vector norm, or its induced operator norm. The logarithmic norm was independently introduced by Germund Dahlquist and Sergei Lozinskiĭ in 1958, for square matrices. It has since been extended to nonlinear operators and unbounded operators as well. The logarithmic norm has a wide range of applications, in particular in matrix theory, differential equations and numerical analysis. In the finite-dimensional setting, it is also referred to as the matrix measure or the Lozinskiĭ measure.

In mathematics, the Johnson–Lindenstrauss lemma is a result named after William B. Johnson and Joram Lindenstrauss concerning low-distortion embeddings of points from high-dimensional into low-dimensional Euclidean space. The lemma states that a set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved. The map used for the embedding is at least Lipschitz, and can even be taken to be an orthogonal projection.

In mathematics, particularly linear algebra, the Schur–Horn theorem, named after Issai Schur and Alfred Horn, characterizes the diagonal of a Hermitian matrix with given eigenvalues. It has inspired investigations and substantial generalizations in the setting of symplectic geometry. A few important generalizations are Kostant's convexity theorem, Atiyah–Guillemin–Sternberg convexity theorem, Kirwan convexity theorem.

In mathematics, singular integral operators of convolution type are the singular integral operators that arise on Rⁿ and Tⁿ through convolution by distributions; equivalently they are the singular integral operators that commute with translations. The classical examples in harmonic analysis are the harmonic conjugation operator on the circle, the Hilbert transform on the circle and the real line, the Beurling transform in the complex plane and the Riesz transforms in Euclidean space. The continuity of these operators on L² is evident because the Fourier transform converts them into multiplication operators. Continuity on L^p spaces was first established by Marcel Riesz. The classical techniques include the use of Poisson integrals, interpolation theory and the Hardy–Littlewood maximal function. For more general operators, fundamental new techniques, introduced by Alberto Calderón and Antoni Zygmund in 1952, were developed by a number of authors to give general criteria for continuity on L^p spaces. This article explains the theory for the classical operators and sketches the subsequent general theory.

References

↑ Kreiss, Heinz-Otto (1962). "Über Die Stabilitätsdefinition Für Differenzengleichungen Die Partielle Differentialgleichungen Approximieren". BIT. 2 (3): 153–181. doi:10.1007/bf01957330. ISSN 0006-3835. S2CID 118346536.
↑ Strikwerda, John; Wade, Bruce (1997). "A survey of the Kreiss matrix theorem for power bounded families of matrices and its extensions". Banach Center Publications. 38 (1): 339–360. doi: 10.4064/-38-1-339-360 . ISSN 0137-6934.
1 2 3 4 Raouafi, Samir (2018). "A generalization of the Kreiss Matrix Theorem". Linear Algebra and Its Applications. 549: 86–99. doi: 10.1016/j.laa.2018.03.011 . S2CID 126237400.
↑ Jacob Nathaniel Stroh (2006). Non-normality in scalar delay differential equations (PDF) (Thesis).
1 2 Mitchell, Tim (2020). "Computing the Kreiss Constant of a Matrix". SIAM Journal on Matrix Analysis and Applications. 41 (4): 1944–1975. arXiv: 1907.06537 . doi:10.1137/19m1275127. ISSN 0895-4798. S2CID 196622538.
1 2 Apkarian, Pierre; Noll, Dominikus (2020). "Optimizing the Kreiss Constant". SIAM Journal on Control and Optimization. 58 (6): 3342–3362. arXiv: 1910.12572 . doi:10.1137/19m1296215. ISSN 0363-0129. S2CID 204904802.
↑ Trefethen, Lloyd N.; Embree, Mark (2005), Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, p. 177
↑ Wegert, Elias; Trefethen, Lloyd N. (1994). "From the Buffon Needle Problem to the Kreiss Matrix Theorem". The American Mathematical Monthly. 101 (2): 132. doi:10.2307/2324361. hdl: 1813/7113 . JSTOR 2324361.
↑ Trefethen, Lloyd N.; Embree, Mark (2005), Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, p. 183

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Kreiss, Heinz-Otto (1962). "Über Die Stabilitätsdefinition Für Differenzengleichungen Die Partielle Differentialgleichungen Approximieren". BIT. 2 (3): 153–181. doi:10.1007/bf01957330. ISSN 0006-3835. S2CID 118346536.

[2] Strikwerda, John; Wade, Bruce (1997). "A survey of the Kreiss matrix theorem for power bounded families of matrices and its extensions". Banach Center Publications. 38 (1): 339–360. doi: 10.4064/-38-1-339-360 . ISSN 0137-6934.

[:0-3] 1 2 3 4 Raouafi, Samir (2018). "A generalization of the Kreiss Matrix Theorem". Linear Algebra and Its Applications. 549: 86–99. doi: 10.1016/j.laa.2018.03.011 . S2CID 126237400.

[4] Jacob Nathaniel Stroh (2006). Non-normality in scalar delay differential equations (PDF) (Thesis).

[:1-5] 1 2 Mitchell, Tim (2020). "Computing the Kreiss Constant of a Matrix". SIAM Journal on Matrix Analysis and Applications. 41 (4): 1944–1975. arXiv: 1907.06537 . doi:10.1137/19m1275127. ISSN 0895-4798. S2CID 196622538.

[:2-6] 1 2 Apkarian, Pierre; Noll, Dominikus (2020). "Optimizing the Kreiss Constant". SIAM Journal on Control and Optimization. 58 (6): 3342–3362. arXiv: 1910.12572 . doi:10.1137/19m1296215. ISSN 0363-0129. S2CID 204904802.

[7] Trefethen, Lloyd N.; Embree, Mark (2005), Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, p. 177

[8] Wegert, Elias; Trefethen, Lloyd N. (1994). "From the Buffon Needle Problem to the Kreiss Matrix Theorem". The American Mathematical Monthly. 101 (2): 132. doi:10.2307/2324361. hdl: 1813/7113 . JSTOR 2324361.

[9] Trefethen, Lloyd N.; Embree, Mark (2005), Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators, Princeton University Press, p. 183

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]