Semiconvergence of P-regular splittings for solving singular linear systems

We investigate necessary and sufficient conditions for semiconvergence of a splitting for solving singular linear systems, where the coefficient matrix A is a singular EP matrix. When A is a singular Hermitian matrix, necessary and sufficient conditions for semiconvergence of P-regular splittings are given, which generalize known results. As applications, the necessary and sufficient conditions for semiconvergence of block AOR and SSOR iterative methods are derived. A numerical example is given to illustrate the theoretical results. The work is supported by the National Natural Science Foundation of China under grant 10371056, the Foundation for the Authors of the National Excellent Doctoral Thesis Award of China under grant 200720 and the Natural Science Foundation of Jiangsu Province of China under grant BK2006725.     

DCT- and DST-based splitting methods for Toeplitz systems

New splitting iterative methods for Toeplitz systems are proposed by means of recently developed matrix splittings based on discrete sine and cosine transforms due to Kailath and Olshevsky [Displacement structure approach to discrete-trigonometric transform-based preconditioners of G. Strang type and of T. Chan type, SIAM J. Matrix Anal. Appl. 26 (2005), pp. 706–734]. Theoretical analysis shows that new splitting iterative methods converge to the unique solution of a symmetric Toeplitz linear system. Moreover, an upper bound of the contraction factor of our new splitting iterations is derived. Numerical examples are reported to illustrate the effectiveness of new splitting iterative methods.     

On convergence of splitting iteration methods for non-Hermitian positive-definite linear systems

A new splitting iteration method is presented for the system of linear equations when the coefficient matrix is a non-Hermitian positive-definite matrix. The spectral radius, the optimal parameter, and some norm properties of the iteration matrix for the new method are discussed in detail. Based on these results, the new method is convergent under reasonable conditions for any non-Hermitian positive-definite linear system. Finally, the numerical examples show that the new method is more effective than the Hermitian and skew-Hermitian splitting iterative (or positive-definite and skew-Hermitian splitting iterative) method in central processing unit time.     

Trigonometric transform splitting methods for real symmetric Toeplitz systems

In this paper we study efficient iterative methods for real symmetric Toeplitz systems based on the trigonometric transformation splitting (TTS) of the real symmetric Toeplitz matrix $A$. Theoretical analyses show that if the generating function $f$ of the $n\times n$ Toeplitz matrix $A$ is a real positive even function, then the TTS iterative methods converge to the unique solution of the linear system of equations for sufficient large $n$. Moreover, we derive an upper bound of the contraction factor of the TTS iteration which is dependent solely on the spectra of the two TTS matrices involved.Different from the CSCS iterative method in Ng (2003) in which all operations counts concern complex operations when the DFTs are employed, even if the Toeplitz matrix $A$ is real and symmetric, our method only involves real arithmetics when the DCTs and DSTs are used. The numerical experiments show that our method works better than CSCS iterative method and much better than the positive definite and skew-symmetric splitting (PSS) iterative method in Bai et al. (2005) and the symmetric Gauss–Seidel (SGS) iterative method.     

Multipoint efficient iterative methods and the dynamics of Ostrowski's method

ABSTRACT

In this work, we introduce a modification into the technique, presented in A. Cordero, J.L. Hueso, E. Martínez, and J.R. Torregrosa [Increasing the convergence order of an iterative method for nonlinear systems, Appl. Math. Lett. 25 (2012), pp. 2369–2374], that increases by two units the convergence order of an iterative method. The main idea is to compose a given iterative method of order p with a modification of Newton's method that introduces just one evaluation of the function, obtaining a new method of order p+2, avoiding the need to compute more than one derivative, so we improve the efficiency index in the scalar case. This procedure can be repeated n times, with the same approximation to the derivative, obtaining new iterative methods of order p+2n. We perform different numerical tests that confirm the theoretical results. By applying this procedure to Newton's method one obtains the well known fourth order Ostrowski's method. We finally analyse its dynamical behaviour on second and third degree real polynomials.     

Modified iterative methods for nonnegative matrices and M-matrices linear systems

The purpose of this paper is to present new preconditioning techniques for solving nonnegative matrices linear system and M-matrices linear system Ax = b based on the I + S(α) type preconditioning matrices provided by Hadjidimos et al. ^[1] and Evans et al. ^[2]. Convergence analysis of the proposed methods are given. Numerical results are presented, which show the improvements on the convergence rate of the Jacobi type and Gauss-Seidel type preconditioned iterative methods.     

Scheduling parallel iterative methods on multiprocessor systems

The paper describes the implementation of the Successive Overrelaxation (SOR) method on an asynchronous multiprocessor computer for solving large, linear systems. The parallel algorithm is derived by dividing the serial SOR method into noninterfering tasks which are then combined with an optimal schedule of a feasible number of processors. The important features of the algorithm are: (i) achieves a speedup S_p O(N/3) and an efficiency E_p 2/3 using P = [N/2] processors, where N is the number of the equations, (ii) contains a high level of inherent parallelism, whereas on the other hand, the convergence theory of the parallel SOR method is the same as its sequential counterpart and (iii) may be modified to use block methods in order to minimise the overhead due to communication and synchronisation of the processors.     

Convergence of relaxation methods for two-point boundary-value linear problems

The solution of linear differential problems, with explicit two-point boundary conditions, can sometimes be obtained by a relaxation method of computation. This paper shows that the convergence of iterations is linked to the spectral radius value of an integral operator. The equivalence between eigenvalues research and critical lengths calculation of a differential system is demonstrated. In this context, we present a case of optimal control law calculation of a linear system. The efficiency of this preliminary convergence calculation is illustrated by a numerical example.     

A class of iterative methods for computing polar decomposition

In this article, there is offered a parametric class of iterative methods for computing the polar decomposition of a matrix. Each iteration of this class needs only one scalar-by-matrix and three matrix-by-matrix multiplications. It is no use computing inversion, so no numerical problems can be created because of ill-conditioning. Some available methods can be included in this class by choosing a suitable value for the parameter. There are obtained conditions under which this class is always quadratically convergent. The numerical comparison performed among six quadratically convergent methods for computing polar decomposition, and a special method of this class, chosen based on a specific value for the parameter, shows that the number of iterations of the special method is considerably near that of a cubically convergent Halley's method. Ten n×n matrices with n=5, 10, 20, 50, 100 were chosen to make this comparison.     

Singular H∞ control in nonlinear systems: positive semidefinite storage functions and separation principle

A framework is developed for the general nonlinear H_∞ output feedback control problem, in which two major restrictions are relaxed, i.e., the non-singular penalty in H_∞ cost and the positive definite solution of Hamilton–Jacobi inequality at present state space nonlinear H_∞ control literatures. As illustrated in an example, positive semidefinite solution simplifies the structure of the H_∞ controller. Based on this framework, some sufficient conditions are derived. While specialized to linear systems, the controller reduces to the so-called central controller. © 1997 by John Wiley & Sons, Ltd.     

Parallelizable restarted iterative methods for nonsymmetric linear systems. part I: Theory

Large sparse nonsymmetric problems of the form A u = b are frequently solved using restarted conjugate gradient-type algorithms such as the popular GCR and GMRES algorithms. In this study we define a new class of algorithms which generate the same iterates as the standard GMRES algorithm but require as little as half of the computational expense. This performance improvement is obtained by using short economical three-term recurrences to replace the long recurrence used by GMRES. The new algorithms are shown to have good numerical properties in typical cases, and the new algorithms may be easily modified to be as numerically safe as standard GMRES. Numerical experiments with these algorithms are given in Part II, in which we demonstrate the improved performance of the new schemes on different computer architectures.     

Constructing third-order derivative-free iterative methods

In this work, we develop nine derivative-free families of iterative methods from the three well-known classical methods: Chebyshev, Halley and Euler iterative methods. Methods of the developed families consist of two steps and they are totally free of derivatives. Convergence analysis shows that the methods of these families are cubically convergent, which is also verified through the computational work. Apart from being totally free of derivatives, numerical comparison demonstrates that the developed methods perform better than the three classical methods.     

Convergence of normalized iterative identification of Hammerstein systems

An iterative identification algorithm of Hammerstein systems needs a proper initial condition to guarantee its convergence. In this paper, we propose a new algorithm by fixing the norm of the parameter estimates. The normalized algorithm ensures the convergence property under arbitrary nonzero initial conditions. The proofs of the property also give a geometrical explanation on why the normalization guarantees the convergence. An additional contribution is that the static function in the Hammerstein system is extended to square-integrable functions.     

Parallel,iterative solution of sparse linear systems: Models and architectures

Solving large, sparse, linear systems of equations is a fundamental problems in large scale scientific and engineering computation. A model of a general class of asynchronous, iterative solution methods for linear systems is developed. In the model, the system is solved by creating several cooperating tasks that each compute a portion of the solution vector. A data transfer model predicting both the probability that data must be transferred between two tasks and the amount of data to be transferred is presented. This model is used to derive an execution time model for predicting parallel execution time and an optimal number of tasks given the dimension and sparsity of the coefficient matrix and the costs of computation, synchronization, and communication.The suitability of different parallel architectures for solving randomly sparse linear systems is discussed. Based on the complexity of task scheduling, one parallel architecture, based on a broadcast bus, is presented and analyzed.     

A third-order convergent iterative method for solving non-linear equations

In this paper, we present and analyse a new predictor-corrector iterative method for solving non-linear single variable equations. The convergence analysis establishes that the new method is cubically convergent. Numerical tests show that the method is comparable with the well-known existing methods and in many cases gives better results.     

Monotonically convergent iterative learning control for linear discrete-time systems

In iterative learning control schemes for linear discrete time systems, conditions to guarantee the monotonic convergence of the tracking error norms are derived. By using the Markov parameters, it is shown in the time-domain that there exists a non-increasing function such that when the properly chosen constant learning gain is multiplied by this function, the convergence of the tracking error norms is monotonic, without resort to high-gain feedback.     

Explicit isomorphic iterative methods for solving arrow-type linear systems

A new class of approximate inverse arrow-type matrix techniques based on the concept of sparse approximate LU-type factorization procedures is introduced for computing explicitly approximate inverses without inverting the decomposition factors. Isomorphic methods in conjunction with explicit preconditioned schemes based on approximate inverse matrix techniques are presented for the efficient solution of arrow-type linear systems. Applications of the proposed method on linear systems is discussed and numerical results are given     

Parallel iterative solvers for sparse linear systems in circuit simulation

For the solution of sparse linear systems from circuit simulation whose coefficient matrices include a few dense rows and columns, a parallel iterative algorithm with distributed Schur complement preconditioning is presented. The parallel efficiency of the solver is increased by transforming the equation system into a problem without dense rows and columns as well as by exploitation of parallel graph partitioning methods. The costs of local, incomplete LU decompositions are decreased by fill-in reducing reordering methods of the matrix and a threshold strategy for the factorization. The efficiency of the parallel solver is demonstrated with real circuit simulation problems on PC clusters.     

Fourth-order two-step iterative methods for determining multiple zeros of non-linear equations

In this paper, we describe and analyse two two-step iterative methods for finding multiple zeros of non-linear equations. We prove that the methods have fourth-order convergence. The methods calculate the multiple zeros with high accuracy. These are the first two-step multiple zero finding methods. The numerical tests show their better performance in the case of algebraic as well as non-algebraic equations     

Realization of continuous-time positive linear systems

Positive linear systems are used in biomathematics, economics, and other research areas. For discrete-time positive linear systems, part of the realization problem has been solved. In this paper the solution of the corresponding problem for continuous-time positive linear systems will be presented, which can be deduced from that of the discrete-time case by a transformation. Sufficient and necessary conditions for the existence of a positive realization are presented. To solve the problem of minimality, the solution of the factorization of positive matrices is needed.