Implementations of range restricted iterative methods for linear discrete ill-posed problems

This paper is concerned with iterative solution methods for large linear systems of equations with a matrix of ill-determined rank and an error-contaminated right-hand side. The numerical solution is delicate, because the matrix is very ill-conditioned and may be singular. It is natural to require that the computed iterates live in the range of the matrix when the latter is symmetric, because then the iterates are orthogonal to the null space. Computational experience indicates that it can be beneficial to require that the iterates live in the range of the matrix also when the latter is nonsymmetric. We discuss the design and implementation of iterative methods that determine iterates with this property. New implementations that are particularly well suited for use with the discrepancy principle are described.     

Subgradient Projection Algorithms and Approximate Solutions of Convex Feasibility Problems

In the present paper, we use subgradient projection algorithms for solving convex feasibility problems. We show that almost all iterates, generated by a subgradient projection algorithm in a Hilbert space, are approximate solutions. Moreover, we obtain an estimate of the number of iterates which are not approximate solutions. In a finite-dimensional case, we study the behavior of the subgradient projection algorithm in the presence of computational errors. Provided computational errors are bounded, we prove that our subgradient projection algorithm generates a good approximate solution after a certain number of iterates.     

A uniform ergodic Theorem for certain Markov operators on Lipschitz functions on bounded metric spaces

Summary Some sufficient conditions are given for uniform convergence of the iterates of transition operators associated with random contractions of a bounded metric space.Supported by National Science Foundation grant GP-7335.     

Forcing sequences and inexact Newton iterates in Banach space

We use inexact Newton iterates to approximate a solution of a nonlinear equation in a Banach space. Solving a nonlinear equation using Newton iterates at each stage is very expensive in general. That is why we consider inexact Newton methods, where the Newton equations are solved only approximately and in some unspecified manner. In the elegant paper [1], natural assumptions under which the forcing sequence is uniformly less than one were given based on the first Fréchet-derivative of the operator involved. Here, we use assumption on the second Fréchet-derivative. This way, we essentially reproduce all results found earlier. However, our upper error bounds on the distances involved are smaller.     

On the equivariant Morse complex of the free loop space of a surface

We prove two theorems about the equivariant topology of the free loop space of a surface. The first deals with the nondegenerate case and says that the ``ordinary' Morse complex can be given an -action in such a way that it carries the -homotopy type of the free loop space. The second says that, in terms of topology, the iterates of an isolated degenerate closed geodesic ``look like' the continuous limit of the iterates of a finite, fixed number of nondegenerate closed geodesics.

     

A semilinear boundary value problem

Weak solutions to the mixed semilinear boundary value problem are constructed via a monotone sequence of iterates. In this paper a nonlinear terms has the general form of an operator from a convex subset of H₁(Ω) into its dual space.     

Reproducing Kernels for Iterated Parabolic Operators on the Upper Half Space with Application to Polyharmonic Bergman Spaces

We consider parabolic operators of fractional order and their iterates on the upper half space of the euclidean space. We deal with Hilbert spaces of solutions of those parabolic equations. We shall show, in this note, the existence of reproducing kernels and give a formula by using their fundamental solutions. As an application, we also discuss the polyharmonic Bergman spaces and give their reproducing kernels by using the Poisson kernel on the upper half space.     

Preconditioning and globalizing conjugate gradients in dual space for quadratically penalized nonlinear-least squares problems

When solving nonlinear least-squares problems, it is often useful to regularize the problem using a quadratic term, a practice which is especially common in applications arising in inverse calculations. A solution method derived from a trust-region Gauss-Newton algorithm is analyzed for such applications, where, contrary to the standard algorithm, the least-squares subproblem solved at each iteration of the method is rewritten as a quadratic minimization subject to linear equality constraints. This allows the exploitation of duality properties of the associated linearized problems. This paper considers a recent conjugate-gradient-like method which performs the quadratic minimization in the dual space and produces, in exact arithmetic, the same iterates as those produced by a standard conjugate-gradients method in the primal space. This dual algorithm is computationally interesting whenever the dimension of the dual space is significantly smaller than that of the primal space, yielding gains in terms of both memory usage and computational cost. The relation between this dual space solver and PSAS (Physical-space Statistical Analysis System), another well-known dual space technique used in data assimilation problems, is explained. The use of an effective preconditioning technique is proposed and refined convergence bounds derived, which results in a practical solution method. Finally, stopping rules adequate for a trust-region solver are proposed in the dual space, providing iterates that are equivalent to those obtained with a Steihaug-Toint truncated conjugate-gradient method in the primal space.     

Fixed points of Mizoguchi–Takahashi contraction on a metric space with a graph and applications

In this paper we extend Mizoguchi–Takahashi's fixed point theorem for multi-valued mappings on a metric space endowed with a graph. As an application, we establish a fixed point theorem on an ε  -chainable metric space for mappings satisfying Mizoguchi–Takahashi contractive condition uniformly locally. Also, we establish a result on the convergence of successive approximations for certain operators (not necessarily linear) on a Banach space as another application. Consequently, this result yields the Kelisky–Rivlin theorem on iterates of the Bernstein operators on the space C[0,1]$C[0,1]$ and also enables us study the asymptotic behaviour of iterates of some nonlinear Bernstein type operators on C[0,1]$C[0,1]$.     

The contraction principle for mappings on a metric space with a graph

We give some generalizations of the Banach Contraction Principle to mappings on a metric space endowed with a graph. This extends and subsumes many recent results of other authors which were obtained for mappings on a partially ordered metric space. As an application, we present a theorem on the convergence of successive approximations for some linear operators on a Banach space. In particular, the last result easily yields the Kelisky-Rivlin theorem on iterates of the Bernstein operators on the space .

     

A three-level BDDC algorithm for a saddle point problem

BDDC algorithms have previously been extended to the saddle point problems arising from mixed formulations of elliptic and incompressible Stokes problems. In these two-level BDDC algorithms, all iterates are required to be in a benign space, a subspace in which the preconditioned operators are positive definite. This requirement can lead to large coarse problems, which have to be generated and factored by a direct solver at the beginning of the computation and they can ultimately become a bottleneck. An additional level is introduced in this paper to solve the coarse problem approximately and to remove this difficulty. This three-level BDDC algorithm keeps all iterates in the benign space and the conjugate gradient methods can therefore be used to accelerate the convergence. This work is an extension of the three-level BDDC methods for standard finite element discretization of elliptic problems and the same rate of convergence is obtained for the mixed formulation of the same problems. Estimate of the condition number for this three-level BDDC methods is provided and numerical experiments are discussed.     

A note on mixing transformations

Let (Θ, ℱ, μ) be a probability space andT a 1-1, onto, measure-preserving transformation. Necessary and sufficient conditions are given forT to be mixing, in terms of union of iterates of sets. Research supported by N.S.F. Grant GP-8290. Part of the research in this paper was carried out while the author was on Sabbatical Leave at the Israel Institute of Technology.     

An Extension of Set-Valued Contraction Principle for Mappings on a Metric Space with a Graph and Application

In this paper, we obtain an existence theorem for fixed points of contractive set-valued mappings on a metric space endowed with a graph. This theorem unifies and extends several fixed point theorems for mappings on metric spaces and for mappings on metric spaces endowed with a graph. As an application, we obtain a theorem on the convergence of successive approximations for some linear operators on an arbitrary Banach space. This result yields the well-known Kelisky–Rivlin theorem on iterates of the Bernstein operators on C[0,1].     

Right preconditioned MINRES for singular systems†

We consider solving large sparse symmetric singular linear systems. We first introduce an algorithm for right preconditioned minimum residual (MINRES) and prove that its iterates converge to the preconditioner weighted least squares solution without breakdown for an arbitrary right‐hand‐side vector and an arbitrary initial vector even if the linear system is singular and inconsistent. For the special case when the system is consistent, we prove that the iterates converge to a min‐norm solution with respect to the preconditioner if the initial vector is in the range space of the right preconditioned coefficient matrix. Furthermore, we propose a right preconditioned MINRES using symmetric successive over‐relaxation (SSOR) with Eisenstat's trick. Some numerical experiments on semidefinite systems in electromagnetic analysis and so forth indicate that the method is efficient and robust. Finally, we show that the residual norm can be further reduced by restarting the iterations.     

Iterates of the infinitesimal generator and space–time harmonic polynomials of a Markov process

We relate iterates of the infinitesimal generator of a Markov process to space–time harmonic functions. First, we develop the theory for a general Markov process and create a family a space–time martingales. Next, we investigate the special class of subordinators. Combinatorics results on space–time harmonic polynomials and generalized Stirling numbers are developed and interpreted from a probabilistic point of view. Finally, we introduce the notion of pairs of subordinators in duality, investigate the implications on the associated martingales and consider some explicit examples.     

Monotone method for equations describing transport phenomena in a Banach space

In this paper monotone methods have been developed for equations arising in transport processes in a Banach space. This method proves the existence of extremal solutions for such equations. The advantage of the method for such type of equations is that the successive iterates are solutions of the corresponding initial value problems.     

Perturbed projections and subgradient projections for the multiple-sets split feasibility problem

We study the multiple-sets split feasibility problem that requires to find a point closest to a family of closed convex sets in one space such that its image under a linear transformation will be closest to another family of closed convex sets in the image space. By casting the problem into an equivalent problem in a suitable product space we are able to present a simultaneous subgradients projections algorithm that generates convergent sequences of iterates in the feasible case. We further derive and analyze a perturbed projection method for the multiple-sets split feasibility problem and, additionally, furnish alternative proofs to two known results.     

A discrete problem on d-dimensional symmetric weighted median filters

Using a tool-energy of d-dimensional signal sequences taking values 1 or -1, we have completely solved an interesting discrete mathematical problem on d-dimensional symmetric weighted median filters, i.e., when a d-dimensional symmetric weighted median filter is applied iteratively to a real signal sequence, then the limit of the iterates with even index as well as the limit of the iterates with odd index both converge.     

On the iterates of Jackson type operator GS,N in Hilbert space

In this paper we study the limit of the iterates of Jackson type operator. Our results continue the works of Badea [2] and Nagler et al. [9, 10]. The proofs are based on spectral theory of linear operators and are performed at first for Hilbert space and then are extended for some Banach spaces.     

A simple proof of the mean ergodic theorem for nonlinear contractions in Banach spaces

The following theorem is proven:if E is a uniformly rotund Banach space with a Fréchet differentiable norm, C is a bounded nonempty closed convex subset of E, and T: C→C is a contraction, then the iterates {T ⁿx} are weakly almost-convergent to a fixed-point of T. Supported by NSF Grant MCS 76-08217.