A Quadratic Clipping Step with Superquadratic Convergence for Bivariate Polynomial Systems

A new numerical approach to compute all real roots of a system of two bivariate polynomial equations over a given box is described. Using the Bernstein–Bézier representation, we compute the best linear approximant and the best quadratic approximant of the two polynomials with respect to the L ² norm. Using these approximations and bounds on the approximation errors, we obtain a fat line bounding the zero set first of the first polynomial and a fat conic bounding the zero set of the second polynomial. By intersecting these fat curves, which requires solely the solution of linear and quadratic equations, we derive a reduced subbox enclosing the roots. This algorithm is combined with splitting steps, in order to isolate the roots. It is applied iteratively until a certain accuracy is obtained. Using a suitable preprocessing step, we prove that the convergence rate is 3 for single roots. In addition, experimental results indicate that the convergence rate is superlinear (1.5) for double roots.     

A proximal point algorithm for finding a common zero of a finite family of maximal monotone operators in the presence of computational errors

In a Hilbert space, we study the convergence of a proximal point method to a common zero of a finite family of maximal monotone operators under the presence of computational errors. Most results known in the literature establish the convergence of proximal point methods, when computational errors are summable. In the present paper, the convergence of the method is established for nonsummable computational errors. We show that the proximal point method generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant.     

Spectral analysis of the errors of some families of multi-step Newton-like methods

Higher order multi-point methods are advantageous to solve scalar nonlinear equations because of their speed of convergence. The approximate solution is usually obtained in a few steps, thus saving time and computational effort. In this work, we study the Power Spectrum of the Fourier Transforms of the errors of a well-known family of multi-step Newton method. Firstly, by two numerical examples we observe that as the order p of the methods increases, the Power Spectrum of Low Frequency modes of successive approximations decreases and the Power Spectrum of the High Frequency modes increases until they become almost equal when p become large. We prove this point analytically by showing that the Power spectrum of the Fourier Transforms of the errors of the methods from the error equation is independent of the frequency and the Amplitude of the Power Spectrum tends to zero as p tends to infinity. From there, we attempt to find the best method of this family. We also compare the family with two other families of higher order multistep methods, in terms of order, efficiency index and Amplitude of Power Spectrum. Finally, we conduct more numerical experiments to find the best method of the 3 families. The work of the first author is partly supported by Tertiary Education Commission and University of Mauritius.     

Weak convergence of a splitting algorithm in Hilbert spaces

In this paper, we present a splitting algorithm with computational errors for solving common solutions of zero point, fixed point and equilibrium problems. Weak convergence theorems of common solutions are established in the framework of real Hilbert spaces.     

On the Algebraic Properties of Errors

In numerical analysis (absolute) errors can be identified with one‐dimensional intervals symmetric with respect to zero. Addition, multiplication and inclusion of errors are well‐defined (set‐theoretically) in interval analysis. We study axiomatically the algebraic properties of such a system of errors. To this end we introduce and investigate a new abstract algebraic structure called e‐ring.     

Computing singular values of diagonally dominant matrices to high relative accuracy

For a (row) diagonally dominant matrix, if all of its off-diagonal entries and its diagonally dominant parts (which are defined for each row as the absolute value of the diagonal entry subtracted by the sum of the absolute values of off-diagonal entries in that row) are accurately known, we develop an algorithm that computes all the singular values, including zero ones if any, with relative errors in the order of the machine precision. When the matrix is also symmetric with positive diagonals (i.e. a symmetric positive semi-definite diagonally dominant matrix), our algorithm computes all eigenvalues to high relative accuracy. Rounding error analysis will be given and numerical examples will be presented to demonstrate the high relative accuracy of the algorithm.

     

A note on convergence of an approximate hedging portfolio with liquidity risk

When the underlying asset price depends on activities of traders, hedging errors include costs due to the illiquidity of the underlying asset and the size of this cost can be substantial. Cetin et al. (2004), Liquidity risk and arbitrage pricing theory, Finance and Stochastics, 8(3), 311-341, proposed a hedging strategy that approximates the classical Black–Scholes hedging strategy and produces zero liquidity costs. Here, we compute the rate of convergence of the final value of this hedging portfolio to the option payoff in case of a European call option; i.e. we see how fast its hedging error converges to zero. The hedging strategy studied here is meaningful due to its simple liquidity cost structure and its smoothness relative to the classical Black–Scholes delta.     

The average errors for Hermite-Fejr interpolation on the Wiener space

For 1≤ p ∞, firstly we prove that for an arbitrary set of distinct nodes in [-1, 1], it is impossible that the errors of the Hermite-Fejr interpolation approximation in L p -norm are weakly equivalent to the corresponding errors of the best polynomial approximation for all continuous functions on [-1, 1]. Secondly, on the ground of probability theory, we discuss the p-average errors of Hermite-Fejr interpolation sequence based on the extended Chebyshev nodes of the second kind on the Wiener space. By our results we know that for 1≤ p ∞ and 2≤ q ∞, the p-average errors of Hermite-Fejr interpolation approximation sequence based on the extended Chebyshev nodes of the second kind are weakly equivalent to the p-average errors of the corresponding best polynomial approximation sequence for L q -norm approximation. In comparison with these results, we discuss the p-average errors of Hermite-Fejr interpolation approximation sequence based on the Chebyshev nodes of the second kind and the p-average errors of the well-known Bernstein polynomial approximation sequence on the Wiener space.     

Two-derivative Runge-Kutta methods with optimal phase properties

In this work, we consider two-derivative Runge-Kutta methods for the numerical integration of first-order differential equations with oscillatory solution. We construct methods with constant coefficients and special properties as minimum phase-lag and amplification errors with three and four stages. All methods constructed have fifth algebraic order. We also present methods with variable coefficients with zero phase-lag and amplification errors. In order to examine the efficiency of the new methods, we use four well-known oscillatory test problems.     

Degeneracy in Heteroscedastic Regression Models

The maximum likelihood estimation in a regression model with heteroscedastic errors is considered. When the design matrices in the model are inappropriately specified, the maximum likelihood estimates of the variances of certain observations are found to be zero irrespective of the observed values, resulting in degeneracy. Necessary and sufficient conditions for degeneracy are given and used for its avoidance.     

Non-independence of excursions of the Brownian sheet and of additive Brownian motion

A classical and important property of Brownian motion is that given its zero set, distinct excursions away from zero are independent. In this paper, we examine the analogous question for the Brownian sheet, and also for additive Brownian motion. Our main result is that given the level set of the Brownian sheet at level zero, distinct excursions of the sheet away from zero are not independent. In fact, given the zero set of the Brownian sheet in the entire non-negative quadrant, and the sign of all but a finite number of excursions away from zero, the signs of the remaining excursions are determined. For additive Brownian motion, we prove the following definitive result: given the zero set of additive Brownian motion and the sign of a single excursion, the signs of all other excursions are determined. In an appendix by John B. Walsh, it is shown that given the absolute value of the sheet in the entire quadrant and, in addition, the sign of the sheet at a fixed, non-random time point, then the whole sheet can be recovered.

     

Numerical computation of characteristic polynomials of Boolean functions and its applications

We study the problem of evaluation of characteristic polynomials of Boolean functions with applications to combinational circuit verification. Two Boolean functions are equivalent if and only if their corresponding characteristic polynomials are identical. However, to verify the equivalence of two Boolean functions it is often impractical to construct the corresponding characteristic polynomials due to a possible exponential blow-up of the terms of the polynomials. Instead, we compare their values at a sample point without explicitly constructing the characteristic polynomials. Specifically, we sample uniformly at random in a unit cube and determine whether two characteristic polynomials are identical by their evaluations at the sample point; the error probability is zero when there are no round-off errors. In the presence of round-off errors, we sample on regular grids and analyze the error probability. We discuss in detail the Shannon expansion for characteristic polynomial evaluation. This revised version was published online in June 2006 with corrections to the Cover Date.     

Some Bounds for the Number of Components of Real Zero Sets of Sparse Polynomials

We prove that the zero set of a 4-nomial in n variables in the positive orthant has at most three connected components. This bound, which does not depend on the degree of the polynomial, not only improves the best previously known bound (which was 10) but is optimal as well. In the general case we prove that the number of connected components of the zero set of an m-nomial in n variables in the positive orthant is lower than or equal to (n+1)^m-12^{1 + (m - 1)(m - 2)/2}, improving slightly the known bounds. Finally, we show that for generic exponents, the number of non-compact connected components of the zero set of a 5-nomial in three variables in the positive octant is at most 12. This strongly improves the best previously known bound, which was 10,384. All the bounds obtained in this paper continue to hold for real exponents.     

Prediction with measurement errors in finite populations

We address the problem of selecting the best linear unbiased predictor (BLUP) of the latent value (e.g., serum glucose fasting level) of sample subjects with heteroskedastic measurement errors. Using a simple example, we compare the usual mixed model BLUP to a similar predictor based on a mixed model framed in a finite population (FPMM) setup with two sources of variability, the first of which corresponds to simple random sampling and the second, to heteroskedastic measurement errors. Under this last approach, we show that when measurement errors are subject-specific, the BLUP shrinkage constants are based on a pooled measurement error variance as opposed to the individual ones generally considered for the usual mixed model BLUP. In contrast, when the heteroskedastic measurement errors are measurement condition-specific, the FPMM BLUP involves different shrinkage constants. We also show that in this setup, when measurement errors are subject-specific, the usual mixed model predictor is biased but has a smaller mean squared error than the FPMM BLUP which points to some difficulties in the interpretation of such predictors.     

Lagrange插值和Hermite-Fejér插值在Wiener空间下的平均误差

在L_q-范数逼近的意义下,确定了基于Chebyshev多项式零点的Lagrange插值多项式列和Hermite-Fejér插值多项式列在Wiener空间下的p-平均误差的弱渐近阶.从我们的结果可以看出,当2≤q<∞,1≤p<∞时,基于第一类Chebyshev多项式零点的Lagrange插值多项式列和Hermite-Fejér插值多项式列的p-平均误差弱等价于相应的最佳逼近多项式列的p-平均误差.在信息基计算复杂性的意义下,如果可允许信息泛函为计算函数在固定点的值,那么当1≤p,q<∞时,基于第一类Chebyshev多项式零点的Lagrange插值多项式列和Hermite-Fejér插值多项式列在Wiener空间下的p-平均误差弱等价于相应的最小非自适应p-平均信息半径.     

Convergence and optimality of BS-type discrete hedging strategy under stochastic interest rate

We focus on the asymptotic convergence behavior of the hedging errors of European stock option due to discrete hedging under stochastic interest rates. There are two kinds of BS-type discrete hedging differ in hedging instruments: one is the portfolio of underlying stock, zero coupon bond, and the money market account (Strategy BSI); the other is the underlying stock, zero coupon bond (Strategy BSII). Similar to the results of the deterministic interest rate case, we show that convergence speed of the disco...     

A simplified proof of weak convergence in Douglas–Rachford method

Douglas–Rachford method is a splitting algorithm for finding a zero of the sum of two maximal monotone operators. Weak convergence in this method to a solution of the underlying monotone inclusion problem in the general case remained an open problem for 30 years and was proved by the author 7 years ago. That proof was cluttered with technicalities because we considered the inexact version with summable errors. In this short communication we present a streamlined proof of this result.     

插值多项式在一重积分Wiener空间下的同时逼近平均误差

本文在加权L_p范数逼近意义下确定了基于第一类Chebyshev 结点组的Lagrange 插值多项式列在一重积分Wiener 空间下同时逼近平均误差的渐近阶. 结果显示在L_p范数逼近意义下Lagrange 插值多项式列的平均误差弱等价于相应的最佳逼近多项式列的平均误差. 同时, 当2≤p≤4 时,Lagrange 插值多项式列导数逼近的平均误差弱等价于相应的导数最佳逼近多项式列的平均误差. 作为对比, 本文也确定了相应的Hermite-Fejér 插值多项式列在一重积分Wiener空间下逼近的平均误差的渐近阶.     

Frequency and Magnitude Response Design Approximation Problems for Nonlinear-phase Nonrecursive Digital Filters

In this article special (possibly constrained) problems of linear and nonlinear complex approximation are studied with respect to the existence and uniqueness of solutions and the convergence of the approximation errors, where the errors are measured by an arbitrary L p and l p norm respectively. The problems arise in connection with the frequency and magnitude response approximation at the design of nonrecursive digital filters in the frequency domain. Two main results of the article concern the completeness of the functions exp ( m ik y ), k = 0,1,2,… , with respect to a certain space of continuous functions. These results imply that, under usual assumptions and with increasing number of approximating functions exp ( m ik y ), the errors in the frequency and magnitude response approximation problems converge to zero when the design region is not the total interval [0, ~ ] (in case of real coefficients) and not [ m ~ , ~ ] (in case of complex coefficients) which is given for the majority of filter design problems, but that the frequency response errors may not converge to zero when the design region equals [0, ~ ] or [ m ~ , ~ ] respectively.     

Stable zero duality gaps in convex programming: Complete dual characterisations with applications to semidefinite programs

The zero duality gap that underpins the duality theory is one of the central ingredients in optimisation. In convex programming, it means that the optimal values of a given convex program and its associated dual program are equal. It allows, in particular, the development of efficient numerical schemes. However, the zero duality gap property does not always hold even for finite-dimensional problems and it frequently fails for problems with non-polyhedral constraints such as the ones in semidefinite programming problems. Over the years, various criteria have been developed ensuring zero duality gaps for convex programming problems. In the present work, we take a broader view of the zero duality gap property by allowing it to hold for each choice of linear perturbation of the objective function of the given problem. Globalising the property in this way permits us to obtain complete geometric dual characterisations of a stable zero duality gap in terms of epigraphs and conjugate functions. For convex semidefinite programs, we establish necessary and sufficient dual conditions for stable zero duality gaps, as well as for a universal zero duality gap in the sense that the zero duality gap property holds for each choice of constraint right-hand side and convex objective function. Zero duality gap results for second-order cone programming problems are also given. Our approach makes use of elegant conjugate analysis and Fenchel's duality.