Defect Correction

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
of 19

Please download to get full document.

View again

Defect Correction Methods in CFD basic principle and application
  Numer. Math. 29, 425-443 (1978) NumerischeMathemaUk 9 by Springer-Verlag 1978 The Defect Correction Principleand Discretization Methods Hans J. Stetter*Institut ftir Numerische Mathematik der Technischen Universitfit,Gusshausstr. 27, A-1040 Wien, AustriaSummary. Recently, a number of closely related techniques for error esti-mation and iterative improvement in discretization algorithms have beenproposed. In this article, we expose the common structural principle of allthese techniques and exhibit the principal modes of its implementation in adiscretization context. Subject Classifications. AMS(MOS): 65J05, 65L99; CR: 5.17. 1. Introduction During the past years, there have been numerous attempts to estimate the errorof discretization methods or, equivalently, to improve the accuracy of theirresults. Two approaches have proved to be widely applicable: RichardsonExtrapolation and Deferred Correction. Both can be used in an iterativefashion; the most notable difference between the two is the fact that DeferredCorrection proceeds on the srcinal grid of the discretization while RichardsonExtrapolation needs repeated grid refinement and yet produces answers on thesrcinal grid only.Recently a further technique of iterative improvement has been suggested.Presumably it has been used informally on various occasions; its conscious use-without iteration and for error estimations only-was promoted by Za-dunaisky in [1-3] and at the 1973 Dundee conference; following this meetingStetter [4] formalized the procedure and conceived its iterative application.Detailed analyses of particular applications were then made by Frank [6, 7],Frank and Ueberhuber [8, 9, 11] and Frank, Hertling and Ueberhuber [10, 12].Lindberg [16], in generalizing the Deferred Correction approach, independentlyarrived at one version of the general technique. While Stetter had suggested tocall the technique Differential Correction, Frank and Ueberhuber introduced* Written during a sabbatical stay at Oxford Universitypartially supported by the British Science and Research Council0029-599 X/78/0029/0425/$03.80  426 H.J. Stetterthe term Defect Correction. In Section 5 of this paper we shall see that thewellknown Iterated Deferred Correction (or Difference Correction) technique ofFox (e.g. [13]) and Pereyra (e.g. [14, 15]) can be interpreted as a special case ofthe general principle of Iterative Updating Defect Correction.In order to see the general principle and its ramifications more clearly, weshall study it at first without reference to discretizations or to differentialequations. Actually, Iterative Defect Correction may be a very powerful tech-nique in other areas of Mathematics as well. The Examples in the following areonly of a demonstrative nature. Realistic implementations of Defect Correctionhave been discussed in many of the quoted references and numerical results havealso been presented there. 2. The Basic Principle Consider two normed linear spaces E and E ~ and a continuous (generally non-linear) mapping F: E--,E ~ Let F be bijective between a domain XcE and adomain YcE ~ with 0~ Y, and assume that in all our operations we shall neverleave these domains (in an application this has to be checked). Our aim is to finda good approximation to the unique solution x*sX of Fx=O (2.1)with the aid of an approximate inverse G: Y~X; C, is also assumed to bebijective and continuous. (~ may be considered as the solution operator of anapproximationFx=0 (2.2)of (2.1).To obtain an estimate for the error of Xo:=G0, we form the defect do: =Fxo and compute ffo:=Gdo (see Fig. 1). Thus Y0 is the approximate solution of theequation Fx = d o which is a neighboring problem of (2.1) whose exact solutionx o is known. If we assume that the error generated by our approximate solutionoperator G is nearly the same for the two problems we obtainx o -x* ~X o -x o. (2.3)This idea may either be used to estimate Xo-X* by (2.3), or to obtain animproved approximation (see Fig. 1) xl . =Xo-(~o-Xo). But then the process may be repeated (i=0, 1, 2 .... ): ~i'.= GFx i = Gd,, (2.4) xi + 1 = xi - (xi - Xo) = (I - GF) x~ + x o ; (2.5)this is the principle of Iterative Defect Correction (IDeC), version A.  The Defect Correction Principle and Discretization Methods 427Fig. 1. Defect correction, version A xl ,'J~/ ./. ~, l xo.Wr/~ F .!do Fig. 2. Defect correction, version B x* of (2.1) is a fixed point of (2.5) (remember that Xo,=G0); therefore (2.5)will converge to x* if I-GF is a contraction in X, and the rate of convergencewill depend on the (local) Lipschitz constant. Obviously, P must reflect the localbehavior of F sufficiently well.The defect do=Fx o may also be used in another way: We may attempt toobtain a better approximation to the unique element l* e Y which satisfiesl* = x*. (2.6)By virtue of the neighbouring problem idea (see Fig. 2) l~:= -d o = l o- d o is abetter approximation to l* than the initial value lo=0. Thus x~:=Gl 1 permitsthe estimate Xo-X 1 for Xo-X*; also the process may be continued iteratively(i=0, 1, 2 ... ): li+ 1 :=li-di=li-Fxi, (2.7)xl + 1: = G ti + i- (2.8)This is version B of the IDeC principle (cf. Fig. 2); it was already suggested inStetter [4].When we substitute (2.8) into (2.7) we obtainli+ 1: = (I- FG) li (2.9)which establishes version B as a dual of version A (cf. (2.5)); if we had startedfrom Fx=lo, lo:~O we would have had to add l o in (2.7) and (2.9) and theduality would have been complete.Version B may also be written as an iteration in X; (2.8) and (2.7) imply x, + 1: = G(/, -di) = d(F - F) x i ; (2.10)this may be confronted with version A in the form (cf. (2.5)) x i+ 1: = xi- (GFx i- GO) =(dF- GF) x i + dO. (2.11)From (2.10) and (2.11) it is obvious that the two versions are equivalent if dis an affine mapping0y = G0+ Goy, d~s [Y, X]; (2.12)  428 H.J. Stetter F need not be linear for this equivalence. With a non-linear G, on the otherhand, the sequences {xl} obtained from versions A and B will generally differ.If G is Frechet-differentiable, one may wish to linearize'' it, i.e. replace it by(2.12), with G~. = G'(0). This causes the two versions to coincide. Examples. 1) Iterative Improvement in Linear Algebraic Equations: X = Y= ~ ; Fy=Ax-b; CJy is the result of applying the numerically obtained triangulardecomposition of A to the righthand side b + y.2) Simplified Newton method (in Banach spaces): Let F: X ~ Y be Frechet-differentiable and take Fx:=Fz+F'(z)(x-z), z~X fixed, so that Gy:=z- F' (z)- 1(F z - y). Then (2.10) and (2.11) become x i + 1: = xi - F' (z)- 1 F x i .3) Defect correction does not depend on local linearization: Consider thenon-linear boundary value problema) x (t)-eX(~ on (-1, +1), (2.13)b) x(- 1)=x(+ 1)=0,to define F: Cr -- 1, + 1-1--. CI--1, + 1] x ~2. To obtain an approximate prob-lem, take an approximation for ex in the interval -0.4 < x_< 0 (where x*(t) wiltlie), say eX~0.99+0.81x, and define (2.2) bya) x (t)-O.81x(t)-0.99=O on (-1, +1),(2.14)b) x(-1)=x(+l)=0;(2.14) is not a local linearization of (2.13). Since the Green's function of thedifferential operator in (2.14) is known, the integral representation of G can beused to compute the x~, i=0, 1,2 .... at least numerically. The sequence con-verges quickly to the solution x* of (2.13).Note that the linearity of (2.14) is not required by the method but it isconvenient for the evaluation of G. 3. Approximate Solution in a Subspaee As a step towards studying IDeC in a discretization setting, we now assume thatis not one-to-one between Y and X but maps Y into a proper subspace of Ewhose intersection with X we call ~, and that x*6~. The image of ~ under F wedenote by H (Fig. 3). H is not a linear manifold in Y if F is nonlinear. (Tovisualize this situation assume that E and E ~ are spaces of continuous functionsbut that G always produces a polynomial of degree < N.) The restriction of G toH is assumed to be bijective from H to ~; the restriction of F to ~ is naturallybijective from ~ to H.Figure 3 shows that version A of IDeC may be carried out as previouslysince ~ is a domain in a linear space. With ~o=G0 (greek letters denoteelements in ~), (2.5) becomes {i+ 1: = (I- GF) ~i + 4o ; (3.1)
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks