A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

On the numerical solutions for the fractional diffusion equation

Fractional differential equations have recently been applied in various area of engineering, science, finance, applied mathematics, bio-engineering and others. However, many researchers remain unaware of this field. In this paper, an efficient numerical method for solving the fractional diffusion equation (FDE) is considered. The fractional derivative is described in the Caputo sense. The method is based upon Chebyshev approximations. The properties of Chebyshev polynomials are utilized to reduce FDE to a system of ordinary differential equations, which solved by the finite difference method. Numerical simulation of FDE is presented and the results are compared with the exact solution and other methods.     

A deficient spline function approximation to systems of first order differential equations

The stability of the vector-valued spline function approximations S(x) of degree m deficiency 3, i.e., S∈C^m?3, to systems of first order differential equations are investigated. The method will be shown to be A-stable for m=4, unstable and hence divergent for m?6. The method is stable form=5.     

Error-free computer solution of certain systems of linear equations

In this article we propose a procedure which generates the exact solution for the system Ax = b, where A is an integral nonsingular matrix and b is an integral vector, by improving the initial floating-point approximation to the solution. This procedure, based on an easily programmed method proposed by Aberth [1], first computes the approximate floating-point solution x^* by using an available linear equation solving algorithm. Then it extracts the exact solution x from x^* if the error in the approximation x^* is sufficiently small. An a posteriori upper bound for the error of x^* is derived when Gaussian Elimination with partial pivoting is used. Also, a computable upper bound for |det(A)|, which is an alternative to using Hadamard's inequality, is obtained as a byproduct of the Gaussian Elimination process.     

On the asymptotic convergence factor of the total step method in interval computation

For a special class of n×n interval matrices A we derive a necessary and sufficient condition for the asymptotic convergence factor α of the total step method x^(m+1)=Ax^(m)+b to be less than the spectral radius ϱ(|A|) of the absolute value |A| of A.     

Roundoff-error analysis of a new class of conjugate-gradient algorithms

We perform the rounding-error analysis of the conjugate-gradient algorithms for the solution of a large system of linear equations Ax=b where Ais an hermitian and positive definite matrix. We propose a new class of conjugate-gradient algorithms and prove that in the spectral norm the relative error of the computed sequence {x_k} (in floating-point arithmetic) depends at worst on ζк^{$\text{3}\text{2}$}, where ζ is the relative computer precision and к is the condition number of A. We show that the residual vectors r_k=Ax_k-b are at worst of order ζк?vA?v ?vx_k?v. We p oint out that with iterative refinement these algorithms are numerically stable. If ζк ² is at most of order unity, then they are also well behaved.     

A family of implicit Chebyshev methods for the numerical integration of second-order differential equations

A family of implicit methods based on intra-step Chebyshev interpolation is developed for the solution of initial-value problems whose differential equations are of the special second-order form y″ = f(y(x); x). The general procedure allows stepsizes which are considerably larger than commonly used in conventional methods. Computation overhead is comparable to that required by high-order single or multistep procedures. In addition, the iterative nature of the method substantially reduces local errors while maintaining a low rate of global error growth.     

A deficient spline function approximation to systems of first-order differential equations: part 2

The problem of stability was discussed in part 1 of this paper (Appl. Math. Modelling 1983, 7, 380). This part looks at the convergence of the spline approximation of deficiency 3 to systems of first-order differential equations. Convergence is shown for m = 4 and 5. In addition, global error bounds of the form: ∥S⁽ⁱ⁾(x) ? y⁽ⁱ⁾(x)∥∞ = 0(h^m+1?i), i = 0(1)m are presented, together with a computational example which illustrates the convergence of the proposed method.     

On the Rate of Multivariate Poisson Convergence

The distribution of the sum of independent nonidentically distributed Bernoulli random vectors inR^kis approximated by a multivariate Poisson distribution. By using a multivariate adaption of Kerstan's (1964,Z. Wahrsch. verw. Gebiete2, 173–179) method, we prove a conjecture of Barbour (1988,J. Appl. Probab.25A, 175–184) on removing a log-term in the upper bound of the total variation distance. Second-order approximations are included.     

Some inverse problems involving conditional expectations

Let (Ω, F, P) be a probability space, let H be a sub-σ-algebra of F, and let Y be positive and H-measurable with E[Y] = 1. We discuss the structure of the convex set CE(Y; H) = {X ∈ pF: Y = E[X|H]} of random variables whose conditional expectation given H is the prescribed Y. Several characterizations of extreme points of CE(Y; H) are obtained. A necessary and sufficient condition is given in order that CE(Y; H) be the closed, convex hull of its extreme points. For the case of finite F we explicitly calculate the extreme points of CE(Y; H), identify pairs of adjacent extreme points, and characterize extreme points of CE(Y; H) ? CE(Z; G), where G is a second sub-σ-algebra of F and Z ∈ pG. When H = σ(Y) and appropriate topological hypotheses hold, extreme points of CE(Y; H) are shown to be in explicit one-to-one correspondence with certain left inverses of Y. Finally, it is shown how the same approach can be applied to the problem of extremal random measures on $\text{R}$₊ with a prescribed compensator, to deduce that the number of extreme points is zero or one.     

Local times for stochastic processes which are subordinate to Gaussian processes

Let X and Y be random vectors of the same dimension such that Y has a normal distribution with mean vector O and covariance matrix R. Let g(x), x≥0, be a bounded nonincreasing function. X is said to be g-subordinate to Y if |Ee^iu′X| ≤ g(u′Ru) for all real vectors u of the same dimension as X. This is used to define the g-subordination of a real stochastic process X(t), 0 ≤ t ≤ 1, to a Gaussian process Y(t), 0 ≤ t ≤ 1. It is shown that the basic local time properties of a given Gaussian process are shared by all the processes that age g-subordinate to it. It is shown in particular that certain random series, including some random Fourier series, are g-subordinate to Gaussian processes, and so have their local time properties.     

A remark on the transformation formula of theta functions associated to positive definite quadratic forms

Let L be a positive Z-lattice with level N = cd, (c, d) = 1. Then the Fourier expansion at cusp $\text{1}\text{d}$ of the theta function associated to L is a theta function associated to L₁, where a lattice L₁ is defined by Z_pL₁ = Z_pL for $\text{p?c}$, Z_pL₁ = the dual of Z_pL for p | c.     

Deformations of plane graphs

It is proven that, if Γ₀ and Γ₁ are isomorphic strictly convex graphs such that their outer polygons correspond to each other and have the same orientations, then Γ₀ can be continuously deformed into Γ₁ such that, at each stage, the graph under consideration is convex. This extends a result of Cairns (Ann of Math.45 (2) (1944), 207–217; Amer. Math. Monthly51 (1944), 247–252) and proves a conjecture of Grünbaum and Shepard (“Proceedings, 8th British Combinatorial Conf.”, 1981). This result is applied to prove an analogous conjecture by Grünbaum and Shepard on deformations of straight graphs in general and it is shown how the proof method also can be used to verify a conjecture of Robinson (“Proceedings, 8th British Combinatorial Conf.”, 1981) on deformations of rectanguloid curves.     

On the existence of free topological groups

Given a Tychonoff space X and classes U and V of topological groups, we say that a topological group G = G(X, U, V) is a free (U,V)-group over X if (a) X is a subspace of G, (b) G ϵ U, and (c) every continuous f: X → H with H ϵ V extends uniquely to a continuous homomorphism f̄: G→H. For certain classes U and V, we consider the question of the existence of free (U,V)- groups. Our principal results are the following. Let PA and CA denote, respectively, the class ofpseudocompact Abelian groups and the class of compact Abelian groups. Then

• 1.(a) there is a free (PA,PA)-group over X iff; X=Ø and
• 2.(b) there is for each X a free (PA,CA)-group over X in which X is closed.

     

Quadratic mappings of spheres

In this paper we obtain a basis-free method for determining the general form of quadratic maps over R between spheres. We show that all quadratic maps (over certain R-lattices) between spheres are Hopf maps, and that the classical Hopf fibrations, S^2m?1→S^m, for m=2, 4, 8, are the unique nontrivial maps over Z, up to action by the orthogonal group.     

The iterative instrumental variables method and the full information maximum likelihood method for estimating interdependent systems

The “iterative instrumental variables” (IIV) method for estimating interdependent systems, originally referred to as a symmetric counterpart to the “fix-point” (FP) method, shares its symmetry properties with Durbin's iterative method for performing the “full information maximum likelihood” (FIML) estimation. Classical interdependent systems are considered and identities may occur among the structural equations. Alternative symmetric procedures for obtaining FIML estimates are also dealt with, including the sequential maximization of the likelihood function with respect to the coefficients of one structural equation at a time.Two recent estimation methods developed by Brundy and Jorgenson (1971, Review of Economics and Statistics53, 207–224) as well as Dhrymes (1971, Austral. J. Statist.13, 168–175) can be considered the second approximation of the IIV method and Durbin's method respectively with the first approximation obtained by the “ordinary instrumental variables” (OIV) method. In practice the second approximation depends heavily on the choice of initial instrumental variables, although the asymptotic distribution is not changed by the continued iteration.     

A topological property enjoyed by near points but not by large points

Let H denote the halfline [0,∞). A point p?βH?H is called a near point if p is in the closure of some countable discrete closed subspace of H. In addition, a point p?βH?H is called a large point if p is not in the closure of a closed subset of H of finite Lebesgue measure. We will show that for every autohomeomorphism ? of βH?H and for each near point p we have that ?(p) is not large. In addition, we establish, under CH, the existence of a point x?βH?H such that for each autohomeomorphism ? of βH?H the point ?(x) is neither large nor near.     

Matching relations and the dimensional structure of social choices

The concept of a matching relation M generalizes that of an equivalence, in a case in which the domain and range of M are not necessarily identical and may be disjoint. This paper analyzes the representation of any relation R by a union of matching relations. The interpretation of such representation is that a R d — the choice of some individual or object d by some individual a requires the coincidence of at least one value of the chosen and the chooser on some relevant factor. A general discussion of matching relations is given, and various results concerning the representation are presented.     

Matching and multiscale expansions for a model singular perturbation problem

We consider the Laplace–Dirichlet equation in a polygonal domain which is perturbed at the scale ε near one of its vertices. We assume that this perturbation is self-similar, that is, derives from the same pattern for all values of ε. On the base of this model problem, we compare two different approaches: the method of matched asymptotic expansions and the method of multiscale expansion. We enlighten the specificities of both techniques, and show how to switch from one expansion to the other. To cite this article: S. Tordeux et al., C. R. Acad. Sci. Paris, Ser. I 343 (2006).