Constructing fixed rank optimal estimators with method of best recurrent approximations

We propose a new approach which generalizes and improves principal component analysis (PCA) and its recent advances. The approach is based on the following underlying ideas. PCA can be reformulated as a technique which provides the best linear estimator of the fixed rank for random vectors. By the proposed method, the vector estimate is presented in a special quadratic form aimed to improve the error of estimation compared with customary linear estimates. The vector is first pre-estimated from the special iterative procedure such that each iterative loop consists of a solution of the unconstrained nonlinear best approximation problem. Then, the final vector estimate is obtained from a solution of the constrained best approximation problem with the quadratic approximant. We show that the combination of these techniques allows us to provide a new nonlinear estimator with a significantly better performance compared with that of PCA and its known modifications.     

Method of Best Successive Approximations for Nonlinear Operators

We present a new approach to the approximation of nonlinear operators in probability spaces. The approach is based on a combination of the specific iterative procedure and the best approximation problem solution with a quadratic approximant. We show that the combination of these new techniques allow us to build a computationally efficient and flexible method. The algorithm of the method and its application to the optimal filtering of stochastic signals are given.     

Iterative solution of a coupled mixed and standard Galerkin discretization method for elliptic problems

In this paper, we consider approximation of a second‐order elliptic problem defined on a domain in two‐dimensional Euclidean space. Partitioning the domain into two subdomains, we consider a technique proposed by Wieners and Wohlmuth [9] for coupling mixed finite element approximation on one subdomain with a standard finite element approximation on the other. In this paper, we study the iterative solution of the resulting linear system of equations. This system is symmetric and indefinite (of saddle‐point type). The stability estimates for the discretization imply that the algebraic system can be preconditioned by a block diagonal operator involving a preconditioner for H (div) (on the mixed side) and one for the discrete Laplacian (on the finite element side). Alternatively, we provide iterative techniques based on domain decomposition. Utilizing subdomain solvers, the composite problem is reduced to a problem defined only on the interface between the two subdomains. We prove that the interface problem is symmetric, positive definite and well conditioned and hence can be effectively solved by a conjugate gradient iteration. Copyright © 2001 John Wiley & Sons, Ltd.     

On iterative optimization ol structured Markov decision processes with discounted rewards

The paper gives a survey on solution techniques for Markov decision processes with respect to the total reward criterion. We will discuss briefly a number of problem structures which guarantee that the optimal policy possesses a specific structure which can be exploited in numerical solution procedures. However, the main emphasis is on iterative methods. It is shown by examples that the effect of a number of modifications of the standard iterative method, which are advocated in the literature, is limited in some realistic situations. Numerical evidence is provided to show that exploiting the structure of a problem under consideration of ten yields a more substantial reduction of the required computational effort than some of the existing acceleration procedures.

We advocate that this structure should be analyzed and used in choosing the appropriate solution procedure. The appropriate procedure might be composed on one hand by blending several of the acceleration concepts that are described in literature. On the other hand it should exploit the structure of optimal policies. This latter can often be done by using monotonicity properties of the computed value vector or policy. To illustrate the influence of the structure of a problem and if available, the structure of optimal policies, we sketch and solve four test problems with several successive approximation methods. In the final part of the paper, the required computational efforts are compared.     

Preconditioning techniques for the iterative solution of scattering problems

We consider a time-harmonic electromagnetic scattering problem for an inhomogeneous medium. Some symmetry hypotheses on the refractive index of the medium and on the electromagnetic fields allow to reduce this problem to a two-dimensional scattering problem. This boundary value problem is defined on an unbounded domain, so its numerical solution cannot be obtained by a straightforward application of usual methods, such as for example finite difference methods, and finite element methods. A possible way to overcome this difficulty is given by an equivalent integral formulation of this problem, where the scattered field can be computed from the solution of a Fredholm integral equation of second kind. The numerical approximation of this problem usually produces large dense linear systems. We consider usual iterative methods for the solution of such linear systems, and we study some preconditioning techniques to improve the efficiency of these methods. We show some numerical results obtained with two well known Krylov subspace methods, i.e., Bi-CGSTAB and GMRES.     

The use of Chebyshev series for approximate analytic solution of ordinary differential equations

Application of Chebyshev series to solve ordinary differential equations is described. This approach is based on the approximation of the solution to a given Cauchy problem and its derivatives by partial sums of shifted Chebyshev series. The coefficients of the series are determined by an iterative process using Markov quadrature formulas. It is shown that the proposed approach can be applied to formulate an approximate analytical method for solving Cauchy problems. A number of examples are considered to illustrate the obtaining of approximate analytical solutions in the form of partial sums of shifted Chebyshev series.     

Optimal Recursive Estimation of Raw Data

We present a new approach to the optimal estimation of random vectors. The approach is based on a combination of a specific iterative procedure and the solution of a best approximation problem with a polynomial approximant. We show that the combination of these new techniques allow us to build a computationally effective and flexible estimator. The strict justification of the proposed technique is provided. This work was supported by the Australian Research Council under the ARC Large Grant Scheme.     

Minimal residual methods for large scale Lyapunov equations

Projection methods have emerged as competitive techniques for solving large scale matrix Lyapunov equations. We explore the numerical solution of this class of linear matrix equations when a Minimal Residual (MR) condition is used during the projection step. We derive both a new direct method, and a preconditioned operator-oriented iterative solver based on CGLS, for solving the projected reduced least squares problem. Numerical experiments with benchmark problems show the effectiveness of an MR approach over a Galerkin procedure using the same approximation space.     

The regularizing effect of the Golub-Kahan iterative bidiagonalization and revealing the noise level in the data

Regularization techniques based on the Golub-Kahan iterative bidiagonalization belong among popular approaches for solving large ill-posed problems. First, the original problem is projected onto a lower dimensional subspace using the bidiagonalization algorithm, which by itself represents a form of regularization by projection. The projected problem, however, inherits a part of the ill-posedness of the original problem, and therefore some form of inner regularization must be applied. Stopping criteria for the whole process are then based on the regularization of the projected (small) problem. In this paper we consider an ill-posed problem with a noisy right-hand side (observation vector), where the noise level is unknown. We show how the information from the Golub-Kahan iterative bidiagonalization can be used for estimating the noise level. Such information can be useful for constructing efficient stopping criteria in solving ill-posed problems.     

A combined Lagrangian, linear programming, and implication heuristic for large-scale set partitioning problems

Given a finite ground set, a set of subsets, and costs on the subsets, the set partitioning problem is to find a minimum cost partition of the ground set. Many combinatorial optimization problems can be formulated as set partitioning problems. We present an approximation algorithm that produces high-quality solutions in an acceptable amount of computation time. The algorithm is iterative and combines problem size-reduction techniques, such as logical implications derived from feasibility and optimality conditions and reduced cost fixing, with a primal heuristic based on cost perturbations embedded in a Lagrangian dual framework, and cutting planes. Computational experiments illustrate the effectiveness of the approximation algorithm.     

半线性椭圆问题Petrov-Galerkin逼近及亏量迭代

本文考虑了二阶半线性椭圆问题的Petrov-Galerkin逼近格式,用双二次多项式空间作为形函数空间,用双线性多项式空间作为试探函数空间,证明了此逼近格式与标准的二次有限元逼近格式有同样的收敛阶.并且根据插值算子的逼近性质,进一步证明了半线性有限元解的亏量迭代序列收敛到Petrov-Galerkin解.     

Numerical performance of parallel group explicit solvers for the solution of fourth order elliptic equations

Many applications in applied mathematics and engineering involve numerical solutions of partial differential equations (PDEs). Various discretisation procedures such as the finite difference method result in a problem of solving large, sparse systems of linear equations. In this paper, a group iterative numerical scheme based on the rotated (skewed) five-point finite difference discretisation is proposed for the solution of a fourth order elliptic PDE which represents physical situations in fluid mechanics and elasticity. The rotated approximation formulas lead to schemes with lower computational complexities compared to the centred approximation formulas since the iterative procedure need only involve nodes on half of the total grid points in the solution domain. We describe the development of the parallel group iterative scheme on a cluster of distributed memory parallel computer using Message-Passing Interface (MPI) programming environment. A comparative study with another group iterative scheme derived from the centred difference formula is also presented. A detailed performance analysis of the parallel implementations of both group methods will be reported and discussed.     

Weighted iterative solutions of linear differential equations and heat conduction of ideal gases in moment theory

An iterative method is proposed to find a particular solution of a system of linear differential equations, in the form of a fixed-point problem, with no boundary conditions. To circumvent the unboundedness of differential operators, iterative approximation with gradually decreasing weight is used. Conditions for convergence that can easily be checked in numerical iterations are established. Furthermore, for the numerical iterative scheme, uniqueness and stability theorems are proved. These results are applied to heat conduction of ideal gases in moment theory.     

Weighted iterative solutions of linear differential equations and heat conduction of ideal gases in moment theory

An iterative method is proposed to find a particular solution of a system of linear differential equations, in the form of a fixed-point problem, with no boundary conditions. To circumvent the unboundedness of differential operators, iterative approximation with gradually decreasing weight is used. Conditions for convergence that can easily be checked in numerical iterations are established. Furthermore, for the numerical iterative scheme, uniqueness and stability theorems are proved. These results are applied to heat conduction of ideal gases in moment theory.     

THE DEFECT ITERATION OF THE FINITE ELEMENT FOR ELLIPTIC BOUNDARY VALUE PROBLEMS AND PETROV-GALERKIN APPROXIMATION

1.IntroductionFranketc.of.[l]establishedtheiterateddefectcorrectionschemeforfiniteelemelltofellipticboundaryproblems.FOrlinearellipticboundaryvalueproblem[2--5]havediscllssedtheefficiencyoftheschemebyusillgsuperconvergenceandasymptoticexpansion"lidertheco…     

On a stopping rule for iterative orthogonalization of symmetric matrices

In this paper we consider three versions of Kovarik's iterative orthogonalization algorithms, for approximating the minimal norm solution of symmetric least squares problems. Although the convergence of these algorithms is linear, in practical applications we observed that a too big number of iterations can dramatically deteriorate the already obtained approximation. In this respect we analyse the above mentioned Kovarik–like methods according to the modifications they make on the “machine zero” eigenvalues of the problem (symmetric) matrix. We establish a theoretical almost optimal formula for the number of iterations necessary to obtain an enough accurate approximation, as well as to avoid the above mentioned troubles. Experiments on collocation discretization of a Fredholm first kind integral equation ilustrate the efficiency of our considerations. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Using approximate inverses in algebraic multilevel methods

Summary. This paper deals with the iterative solution of large sparse symmetric positive definite systems. We investigate preconditioning techniques of the two-level type that are based on a block factorization of the system matrix. Whereas the basic scheme assumes an exact inversion of the submatrix related to the first block of unknowns, we analyze the effect of using an approximate inverse instead. We derive condition number estimates that are valid for any type of approximation of the Schur complement and that do not assume the use of the hierarchical basis. They show that the two-level methods are stable when using approximate inverses based on modified ILU techniques, or explicit inverses that meet some row-sum criterion. On the other hand, we bring to the light that the use of standard approximate inverses based on convergent splittings can have a dramatic effect on the convergence rate. These conclusions are numerically illustrated on some examples Received March 3, 1997 / Revised version received July 16, 1997     

Banach空间中微分方程的弱Carathodory解

本文在一般Banach空间中讨论微分方程的初值问题：u＇＝f（t，u），u（0）＝x0．设f（t，u）不连续，仅满足所谓弱Caratheodory条件，但仍证明了初值问题的解可由迭代序列的一致极限得到，并给出了逼近解的迭代序列的误差估计．对周期过值问题得到了类似的结果．     

Iterative methods for finding the boundaries of unrecovered viscoplastic oil in multilayer beds

We suggest a generalized statement of the problem of finding the boundaries of limit-equilibrium unrecovered viscoplastic oil in multilayer beds in the form of a mixed variational inequality. We analyze the solvability of the problem. For its solution, we suggest an iterative method whose each step can essentially be reduced to the solution of the Dirichlet problem for the Poisson equation.     

A methodology for solving chemical equilibrium systems

This paper describes a methodology for solving chemical equilibrium systems. The methodology is especially appropriate when many systems with the same structure must be solved quickly, as in finite-difference models of fluid flow and combustion. The approach features identifying a “canonical form” for such systems and exploiting this canonical form to effect a preliminary algebraic reduction. Then numerical scaling and iterative solution techniques are evoked. Both homotopy continuation and a variant of Newton's method are effective solution methods. This methodology is a significant advance over previous approaches to solving chemical equilibrium systems. The problem of solving such systems has heretofore been regarded as challenging; solution techniques have tended to emphasize case-by-case analyses and hit-or-miss numerical methods. We show that the problem can be solved by a unified approach, quickly and reliably.