*D. A. Bini, G. Latouche, and B. Meini*

- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198527688
- eISBN:
- 9780191713286
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198527688.003.0009
- Subject:
- Mathematics, Numerical Analysis

Some specialized structures are investigated in this chapter and some of the algorithms in previous chapters are adapted to the specific cases. Markov chains with limited displacement (non-skip-free ...
More

Some specialized structures are investigated in this chapter and some of the algorithms in previous chapters are adapted to the specific cases. Markov chains with limited displacement (non-skip-free processes) are solved by means of functional iterations and cyclic reduction. Markov chains of M/G/1-type are reduced to a special QBD process with infinite blocks and treated with cyclic reduction. Finally, three different algorithms for tree-like stochastic processes, relying on fixed point iterations, Newton’s iteration, and cyclic reduction, are introduced and analysed.Less

Some specialized structures are investigated in this chapter and some of the algorithms in previous chapters are adapted to the specific cases. Markov chains with limited displacement (non-skip-free processes) are solved by means of functional iterations and cyclic reduction. Markov chains of M/G/1-type are reduced to a special QBD process with infinite blocks and treated with cyclic reduction. Finally, three different algorithms for tree-like stochastic processes, relying on fixed point iterations, Newton’s iteration, and cyclic reduction, are introduced and analysed.

*D. A. Bini, G. Latouche, and B. Meini*

- Published in print:
- 2005
- Published Online:
- September 2007
- ISBN:
- 9780198527688
- eISBN:
- 9780191713286
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780198527688.003.0006
- Subject:
- Mathematics, Numerical Analysis

The major iterative algorithms based on functional iteration techniques for solving nonlinear matrix equations are described, analysed, and compared in this chapter. First, the basic concepts on ...
More

The major iterative algorithms based on functional iteration techniques for solving nonlinear matrix equations are described, analysed, and compared in this chapter. First, the basic concepts on fixed point iterations are recalled, then linearly convergent iterations are treated, and finally Newton’s iteration is considered.Less

The major iterative algorithms based on functional iteration techniques for solving nonlinear matrix equations are described, analysed, and compared in this chapter. First, the basic concepts on fixed point iterations are recalled, then linearly convergent iterations are treated, and finally Newton’s iteration is considered.

*S. G. Rajeev*

- Published in print:
- 2013
- Published Online:
- December 2013
- ISBN:
- 9780199670857
- eISBN:
- 9780191775154
- Item type:
- chapter

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199670857.003.0018
- Subject:
- Physics, Atomic, Laser, and Optical Physics

The Kolmogorov-Arnold-Moser (KAM) theorem presents limits to the notion of chaos. This is the deepest result to date on this subject. This chapter starts with a review of Newton's method for solving ...
More

The Kolmogorov-Arnold-Moser (KAM) theorem presents limits to the notion of chaos. This is the deepest result to date on this subject. This chapter starts with a review of Newton's method for solving non-linear equations, itself the iteration of a function. It introduces a notion of distance from the fixed point of Newton's iteration, which is used to prove convergence for good initial conditions. This is then applied to a model problem, that of bringing a matrix to normal form. KAM theory for maps of the circle to itself is developed next. Amazingly, maps close to rational rotations are chaotic while those close to irrational rotations are not. A digression into number theory explores the connection to Diophantine equations. Finally, the chapter solves the Hamilton-Jacobi equation by Newton's iteration, establishing that there are small perturbations of integrable systems that are not chaotic.Less

The Kolmogorov-Arnold-Moser (KAM) theorem presents limits to the notion of chaos. This is the deepest result to date on this subject. This chapter starts with a review of Newton's method for solving non-linear equations, itself the iteration of a function. It introduces a notion of distance from the fixed point of Newton's iteration, which is used to prove convergence for good initial conditions. This is then applied to a model problem, that of bringing a matrix to normal form. KAM theory for maps of the circle to itself is developed next. Amazingly, maps close to rational rotations are chaotic while those close to irrational rotations are not. A digression into number theory explores the connection to Diophantine equations. Finally, the chapter solves the Hamilton-Jacobi equation by Newton's iteration, establishing that there are small perturbations of integrable systems that are not chaotic.

*S. G. Rajeev*

- Published in print:
- 2013
- Published Online:
- December 2013
- ISBN:
- 9780199670857
- eISBN:
- 9780191775154
- Item type:
- book

- Publisher:
- Oxford University Press
- DOI:
- 10.1093/acprof:oso/9780199670857.001.0001
- Subject:
- Physics, Atomic, Laser, and Optical Physics

This book begins with the ancient parts of classical mechanics: the variational principle, Lagrangian and Hamiltonian formalisms, and Poisson brackets. The simple pendulum provides a glimpse of the ...
More

This book begins with the ancient parts of classical mechanics: the variational principle, Lagrangian and Hamiltonian formalisms, and Poisson brackets. The simple pendulum provides a glimpse of the beauty of elliptic curves, which will also appear later in rigid body mechanics. Geodesics in Riemannian geometry are presented as an example of a Hamiltonian system. Conversely, the path of a non-relativistic particle is a geodesic in a metric that depends on the potential. Orbits around a black hole are found. Hamilton-Jacobi theory is discussed, showing a path towards quantum mechanics and a connection to the eikonal of optics. The three body problem is studied in detail, including small orbits around the Lagrange points. The dynamics of a charged particle in a magnetic field, especially a magnetic monopole, is studied in the Hamiltonian formalism. Spin is shown to be a classical phenomenon. Symplectic integrators that allow numerical solutions of mechanical systems are derived. A simplified version of Feigenbaum's theory of period doubling introduces chaos. Following a classification of Mobius transformations, this book studies chaos on the complex plane: Julia sets, Fatou sets, and the Mandelblot are explained. Newton's method for solution of non-linear equations is viewed as a dynamical system, allowing a novel approach to the reduction of matrices to canonical form. This is used as a stepping stone to the KAM theory of maps of a circle to itself, unravelling a connection to the Diophantine problem of number theory. KAM theory of the solution of the Hamilton-Jacobi equation using Newton's iteration concludes the book.Less

This book begins with the ancient parts of classical mechanics: the variational principle, Lagrangian and Hamiltonian formalisms, and Poisson brackets. The simple pendulum provides a glimpse of the beauty of elliptic curves, which will also appear later in rigid body mechanics. Geodesics in Riemannian geometry are presented as an example of a Hamiltonian system. Conversely, the path of a non-relativistic particle is a geodesic in a metric that depends on the potential. Orbits around a black hole are found. Hamilton-Jacobi theory is discussed, showing a path towards quantum mechanics and a connection to the eikonal of optics. The three body problem is studied in detail, including small orbits around the Lagrange points. The dynamics of a charged particle in a magnetic field, especially a magnetic monopole, is studied in the Hamiltonian formalism. Spin is shown to be a classical phenomenon. Symplectic integrators that allow numerical solutions of mechanical systems are derived. A simplified version of Feigenbaum's theory of period doubling introduces chaos. Following a classification of Mobius transformations, this book studies chaos on the complex plane: Julia sets, Fatou sets, and the Mandelblot are explained. Newton's method for solution of non-linear equations is viewed as a dynamical system, allowing a novel approach to the reduction of matrices to canonical form. This is used as a stepping stone to the KAM theory of maps of a circle to itself, unravelling a connection to the Diophantine problem of number theory. KAM theory of the solution of the Hamilton-Jacobi equation using Newton's iteration concludes the book.