On the computational complexity of best Chebyshev approximations

The best Chebyshev approximation of degree n to a continuous function f on [0, 1] is the unique polynomial ϕ of degree less than or equal to n such that the maximum difference of f and ϕ on [0, 1] is minimized. On the basis of a formal model of computation, it is shown that the question of whether the best Chebyshev approximations of polynomial-time computable functions on [0, 1] are always polynomial-time computable depends on the relationship among well-known discrete complexity classes. In particular, P = NP implies that these best approximations are polynomial-time computable, and EXP ≠ NEXP implies that these best approximations are not polynomial-time computable. It is also pointed out that the fact that the popular Remes algorithm converges fast does not conflict with the above result, since the Remes algorithm requires, in each iteration, the finding of maximal points of continuous functions on an interval [a, b], which is, in general, provably intractable.     

On certain order constrained Chebyshev rational approximations

Some rational approximations which share the properties of Padé and best uniform approximations are considered. The approximations are best in the Chebyshev sense, but the optimization is performed over subsets of the rational functions which have specified derivatives at one end point of the approximation interval. Explicit relationships between the Padé and uniform approximations are developed assuming the function being approximated satisfies easily verified constraints. The results are applied to the exponential function to determine the existence of best uniform A-acceptable approximations.     

On the sensitivity to rounding errors of Chebyshev series approximations

By analysing the effects of rounding errors from all sources, it is shown that the coefficients of the polynomial interpolating at the points cos jπ/n, (j=0,1,…, n), can be determined by a stable process, and an algorithm is derived which combines efficiency and stability.     

On the convergence rate of vanishing viscosity approximations

Given a strictly hyperbolic, genuinely nonlinear system of conservation laws, we prove the a priori bound ‖u(t, ·) ? u^?(t, ·)‖ = O(1)(1 + t) · |ln ?| on the distance between an exact BV solution u and a viscous approximation u^?, letting the viscosity coefficient ? → 0. In the proof, starting from u we construct an approximation of the viscous solution u^? by taking a mollification u * and inserting viscous shock profiles at the locations of finitely many large shocks for each fixed ?. Error estimates are then obtained by introducing new Lyapunov functionals that control interactions of shock waves in the same family and also interactions of waves in different families. © 2004 Wiley Periodicals, Inc.     

On the rate of convergence of the diffusion approximations

Institute of Mathematics and Informatics, Akademijos 4, 2600 Vilnius, Lithuania. Translated from Lietuvos Matematikos Rinkinys, Vol. 32, No. 2, pp. 261–284, April–June, 1992.     

On optimal convergence for regularized Tikhonov approximations

We consider the generalized solution to a Fredholm integral equation of the first kind, and establish conditions for which the Tikhonov and Raleigh-Ritz approximations converge to the true solution at the same rate as the perturbed data approaches to the exact data.     

On the accuracy and convergence of conjugate flux approximations

We prove that the L²-projections of derivatives of piecewise bilinear or linear finite element approximations of smooth solutions of elliptic boundary-value problems on the interior of uniform meshes, converge in L² and L^∞ at a rate faster than that of derivatives of the approximations themselves.     

On sufficient conditions for the convergence of successive approximations

We obtain sufficient conditions for the convergence of successive approximations to the solution of operator equations. We show how these conditions can be used in the case of nonlinear integral Hammerstein-type equations. Translated fromMatematicheskie Zametki, Vol. 65, No. 6, pp. 854–859, June, 1999.     

On the speed of convergence in the method of Fejer approximations

The problem of the speed of convergence in the method of Fejer approximations is examined, with an application to the problem of finding at least one solution of the system of inequalitiesf _j(x) 0, j=1,..., m, where thef_j(x) are smooth convex functions defined on a real Hilbert space.Translated from Matematicheskie Zametki, Vol. 4, No. 1, pp. 53–62, July, 1968.     

On the convergence of the multigroup approximations for multidimensional media

Summary In this paper, we investigate the stability, convergence, and consistency properties of steady-state multigroup models for submultiplying media with spatial dimensions greater than one. We define these concepts in a Banach space whose norm measures the collision density integrated over phase space. Stability and consistency occur under the conditions that the maximum fluctuations in the total cross section, and in the expected number of secondary particles arising from each energy level, tend to zero as the energy mesh becomes finer. A concluding example and discussion deal with pathologies of the multigroup model in situations where these fluctuations do not tend to zero as the norms of the energy partitions. The results in this paper complement the time-dependent results of both Belleni-Morante and Busoni for isotropic slabs and of Yang Mingzhu and Zhu Guangtian for bounded, three-dimensional media. This work directly extends the steady-state results of Paul Nelson, Jr. and H. D. Victory, Jr. for slab media to steady-state transport in multidimensional media.This research was partially supported by the Alexander von Humboldt Foundation and by a Faculty Development Leave from Texas Tech University during the academic year 1982–1983. Partial support was also provided in the initial stages of this work by the U.S. National Science Foundation under Grant CPE 8007396.     

Chebyshev expansions and rational approximations

Let A(z) = A_m(z) + a_mz^mB(z,m) where A_m(z) is a polynomial in z of degree m-1. Suppose A(z) and B(z,m) are approximated by main diagonal Padé approximations of order n and r respectively. Suppose that the number of operations needed to evaluate both sides of the above equations by means of the Padé approximations and polynomial noted are the same. Thus 4n = 3m + 4r. We address ourselves to the question of which procedure is more efficient? That is, which procedure produces the smallest error? A variant of this problem is the situation where A(z) and B(z,m) are approximated by their representations in infinite series of Chebyshev polynomials of the first kind truncated after n and r terms respectively. Here n = m + r.Let F(z) have two different series type representations in overlapping or completely disjoint regions of the complex z-plane. Suppose that for each representation there is a sequence of rational approximations of the same type, say of the Padé class, which converge for |arg z| < π except possibly for some finite set of points. Assume that the number of machine operations required to make evaluations using the noted approximations are the same. Again, we ask which procedure is best? Other variants are studied.General answers to the above questions are not known. Instead, we illustrate the ideas for a number of the rather common special functions.     

Chebyshev approximations in subspaces of spline functions

The main purpose of this paper is to consider strict approximations from subspaces of spline functions of degree m-1 with k fixed knots. Rice defines the strict approximation which is a particular unique best Chebyshev approximation for problems defined on a finite set. In order to determine best approximations on an interval I we define a sequence of strict approximations on finite subsets of I where the subsets fill up the interval. It is shown that the sequences always converge if k≤m. In the case k>m the sequences are convergent if we restrict ourselves to problems defined on certain subsets of I. It seems to be natural to denote these limits as strict approximations. To be able to compute these functions we also develop a Remez type algorithm.     

On rates of convergence for approximations to the generalized inverse

A rate of convergence result for a general class of approximation methods for the generalized inverse of a bounded linear operator with arbitrary range is presented. Applications are given to a number of iterative and noniterative approximation techniques.     

On the number of best approximations in certain non-linear families of functions

Ohne Zusammenfassung