Mathematics – Optimization and Control
Scientific paper
2011-06-19
Mathematics
Optimization and Control
55 pages, 10 figures
Scientific paper
We address the problem of the exact computation of two joint spectral characteristics of a family of linear operators, the joint spectral radius (in short JSR) and the lower spectral radius (in short LSR), which are well-known different generalizations to a set of operators of the usual spectral radius of a linear operator. In this article we develop a method which - under suitable assumptions - allows to compute the JSR and the LSR of a finite family of matrices exactly. We remark that so far no algorithm was 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 less than 20. For nonnegative matrices it works faster and finds 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 are able to apply it in order to give answers to several conjectures which have been recently stated in combinatorics, number theory, and the theory of formal languages.
Guglielmi Nicola
Protasov Vladimir
No associations
LandOfFree
Exact computation of joint spectral characteristics of linear operators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Exact computation of joint spectral characteristics of linear operators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exact computation of joint spectral characteristics of linear operators will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-723307