Riemannian convexity of functionals

This paper extends the Riemannian convexity concept to action functionals defined by multiple integrals associated to Lagrangian differential forms on first order jet bundles. The main results of this paper are based on the geodesic deformations theory and their impact on functionals in Riemannian setting. They include the basic properties of Riemannian convex functionals, the Riemannian convexity of functionals associated to differential m-forms or to Lagrangians of class C ¹ respectively C ², the generalization to invexity and geometric meaningful convex functionals. Riemannian convexity of functionals is the central ingredient for global optimization. We illustrate the novel features of this theory, as well as its versatility, by introducing new definitions, theorems and algorithms that bear upon the currently active subject of functionals in variational calculus and optimal control. In fact so deep rooted is the convexity notion that nonconvex problems are tackled by devising appropriate convex approximations.     

On the power of standard information for <Emphasis Type="Italic">L</Emphasis><Subscript>∞</Subscript> approximation in the randomized setting

We study approximation of multivariate functions from a general separable reproducing kernel Hilbert space in the randomized setting with the error measured in the L _∞ norm. We consider algorithms that use standard information consisting of function values or general linear information consisting of arbitrary linear functionals. The power of standard or linear information is defined as, roughly speaking, the optimal rate of convergence of algorithms using n function values or linear functionals. We prove under certain assumptions that the power of standard information in the randomized setting is at least equal to the power of linear information in the worst case setting, and that the powers of linear and standard information in the randomized setting differ at most by 1/2. These assumptions are satisfied for spaces with weighted Korobov and Wiener reproducing kernels. For the Wiener case, the parameters in these assumptions are prohibitively large, and therefore we also present less restrictive assumptions and obtain other bounds on the power of standard information. Finally, we study tractability, which means that we want to guarantee that the errors depend at most polynomially on the number of variables and tend to zero polynomially in n ⁻¹ when n function values are used.     

Diffraction tomography: Construction and interpretation of tomographic functionals

On the basis of a linearized model of propagation of seismic wave fields the notion of tomographic functionals is introduced. The physical interpretation of tomographic functionals is that their integral kernels are spatial functions of the influence of variations of the medium parameters in question upon particular measurements of the wave field of the sounding signal. The norm of a tomographic functional is determined by the intensity of the influence function related to the interaction operator. The field is generated by a “source” with the dependence on time determined by the apparatus function of the seismic channel. The analysis of tomographic functionals makes it possible to mathematically design tomographic experiments for monitoring active seismic zones by controlling the parameters of tomographic functionals. The richness in content of a tomographic experiments is determined not only by the norms of tomographic functionals, but also by the region where their supports overlap. Tomographic functionals for the wave and Lamé equations are analyzed. Bibliography:14 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 218, 1994, pp. 176–196. This work was supported by the Russian Foundation of Fundamental Research (Grant 93059961) and by the ISF. Translated by V. N. Troyan.     

Implementation of the recurrence relations of biorthogonality

The aim of this work is the implementation of general algorithms for computing some generalized Padé-type approximants [1]. The quality of these approximants depends on the choice of some functionals. In the classical example of the seriesf(t)=log(1+t)/t we found functionals that give better results than the usual ones.     

Three critical points for perturbed nonsmooth functionals and applications

A recently established three-critical-points theorem of Ricceri relating to continuously Gâteaux differentiable functionals, based on a minimax inequality and on a truncation argument, is extended to Motreanu–Panagiotopoulos functionals. As an application, multiplicity results, also yielding a uniform bound on the norms of solutions, are obtained for variational–hemivariational inequalities depending on two parameters.     

Weight Monte Carlo algorithms for estimation and parametric analysis of the solution to the kinetic coagulation equation

The Smoluchowski equation with linear coagulation coefficients depending on two parameters is considered. We construct weight algorithms for estimating various linear functionals in an ensemble that is governed by the equation under study. The algorithms constructed allow us to estimate the functionals for various parameters, as well as parametric derivatives by using the same set of trajectories. Moreover, we construct the value algorithms and analyze their efficiency for estimating the total monomer concentration, as well as the total monomer and dimer concentration in the ensemble. The computational cost is considerably reduced via the approximate value simulation of the time between interactions combined with the value simulation of the interacting pair number.     

de Boor-Fix dual functionals and algorithms for Tchebycheffian B-spline curves

The de Boor-Fix dual functionals are a potent tool for deriving results about piecewise polynomial B-spline curves. In this paper we extend these functionals to Tchebycheffian B-spline curves and then use them to derive fundamental algorithms that are natural generalizations of algorithms for piecewise polynomial B-spline algorithms. Then, as a further example of the utility of this approach, we introduce “geometrically continuous Tchebycheffian spline curves,” and show that a further generalization works for them as well.     

Identification of distributed systems and the theory of the regularization

The identification problems, i.e., the problems of finding unknown parameters in distributed systems from the observations are very important in modern control theory. The solutions of these identification problems can be obtained by solving the equations of the first kind. However, the solutions are often unstable. In other words, they are not continuously dependent on the data. The regularization or Tihonov's regularization is known as one of the stabilizing algorithms to solve these non well-posed problems. In this paper is studied the regularization method for identification of distributed systems. Several approximation theorems are proved to solve the equations of the first kind. Then, identification problems are reduced to the minimization of quadratic cost functionals by virtue of these theorems. On the other hand, it is known that the statistical methods for identification such as the maximum likelihood lead to the minimization problems of certain quadratic functionals. Comparing these quadratic cost functionals, the relations between the regularization and the statistical methods are discussed. Further, numerical examples are given to show the effectiveness of this method.     

Test closures of sets in Banach spaces generated by linear functionals

Some criteria are proved for an element of a Banach space to belong to the test or Korovkin closure of a given set. The operations of closure in question are determined by linear functionals. The cases of arbitrary linear functionals and of positive functionals are considered. Some sufficient conditions are given for the test closure to coincide with the Korovkin closure. Bibliography: 33 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 247, 1997, pp. 114–145. Translated by S. Yu. Pilyugin.     

Topological grammars for data approximation

A method of topological grammars is proposed for multidimensional data approximation. For data with complex topology we define a principal cubic complex of low dimension and given complexity that gives the best approximation for the dataset. This complex is a generalization of linear and non-linear principal manifolds and includes them as particular cases. The problem of optimal principal complex construction is transformed into a series of minimization problems for quadratic functionals. These quadratic functionals have a physically transparent interpretation in terms of elastic energy. For the energy computation, the whole complex is represented as a system of nodes and springs. Topologically, the principal complex is a product of one-dimensional continuums (represented by graphs), and the grammars describe how these continuums transform during the process of optimal complex construction. This factorization of the whole process onto one-dimensional transformations using minimization of quadratic energy functionals allows us to construct efficient algorithms.     

含多个任意参数的广义变分原理及换元乘子法

弹性力学变分原理的泛函变换可分为三种格式:Ⅰ、放松格式,Ⅱ、增广格式,Ⅲ、等价格式. 根据格式Ⅲ,提出含多个任意参数的广义变分原理及其泛函表示式,其中包括:以位移u为一类泛函变量的多参数广义变分原理;以位移u和应力σ为二类泛函变量的多参数广义变分原理;以位移u和应变ε为二类泛函变量的多参数广义变分原理;以位移u应变ε和应力σ为三类泛函变量的多参数广义变分原理.由这些原理可得出等价泛函一系列新形式,此外,通过参数的合理选择,可构造出一系列有限元模型. 本文还讨论了拉氏乘子法“失效”问题,指出“失效”现象产生的原因,提出乘子法“恢复有效”的作法——换元乘子法.     

Minimum asymptotic error of algorithms for solving ODE

We deal with algorithms for solving systems z′(x) = f(x, z(x)), x ε [0, c], z(0) = η where f has r continuous bounded derivatives in [0, c) × ^s. We consider algorithms whose sole dependence on f is through the values of n linear continuous functionals at f. We show that if these functionals are defined by partial derivatives off then, roughly speaking, the error of an algorithm (for a fixed f) cannot converge to zero faster than n^−r as n → +∞. This minimal error is achieved by the Taylor algorithm. If arbitrary linear continuous functionals are allowed, then the error cannot converge to zero faster than n^−(r+1) as n → +∞. This minimal error is achieved by the Taylor-integral algorithm which uses integrals of f.     

On a quadrature algorithm for the piecewise linear wavelet collocation applied to boundary integral equations

In this paper, we consider a piecewise linear collocation method for the solution of a pseudo‐differential equation of order r=0, ?1 over a closed and smooth boundary manifold. The trial space is the space of all continuous and piecewise linear functions defined over a uniform triangular grid and the collocation points are the grid points. For the wavelet basis in the trial space we choose the three‐point hierarchical basis together with a slight modification near the boundary points of the global patches of parametrization. We choose linear combinations of Dirac delta functionals as wavelet basis in the space of test functionals. For the corresponding wavelet algorithm, we show that the parametrization can be approximated by low‐order piecewise polynomial interpolation and that the integrals in the stiffness matrix can be computed by quadrature, where the quadrature rules are composite rules of simple low‐order quadratures. The whole algorithm for the assembling of the matrix requires no more than O(N [logN]³) arithmetic operations, and the error of the collocation approximation, including the compression, the approximative parametrization, and the quadratures, is less than O(N^?(2?r)/2). Note that, in contrast to well‐known algorithms by Petersdorff, Schwab, and Schneider, only a finite degree of smoothness is required. In contrast to an algorithm of Ehrich and Rathsfeld, no multiplicative splitting of the kernel function is required. Beside the usual mapping properties of the integral operator in low order Sobolev spaces, estimates of Calderón–Zygmund type are the only assumptions on the kernel function. Copyright © 2003 John Wiley & Sons, Ltd.     

Another version of the proximal point algorithm in a Banach space

In this paper, we study some non-traditional schemes of proximal point algorithm for nonsmooth convex functionals in a Banach space. The proximal approximations to their minimal points and/or their minimal values are considered separately for unconstrained and constrained minimization problems on convex closed sets. For the latter we use proximal point algorithms with the metric projection operators and first establish the estimates of the convergence rate with respect to functionals. We also investigate the perturbed projection proximal point algorithms and prove their stability. Some results concerning the classical proximal point method for minimization problems in a Banach space is also presented in this paper.     

A scheme for constructing algorithms for correcting a local perturbation in a finite semimetric

A three-step scheme for constructing algorithms for transforming metric information in data mining is proposed and investigated. The correction problem of a local perturbation of a semimetric on a finite set of objects is considered. In the framework of the proposed scheme, algorithms correcting the changes of the distance between a pair of objects by a given quantity that preserve the metric properties are examined. Sufficient conditions under which the correction of semimetrics using the proposed three-step scheme actually completes in two steps and in some special cases even after the first step are obtained. Semimetric similarity functionals are considered, and the correction algorithms are matched to those functionals.     

Optimality of Euler-integral information for solving a scalar autonomous ode

We study the minimum error of algorithms for solving a scalar autonomous ODE. Information is defined asn evaluations of functionals of the right hand sidef. These functionals can be linear or nonlinear and continuous. Euler-integral information is defined and its optimality is proved in a class of regularf.     

Basic properties of scalarizmg functionals for multiobjective optimization

If a partial ordering or preordering induced by a cone D defines a multi objective optimization problem, then scalarizing functionals for this problem shall posses two basic properties. D – monotonicity and D _e approximation. Several ways of constructing functionals with these properties are discussed in the paper.     

Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss–Seidel algorithms

The randomized extended Kaczmarz and Gauss–Seidel algorithms have attracted much attention because of their ability to treat all types of linear systems (consistent or inconsistent, full rank or rank deficient). In this paper, we present tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss–Seidel algorithms. Numerical experiments are given to illustrate the theoretical results.     

Wavelet decompositions of L 2-functionals

Based on distribution-theoretical definitions of L ₂ and Sobolev spaces given by Werner in [P. Werner (1970). A distribution-theoretical approach to certain Lebesgue and Sobolev spaces. J. Math. Anal. Appl., 29, 19–78.] real interpolation, Besov type spaces and approximation spaces with respect to multiresolution approximations are considered. The key for the investigation are generalized moduli of smoothness introduced by Haf in [H. Haf (1992). On the approximation of functionals in Sobolev spaces by singular integrals. Applicable Analysis, 45, 295–308.]. Those moduli of smoothness allow to connect the concept of L ₂-functionals with more recent developments in multiscale analysis, see e.g. [W. Dahmen (1995). Multiscale analysis, approximation, and interpolation spaces. In: C.K. Chui and L.L. Schumaker (Eds.), Approximation Theory VIII, Vol. 2: Wavelets and Multilevel Approximation, pp. 47–88.]. In particular, we derive wavelet characterizations for the Sobolev spaces introduced by Werner and establish stable wavelet decompositions of L ₂-functionals. Generalizations to more general spaces of functionals and applications are also mentioned.     

An algorithm for the computation of the exponential spline

Summary Procedures for the calculation of the exponential spline (spline under tension) are presented in this paper. The procedureexsplcoeff calculates the second derivatives of the exponential spline. Using the second derivatives the exponential spline can be evaluated in a stable and efficient manner by the procedureexspl. The limiting cases of the exponential spline, the cubic spline and the linear spline are included. A proceduregenerator is proposed, which computes appropriate tension parameters. The performance of the algorithm is discussed for several examples.Editor's Note: In this fascile, prepublication of algorithms from the Approximation series of the Handbook for Automatic Computation is continued. Algorithms are published in ALGOL 60 reference language as approved by the IFIP. Contributions in this series should be styled after the most recently published ones