New preconditioned AOR iterative method for Z-matrices

In this paper, we present a new preconditioned AOR-type iterative method for solving the linear system Ax=b, where A is a Z-matrix, and prove its convergence. Then we give some comparison theorems to show that the rate of convergence of the preconditioned AOR-type iterative method is faster than the rate of convergence of the AOR-type iterative method. Finally, we give two numerical examples to illustrate our results.     

Attracting cycles for the relaxed Newton’s method

We study the relaxed Newton’s method applied to polynomials. In particular, we give a technique such that for any n≥2, we may construct a polynomial so that when the method is applied to a polynomial, the resulting rational function has an attracting cycle of period n. We show that when we use the method to extract radicals, the set consisting of the points at which the method fails to converge to the roots of the polynomial p(z)=z^m−c (this set includes the Julia set) has zero Lebesgue measure. Consequently, iterate sequences under the relaxed Newton’s method converge to the roots of the preceding polynomial with probability one.     

Transformation methods for finding multiple roots of nonlinear equations

In this paper, to estimate a multiple root p of an equation f(x) = 0, we transform the function f(x) to a hyper tangent function combined with a simple difference formula whose value changes from −1 to 1 as x passes through the root p. Then we apply the so-called numerical integration method to the transformed equation, which may result in a specious approximate root. Furthermore, in order to enhance the accuracy of the approximation we propose a Steffensen-type iterative method, which does not require any derivatives of f(x) nor is quite affected by an initial approximation. It is shown that the convergence order of the proposed method becomes cubic by simultaneous approximation to the root and its multiplicity. Results for some numerical examples show the efficiency of the new method.     

Some analytic approximations for neutral stochastic functional differential equations

We consider an analytic iterative method to approximate the solution of a neutral stochastic functional differential equation. More precisely, we define a sequence of approximate equations and we give sufficient conditions under which the approximate solutions converge with probability one and in pth moment sense, p ? 2, to the solution of the initial equation. We introduce the notion of the Z-algorithm for this iterative method and present some examples to illustrate the theory. Especially, we point out that the well-known Picard method of iterations is a special Z-algorithm.     

On the convergence of the modified overrelaxation method

The modified overrelaxation (MSOR) method is applied to a linear system Ax=b, where A has property A. We get bounds for the spectral radius of the iteration matrix of this method, and we achieve convergence conditions for the MSOR method when A is strictly diagonally dominant. We extend our conclusions to another kind of matrices—H,L,M or Stieltjes. In the last section we use the vectorial norms, getting convergence conditions for the MSOR method, when A is a block-H matrix. We also generalize a theorem of Robert's for this kind of matrices.     

A Shamanskii-like Levenberg-Marquardt method for nonlinear equations

In this paper, we propose a Shamanskii-like Levenberg-Marquardt method for nonlinear equations. At every iteration, not only a LM step but also m?1 approximate LM steps are computed, where m is a positive integer. Under the local error bound condition which is weaker than nonsingularity, we show the Shamanskii-like LM method converges with Q-order m+1. The trust region technique is also introduced to guarantee the global convergence of the method. Since the Jacobian evaluation and matrix factorization are done after every m computations of the step, the overall cost of the Shamanskii-like LM method is usually much less than that of the general LM method (the m=1 case).     

Extended convergence regions for the AOR method

In this paper, we give sufficient conditions for the convergence of the (AOR) method, when the matrix A for Ax = b is a strictly diagonally dominant matrix. These results improve the conclusions obtained in the Theorem 4 [10].With the notion of generalized diagonal dominant matrix, we enlarge the convergence regions given in Theorem 9 [10], when A is a nonsingular H-matrix.In the last section we generalize theorem 6 of Robert [11] and we present some results which extend the convergence regions for the (AOR) method.     

An almost fourth order uniformly convergent domain decomposition method for a coupled system of singularly perturbed reaction-diffusion equations

We consider a system of M(≥2) singularly perturbed equations of reaction-diffusion type coupled through the reaction term. A high order Schwarz domain decomposition method is developed to solve the system numerically. The method splits the original domain into three overlapping subdomains. On two boundary layer subdomains we use a compact fourth order difference scheme on a uniform mesh while on the interior subdomain we use a hybrid scheme on a uniform mesh. We prove that the method is almost fourth order ε-uniformly convergent. Furthermore, we prove that when ε is small, one iteration is sufficient to get almost fourth order ε-uniform convergence. Numerical experiments are performed to support the theoretical results.     

A finite element method for a single phase quasilinear free boundary problem in one space dimension

In this paper, we apply finite element Galerkin method to a singlephase quasilinear Stefan problem with a forcing term. To construct the fully discrete approximation we apply the extrapolated Crank-Nicolson method and we derive the optimal order of convergence 2 in the temporal direction inL ²,H ¹ normed spaces.     

An ε-sensitivity analysis in the primal–dual interior point method

This paper presents a method of sensitivity analysis on the cost coefficients and the right-hand sides for most variants of the primal–dual interior point method. We first define an ε-optimal solution to describe the characteristics of the final solution obtained by the primal–dual interior point method. Then an ε-sensitivity analysis is defined to determine the characteristic region where the final solution remains the ε-optimal solution as a cost coefficient or a right-hand side changes. To develop the method of ε-sensitivity analysis, we first derive the expressions for the final solution from data which are commonly maintained in most variants of the primal–dual interior point method. Then we extract the characteristic regions on the cost coefficients and the right-hand sides by manipulating the mathematical expressions for the final solution. Finally, we show that in the nondegenerate case, the characteristic regions obtained by ε-sensitivity analysis are convergent to those obtained by sensitivity analysis in the simplex algorithm.     

Accelerated iterative method for Z-matrices

It has recently been reported that the convergence of the preconditioned Gauss-Seidel method which uses a matrix of the type (I + U) as a preconditioner is faster than the basic iterative method. In this paper, we generalize the preconditioner to the type (I + βU), where β is a positive real number. After discussing convergence of the method applied to Z-matrices, we propose an algorithm for estimating the optimum β. Numerical examples are also given, which show the effectiveness of our algorithm.     

On construction of involutory MDS matrices from Vandermonde Matrices in GF(2 q )

Due to their remarkable application in many branches of applied mathematics such as combinatorics, coding theory, and cryptography, Vandermonde matrices have received a great amount of attention. Maximum distance separable (MDS) codes introduce MDS matrices which not only have applications in coding theory but also are of great importance in the design of block ciphers. Lacan and Fimes introduce a method for the construction of an MDS matrix from two Vandermonde matrices in the finite field. In this paper, we first suggest a method that makes an involutory MDS matrix from the Vandermonde matrices. Then we propose another method for the construction of 2 ⁿ × 2 ⁿ Hadamard MDS matrices in the finite field GF(2 ^q ). In addition to introducing this method, we present a direct method for the inversion of a special class of 2 ⁿ ?× 2 ⁿ Vandermonde matrices.     

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.     

A fast Fourier-collocation method for second boundary integral equations

In this paper we develop a fast collocation method for second boundary integral equations by the trigonometric polynomials. We propose a convenient way to compress the dense matrix representation of a compact integral operator with a smooth kernel under the Fourier basis and the corresponding collocation functionals. The compression leads to a sparse matrix with only O(nlog²n) number of nonzero entries, where 2n+1 denotes the order of the matrix. Thus we develop a fast Fourier-collocation method. We prove that the fast Fourier-collocation method gives the optimal convergence order up to a logarithmic factor. Moreover, we design a fast scheme for solving the corresponding truncated linear system. We establish that this algorithm preserves the quasi-optimal convergence of the approximate solution with requiring a number of O(nlog³n) multiplications.     

A global harmonic Arnoldi method for large non-Hermitian eigenproblems with an application to multiple eigenvalue problems

The global Arnoldi method can be used to compute exterior eigenpairs of a large non-Hermitian matrix A, but it does not work well for interior eigenvalue problems. Based on the global Arnoldi process that generates an F-orthonormal basis of a matrix Krylov subspace, we propose a global harmonic Arnoldi method for computing certain harmonic F-Ritz pairs that are used to approximate some interior eigenpairs. We propose computing the F-Rayleigh quotients of the large non-Hermitian matrix with respect to harmonic F-Ritz vectors and taking them as new approximate eigenvalues. They are better and more reliable than the harmonic F-Ritz values. The global harmonic Arnoldi method inherits convergence properties of the harmonic Arnoldi method applied to a larger matrix whose distinct eigenvalues are the same as those of the original given matrix. Some properties of the harmonic F-Ritz vectors are presented. As an application, assuming that A is diagonalizable, we show that the global harmonic Arnoldi method is able to solve multiple eigenvalue problems both in theory and in practice. To be practical, we develop an implicitly restarted global harmonic Arnoldi algorithm with certain harmonic F-shifts suggested. In particular, this algorithm can be adaptively used to solve multiple eigenvalue problems. Numerical experiments show that the algorithm is efficient for the eigenproblem and is reliable for quite ill-conditioned multiple eigenproblems.     

Extrapolated Crank-Nicolson approximation for a linear Stefan problem with a forcing term

In this paper, we apply finite element Galerkin method to a single-phase linear Stefan problem with a forcing term. We apply the extrapolated Crank-Nicolson method to construct the fully discrete approximation and we derive optimal error estimates in the temporal direction inL ²,H ¹ spaces.     

A Jacobi-collocation method for solving second kind Fredholm integral equations with weakly singular kernels

In this work, we propose a Jacobi-collocation method to solve the second kind linear Fredholm integral equations with weakly singular kernels. Particularly, we consider the case when the underlying solutions are sufficiently smooth. In this case, the proposed method leads to a fully discrete linear system. We show that the fully discrete integral operator is stable in both infinite and weighted square norms. Furthermore, we establish that the approximate solution arrives at an optimal convergence order under the two norms. Finally, we give some numerical examples, which confirm the theoretical prediction of the exponential rate of convergence.     

Aggregation via empirical risk minimization

Given a finite set F of estimators, the problem of aggregation is to construct a new estimator whose risk is as close as possible to the risk of the best estimator in F. It was conjectured that empirical minimization performed in the convex hull of F is an optimal aggregation method, but we show that this conjecture is false. Despite that, we prove that empirical minimization in the convex hull of a well chosen, empirically determined subset of F is an optimal aggregation method.     

An algorithm for computing the eigenvalues of block companion matrices

In this paper we propose a method for computing the roots of a monic matrix polynomial. To this end we compute the eigenvalues of the corresponding block companion matrix C. This is done by implementing the QR algorithm in such a way that it exploits the rank structure of the matrix. Because of this structure, we can represent the matrix in Givens-weight representation. A similar method as in Chandrasekaran et al. (Oper Theory Adv Appl 179:111–143, 2007), the bulge chasing, is used during the QR iteration. For practical usage, matrix C has to be brought in Hessenberg form before the QR iteration starts. During the QR iteration and the transformation to Hessenberg form, the property of the matrix being unitary plus low rank numerically deteriorates. A method to restore this property is used.