Discrete cubic spline interpolation

Summary In the present paper we study the existence, uniqueness and convergence of discrete cubic spline which interpolate to a given function at one interior point of each mesh interval. Our result in particular, includes the interpolation problems concerning continuous periodic cubic splines and discrete cubic splines with boundary conditions considered respectively in Meir and Sharma (1968) and Lyche (1976) for the case of equidistant knots.     

Natural spline functions,their associated eigenvalue problem

Summary We consider the problem of studying the behaviour of the eigenvalues associated with spline functions with equally spaced knots. We show that they are wherem is the order of the spline andn, the number of knots.This result is of particular interest to prove optimality properties of the Generalized Cross-Validation Method and had been conjectured by Craven and Wahba in a recent paper.     

Error estimates for spline interpolants on equidistant grids

Summary For oddm, the error of them-th-degree spline interpolant of power growth on an equidistant grid is estimated. The method is based on a decomposition formula for the spline function, which locally can be represented as an interpolation polynomial of degreem which is corrected by an (m+1)-st.-order difference term.Dedicated to Prof. Dr. Karl Zeller on the occasion of his 60th birthday     

An algorithmic approach to Hermite-Birkhoff-interpolation

Summary This paper deals with an algorithmic approach to the Hermite-Birkhoff-(HB)interpolation problem. More precisely, we will show that Newton's classical formula for interpolation by algebraic polynomials naturally extends to HB-interpolation. Hence almost all reasons which make Newton's method superior to just solving the system of linear equations associated with the interpolation problem may be repeated. Let us emphasize just two: Newton's formula being a biorthogonal expansion has a well known permanence property when the system of interpolation conditions grows. From Newton's formula by an elementary argument due to Cauchy an important representation of the interpolation error can be derived. All of the above extends to HB-interpolation with respect to canonical complete ebyev-systems and naturally associated differential operators [7]. A numerical example is given.     

Newton interpolation is efficient for approximation of linear functionals

Summary The Newton interpolation approach is developed for approximation of linear functionals. It is shown that in numerical interpolation and numerical differentiation, the Newton interpolation approach is more efficient than solving the Vandermonde systems.This work was supported in part by the United States Air Force under a grant AFOSR 76-3020     

An alternative computational method for the approximation of random functions

Summary This paper shows that a computational procedure for approximation of random functions can be accomplished using purely linear programming techniques. This contrasts with previous results which use a twostage approach for the computation, one of which requires linear programming techniques. Computational results are given.     

An algorithm for a special case of a generalization of the Richardson extrapolation process

Summary A special case of a generalization of the Richardson extrapolation process is considered, and its complete solution is given in closed form. Using this, an algorithm for implementing the extrapolation is devised. It is shown that this algorithm needs a very small amount of arithmetic operations and very little storage. Convergence and stability properties for some cases are also considered.     

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     

On the convergence of an algorithm for discreteL p approximation

Summary The convergence properties of an algorithm for discreteL _p approximation (1p<2) that has been considered by several authors are studied. In particular, it is shown that for 1<p<2 the method converges (with a suitably close starting value) to the best approximation at a geometric rate with asymptotic convergence constant 2-p. A similar result holds forp=1 if the best approximation is unique. However, in this case the convergence constant depends on the function to be approximated.     

A general extrapolation algorithm

Summary In this paper a general formalism for linear and rational extrapolation processes is developped. This formalism includes most of the sequence transformations actually used for convergence acceleration. A general recursive algorithm for implementing the method is given. Convergence results and convergence acceleration results are proved. The vector case and some other extensions are also studied.     

An implementation of the method of Ermakov and Zolotukhin for multidimensional integration and interpolation

Summary An interactive procedure is discussed for generating samples from the density function of Ermakov and Zolotukhin for application to Monte Carlo multiple integration and interpolation. The computational details of the implementation are described together with a numerical example.     

An algorithm for best approximate solutions ofAx=b with a smooth strictly convex norm

Summary In this paper, overdetermined systems ofm linear equations inn unknowns are considered. With ^m equipped with a smooth strictly convex norm, ·, an iterative algorithm for finding the best approximate solution of the linear system which minimizes the ·-error is given. The convergence of the algorithm is established and numerical results are presented for the case when · is anl _p norm, 1<p<.Portions of this paper are taken from the author's Ph.D. thesis at Michigan State University     

General order Newton-Padé approximants for multivariate functions

Summary Padé approximants are a frequently used tool for the solution of mathematical problems. One of the main drawbacks of their use for multivariate functions is the calculation of the derivatives off(x ₁, ...,x _p ). Therefore multivariate Newton-Padé approximants are introduced; their computation will only use the value off at some points. In Sect. 1 we shall repeat the univariate Newton-Padé approximation problem which is a rational Hermite interpolation problem. In Sect. 2 we sketch some problems that can arise when dealing with multivariate interpolation. In Sect. 3 we define multivariate divided differences and prove some lemmas that will be useful tools for the introduction of multivariate Newton-Padé approximants in Sect. 4. A numerical example is given in Sect. 5, together with the proof that forp=1 the classical Newton-Padé approximants for a univariate function are obtained.     

An elementary algebraic representation of polynomial spline interpolants for equidistant lattices and its condition

Summary A customary representation formula for periodic spline interpolants contains redundance which, however, can be eliminated by a transcendent method. We use an elementary indentity for the generalized Euler-Frobenius-polynomials, which seems to be unknown until now, in order to derive the theory by purely algebraic arguments. The general cardinal spline interpolation theory can be obtained from the periodic case by a simple approach to the limit. Our representation has minimum condition for odd/even degree if the interpolation points are the lattice (mid-)points. We evaluate the corresponding condition numbers and give an asymptotic representation for them.     

An algorithm for segment approximation

Summary An algorithm for computing a set of knots which is optimal for the segment approximation problem is developed. The method yields a sequence of real numbers which converges to the minimal deviation and a corresponding sequence of knot sets. This sequence splits into at most two subsequences which converge to leveled sets of knots. Such knot sets are optimal. Numerical results concerning piecewise polynomial approximation are given.     

Unicity of best one-sidedL 1-approximations

Summary This paper deals with the problem of uniqueness in one-sidedL ₁-approximation. The chief purpose is to characterize finite dimensional subspacesG of the space of continuous or differentiable functions which have a unique best one-sidedL ₁-approximation. In addition, we study a related problem in moment theory. These considerations have an important application to the uniqueness of quadrature formulae of highest possible degree of precision.     

A unified approach to methods for the simultaneous computation of all zeros of generalized polynomials

Summary Applying Newton's method to a particular system of nonlinear equations we derive methods for the simultaneous computation of all zeros of generalized polynomials. These generalized polynomials are from a function space satisfying a condition similar to Haar's condition. By this approach we bring together recent methods for trigonometric and exponential polynomials and a well-known method for ordinary polynomials. The quadratic convergence of these methods is an immediate consequence of our approach and needs not to be proved explicitly. Moreover, our approach yields new interesting methods for ordinary, trigonometric and exponential polynomials and methods for other functions occuring in approximation theory.     

Padé-type approximants of exp (−z) whose denominators are (1+z/n) n

Summary In this paper, we show that the sequences of Padé-type approximants (k–1/k) and (k/k) converge to exp (–z), uniformly and geometrically on every compact subset of the plane. A numerical study has been done, which discriminates these sequences from the point of view ofA-acceptability.     

Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones

Summary The problem of finding optimal cycles in a doubly weighted directed graph (Problem A) is closely related to the problem of approximating bivariate functions by the sum of two univariate functions with respect to the supremum norm (Problem B). The close relationship between Problem A and Problem B is detected by the characterization (7.4) of the distance dist (f, t) of Problem B.In Part 1 we construct an algorithm for Problem A where the essential role is played by the minimal lengthsy _j(k) defined by (2.3). If weight functiont1 then the minimum of Problem A is computed by equality (2.4). Ift1 then the minimum is obtained by a binary search procedure, Algorithm 3.In Part 2 we construct our algorithms for solving Problem B by following exactly the ideas of Part 1. By Algorithm 4 we compute the minimal pseudolengthsh _k(y, M) defined by (7.5). If weight functiont1 then the infimum dist(f,t) of Problem B is obtained by equality (7.12) which is closely related to (2.4). Ift1 we compute the infimum dist(f,t) by the binary search procedure Algorithm 5.Additionally, Algorithm 4 leads to a constructive proof of the existence of continuous optimal solutions of Problem B (see Theorem 7.1e) which is already known in caset1 but unknown in caset1.Interesting applications to the steady-state behaviour of industrial processes with interference (Sect. 3) and the solution of integral equations (Problem C) are included.Supported by Deutsche Forschungsgemeinschaft Grant No. GO 270/3     

Fehlerabschätzungen für Koeffizienten von Exponentialsummen und Polynomen

Zusammenfassung Für Polynome und Exponentialsummen mit festen Frequenzen werden die Normäquivalenzkonstanten zwischen Parameterraum und Funktionenraum untersucht. Dies führt im Exponentialsummenfall auf Tschebyscheff-Exponentialsummen als Verallgemeinerung der Tschebyscheff-Polynome, wenn man nach numerisch praktikablen Strategien zur Fehlerabschätzung im Parameterraum sucht; für theoretische Zwecke wird eine Ungleichung von Markoff-Typ für Exponentialsummen hergeleitet. Im Falle der Polynome ergeben sich asymptotisch optimale Konstanten als Verschärfungen von Resultaten von Gautschi. Ferner wird eine elementare Herleitung der Normäquivalenzkonstanten für den Fall der Monombasis angegeben.

---

Error estimation in coefficients of exponential sums and polynomials

Summary Equivalence constants for the norms on parameter and function space are considered for both polynomials and exponential sums. In the latter case Chebyshev exponential sums are introduced as generalizations of the Chebyshev polynomials, providing a practical method for error estimation in parameter space. For theoretical purposes a Markoff-type inequality is proved. In the case of polynomials asymptotically optimal constants are derived, thus improving on earlier results of Gautschi. Furthermore, a simple construction of the equivalence constants for the monomial basis is included.

Diese Arbeit entstand als Studie Nr.2 des SFB 135 Ökosysteme auf Kalkgestein unter teiweiser Förderung durch die Deutsche Forschungsgemeinschaft. Die numerischen Rechnungen wurden auf der Rechenanlage der Gesellschaft für wissenschaftliche Datenverarbeitung in Göttingen durchgeführt