For multistep methods, the problems involved with consistence, convergence and stability are complicated because of the number of approximations involved at each step. In the one step method, the approximation
w
i
+
1
{\displaystyle w_{i+1}}
depends only on the previous approximation
w
i
{\displaystyle w_{i}}
, whereas the multistep methods use at least two of the previous approximations, and the usual method that are employed involve more.
Stable Multistep Method
edit
Characteristic polynominals
edit
For the multistep method:
w
0
=
α
,
w
1
=
α
1
,
.
.
.
,
w
m
−
1
=
α
m
−
1
{\displaystyle w_{0}=\alpha ,w_{1}=\alpha _{1},...,w_{m-1}=\alpha _{m-1}}
,
w
i
+
1
=
a
m
−
1
w
i
+
a
m
−
2
w
i
−
1
+
.
.
.
+
a
0
w
i
+
1
−
m
+
h
F
(
t
i
,
h
,
w
i
+
1
,
w
i
,
.
.
.
,
w
i
+
1
−
m
)
{\displaystyle w_{i+1}=a_{m-1}w_{i}+a_{m-2}w_{i-1}+...+a_{0}w_{i+1-m}+hF(t_{i},h,w_{i+1},w_{i},...,w_{i+1-m})}
,
the polynominal
P
(
λ
)
=
λ
m
−
a
m
−
1
λ
m
−
1
−
a
m
−
2
λ
m
−
2
−
.
.
.
a
1
λ
−
a
0
{\displaystyle P(\lambda )=\lambda ^{m}-a_{m-1}\lambda ^{m-1}-a_{m-2}\lambda ^{m-2}-...a_{1}\lambda -a_{0}}
,
is called the characteristic polynominal of the above mutistep method.
The stability of a multistep method with respect to round-off error is dictated by the magnitudes of the zeros of the characteristic polynominal.
Let
λ
1
,
λ
2
,
.
.
.
,
λ
m
,
{\displaystyle \lambda _{1},\lambda _{2},...,\lambda _{m},}
denote the (not necessarily distinct) roots of the characteristic equation
P
(
λ
)
=
λ
m
−
a
m
−
1
λ
m
−
1
−
a
m
−
2
λ
m
−
2
−
.
.
.
a
1
λ
−
a
0
=
0
{\displaystyle P(\lambda )=\lambda ^{m}-a_{m-1}\lambda ^{m-1}-a_{m-2}\lambda ^{m-2}-...a_{1}\lambda -a_{0}=0}
,
associated with the multistep difference method
w
0
=
α
0
,
w
1
=
α
1
,
.
.
.
,
w
m
−
1
=
α
m
−
1
{\displaystyle w_{0}=\alpha _{0},w_{1}=\alpha _{1},...,w_{m-1}=\alpha _{m-1}}
,
w
i
+
1
=
a
m
−
1
w
i
+
a
m
−
2
w
i
−
1
+
.
.
.
+
a
0
w
i
+
1
−
m
+
h
F
(
t
i
,
h
,
w
i
+
1
,
w
i
,
.
.
.
,
w
i
+
1
−
m
)
.
{\displaystyle w_{i+1}=a_{m-1}w_{i}+a_{m-2}w_{i-1}+...+a_{0}w_{i+1-m}+hF(t_{i},h,w_{i+1},w_{i},...,w_{i+1-m})\,.}
If the absolute value
|
λ
i
|
≤
1
{\displaystyle |\lambda _{i}|\leq 1}
, for each i=1,2,...,m, and all roots with abosolute value 1 are the simple roots, then the difference method is said to satisfy the root condition.
Stability Definitions
edit
Methods that satisfy the root condition and have
λ
=
1
{\displaystyle \lambda =1}
as the only root of the characteristic equation of the magnitude one are called strongly stable.
Methods that satisfy the root condition and have more than one distinct root with magnitude one are called weakly stable.
Methods that do not satisfy the root condition are called unstable.
Stable Multistep methods
edit
A multistep method of the form
w
0
=
α
0
,
w
1
=
α
1
,
.
.
.
,
w
m
−
1
=
α
m
−
1
{\displaystyle w_{0}=\alpha _{0},w_{1}=\alpha _{1},...,w_{m-1}=\alpha _{m-1}}
,
w
i
+
1
=
a
m
−
1
w
i
+
a
m
−
2
w
i
−
1
+
.
.
.
+
a
0
w
i
+
1
−
m
+
h
F
(
t
i
,
h
,
w
i
+
1
,
w
i
,
.
.
.
,
w
i
+
1
−
m
)
{\displaystyle w_{i+1}=a_{m-1}w_{i}+a_{m-2}w_{i-1}+...+a_{0}w_{i+1-m}+hF(t_{i},h,w_{i+1},w_{i},...,w_{i+1-m})}
,
is stable if and only if it satisfies the root condition. Moreover, if the difference method is consistent with the differential equation, then the method is stable if and only if it is convergent.
The fourth-order Adams-Bashfoth method is
w
i
+
1
=
w
i
+
(
h
/
24
)
(
55
f
i
−
59
f
i
−
1
+
37
f
i
−
2
−
9
f
i
−
3
)
,
{\displaystyle w_{i+1}=w_{i}+(h/24)(55f_{i}-59f_{i-1}+37f_{i-2}-9f_{i-3}),}
where
f
i
=
f
(
t
i
,
w
i
)
.
{\displaystyle f_{i}=f(t_{i},w_{i})\,.}
The characteristic equation is
λ
4
−
λ
3
=
λ
3
(
λ
−
1
)
=
0
{\displaystyle \lambda ^{4}-\lambda ^{3}=\lambda ^{3}(\lambda -1)=0}
so we find the characteristic roots to be
λ
1
=
1
,
λ
2
=
0
,
λ
3
=
0
,
and
λ
4
=
0
.
{\displaystyle \lambda _{1}=1,\quad \lambda _{2}=0,\quad \lambda _{3}=0,\quad {\text{and}}\quad \lambda _{4}=0\,.}
Thus the 4th-order Adams Method satisfies the root condition and is strongly stable.
Milne's Method is
w
i
+
1
=
w
i
−
3
+
(
4
h
/
3
)
(
2
f
i
−
f
i
−
1
+
2
f
i
−
2
)
,
{\displaystyle w_{i+1}=w_{i-3}+(4h/3)(2f_{i}-f_{i-1}+2f_{i-2}),}
where
f
i
=
f
(
t
i
,
w
i
)
.
{\displaystyle f_{i}=f(t_{i},w_{i})\,.}
The characteristic equation is
λ
4
−
1
=
0
{\displaystyle \lambda ^{4}-1=0}
so the characteristic roots are
λ
1
=
1
,
λ
2
=
−
1
,
λ
3
=
i
,
and
λ
4
=
−
i
.
{\displaystyle \lambda _{1}=1,\quad \lambda _{2}=-1,\quad \lambda _{3}=i,\quad {\text{and}}\quad \lambda _{4}=-i.}
Thus the 4th-order Milne's Method satisfies the root condition, but it is only weakly stable.
Absolute Stability & Region of Absolute stability
edit
Apply a numerical method to initial-value problem
y
′
=
λ
y
{\displaystyle y'=\lambda y}
y
(
0
)
=
α
where
Re
(
λ
)
<
0
.
{\displaystyle y(0)=\alpha \quad {\text{where}}\quad {\text{Re}}(\lambda )<0\,.}
Suppose that a round off error
ξ
0
{\displaystyle \xi _{0}}
is introduced in the initial condition for this method. At the nth step the round off error is
ξ
n
{\displaystyle \xi _{n}}
. Provided the step size h is chosen to satisfy
|
ξ
n
|
<
|
ξ
0
|
{\displaystyle |\xi _{n}|<|\xi _{0}|}
, the numerical method is said to be absolutely stable for the step size h. And
R
=
{\displaystyle R=}
{
h
λ
∈
C
|
|
ξ
n
|
<
|
ξ
0
|
}
{\displaystyle \{h\lambda \in \mathbb {C} ||\xi _{n}|<|\xi _{0}|\}}
is said to be region of absolute stability for numerical method.
Region of absolute stability for one-step method
edit
In general, when a one-step method is applied to the test equation, a function
Q
{\displaystyle Q}
exists with the property that the difference method gives
w
i
+
1
=
Q
(
h
{\displaystyle w_{i+1}=Q(h}
λ
)
w
i
{\displaystyle \lambda )w_{i}}
.
The initial round-off error
ξ
0
{\displaystyle \xi _{0}}
and the round-off error at the ith step
ξ
i
{\displaystyle \xi _{i}}
will satisfy
ξ
i
+
1
=
Q
(
h
{\displaystyle \xi _{i+1}=Q(h}
λ
)
ξ
i
{\displaystyle \lambda )\xi _{i}}
which is
ξ
i
+
1
=
Q
i
(
h
λ
)
ξ
0
{\displaystyle \xi _{i+1}=Q^{i}(h\lambda )\xi _{0}}
.
The inequality
|
ξ
i
|
<
|
ξ
0
|
{\displaystyle |\xi _{i}|<|\xi _{0}|}
will hold if
|
Q
(
h
λ
)
|
<
1
{\displaystyle |Q(h\lambda )|<1}
.
Thus, region R of absolute stability for a one-step method is
R
=
{\displaystyle R=}
{
h
λ
∈
C
|
|
Q
(
h
{\displaystyle \{h\lambda \in \mathbb {C} ||Q(h}
λ
)
|
<
1
}
.
{\displaystyle \lambda )|<1\}\,.}
Region of absolute stability for multistep methods
edit
Consider the k-step method
w
n
+
1
=
∑
j
=
1
k
a
k
−
j
w
n
+
1
−
j
+
h
∑
j
=
0
k
b
k
−
j
f
n
−
j
+
1
{\displaystyle w_{n+1}=\sum _{j=1}^{k}a_{k-j}w_{n+1-j}+h\sum _{j=0}^{k}b_{k-j}f_{n-j+1}}
f
n
−
j
+
1
=
f
(
t
n
−
j
+
1
,
w
n
−
j
+
1
)
.
{\displaystyle f_{n-j+1}=f(t_{n-j+1},w_{n-j+1})\,.}
Applying it to
y
′
=
λ
y
{\displaystyle y'=\lambda y}
we get
w
n
+
1
=
∑
j
=
1
k
a
k
−
j
w
n
+
1
−
j
+
λ
h
∑
j
=
0
k
b
k
−
j
w
n
−
j
+
1
{\displaystyle w_{n+1}=\sum _{j=1}^{k}a_{k-j}w_{n+1-j}+\lambda h\sum _{j=0}^{k}b_{k-j}w_{n-j+1}}
⇔
(
1
−
λ
h
b
k
)
w
n
+
1
−
∑
j
=
1
k
(
a
k
−
j
−
λ
h
b
k
−
j
)
w
n
+
1
−
j
=
0
.
{\displaystyle \Leftrightarrow (1-\lambda hb_{k})w_{n+1}-\sum _{j=1}^{k}(a_{k-j}-\lambda hb_{k-j})w_{n+1-j}=0\,.}
The characteristic polynominal of the method is
Q
(
z
,
h
λ
)
=
(
1
−
{\displaystyle Q(z,h\lambda )=(1-}
λ
h
b
k
)
z
k
−
∑
j
=
1
k
(
a
k
−
j
−
{\displaystyle \lambda hb_{k})z^{k}-\sum _{j=1}^{k}(a_{k-j}-}
λ
h
b
k
−
j
)
z
k
−
j
=
0
{\displaystyle \lambda hb_{k-j})z^{k-j}=0}
The region R of absolute stability for a multistep method is
R
=
{\displaystyle R=}
{
h
λ
∈
C
|
|
β
j
|
<
1
,
for all zeros
β
j
of
Q
(
z
,
h
λ
)
}
{\displaystyle \{h\lambda \in \mathbb {C} ||\beta _{j}|<1,{\text{ for all zeros }}\beta _{j}{\text{ of }}Q(z,h\lambda )\}}
.
Determine the region of absolute stability for two step method
w
i
+
1
=
w
i
+
h
/
2
(
3
f
i
−
f
i
−
1
)
{\displaystyle w_{i+1}=w_{i}+h/2(3f_{i}-f_{i-1})}
.
Applying this method to:
y
′
=
λ
y
{\displaystyle y'=\lambda y}
, gives
w
i
+
1
=
w
i
+
λ
h
(
3
w
i
−
w
i
−
1
)
/
2
{\displaystyle w_{i+1}=w_{i}+\lambda h(3w_{i}-w_{i-1})/2}
⇔
w
i
+
1
−
(
1
+
3
h
λ
/
2
)
w
i
+
λ
h
/
2
w
i
−
1
=
0
.
{\displaystyle \Leftrightarrow w_{i+1}-(1+3h\lambda /2)w_{i}+\lambda h/2w_{i-1}=0\,.}
The characteristic polynominal of above method is
Q
(
z
,
h
λ
)
=
z
2
−
(
1
+
3
h
λ
/
2
)
z
+
h
λ
/
2
{\displaystyle Q(z,h\lambda )=z^{2}-(1+3h\lambda /2)z+h\lambda /2}
All the zeros of the characteristic polynominal are
z
1
,
2
=
+
(
1
+
3
h
λ
/
2
)
±
1
+
λ
h
+
9
λ
2
h
2
/
4
2
.
{\displaystyle z_{1,2}={+(1+3h\lambda /2)\pm {\sqrt {1+\lambda h+9\lambda ^{2}h^{2}/4}} \over 2}\,.}
Thus the region of absolute stability for this method
is
R
=
{\displaystyle R=}
{
h
λ
∈
C
|
|
z
1
,
2
|
<
1
}
{\displaystyle \{h\lambda \in \mathbb {C} ||z_{1,2}|<1\}}
.
Find the region of the absolute stability of Euler's method:
w
k
+
1
=
w
k
+
h
f
(
t
k
,
w
k
)
.
{\displaystyle w_{k+1}=w_{k}+hf(t_{k},w_{k}).}
Find the region R of the absolute stability of Trapezoidal method
w
k
+
1
=
w
k
+
h
/
2
(
f
(
t
k
,
w
k
)
+
f
(
t
k
+
1
,
w
k
+
1
)
)
.
{\displaystyle w_{k+1}=w_{k}+h/2(f(t_{k},w_{k})+f(t_{k+1},w_{k+1})).}
Make a table of the interval of absolute stability for four one-step methods: Euler's method, Backward- Euler, M-Euler and Trapezoidal method.
Find the Region of absolute stability of Adams-Bashforth explict Four-step Method
w
n
+
1
=
w
n
+
(
h
/
24
)
(
55
f
n
−
59
f
n
−
1
+
37
f
n
−
2
−
9
f
n
−
3
)
.
{\displaystyle w_{n+1}=w_{n}+(h/24)(55f_{n}-59f_{n-1}+37f_{n-2}-9f_{n-3})\,.}
The following is a quiz covering information presented on the associated multistep method.