Least Squares Shadowing sensitivity analysis of chaotic limit cycle oscillations

Qiqi Wang; Rui Hu; Patrick Blonigan

Source-linked AI summary

Least Squares Shadowing sensitivity analysis of chaotic limit cycle oscillations

Qiqi Wang, Rui Hu, Patrick Blonigan

arXiv:1204.0159v7Apr 1, 2012physics.comp-phnlin.CDphysics.flu-dyn

TL;DR

Conventional sensitivity methods can produce excessively large derivatives for long-time averages in chaotic systems because the underlying initial-value problems are ill-conditioned. This paper replaces that problem with the well-conditioned Least Squares Shadowing problem, linearizes it, and demonstrates derivatives that are more accurate than finite differences across periodic, chaotic, and mixed regimes. The method requires solving a larger sparse system or time boundary-value problem, increasing computational cost relative to an initial-value solve.

Problem
Conventional sensitivity methods fail for long-time averaged outputs in chaos because chaotic initial-value problems are ill-conditioned and can yield derivatives that are too large for practical use.
Method
The paper replaces the initial-value problem with the well-conditioned Least Squares Shadowing problem, linearizes it, and solves the resulting system numerically.
Results
The method computes more accurate derivatives than finite differences at equal trajectory lengths for the Van der Pol oscillator and across complex Lorenz regimes, including non-hyperbolic behavior.
Takeaways & Limitations
The demonstrations indicate that Least Squares Shadowing can compute useful long-time-average derivatives across fixed-point, limit-cycle, quasi-hyperbolic, and non-hyperbolic regimes.
Takeaways & Limitations
Least Squares Shadowing requires a sparse matrix solve or time boundary-value problem roughly twice as large as a linearized initial-value problem, increasing the cost of derivative computation.

Abstract

from arXiv · show

The adjoint method, among other sensitivity analysis methods, can fail in chaotic dynamical systems. The result from these methods can be too large, often by orders of magnitude, when the result is the derivative of a long time averaged quantity. This failure is known to be caused by ill-conditioned initial value problems. This paper overcomes this failure by replacing the initial value problem with the well-conditioned "least squares shadowing (LSS) problem". The LSS problem is then linearized in our sensitivity analysis algorithm, which computes a derivative that converges to the derivative of the infinitely long time average. We demonstrate our algorithm in several dynamical systems exhibiting both periodic and chaotic oscillations.

1. Introduction

Sensitivity analysis supports many simulation tasks, but conventional tangent and adjoint methods fail for chaotic systems with long-time averaged outputs. The paper introduces Least Squares Shadowing to compute useful derivatives in such settings.

Sensitivity analysis computes derivatives of simulation outputs with respect to inputs for engineering, control, inverse problems, error estimation, data assimilation, and uncertainty quantification.
Conventional tangent and adjoint methods fail for chaotic systems when outputs are long-time averages, producing derivatives that can grow exponentially with simulation time.The failure is attributed to the butterfly effect and sensitivity of chaotic initial-value problems.
Existing alternatives include ensemble adjoints and fluctuation-dissipation approaches, but they require impractically many trajectories or rely on restrictive distribution and noise assumptions.
The paper presents Least Squares Shadowing, which linearizes a constrained least-squares problem and computes derivatives of long-time averaged outputs in chaos.

2. Conventional method for sensitivity analysis

Conventional sensitivity analysis differentiates an initial-value simulation with respect to its inputs. Tangent and adjoint formulations use the resulting linearized dynamics to compute output derivatives.

An initial-value problem maps an input s and initial condition to a time-dependent solution uiv(t; s).
An output J depends on the solution and input, while substituting uiv(t; s) makes it a function of time and s.
Time-averaging J over the simulation interval produces an output that depends only on s, whose derivative can be computed by the tangent method.
The tangent method solves a linearized governing equation with a linearized initial condition to determine how changes in s alter the initial-value solution.
The adjoint transformation computes one objective derivative with respect to many inputs simultaneously, supporting optimal control, inverse problems, and data assimilation.

3. Failure of the conventional method for time averaged outputs in chaos

For chaotic systems, conventional sensitivity analysis becomes unreliable for long-time averages because the initial-value problem is exponentially ill-conditioned. The resulting derivatives can be far larger than the practical slope of the averaged-output function.

The conventional method fails for chaotic simulations when the output is averaged over a long time T.
A positive maximal Lyapunov exponent makes the linearized initial-value solution grow at rate e^λt, producing exponentially large sensitivities.
In the Lorenz system, the heat-convection output is expected to increase with the Rayleigh-number input at a ratio of about 1, but conventional derivatives become orders of magnitude larger.
A derivative as large as 10^50 is useful only over intervals smaller than 10^-50, making it unusable for approximating slopes over practical intervals.
The failure is not limited to the Lorenz system; it also occurs in other chaotic systems, including chaotic fluid flows.
When derivatives fluctuate rapidly between extreme positive and negative values, their magnitude can greatly exceed the slope over a practical input interval.
A chaotic initial-value problem has condition number on the order of e^λT, so even moderately long simulations can make sensitivity analysis fail.

4. Sensitivity analysis via Least Squares Shadowing

Least Squares Shadowing replaces chaotic initial value problems with a constrained, better-conditioned trajectory-matching problem. Its linearized formulation yields derivatives of long-time averages that converge to the derivative of the infinite-time average.

LSS formulation: Under ergodicity, infinite-time averages are independent of the initial condition, allowing the initial condition to be replaced by a conditioning criterion.The method assumes interest is limited to infinite-time averaged outputs and functions thereof.
LSS formulation: The LSS problem selects a governing-equation trajectory and monotone time transformation that remain close to a reference trajectory under a weighted distance.The reference trajectory solves the governing equation at a different input value, and the weighting balances the two terms in the metric.
Well-conditioning: Replacing the chaotic initial value problem with LSS produces a well-conditioned solution that is less sensitive to parameter perturbations and has useful long-time-average derivatives.The shadowing lemma provides the theoretical basis under uniform hyperbolicity by placing a true trajectory near an approximate trajectory.
Well-conditioning: The initial value problem becomes increasingly sensitive as trajectory length grows, whereas LSS remains well-conditioned and its condition number stays relatively constant.Figure 2 contrasts time-dependent outputs from initial value and LSS problems; Figure 3 compares their condition numbers.
Derivative convergence: As trajectory length T tends to infinity, the LSS slope converges to the slope of the infinite-time average, and the LSS derivative converges to its derivative.The convergence follows from uniform convergence of the finite-interval slope to the derivative as the parameter interval vanishes.
Derivative computation: The sensitivity algorithm linearizes the nonlinear LSS problem and the time-averaged output to compute the desired derivative from the linearized solution.The linearized variables arise by perturbing the input and discarding O(δs^2) terms.

5. Numerical solution of the Least Squares Shadowing (LSS) problem

The linearized LSS problem is discretized into a constrained least-squares problem whose KKT system yields the sensitivity solution. The resulting system can be solved directly or iteratively, after which the desired derivative is computed.

Discretization: The linearized LSS problem is discretized over uniform time steps using trapezoidal approximations for the state and sensitivity derivatives.Uniform steps simplify notation, while the trapezoidal rule is single-step and second-order accurate.
KKT formulation: The discretized constrained least-squares problem produces a KKT system whose solution gives the LSS variables v_i and η_i.The continuous formulation can also be converted to optimality equations through variational calculus.
Linear-system solution: The KKT system can be reduced through a Schur complement to a symmetric-positive-definite block-tridiagonal system.Its block size is the dynamical-system dimension n.
Linear-system solution: A direct banded solver or sparse QR factorization solves the reduced system in O(m n^3) floating-point operations, while iterative methods are available for large n.Here m is the number of time steps and n is the system dimension.
Sensitivity computation: After solving for w, the method computes v_i and η_i and then evaluates the desired derivative from the resulting discretized sensitivity expression.The algorithm first forms the required matrices, solves the reduced system, recovers the sensitivity variables, and computes the derivative.
Adjoint formulation: The adjoint formulation uses the same system matrix with a different right-hand side, and its derivative agrees with the Section 5.4 computation up to round-off error.The paper’s examples use the Section 5.4 algorithm.

6. Application to the Van der Pol oscillator

The method is applied to sensitivity of a time-averaged output of the periodic Van der Pol oscillator with respect to β. Against finite differences, LSS is more accurate for trajectories of the same length.

Setup: The Van der Pol experiment computes sensitivity to the parameter β using the LSS method.Random initial conditions are evolved toward the attractor before trajectories are used for sensitivity computation.
Comparison: 20 repeated estimates on trajectories of length 50 quantify the spread caused by insufficient trajectory length, while length-5000 trajectories provide more accurate reference estimates.This repetition is performed for both finite differences and LSS.
Comparison: Figure 4 compares LSS sensitivity estimates with finite-difference estimates across β values.The comparison uses repeated randomly initialized trajectories.
Result: LSS is more accurate than finite difference for this problem when both use the same trajectory length.The conclusion is based on the spread and comparison of computed derivatives.

7. Application to the Lorenz system

The LSS method is evaluated on the Lorenz system across parameter ρ values spanning fixed-point, chaotic, quasi-attractor, and periodic regimes. It produces consistent gradients on short random trajectories and remains more accurate than finite differences despite non-hyperbolic behavior.

Setup: The Lorenz experiment analyzes sensitivity of the time-averaged mean z value to the parameter ρ.The system is integrated toward its attractor before 5000 states are used for the computation.
Dynamical regimes: The parameter sweep covers fixed-point, strange-attractor, non-hyperbolic quasi-attractor, and periodic regimes with period doubling.These regimes occur over distinct ρ intervals described in the experiment.
Results: LSS computes accurate and consistent gradients on randomly chosen short trajectories on the attractor across the Lorenz transition region.The finite-difference estimate exhibits a dip near ρ = 22.5 associated with the fixed-point-to-strange-attractor bifurcation range 24.0 ≤ ρ ≤ 24.74.
Convergence: The LSS gradient error is empirically O(T^-1/2), consistent with a theoretical discrete-time result.This convergence behavior is shown in Figure 6.
Results: For ρ > 31, LSS remains more accurate than finite difference on equal-length trajectories despite non-hyperbolic quasi-attractor behavior.The result also covers the system’s subsequent transition to periodic oscillations and period doublings.

8. Application to an aero-elastic limit cycle oscillator

The method is applied to an aero-elastic oscillator whose dynamics shift among asymmetric periodic, chaotic, symmetric periodic, and other oscillatory regimes as Q varies. LSS estimates sensitivity of the pitch-oscillation magnitude using the L8 norm of α.

Setup: The aero-elastic model analyzes sensitivity to reduced dynamic pressure Q.The state contains plunge and pitch variables and their time derivatives.
Dynamical regimes: As Q increases, the model undergoes period doubling into chaos beyond about Q = 11, returns to symmetric periodic oscillation near Q = 12.5, and shows further asymmetric windows beyond about Q = 13.25.A further transition occurs at about Q = 13.9.
Objective: The objective is the L8 norm of the pitch angle α, chosen to represent the magnitude of pitching oscillation.The L8 norm has a similar trend to the L∞ norm.
Procedure: LSS sensitivity is computed from trajectories initialized at t = −300 and evolved to t = 0 before a length-300 trajectory is analyzed.Random initial conditions are used for each Q.
Comparison: Figure 8 compares LSS estimates with finite-difference estimates across Q, using 20 trajectory pairs of length 300 and longer trajectories of length 30000 for the reference curve.The figure also includes a bifurcation diagram and phase plots at Q = 8, 12, and 16.

9. Conclusion

The Least Squares Shadowing method replaces ill-conditioned initial-value linearizations with a well-conditioned formulation for useful derivatives of long time averaged quantities. Demonstrations span periodic, chaotic, and mixed nonlinear dynamics, while computational cost remains close to that of an initial-value solution in favorable settings.

Method: Least Squares Shadowing computes useful derivatives of long time averaged quantities by linearizing a well-conditioned least squares shadowing problem.Traditional tangent and adjoint methods linearize an ill-conditioned initial value problem and can produce derivatives too large for control, optimization, and inference.
Applications: The method was demonstrated on the periodic van der Pol oscillator, chaotic Lorenz attractor, and mixed periodic-chaotic aero-elastic oscillation model.These applications cover fixed points, limit cycles, and quasi-hyperbolic and non-hyperbolic strange attractors.
Computational cost: The method requires solving either a sparse matrix system or a boundary value problem in time.The resulting problem is about twice as large as a linearized initial value problem in the relevant discrete or continuous formulation.
Computational cost: For low-dimensional systems, direct sparse solvers can make derivative computation cost only a few times more than computing the output itself.For high-dimensional systems, the paper proposes iterative methods because the system is well-conditioned and only twice as large as an initial value problem.

Appendix A. Derivation of Equations (13) and (15)

The appendix derives the linearized least squares shadowing equations by perturbing the parameter while retaining a reference trajectory and translating the original objective and constraint.

Reference solution: For a reference trajectory satisfying the original problem, the least squares shadowing solution at the reference parameter is the trajectory itself with identity time transformation.At a perturbed parameter, well-conditioning implies the corresponding solution for the same reference trajectory changes only slightly.
Objective: The derivation translates the original least squares shadowing objective into the objective used by the linearized problem.The appendix describes this translation for the perturbed solution and parameter.
Constraint: Linearizing the governing constraint discards second-order parameter-perturbation terms and yields the constraint of the linearized least squares shadowing problem.The appendix explicitly notes that O(δs^2) terms are ignored in this step.