An optimal order multigrid method for biharmonic,C 1 finite element equations

Summary In this paper, we study a special multigrid method for solving large linear systems which arise from discretizing biharmonic problems by the Hsieh-Clough-Tocher,C ¹ macro finite elements or several otherC ¹ finite elements. Since the multipleC ¹ finite element spaces considered are not nested, the nodal interpolation operator is used to transfer functions between consecutive levels in the multigrid method. This method converges with the optimal computational order.     

Basic Theory in Construction of Boolean Functions with Maximum Possible Annihilator Immunity

So far there is no systematic attempt to construct Boolean functions with maximum annihilator immunity. In this paper we present a construction keeping in mind the basic theory of annihilator immunity. This construction provides functions with the maximum possible annihilator immunity and the weight, nonlinearity and algebraic degree of the functions can be properly calculated under certain cases. The basic construction is that of symmetric Boolean functions and applying linear transformation on the input variables of these functions, one can get a large class of non-symmetric functions too. Moreover, we also study several other modifications on the basic symmetric functions to identify interesting non-symmetric functions with maximum annihilator immunity. In the process we also present an algorithm to compute the Walsh spectra of a symmetric Boolean function with O(n²) time and O(n) space complexity. We use the term “Annihilator Immunity” instead of “Algebraic Immunity” referred in the recent papers [3–5, 9, 18, 19]. Please see Remark 1 for the details of this notational change     

Best Approximation with Walsh Atoms

We consider the approximation in L ² R of a given function using finite linear combinations of Walsh atoms, which are Walsh functions localized to dyadic intervals, also called Haar—Walsh wavelet packets. It is shown that up to a constant factor, a linear combination of K atoms can be represented to relative error ɛ by a linear combination of orthogonal atoms. In finite dimension N, best approximation with K orthogonal atoms can be realized with an algorithm of order . A faster algorithm of order solves the problem with indirect control over K. Therefore the above result connects algorithmic and theoretical best approximation. Date received: July 6, 1995. Date revised: January 8, 1996.     

How good can polynomial interpolation on the sphere be?

This paper explores the quality of polynomial interpolation approximations over the sphere S ^r−1⊂R ^r in the uniform norm, principally for r=3. Reimer [17] has shown there exist fundamental systems for which the norm ‖Λ _n ‖ of the interpolation operator Λ _n , considered as a map from C(S ^r−1) to C(S ^r−1), is bounded by d _n , where d _n is the dimension of the space of all spherical polynomials of degree at most n. Another bound is d _n ^1/2(λ_avg/λ_min)^1/2, where λ_avg and λ_min are the average and minimum eigenvalues of a matrix G determined by the fundamental system of interpolation points. For r=3 these bounds are (n+1)² and (n+1)(λ_avg/λ_min)^1/2, respectively. In a different direction, recent work by Sloan and Womersley [24] has shown that for r=3 and under a mild regularity assumption, the norm of the hyperinterpolation operator (which needs more point values than interpolation) is bounded by O(n ^1/2), which is optimal among all linear projections. How much can the gap between interpolation and hyperinterpolation be closed?

For interpolation the quality of the polynomial interpolant is critically dependent on the choice of interpolation points. Empirical evidence in this paper suggests that for points obtained by maximizing λ_min, the growth in ‖Λ _n ‖ is approximately n+1 for n<30. This choice of points also has the effect of reducing the condition number of the linear system to be solved for the interpolation weights. Choosing the points to minimize the norm directly produces fundamental systems for which the norm grows approximately as 0.7n+1.8 for n<30. On the other hand, ‘minimum energy points’, obtained by minimizing the potential energy of a set of (n+1)² points on S ², turn out empirically to be very bad as interpolation points.

This paper also presents numerical results on uniform errors for approximating a set of test functions, by both interpolation and hyperinterpolation, as well as by non-polynomial interpolation with certain global basis functions.

     

Partially-bent functions

We study a conjecture stated in [6] about the numbers of non-zeros of, respectively, the auto-correlation function and the Walsh transform of the function (–1) ^f(x) , wheref(x) is any boolean function on {0, 1} ⁿ . The result that we obtain leads us to introduce the class of partially-bent functions. We study within these functions the propagation criterion. We characterize those partially-bent functions which are balanced and prove a relation between their number (which is unknown) and the number of non-balanced partially-bent functions on {0, 1} ^n–1. Eventually, we study their correlation immunity.     

A de Montessus type convergence study of a least-squares vector-valued rational interpolation procedure

In a recent paper of the author [A. Sidi, A new approach to vector-valued rational interpolation, J. Approx. Theory 130 (2004) 177–187], three new interpolation procedures for vector-valued functions F(z), where F:C→C^N, were proposed, and some of their algebraic properties were studied. One of these procedures, denoted IMPE, was defined via the solution of a linear least-squares problem. In the present work, we concentrate on IMPE, and study its convergence properties when it is applied to meromorphic functions with simple poles and orthogonal vector residues. We prove de Montessus and Koenig type theorems when the points of interpolation are chosen appropriately.     

A generalization ofL-splines

A theory of generalized splines is developed for all regular formally self adjoint differential operatorsL with real coefficients. A special case of such operators are those which may be factored in the formL =L ₁ ^* L ₁, such as those related to the generalized splines of Ahlberg, Nilson, and Walsh [1, 2], and theL-splines of Schultz and Varga [6]. Theorems giving unique interpolation, integral relations, and convergence rates are established. IfL has a certain positivity property, a useful extremal result is proven.This research was supported in part by a NASA Traineeship, at the Georgia Institute of Technology.     

Generalized Interpolation in Bergman Spaces and Extremal Functions

In a recent paper A. Schuster and K. Seip [SchS] have characterized interpolating sequences for Bergman spaces in terms of extremal functions (or canonical divisors). As these are natural analogues in Bergman spaces of Blaschke products, this yields a Carleson type condition for interpolation. We intend to generalize this idea to generalized free interpolation in weighted Bergman spaces B^{p, α} as was done by V. Vasyunin [Va1] and N. Nikolski [Ni1] (cf.also [Ha2]) in the case of Hardy spaces. In particular we get a strong necessary condition for free interpolation in B^{p, α} on zero–sets of B^{p, α}–functions that in the special case of finite unions of B^{p, α}–interpolating sequences turns out to be also sufficient.     

Piecewise-Linear Approximations of Multidimensional Functions

We develop explicit, piecewise-linear formulations of functions f(x):ℝ ⁿ ↦ℝ, n≤3, that are defined on an orthogonal grid of vertex points. If mixed-integer linear optimization problems (MILPs) involving multidimensional piecewise-linear functions can be easily and efficiently solved to global optimality, then non-analytic functions can be used as an objective or constraint function for large optimization problems. Linear interpolation between fixed gridpoints can also be used to approximate generic, nonlinear functions, allowing us to approximately solve problems using mixed-integer linear optimization methods. Toward this end, we develop two different explicit formulations of piecewise-linear functions and discuss the consequences of integrating the formulations into an optimization problem.     

Estimation de l'erreur d'interpolation d'Hermite dans ℝ n

Summary This paper is devoted to study the Hermite interpolation error in an open subset of ⁿ .It follows a previous work of Arcangeli and Gout [1]. Like this one, it is based principally on the paper of Ciarlet and Raviart [7].We obtain two kinds of the Hermite interpolation error, the first from the Hermite interpolation polynomial, the other from approximation method using the Taylor polynomial.Finally in the last part we study some numerical examples concerning straight finite element methods: in the first and second examples, we use finite elements which are included in the affine theory, but it is not the case in the last example. However, in this case, it is possible to refer to the affine theory by the way of particular study (cf. Argyris et al. [2]; Ciarlet [6]; ciarlet and Raviart [7]; Raviart [11]).

     

On Newton's interpolation polynomials

In this paper functional analytic methods for nuclear locally convex spaces are applied to problems of analytic functions. The question is discussed whether the so-called Newton interpolation polynomials constitute a Schauder-basis in the space of analytic functions on the open unit circle (see Marku evi [3]). There are several different approaches to this problem, see, for instance, Walsh [7] and Gelfond [1]. Here we give a necessary and sufficient condition in terms of the interpolation points only. We consider the above space of analytic functions as a nuclear Kö-the-sequence space and use some deep theorems about nuclear spaces, such as the theorem of Dynin and Mitjagin (see Rolewicz [6], Pietsch An interesting connection with the theory of uniformly distributed sequences is mentioned.     

Zur Approximation pseudoanalytischer Funktionen durch Pseudopolynome

In the theory of pseudoanalytic functions one can define (pseudoanalytic) rational functions, especially polynomials called “pseudopolynomials”. (See Bers [3], [4], Vekua [12]) Therefore it can be developed a theory of approximation and interpolation by rational functions. First results have been published by Bers [3] (Runge's theorem), Ismailov and Taglieva [8]. Let G be a domain of the complex plane bounded by a closed Jordan curve, let w(z) be pseudoanalytic in G. In this paper we deal with a relation between the behaviour of w(z) on C (Hölder-continuity) and the degree of approximation of w(z) by pseudopolynomials. The results correspond to certain theorems of Curtiss, Sewell and Walsh in the theory of analytic functions.     

The Bitangential Inverse Input Impedance Problem for Canonical Systems,I: Weyl-Titchmarsh Classification,Existence and Uniqueness

The inverse input impedance problem is investigated in the class of canonical integral systems with matrizants that are strongly regular J-inner matrix valued functions in the sense introduced in [ArD1]. The set of solutions for a problem with a given input impedance matrix (i.e., Weyl- Titchmarsh function) is parameterized by chains of associated pairs of entire inner p × p matrix valued functions. In our considerations the given data for the inverse bitangential input impedance problem is such a chain and an input impedance matrix, i.e., a p × p matrix valued function in the Carathéodory class. Existence and uniqueness theorems for the solution of this problem are obtained by consideration of a corresponding family of generalized bitangential Carathéodory interpolation problems. The connection between the inverse bitangential input scattering problem that was studied in [ArD4] and the bitangential input impedance problem is also exploited. The successive sections deal with: 1. The introduction, 2. Domains of linear fractional transformations, 3. Associated pairs of the first and second kind, 4. Matrix balls, 5. The classification of canonical systems via the limit ball, 6. The Weyl-Titchmarsh characterization of the input impedance, 7. Applications of interpolation to the bitangential inverse input impedance problem. Formulas for recovering the underlying canonical integral systems, examples and related results on the inverse bitangential spectral problem will be presented in subsequent publications.D. Z. Arov thanks the Weizmann Institute of Science for hospitality and support, partially as a Varon Visiting Professor and partially through the Minerva Foundation. H. Dym thanks Renee and Jay Weiss for endowing the chair which supports his research and the Minerva Foundation.     

L-Splines

In this paper, we study the problem of unique interpolation and approximation by a class of spline functions,L-splines, containing as special cases the deficient and generalized spline functions ofAhlberg, Nilson, andWalsh [3, 5, 6], the Chebyshevian spline functions ofKarlin andZiegler [27], and the piecewise Hermite polynomial functions, as considered in [17]. We first give sufficient conditions for unique interpolation byL-spline functions in Section 2. Then, we obtain newL andL ² error estimates for interpolation byL-splines in Section 4, and show that these error estimates are, in a certain sense, sharp. In addition, we make a similar study for theg-splines ofSchoenberg, cf. [44, 3], in Section 5. In Section 6, an application of these new error estimates is made to the analysis of the error made in the use of finite dimensional subspaces ofL-splines andg-splines. in the Rayleigh-Ritz procedure for the class of nonlinear two-point boundary value problems studied in [17].Because of the rapid growth of the number of papers devoted to or connected with the topic of splines, we believe that a compilation of papers on splines for the reader's use is desirable, and such a list is found in the References at the end of this paper.This research was supported in part by NSF Grant GP-5553Papers not specifically concerned with splines are referred to in the text by [1, 2], etc.     

Optimal recovery of interpolation operators in Hardy spaces

We continue studies begun by C.A. Micchelli and T.J. Rivlin on optimal recovery in H^p spaces. The feature operators are various interpolation operators drawn from the theory of Walsh equiconvergence, as are the information sets. The theory is of interest in that it identifies linear algorithms which might not otherwise be isolated for study or used as approximations of the feature operators. In some cases, we can identify the optimal algorithm although we cannot explicitly determine the exact order of the approximation that it achieves. For Charles Micchelli on his sixtieth birthday, with appreciation Mathematics subject classifications (2000) 41A05, 30B30. A. Sharma: Deceased.     

Quadrature formula for approximating the singular integral of Cauchy type with unbounded weight function on the edges

New quadrature formulas (QFs) for evaluating the singular integral (SI) of Cauchy type with unbounded weight function on the edges is constructed. The construction of the QFs is based on the modification of discrete vortices method (MMDV) and linear spline interpolation over the finite interval [−1,1]. It is proved that the constructed QFs converge for any singular point x not coinciding with the end points of the interval [−1,1]. Numerical results are given to validate the accuracy of the QFs. The error bounds are found to be of order O(h^α|lnh|) and O(h|lnh|) in the classes of functions H^α([−1,1]) and C¹([−1,1]), respectively.     

A numerical approach to variational problems subject to convexity constraint

Summary. We describe an algorithm to approximate the minimizer of an elliptic functional in the form on the set of convex functions u in an appropriate functional space X. Such problems arise for instance in mathematical economics [4]. A special case gives the convex envelope of a given function . Let be any quasiuniform sequence of meshes whose diameter goes to zero, and the corresponding affine interpolation operators. We prove that the minimizer over is the limit of the sequence , where minimizes the functional over . We give an implementable characterization of . Then the finite dimensional problem turns out to be a minimization problem with linear constraints. Received November 24, 1999 / Published online October 16, 2000     

Lineability of sets of nowhere analytic functions

Although the set of nowhere analytic functions on [0,1] is clearly not a linear space, we show that the family of such functions in the space of C^∞-smooth functions contains, except for zero, a dense linear submanifold. The result is even obtained for the smaller class of functions having Pringsheim singularities everywhere. Moreover, in spite of the fact that the space of differentiable functions on [0,1] contains no closed infinite-dimensional manifold in C([0,1]), we prove that the space of real C^∞-smooth functions on (0,1) does contain such a manifold in C((0,1)).     

Continuous piecewise linear finite elements for the Kirchhoff–Love plate equation

A family of continuous piecewise linear finite elements for thin plate problems is presented. We use standard linear interpolation of the deflection field to reconstruct a discontinuous piecewise quadratic deflection field. This allows us to use discontinuous Galerkin methods for the Kirchhoff–Love plate equation. Three example reconstructions of quadratic functions from linear interpolation triangles are presented: a reconstruction using Morley basis functions, a fully quadratic reconstruction, and a more general least squares approach to a fully quadratic reconstruction. The Morley reconstruction is shown to be equivalent to the basic plate triangle (BPT). Given a condition on the reconstruction operator, a priori error estimates are proved in energy norm and L ² norm. Numerical results indicate that the Morley reconstruction/BPT does not converge on unstructured meshes while the fully quadratic reconstruction show optimal convergence.     

Tangential Interpolation in Weighted Vector-valued H p Spaces, with Applications

In this paper, norm estimates are obtained for the problem of minimal-norm tangential interpolation by vector-valued analytic functions in weighted H^p spaces, expressed in terms of the Carleson constants of related scalar measures. Applications are given to the notion of p-controllability properties of linear semigroup systems and controllability by functions in certain Sobolev spaces.