Ein verallgemeinerter Kettenbruch-Algorithmus zur rationalen Hermite-Interpolation

Summary In this paper we consider rational interpolation for an Hermite Problem, i.e. prescribed values of functionf and its derivatives. The algorithm presented here computes a solutionp/q of the linearized equationsp–fq=0 in form of a generalized continued fraction. Numeratorp and denominatorq of the solution attain minimal degree compatible with the linearized problem. The main advantage of this algorithm lies in the fact that accidental zeros of denominator calculated during the algorithm cannot lead to an unexpected stop of the algorithm. Unattainable points are characterized.

Herrn Prof. Dr. Dr. h.c.mult. L. Collatz zum 70. Geburtstag gewidmet     

OnG 2 continuous cubic spline interpolation

In this paper the interpolation byG ² continuous planar cubic Bézier spline curves is studied. The interpolation is based upon the underlying curve points and the end tangent directions only, and could be viewed as an extension of the cubic spline interpolation to the curve case. Two boundary, and two interior points are interpolated per each spline section. It is shown that under certain conditions the interpolation problem is asymptotically solvable, and for a smooth curvef the optimal approximation order is achieved. The practical experiments demonstrate the interpolation to be very satisfactory. Supported in prat by the Ministry of Science and Technology of Slovenjia, and in part by the NSF and SF of National Educational Committee of China.     

Complément de Schur et sous-différentiel du second ordre d'une fonction convexe

Summary The Schur complement relative to the linear mappingA of a functionf is denotedAf and defined as the image off underA. In this paper we give some estimates for the second-order differential ofAf whenf is either a partially quadratic convex function or aC ² convex function with a nonsingular second-order differential. We then consider an arbitrary convex functionf and study the second-order differentiability ofAf in a more general sense.

     

Sur le choix du paramètre d'ajustement dans le lissage par fonctions spline

Summary We consider the problem of approximating an unknown functionf, known with error atn equally spaced points of the real interval [a, b].To solve this problem, we use the natural polynomial smoothing splines. We show that the eigenvalues associated to these splines converge to the eigenvalues of a differential operator and we use this fact to obtain an algorithm, based on the Generalized Cross Validation method, to calculate the smoothing parameter.With this algorithm, we divide byn the time used by classical methods.

     

Die mehrstellenformeln für den Laplaceoperator

Summary Difference methods for the numerical solution of linear partial differential equations may often be improved by using a weighted right hand side instead of the original right hand side of the differential equation. Difference formulas, for which that is possible, are called Mehrstellenformeln or Hermitian formulas. In this paper the Hermitian formulas for the approximation of Laplace's operator are characterized by a very simple condition. We prove, that in two-dimensional case for a Hermitian formula of ordern at leastn+3 discretization points are necessary. We give examples of such optimal formulas of arbitrary high-order.

     

Bivariate Lagrange interpolation at the Padua points: the ideal theory approach

The Padua points are a family of points on the square [−1, 1]² given by explicit formulas that admits unique Lagrange interpolation by bivariate polynomials. Interpolation polynomials and cubature formulas based on the Padua points are studied from an ideal theoretic point of view, which leads to the discovery of a compact formula for the interpolation polynomials. The L ^p convergence of the interpolation polynomials is also studied. S. De Marchi and M. Vianello were supported by the “ex-60%” funds of the University of Padua and by the INdAM GNCS (Italian National Group for Scientific Computing). Y. Xu was partially supported by NSF Grant DMS-0604056.     

A Family of Approximation Formulas and some Applications

The general scheme, suggested in [1] using a basis of an infinite-dimensional space and allowing to construct finite-dimensional orthogonal systems and interpolation formulas, is improved in the paper. This results particularly in a generalization of the well-known scheme by which periodic interpolatory wavelets are constructed. A number of systems which do not satisfy all the conditions for multiresolution analysis but have some useful properties are introduced and investigated.

Starting with general constructions in Hilbert spaces, we give a more careful consideration to the case connected with the classic Fourier basis.

Convergence of expansions which are similar to partial sums of the summation method of Fourier series, as well as convergence of interpolation formulas are considered.

Some applications to fast calculation of Fourier coefficients and to solution of integrodifferential equations are given. The corresponding numerical results have been obtained by means of MATHEMATICA 3.0 system.     

Enumeration of k-poles

Ak-pole in this paper is a regular planar map withk vertices. Poles with even degrees were first enumerated by Tutte [9] in 1962 where he obtained a very simple and elegant expression. Using Brown's quadratic method, Bender and Canfield [2] derived two algebraic equations for the generating function of the poles. But the equations seem to be quite complicated for the odd degree case, and so far no progress has been seen in utilizing these equations to derive any result for the number of poles with odd degree. In this paper, we use hypergeometric functions to enumerate poles. We will show that the odd degree case is indeed very different from, and much more complicated than, the even degree case. Research supported by NSERC.     

Root finding by divided differences

Summary A recursive method is presented for computing a simple zero of an analytic functionf from information contained in a table of divided differences of its reciprocalh=1/f. A good deal of flexibility is permitted in the choice of ordinate and derivative values, and in the choice of the number of previous points upon which to base the next estimate of the required zero.The method is shown to be equivalent to a process of fitting rational functions with linear numerators to data sampled fromf. Asymptotic and regional convergence properties of such a process have already been studied; in particular, asymptotically quadratic convergence is easily obtained, at the expense of only one function evaluation and a moderate amount of overhead computation per step. In these respects the method is comparable with the Newton form of iterated polynomial inverse interpolation, while its regional convergence characteristics may be superior in certain circum-stances.It is also shown that the method is not unduly sensitive to round-off errors.     

Bisection is optimal

Summary We seek an approximation to a zero of a continuous functionf:[a,b] such thatf(a)0 andf(b)0. It is known that the bisection algorithm makes optimal use ofn function evaluations, i.e., yields the minimal error which is (b–a)/2 ⁿ⁺¹, see e.g. Kung [2]. Traub and Wozniakowski [5] proposed using more general information onf by permitting the adaptive evaluations ofn arbitrary linear functionals. They conjectured [5, p. 170] that the bisection algorithm remains optimal even if these general evaluations are permitted. This paper affirmatively proves this conjecture. In fact we prove optimality of the bisection algorithm even assuming thatf is infinitely many times differentiable on [a, b] and has exactly one simple zero.     

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 method of linearizations for linearly constrained nonconvex nonsmooth minimization

A readily implementable algorithm is given for minimizing a (possibly nondifferentiable and nonconvex) locally Lipschitz continuous functionf subject to linear constraints. At each iteration a polyhedral approximation tof is constructed from a few previously computed subgradients and an aggregate subgradient, which accumulates the past subgradient information. This aproximation and the linear constraints generate constraints in the search direction finding subproblem that is a quadratic programming problem. Then a stepsize is found by an approximate line search. All the algorithm's accumulation points are stationary. Moreover, the algorithm converges whenf happens to be convex.     

The Hilbert Symbol in a Complete Multidimensional Field. I

In the first part of the paper, we discuss two different definitions of the Hilbert symbol and prove their equivalence. The second part is devoted to a detailed consideration of the one-dimensional case for an arbitrary prime number p (odd as well as even). At the end of the article, we give explicit formulas in the general case of a multidimensional local field for both cases of different and mixed characteristics, for an arbitrary prime number. Bibliography: 25 titles.     

Asymptotic near optimality of the bisection method

Summary We seek a approximation to a zero of an infinitely differentiable functionf: [0, 1] such thatf(0)0 andf(1)0. It is known that the error of the bisection method usingn function evaluations is 2^–(n+1). If the information used are function values, then it is known that bisection information and the bisection algorithm are optimal. Traub and Woniakowski conjectured in [5] that the bisection information and algorithm are optimal even if far more general information is permitted. They permit adaptive (sequential) evaluations of arbitrary linear functionals and arbitrary transformations of this information as algorithms. This conjecture was established in [2]. That is forn fixed, the bisection information and algorithm are optimal in the worst case setting. Thus nothing is lost by restricting oneself to function values.One may then ask whether bisection is nearly optimal in theasymptotic worst case sense, that is,possesses asymptotically nearly the best rate of convergence. Methods converging fast asymptotically, like Newton or secant type, are of course, widely used in scientific computation. We prove that the answer to this question is positive for the classF of functions having zeros ofinfinite multiplicity and information consisting of evaluations of continuous linear functionals. Assuming that everyf inF has zeroes withbounded multiplicity, there are known hybrid methods which have at least quadratic rate of convergence asn tends to infinity, see e.g., Brent [1], Traub [4] and Sect. 1.     

Baryzentrische Formeln zur trigonometrischen Interpolation (II) Stabilität und Anwendung auf die Fourieranalyse bei ungleichabständigen Stützstellen

Summary In Part I we have presented barycentric formulas for trigonometric interpolation. Here we show that these formulas make it possible to calculate Fourier coefficients easily and efficiently. The only inconvenience is their instability when the number of interpolating points becomes large; this instability can be avoided in a special case. The formulas can be used to approximate the inverse of a periodic function, for instance of the boundary correspondence function in numerical conformal mapping.

---

Résumé Dans la première partie, nous avons présenté des formules barycentriques pour l'interpolation trigonométrique. Ici, nous montrons que ces formules permettent une analyse de Fourier particuliérement simple et efficiente; leur seul inconvénient réside dans leur instabilité lorsque le nombre de noeuds croît, instabilité qui peut être évitée dans un cas particulier. Elles sont applicables à l'approximation de l'inverse d'une fonction périodique, par exemple de la fonction de correspondance des frontières en application conforme numérique.

     

Monotone and Convex C 1 Hermite Interpolants Generated by a Subdivision Scheme

   Abstract. We propose C ¹ Hermite interpolants generated by the general subdivision scheme introduced by Merrien [17] and satisfying monotonicity or convexity constraints. For arbitrary values and slopes of a given function f at the end-points of a bounded interval, which are compatible with the contraints, the given algorithms construct shape-preserving interpolants. Moreover, these algorithms are quite simple and fast as well as adapted to CAGD. We also give error estimates in the case of interpolation of smooth functions.     

Bisection is not optimal on the average

Summary We seek the zero of a continuous increasing functionf: [0, 1] [–1, 1] such thatf(0)=–1 andf(1)=1. It is known that the bisection method makes optimal use ofn function evaluations within a worst case analysis. In this paper we study the average error with respect to the natural measure of Graf et al. (1986). We prove that the bisection method is not optimal on the average. Actually, the average error of the bisection method is about (1/2) ⁿ , while the average error of the optimal method is less than ⁿ with some <1/2.     

Fehlerabschätzung für die numerische Differentiation analytischer Funktionen durch Quadratur

Summary Numerical treatment of the integral in Cauchy's integral formula produces approximations for the derivatives of an analytic functionf; this fact has already been utilized byLyness andMoler [3, 4]. In the present paper this idea is investigated especially in view of the accuracy of these formulas regarded as quadrature formulas. Since the integration can be reduced to the integration of a periodic analytic function, it is possible to continue the considerations ofDavis [2] in order to find bounds for the error of the differentiation rules. For the application of these bounds one essentially needs estimations of the maximum off on a circle inside of its region of analyticity. Examples show the practical use of the bounds.

---

---

Meinem verehrten LehrerH. Görtler zur Vollendung seines 60. Lebensjahres gewidmet     

A summability method for the arithmetic Fourier transform

The Arithmetic Fourier Transform (AFT) is an algorithm for the computation of Fourier coefficients, which is suitable for parallel processing and in which there are no multiplications by complex exponentials. This is accomplished by the use of the Möbius function and Möbius inversion. However, the algorithm does require the evaluation of the function at an array of irregularly spaced points. In the case that the function has been sampled at regularly spaced points, interpolation is used at the intermediate points of the array. Generally theAFT is most effective when used to calculate the Fourier cosine coefficients of an even function.In this paper a summability method is used to derive a modification of theAFT algorithm. The proof of the modification is quite independent of theAFT itself and involves a summation by primes. One advantage of the new algorithm is that with a suitable sampling scheme low order Fourier coefficients may be calculated without interpolation.     

A remark on random and equidistributed sequences

The average of the values of a function f on the points of an equidistributed sequence in [0, 1] ^s converges to the integral of f as soon as f is Riemann integrable. Some known low discrepancy sequences perform faster integration than independent random sampling (cf. [1]). We show that a small random absolutely continuous perturbation of an equidistributed sequence allows to integrate bounded Borel functions, and more generally that, if the law of the random perturbation doesn't charge polar sets, such perturbed sequences allow to integrate bounded quasi-continuous functions.