I OFL
ORNL P
1033
W
J
EEEFEEEE
i
114 LG
MICROCOPY RESOLUTION TEST CHART
NATIONAL BUREAU OF STANOAKOS - 1963
ORNI - AC - OFFICIAL
.
....
--.--... .....
........... --...
LEGAL NOTICE
This report was prepared as an account of
Government sponsored work. Neither the
United States, nor the Commission, nor any
person acting on behalf of the Commission:
A. Makes any warranty or representa-
tion, expressed or implied, with respect to
the accuracy, completeness, or usefulness
of the information contained in this report,
or that the use of any information, appa-
ratus, method, or process disclosed in this
report may not infringe privately owned
rights; or
B. Assumes any liabilities with respect
to the use of, or for damages resulting from
the use of any information, apparatus,
method, or process disclosed in this report.
As used in the above, “person acting on
behalf of the Commission” includes any em-
ployee or contractor of the Commission, or
employee of such contractor, to the extent
that such employee or contractor of the
Commission, or employee of such contractor
prepares, disseminates, or provides access
to, any information pursuant to his employ-
ment or contract with the Commission, or
his employment with such contractor.
.. cm.........--. ....macaco. ---. ......
..
ORNL - AEC - OFFICIAL.....
ORNU.P. 1033
CONF-65020n-/
1965
ORNI - AIC - OFFICIAL
In
XIVES
ORNI - AEC-OFFICIAL
MASTER
ON NONLINEAR MULT ISTEP METHODS FOR
ORDINARY INITIAL-VALUE PROBLEMS
PATENT. CLEARANCE OBTAINED, RELEASE TO
THE PUBLIC IS APPROVEC. PREOOLS
ARE ON FOLE IN THE ?**?"", 17"?!!!!!
William B. Grage
Mathematics Division
Oak Ridge National Laboratory*
Oak Ridge, Tennessee, U.S.A.
-LEGAL NOTICE
TW. report w popredu na tom of Covena moored work. Malther the United
Bar., nor Com nieko, ms my pertan etho l l of the Coundation:
A. Mem urunty or a tion,
or legaled, with up to the co-
rky, competent, or wefaline of the tadornation contained in the report, or that the one
of way beformation, part, method, ar praca d loud to the raport my mot mentre
privately owned rhyhet; or
B.
A n y Habilities w eet the weal, or for dumpurning from the
uw of way informatum, apparte, mand, or procura dachowed in the report
Au word to the whowe, 'perman estes au bakalf of the Comm on" cheating may ma-
ploy or contractor of the Comminator, o p loyee of mucha contractor, to the chose that
ich player contractor of the
C
o n, or uployee of charactor prepare
Mount, or provides word to, wag tormation parte do Momployment of contract
with the Creator, az Mo employ the contractor.

Research sponsored by the U. S. Atomic Energy Commission under contract
with the Union Carbide Corporation.
ORN! - AIC - OFFICIAL
0
IV1J1310-):8-1
On Nonlinear Multister. Methods for
Ordinary Initial-Value Problems
William B. Grage
1.
Introduction.
Linear difference operators
+
...
+
B
x'
o tk+ ... + n - n but the + ... + Box ~ Cp+z *P*2) gpt2, (2)
with x ) = x(*)(4x), occur in the theory (2,4) of the numerical
solution of initial-value problems
x(a) = 8,
x' = f(t,x), te I = [a,b],
by linear multietep methods
che utk + ... + ax = h[BP(tatkXatk) + ... + B +(tmX.)]
The method is of order p 17 (1) holds, for sufficiently differentiable
functions x(t), with Cp+1+0.
If X(t) is the solution of (2) then (1) is the local
discretization error. Thus, for small steps h, it is natural to choose
the Q4, B, so that p 18 as large as possible. Indeed, p = 2k may be
achieved (2), but the resulting methods are not suitable for step-by-step
application. It is necessary to insist that the method be stable. In
terms of the zeros of p(z) - Eazz' this means that
(1) p(z) -0 =1z1 si, and
(11) p(z) - p'(z) = 0 3
121 <1.
09-DIY-IN.
Trivstoo-)1-INIO
IV)
-2-
OINAC - OPR1C1!
ORHI - AIC - UFFICIAL
Dahlquist's interesting negative result 18 that the requirement of
stability restricts the order to psk + 2; moreover p = k + 2 only if
k 18 even and all zeros of p(z) are of unit modulus.
Stetter and the present author (3), and independently Butcher
(1), have found that the analogous conclusions no longer hold for the
. modified operator
o tato + ... + x - h[Be*+ Bx'nts + Bx=2**k-1 + ... + B. *)
(3)
~ €p+2(8) (P+2)
which is a function of the real parameter s. In fact p = 2k + 2 18
possible for k = 1, 2, ..., 6: Butcher has obtained explicit formulas
for the coefficients a, (s), B,(s), B(s) so his approach is followed here:
Hermite Interpolation with Equally Spaced Points. Let x(t) have
derivatives of sufficiently high order in a neighborhood of t. Put
t = to = to + sh and x) = x(m) (t). The unique polynomial ILE(t) of
degree s 2k + 1 which satisfies
Ax(+2) = xzo hiltz) = x,. 1 = 0, 1, ..., k,
18
() = § 17 / (0)*x + 10,8()x,
iso
where, 11
(8) = 8(8-1) ... (8-k),
ORNI - "1C-orririni
omnia IIC -OSFICIAL
.....
.
11121310-)}1-8.:
24 = 12 +252 + ... +1-1,
-0,
ORIL-AC - OPTICI!
then
14- (* 191° Cm
2.) – [** (?!)..
6
-
The error of the approximation to x is
- grans que,
ay
and that of the approximation to x 16
k+2
begin
to decorap + ax: (02:p
en egense) yake. 15)
tho
120
3. Modified Multister Operators with By FC. If (3), with a = 0 and
8 + 0, 1, ..., k, 18 solved for hx and compared with (5) it 18 seen
that a normalized family of operators of order p = 2k+1 18 obtained
18 (8) = 1 and
&. (8)
BBJ =
x(s),
y = -b/1(8),
1 = 0, 1, ..., k.
Then also
Cakte(s) = -28(8)
2 (8) (8)
3
726+2)!
:!-
ORNI - IC - OFFICIAL
.::.
IV
4.
ORAL - AC - OPTICI:
The principal result is that there exists a decreasing sequence of
intervale Sk such that If 8 € Sx then the corresponding operator 18
stable; more precisely
ORNI - AIC - OSPICIAL
(-oo, + c) = $352> ...) Sy > Sg = $.
(8)
This has been proved for k up to 4 by the methods in (3); It was
establiched emy erically by Butcher who suggests the convenient values
6 = k - and k - for k = 1, 2, 3 and x = 4, 5; 6, respectively.
In (3) It was further asked 12 "optimal" stable operator's
of order p = 2k + 2 could be achieved by choosing 8 appropriately.
From (7) a necessary condition for this 18 (8) = 0. Denoting by se
the zero of w(s) in (x-1,k) it turns out that & € Sy, k = 1, 2, ..., 6.
firesulting in a "compressed" Simpson's rule.
Note that
Modified Multistep Operators with Bi = 0. A simpler subclass of
modif led multistep inethods 18 obtained by requiring that By = 0
(3). I s 18 restricted so that
04-1(s) -1(8) 0
then, by considering a linear combination of (4) and (5) with
replaced by kol, a normalized family of operators of order p = 2
results with
· 0;(8) = -4-1,1(k) + B(8)%-2,4(),
(9)
B4 (8) = bx-1,2(k) - B(8)D'x-2,4(6), 10, ...kol,
ORNI - 11C - OFFICIAL
ORNI -"10 - OIFICIAL
iris.
181311.3.::.-
OINI- AC - OPTICIAL
and
B(x) = 2.0-1. (@xy-10T
I S, is the interval of 8 for which the k-step operator 18 stable
then it is known triat
52 = (-0, + m) – 52 = (1,2)=5,(2.70,2.82); 54,55€ 0.
.
In particular, 'k -
Por k = 1, 2, 3.
Optimal operators of order p = 2k+l can be found by setting
B4 (8) = 0 10 (6). This Leads to
20(8) - -(8) = 0.
II &
denotes the largest root of this equation then
kol <
<
<
and
€ 5, k = 1, 2, 3, 4. For i = 1 a simple Rudau formula results.
5. Fredictors for Modified Multistep Methods. To apply th' general
operator (3) to the solution of (2), approximate values of xong, Xanh
may be found from predictors
to ***-1**-1 + ... + a 1 - HC 07-2X"D#k-2 + ... + hydr.
atko
(10)
*
– Can
(26)
2k
i
ini disse-, . . ltito
1912.
ORNI - AIC - OFICIAL
ORNI - AC - OffiCo.
e Shtuka + ... +&o Albox to + BE-*ek-2 + ... + Box-
men etenkin
Porcom (4), ir a*(8) = 1, then
af (B) = --1,1(8), (8) = 0,-1,168), 1 = 0, ..., k-1.
.
section.
tions
logo
Bat
The â, (s), B. (s), B(s) may be found exactly as in the previous
section. They are given by equations analogous to (9). But now b(s) in
not chosen to make ĉoz(8) = 0. Instead It is chosen to annihilate the
leading term of the loca.. discretization error after (3) has been applied.
Some calculation gives
not chose
2.
Instead
is chosen
onthilate
leac
m of
e local discretization error alte
as been
ols.ed.
(s) - Br(s)-1(k) + $(5), (6)
- 2007.1 (5) au 8-1 (8)
This device, which is due to Butcher, results in a genuine nonlinear
k-step method of order p = 2k+). It requires three evaluations of f
per step.
If the optimal modified operators are used it is necessary
to include an additional point tha, Into the predictor. This 18
common practice when predictor-corrector methods are used and as the
approach taken in (3). Only two evaluations of e are theu necessary,
but the method 18 truly a (k+1)- step one.
OINT-IC-OFFICIAL
-7-
I11ISO-Drai. ☺
ORII - AIC -0:11C174
The most reasonable scheme, perhaps, 1.6 the modified operator
with Bk = 0, coupled wita the single predictor (20). This results in
& nonlinear k-step method of order p = 2k requiring two evaluat1018
per step.
::.-17;
GIN 18C-OIFICIAL
Ividis.
61-
.
-
...
-
........
.....
.
References
O2111-AIC - Orris.
(1)
Butcher, J. C.: A Modified Multistep Method for the Numerical
Integration of Ordinary Differential Equations. J. Assoc. Covip.
Mach. 12 (1955) 134-135.
(2)
Dahlquist, G.: Convergence and Stability in the Naverical Integšation
of Ordinary Differential Equations. Math. Scand. 4 (1956) 33-55.
13]
Grage, W. B., and H. J. Stetter.: Generalized Multistep Predictor-
Corrector Methods. J. Assoc. Comp. Mech. 11 (1964) 188-209.
[4]
Henrici, P.: Discrete Variable Methods in Ordinary Differential
Equations. John Wiley and Sons, Inc., New York, 1962.
-
-
-
-
-
- -
DATE FILMED
7 / 20 /165







>
PA
IX
I_
END