Аннотация: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 well-known different generalizations to a set
of operators of the usual spectral radius of a linear operator. In this paper we develop
a method which—under suitable assumptions—allows 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.