ISSN 0869-6632 (Print)
ISSN 2542-1905 (Online)

For citation:

Makarenko N. G., Karimova L. M., Muhamedzhanova S. A., Knjazeva I. S. Iterated function system and marcovian prediction of time series. Izvestiya VUZ. Applied Nonlinear Dynamics, 2006, vol. 14, iss. 6, pp. 3-20. DOI: 10.18500/0869-6632-2006-14-6-3-20

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Full text:
(downloads: 99)
Article type: 

Iterated function system and marcovian prediction of time series

Makarenko Nikolaj Grigorevich, Federal state budgetary institution of science Main (Pulkovo) astronomical Observatory of Russian Academy of Sciences
Karimova Lailja Mithatovna, The Republican State Enterprise "Institute of Mathematics of the Ministry of Education and Science of the Republic of Kazakhstan"
Muhamedzhanova Svetlana Adikovna, The Republican State Enterprise "Institute of Mathematics of the Ministry of Education and Science of the Republic of Kazakhstan"
Knjazeva Irina Sergeevna, Federal state budgetary institution of science Main (Pulkovo) astronomical Observatory of Russian Academy of Sciences

This paper demonstrates a tool for prediction time series on a base of iterated function system of the theory of fractals. Iterations result in an attractor or fractal in a space of compacts. The attractor is a support of invariant probabilistic measure or multifractal in a space of Borel measures. An inverse problem consists of finding iterated function system and its probabilities by means of empirical measure. The estimates might be obtained from time series by symbolic dynamics methods. In addition to necessary mathematical material two practical results of predictions of threshold values for financial time series and geomagnetic storms are represented.

Key words: 
  1. Noakes L. The Takens embedding theorem. Inter. J. Bifurcation and Chaos. 1991;1(4):867–872. DOI: 10.1142/S0218127491000634.
  2. Sauer T, Yorke JA, Casdagli M. Embedology. J. Statist. Phys. 1991;65(3-4):579–616. DOI: 10.1007/BF01053745.
  3. Afraimovich VS, Reiman AM. Dimension and entropy in multidimensional systems. Nonlinear waves. Dynamics and evolution. Moscow: Nauka; 1989. P. 238. (In Russian).
  4. Makarenko NG. Reconstruction of dynamic systems according to chaotic time series. In: Nonlinear waves 2004. Nizhny Novgorod: IPF RAS; 2004. P. 398. (In Russian).
  5. Stark J. Delay reconstruction: dynamics versus statistics. Nonlinear dynamics and statistics. A.I. Mees ed. Birkhauser; 2001. P. 81.
  6. Makarenko NG. Embedology and neuroprognosis. Lectures on neuroinformatics. Part 1. Neuroinformatics-2003. Moscow: MIPhI; 2003. P. 86. (In Russian).
  7. Poggio T, Girosi F. A theory of networks for approximation and learning. MIT AI Lab. Techn. Rep. 1989;1140.
  8. Malinetsky GG, Potapov AB. Modern problems of nonlinear dynamics. Moscow: URSS; 2002. 358 p. (In Russian).
  9. Farmer JD, Sidorowich JJ. Predicting chaotic time series. Phys Rev Lett. 1987;59(8):845–848. DOI: 10.1103/PhysRevLett.59.845.
  10. Kantz H, Schreiber Th. Nonlinear time series analysis. Cambridge: Cambridge Univ.Press; 2004. 369 p.
  11. McSharry PE. Innovations in consistent nonlinear deterministic prediction. D.Phil. Thesis. Oxford: University of Oxford; 1999.
  12. Nakamura T, Kilminster D, Judd K, Mees A. A comparative study of model selection methods for nonlinear time series. Int. J. of Bifur. and Chaos. 2004;14(3):1129–1146. DOI: 10.1142/S0218127404009752.
  13. Mukhin DN, Feigin AM, Loscutov EM, Molkov YI. Modified Bayesian approach for the reconstruction of dynamical systems from time series. Phys.Rev.E. 2006;73(3):036211. DOI: 10.1103/PHYSREVE.73.036211.
  14. Kantz H, Ragwitz M. Phase space reconstruction and nonlinear predictions for stationary and nonstationary Markovian processes. Intern. Journal of Bifurcation and Chaos. 2004;14(6):1935–1945. DOI: 10.1142/S0218127404010357.
  15. Froyland G. Extracting dynamical behaviour via Markov models. Nonlinear dynamics and statistics. AI. Mees ed. Birkhauser; 2001. P. 283.
  16. Froyland G. Markov modelling for random dynamical systems. 1998. Available from:
  17. Daw CS, Finney CEA, Tracy ER. A review of symbolic analysis of experimental data. Rev. of Scientific Instruments. 2003;74(2):916–930. DOI: 10.1063/1.1531823.
  18. Wanliss JA, Ahn VV, Yu ZG, Watson S. Multifractal modeling of magnetic storms via symbolic dynamics analysis. J. Geopys. Res. 2005;110(A8):AO814. DOI: 10.1029/2004JA010996.
  19. Anh Vo, Lau Ka-Sing, Yu Zu-Gao. Multifractal characterization of complete genomes. J.Phys. A: Math.Gen. 2001;34(36):7127–7139.
  20. Tino P. Multifractal properties of Hao’s geometric representations of sequences. Physica A. 2002;304(3–4):480–494.
  21. Barnsley M. Fractals everywhere. New York: Academic Press; 1988. 531 p.
  22. Falconer K. Fractal geometry. Mathematical Foundations and Applications. Wiley; 2003. 337 p.
  23. Barnsley MF, Demko S. Iterated function systems and the global construction of fractals. Proc. Roy. Soc. London A. 1985;399:243–275. DOI: 10.1098/rspa.1985.0057.
  24. Hutchinson JE. Fractals and self-similarity. Indiana Univ. Math. 1981;30:713–747.
  25. Diaconis P. Iterated random function. SIAM Review. 1999;41(1):45–76.
  26. Vrscay ER. From fractal image compression to fractal-based methods in mathematics. Fractals in Multimedia. Ed. by MF. Barnsley, D. Saupe and ER. Vrscay. New York: Springer-Verlag; 2002.
  27. Jeffrey HJ. Chaos game representation of gene structure. Nucleic Acids Research. 1990;18(8):2163–2170. DOI: 10.1093/nar/18.8.2163.
  28. Tino P. Spatial representation of symbolic sequences through iterative function systems. IEEE Transactions on Systems, Man, and Cybernetics: Part A: Systems and Humans. 1999;29(4):386–393. DOI: 10.1109/3468.769757.
  29. Tino P, Dorffner G. Predicting the future of discrete sequences from fractal representations of the past. Machine Learning. 2001;45(2):187–217. DOI: 10.1023/A:1010972803901.
  30. Barnsley MF, Ervin V, Hardin D, Lancaster J. Solution of an inverse problem for fractals and other sets. Proc Natl Acad Sci U S A. 1986;83(7):1975–1977. DOI: 10.1073/pnas.83.7.1975.
  31. Iacus StM, Torre DL. Approximating distribution functions by iterated function systems. Departemental Working Papers 2002–03, Department of Economics University of Milan Italy. Available from:
  32. Hart JC. Computer display of linear fractal surfaces. Doctor Thesis. University of Illinois at Chicago, 1991. Available from:
  33. Makarenko NG. Fractals, multifractal measures and attaractors. In: Nonlinear waves 2002. Nizhny Novgorod: IPF RAS; 2003. P. 381. (In Russian).
  34. Makarenko NG. Fractals, attractors, neural networks and all that. Lectures on neuroinformatics. V.2 . Neuroinformatics-2002. Moscow: MIPhI; 2002. P. 121. (In Russian).
  35. Falconer K. Techniques in fractal geometry. Wiley & Sons; 1997. 256 p.
  36. Hutchinson JE. Measure Theory. 1995. Available from:
  37. Rubner Y, Tomasi C, Guibas LJ. The Earth mover’s distance as a metric for image retrieval. International Journal of Computer Vision. 2000;40:99–121. DOI: 10.1023/A:1026543900054.
  38. Kaijser T. Computing the Kantorovich distance for images. J. Mathematical Imaging and Vision. 1998;9(2):173–191. DOI: 10.1023/A:1008389726910.
  39. Lemeshko BYu. Optimization methods. A conception of lectures. Novosibirsk: NSTU; 2009. 154 p. (In Russian).
  40. Stark J. A neural network to compute the Hutchinson metric in fractal image processing. IEEE Trans Neural Netw. 1991;2(1):156–158. DOI: 10.1109/72.80303.
  41. Wadstromer N. Coding of fractal binary images with contractive set mappings composed of affine transformations. PhD Theses. Linköping: Linkopings univer.; 2001. 146 p.
  42. Ling H, Okada K. EMD-L1: An efficient and robust algorithm for comparing histogram-based descriptors. European Conference on Computer Vision. 2006. Available from: hbling/main.htm.
  43. Forte B, Vrscay E. R. Solving the inverse problem for function/image approximations using iterated function systems. I.Theoretical basis; II. Algorithm and computations. Fractals. 1994;2,3:325–346.
  44. Handy CR, Mantica G. Inverse problems in fractal construction: moment method solution. Phys. D. 1990;43(1):17–36.
  45. Abendat S, Demko S, Turchetti G. Local moments and inverse problem for fractal measures. Inverse Problems. 1992;8:739–750.
  46. Lutton E, Levy-Vehel J, Cretin G, Glevarec Ph, Roll C. Mixed IFS: Resolution of the inverse problem using genetic programming. Complex Systems. 1995;9:375. DOI: 10.1007/3-540-61108-8_42.
  47. Zabolotnaya NA. Indices of geomagnetic activity. Moscow: Gidrometizdat; 1977. 39 p. (In Russian).
  48. Yanovsky BM. Earth magnetism. Leningrad: Leningrad State University; 1978. 592 p. (In Russian).
  49. Pudovkin MI, Raspopov OM, Kleimenova NT. Perturbations of the Earth's electromagnetic field. Leningrad: Leningrad State University; 1976. 247 p. (In Russian).
  50. Watanabe Sh, Sagawa E, Ohtaka K, Shimazu H. Prediction of the Dst index from solar wind parameters by a neural network method. Earth Planets Space. 2002;54(12):1263–1275. DOI: 10.1186/BF03352454.
  51. Stepanova M, Antonova E, Troshichev O. Prediction of Dst variations from Polar Cap indices using time-delay neural network. J.Atmosph. and Solar-Terrestrial Phys. 2005;67(17-18):1658–1664. DOI: 10.1016/J.JASTP.2005.02.027.
  52. Strivastava N. A logistic regression model for predicting the occurrence of intense geomagnetic storms. Ann.Geophys. 2005;23(9):2969–2974. DOI: 10.5194/angeo-23-2969-2005.
  53. Ahn VV, Yu ZG, Wanliss JA, Watson SM. Prediction of magnetic storm events using the Dst index. Nonlinear Processes in Geophysics. 2005;12(6):799–806. DOI: 10.5194/NPG-12-799-2005.
  54. Levy Vehel J. Numerical computation of the large deviation multifractal spectrum. Available from:
  55. Forte B, Vrscay ER. Theory of generalized fractal transforms. Fractal Image Encoding and Analysis. Edited by Y. Fisher. Heidelberg: Springer Verlag; 1998. Available from:
Short text (in English):
(downloads: 53)