How to minimize the cost of iterative methods in the presence of perturbations (Q1394939): Difference between revisions

The paper deals with the iterative solution of nonlinear systems when the actual computations are affected by perturbations that distort the numerical results, as is the case for instance with rounding errors. The methods analyzed are assumed to be one-step stationary with linear or superlinear convergence. It is also assumed that the cost of computing each iteration depends on the size of the perturbations. The main scope of the paper is to compute an iterate with a priori given error \(\varepsilon >0\) while minimizing the total cost needed to produce such approximate solution. For a convenient class of cost functions \(c(.)\) it is proved that the cost of producing the iterate can be made proportional to the cost \(c(\varepsilon)\) of one single iterative step carried out with accuracy proportional to \(\varepsilon \). It is also proved that for some cost functions the total cost is proportional to \(c(\varepsilon)^2\). All this is accomplished by properly selecting the precision which is employed at each successive iteration. An interesting application of these results is discussed in order to determine the complexity of nonlinear boundary value problems. The application yields sharp lower and upper bounds for the complexity. In the erratum some misprints have been corrected.