Finite element method for a nonsmooth elliptic equation

In this paper, we study the finite element method for a non-smooth elliptic equation. Error analysis is presented, including a priori and a posteriori error estimates as well as superconvergence analysis. We also propose two algorithms for solving the underlying equation. Numerical experiments are employed to confirm our error estimations and the efficiency of our algorithms.     

Properties of Solutions for a Functional Equation Arising in Dynamic Programming

This paper is concerned with a new functional equation arising in dynamic programming of multistage decision processes. Utilizing the Banach fixed point theorem and iterative algorithms, we prove the existence, uniqueness, and iterative approximations of solutions for the functional equation in Banach spaces and a complete metric space, respectively. Some error estimates between the iterative sequences generated by iterative algorithms and the solutions are discussed. Five examples are constructed to illustrate the results presented in this paper.     

Multilevel algorithms for ill-posed problems

Summary In this paper new multilevel algorithms are proposed for the numerical solution of first kind operator equations. Convergence estimates are established for multilevel algorithms applied to Tikhonov type regularization methods. Our theory relates the convergence rate of these algorithms to the minimal eigenvalue of the discrete version of the operator and the regularization parameter. The algorithms and analysis are presented in an abstract setting that can be applied to first kind integral equations.Dedicated to Jim Bramble on the occasion of his sixtieth birthday     

Study of weighted Monte Carlo algorithms with branching

Various weighted algorithms for numerical statistical simulation are formulated and studied. The trajectory of an algorithm branches when the current weighting factor exceeds unity. As a result, the weight of an individual branch does not exceed unity and the variance of the estimate for the computed functional is finite. The unbiasedness and finiteness of the variance of estimates are analyzed using the recurrence “partial“ averaging method formulated in this study. The estimation of the particle reproduction factor and solutions to the Helmholtz equation are considered as applications. The comparative complexity of the algorithms is examined using a test problem. The variances of weighted algorithms with branching as applied to integral equations with power nonlinearity are analyzed.     

Estimation of the reliability of a classification algorithm as based on a new information model

A new approach to the estimation of the reliability of classification algorithms is proposed. The approach is based on an unconventional information model of such algorithms. Examples of new estimates are given, which are compared with usual statistical estimates.     

Fully discrete finite element approximations of the forced Fisher equation

We consider fully discrete finite element approximations of the forced Fisher equation that models the dynamics of gene selection/migration for a diploid population with two available alleles in a multidimensional habitat and in the presence of an artificially introduced genotype. Finite element methods are used to effect spatial discretization and a nonstandard backward Euler method is used for the time discretization. Error estimates for the fully discrete approximations are derived by applying the Brezzi-Rappaz-Raviart theory for the approximation of a class of nonlinear problems. The approximation schemes and error estimates are applicable under weaker regularity hypotheses than those that are typically assumed in the literature. The algorithms and analyses, although presented in the concrete setting of the forced Fisher equation, also apply to a wide class of semilinear parabolic partial differential equations.     

Iterative algorithms for nonlinear problems in remote sensing

First a brief review of the Backus and Gilbert method for the linear problems is given. Then a comprehensive presentation of iterative algorithms for constructing approximate solutions of nonlinear problems from erroneous inadequate data is given. Proofs of convergence and error estimates of these iterative algorithms are obtained. It is found that locally the limit of the iterates does not satisfy the original nonlinear operator equation, but a somewhat different nonlinear equation which depends on the initial iterate. A nonlinear radiative transfer equation in remote sensing of the atmospheric temperature profiles is used as an example to demonstrate the applicability of the iterative algorithms. Finally, a discussion of the present status of research in this domain and some personal views on what should be the useful lines for future research is given.     

On solving sparse algebraic equations over finite fields

A system of algebraic equations over a finite field is called sparse if each equation depends on a small number of variables. In this paper new deterministic algorithms for solving such equations are presented. The mathematical expectation of their running time is estimated. These estimates are at present the best theoretical bounds on the complexity of solving average instances of the above problem. In characteristic 2 the estimates are significantly lower the worst case bounds provided by SAT solvers.     

Estimates for multigrid methods based on red-black Gauss-Seidel smoothings

Summary TheMGR[v] algorithms of Ries, Trottenberg and Winter, the Algorithms 2.1 and 6.1 of Braess and the Algorithm 4.1 of Verfürth are all multigrid algorithms for the solution of the discrete Poisson equation (with Dirichlet boundary conditions) based on red-black Gauss-Seidel smoothing. Both Braess and Verfürth give explicit numerical upper bounds on the rate of convergence of their methods in convex polygonal domains. In this work we reconsider these problems and obtain improved estimates for theh–2h Algorithm 4.1 as well asW-cycle estimates for both schemes in non-convex polygonal domains. The proofs do not depend on the strengthened Cauchy inequality.Sponsored by the Air Force Office of Scientific Research under Contract No. AFOSR-86-0163     

Algorithms for numerical solution of the modified equal width wave equation using collocation method

Quintic B-spline collocation algorithms for numerical solution of the modified equal width wave (MEW) equation have been proposed. The algorithms are based on Crank–Nicolson formulation for time integration and quintic B-spline functions for space integration. Quintic B-spline collocation method over the finite intervals is also applied to the time split MEW equation and space split MEW equation. Results for the three algorithms are compared by studying the propagation of the solitary wave, interaction of the solitary waves, wave generation and birth of solitons.     

Application of Neumann-Ulam scheme to solving the first boundary value problem for a parabolic equation

Statistical estimates of the solutions of boundary value problems for parabolic equations with constant coefficients are constructed on paths of random walks. The phase space of these walks is a region in which the problem is solved or the boundary of the region. The simulation of the walks employs the explicit form of the fundamental solution; therefore, these algorithms cannot be directly applied to equations with variable coefficients. In the present work, unbiased and low-bias estimates of the solution of the boundary value problem for the heat equation with a variable coefficient multiplying the unknown function are constructed on the paths of a Markov chain of random walk on balloids. For studying the properties of the Markov chains and properties of the statistical estimates, the author extends von Neumann-Ulam scheme, known in the theory of Monte Carlo methods, to equations with a substochastic kernel. The algorithm is based on a new integral representation of the solution to the boundary value problem.     

The Design and Analysis of Benchmark Experiments

The assessment of the performance of learners by means of benchmark experiments is an established exercise. In practice, benchmark studies are a tool to compare the performance of several competing algorithms for a certain learning problem. Cross-validation or resampling techniques are commonly used to derive point estimates of the performances which are compared to identify algorithms with good properties. For several benchmarking problems, test procedures taking the variability of those point estimates into account have been suggested. Most of the recently proposed inference procedures are based on special variance estimators for the cross-validated performance. We introduce a theoretical framework for inference problems in benchmark experiments and show that standard statistical test procedures can be used to test for differences in the performances. The theory is based on well-defined distributions of performance measures which can be compared with established tests. To demonstrate the usefulness in practice, the theoretical results are applied to regression and classification benchmark studies based on artificial and real world data.     

Blow-up time for solutions to some nonlinear Volterra integral equations

The problem of the estimating of a blow-up time for solutions of Volterra nonlinear integral equation with convolution kernel is studied. New estimates, lower and upper, are found and, moreover, the procedure for the improvement of the lower estimate is presented. Main results are illustrated by examples. The new estimates are also compared with some earlier ones related to a shear band model.     

On mixed finite element approximations of shape gradients in shape optimization with the Navier–Stokes equation

For shape optimization of fluid flows governed by the Navier–Stokes equation, we investigate effectiveness of shape gradient algorithms by analyzing convergence and accuracy of mixed finite element approximations to both the distributed and boundary types of shape gradients. We present convergence analysis with a priori error estimates for the two approximate shape gradients. The theoretical analysis shows that the distributed formulation has superconvergence property. Numerical results with comparisons are presented to verify theory and show that the shape gradient algorithm based on the distributed formulation is highly effective and robust for shape optimization.     

An adaptive finite element method for Fredholm integral equations of the first kind and its verification on experimental data

We propose an adaptive finite element method for the solution of a linear Fredholm integral equation of the first kind. We derive a posteriori error estimates in the functional to be minimized and in the regularized solution to this functional, and formulate corresponding adaptive algorithms. To do this we specify nonlinear results obtained earlier for the case of a linear bounded operator. Numerical experiments justify the efficiency of our a posteriori estimates applied both to the computationally simulated and experimental backscattered data measured in microtomography.     

Adaptive multilevel methods in space and time for parabolic problems-the periodic case

The aim of this paper is to display numerical results that show the interest of some multilevel methods for problems of parabolic type. These schemes are based on multilevel spatial splittings and the use of different time steps for the various spatial components. The spatial discretization we investigate is of spectral Fourier type, so the approximate solution naturally splits into the sum of a low frequency component and a high frequency one. The time discretization is of implicit/explicit Euler type for each spatial component. Based on a posteriori estimates, we introduce adaptive one-level and multilevel algorithms. Two problems are considered: the heat equation and a nonlinear problem. Numerical experiments are conducted for both problems using the one-level and the multilevel algorithms. The multilevel method is up to 70% faster than the one-level method.

     

The computation of Lagrange-multiplier estimates for constrained minimization

Almost all efficient algorithms for constrained optimization require the repeated computation of Lagrange-multiplier estimates. In this paper we consider the difficulties in providing accurate estimates and what tests can be made in order to check the validity of the estimates obtained. A variety of formulae for the estimation of Lagrange multipliers are derived and their respective merits discussed. Finally the role of Lagrange multipliers within optimization algorithms is discussed and in addition to other results, it is shown that some algorithms are particularly sensitive to errors in the estimates.     

γ-条件下变形Chebyshev迭代方法的收敛性及其应用

在sm a le点估计理论引导下,利用优序列方法,研究γ-条件下,变形chebyshev迭代方法在求解Banach空间中非线性方程F(x)=0时的收敛性问题,并给出了误差估计,而且通过一个积分方程实例比较了它和N ew ton法,导数超前计值的变形N ew ton法,避免导数求逆的变形N ew ton法的每步误差.     

The convergence of V-cycle multigrid algorithms for axisymmetric Laplace and Maxwell equations

We investigate some simple finite element discretizations for the axisymmetric Laplace equation and the azimuthal component of the axisymmetric Maxwell equations as well as multigrid algorithms for these discretizations. Our analysis is targeted at simple model problems and our main result is that the standard V-cycle with point smoothing converges at a rate independent of the number of unknowns. This is contrary to suggestions in the existing literature that line relaxations and semicoarsening are needed in multigrid algorithms to overcome difficulties caused by the singularities in the axisymmetric Maxwell problems. Our multigrid analysis proceeds by applying the well known regularity based multigrid theory. In order to apply this theory, we prove regularity results for the axisymmetric Laplace and Maxwell equations in certain weighted Sobolev spaces. These, together with some new finite element error estimates in certain weighted Sobolev norms, are the main ingredients of our analysis.

     

Economical Iterative Algorithms for Solving Stationary Problems of Mathematical Physics

We construct and investigate additive iterative methods of complete approximation for solving stationary problems of mathematical physics. We prove the convergence of the proposed methods and obtain error estimates without the requirement of commutativity of the decomposition operators. We provide the results of a computational experiment for a three-dimensional boundary-value problem. We consider possible generalizations of algorithms for equations with mixed derivatives and Navier–Stokes equation systems.