A Note on the Spectral Collocation Approximation of Some Differential Equations with Singular Source Terms

The solution of differential equations with singular source terms contains the local jump discontinuity in general and its spectral approximation is oscillatory due to the Gibbs phenomenon. To minimize the Gibbs oscillations near the local jump discontinuity and improve convergence, the regularization of the approximation is needed. In this note, a simple derivative of the discrete Heaviside function H _c (x) on the collocation points is used for the approximation of singular source terms δ(x−c) or δ ⁽ⁿ⁾(x−c) without any regularization. The direct projection of H _c (x) yields highly oscillatory approximations of δ(x−c) and δ ⁽ⁿ⁾(x−c). In this note, however, it is shown that the direct projection approach can yield a non-oscillatory approximation of the solution and the error can also decay uniformly for certain types of differential equations. For some differential equations, spectral accuracy is also recovered. This method is limited to certain types of equations but can be applied when the given equation has some nice properties. Numerical examples for elliptic and hyperbolic equations are provided. The current address: Department of Mathematics, State University of New York at Buffalo, Buffalo, NY 14260-2900, USA.     

The discrete collocation method for weakly singular Urysohn equations

In this paper, we analyse the iterated collocation method for the nonlinear Urysohn operator equation x=y+K(x) with K a singular kernel. The paper extends the study [H. Kaneko, R.D. Noren, and P.A. Padilla, J. Comput. Appl. Math. 80 (1997), pp. 335–349] in which the convergence of the iterated collocation method for Urysohn equations is considered.     

A recursive formulation of collocation in terms of canonical polynomials

In this paper we discuss two related but analytically different techniques: the collocation method and Ortiz's recursive formulation of the Tau Method. Specifically, we show that it is possible to simulate with the Tau Method collocation approximants for any desired degree. We give a representation for collocation approximants in terms ofshifted canonical polynomials, which are introduced here. We show that in the linear case computing a collocation approximant of orderN by this new approach requiresO(N) arithmetic operations while obtaining the same approximant by the direct approach involvesO(N ³). Furthermore, our technique leads to a recursive formulation of collocation. We discuss separately the linear and nonlinear cases and propose a more efficienteconomized approach for the latter.     

An extension of Christopher's method†

A proposal is made to extend the method of Christopher (1973). which gives an accurate approximation to equations of the form

$

to equations of the form

where f(x) is cither a polynomial of the form

$

or can be approximated by such a polynomial.

The approach suggested is the approximation of f(x) by the cubic, c ₁ x + c ₃ x ³, in a Chebychev sense. Having thus obtained the coefficients c ₁, and c ₃, Christopher's method can then be applied to the resulting approximate equation.     

Perturbed Chebyshev rational approximation

In this work, we give a perturbed Chebyshev rational approximation for a function f (x) which has a Chebyshev expansion. This approximation contains a perturbation parameter ~ which is calculated so that the perturbed Chebyshev rational approximation agrees with the Chebyshev expansion to a certain number of terms. Also, we introduce a perturbed Chebyshev rational approximation for the definite integral of a function f (x) having Chebyshev expansion and show that this method can be used iteratively to approximate the multiple integral of the considered function. The method has been applied to approximate some functions and their definite integrals.     

An extended collocation method

Given an approximate solutionx _n of a linear operator equation obtained by a collocation method, an improved solutionx ^* _n+m is obtained fromx _n by an «extended collocation method» which consists in solving a further (m)-order linear system instead of an (n+m)-order one, diminishing the effects of rounding error in carrying out the calculations. For a suitable choice of the knot, the method may be recursively performed both by spline approximation and by algebraic and trigonometric polynomial approximation. A numerical example with a two point boundary value problem confirms the advantages of the extended method with respect to the direct one.     

Coefficients perturbation methods for higher-order differential equations

In this paper, we develop a general approach for estimating and bounding the error committed when higher-order ordinary differential equations (ODEs) are approximated by means of the coefficients perturbation methods. This class of methods was specially devised for the solution of Schrödinger equation by Ixaru in 1984. The basic principle of perturbation methods is to find the exact solution of an approximation problem obtained from the original one by perturbing the coefficients of the ODE, as well as any supplementary condition associated to it. Recently, the first author obtained practical formulae for calculating tight error bounds for the perturbation methods when this technique is applied to second-order ODEs. This paper extends those results to the case of differential equations of arbitrary order, subjected to some specified initial or boundary conditions. The results of this paper apply to any perturbation-based numerical technique such as the segmented Tau method, piecewise collocation, Constant and Linear perturbation. We will focus on the Tau method and present numerical examples that illustrate the accuracy of our results.     

Parametric quintic spline solution of third-order boundary value problems

In this paper, we develop parametric quintic spline function to approximate the solution of third-order boundary value problems of the form u″′=f(x, u), a≤x≤b, subject to the boundary conditions u(a)=k ₁, u′(a)=k ₂ and u(b)=k ₃. The class of methods are second-, fourth- and sixth-order accurate. End equations of the splines are derived and truncation error is given. Three numerical examples are presented to illustrate the practical use of our methods as well as their accuracies when compared with some existing spline function methods. It is shown that the new methods give approximations, which are better than those produced by other methods.     

The iterated defect correction methods for singular two-point boundary value problems

In this paper, the iterated defect correction (IDeC) techniques based on the centered Euler method for the equivalent first order system of the singular two-point boundary value problem in linear case (x ^α y′(x))′ = f(x), y(0) = a,y(1) = b, where 0 < α < 1 are considered. By using the asymptotic expansion of the global error, it is analyzed that the IDeC methods improved the approximate results by means of IDeC steps and the degree of the interpolating polynomials used. Some numerical examples from the literature are given in illustration of this theory.     

Lanczos <Emphasis Type="Italic">τ</Emphasis>-method regularization algorithm and its algebraic-programming implementation

An algebraic algorithm is developed for computing an algebraic polynomial y _n of order n ∈ N in computer algebra systems. This polynomial is the optimal approximation of the solution y = y(x), x ∈ [a,b], to a system of linear differential equations with polynomial coefficients and initial conditions at a regular singular zero point of this equation in a space C_{[ a,b ]}^k C_{\left[ {a,b} \right]}^k .     

A novel numerical method for a class of problems with the transition layer and Burgers’ equation

A numerical method for solving a class of quasi-linear singular two-point boundary value problems with a transition layer is presented in this paper. For the problem ? u _xx +a(u+f(x))u _x +b(x, u)=0, we develop a multiple scales method. First, this method solves the location of the transition layer, then it approximates the singular problem with reduced problems in the non-layer domain and pluses a layer corrected problem which nearly has an effect in the layer domain. Both problems are transformed into first-order problems which can be solved easily. For the problem ? u _xx +b(x, u)=0, we establish a similar method which approximate the problem with reduced problems and a two-point boundary value problem. Unsteady problems are also considered in our paper. We extend our method to solve Burgers’ equation problems by catching the transition layer with the formula of shock wave velocity and approximating it by a similar process.     

A least distance algorithm for a smooth strictly convex norm

An algorithm for approximating a non negative solution of inconsistent systems of linear equations is presented. We define a best approximate solution of a system Ax = b x≥0 to be the vector x≥0 which minimizes the norm of the residual r(x) = b ? Ax, for a smooth and strictly convex norm. The algorithm is shown to be feasible and globally convergent. The special case of the ? ^p norm is included. In particular, the method converges for 1 < p < 2. A generalization of this algorithm is also given. Numerical results are included.     

A Nonoverlapping Domain Decomposition Method for Legendre Spectral Collocation Problems

We consider the Dirichlet boundary value problem for Poisson’s equation in an L-shaped region or a rectangle with a cross-point. In both cases, we approximate the Dirichlet problem using Legendre spectral collocation, that is, polynomial collocation at the Legendre–Gauss nodes. The L-shaped region is partitioned into three nonoverlapping rectangular subregions with two interfaces and the rectangle with the cross-point is partitioned into four rectangular subregions with four interfaces. In each rectangular subregion, the approximate solution is a polynomial tensor product that satisfies Poisson’s equation at the collocation points. The approximate solution is continuous on the entire domain and its normal derivatives are continuous at the collocation points on the interfaces, but continuity of the normal derivatives across the interfaces is not guaranteed. At the cross point, we require continuity of the normal derivative in the vertical direction. The solution of the collocation problem is first reduced to finding the approximate solution on the interfaces. The discrete Steklov–Poincaré operator corresponding to the interfaces is self-adjoint and positive definite with respect to the discrete inner product associated with the collocation points on the interfaces. The approximate solution on the interfaces is computed using the preconditioned conjugate gradient method. A preconditioner is obtained from the discrete Steklov–Poincaré operators corresponding to pairs of the adjacent rectangular subregions. Once the solution of the discrete Steklov–Poincaré equation is obtained, the collocation solution in each rectangular subregion is computed using a matrix decomposition method. The total cost of the algorithm is O(N ³), where the number of unknowns is proportional to N ².      

Sextic C 1-spline collocation methods for solving delay differential equations

In this paper, we propose a global collocation method for the numerical solution of the delay differential equations (DDEs). The method presented is based on sextic C ¹-splines s(x) as an approximation to the exact solution y(x) of the DDEs. Convergence results shows that the error bounds ‖ s ^j ?y ^j ‖=O(h ⁶), j=0, 1, in the uniform norm. Moreover, the stability analysis properties of these methods have been studied. Numerical experiments will also be considered.     

Non-approximability of just-in-time scheduling

We consider the following single machine just-in-time scheduling problem with earliness and tardiness costs: Given n jobs with processing times, due dates and job weights, the task is to schedule these jobs without preemption on a single machine such that the total weighted discrepancy from the given due dates is minimum. NP-hardness of this problem is well established, but no approximation results are known. Using the gap-technique, we show in this paper that the weighted earliness–tardiness scheduling problem and several variants are extremely hard to approximate: If n denotes the number of jobs and b∈ℕ is any given constant, then no polynomial-time algorithm can achieve an approximation which is guaranteed to be at most a factor of O(b ⁿ ) worse than the optimal solution unless P = NP.     

New explicit filters and smoothers for diffusions with nonlinear drift and measurements

The optimal least-squares filtering of a diffusion x(t) from its noisy measurements {y(τ); 0 τ t} is given by the conditional mean E[x(t)|y(τ); 0 τ t]. When x(t) satisfies the stochastic diffusion equation dx(t) = f(x(t)) dt + dw(t) and y(t) = ∫₀^tx(s) ds + b(t), where f(·) is a global solution of the Riccati equation /xf(x) + f(x)² = f(x)² = αx² + βx + γ, for some , and w(·), b(·) are independent Brownian motions, Benes gave an explicit formula for computing the conditional mean. This paper extends Benes results to measurements y(t) = ∫₀^tx(s) ds + ∫₀^t dx(s) + b(t) (and its multidimensional version) without imposing additional conditions on f(·). Analogous results are also derived for the optimal least-squares smoothed estimate E[x(s)|y(τ); 0 τ t], s < t. The methodology relies on Girsanov's measure transformations, gauge transformations, function space integrations, Lie algebras, and the Duncan-Mortensen-Zakai equation.     

A Bessel polynomial approach for solving general linear Fredholm integro-differential–difference equations

In this paper, to find an approximate solution of general linear Fredholm integro-differential–difference equations (FIDDEs) under the initial-boundary conditions in terms of the Bessel polynomials, a practical matrix method is presented. The idea behind the method is that it converts FIDDEs to a matrix equation which corresponds to a system of linear algebraic equations and is based on the matrix forms of the Bessel polynomials and their derivatives by means of collocation points. The solutions are obtained as the truncated Bessel series in terms of the Bessel polynomials J _n (x) of the first kind defined in the interval [0, ∞). The error analysis and the numerical examples are included to demonstrate the validity and applicability of the technique.     

Iterative Methods for Linear Complementarity Problems with Interval Data

A ] and an interval vector [b]. If all A∈[A] are H-matrices with positive diagonal elements, these methods are all convergent to the same interval vector [x ^*]. This interval vector includes the solution x of the linear complementarity problem defined by any fixed A∈[A] and any fixed b∈[b]. If all A∈[A] are M-matrices, then we will show, that [x ^*] is optimal in a precisely defined sense. We also consider modifications of those methods, which under certain assumptions on the starting vector deliver nested sequences converging to [x ^*]. We close our paper with some examples which illustrate our theoretical results. Received October 7, 2002; revised April 15, 2003 Published online: June 23, 2003 RID="*" ID="*" Dedicated to U. Kulisch on the occasion of his 70th birthday. We are grateful to the referee who has given a series of valuable comments.     

Scaled runge-kutta-nyström methods for the second order differential equation ÿ = f(x,y)

New Runge-Kutta-Nyström algorithms are presented which determine an approximation of the solution and its derivative of the second order differential equation ÿ = f(x,y) at intermediate points of a given integration step, as well as at the end of each step. These new algorithms, called scaled Runge-Kutta-Nyström (SRKN) methods, are designed to be used with existing Runge-Kutta-Nyström (RKN) formulas, using the function evaluations of these methods as the core of the new system. Thus, for a slight increase of the cost, the solution may be generated within a successful step, improving so the efficiency of the existing RKN methods.     

Exponentially weighted Legendre-Gauss Tau methods for linear second-order differential equations

We develop a method to solve a class of second-order ordinary differential equations with highly oscillatory solutions. The method consists in combining three different techniques: Legendre-Gauss spectral Tau method, exponential fitting, and coefficient perturbation methods. With our approach, the resulting approximate solutions are expressed in terms of an exponentially weighted Legendre polynomial basis {e^ω_nxL_n(x);n≥0}, where ω_n are appropriately chosen complex numbers. The accuracy and efficiency of the method are discussed and illustrated numerically.