Parallel methods for solving equations

Two classes of algorithms for equation solving are presented and analyzed. These algorithms have been devised in recent years because of the computational facility of the multiprocessor. The first class consists of parallel search methods while the second class consists of asynchronous methods. The first class of methods are fail safe. That is they always provide an approximation to the root as well as the smallest possible interval (for the work done) guaranteed to contain the root. The second class frees the intrinsically interlocked nature of the more complicated forms of algorithms designed for multiprocessors by omitting the synchrony usually demanded in computation.     

Subdivision methods for solving polynomial equations

This paper presents a new algorithm for solving a system of polynomials, in a domain of Rⁿ${\mathbb{R}}^n$. It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule  . We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of Rⁿ${\mathbb{R}}^n$. The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem.     

The method of particular solutions for solving nonlinear Poisson problems

Based on the recent development in the method of particular solutions, we re-exam three approaches using different basis functions for solving nonlinear Poisson problems. We further propose to simplify the solution procedure by removing the insolvency condition when the radial basis functions are augmented with high order polynomial basis functions. We also specify the deficiency of some of these methods and provide necessary remedy. The traditional Picard method is introduced to compare with the recent proposed methods using MATLAB optimization toolbox solver for solving nonlinear Poisson equations. Ranking on these three approaches are given based on the results of numerical experiment.     

Multipoint iterative parallel methods for solving equations

In this paper we show the results of some research carried out on parallel iterative methods to solve equations. In particular we study general classes of one point parallel methods and multipoint ones without memory, and we point out the convergence order of these methods and the conditions which are both necessary and sufficient for them to be optimal. In addition we prove that the convergence order for multipoint parallel procedures without memory cannot be more thenr(r+) ^m−1 , wherer indicates the number of the parallel processor used andm the number of the functions and eventual derivatives, calculated not simultaneously in every iteration.

---

Sommario In questo articolo presentiamo alcuni risultati concernenti i metodi iterativi paralleli per risolvere equazioni. In particolare analizziamo alcune classi generali di procedimenti ad un punto ed a più punti senza memoria, il loro ordine di convergenza e le condizioni necessarie e sufficienti per ottenere l'ottimalità. Inoltre dimostriamo che l'ordine di convergenza di un procedimento iterativo senza memoria non può eccedere:r(r+1) ^m−1 , dover indica il numero di processor in parallelo usati edm indica il numero di funzioni ed eventuali derivate calcolate non simultaneamente in ogni iterazione.

     

Fourth-order derivative-free methods for solving non-linear equations

Two new one-parameter families of methods for finding simple and real roots of non-linear equations without employing derivatives of any order are developed. Error analysis providing the fourth-order convergence is given. Each member of the families requires three evaluations of function per step, and therefore the method has an efficiency index of 1.587. Numerical examples are presented and the performance of the method presented here is compared with methods available in the literature.     

Conforming spectral methods for Poisson problems in cuboidal domains

A Chebyshev collocation strategy is introduced for the subdivision of cuboids into cuboidal subdomains (elements). These elements are conforming, which means that the approximation to the solution isC ⁰ continuous at all points across their interfaces.     

Continuation methods for solving modified discrete-time algebraicRiccati equations

It is well known that the continuation methods have been successfully applied to solve polynomial systems and fixed point problems, etc. In this paper, we consider a discrete-time algebraic Riccati equation with an admissible, low rank, and symmetric perturbation. Our attention is directed primarily to this modified discrete-time algebraic Riccati equation and the numerical method for its solution based on proceeding along the continuation path     

Conforming Chebyshev spectral methods for Poisson problems in rectangular domains

Four and six-element conforming domain decomposition techniques are developed for Chebyshev spectral collocation methods for Poisson problems in rectangular domains. The applicability of the methods is demonstrated on standard test problems.Parts of this work were performed while the author was at the Mathematics Department, Southern Methodist University, Dallas, Texas 75275.     

A new analytical method for solving systems of Volterra integral equations

In this paper, a new modified homotopy perturbation method (NHPM) is introduced for solving systems of Volterra integral equations of the second kind. Theorems of existence and uniqueness of the solutions to these equations are presented. Comparison of the results of applying the NHPM with those of the homotopy perturbation method and Adomian's decomposition method leads to significant consequences. Several examples, including the system of linear and nonlinear Volterra integral equations, are given to demonstrate the efficiency of the new method.     

Optimization of projection methods for solving ill-posed problems

In this paper we propose a modification of the projection scheme for solving ill-posed problems. We show that this modification allows to obtain the best possible order to accuracy of Tikhonov Regularization using an amount of information which is far less than for the standard projection technique.     

Pseudospectral methods for solving infinite-horizon optimal control problems

An important aspect of numerically approximating the solution of an infinite-horizon optimal control problem is the manner in which the horizon is treated. Generally, an infinite-horizon optimal control problem is approximated with a finite-horizon problem. In such cases, regardless of the finite duration of the approximation, the final time lies an infinite duration from the actual horizon at t=+∞. In this paper we describe two new direct pseudospectral methods using Legendre–Gauss (LG) and Legendre–Gauss–Radau (LGR) collocation for solving infinite-horizon optimal control problems numerically. A smooth, strictly monotonic transformation is used to map the infinite time domain t∈[0,∞) onto a half-open interval τ∈[−1,1). The resulting problem on the finite interval is transcribed to a nonlinear programming problem using collocation. The proposed methods yield approximations to the state and the costate on the entire horizon, including approximations at t=+∞. These pseudospectral methods can be written equivalently in either a differential or an implicit integral form. In numerical experiments, the discrete solution exhibits exponential convergence as a function of the number of collocation points. It is shown that the map ?:[−1,+1)→[0,+∞) can be tuned to improve the quality of the discrete approximation.     

Moving mesh methods for solving parabolic partial differential equations

A new adaptive method is described for solving nonlinear parabolic partial differential equations with moving boundaries, using a moving mesh with continuous finite elements. The evolution of the mesh within the interior of the spatial domain is based upon conserving the distribution of a chosen monitor function across the domain throughout time, where the initial distribution is selected based upon the given initial data. The mesh movement at the boundary is governed by a second monitor function, which may or may not be the same as that used to drive the interior mesh movement. The method is described in detail and a selection of computational examples are presented using different monitor functions applied to the porous medium equation (PME) in one and two space dimensions.     

Efficient Jarratt-like methods for solving systems of nonlinear equations

We present the iterative methods of fourth and sixth order convergence for solving systems of nonlinear equations. Fourth order method is composed of two Jarratt-like steps and requires the evaluations of one function, two first derivatives and one matrix inversion in each iteration. Sixth order method is the composition of three Jarratt-like steps of which the first two steps are that of the proposed fourth order scheme and requires one extra function evaluation in addition to the evaluations of fourth order method. Computational efficiency in its general form is discussed. A comparison between the efficiencies of proposed techniques with existing methods of similar nature is made. The performance is tested through numerical examples. Moreover, theoretical results concerning order of convergence and computational efficiency are confirmed in the examples. It is shown that the present methods are more efficient than their existing counterparts, particularly when applied to the large systems of equations.     

A family of Newton-type methods for solving nonlinear equations

A family of Newton-type methods free from second and higher order derivatives for solving nonlinear equations is presented. The order of the convergence of this family depends on a function. Under a condition on this function this family converge cubically and by imposing one condition more on this function one can obtain methods of order four. It has been shown that this family covers many of the available iterative methods. From this family two new iterative methods are obtained. Numerical experiments are also included.     

An efficient analytical approach for solving fourth order boundary value problems

Based on the homotopy analysis method (HAM), an efficient approach is proposed for obtaining approximate series solutions to fourth order two-point boundary value problems. We apply the approach to a linear problem which involves a parameter c and cannot be solved by other analytical methods for large values of c, and obtain convergent series solutions which agree very well with the exact solution, no matter how large the value of c is. Consequently, we give an affirmative answer to the open problem proposed by Momani and Noor in 2007 [S. Momani, M.A. Noor, Numerical comparison of methods for solving a special fourth-order boundary value problem, Appl. Math. Comput. 191 (2007) 218-224]. We also apply the approach to a nonlinear problem, and obtain convergent series solutions which agree very well with the numerical solution given by the Runge-Kutta-Fehlberg 4-5 technique.     

Implementation issues in solving nonlinear equations for two-point boundary value problems

Complex numerical methods often contain subproblems that are easy to state in mathematical form, but difficult to translate into software. Several algorithmic isues of this nature arise in implementing a Newton iteration scheme as part of a finite-difference method for two-point boundary value problems. We describe the practical as well as theoretical considerations behind the decisions included in the final code, with special emphasis on two “watchdog” strategies designed to improve reliability and allow early termination of the Newton iterates.