Editing Recurrence relation (section)

==Stability==

===Stability of linear higher-order recurrences===
The linear recurrence of order <math>d</math>,

:<math>a_n = c_1a_{n-1} + c_2a_{n-2}+\cdots+c_da_{n-d},  </math>

has the [[Characteristic polynomial|characteristic equation]]

:<math>\lambda^d - c_1 \lambda^{d-1} - c_2 \lambda^{d-2} - \cdots - c_d \lambda^0 =0. </math>

The recurrence is [[Stability theory|stable]], meaning that the iterates converge asymptotically to a fixed value, if and only if the [[eigenvalues]] (i.e., the roots of the characteristic equation), whether real or complex, are all less than [[unity (mathematics)|unity]] in absolute value.

===Stability of linear first-order matrix recurrences===
{{Main|Matrix difference equation}}

In the first-order matrix difference equation

:<math>[x_t - x^*] = A[x_{t-1}-x^*]</math>

with state vector <math>x</math> and transition matrix <math>A</math>, <math>x</math> converges asymptotically to the steady state vector <math>x^*</math> if and only if all eigenvalues of the transition matrix <math>A</math> (whether real or complex) have an [[absolute value]] which is less than&nbsp;1.

===Stability of nonlinear first-order recurrences===
Consider the nonlinear first-order recurrence

:<math>x_n=f(x_{n-1}).</math>

This recurrence is [[stability theory|locally stable]], meaning that it [[limit of a sequence|converges]] to a fixed point <math>x^*</math> from points sufficiently close to <math>x^*</math>, if the slope of <math>f</math>  in the neighborhood of <math>x^*</math> is smaller than [[unity (mathematics)|unity]] in absolute value:  that is,

: <math>| f' (x^*) | < 1. </math>

A nonlinear recurrence could have multiple fixed points, in which case some fixed points may be locally stable and others locally unstable; for continuous ''f''  two adjacent fixed points cannot both be locally stable.

A nonlinear recurrence relation could also have a cycle of period <math>k</math> for <math>k > 1</math>.  Such a cycle is stable, meaning that it attracts a set of initial conditions of positive measure, if the composite function

:<math>g(x) := f \circ f \circ \cdots \circ f(x)</math>

with <math>f</math> appearing <math>k</math> times is locally stable according to the same criterion:

: <math>| g' (x^*) | < 1,</math>

where <math>x^*</math> is any point on the cycle.

In a [[chaos theory|chaotic]] recurrence relation, the variable <math>x</math> stays in a bounded region but never converges to a fixed point or an attracting cycle; any fixed points or cycles of the equation are unstable.  See also [[logistic map]], [[dyadic transformation]], and [[tent map]].