- Home
- Documents
*GLOBAL ASYMPTOTIC BEHAVIOR OF ITERATIVE ASYMPTOTIC BEHAVIOR OF ITERATIVE IMPLICIT SCHEMES* ... type*

prev

next

out of 34

View

217Download

0

Embed Size (px)

NASA-CR-202479

International Journal of Bifurcation and Chaos, Vol. 4, No. 6 (1994) 1579-1611

(_) World Scientific Publishing Company

Y//-.

.- .j

GLOBAL ASYMPTOTIC BEHAVIOR OF

ITERATIVE IMPLICIT SCHEMES*

H. C. YEE

NASA Ames Research Center, Moffett Field, CA 94035, USA

P. K. SWEBY

University of Reading, Whiteknights, Reading RG6 PAX, England

Received January 14, 1994; Revised March 16, 1994

The global asymptotic nonlinear behavior of some standard iterative procedures in solvingnonlinear systems of algebraic equations arising from four implicit linear multistep methods

(LMMs) in discretizing three models of 2 2 systems of first-order autonomous nonlinear

ordinary differential equations (ODEs) is analyzed using the theory of dynamical systems. Theiterative procedures include simple iteration and full and modified Newton iterations. The

results are compared with standard Runge-Kutta explicit methods, a noniterative implicit

procedure, and the Newton method of solving the steady part of the ODEs. Studies showedthat aside from exhibiting spurious asymptotes, all of the four implicit LMMs can change the

type and stability of the steady states of the differential equations (DEs). They also exhibit adrastic distortion but less shrinkage of the basin of attraction of the true solution than standard

nonLMM explicit methods. The simple iteration procedure exhibits behavior which is similar

to standard nonLMM explicit methods except that spurious steady-state numerical solutionscannot occur. The numerical basins of attraction of the noniterative implicit procedure mimic

more closely the basins of attraction of the DEs and are more efficient than the three iterative

implicit procedures for the four implicit LMMs. Contrary to popular belief, the initial data

using the Newton method of solving the steady part of the DEs may not have to be close to the

exact steady state for convergence. These results can be used as an explanation for possiblecauses and cures of slow convergence and nonconvergence of steady-state numerical solutions

when using an implicit LMM time-dependent approach in computational fluid dynamics.

1. Background and Objective

It has been shown recently by the authors and

others [Yee et al., 1991; Yee & Sweby, 1992;

Lafon & Yee, 1991; Lafon & Yee, 1992; Griffiths

et al., 1992a,b; Sweby & Yee, 1991; Yee et al.,

1992; Mitchell & Griffiths, 1985; Iserles, 1988;

Iserles et al., 1990; Stuart, 1989; Dieci & Estep,

1990] that the dynamics of the numerical dis-

cretizations of nonlinear differential equations

(DEs) can differ significantly from that of the

original DEs themselves. For example, it was shown

in Yee et al. [1991], Yee & Sweby [1992], and Lafon

& Yee [1991, 1992] that the discretizations can pos-

sess spurious steady-state numerical solutions and

*Written version of the paper presented at the SIAM Conference on Applications of Dynamical Systems, October 15-19, 1992,Salt Lake City, Utah; a condensed version will appear in the Proceedings of the Chaotic Numerics Workshop, July 12-16,1993, Deakin University, Geelong, Australia.

1579

https://ntrs.nasa.gov/search.jsp?R=19970002975 2018-07-16T05:13:31+00:00Z

1580 H. C. Yee,_ P. K. Sweby

spurious asymptotes which do not satisfy the orig-

inal DEs. These spurious numerical solutions may

be stable or unstable and may occur both below and

above the linearized stability limit of the numer-

ical scheme (on the time step for the equilibrium

or asymptote of the DE). In Yee & Sweby [1992],

Lafon & Yee [1991], Sweby & Yee [1991], and Yeeet al. [1992a] we showed how "numerical" basins

of attraction can complement the bifurcation dia-

grams in obtaining the global asymptotic behav-ior of numerical solutions for nonlinear DEs. We

showed how in the presence of spurious asymptotes

the basins of the true stable steady states could be

altered by the basins of the spurious stable and un-

stable asymptotes. One major consequence of thisphenomenon which is not commonly known is that

this spurious behavior can result in a dramatic dis-

tortion and, in most cases, a dramatic shrinkageand segmentation of the basin of attraction of the

true solution for finite time steps. Such distortion,

shrinkage, and segmentation of the numerical basins

of attraction will occur regardless of the stability of

the spurious asymptotes.

We use the term "spurious asymptotic numer-ical solutions" to mean asymptotic solutions that

satisfy the discretized counterparts but do not sat-

isfy the underlying ordinary differential equations

(ODEs) or partial differential equations (PDEs). Inother words, asymptotic solutions that are asymp-

totes of the discretized counterparts but are not

asymptotes of the DEs. Asymptotic solutions here

include steady-state solutions, periodic solutions,limit cycles, chaos, and strange attractors. Here,the basin of attraction is a domain of a set of ini-

tial conditions whose solution curves (trajectories)all approach the same asymptotic state. Also, weuse the term "exact" and "numerical" basins of at-

traction to distinguish "basins of attraction of the

underlying DEs" and "basins of attraction of thediscretized counterparts".

In view of the above nonlinear behavior of nu-

merical schemes, it is possible that numerical com-

putations may converge to an incorrect steady state

or other asymptotes which appear to be physically

reasonable. One major implication is that what is

expected to be physical initial data associated with

a true steady state might lead to a wrong steadystate, a spurious asymptote, or a divergence or non-

convergence of the numerical solution. In addition,

the existence of spurious limit cycles [Yee et al.,

1992; Yee et al., 1991; Yee & Sweby_ 1992] may re-sult in the type of nonconvergence of steady-state

numerical solutions observed in time-dependent

approaches to the steady states. It is our belief

that the understanding of the symbiotic relation-ship between the strong dependence on initial data

and permissibility of spurious stable and unstable

asymptotic numerical solutions at the fundamental

level can guide the tuning of the numerical param-

eters and the proper and/or efficient usage of nu-

merical algorithms in a more systematic fashion. It

can also explain why certain schemes behave nonlin-

early in one way but not another. Here, strong de-pendence on initial data means that for a finite time

step At that is not sufficiently small, the asymptoticnumerical solutions and the associated numerical

basins of attraction depend continuously on the ini-

tial data. Unlike nonlinear problems, the associated

numerical basins of attraction of linear problems are

independent of At as long as At is below a certain

upper bound.

Studies in Yee et al. [1991], Yee & Sweby [1992],

Lafon & Yee [1991, 1992], Griffiths et al. [1992a,b],

Sweby & Yee [1991], Yee et al. [1992], Mitchell &

Griffiths [1985], Iserles [1988], Iserles et al. [1990],

Stuart [1989], and Dieci & Estep [1990] are par-ticularly important for computational fluid dynam-

ics (CFD), since it is a common practice in CFD

computations to use a time-dependent approach to

obtain steady-state numerical solutions of compli-cated steady fluid flows which often consist of stiff

nonlinear PDEs of the mixed type. When a time-

dependent approach is used to obtain steady-state

numerical solutions of a fluid flow or a steady PDE,a boundary value problem is transformed into an

initial-boundary value problem with unknown ini-

tial data. If the steady PDE is strongly nonlinear

and/or contains stiff nonlinear source terms, phe-

nomena such as slow convergence, nonconvergence

or spurious steady-state numerical solutions com-

monly occur even though the time step is well belowthe linearized stability limit and the initial data are

physically relevant.

It is also a common practice in CFD to use im-

plicit methods to solve stiff problems. Such schemes,

however, introduce the added difficulty of solving

the implicit equations (nonlinear algebraic equa-

tions) in order to obtain the solution at the nexttime level. Various options such as linearization or

iteration are available for this purpose. In Yee &

Sweby [1992], we included a study on the dynamics

of a noniterative linearized version of the implicit

Euler and trapezoidal methods. In this work we

generalize our earlier work [Yee & Sweby, 1992] to

Global Asymptotic Behavior of Iterative Implicit Schemes 1581

include iterative solution procedures of the implicitdiscretized equations, namely, simple iteration andfull and modified Newton iteration. In addition, we

also study the 3-level backward differentiation for-

mula (BDF) and a midpoint implicit method (one-

legged method of the trapezoidal method) with

these four methods (noniterative versus iterative) of

solving the resulting nonlinear algebraic equations

applied to it. A comparison of the above combina-tion of implicit methods with the nine explicit meth-

ods studied in Yee & Sweby [1992], and with the

"straight" Newton method in solving the steady

part of the equations, is also performed. We use

the te