Die Struktur der normalen rationalen Funktionen

Summary We determine the connected components of the set of normal elements of the family _m ⁿ [a,b] of rational functions. Numerical difficulties occuring with the computation of the Chebyshev approximation via the Remez algorithm can be caused by its disconnectedness. In order to illustrate this we give numerical examples.

Gefördert von der DFG unter Nr. Be 808/2     

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.     

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 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     

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

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     

Solving complex approximation problems by semiinfinite - finite optimization techniques: A study on convergence

Summary We transform a complex approximation problem into an equivalent semiinfinite optimization problem whose constraints are described in terms of a quantity [0,2[=I. We study the effect of disturbing the problem by replacingI by a compact subsetMI which includes as special case the discrete case whereM consists only of finitely many points. We introduce a measure for the deviation ofM fromI and show that in any complex approximation problem the minimal distance of the disturbed problem converges quadratically with 0 to the minimal distance of the undisturbed problem which is a generalization of a result by Streit and Nuttall. We also show that in a linear finite dimensional approximation problem the convergence of the coefficients of the disturbed problem is in general at most linear. There are some graphical representations of best complex approximations computed with the described method.     

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     

Strong uniqueness and second order convergence in nonlinear discrete approximation

Summary Strong uniqueness has proved to be an important condition in demonstrating the second order convergence of the generalised Gauss-Newton method for discrete nonlinear approximation problems [4]. Here we compare strong uniqueness with the multiplier condition which has also been used for this purpose. We describe strong uniqueness in terms of the local geometry of the unit ball and properties of the problem functions at the minimum point. When the norm is polyhedral we are able to give necessary and sufficient conditions for the second order convergence of the generalised Gauss-Newton algorithm.     

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.     

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.     

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.     

Asymptotische Entwicklungen für Eigenwerte und Eigenvektoren bei der Approximation parameternichtlinearer Eigenwertaufgaben

Summary In order to apply extrapolation processes to the numerical solution of eigenvalue problems depending nonlinear on a parameter the existence of asymptotic expansions for eigenvalues and eigenvectors is studied. At the end of the paper some numerical examples are given.

     

Ein Abstiegsverfahren für Approximationsaufgaben in normierten Räumen

Summary A numerical method for constrained approximation problems in normed linear spaces is presented. The method uses extremal subgradients of the norms or sublinear functionals involved in the approximation problem considered. Under certain weak assumptions the convergence of the method is proved. For various normed spaces hints for practical realization are given and several numerical examples are described.

---

Ein Abstiegsverfahren für Approximationsaufgaben in normierten Räumen

     

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.     

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.