Basis of splines associated with some singular differential operators

Functions being piecewise in Ker (D ^k DpD) are a special case of Chebyshev splines having one nontrivial weight and also a special case of singular splines. An algorithm is designed which enables calculating with related B-splines and their derivatives. Ifp(t) is approximated by a piecewise constant, an interesting recurrence for calculating with polynomial B-splines is obtained.     

The Chebyshev solution of the linear matrix equationAX+YB=C

Summary In this paper we investigate the properties of the Chebyshev solutions of the linear matrix equationAX+YB=C, whereA, B andC are given matrices of dimensionsm×r, s×n andm×n, respectively, wherer ands. We separately consider two particular cases. In the first case we assumem=r+1 andn=s+1, in the second caser=s=1 andm, n are arbitrary. For these two cases, under the assumption that the matricesA andB are full rank, we formulate necessary and sufficient conditions characterizing the Chebyshev solution ofAX+YB=C and we give the formulas for the Chebyshev error. Then, we propose an algorithm which may be applied to compute the Chebyshev solution ofAX+YB=C for some particular cases. Some numerical examples are also given.     

Shohat-Favard and Chebyshev’s methods in d-orthogonality

This paper is concerned with the Shohat-Favard, Chebyshev and Modified Chebyshev methods for d-orthogonal polynomial sequences d∈ℕ. Shohat-Favard’s method is presented from the concept of dual sequence of a sequence of polynomials. We deduce the recurrence relations for the Chebyshev and the Modified Chebyshev methods for every d∈ℕ. The three methods are implemented in the Mathematica programming language. We show several formal and numerical tests realized with the software developed. This revised version was published online in June 2006 with corrections to the Cover Date.     

A parallel algorithm for discrete least squares rational approximation

Summary A new method for discrete least squares linearized rational approximation is presented. It generalizes the algorithm of Rutishauser-Gragg-Harrod-Reichel for discrete least squares polynomial approximation to the rational case. The algorithm is fast in the sense that it requires orderm computation time wherem is the number of data points and is the degree of the approximant. We describe how this algorithm can be implemented in parallel.     

A hybrid Arnoldi-Faber iterative method for nonsymmetric systems of linear equations

Summary We present here a new hybrid method for the iterative solution of large sparse nonsymmetric systems of linear equations, say of the formAx=b, whereA ^{N, N} , withA nonsingular, andb ^N are given. This hybrid method begins with a limited number of steps of the Arnoldi method to obtain some information on the location of the spectrum ofA, and then switches to a Richardson iterative method based on Faber polynomials. For a polygonal domain, the Faber polynomials can be constructed recursively from the parameters in the Schwarz-Christoffel mapping function. In four specific numerical examples of non-normal matrices, we show that this hybrid algorithm converges quite well and is approximately as fast or faster than the hybrid GMRES or restarted versions of the GMRES algorithm. It is, however, sensitive (as other hybrid methods also are) to the amount of information on the spectrum ofA acquired during the first (Arnoldi) phase of this procedure.     

On the use of rational iterations and domain decomposition methods for the Helmholtz problem

An iterative algorithm for the numerical solution of the Helmholtz problem is considered. It is difficult to solve the problem numerically, in particular, when the imaginary part of the wave number is zero or small. We develop a parallel iterative algorithm based on a rational iteration and a nonoverlapping domain decomposition method for such a non-Hermitian, non-coercive problem. Algorithm parameters (artificial damping and relaxation) are introduced to accelerate the convergence speed of the iteration. Convergence analysis and effective strategies for finding efficient algorithm parameters are presented. Numerical results carried out on an nCUBE2 are given to show the efficiency of the algorithm. To reduce the boundary reflection, we employ a hybrid absorbing boundary condition (ABC) which combines the first-order ABC and the physical $Q$ ABC. Computational results comparing the hybrid ABC with non-hybrid ones are presented. Received May 19, 1994 / Revised version received March 25, 1997     

A modification to the linpack downdating algorithm

Alinpack downdating algorithm is being modified by interleaving its two different phases, the forward solving a triangular system and the backward sweep of Givens rotations, to yield a new forward method for finding the Cholesky decomposition ofR ^T R –zz ^T . By showing that the new algorithm saves forty percent purely redundant operations of the original, better stability properties are expected. In addition, various other downdating algorithms are rederived and analyzed under a uniform framework.     

A numerical study of optimized sparse preconditioners

Preconditioning strategies based on incomplete factorizations and polynomial approximations are studied through extensive numerical experiments. We are concerned with the question of the optimal rate of convergence that can be achieved for these classes of preconditioners.Our conclusion is that the well-known Modified Incomplete Cholesky factorization (MIC), cf. e.g., Gustafsson [20], and the polynomial preconditioning based on the Chebyshev polynomials, cf. Johnson, Micchelli and Paul [22], have optimal order of convergence as applied to matrix systems derived by discretization of the Poisson equation. Thus for the discrete two-dimensional Poisson equation withn unknowns,O(n ^1/4) andO(n ^1/2) seem to be the optimal rates of convergence for the Conjugate Gradient (CG) method using incomplete factorizations and polynomial preconditioners, respectively. The results obtained for polynomial preconditioners are in agreement with the basic theory of CG, which implies that such preconditioners can not lead to improvement of the asymptotic convergence rate.By optimizing the preconditioners with respect to certain criteria, we observe a reduction of the number of CG iterations, but the rates of convergence remain unchanged.Supported by The Norwegian Research Council for Science and the Humanities (NAVF) under grants no. 413.90/002 and 412.93/005.Supported by The Royal Norwegian Council for Scientific and Industrial Research (NTNF) through program no. STP.28402: Toolkits in industrial mathematics.     

Optimum stationary and nonstationary iterative methods for the solution of singular linear systems

Summary A number of iterative methods for the solution of the singular linear systemAx=b (det(A)=0 andb in the range ofA) is analyzed and studied. Among them are the Stationaryk-Step, the Accelerated Overrelaxation (AOR) and the Nonstationary Second Order Chebyshev Semi-Iterative ones. It is proved that, under certain assumptions, the corresponding optimum semiconvergent schemes, which present a great resemblance with their analogs for the nonsingular case, can be determined. Finally, a number of numerical examples shows how one can use the theory to obtain the optimum parameters for each applicable semiconvergent method.     

Pivoting strategy for rank-one modification ofLDM t-like factorization

The rank-one modification algorithm of theLDM ^t factorization was given by Bennett [1]. His method, however, could break down even when the matrix is nonsingular and well-conditioned. We introduce a pivoting strategy for avoiding possible break-down as well as for suppressing error growth in the modification process. The method is based on a symbolic formula of the rank-one modification of the factorization of a possibly singular nonsymmetric matrix. A new symbolic formula is also obtained for the inverses of the factor matrices. Repeated application of our method produces theLDM ^t-like product form factorization of a matrix. A numerical example is given to illustrate our pivoting method. An incomplete factorization algorithm is also introduced for updating positive definite matrix useful in quasi-Newton methods, in which the Fletcher and Powell algorithm [2] and the Gill, Murray and Saunders algorithm [4] are usually used.This paper is presented at the Japan SIAM Annual Meeting held at University of Tokyo, Japan, October 7–9, 1991.     

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     

Some positive cotes numbers for the chebyshev weight function

We show that, for the Chebyshev weight function (1–x ²)^–1/2, the Cotes numbers for the quadrature rule with nodes at the zeros of the ultraspherical polynomialP _n ^/() are nonnegative if and only if –1/2<1.     

Sobolev inner products and orthogonal polynomials of Sobolev type

This survey paper deals with polynomials which are orthogonal with respect to scalar products of the form _R F ^T[A]G withF ^T=[f(x), f(Ⅎ(x),...f ^(y)(x)], [A] A _ji =A _ji =A _ij =d _ji (I _ji ) where d _ji is a measure of supportI _ij and [A] is positive semi-definite. Basic properties are indicated or proved in particular cases.     

High dimensional polynomial interpolation on sparse grids

We study polynomial interpolation on a d-dimensional cube, where d is large. We suggest to use the least solution at sparse grids with the extrema of the Chebyshev polynomials. The polynomial exactness of this method is almost optimal. Our error bounds show that the method is universal, i.e., almost optimal for many different function spaces. We report on numerical experiments for d = 10 using up to 652 065 interpolation points. This revised version was published online in June 2006 with corrections to the Cover Date.     

Error bounds for a near-minimax approximation

It is known that a near minimax polynomial approximation tof C [–1, 1] is provided by a finite carrier projectionM _n fromC[–1, 1] onto the subspace of all polynomials of degree n, such thatM _nf is a weighted least squares approximation off on the set consisting of the extreme points of the Chebyshev polynomialT _{2n + 1}. In this paper, upper bounds for the error f–M _n f are given in terms of divided differences.     

A Levin-type algorithm for accelerating the convergence of Fourier series

A nonlinear sequence transformation is presented which is able to accelerate the convergence of Fourier series. It is tailored to be exact for a certain model sequence. As in the case of the Levin transformation and other transformations of Levin-type, in this model sequence the partial sum of the series is written as the sum of the limit (or antilimit) and a certain remainder, i.e., it is of Levin-type. The remainder is assumed to be the product of a remainder estimate and the sum of the first terms oftwo Poincaré-type expansions which are premultiplied by two different phase factors. This occurrence of two phase factors is the essential difference to the Levin transformation. The model sequence for the new transformation may also be regarded as a special case of a model sequence based on several remainder estimates leading to the generalized Richardson extrapolation process introduced by Sidi. An algorithm for the recursive computation of the new transformation is presented. This algorithm can be implemented using only two one-dimensional arrays. It is proved that the sequence transformation is exact for Fourier series of geometric type which have coefficients proportional to the powers of a numberq, |q|<1. It is shown that under certain conditions the algorithm indeed accelerates convergence, and the order of the convergence is estimated. Finally, numerical test data are presented which show that in many cases the new sequence transformation is more powerful than Wynn's epsilon algorithm if the remainder estimates are properly chosen. However, it should be noted that in the vicinity of singularities of the Fourier series the new sequence transformation shows a larger tendency to numerical instability than the epsilon algorithm.     

A Banach space in which all compact sets, but not all bounded sets, admit Chebyshev centers

Given a Banach spaceX, letc ₀(X) be the space of all null sequences inX (equipped with the supremum norm). We show that: 1) each compact set inc ₀(X) admits a (Chebyshev) center iff each compact set inX admits a center; 2) forX satisfying a certain condition (Q), each bounded set inc ₀(X) admits a center iffX is quasi uniformly rotund. We construct a Banach spaceX such that the compact subsets ofX admit centers,X satisfies the condition (Q) andX is not quasi uniformly rotund. It follows that the Banach spaceE=c ₀(X) has the property from the title. Eine überarbeitete Fassung ging am 4. 7. 2001 ein     

Weak Chebyshev Subspaces and Continuous Selections for Parametric Projections

We examine the existence of continuous selections for the parametric projection onto weak Chebyshev subspaces. In particular, we show that if is the class of polynomial splines of degree n with the k fixed knots then the parametric projection admits a continuous selection if and only if the number of knots does not exceed the degree of splines plus one. February 15, 1996. Date revised: September 16, 1996.     

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.     

Recurrence Relations for Chebyshev-Type Methods

The convergence of new second-order iterative methods are analyzed in Banach spaces by introducing a system of recurrence relations. A system of a priori error bounds for that method is also provided. The methods are defined by using a constant bilinear operator A , instead of the second Fréchet derivative appearing in the defining formula of the Chebyshev method. Numerical evidence that the methods introduced here accelerate the classical Newton iteration for a suitable A is provided. Accepted 23 October 1998