On numerical differentiation

In a recent paper Ström analyzed a simple extrapolation algorithm for numerical differentiation and derived certain properties about the kernel function of the integral representation of the remainder term. These properties are useful for placing bounds on the error in cases when specified higher order derivatives are known not to change sign. The algorithm involves a separate Romberg table for each derivative and is rather inconvenient from the point of view of economizing the number of function values required. In this paper we generalize Ström's results in two stages. First we show that they are valid for a very wide choice of definitions of the initial column of each Romberg table. Then we show that one such choice, making full use of the computed function values, gives results identical to those that can be obtained using an algorithm suggested by Lyness and Moler with a particular choice of sequence of function evaluations. There is no detailed discussion of the effect of round-off error.     

一种求解弹性l_2-l_q正则化问题的算法

给出了一种求解弹性l_{2}-l_{q}正则化问题的迭代重新加权l_{1}极小化算法, 并证明了由该算法产生的迭代序列是有界且渐进正则的. 对于任何有理数q\in(0,1), 基于一个代数的方法, 进一步证明了迭代重新加权l_{1}极小化算法收敛到弹性l_{2}-l_{q}(0相似文献   

On forming the Romberg table

Romberg-type extrapolation is commonly used in many areas of numerical computation. An algorithm is presented for forming the Romberg table for general step-length sequence and general powers in the asymptotic expansion. It is then shown that parameters of the algorithm can be used to gain an a priori bound on propagation of rounding errors in the table.     

An Algorithm for Computing a Gröbner Basis of a Polynomial Ideal over a Ring with Zero Divisors

An algorithm for computing a Gr?bner basis of an ideal of polynomials whose coefficients are taken from a ring with zero divisors, is presented; such rings include \mathbb Z_n\mathbb {Z}_n and \mathbb Z_n[i]\mathbb {Z}_n[i], where n is not a prime number. The algorithm is patterned after (1) Buchberger’s algorithm for computing a Gr?bner basis of a polynomial ideal whose coefficients are from a field and (2) its extension developed by Kandri-Rody and Kapur when the coefficients appearing in the polynomials are from a Euclidean domain. The algorithm works as Buchberger’s algorithm when a polynomial ideal is over a field and as Kandri-Rody–Kapur’s algorithm when a polynomial ideal is over a Euclidean domain. The proposed algorithm and the related technical development are quite different from a general framework of reduction rings proposed by Buchberger in 1984 and generalized later by Stifter to handle reduction rings with zero divisors. These different approaches are contrasted along with the obvious approach where for instance, in the case of \mathbb Z_n{\mathbb {Z}}_n, the algorithm for polynomial ideals over \mathbb Z{\mathbb {Z}} could be used by augmenting the original ideal presented by polynomials over \mathbb Z_n{\mathbb {Z}}_n with n (similarly, in the case of \mathbb Z_n[i]{\mathbb {Z}}_n[i], the original ideal is augmented with n and i² + 1).     

An O（rL） Infeasible Interior-point Algorithm for Symmetric Cone LCP via CHKS Function

In this paper, we propose a theoretical framework of an infeasible interior-point algorithm for solving monotone linear cornplementarity problems over symmetric cones （SCLCP）. The new algorithm gets Newton-like directions from the Chen-Harker-Kanzow-Smale （CHKS） smoothing equation of the SCLCP. It possesses the following features： The starting point is easily chosen; one approximate Newton step is computed and accepted at each iteration; the iterative point with unit stepsize automatically remains in the neighborhood of central path; the iterative sequence is bounded and possesses （9（rL） polynomial-time complexity under the monotonicity and solvability of the SCLCP.     

The Dual Kaczmarz Algorithm

The Kaczmarz algorithm is an iterative method for solving a system of linear equations. It can be extended so as to reconstruct a vector \(x\) in a (separable) Hilbert space from the inner-products \(\{\langle x, \phi _{n} \rangle \}\). The Kaczmarz algorithm defines a sequence of approximations from the sequence \(\{\langle x, \phi _{n} \rangle \}\); these approximations only converge to \(x\) when \(\{\phi _{n}\}\) is effective. We dualize the Kaczmarz algorithm so that \(x\) can be obtained from \(\{\langle x, \phi _{n} \rangle \}\) by using a second sequence \(\{\psi _{n}\}\) in the reconstruction. This allows for the recovery of \(x\) even when the sequence \(\{\phi _{n}\}\) is not effective; in particular, our dualization yields a reconstruction when the sequence \(\{\phi _{n}\}\) is almost effective. We also obtain some partial results characterizing when the sequence of approximations from \(\{\langle x, \phi _{n} \rangle \}\) using \(\{\psi _{n}\}\) converges to \(x\), in which case \(\{(\phi _{n}, \psi _{n})\}\) is called an effective pair.

     

Bases de type schauder deC[0,1] et formules de quadrature associées

Résumé On caractérise deux familles de bases deC[0,1] et l'on étudie les formules de quadrature associées. On montre en particulier que les formules de quadrature de Romberg proviennent d'une suite de bases engendrées par des polynômes.

---

Bases of schauder type inC[0, 1] and associated quadrature formulas

Summary We characterize two families of bases ofC[0,1] and we study the associated quadrature formulae. In particular, we prove that the Romberg quadrature formulae come from a sequence of bases generated by polynomials.

     

On a bipartition problem of Bollobás and Scott

The bipartite density of a graph G is max {|E(H)|/|E(G)|: H is a bipartite subgraph of G}. It is NP-hard to determine the bipartite density of any triangle-free cubic graph. A biased maximum bipartite subgraph of a graph G is a bipartite subgraph of G with the maximum number of edges such that one of its partite sets is independent in G. Let $ \mathcal{H} $ \mathcal{H} denote the collection of all connected cubic graphs which have bipartite density $ \tfrac{4} {5} $ \tfrac{4} {5} and contain biased maximum bipartite subgraphs. Bollobás and Scott asked which cubic graphs belong to $ \mathcal{H} $ \mathcal{H} . This same problem was also proposed by Malle in 1982. We show that any graph in $ \mathcal{H} $ \mathcal{H} can be reduced, through a sequence of three types of operations, to a member of a well characterized class. As a consequence, we give an algorithm that decides whether a given graph G belongs to $ \mathcal{H} $ \mathcal{H} . Our algorithm runs in polynomial time, provided that G has a constant number of triangles that are not blocks of G and do not share edges with any other triangles in G.     

Graphs of linear operators

In 2006 the author proposed an algorithm for constructing graphs of difference operators. In this paper, the following question is studied: to which linear operators $ \mathcal{A} In 2006 the author proposed an algorithm for constructing graphs of difference operators. In this paper, the following question is studied: to which linear operators does this algorithm apply? Graphs of difference operators are used to determine the complexity of a sequence in the sense of Arnold, so the algorithm makes it possible to determine the complexity of any sequence. Original Russian Text ? A.I. Garber, 2008, published in Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2008, Vol. 263, pp. 64–71.     

Tight upper bounds for semi-online scheduling on two uniform machines with known optimum

We consider a semi-online version of the problem of scheduling a sequence of jobs of different lengths on two uniform machines with given speeds 1 and s. Jobs are revealed one by one (the assignment of a job has to be done before the next job is revealed), and the objective is to minimize the makespan. In the considered variant the optimal offline makespan is known in advance. The most studied question for this online-type problem is to determine the optimal competitive ratio, that is, the worst-case ratio of the solution given by an algorithm in comparison to the optimal offline solution. In this paper, we make a further step towards completing the answer to this question by determining the optimal competitive ratio for s between \(\frac{5 + \sqrt{241}}{12} \approx 1.7103\) and \(\sqrt{3} \approx 1.7321\), one of the intervals that were still open. Namely, we present and analyze a compound algorithm achieving the previously known lower bounds.

     

A variable dimension fixed point algorithm and the orientation of simplices

A variable dimension algorithm with integer labelling is proposed for solving systems ofn equations inn variables. The algorithm is an integer labelling version of the 2-ray algorithm proposed by the author. The orientation of lower dimensional simplices is studied and is shown to be preserved along a sequence of adjacent simplices.     

Modified Dinkelbach-Type Algorithm for Generalized Fractional Programs with Infinitely Many Ratios

In this paper, we extend the Dinkelbach-type algorithm of Crouzeix, Ferland, and Schaible to solve minmax fractional programs with infinitely many ratios. Parallel to the case with finitely many ratios, the task is to solve a sequence of continuous minmax problems,

An approximating algorithm for the solution of an integral equation from epidemics

The following delay integral equation

$ x(t)=\int\limits_{t-\tau}^{t}f(s,x(s))ds,\quad t\in \mathbb{R}, $

has been proposed by Cooke and Kaplan to describe the spread of certain infectious diseases with periodic contact rate that varies seasonally. This mathematical model can also be interpreted as an evolution equation of a single species population. The purpose of this paper is to present an approximating algorithm for the continuous positive solution of this integral equation from the theory of epidemics. This algorithm is obtained by applying the successive approximations method and the rectangle formula, used for the calculation of the approximate value of integrals which appear in the right-hand-side of the terms of the sequence of successive approximations. In order to establish this approximating algorithm, we will suppose that this integral equation has a unique solution. The main result contains also the error of approximation of the solution obtained by applying this approximating algorithm.

     

Error bounds for Romberg quadrature

Denote by the error of a Romberg quadrature rule applied to the function f. We determine approximately the constants in the bounds of the types and for all classical Romberg rules. By a comparison with the corresponding constants of the Gaussian rule we give the statement “The Gaussian quadrature rule is better than the Romberg method” a precise meaning. Received September 10, 1997 / Revised version received February 16, 1998     

Learning finite binary sequences from half‐space data

The problem of inferring a finite binary sequence w *∈{−1, 1}ⁿ is considered. It is supposed that at epochs t=1, 2,…, the learner is provided with random half‐space data in the form of finite binary sequences u ^(t)∈{−1, 1}ⁿ which have positive inner‐product with w *. The goal of the learner is to determine the underlying sequence w * in an efficient, on‐line fashion from the data { u ^(t), t≥1}. In this context, it is shown that the randomized, on‐line directed drift algorithm produces a sequence of hypotheses {w^(t)∈{−1, 1}ⁿ, t≥1} which converges to w * in finite time with probability 1. It is shown that while the algorithm has a minimal space complexity of 2n bits of scratch memory, it has exponential time complexity with an expected mistake bound of order Ω(e^0.139n). Batch incarnations of the algorithm are introduced which allow for massive improvements in running time with a relatively small cost in space (batch size). In particular, using a batch of 𝒪(n log n) examples at each update epoch reduces the expected mistake bound of the (batch) algorithm to 𝒪(n) (in an asynchronous bit update mode) and 𝒪(1) (in a synchronous bit update mode). The problem considered here is related to binary integer programming and to learning in a mathematical model of a neuron. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 345–381 (1999)     

The maximum entropy method on the mean: Applications to linear programming and superresolution

A continuous deformation algorithm is proposed for solving a variational inequality problem on a polytopeK. The algorithm embeds the polytopeK intoK× [0, ) and starts by applying a variable dimension algorithm onK× {0} until an approximate solution is found onK× {0}. Then by tracing the path of solutions of a system of equations the algorithm virtually follows a path of approximate solution inK× [0, ). When the path inK× [0, ) returns to level 0, i.e.,K× {0}, the variable dimension algorithm is again used until a new approximate solution is found onK× {0}. The setK× [0, ) is triangulated so that the approximate solution on the path improves the accuracy as the level increases. A contrivance for a practical implementation of the algorithm is proposed and tested for some test problems.Corresponding author.     

A Variant of the Topkis—Veinott Method for Solving Inequality Constrained Optimization Problems

In this paper we give a variant of the Topkis—Veinott method for solving inequality constrained optimization problems. This method uses a linearly constrained positive semidefinite quadratic problem to generate a feasible descent direction at each iteration. Under mild assumptions, the algorithm is shown to be globally convergent in the sense that every accumulation point of the sequence generated by the algorithm is a Fritz—John point of the problem. We introduce a Fritz—John (FJ) function, an FJ1 strong second-order sufficiency condition (FJ1-SSOSC), and an FJ2 strong second-order sufficiency condition (FJ2-SSOSC), and then show, without any constraint qualification (CQ), that (i) if an FJ point z satisfies the FJ1-SSOSC, then there exists a neighborhood N(z) of z such that, for any FJ point y ∈ N(z) \ {z } , f ₀ (y) ≠ f ₀ (z) , where f ₀ is the objective function of the problem; (ii) if an FJ point z satisfies the FJ2-SSOSC, then z is a strict local minimum of the problem. The result (i) implies that the entire iteration point sequence generated by the method converges to an FJ point. We also show that if the parameters are chosen large enough, a unit step length can be accepted by the proposed algorithm. Accepted 21 September 1998     

The Convergence of a Levenberg–Marquardt Method for Nonlinear Inequalities

In this paper, we consider the least l ₂-norm solution for a possibly inconsistent system of nonlinear inequalities. The objective function of the problem is only first-order continuously differentiable. By introducing a new smoothing function, the problem is approximated by a family of parameterized optimization problems with twice continuously differentiable objective functions. Then a Levenberg–Marquardt algorithm is proposed to solve the parameterized smooth optimization problems. It is proved that the algorithm either terminates finitely at a solution of the original inequality problem or generates an infinite sequence. In the latter case, the infinite sequence converges to a least l ₂-norm solution of the inequality problem. The local quadratic convergence of the algorithm was produced under some conditions.     

Romberg quadrature using the Bulirsch sequence

Summary. In this note, we prove a conjecture of Bulirsch concerning the definiteness of the Romberg quadrature rules using the Bulirsch sequence. We compare these rules with the classical Romberg scheme and the Gaussian rules. Received May 16, 2000 / Published online May 30, 2001     

Improving the accuracy of multiple integral evaluation by applying Romberg’s method

Romberg’s method, which is used to improve the accuracy of one-dimensional integral evaluation, is extended to multiple integrals if they are evaluated using the product of composite quadrature formulas. Under certain conditions, the coefficients of the Romberg formula are independent of the integral’s multiplicity, which makes it possible to use a simple evaluation algorithm developed for one-dimensional integrals. As examples, integrals of multiplicity two to six are evaluated by Romberg’s method and the results are compared with other methods.