×

Direct and inverse computation of Jacobi matrices of infinite iterated function systems. (English) Zbl 1282.65050

Summary: We introduce a new set of algorithms to compute the Jacobi matrices associated with invariant measures of infinite iterated function systems, composed of one-dimensional, homogeneous affine maps. We demonstrate their utility in the study of theoretical problems, like the conjectured almost periodicity of such Jacobi matrices, the singularity of the measures, and the logarithmic capacity of their support. Since our technique is based on a reversible transformation between pairs of Jacobi matrices, it can also be applied to solve an inverse/approximation problem. The proposed algorithms are tested in significant, highly sensitive cases: They perform in a stable fashion, and can reliably compute Jacobi matrices of large order.

MSC:

65F30 Other matrix algorithms (MSC2010)
47B36 Jacobi (tridiagonal) operators (matrices) and generalizations
42C05 Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis
65D32 Numerical quadrature and cubature formulas
65J22 Numerical solution to inverse problems in abstract spaces

Software:

OPQ
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abenda, S., Turchetti, G.: Inverse problem for fractal sets on the real line via the moment method. Nuovo Cim. B 104, 213-227 (1989) · doi:10.1007/BF02906318
[2] Akhiezer, N.I.: The classical moment problem. Hafner, New York (1965) · Zbl 0135.33803
[3] Alexander, Z., Meiss, J.D., Bradley, E., Garland, J.: Iterated function system models in data analysis: Detection and separation. Chaos 22, 023103 (2012) · Zbl 1331.37117 · doi:10.1063/1.3701728
[4] Barnsley, M.F., Demko, S.G.: Iterated function systems and the global construction of fractals. Proc. R. Soc. London A 399, 243-275 (1985) · Zbl 0588.28002 · doi:10.1098/rspa.1985.0057
[5] Barnsley, M.F., Ervin, V., Hardin, D., Lancaster, J.: Solution of an inverse problem for fractals and other sets. Proc. Natl. Acad. Sci. USA 83, 1975-1977 (1986) · Zbl 0613.28008 · doi:10.1073/pnas.83.7.1975
[6] Barnsley, M.F.: Fractals everywhere. Academic Press, New York (1988) · Zbl 0691.58001
[7] Barnsley, M.F.: Fractal image compression. Notices of the AMS 43(6), 657-662 (1996) · Zbl 1044.94501
[8] Beckermann, B., Bourreau, E.: How to choose modified moments? J. Comput. Appl. Math. 98, 81-98 (1998) · Zbl 0935.65011 · doi:10.1016/S0377-0427(98)00116-2
[9] Bessis, D., Demko, S.: Stable recovery of fractal measures by polynomial sampling. Physica D 47, 429-438 (1991) · Zbl 0717.41014 · doi:10.1016/0167-2789(91)90040-G
[10] Brezinski, C., Redivo, Zaglia M.: Extrapolation Methods: Theory and Practice. North Holland, Amsterdam (1991) · Zbl 0744.65004
[11] Christiansen, J.S.: Szegö’s theorem on Parreau-Widom sets. Adv. Math. 229, 1180-1204 (2012) · Zbl 1235.42021 · doi:10.1016/j.aim.2011.09.012
[12] Christiansen, J.S., Simon, B., Zinchenko, M.: Finite gap Jacobi matrices, III. Beyond the Szegö class. Constr. Approx. 35, 259-272 (2012) · Zbl 1238.42009 · doi:10.1007/s00365-012-9152-4
[13] Clenshaw, C.W.: A note on the summation of Chebyshev series. Math. Tables Aids Comput. 9, 118-120 (1955) · Zbl 0065.05403
[14] Damanik, D., Simon, B.: Jost function and Jost solution for Jacobi matrices. I. Invent. Math. 165, 1-50 (2006) · Zbl 1122.47029 · doi:10.1007/s00222-005-0485-5
[15] de Boor, C., Golub, G.H.: The numerically stable reconstruction of a Jacobi matrix from spectral data. Linear Alg. Appl. 21, 245-260 (1978) · Zbl 0388.15010 · doi:10.1016/0024-3795(78)90086-1
[16] Demko, SG; Peitgen, HO (ed.); Henriques, JM (ed.); Penedo, LF (ed.), Euler Maclauren type expansions for some fractal measures, 101-110 (1991), Amsterdam
[17] Diaconis, P., Shahshahani, M.: Products of random matrices and computer image Generation. Contemporary Math. 50, 173-182 (1986) · doi:10.1090/conm/050/841091
[18] Diekema, E., Koornwinder, T.H.: Differentiation by integration using orthogonal polynomials, a survey. J. Approx. Theory 164, 637-667 (2012) · Zbl 1259.65050 · doi:10.1016/j.jat.2012.01.003
[19] Donovan, G., Geronimo, J., Hardin, D., Massopust, P.: Construction of orthogonal wavelets using fractal interpolation functions. SIAM J. Math. Anal. 27, 1158-1192 (1996) · Zbl 0873.42021 · doi:10.1137/S0036141093256526
[20] Elton, J.H., Yan, Z.: Approximation of measures by Markov processes and homogeneous affine iterated function systems. Constr. Appr. 5, 69-87 (1989) · Zbl 0658.60093 · doi:10.1007/BF01889599
[21] The numerical applicability of the inverse technique in [20], although sought for since its publication and predating the others, has only been preliminarly investigated. J. H. Elton, private communication. · Zbl 1194.81085
[22] Escribano, C., Giraldo, A., Sastre, M.A., Torrano, E.: Computing the Hessenberg matrix associated with a self-similar measure. J. App. Theory 163, 49-64 (2011) · Zbl 1219.28006 · doi:10.1016/j.jat.2010.02.008
[23] Fernau, H.: Infinite iterated function systems. Math. Nach. 170, 79-91 (1994) · Zbl 0817.28006 · doi:10.1002/mana.19941700107
[24] Fischer, H.-J.: On the condition of orthogonal polynomials via modified moments. Z. Anal. Anwendungen 15, 223-244 (1996) · Zbl 0840.42018 · doi:10.4171/ZAA/696
[25] Fischer, H.-J.: Recurrence coefficients of orthogonal polynomials with respect to some self-similar singular distributions. Z. Anal. Anwendungen 14, 141-155 (1995) · Zbl 0820.42010 · doi:10.4171/ZAA/667
[26] Fischer, H.-J.: On generating orthogonal polynomials for discrete measures. Z. Anal. Anwendungen 17, 183-205 (1998) · Zbl 0901.42017 · doi:10.4171/ZAA/815
[27] Forte, B., Vrscay, E.R.: Solving the inverse problem for measures using iterated function systems: a new approach. Adv. Appl. Prob. 27, 800-820 (1995) · Zbl 0829.28005 · doi:10.2307/1428134
[28] Gautschi, W.: On the construction of gaussian quadrature rules from modified moments. Math. Comp. 24, 245-260 (1970) · Zbl 0213.16701
[29] Gautschi, W.; Nevai, P. (ed.), Computational aspects of orthogonal polynomials, 181-216 (1990), Dordrecht · doi:10.1007/978-94-009-0501-6_9
[30] Gautschi, W.: Orthogonal polynomials: computation and approximation. Numerical mathematics and scientific computation. Oxford University Press, New York (2004) · Zbl 1130.42300
[31] Gautschi, W.: Orthogonal polynomials (inMatlab). J. Comput. Appl. Math. 178, 215-234 (2005) · Zbl 1067.65023 · doi:10.1016/j.cam.2004.03.029
[32] Gautschi, W.: On generating orthogonal polynomials. SIAM J. Sci. Comp. 3, 289-317 (1982) · Zbl 0482.65011 · doi:10.1137/0903018
[33] Gautschi, W., Gori, L., Pitolli, F.: Gauss quadrature for refinable weight functions. Appl. Comp. Harm. Anal. 8, 249-257 (2000) · Zbl 0954.65018 · doi:10.1006/acha.1999.0306
[34] Golub, G.H., Welsch, J.H.: Calculation of Gauss quadrature rules. Math. Comp. 23, 221-230 (1969) · Zbl 0179.21901 · doi:10.1090/S0025-5718-69-99647-1
[35] Golub, G.H., Meurant, G.: Matrices, moments and quadrature with applications. Princeton University Press, New Jersey (2010) · Zbl 1217.65056
[36] Gragg, W.B., Harrod, W.J.: The numerically stable reconstruction of Jacobi matrices from spectral data. Numer. Math. 44, 317-335 (1984) · Zbl 0556.65027 · doi:10.1007/BF01405565
[37] Guarneri, I., Mantica, G.: Multifractal energy spectra and their dynamical implications. Phys. Rev. Lett. 73, 3379-3382 (1994) · doi:10.1103/PhysRevLett.73.3379
[38] Handy, C.R., Mantica, G.: Inverse problems in fractal construction: moment method solution. Physica D 43, 17-36 (1990) · Zbl 0704.58033 · doi:10.1016/0167-2789(90)90013-F
[39] Heilman, S.M., Owrutsky, P., Strichartz, R.S.: Orthogonal polynomials with respect to self-similar measures. Experiment. Math. 20, 238-259 (2011) · Zbl 1262.33010 · doi:10.1080/10586458.2011.564966
[40] Hutchinson, J.: Fractals and self-similarity. Indiana J. Math. 30, 713-747 (1981) · Zbl 0598.28011 · doi:10.1512/iumj.1981.30.30055
[41] Janardhan, P., Rosenblum, D., Strichartz, R.S.: Numerical experiments in Fourier asymptotics of Cantor measures and wavelets. Experiment. Math. 1, 249-273 (1992) · Zbl 0788.65129 · doi:10.1080/10586458.1992.10504561
[42] Jorgensen, P.E.T., Kornelson, K.A., Shuman, K.L.: Iterated Function Systems, Moments, and Transformations of Infinite Matrices, Memoirs of the AMS 213 (2011) · Zbl 1243.47033
[43] Kaneko, K.: Inter-intra molecular dynamics as an iterated function system. J. Phys. Soc. Japan 74, 2386-2390 (2005) · doi:10.1143/JPSJ.74.2386
[44] Laurie, D.P.: Computation of Gauss-type quadrature formulas. J. Comput. Appl. Math. 127, 201-217 (2001) · Zbl 0980.65021 · doi:10.1016/S0377-0427(00)00506-9
[45] Laurie, D.: Accurate recovery of recursion coefficients from Gaussian quadrature formulae. J. Comp. Appl. Math. 112, 165-180 (1999) · Zbl 0942.65022 · doi:10.1016/S0377-0427(99)00228-9
[46] Laurie, D., De Villiers, J.: Orthogonal polynomials and Gaussian quadrature for refinable weight functions. Appl. Comp. Harm. Anal. 17, 241-248 (2004) · Zbl 1064.42023 · doi:10.1016/j.acha.2004.06.002
[47] Laurie, D., De Villiers, J.: Orthogonal polynomials for refinable linear functionals. Math. Comp. 75, 1891-1903 (2006) · Zbl 1107.65130 · doi:10.1090/S0025-5718-06-01855-2
[48] O’Leary, D.P., Strakoš, Z., Tichý, P.: On the sensitivity of Gauss-Christoffel quadrature. Numer. Math. 107, 147-174 (2007) · Zbl 1117.41023 · doi:10.1007/s00211-007-0078-x
[49] Mantica, G.: A Stieltjes technique for computing Jacobi matrices associated With singular measures. Constr. Appr. 12, 509-530 (1996) · Zbl 0878.42014 · doi:10.1007/BF02437506
[50] Mantica, G.: Quantum intermittency in almost periodic systems derived from their spectral properties. Physica D 103, 576-589 (1997) · Zbl 1194.81085 · doi:10.1016/S0167-2789(96)00287-4
[51] Mantica, G.: Wave propagation in almost-periodic structures. Physica D 109, 113-127 (1997) · Zbl 0925.58041 · doi:10.1016/S0167-2789(97)00163-2
[52] Mantica, G.: On computing Jacobi matrices associated with recurrent and Möbius iterated functions systems. J. Comp. Appl. Math. 115, 419-431 (2000) · Zbl 0977.65018 · doi:10.1016/S0377-0427(99)00188-0
[53] Mantica, G.: Fourier transforms of orthogonal polynomials of singular continuous spectral measures. ISNM Int. Ser. Numer. Math. 131, 153-163 (1999) · Zbl 0937.65081
[54] Mantica, G., Vaienti, S.: The asymptotic behaviour of the Fourier transform of orthogonal polynomials I: Mellin transform techniques. Ann. Henri Poincaré 8, 265-300 (2007) · Zbl 1215.42032 · doi:10.1007/s00023-006-0308-2
[55] Mantica, G., Guzzetti, D.: The asymptotic behaviour of the Fourier transform of orthogonal polynomials II: iterated function systems and quantum mechanics. Ann. Henri Poincaré 8, 301-336 (2007) · Zbl 1215.42031 · doi:10.1007/s00023-006-0309-1
[56] Mantica, G.: Fourier-Bessel functions of singular continuous measures and their many asymptotics. Electron. Trans. Numer. Anal. (Electronic) 25, 409-430 (2006) · Zbl 1160.42310
[57] Mantica, G.: Polynomial sampling and fractal measures: I.F.S.-Gaussian integration. Num. Alg. 45, 269-281 (2007) · Zbl 1131.65027 · doi:10.1007/s11075-007-9111-5
[58] Mantica, G.: Dynamical systems and numerical analysis: the study of measures generated by uncountable I.F.S. Num. Alg. 55, 321-335 (2010) · Zbl 1200.65037 · doi:10.1007/s11075-010-9398-5
[59] Mantica, G., Sloan, A.: Chaotic optimization and the construction of fractals. Complex Syst. 3, 37-72 (1989) · Zbl 0729.58033
[60] Mauldin, D., Urbansky, M.: Dimensions and measures in infinite iterated function systems. Proc. London Math. Soc. 73(3), 105-154 (1996) · Zbl 0852.28005 · doi:10.1112/plms/s3-73.1.105
[61] Mendivil, F.: A generalization of IFS with probabilities to infinitely many maps. Rocky Mountain J. Math. 28, 1043-1051 (1998) · Zbl 0995.37010 · doi:10.1216/rmjm/1181071754
[62] Moran, P.A.P.: Additive functions of intervals and Hausdorff measure. Proc. Camb. Phil. Soc. 42, 15-23 (1946) · Zbl 0063.04088 · doi:10.1017/S0305004100022684
[63] Moran, M.: Hausdorff measure of infinitely gernerated self-similar sets. Mh. Math. 122, 387-399 (1996) · Zbl 0862.28008 · doi:10.1007/BF01326037
[64] Nuttall, J., Singh, S.R.: Orthogonal polynomials and Padé approximants associated with a system of arcs. J. Approx. Theory 21, 1-42 (1977) · Zbl 0355.30004 · doi:10.1016/0021-9045(77)90117-4
[65] Peherstorfer, F.: On Bernstein-Szego orthogonal polynomials on several intervals, SIAM J. Math. Anal. 21, 461-482 (1990) · Zbl 0688.42020
[66] Peres, Y., Schlag, W., Solomyak, B.: Sixty Years of Bernoulli Convolutions. In: Fractal Geometry and Stochastics II, Progress in Probability 46 pp 39-68. Birkhauser, Basel (2000) · Zbl 0961.42006
[67] Reichel, L.: Construction of polynomials that are orthogonal with respect to a discrete bilinear form. Adv. Comp. Math. 1, 241-258 (1993) · Zbl 0824.65007 · doi:10.1007/BF02071388
[68] Wasserstein metric. L. Rueshendorff (originator), Encyclopedia of Mathematics. http://www.encyclopediaofmath.org/index.php?title=Wasserstein_metric&oldid=15624 · Zbl 0752.65011
[69] Sack, R.A., Donovan, A.F.: An algorithm for Gaussian quadrature given modified moments. Numer. Math. 18, 465-478 (1972) · Zbl 0221.65041 · doi:10.1007/BF01406683
[70] Strichartz, R.S.: Analysis on fractals. Notices AMS 46(10), 1199-1208 (1999) · Zbl 1194.58022
[71] Strichartz, R.S.: Differential equations on fractals: A tutorial. Princeton University Press, New Jersey (2006) · Zbl 1190.35001
[72] Strichartz, R.S.: Self-similar measures and their Fourier transforms I. Indiana U. Math. J. 39, 797-817 (1990) · Zbl 0695.28003 · doi:10.1512/iumj.1990.39.39038
[73] StrichartzR, S.: Self-similar measures and their Fourier transforms II. Trans. Amer. Math. Soc. 336, 335-361 (1993) · Zbl 0765.28007 · doi:10.1090/S0002-9947-1993-1081941-2
[74] Strichartz, R.S.: Self similar measures and their Fourier transforms III. Indiana Univ. Math. J. 42, 367-411 (1993) · Zbl 0790.28003 · doi:10.1512/iumj.1993.42.42018
[75] Stahl, H., Totik, V.: General orthogonal Polypomials. Cambridge University Press, Cambridge (2010) · Zbl 1187.33008
[76] Sweldens, W., Piessens, R.: Quadrature formulae and asymptotic error estimates for wavelet approximation of smooth functions. SIAM J. Numer. Anal. 31, 1240-1264 (1994) · Zbl 0822.65013 · doi:10.1137/0731065
[77] Van Assche, W.: Asymptotics for orthogonal polynomials and three-term recurrences, in Orthogonal Polynomials. Theor. Practice NATO-ASI series C 294, 435-462 (1990)
[78] Widom, H.: Extremal polynomials associated with a system of curves in the complex plane. Adv. Math. 3, 127-232 (1969) · Zbl 0183.07503 · doi:10.1016/0001-8708(69)90005-X
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.