Which spaces for design?

We determine the largest class of spaces of sufficient regularity which are suitable for design in the sense that they do possess blossoms. It is the class of all spaces containing constants of which the spaces derived under differentiation are Quasi Extended Chebyshev spaces, i.e., they permit Hermite interpolation, Taylor interpolation excepted. It is also the class of all spaces which possess Bernstein bases, or of all spaces for which any associated spline space does possess a B-spline basis. Note that blossoms guarantee that such bases are normalised totally positive bases. They even are the optimal ones.     

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]).

     

A transference theorem for hermite expansions

A transference theorem for multipliers of Hermite expansions is proved. The result allows to transfer weightedL ²(ℝ ⁿ ) estimates from lower to higher dimensions. Research of the author supported by grant BFM2003-06335-603-03 of the D.G.I..     

Fourier analysis of schwarz alternating methods for piecewise hermite bicubic orthogonal spline collocation

The rates of convergence of two Schwarz alternating methods are analyzed for the iterative solution of a discrete problem which arises when orthogonal spline collocation with piecewise Hermite bicubics is applied to the Dirichlet problem for Poisson's equation on a rectangle. In the first method, the rectangle is divided into two overlapping subrectangles, while three overlapping subrectangles are used in the second method. Fourier analysis is used to obtain explicit formulas for the convergence factors by which theH ¹-norm of the errors is reduced in one iteration of the Schwarz methods. It is shown numerically that while these factors depend on the size of overlap, they are independent of the partition stepsize. Results of numerical experiments are presented which confirm the established rates of convergence of the Schwarz methods.This research was supported in part by funds from the National Science Foundation grant CCR-9103451.     

A generalized Taylor factorization for Hermite subdivision schemes

In a recent paper, we investigated factorization properties of Hermite subdivision schemes by means of the so-called Taylor factorization. This decomposition is based on a spectral condition which is satisfied for example by all interpolatory Hermite schemes. Nevertheless, there exist examples of Hermite schemes, especially some based on cardinal splines, which fail the spectral condition. For these schemes (and others) we provide the concept of a generalized Taylor factorization and show how it can be used to obtain convergence criteria for the Hermite scheme by means of factorization and contractivity.     

A new non‐polynomial univariate interpolation formula of Hermite type

A new C ^∞ interpolant is presented for the univariate Hermite interpolation problem. It differs from the classical solution in that the interpolant is of non‐polynomial nature. Its basis functions are a set of simple, compact support, transcendental functions. The interpolant can be regarded as a truncated Multipoint Taylor series. It has essential singularities at the sample points, but is well behaved over the real axis and satisfies the given functional data. The interpolant converges to the underlying real‐analytic function when (i) the number of derivatives at each point tends to infinity and the number of sample points remains finite, and when (ii) the spacing between sample points tends to zero and the number of specified derivatives at each sample point remains finite. A comparison is made between the numerical results achieved with the new method and those obtained with polynomial Hermite interpolation. In contrast with the classical polynomial solution, the new interpolant does not suffer from any ill conditioning, so it is always numerically stable. In addition, it is a much more computationally efficient method than the polynomial approach. This revised version was published online in June 2006 with corrections to the Cover Date.     

Weighted median algorithms for L1 approximation

The weighted median problem arises as a subproblem in certain multivariate optimization problems, includingL ₁ approximation. Three algorithms for the weighted median problem are presented and the relationships between them are discussed. We report on computational experience with these algorithms and on their use in the context of multivariateL ₁ approximation.This work was supported in part by National Science Foundation Grant CCR-8713893 and in part by a grant from The City University of New York PSC-CUNY Research Award program.     

On the finite volume element method

Summary The finite volume element method (FVE) is a discretization technique for partial differential equations. It uses a volume integral formulation of the problem with a finite partitioning set of volumes to discretize the equations, then restricts the admissible functions to a finite element space to discretize the solution. this paper develops discretization error estimates for general selfadjoint elliptic boundary value problems with FVE based on triangulations with linear finite element spaces and a general type of control volume. We establishO(h) estimates of the error in a discreteH ¹ semi-norm. Under an additional assumption of local uniformity of the triangulation the estimate is improved toO(h ²). Results on the effects of numerical integration are also included.This research was sponsored in part by the Air Force Office of Scientific Research under grant number AFOSR-86-0126 and the National Science Foundation under grant number DMS-8704169. This work was performed while the author was at the University of Colorado at Denver     

Spline approximation methods for multidimensional periodic pseudodifferential equations

We investigate several numerical methods for solving the pseudodifferential equationAu=f on the n-dimensional torusT ⁿ . We examine collocation methods as well as Galerkin-Petrov methods using various periodical spline functions. The considered spline spaces are subordinated to a uniform rectangular or triangular grid. For given approximation method and invertible pseudodifferential operatorA we compute a numerical symbol ^C , resp. ^G , depending onA and on the approximation method. It turns out that the stability of the numerical method is equivalent to the ellipticity of the corresponding numerical symbol. The case of variable symbols is tackled by a local principle. Optimal error estimates are established.The second author has been supported by a grant of Deutsche Forschungsgemeinschaft under grant namber Ko 634/32-1.     

A one-step 7-stage Hermite-Birkhoff-Taylor ODE solver of order 11

A one-step 7-stage Hermite-Birkhoff-Taylor method of order 11, denoted by HBT(11)7, is constructed for solving nonstiff first-order initial value problems y^′=f(t,y), y(t₀)=y₀. The method adds the derivatives y^′ to y⁽⁶⁾, used in Taylor methods, to a 7-stage Runge-Kutta method of order 6. Forcing an expansion of the numerical solution to agree with a Taylor expansion of the true solution to order 11 leads to Taylor- and Runge-Kutta-type order conditions. These conditions are reorganized into Vandermonde-type linear systems whose solutions are the coefficients of the method. The new method has a larger scaled interval of absolute stability than the Dormand-Prince DP87 and a larger unscaled interval of absolute stability than the Taylor method, T11, of order 11. HBT(11)7 is superior to DP87 and T11 in solving several problems often used to test higher-order ODE solvers on the basis of the number of steps, CPU time, and maximum global error. Numerical results show the benefit of adding high-order derivatives to Runge-Kutta methods.     

Adaptive Lanczos methods for recursive condition estimation

Estimates for the condition number of a matrix are useful in many areas of scientific computing, including: recursive least squares computations, optimization, eigenanalysis, and general nonlinear problems solved by linearization techniques where matrix modification techniques are used. The purpose of this paper is to propose anadaptiveLanczosestimator scheme, which we callale, for tracking the condition number of the modified matrix over time. Applications to recursive least squares (RLS) computations using the covariance method with sliding data windows are considered.ale is fast for relatively smalln-parameter problems arising in RLS methods in control and signal processing, and is adaptive over time, i.e., estimates at timet are used to produce estimates at timet+1. Comparisons are made with other adaptive and non-adaptive condition estimators for recursive least squares problems. Numerical experiments are reported indicating thatale yields a very accurate recursive condition estimator.Research supported by the US Air Force under grant no. AFOSR-88-0285.Research supported by the US Army under grant no. DAAL03-90-G-105.Research supported by the US Air Force under grant no. AFOSR-88-0285.     

Convergence properties of ART and SOR algorithms

Summary ART algorithms with relaxation parameters are studied for general (consistent or inconsistent) linear algebraic systemsRx=f, and a general convergence theorem is formulated. The advantage of severe underrelaxation is reexamined and clarified. The relationship to solutions obtained by applying SOR methods to the equationRR ^T y=f is investigated.The work of this autor was supported by a research grant from the Natural Sciences and Engineering Research Council of Canada     

A globally and quadratically convergent affine scaling method for linearℓ 1 problems

Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this interior point philosophy can be adapted to the linear ₁ problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide aglobally and ultimatelyquadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim.This paper was presented at the Third SIAM Conference on Optimization, in Boston, April 1989.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University, and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.Research partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.     

An implicit shift bidiagonalization algorithm for ill-posed systems

Iterative methods based on Lanczos bidiagonalization with full reorthogonalization (LBDR) are considered for solving large-scale discrete ill-posed linear least-squares problems of the form min _x Ax–b₂. Methods for regularization in the Krylov subspaces are discussed which use generalized cross validation (GCV) for determining the regularization parameter. These methods have the advantage that no a priori information about the noise level is required. To improve convergence of the Lanczos process we apply a variant of the implicitly restarted Lanczos algorithm by Sorensen using zero shifts. Although this restarted method simply corresponds to using LBDR with a starting vector (AA ^T) ^p b, it is shown that carrying out the process implicitly is essential for numerical stability. An LBDR algorithm is presented which incorporates implicit restarts to ensure that the global minimum of the CGV curve corresponds to a minimum on the curve for the truncated SVD solution. Numerical results are given comparing the performance of this algorithm with non-restarted LBDR.This work was partially supported by DARPA under grant 60NANB2D1272 and by the National Science Foundation under grant CCR-9209349.     

Co-volume methods for degenerate parabolic problems

Summary A complementary volume (co-volume) technique is used to develop a physically appealing algorithm for the solution of degenerate parabolic problems, such as the Stefan problem. It is shown that, these algorithms give rise to a discrete semigroup theory that parallels the continuous problem. In particular, the discrete Stefan problem gives rise to nonlinear semigroups in both the discreteL ¹ andH ^–1 spaces.The first author was supported by a grant from the Hughes foundation, and the second author was supported by the National Science Foundation Grant No. DMS-9002768 while this work was undertaken. This work was supported by the Army Research Office and the National Science Foundation through the Center for Nonlinear Analysis.     

Feedback and adaptive finite element solution of one-dimensional boundary value problems

Summary This paper examines the concepts of feedback and adaptivity for the Finite Element Method. The model problem concernsC ⁰ elements of arbitrary, fixed degree for a one-dimensional two-point boundary value problem. Three different feedback methods are introduced and a detailed analysis of their adaptivity is given.Dedicated to F.L. Bauer on the occasion of his 60th birthdayThis research was partially supported by the Office of Naval Research under grant number N00014-77-C-0623     

An Adaptive Finite Element Method for the H- ψ Formulation of Time-dependent Eddy Current Problems

In this paper, we develop an adaptive finite element method based on reliable and efficient a posteriori error estimates for the H − ψ formulation of eddy current problems with multiply connected conductors. Multiply connected domains are considered by making “cuts”. The competitive performance of the method is demonstrated by an engineering benchmark problem, Team Workshop Problem 7, and a singular problem with analytic solution.W. Zheng was supported in part by China NSF under the grant 10401040.Z. Chen was supported in part by China NSF under the grant 10025102 and 10428105, and by the National Basic Research Project under the grant 2005CB321701.     

Hermite Subdivision Schemes and Taylor Polynomials

We propose a general study of the convergence of a Hermite subdivision scheme ℋ of degree d>0 in dimension 1. This is done by linking Hermite subdivision schemes and Taylor polynomials and by associating a so-called Taylor subdivision (vector) scheme . The main point of investigation is a spectral condition. If the subdivision scheme of the finite differences of is contractive, then is C ⁰ and ℋ is C ^d . We apply this result to two families of Hermite subdivision schemes. The first one is interpolatory; the second one is a kind of corner cutting. Both of them use the Tchakalov-Obreshkov interpolation polynomial.      

Fredholm theory and finite section method for band-dominated operators

The topics of this paper are Fredholm properties and the applicability of the finite section method for band operators onl ^p -spaces as well as for their norm limits which we call band-dominated operators. The derived criteria will be established in terms of the limit operators of the given band-dominated operator. After presenting the general theory, we present its specifications to concrete classes of band-dominated operators.To the memory of Professor Mark KreinSupported by the DFG grant 436 RUS/17/148/95Supported by a DFG Heisenberg grant     

A look-ahead algorithm for the solution of general Hankel systems

Summary The solution of systems of linear equations with Hankel coefficient matrices can be computed with onlyO(n ²) arithmetic operations, as compared toO(n ³) operations for the general cases. However, the classical Hankel solvers require the nonsingularity of all leading principal submatrices of the Hankel matrix. The known extensions of these algorithms to general Hankel systems can handle only exactly singular submatrices, but not ill-conditioned ones, and hence they are numerically unstable. In this paper, a stable procedure for solving general nonsingular Hankel systems is presented, using a look-ahead technique to skip over singular or ill-conditioned submatrices. The proposed approach is based on a look-ahead variant of the nonsymmetric Lanczos process that was recently developed by Freund, Gutknecht, and Nachtigal. We first derive a somewhat more general formulation of this look-ahead Lanczos algorithm in terms of formally orthogonal polynomials, which then yields the look-ahead Hankel solver as a special case. We prove some general properties of the resulting look-ahead algorithm for formally orthogonal polynomials. These results are then utilized in the implementation of the Hankel solver. We report some numerical experiments for Hankel systems with ill-conditioned submatrices.The research of the first author was supported by DARPA via Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).The research of the second author was supported in part by NSF grant DRC-8412314 and Cooperative Agreement NCC 2-387 between NASA and the Universities Space Research Association (USRA).