\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Dynamics of the QR-flow for upper Hessenberg real matrices

Abstract / Introduction Full Text(HTML) Figure(8) / Table(1) Related Papers Cited by
  • We investigate the main phase space properties of the QR-flow when restricted to upper Hessenberg matrices. A complete description of the linear behavior of the equilibrium matrices is given. The main result classifies the possible $ \alpha $- and $ \omega $-limits of the orbits for this system. Furthermore, we characterize the set of initial matrices for which there is convergence towards an equilibrium matrix. Several numerical examples show the different limit behavior of the orbits and illustrate the theory.

    Mathematics Subject Classification: Primary: 65F15, 37N30.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  Left: Typical form of a block $ Y_{j,j} $ of $ \omega(X_0) $. Right: Reordered Jordan normal form used in the proof of Theorem 4.1. In both plots, the blocks labelled by O$ k $, $ k = 1,3,\dots $ (resp. by E$ k $, $ k = 2,4,\dots $), have simple eigenvalues $ \lambda \in \mathrm{Spec}({X_0}) $ with the same real part and odd (resp. even) multiplicity $ \mathrm{mult}({\lambda}) \geq k $. In the right plot, Id refers to the identity matrix of the corresponding dimension

    Figure 2.  We consider $ X_0 $ from Example 4.2. Left: We display $ \log((X(t))_{4,3}) $ as a function of $ t $. The straight lines correspond to $ y = 5-x $ and $ y = 6-x $. Right: We display $ \log((X(t))_{6,5}) $ as a function of $ \log(t) $. The straight lines correspond to $ y = -2x $ and $ y = 1.8-2x $

    Figure 3.  Phase portrait of the system (21) for $ c = d = 2 $. The triangular equilibrium matrices $ A_x $ correspond to the line of fixed points $ y = 2 $. The matrix $ C $ corresponds to the fixed point at $ (1,1) $

    Figure 4.  Left: Evolution of the coefficient $ x_{11} $ of the trajectory of $ X_{0,\epsilon} $ as a function of the integration time $ t $ for $ \epsilon = 10^{-2} $ (green), $ \epsilon = 0 $ (blue) and $ \epsilon = 10^{-2} $ (red). For $ \epsilon = 10^{-2} $, $ x_{11} $ tends to be $ \pi $-periodic, reaching a sequence of maxima close to 8. For $ \epsilon = 0 $, $ x_{11} $ tends to be $ 2\pi $-periodic. For $ \epsilon>0 $, $ x_{11} $ tends to 2. Right: Projection onto the coordinates $ (x_{2,1},x_{2,2},x_{3,2}) $ of the $ \omega $-limit for $ X_{0,10^{-2}} $ (red), $ X_{0,-10^{-2}} $ (green), and the periodic orbit of $ X_{0,0} $ (blue). The $ \pi $-periodic orbit obtained as $ \omega $-limit for $ \epsilon> 0 $ (resp. for $ \epsilon <0 $) are observed in the coordinates plane $ x_{2,1} = 0 $ (resp. $ x_{3,2} = 0 $). For $ \epsilon = 0 $ the $ \omega $-limit is the $ 2\pi $-periodic orbit of $ X_{0,0} $

    Figure 5.  From left to right, we show the orbit of $ X_0 $ in cases (ⅰ) $ \alpha = \pi/2,\ \beta = \pi/4 $, (ⅱ) $ \alpha = \pi/2, \ \beta = \pi/2 $ and (ⅲ) $ \alpha = \pi/4 $, $ \beta \approx 0.361367 $. In the first case the orbit is dens in a 2D torus. In the cases (ⅱ) and (ⅲ) the orbit is a periodic orbit

    Figure 6.  We display the evolution of $ x_{2,1} $ with respect the time integration (top) and the projection onto the $ (x_{1,1},x_{2,1}) $-plane. Left: Orbit of $ X_0^{\mathbb{Q}} $. Right: Orbit of $ X_0^{\mathbb{R}\setminus \mathbb{Q}} $

    Figure 7.  Homoclinic and heteroclinic orbits to $ X_{\pm,\pm} $. We represent some components of the solution $ X(t) $ of the QR-flow starting at $ X_i $, $ 1 \leq i \leq 8 $. In both plots we display the coefficient $ x_{2,3} $ in the $ y $-axis. Left: In the $ x $-axis we display the coefficient $ x_{1,1} $. The four equilibrium matrices are projected onto the points $ (0,1) $ and $ (0,-1) $. The homoclinic orbits appear as ellipses tangent to the origin. Each curve corresponds to two homoclinic or heteroclinic orbits (they are superimposed in this projection). Right: In the $ x $-axis we display the coefficient $ x_{1,2} $. The four equilibrium matrices are at the vertices of the square. The four homoclinic orbits start in one of the vertices, go to the center of the square and return. The four heteroclinic orbits are clearly observed

    Figure 8.  Homoclinic and heteroclinic orbits to $ X_{i,j,k}^{+,+} $ (labelled by $ ijk $ in the top plots). In the bottom plots the points represent projections of more than one equilibrium matrix. Top left: Heteroclinic orbits to these equilibria. The two pieces of orbits which go to the bottom left vertex of the window correspond to the same heteroclinic orbit from $ X_{321}^{+,+} $ to $ X_{123}^{+,+} $. Top right: a scheme of the local homo/heteroclinic structure. Bottom left: The same of top plot, but in a larger window, to see the full heteroclinic orbit from $ X_{321}^{+,+} $ to $ X_{123}^{+,+} $. Bottom right: In the displayed projection each pair of points on the same horizontal coordinate in the top left plot project onto the same point

    Table 1.  Notation for the matrices sets used through the text

    $\mathcal{M}_{n,m}$ Set of $n\times m$ real matrices.
    $I_n$ Identity matrix of dimension $n$
    Real matrices subsets:
    $\mathbf{H}_n$ Set of $n$-dimensional upper Hessenberg matrices
    $\mathbf{H}_n^\star$ Set of $n$-dimensional unreduced upper Hessenberg matrices
    $\mathbf{T}_n$ Set of $n$-dimensional upper triangular matrices
    $\mathbf{D}_n$ Set of $n$-dimensional diagonal matrices
    $\mathbf{O}_n$ Set of $n$-dimensional orthogonal matrices
    $\mathbf{Sym}_n$ Set of $n$-dimensional symmetric matrices
    $\mathbf{Skew}_n$ Set of $n$-dimensional skew-symmetric matrices
    Block real matrices subsets:
    $\mathbf{B \! U \! T}_{n_1,\dots,n_m}^n$ Set of $n$-dimensional block upper triangular matrices with diagonal blocks belonging to $\mathcal{M}_{n_i,n_i}$, $i=1, \dots, m$, $n=n_1 +\dots + n_m$.
    $\mathbf{B \! D}_{n_1,\dots,n_m}^n$ Set of $n$-dimensional block diagonal matrices with diagonal blocks belonging to $\mathcal{M}_{n_i,n_i}$, $i=1, \dots, m$, $n=n_1 +\dots + n_m$.
    $\mathbf{B \! L \! T}_{n_1,\dots,n_m}^n$ Set of $n$-dimensional block lower triangular matrices with diagonal blocks belonging to $\mathcal{M}_{n_i,n_i}$, $i=1, \dots, m$, $n=n_1 +\dots + n_m$.
     | Show Table
    DownLoad: CSV
  • [1] A. Bostan and P. Dumas, Wronskians and linear independence, The American Mathematical Monthly, 117 (2010), 722-727.  doi: 10.4169/000298910x515785.
    [2] M. P. CalvoA. Iserles and A. Zanna, Numerical solution of isospectral flows, Math. Comp., 66 (1997), 1461-1486.  doi: 10.1090/S0025-5718-97-00902-2.
    [3] M. P. CalvoA. Iserles and A. Zanna, Semi-explicit methods for isospectral flows, Advances in Computational Mathematics, 14 (2001), 1-24.  doi: 10.1023/A:1016635812817.
    [4] M. T. Chu, The generalized Toda flow, the QR algorithm and the center manifold theory, SIAM J. Alg. Disc. Meth., 5 (1984), 187-201.  doi: 10.1137/0605020.
    [5] M. T. Chu, Matrix differential equations: A continuous realization process for linear algebra problems, Nonlinear Anal., 18 (1992), 1125-1146.  doi: 10.1016/0362-546X(92)90157-A.
    [6] M. T. Chu, Linear algebra algorithms as dynamical systems, Acta Numer., 17 (2008), 1-86.  doi: 10.1017/S0962492906340019.
    [7] M. T. Chu and L. K. Norris, Isospectral flows and abstract matrix factorizations, SIAM J. Numer. Anal., 25 (1988), 1383-1391.  doi: 10.1137/0725080.
    [8] M. J. Colbrook and A. C. Hansen, On the infinite-dimensional QR algorithm, Numerische Mathematik, 143 (2019), 17-83.  doi: 10.1007/s00211-019-01047-5.
    [9] P. DeiftL. C. LiT. Nanda and C. Tomei, The Toda flow on a generic orbit is integrable, Comm. Pure Appl. Math., 39 (1986), 183-232.  doi: 10.1002/cpa.3160390203.
    [10] P. DeiftL. C. Li and C. Tomei, Matrix factorizations and integrable systems, Comm. Pure Appl. Math., 42 (1989), 443-521.  doi: 10.1002/cpa.3160420405.
    [11] P. DeiftT. Nanda and C. Tomei, Ordinary differential equations and the symmetric eigenvalue problem, SIAM J. Numer. Anal., 20 (1983), 1-22.  doi: 10.1137/0720001.
    [12] P. J. Eberlein and C. P. Huang, Global convergence of the QR algorithm for unitary matrices with some results for normal matrices, SIAM J. Numer. Anal., 12 (1975), 97-104.  doi: 10.1137/0712009.
    [13] H. Flaschka, The Toda lattice. Ⅰ. Existence of integrals, Phys. Rev. B (3), 9 (1974), 1924-1925.  doi: 10.1103/PhysRevB.9.1924.
    [14] J. G. F. Francis, The $QR$ transformation: A unitary analogue to the $LR$ transformation. Ⅰ, Comput. J., 4 (1961/62), 265-271.  doi: 10.1093/comjnl/4.3.265.
    [15] G. H. Golub and C. F. Van Loan, Matrix Computations, Fourth edition, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2013.
    [16] R. T. Gregory and D. L. Karney, A Collection of Matrices for Testing Computational Algorithms, Corrected reprint of the 1969 edition. Robert E. Krieger Publishing Co., Huntington, N.Y., 1978.
    [17] J. K. Hale, Ordinary Differential Equations, Second edition, Robert E. Krieger Publishing Co., Inc., Huntington, N.Y., 1980.
    [18] A. C. Hansen, On the Approximation of Spectra of Linear Hilbert Space Operators, PhD thesis, University of Cambridge, 2008.
    [19] M. Hénon, Integrals of the Toda lattice, Phys. Rev. B (3), 9 (1974), 1921-1923.  doi: 10.1103/PhysRevB.9.1921.
    [20] J. E. Humphreys, Introduction to Lie Algebras and Representation Theory, Graduate Texts in Mathematics, 9. Springer-Verlag, New York-Berlin, 1978.
    [21] À. Jorba and M. R. Zou, A software package for the numerical integration of ODEs by means of high-order Taylor methods, Experiment. Math., 14 (2005), 99-117.  doi: 10.1080/10586458.2005.10128904.
    [22] Y. Kodama and B. A. Shipman, Fifty years of the finite nonperiodic Toda lattice: A geometric and topological viewpoint, J. Phys. A, 51 (2018), 353001, 39 pp. doi: 10.1088/1751-8121/aacecf.
    [23] J. Moser, Finitely many mass points on the line under the influence of an exponential potential - an integrable system, Dynamical Systems, Theory and Applications, Lecture Notes in Phys., Springer, Berlin, 38 (1975), 467-497. 
    [24] T. Nanda, Differential equations and the $QR$ algorithm, SIAM J. Numer. Anal., 22 (1985), 310-321.  doi: 10.1137/0722019.
    [25] B. Parlett, Canonical decomposition of hessenberg matrices, Math. Comp., 21 (1967), 223-227.  doi: 10.1090/S0025-5718-1967-0228519-6.
    [26] B. Parlett, Global convergence of the basic QR algorithm on Hessenberg matrices, Math. Comp., 22 (1968), 803-817.  doi: 10.2307/2004579.
    [27] W. W. Symes, Hamiltonian group actions and integrable systems, Phys. D, 1 (1980), 339-374.  doi: 10.1016/0167-2789(80)90017-2.
    [28] W. W. Symes, The $QR$ algorithm and scattering for the finite nonperiodic Toda lattice, Phys. D, 4 (1981/82), 275-280.  doi: 10.1016/0167-2789(82)90069-0.
    [29] M. Toda, Theory of Nonlinear Lattices, Second edition, Springer Series in Solid-State Sciences, 20. Springer-Verlag, Berlin, 1989. doi: 10.1007/978-3-642-83219-2.
    [30] C. Tomei, The Toda lattice, old and new, J. Geom. Mech., 5 (2013), 511-530.  doi: 10.3934/jgm.2013.5.511.
    [31] M. Webb, Isospectral Algorithms, Toeplitz Matrices and Orthogonal Polynomials, PhD thesis, University of Cambridge, 2017.
    [32] F. Z. Zhang, Matrix Theory. Basic Results and Techniques, Second edition, Universitext. Springer, New York, 2011. doi: 10.1007/978-1-4614-1099-7.
  • 加载中

Figures(8)

Tables(1)

SHARE

Article Metrics

HTML views(3984) PDF downloads(318) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return