A Tau method with perturbed boundary conditions for certain ordinary differential equations

Ortiz' recursive formulation of the Lanczos Tau method (TM) is a powerful and efficient technique for producing polynomial approximations for initial or boundary value problems. The method consists in obtaining a polynomial which satisfies (i) aperturbed version of the given differential equation, and (ii) the imposed supplementary conditionsexactly. This paper introduces a new form of the TM, (denoted by PTM), for a restricted class of differential equations, in which the differential equations as well as the supplementary conditions areperturbed simultaneously. PTM is compared to the classical TM from the point of view of their errors: it is found that the PTM error is smaller and more oscillatory than that of the TM; we further find that approximations nearly as accurate as minimax polynomial approximations can be constructed by means of the PTM. Detailed formulae are derived for the polynomial approximations in TM and PTM, based on Canonical Polynomials. Moreover, various limiting properties of Tau coefficients are established and it is shown that the perturbation in PTM behaves asymptotically proprtional to a Chebyshev polynomial. Dedicated to Eduardo L. Ortiz on the occasion of his 70th birthday     

Iterated solutions of linear operator equations with the Tau method

The Tau Method produces polynomial approximations of solutions of differential equations. The purpose of this paper is (i) to extend the recursive formulation of this method to general linear operator equations defined in a separable Hilbert space, and (ii) to develop an iterative refinement procedure which improves on the accuracy of Tau approximations. Applications to Fredholm integral equations demonstrate the effectiveness of this technique.

     

Computation of the canonical polynomials and applications to some optimal control problems

The Tau method is a numerical technique that consists in constructing polynomial approximate solutions for ordinary differential equations. This method has two approaches: operational and recursive. The former converts the differential problem to a matrix problem and produces approximations in terms of a prescribed orthogonal polynomials basis. In the recursive approach, we construct approximate solutions in terms of a special set of polynomials {Q _k (t); k?=?0, 1, 2...} called canonical polynomials basis. In some cases, the Q _k ??s can be obtained explicitly through a recursive formula. But no analogous formulae are reported in the literature for the general cases. In this paper, utilizing the operational Tau method, we develop an algorithm that allows to generate those canonical polynomials iteratively and explicitly. In addition, we demonstrate the capability of the operational Tau method in treating quadratic optimal control problems governed by ordinary differential equations.     

Upper Bound of the Constant in Strengthened C.B.S. Inequality for Systems of Linear Partial Differential Equations

The constant in the strengthened Cauchy–Bunyakowski–Schwarz (C.B.S.) inequality plays a crucial role in the convergence rate of multilevel iterative methods as well as in the efficiency of a posteriori error estimators, that is the framework of finite element approximations of systems of partial differential equations. We consider an approximation of general systems of linear partial differential equations in R ³. Concerning a multilevel convergence rate corresponding to nested general tetrahedral meshes of size h and 2h, we give an estimate of this constant for general three-dimensional cases.     

Spectral convergence for orthogonal polynomials on triangles

We study the behavior of orthogonal polynomials on triangles and their coefficients in the context of spectral approximations of partial differential equations. In these spectral approximations one studies series expansions $u=\sum _{k=0}^{\infty } \hat{u}_k \phi _k$ where the $\phi _k$ are orthogonal polynomials. Our results show that for any function $u\in C^{\infty }$ the series expansion converges faster than with polynomial order.     

A Note on Euler's Approximations

We prove that Euler's approximations for stochastic differential equations on domains of ^d converge almost surely if the drift satisfies the monotonicity condition and the diffusion coefficient is Lipschitz continuous.     

A note on accurate estimations of the local truncation error of polynomial methods for differential equations

We give sharp error estimations for the local truncation error of polynomial methods for the approximate solution of initial value problems. Our analysis is developed for second order differential equations with polynomial coefficients using the Tau Method as an analytical tool. Our estimates apply to approximations derived with the latter, with collocation and with techniques based on series expansions. An example on collocation is given, to illustrate the use of our estimates.     

Discrete approximations, relaxation, and optimization of one-sided Lipschitzian differential inclusions in Hilbert spaces

We study discrete approximations of nonconvex differential inclusions in Hilbert spaces and dynamic optimization/optimal control problems involving such differential inclusions and their discrete approximations. The underlying feature of the problems under consideration is a modified one-sided Lipschitz condition imposed on the right-hand side (i.e., on the velocity sets) of the differential inclusion, which is a significant improvement of the conventional Lipschitz continuity. Our main attention is paid to establishing efficient conditions that ensure the strong approximation (in the W^1,p-norm as p1) of feasible trajectories for the one-sided Lipschitzian differential inclusions under consideration by those for their discrete approximations and also the strong convergence of optimal solutions to the corresponding dynamic optimization problems under discrete approximations. To proceed with the latter issue, we derive a new extension of the Bogolyubov-type relaxation/density theorem to the case of differential inclusions satisfying the modified one-sided Lipschitzian condition. All the results obtained are new not only in the infinite-dimensional Hilbert space framework but also in finite-dimensional spaces.     

Classification of the centers and their isochronicity for a class of polynomial differential systems of arbitrary degree

In this paper we classify the centers localized at the origin of coordinates, and their isochronicity for the polynomial differential systems in R² of degree d that in complex notation z=x+iy can be written as where j is either 0 or 1. If j=0 then d?5 is an odd integer and n is an even integer satisfying 2?n?(d+1)/2. If j=1 then d?3 is an integer and n is an integer with converse parity with d and satisfying 0<n?[(d+1)/3] where [⋅] denotes the integer part function. Furthermore λ∈R and A,B,C,D∈C. Note that if d=3 and j=0, we are obtaining the generalization of the polynomial differential systems with cubic homogeneous nonlinearities studied in K.E. Malkin (1964) [17], N.I. Vulpe and K.S. Sibirskii (1988) [25], J. Llibre and C. Valls (2009) [15], and if d=2, j=1 and C=0, we are also obtaining as a particular case the quadratic polynomial differential systems studied in N.N. Bautin (1952) [2], H. Zoladek (1994) [26]. So the class of polynomial differential systems here studied is very general having arbitrary degree and containing the two more relevant subclasses in the history of the center problem for polynomial differential equations.     

Numerical approximations for the steady‐state waiting times in a GI/G/1 queue

This paper focuses on easily computable numerical approximations for the distribution and moments of the steadystate waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steadystate idle times and interdeparture times. The approximations presented in this paper are intended to be useful in roughcut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.     

Numerical computation of polynomial zeros by means of Aberth's method

An algorithm for computing polynomial zeros, based on Aberth's method, is presented. The starting approximations are chosen by means of a suitable application of Rouché's theorem. More precisely, an integerq 1 and a set of annuliA _i,i=1,...,q, in the complex plane, are determined together with the numberk _i of zeros of the polynomial contained in each annulusA _i. As starting approximations we choosek _i complex numbers lying on a suitable circle contained in the annulusA _i, fori=1,...,q. The computation of Newton's correction is performed in such a way that overflow situations are removed. A suitable stop condition, based on a rigorous backward rounding error analysis, guarantees that the computed approximations are the exact zeros of a nearby polynomial. This implies the backward stability of our algorithm. We provide a Fortran 77 implementation of the algorithm which is robust against overflow and allows us to deal with polynomials of any degree, not necessarily monic, whose zeros and coefficients are representable as floating point numbers. In all the tests performed with more than 1000 polynomials having degrees from 10 up to 25,600 and randomly generated coefficients, the Fortran 77 implementation of our algorithm computed approximations to all the zeros within the relative precision allowed by the classical conditioning theorems with 11.1 average iterations. In the worst case the number of iterations needed has been at most 17. Comparisons with available public domain software and with the algorithm PA16AD of Harwell are performed and show the effectiveness of our approach. A multiprecision implementation in MATHEMATICA is presented together with the results of the numerical tests performed.Work performed under the support of the ESPRIT BRA project 6846 POSSO (POlynomial System SOlving).     

Constrained near-minimax approximation by weighted expansion and interpolation using Chebyshev polynomials of the second,third, and fourth kinds

Well known results on near-minimax approximation using Chebyshev polynomials of the first kind are here extended to Chebyshev polynomials of the second, third, and fourth kinds. Specifically, polynomial approximations of degreen weighted by (1–x ²)^1/2, (1+x)^1/2 or (1–x)^1/2 are obtained as partial sums of weighted expansions in Chebyshev polynomials of the second, third, or fourth kinds, respectively, to a functionf continuous on [–1, 1] and constrained to vanish, respectively, at ±1, –1 or +1. In each case a formula for the norm of the resulting projection is determined and shown to be asymptotic to 4^–2logn +A +o(1), and this provides in each case and explicit bound on the relative closeness of a minimax approximation. The constantA that occurs for the second kind polynomial is markedly smaller, by about 0.27, than that for the third and fourth kind, while the latterA is identical to that for the first kind, where the projection norm is the classical Lebesgue constant _n . The results on the third and fourth kind polynomials are shown to relate very closely to previous work of P.V. Galkin and of L. Brutman.Analogous approximations are also obtained by interpolation at zeros of second, third, or fourth kind polynomials of degreen+1, and the norms of resulting projections are obtained explicitly. These are all observed to be asymptotic to 2^–1logn +B +o(1), and so near-minimax approximations are again obtained. The norms for first, third, and fourth kind projections appear to be converging to each other. However, for the second kind projection, we prove that the constantB is smaller by a quantity asymptotic to 2^–1log2, based on a conjecture about the point of attainment of the supremum defining the projection norm, and we demonstrate that the projection itself is remarkably close to a minimal (weighted) interpolation projection.All four kinds of Chebyshev polynomials possess a weighted minimax property, and, in consequence, all the eight approximations discussed here coincide with minimax approximations when the functionf is a suitably weighted polynomial of degreen+1.     

Magnus integrators for solving linear-quadratic differential games

We consider Magnus integrators to solve linear-quadratic N$N$-player differential games. These problems require to solve, backward in time, non-autonomous matrix Riccati differential equations which are coupled with the linear differential equations for the dynamic state of the game, to be integrated forward in time. We analyze different Magnus integrators which can provide either analytical or numerical approximations to the equations. They can be considered as time-averaging methods and frequently are used as exponential integrators. We show that they preserve some of the most relevant qualitative properties of the solution for the matrix Riccati differential equations as well as for the remaining equations. The analytical approximations allow us to study the problem in terms of the parameters involved. Some numerical examples are also considered which show that exponential methods are, in general, superior to standard methods.     

The weighting subspaces of the Tau Method and orthogonal collocation

In this paper we characterise the weighting subspaces associated with two approximation techniques for solving ordinary differential equations: the Tau Method [E.L. Ortiz, The Tau Method, SIAM J. Numer. Anal. 6 (1969) 480-92] and the orthogonal collocation method. We show that approximations constructed by means of these two methods are always expressible in terms of a prescribed orthogonal polynomials basis, by projection on a suitably chosen finite dimensional weighting subspace. We show, in particular, that collocation is a special Tau Method with a twisted basis.     

Polynomial approximations in the complex plane

Good polynomial approximations for analytic functions are potentially useful but are in short supply. A new approach introduced here involves the Lanczos τ-method, with perturbations proportional to Faber or Chebyshev polynomials for specific regions of the complex plane. The results show that suitable forms of the τ-method, which are easy to use, can produce near-minimax polynomial approximations for functions which satisfy linear differential equations with polynomial coefficients. In particular, some accurate approximations of low degree for Bessel functions are presented. An appendix describes a simple algorithm which generates polynomial approximations for the Bessel function J_ν(z) of any given order ν.     

On coefficients of polynomials over finite fields

In this paper we study the relation between coefficients of a polynomial over finite field Fq and the moved elements by the mapping that induces the polynomial. The relation is established by a special system of linear equations. Using this relation we give the lower bound on the number of nonzero coefficients of polynomial that depends on the number m of moved elements. Moreover we show that there exist permutation polynomials of special form that achieve this bound when m|q−1. In the other direction, we show that if the number of moved elements is small then there is an recurrence relation among these coefficients. Using these recurrence relations, we improve the lower bound of nonzero coefficients when m?q−1 and . As a byproduct, we show that the moved elements must satisfy certain polynomial equations if the mapping induces a polynomial such that there are only two nonzero coefficients out of 2m consecutive coefficients. Finally we provide an algorithm to compute the coefficients of the polynomial induced by a given mapping with O(q3/2) operations.     

The Buchstab’s function and the operational Tau Method

In this article we discuss some aspects of operational Tau Method on delay differential equations and then we apply this method on the differential delay equation defined byw(u) = 1/u for 1 ≤u ≤ 2 and(uw(u))′ = w(u-1) foru ≥ 2, which was introduced by Buchstab. As Khajah et al.[l] applied the Recursive Tau Method on this problem, they had to apply that Method under theMathematica software to get reasonable accuracy. We present very good results obtained just by applying the Operational Tau Method using a Fortran code. The results show that we can obtain as much accuracy as is allowed by the Fortran compiler and the machine-limitations. The easy applications and reported results concerning the Operational Tau are again confirming the numerical capabilities of this Method to handle problems in different applications.     

Modified linear multistep methods for a class of stiff ordinary differential equations

Implicit and explicit Adams-like multistep formulas are derived for equations of the typeP(d/dt)y=f(t,y) whereP is a polynomial with constant coefficients and where f/y is considered small compared with the roots ofP. Such equations appear for instance in control theory. An analysis of the local truncation error is performed and some examples are discussed where a considerable gain of computation time is obtained compared with classical methods. Finally some extensions of this method are mentioned in order to treat more general systems of differential equations.This research was supported in part by the Swedish National Council for Scientific Research and the Research Institute of the Swedish National Defence.     

Semidefinite representations for finite varieties

We consider the problem of minimizing a polynomial over a set defined by polynomial equations and inequalities. When the polynomial equations have a finite set of complex solutions, we can reformulate this problem as a semidefinite programming problem. Our semidefinite representation involves combinatorial moment matrices, which are matrices indexed by a basis of the quotient vector space ℝ[x ₁, . . . ,x _n ]/I, where I is the ideal generated by the polynomial equations in the problem. Moreover, we prove the finite convergence of a hierarchy of semidefinite relaxations introduced by Lasserre. Semidefinite approximations can be constructed by considering truncated combinatorial moment matrices; rank conditions are given (in a grid case) that ensure that the approximation solves the original problem to optimality. Supported by the Netherlands Organisation for Scientific Research grant NWO 639.032.203.     

Minimum relative error approximations for 1/t

Summary We give explicit solutions to the problem of minimizing the relative error for polynomial approximations to 1/t on arbitrary finite subintervals of (0, ). We give a simple algorithm, using synthetic division, for computing practical representations of the best approximating polynomials. The resulting polynomials also minimize the absolute error in a related functional equation. We show that, for any continuous function with no zeros on the interval of interest, the geometric convergence rates for best absolute error and best relative error approximants must be equal. The approximation polynomials for 1/t are useful for finding suitably precise initial approximations in iterative methods for computing reciprocals on computers.