On Gauss quadrature formulas with equal weights

Summary It is well known that the Chebyshev weight function (1–x ²)^–1/2 is the only weight function (up to a linear transformation) for which then point Gauss quadrature formula has equal weights for alln. In this paper we describe all weight functions for which thenm point Gauss quadrature formula has equal weights for alln, wherem is fixed.     

On the convergence of finite-difference schemes for parabolic equations with variable coefficients

Summary We study the convergence of the finite-difference schemes for the first initial-boundary value problem for linear second-order parabolic equations with variable coefficients. Using the bilinear version of the Bramble-Hilbert lemma we obtain estimate of convergence, in discreteW ₂ ^{1, 1/2} norm, compatible with the smoothness of generalized solutionuW ₂ ^{, /2} (Q) (1<3) and coefficients of equation.     

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.     

Generalizations of the projection method with applications to SOR theory for hermitian positive semidefinite linear systems

Summary Ann×n complex matrixB is calledparacontracting if B₂1 and 0x[N(I-B)]Bx₂<x₂. We show that a productB=B _k B _k–1 ...B ₁ ofk paracontracting matrices is semiconvergent and give upper bounds on the subdominant eigenvalue ofB in terms of the subdominant singular values of theB _i 's and in terms of the angles between certain subspaces. Our results here extend earlier results due to Halperin and due to Smith, Solomon and Wagner. We also determine necessary and sufficient conditions forn numbers in the interval [0, 1] to form the spectrum of a product of two orthogonal projections and hence characterize the subdominant eigenvalue of such a product. In the final part of the paper we apply the upper bounds mentioned earlier to provide an estimate on the subdominant eigenvalue of the SOR iteration matrix associated with ann×n hermitian positive semidefinite matrixA none of whose diagonal entries vanish.The work of this author was supported in part by NSF Research Grant No. MCS-8400879     

Finite element solution of nonlinear elliptic problems

Summary The study of the finite element approximation to nonlinear second order elliptic boundary value problems with mixed Dirichlet-Neumann boundary conditions is presented. In the discretization variational crimes are commited (approximation of the given domain by a polygonal one, numerical integration). With the assumption that the corresponding operator is strongly monotone and Lipschitz-continuous and that the exact solutionuH ¹(), the convergence of the method is proved; under the additional assumptionuH ²(), the rate of convergenceO(h) is derived without the use of Green's theorem.     

Numerical stability of descent methods for solving linear equations

Summary In this paper we perform a round-off error analysis of descent methods for solving a liner systemAx=b, whereA is supposed to be symmetric and positive definite. This leads to a general result on the attainable accuracy of the computed sequence {x _i } when the method is performed in floating point arithmetic. The general theory is applied to the Gauss-Southwell method and the gradient method. Both methods appear to be well-behaved which means that these methods compute an approximationx _i to the exact solutionA ^–1 b which is the exact solution of a slightly perturbed linear system, i.e. (A+A)x _i =b, A of order A, where is the relative machine precision and · denotes the spectral norm.     

On spectral variations under bounded real matrix perturbations

Summary In this paper we investigate the set of eigenvalues of a perturbed matrix {ie509-1} whereA is given and ^{n × n}, ||< is arbitrary. We determine a lower bound for thisspectral value set which is exact for normal matricesA with well separated eigenvalues. We also investigate the behaviour of the spectral value set under similarity transformations. The results are then applied tostability radii which measure the distance of a matrixA from the set of matrices having at least one eigenvalue in a given closed instability domain _b.     

On the solution of singular linear systems of algebraic equations by semiiterative methods

Summary For a square matrixT ^n,n , where (I–T) is possibly singular, we investigate the solution of the linear fixed point problemx=T x+c by applying semiiterative methods (SIM's) to the basic iterationx ₀ ⁿ ,x _k T c _k–1+c(k1). Such problems arise if one splits the coefficient matrix of a linear systemA x=b of algebraic equations according toA=M–N (M nonsingular) which leads tox=M ^–1 N x+M ^–1 bT x+c. Even ifx=T x+c is consistent there are cases where the basic iteration fails to converge, namely ifT possesses eigenvalues 1 with ||1, or if =1 is an eigenvalue ofT with nonlinear elementary divisors. In these cases — and also ifx=T x+c is incompatible — we derive necessary and sufficient conditions implying that a SIM tends to a vector which can be described in terms of the Drazin inverse of (I–T). We further give conditions under which is a solution or a least squares solution of (I–T)x=c.Research supported in part by the Alexander von Humboldt-Stiftung     

Reconstructing dimensions of intersections of convex sets

Denoting by dimA the dimension of the affine hull of the setA, we prove that if {K _i:i T} and {K _i ^j :i T} are two finite families of convex sets inR ⁿ and if dim {K _i :i S} = dim {K _i ^j :i S}for eachS T such that|S| n + 1 then dim {K _i :i T} = dim {K _i : {i T}}.     

Convergence des solutions formelles de certaines équations fonctionnelles

Résumé Soitq un nombre algébrique de module 1, qui ne soit pas une racine de l'unité, etP [X, Y ₀,Y ₁] un polynôme non nul. Dans cet article, nous montrons que toute solution de l'équation fonctionnelleP(z, (z), (qz))=0, qui est une série formelle (z) dansQ[[z]], a un rayon de convergence non nul.

---

Summary Letq Q be an algebraic number of modulus one that is not a root of unity. LetP Q[X, Y ₀,Y ₁] be a non zero polynomial. In this paper, we show that every formal power series,(z) Q[[z]], solution of the functional equationP(z), (z), (qz)) = 0 has a non zero radius of convergence.

     

Numerical treatment of O.D.Es.: The theory ofA-methods

Summary Almost all commonly used methods for O.D.Es. and their most miscellaneous compositions areA-methods, i.e. they can be reduced toz _o=;z _j =Az _j–1 +h(x _j–1 ,z _j–1 ,z _j ;h),z _j ^s ,A(s,s),j=1(1)m. This paper presents a general theory forA-methods and discusses its practical consequences. An analysis of local discretization error (l.d.e.) accumulation results in a general order criterium and reveals which part of the l.d.e. effectively influences the global error. This facilitates the comparison of methods and generalizes considerably the concept of error constants. It is shown, as a consequence, that the global error cannot be safely controlled by the size of the l.d.e. and that the conventional error control may fail in important cases. Furthermore, Butcher's effective order methods, the concept of Nordsieck forms, and Gear's interpretation of lineark-step schemes as relaxation methods are generalized. The stability of step changing is shortly discussed.     

Approximation under an arc length constraint

Let f C[a, b]. LetP be a subset ofC[a, b], L b – a be a given real number. We say thatp P is a best approximation tof fromP, with arc length constraintL, ifA[p] _b ^a [1 + (p(x)) ²]dx L andp – f q – f for allq P withA[q] L. represents an arbitrary norm onC[a, b]. The constraintA[p] L might be interpreted physically as a materials constraint.In this paper we consider the questions of existence, uniqueness and characterization of constrained best approximations. In addition a bound, independent of degree, is found for the arc length of a best unconstrained Chebyshev polynomial approximation.The work of L. L. Keener is supported by the National Research Council of Canada Grant A8755.     

The finite element method for nonlinear elliptic equations with discontinuous coefficients

Summary The study of the finite element approximation to nonlinear second order elliptic boundary value problems with discontinuous coefficients is presented in the case of mixed Dirichlet-Neumann boundary conditions. The change in domain and numerical integration are taken into account. With the assumptions which guarantee that the corresponding operator is strongly monotone and Lipschitz-continuous the following convergence results are proved: 1. the rate of convergenceO(h ) if the exact solutionuH ¹ () is piecewise of classH ¹⁺ (0<1);2. the convergence without any rate of convergence ifuH ¹ () only.     

Connected and alternating vectors: Polyhedra and algorithms

Given a graphG = (V, E), leta ^S, S L, be the edge set incidence vectors of its nontrivial connected subgraphs.The extreme points of = {x R ^E: a^sx |V(S)| - |S|, S L} are shown to be integer 0/± 1 and characterized. They are the alternating vectorsb ^k, k K, ofG. WhenG is a tree, the extreme points ofB 0,b ^kx 1,k K} are shown to be the connected vectors ofG together with the origin. For the four LP's associated with andA, good algorithms are given and total dual integrality of andA proven.On leave from Swiss Federal Institute of Technology, Zurich.     

Spectral properties of cosine operator functions

LetA be the generator of a cosine functionC _t ,t R in a Banach spaceX; we shall connect the existence and uniqueness of aT-periodic mild solution of the equationu = Au + f with the spectral property 1 (C _T ) and, in caseX is a Hilbert space, also with spectral properties ofA. This research was supported in part by DAAD, West Germany.     

Round-off error analysis of iterations for large linear systems

Summary We deal with the rounding error analysis of successive approximation iterations for the solution of large linear systemsA _x =b. We prove that Jacobi, Richardson, Gauss-Seidel and SOR iterations arenumerically stable wheneverA=A ^*>0 andA has PropertyA. This means that the computed resultx _k approximates the exact solution with relative error of order A·A ^–1 where is the relative computer precision. However with the exception of Gauss-Seidel iteration the residual vector Ax _k –b is of order A² A ^–1 and hence the remaining three iterations arenot well-behaved.This work was partly done during the author's visit at Carnegie-Mellon University and it was supported in part by the Office of Naval Research under Contract N00014-76-C-0370; NR 044-422 and by the National Science Foundation under Grant MCS75-222-55     

Joint convergence of conditional expectations

Let P_n, nIN{0}, be probability measures on a-fieldA; f_n, nIN{0}, be a family of uniformly boundedA-measurable functions andA _n, nIN, be a sequence of sub--fields ofA, increasing or decreasing to the-fieldA _o. It is shown in this paper that the conditional expectations converge in P_o-measure to with k, n, m , if P_n|A, nIN, converges uniformly to P_n|A and f_n, nIN, converges in P_o-measure to f_o.     

On a theorem of Stein-Rosenberg type in interval analysis

Summary In classical numerical analysis the asymptotic convergence factor (R ₁-factor) of an iterative processx ^m+1=Ax^m+b coincides with the spectral radius of then×n iteration matrixA. Thus the famous Theorem of Stein and Rosenberg can at least be partly reformulated in terms of asymptotic convergence factor. Forn×n interval matricesA with irreducible upper bound and nonnegative lower bound we compare the asymptotic convergence factor ( _T ) of the total step method in interval analysis with the factor _S of the corresponding single step method. We derive a result similar to that of the Theorem of Stein and Rosenberg. Furthermore we show that _S can be less than the spectral radius of the real single step matrix corresponding to the total step matrix |A| where |A| is the absolute value ofA. This answers an old question in interval analysis.     

Stability inL 1 of some integral operators

A class of Markov operators appearing in biomathematics is investigated. It is proved that these operators are asymptotic stable inL ¹, i.e. lim _n P ⁿ f=0 forfL ¹ and f(x) dx=0.     

Gauss-Tchebycheff quadrature formulas

Summary It is well known that the Tchebycheff weight function (1-x ²)^–1/2 is the only weight function (up to a linear transformation) for which then point Gauss quadrature formula has equal weights for alln. In this paper we describe explicitly all weight functions which have the property that then _k-point Gauss quadrature formula has equal weights for allk, where (n _k),n ₁<n ₂<..., is an arbitrary subsequence of . Furthermore results on the possibility of Tchebycheff quadrature on several intervals are given.