We address the problem of the exact computation of two joint spectralcharacteristics of a family of linear operators, the joint spectral radius (JSR) and thelower spectral radius (LSR), which are wellknown different generalizations to a setof operators of the usual spectral radius of a linear operator. In this paper we developa method which—under suitable assumptions—allows us to compute the JSR andthe LSR of a ﬁnite family of matrices exactly. We remark that so far no algorithm hasbeen available in the literature to compute the LSR exactly.The paper presents necessary theoretical results on extremal norms (and on extremal antinorms) of linear operators, which constitute the basic tools of our procedures, and a detailed description of the corresponding algorithms for the computationof the JSR and LSR (the last one restricted to families sharing an invariant cone). Thealgorithms are easily implemented, and their descriptions are short. If the algorithmsterminate in ﬁnite time, then they construct an extremal norm (in the JSR case) orantinorm (in the LSR case) and ﬁnd their exact values; otherwise, they provide upperand lower bounds that both converge to the exact values. A theoretical criterion fortermination in ﬁnite time is also derived. According to numerical experiments, thealgorithm for the JSR ﬁnds the exact value for the vast majority of matrix familiesin dimensions ≤ 20. For nonnegative matrices it works faster and ﬁnds the JSR indimensions of order 100 within a few iterations; the same is observed for the algorithm computing the LSR. To illustrate the efﬁciency of the new method, we apply itto give answers to several conjectures which have been recently stated in combinatorics, number theory, and formal language theory
We address the problem of the exact computation of two joint spectral characteristics of a family of linear operators, the joint spectral radius (JSR) and the lower spectral radius (LSR), which are wellknown different generalizations to a set of operators of the usual spectral radius of a linear operator. In this paper we develop a method whichunder suitable assumptionsallows us to compute the JSR and the LSR of a finite family of matrices exactly. We remark that so far no algorithm has been available in the literature to compute the LSR exactly. The paper presents necessary theoretical results on extremal norms (and on extremal antinorms) of linear operators, which constitute the basic tools of our procedures, and a detailed description of the corresponding algorithms for the computation of the JSR and LSR (the last one restricted to families sharing an invariant cone). The algorithms are easily implemented, and their descriptions are short. If the algorithms terminate in finite time, then they construct an extremal norm (in the JSR case) or antinorm (in the LSR case) and find their exact values; otherwise, they provide upper and lower bounds that both converge to the exact values. A theoretical criterion for termination in finite time is also derived. According to numerical experiments, the algorithm for the JSR finds the exact value for the vast majority of matrix families in dimensions â¤20. For nonnegative matrices it works faster and finds the JSR in dimensions of order 100 within a few iterations; the same is observed for the algorithm computing the LSR. To illustrate the efficiency of the new method, we apply it to give answers to several conjectures which have been recently stated in combinatorics, number theory, and formal language theory. Â© 2012 SFoCM.
Exact Computation of Joint Spectral Characteristics of Linear Operators
GUGLIELMI, NICOLA;
20130101
Abstract
We address the problem of the exact computation of two joint spectral characteristics of a family of linear operators, the joint spectral radius (JSR) and the lower spectral radius (LSR), which are wellknown different generalizations to a set of operators of the usual spectral radius of a linear operator. In this paper we develop a method whichunder suitable assumptionsallows us to compute the JSR and the LSR of a finite family of matrices exactly. We remark that so far no algorithm has been available in the literature to compute the LSR exactly. The paper presents necessary theoretical results on extremal norms (and on extremal antinorms) of linear operators, which constitute the basic tools of our procedures, and a detailed description of the corresponding algorithms for the computation of the JSR and LSR (the last one restricted to families sharing an invariant cone). The algorithms are easily implemented, and their descriptions are short. If the algorithms terminate in finite time, then they construct an extremal norm (in the JSR case) or antinorm (in the LSR case) and find their exact values; otherwise, they provide upper and lower bounds that both converge to the exact values. A theoretical criterion for termination in finite time is also derived. According to numerical experiments, the algorithm for the JSR finds the exact value for the vast majority of matrix families in dimensions â¤20. For nonnegative matrices it works faster and finds the JSR in dimensions of order 100 within a few iterations; the same is observed for the algorithm computing the LSR. To illustrate the efficiency of the new method, we apply it to give answers to several conjectures which have been recently stated in combinatorics, number theory, and formal language theory. Â© 2012 SFoCM.File  Dimensione  Formato  

2013_ FoundComputMath_13_Guglielmi.pdf
non disponibili
Tipologia:
Versione Editoriale (PDF)
Licenza:
Non pubblico
Dimensione
1.98 MB
Formato
Adobe PDF

1.98 MB  Adobe PDF  Visualizza/Apri Richiedi una copia 
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.