On the fast solutions of nonlinear elliptic equations

Summary In a recent paper we described a multi-grid algorithm for the numerical solution of Fredholm's integral equation of the second kind. This multi-grid iteration of the second kind has important applications to elliptic boundary value problems. Here we study the treatment of nonlinear boundary value problems. The required amount of computational work is proportional to the work needed for a sequence of linear equations. No derivatives are required since these linear problems are not the linearized equations.     

A Multi-Grid Algorithm for Stokes Problem

1.IntroductionConsidertheStokesproblemwhereflisaboundeddomalninRd,d=2or3.Since,withinacodeforthenumer-icalsolutionoftheNavier-Stokesequations,oneneedsanefficientStokessolver,themultigridmethodisveryattractiveforthesolutionofthediscreteanalogueof(1.1).BrezziandDouglas[6Jhaveappliedapenaltyprocedurefor(1.1)withtheC'-piecewiselinearelementofvelocityandpressureandachievedanoptimaJconver-gencerate.Inthispaperweestablishamulti-gridalgorithmforthepenaltyprocedureofStokesproblemandshowthattheconve…     

A MULTI-GRID ALGORITHM FOR MIXED PROBLEMS WITH PENALTY BY C°-PIECEWISE LINEAR ELEMENT APPROXIMATION

In this paper we describe a multi-grid algorithm for mixed problems with penalty by the linear finite element approximation. It is proved that the convergence rate of the algorithm is bound ed away from 1 independently of the meshsize. For convenience, we only discuss Jacobi relaxation as smoothing operator in detail.     

Mathematical stencil and its application in finite difference approximation to the poisson equation

The concept of mathematical stencil and the strategy of stencil elimination for solving the finite difference equation is presented,and then a new type of the iteration algo- rithm is established for the Poisson equation.The new algorithm has not only the obvious property of parallelism,but also faster convergence rate than that of the classical Jacobi iteration.Numerical experiments show that the time for the new algorithm is less than that of Jacobi and Gauss-Seidel methods to obtain the same precision,and the computational velocity increases obviously when the new iterative method,instead of Jacobi method,is applied to polish operation in multi-grid method,furthermore,the polynomial acceleration method is still applicable to the new iterative method.     

A new algorithm for total variation based image denoising

We propose a new algorithm for the total variation based on image denoising problem. The split Bregman method is used to convert an unconstrained minimization denoising problem to a linear system in the outer iteration. An algebraic multi-grid method is applied to solve the linear system in the inner iteration. Furthermore, Krylov subspace acceleration is adopted to improve convergence in the outer iteration. Numerical experiments demonstrate that this algorithm is efficient even for images with large signal-to-noise ratio.     

QN THE CONVERGENCE ANALYSIS OF THE NONLINEAR ABS METHODS

In order to complete the convergence theory of nonlinear ABS algorithm, through a careful investigation to the algorithm structure, the author converts the nonlinear ABS algorithm into an inexact Newton method. Based on such equivalent variation, the Kantorovich type convergence of the ABS algorithm is established and the Convergence conditions of the algorithm that only depend on the initial conditions are obtained, which provides a useful basis for the choices of initial points of the ABS algorithm.     

On truncated incomplete decompositions

In the present paper we introduce truncated incomplete decompositions (TrILU) for constant coefficient matrices. This new ILU variant saves most of the memory and work usually needed to compute and store the factorization. Further it improves the smoothing and preconditioning properties of standard ILU-decompositions. Besides describing the algorithm, we give theoretical results concerning stability and convergence as well as the smoothing property and robustness for TrILU smoothing in a multi-grid method. Further, we add numerical results of TrILU as smoother in a multi-grid method and as preconditioner in a pcg-method fully confirming the theoretical results.This work was supported by Deutsche Forschungsgemeinschaft.     

影响阻尼牛顿法收敛性的两个重要参数

对阻尼牛顿算法作了适当的改进,证明了新算法的收敛性.基于新算法,运用计算机代数系统Matlab,研究了迭代次数k,参数对(μ,λ)与初值x0三者间的依赖关系,研究了病态问题在新算法下趋于稳定的渐变(瞬变)过程.数值结果表明:(1)阻尼牛顿迭代中,参数对(μ,λ)与迭代次数k间存在特有的非线性关系;(2)适当的参数对(μ,λ)与阻尼因子α的共同作用能够在迭代中大幅度地降低病态问题的Jacobi阵的条件数,使病态问题逐渐趋于稳定,从而改变原问题的收敛性与收敛速度.     

Analysis of a symplectic difference scheme for a coupled nonlinear Schrödinger system

In general, proofs of convergence and stability are difficult for symplectic schemes of nonlinear equations. In this paper, a symplectic difference scheme is proposed for an initial-boundary value problem of a coupled nonlinear Schrödinger system. An important lemma and an induction argument are used to prove the unique solvability, convergence and stability of numerical solutions. An iterative algorithm is also proposed for the symplectic scheme and its convergence is proved. Numerical examples show the efficiency of the symplectic scheme and the correction of our numerical analysis.     

Convergence analysis of a nonlinear Lagrange algorithm for general nonlinear constrained optimization problems

The convergence analysis of a nonlinear Lagrange algorithm for solving nonlinear constrained optimization problems with both inequality and equality constraints is explored in detail. The estimates for the derivatives of the multiplier mapping and the solution mapping of the proposed algorithm are discussed via the technique of the singular value decomposition of matrix. Based on the estimates, the local convergence results and the rate of convergence of the algorithm are presented when the penalty parameter is less than a threshold under a set of suitable conditions on problem functions. Furthermore, the condition number of the Hessian of the nonlinear Lagrange function with respect to the decision variables is analyzed, which is closely related to efficiency of the algorithm. Finally, the preliminary numericM results for several typical test problems are reported.     

A penalty function method for solving inverse optimal value problem

In order to consider the inverse optimal value problem under more general conditions, we transform the inverse optimal value problem into a corresponding nonlinear bilevel programming problem equivalently. Using the Kuhn–Tucker optimality condition of the lower level problem, we transform the nonlinear bilevel programming into a normal nonlinear programming. The complementary and slackness condition of the lower level problem is appended to the upper level objective with a penalty. Then we give via an exact penalty method an existence theorem of solutions and propose an algorithm for the inverse optimal value problem, also analysis the convergence of the proposed algorithm. The numerical result shows that the algorithm can solve a wider class of inverse optimal value problem.     

On the convergence of multi-grid methods with transforming smoothers

Summary In the present paper we give a convergence theory for multi-grid methods with transforming smoothers as introduced in [31] applied to a general system of partial differential equations. The theory follows Hackbusch's approach for scalar pde and allows a convergence proof for some well-known multi-grid methods for Stokes- and Navier-Stokes equations as DGS by Brandt-Dinar, [5], TILU from [31] and the SIMPLE-methods by Patankar-Spalding, [23].This work was supported in part by Deutsche Forschungsgemeinschaft     

A multi-grid algorithm for mixed problems with penalty

Summary In this paper we describe a multi-grid algorithm for the finite element approximation of mixed problems with penalty by the MINI-element. It is proved that the convergence rate of the algorithm is bounded away from 1 independently of the meshsize and of the penalty parameter. For convenience, we only discuss Jacobi relaxation as smoothing operator in detail.The paper was written during the author's stay at the Ruhr-Universität Bochum and revised by D. Braess after the author's return to China     

层次分析法中判断矩阵一致性修正的新算法

设计了判断矩阵一致性修正的一种新方法,使判断矩阵一致性在每次迭代修正过程中得到最大程度改善,并通过一个非线性规划模型描述每次迭代的过程.同时作者也证明了这种迭代方法具有收敛性,即通过有限次迭代能够达到满意的一致性阈值.最后给出了一个算例,并进行了比较.     

AN EFFECT ITERATION ALGORITHM FOR NUMERICAL SOLUTION OF DISCRETE HAMILTON-JACOBIBELLMAN EQUATIONS

§1Introduction ConsidertheHamilton-Jacobi-Bellmanequation max1≤v≤m[A(v)u(x)-f(v)(x)]=0,x∈Ω(1.1)withtheboundarycondition u(x)=0,x∈Ω(1.2)whereΩisabounded,smoothdomaininEuclideanspaceRd,d∈N;f(v)(x)aregiven functionsfromC2(Ω);A(v)aresecond-orderuniformlyellipticoperatorsoftheform A(v)=-d i,j=1a(v)ij2xixj+di=1b(v)ixi+c(v).(1.3)Intheaboveexpression(1.3)therearecoefficientsa(v)ij,b(v)i,c(v)∈C2(Ω)satisfying,forall1≤v≤m,a(v)ij(x)=a(v)ji(x),1≤i,j≤d,c(v)≥c0≥0,x∈Ω,a…     

Convergence of a nonlinear wavelet algorithm for the solution of PDEs

We prove convergence of an adaptive wavelet algorithm for the solution of elliptic PDEs, which combines Richardson type iterations with nonlinear projection steps.     

Monotone-iterative method for mixed boundary value problems for generalized difference equations with “maxima”

In this paper the authors investigate special type of difference equations which involve both delays and the maximum value of the unknown function over a past time interval. This type of equations is used to model a real process which present state depends significantly on its maximal value over a past time interval. An appropriate mixed boundary value problem for the given nonlinear difference equation is set up. An algorithm, namely, the monotone iterative technique is suggested to solve this problem approximately. An important feature of our algorithm is that each successive approximation of the unknown solution is equal to the unique solution of an appropriately constructed initial value problem for a linear difference equation with “maxima”, and a formula for its explicit form is given. Also, each approximation is a lower/upper solution of the given nonlinear boundary value problem. Several numerical examples are considered to illustrate the practical application of the suggested algorithm.     

Multi-grid methods for Hamilton-Jacobi-Bellman equations

Summary In this paper we develop multi-grid algorithms for the numerical solution of Hamilton-Jacobi-Bellman equations. The proposed schemes result from a combination of standard multi-grid techniques and the iterative methods used by Lions and mercier in [11]. A convergence result is given and the efficiency of the algorithms is illustrated by some numerical examples.     

Perturbed iterative solution of nonlinear equations with applications to fluid dynamics

In this work a technique has been developed to solve a set of nonlinear equations with the assumption that a solution exists. The algorithm involves nonlinear Gauss-Seidel iteractions and at each iteration the value of the iterate is added to a predetermined perturbation parameter which is computed in terms of quantities already known. This perturbation parameter has two properties: (i) it determines the mode of convergence, that means it shows how many more computations are required so that convergence may be achieved, and (ii) it accelerates the rate of convergence. The algorithm is computationally simple. Several nonlinear equations have been studied. The results seem to be encouraging.     

A numerical algorithm for the nonlinear Kirchhoff string equation

The initial boundary value problem is considered for the dynamic string equation . Its solution is found by means of an algorithm, the constituent parts of which are the Galerkin method, the modified Crank-Nicolson difference scheme used to perform approximation with respect to spatial and time variables, and also a Picard type iteration process for solving the system of nonlinear equations obtained by discretization. Errors of the three parts of the algorithm are estimated and, as a result, its total error estimate is obtained.