1,721,088 research outputs found
Algorithms for approximate calculation of the minimum of a convex function from its values
No full textThe paper deals with a numerical minimization problem for a convex function defined on a convex n-dimensional domain and continuous (but not necessarily smooth). The values of the function can be calculated at any given point. It is required to find the minimum with desired accuracy. A new algorithm for solving this problem is presented, whose computational complexity as n â â is considerably less than that of similar algorithms known to the author. In fact, the complexity is improved from Cn 7 ln 2(n + 1) [4] to Cn 2 ln(n + 1). ©1996 Plenum Publishing Corporation
Lipschitz stability of operators in Banach spaces
No full textWe consider approximations of an arbitrarymap F: X â Y between Banach spaces X and Y by an affine operator A: X â Y in the Lipschitz metric: the difference F - A has to be Lipschitz continuous with a small constant eopen > 0. In the case Y = â we show that if F can be affinely eopen-approximated on any straight line in X, then it can be globally 2eopen-approximated by an affine operator on X. The constant 2eopen is sharp. Generalizations of this result to arbitrary dual Banach spaces Y are proved, and optimality of the conditions is shown in examples. As a corollary we obtain a solution to the problem stated by Zs. Páles in 2008. The relation of our results to the Ulam-Hyers-Rassias stability of the Cauchy type equations is discussed. © 2013 Pleiades Publishing, Ltd
The euler binary partition function and subdivision schemes
No full textFor an arbitrary set D of nonnegative integers, we consider the Euler binary partition function b(k) which equals the total number of binary expansions of an integer k with "digits" from D. By applying the theory of subdivision schemes and refinement equations, the asymptotic behaviour of b(k) as k → ∞ is characterized. For all finite D, we compute the lower and upper exponents of growth of b(k), find when they coincide, and present a sharp asymptotic formula for b(k) in that case, which is done in terms of the corresponding refinable function. It is shown that b(k) always has a constant exponent of growth on a set of integers of density one. The sets D for which b(k) has a regular power growth are classified in terms of cyclotomic polynomials
Spectral factorization of 2-block toeplitz matrices and refinement equations
No full textPairs of 2-block Toeplitz (N ÃN)-matrices (Ts)ij= p2iâj+sâ1, s = 0, 1, i, j â (1, â¦, N), are considered for arbitrary sequences of complex coefficients p0, â¦, pN. A complete spectral resolution of the matrices T0, T1in the system of their common invariant subspaces is obtained. A criterion of nondegeneracy and of irreducibility of these matrices is derived, and their kernels, root subspaces, and all common invariant subspaces are found explicitly. The results are applied to the study of refinement functional equations and also subdivision and cascade approximation algorithms. In particular, the well-known formula for the exponent of regularity of a refinable function is simplified. A factorization theorem that represents solutions of refinement equations by certain convolutions is obtained, along with a characterization of the manifold of smooth refinable functions. The problem of continuity of solutions of the refinement equations with respect to their coefficients is solved. A criterion of convergence of the corresponding cascade algorithms is obtained, and the rate of convergence is computed. © 2007 American Mathematical Society
Piecewise-smooth refinable functions
No full textUnivariate piecewise-smooth refinable functions (i.e., compactly supported solutions of the equation (formula presented) are classified completely. Characterization of the structure of refinable splines leads to a simple convergence criterion for the subdivision schemes corresponding to such splines, and to explicit computation of the rate of convergence. This makes it possible to prove a factorization theorem about decomposition of any smooth refinable function (not necessarily stable or corresponding to a convergent subdivision scheme) into a convolution of a continuous refinable function and a refinable spline of the corresponding order. These results are applied to a problem of combinatorial number theory (the asymptotics of Eulerâs partition function). The results of the paper generalize several previously known statements about refinement equations and help to solve two open problems. © 2005 American Mathematical Society
Resonance and marginal instability of switching systems
No full textWe analyze the so-called Marginal Instability of linear switching systems, both in continuous and discrete time. This is a phenomenon of unboundedness of trajectories when the Lyapunov exponent is zero. We disprove two recent conjectures of Chitour, Mason and Sigalotti (2012) stating that for generic systems, the resonance is sufficient for marginal instability and for polynomial growth of the trajectories. The concept of resonance originated with the same authors is modified. A characterization of marginal instability under some mild assumptions on the system is provided. These assumptions can be verified algorithmically and are believed to be generic. Finally, we analyze possible types of fastest asymptotic growth of trajectories. An example of a marginally unstable pair of matrices with non-polynomial growth is given
Surface dimension, tiles, and synchronizing automata
No full textWe study the surface regularity of compact sets G ⊆ R n which is equal to the supremum of numbers s ≥ 0 such that the measure of the set G∊ G does not exceed C ∊ s , ∊ > 0, where G∊ denotes the ∊-neighborhood of G. The surface dimension is by definition the difference between n and the surface regularity. Those values provide a natural characterization of regularity for sets of positive measure. We show that for self-affine attractors and tiles those characteristics are explicitly computable. We find them for some popular tiles. This, in particular, gives a refined regularity scale for the multivariate Haar wavelets. The classification of attractors of the highest possible regularity is addressed. The relation between the surface regularity and the Holder regularity of multivariate refinable functions and wavelets is found. Finally, the surface regularity is applied to the theory of synchronizing automata, where it corresponds to the concept of parameter of synchronization
Optimizing the spectral radius
No full textWe suggest a new approach to finding the maximal and the minimal spectral radii of linear operators from a given compact family of operators, which share a common invariant cone (e.g., family of nonnegative matrices). In the case of families with the so-called product structure, this leads to efficient algorithms for optimizing the spectral radius and for finding the joint and lower spectral radii of the family. Applications to the theory of difference equations and to problems of optimizing the spectral radius of graphs are considered. Copyright © 2013 by SIAM
Classification of k-primitive sets of matrices
No full textWe develop a new approach for characterizing k-primitive matrix families. Such families generalize the notion of a primitive matrix. They have been intensively studied in the recent literature due to applications to Markov chains, linear dynamical systems, and graph theory. We prove, under some mild assumptions, that a set of k nonnegative matrices is either k-primitive or there exists a nontrivial partition of the set of basis vectors, on which these matrices act as commuting permutations. This gives a convenient classification of k-primitive families and a polynomial-time algorithm to recognize them. This also extends some results of Perron-Frobenius theory to nonnegative matrix families. Copyright © 2013 by SIAM
- …
