Fast Chaotic Artificial Time Integration
Gradient descent methods for large positive definite linear and nonlinear algebraic systems arise when integrating a PDE to steady state and when regularizing inverse problems. However, these methods may converge very slowly when utilizing a constant step
- PDF / 187,750 Bytes
- 9 Pages / 439.37 x 666.142 pts Page_size
- 24 Downloads / 178 Views
Abstract Gradient descent methods for large positive definite linear and nonlinear algebraic systems arise when integrating a PDE to steady state and when regularizing inverse problems. However, these methods may converge very slowly when utilizing a constant step size, or when employing an exact line search at each step, with the iteration count growing proportionally to the condition number. Faster gradient descent methods must occasionally resort to significantly larger step sizes, which in turn yields a strongly nonmonotone decrease pattern in the residual vector norm. In fact, such faster gradient descent methods generate chaotic dynamical systems for the normalized residual vectors. Very little is required to generate chaos here: simply damping steepest descent by a constant factor close to 1 will do. The fastest practical methods of this family in general appear to be the chaotic, two-step ones. Despite their erratic behavior, these methods may also be used as smoothers, or regularization operators. Our results also highlight the need for better theory for these methods. Keywords Gradient descent · Artificial time integration · Dynamical system · Stability · Chaos · Regularization
1 Introduction The famous Courant–Friedrichs–Lewy (CFL) condition really provides a consistency, or compatibility bound, rather than a stability one. It states a bound on the allowed time step in terms of the spatial discretization step for explicit difference methods applied to a hyperbolic partial differential equation (PDE). Its immense popularity relates to the fact that this bound typically coincides with that of the stability condition for simple explicit methods in case of hyperbolic PDEs in one space U. Ascher () · K. van den Doel Department of Computer Science, University of British Columbia, Vancouver, Canada e-mail: [email protected] K. van den Doel e-mail: [email protected] C.A. de Moura, C.S. Kubrusly (eds.), The Courant–Friedrichs–Lewy (CFL) Condition, 147 DOI 10.1007/978-0-8176-8394-8_10, © Springer Science+Business Media New York 2013
148
U. Ascher and K. van den Doel
variable, and it does relate to the essential limitation on time-stepping using explicit methods when applied to time dependent PDEs in general. Thus, practitioners over the years have often come to identify the CFL condition with an essential stability restriction in a wide context. However, occasionally the complete picture is more delicate, and this is indicated already in the following basic example. Example 1 For the simple initial value advection equation ∂u ∂u +a = 0, t ≥ 0, −∞ < x < ∞, ∂t ∂x u(0, x) = u0 (x),
(1a) (1b)
where a is a known constant, the exact solution is u(t, x) = u0 (x − at). For an explicit discretization consider the well-known upwind method (e.g., [2]), where we fix the spatial step size but allow the time step to vary. For a = −1 we have for all j integer vjk+1 = vjk +
αk k vj +1 − vjk , Δx
k = 0, 1, . . . ,
where vjk approximates u(tk , xj ), xj = j Δx and tk = u0 (xj ), ∀j . Next, consider the initial value fu
Data Loading...
