TOPICS
Search

Quadratic Map


A quadratic map is a quadratic recurrence equation of the form

 x_(n+1)=a_2x_n^2+a_1x_n+a_0.
(1)

While some quadratic maps are solvable in closed form (for example, the three solvable cases of the logistic map), most are not.

A simple example of a quadratic map with a closed-form solution is

 x_n=x_(n-1)^2
(2)

with x_0=2, which has solution x_n=2^(2^n), the first few terms of which for n=0, 1, ... are 2, 4, 16, 256, 65536, 4294967296, ... (OEIS A001146).

Another example is the number of "strongly" binary trees of height <=n, given by

 y_n=y_(n-1)^2+1
(3)

with y_0=1. The first few terms are 2, 5, 26, 677, 458330, 210066388901, 44127887745906175987802, ... (OEIS A003095) This recurrence has the "analytic" solution

 y_n=|_c^(2^n)_|,
(4)

where

c=exp[sum_(j=0)^(infty)2^(-j-1)ln(1+y_j^(-2))]
(5)
=1.502836801...
(6)

(OEIS A077496) and |_x_| is the floor function (Aho and Sloane 1973).

A third example is the closest strict underapproximation of the number 1,

 S_n=sum_(i=1)^n1/(z_i),
(7)

where 1<z_1<...<z_n are integers. The solution is given by the recurrence

 z_n=z_(n-1)^2-z_(n-1)+1,
(8)

with z_1=2. The resulting sequence is known as Sylvester's sequence and has first few terms 2, 3, 7, 43, 1807, 3263443, 10650056950807, ... (OEIS A000058). This has a closed solution as

 z_n=|_d^(2^n)+1/2_|
(9)

where

d=1/2sqrt(6)exp{sum_(j=1)^(infty)2^(-j-1)ln[1+(2z_j-1)^(-2)]}
(10)
=1.2640847353...
(11)

(OEIS A076393; Aho and Sloane 1973, Vardi 1991, Graham et al. 1994).

The well-known recurrence

 x_(n+1)=x_n^2+c
(12)

that is often called "the" quadratic map is not in general solvable in closed form. This is the real version of the complex map defining the Mandelbrot set. Fixed points of this map occur when

 x^((1))=[x^((1))]^2+c
(13)
 (x^((1)))^2-x^((1))+c=0
(14)
 x_+/-^((1))=1/2(1+/-sqrt(1-4c)).
(15)

Period two fixed points occur when

x_(n+2)=x_(n+1)^2+c
(16)
=(x_n^2+c)^2+c
(17)
=x_n^4+2cx_n^2+(c^2+c)
(18)
=x_n.
(19)

Dropping the subscripts and factoring gives

 x^4+2x^2-x+(cx^2+c)=(x^2-x+c)(x^2+x+1+c)=0.
(20)

Solutions therefore occur when

 x_+/-^((2))=1/2(1+/-sqrt(-3-4c)).
(21)

Period three fixed points occur when

 x^6+x^5+(3c+1)x^4+(2c+1)x^3+(c^2+3c+1)x^2 
 +(c+1)^2x+(c^3+2c^2+c+1)=0.
(22)

Another example of a quadratic map with a closed-form solution is the case with

 a_0=((a_1-4)(a_1+2))/(4a_2).
(23)

This has solution

 x_n=(r^(2^n)+r^(-2^n)-1/2a_1)/(a_2),
(24)

where

 r=1/4a_1+1/2x_0a_2+1/4sqrt((a_1+4+2x_0a_2)(a_1-4+2x_0a_2)).
(25)

Similarly, the case with

 a_0=(a_1(a_1-2))/(4a_2)
(26)

has solution

 x_n=((2r)^(2^n)-1/2a_1)/(a_2),
(27)

where

 r=1/4a_1+1/2x_0a_2
(28)

(Little).

The most general second-order two-dimensional map with an elliptic fixed point at the origin has the form

x^'=xcosalpha-ysinalpha+a_(20)x^2+a_(11)xy+a_(02)y^2
(29)
y^'=xsinalpha+ycosalpha+b_(20)x^2+b_(11)xy+b_(02)y^2.
(30)

The map must have a determinant of 1 in order to be area-preserving, reducing the number of independent parameters from seven to three. The map can then be put in a standard form by scaling and rotating to obtain

x^'=xcosalpha-ysinalpha+x^2sinalpha
(31)
y^'=xsinalpha+ycosalpha-x^2cosalpha.
(32)

The inverse map is

x=x^'cosalpha+y^'sinalpha
(33)
y=-x^'sinalpha+y^'cosalpha+(x^'cosalpha+y^'sinalpha)^2.
(34)

The fixed points are given by

 x_i^2sinalpha+2x_icosalpha-x_(i-1)-x_(i+1)=0
(35)

for i=0, ..., n-1.


See also

Bogdanov Map, Hénon Map, Julia Set, Linear Recurrence Equation, Logistic Map, Lozi Map, Mandelbrot Set, Quadratic, Quadratic Equation, Quadratic Formula, Quadratic Recurrence Equation, Recurrence Equation, Strange Attractor, Sylvester's Sequence

Explore with Wolfram|Alpha

References

Aho, A. V. and Sloane, N. J. A. "Some Doubly Exponential Sequences." Fib. Quart. 11, 429-437, 1973.Finch, S. R. "Quadratic Recurrence Constants." §6.10 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 443-448, 2003.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Research problem 4.65 in Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, 1994.Little, M. "Novel Exact Solutions to Special Cases of the Quadratic Map." http://homepage.ntlworld.com/little_mm/quadrams.html.Sloane, N. J. A. Sequences A000058/M0865, A001146/M1297, A003095/M1544, A076393, and A077496 in "The On-Line Encyclopedia of Integer Sequences."Sprott, J. C. "Automatic Generation of Strange Attractors." Comput. & Graphics 17, 325-332, 1993. Reprinted in Chaos and Fractals, A Computer Graphical Journey: Ten Year Compilation of Advanced Research (Ed. C. A. Pickover). Amsterdam, Netherlands: Elsevier, pp. 53-60, 1998.Vardi, I. "Are All Euclid Numbers Squarefree?" and "PowerMod to the Rescue." §5.1 and 5.2 in Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, pp. 82-89, 1991.

Referenced on Wolfram|Alpha

Quadratic Map

Cite this as:

Weisstein, Eric W. "Quadratic Map." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/QuadraticMap.html

Subject classifications