Math. Control Signals Systems (1995) 8:1-26 9 1995 Springer-Verlag London Limited
Mathematics of Control, Signals, and Systems
Conditions for Stability of the Extended Kalman Filter and Their Application to the Frequency Tracking Problem* Barbara F. La Scala,t Robert R. Bitmead,t and Matthew R. Jamest Abstract. The error dynamics of the extended Katman filter (EKF), employed as an observer for a general nonlinear, stochastic discrete time system, are analyzed. Sufficient conditions for the boundedness of the errors of the EKF are determined. An expression for the bound on the errors is given in terms of the size of the nonlinearities of the system and the error covariance matrices used in the design of the EKF. The results are applied to the design of a stable EKF frequency tracker for a signal with time-varying frequency. Key words. Extended Kalman filter, Stability, Discrete-time nonlinear systems, Frequency tracking.
1. Introduction
The extended Kalman filter (EKF) is often used to design observers for nonlinear filtering problems in spite of the fact that there are few theoretical results to indicate when such a design will be successful. In practice it has been found that, when the nonlinearities are benign, such a design will often work, but until recently more precise guidelines have not been available. In [BBJ] Baras et al. have given conditions under which the EKF will be a locally asymptotic observer when applied to a deterministic, continuous time system. Following from the work in I-BBJ], Song and Grizzle [SG] have demonstrated a similar result in the discrete time case. In this paper we dispense with the simplifying assumption that the signal model is undriven and consider the more realistic case of a signal with both measurement and process noise, tn addition, motivated by our application, we relax key assumptions used in [BBJ] and [SG] relating to the growth rate of the nonlinearities and to observability. We derive sufficient conditions to ensure that the errors of the EKF will remain bounded when applied to such a signal. In obtaining this nonlinear
* Date received: July 6, 1993. Date revised: March 13, 1995. This research was supported by the Co-operative Research Centre for Robust and Adaptive Systems ((CR)2ASys). The authors wish to acknowledge the funding of the activities of (CR)2ASys by the Australian Commonwealth Government under the Co-operative Research Centre Program. ~"Department of Systems Engineering, Research School of Information Sciences and Engineering, Australian National University, Canberra, ACT 0200, Australia.
2
B.F. La Scala,R. R. Bitmead,and M. R. James
perturbation result it is necessary to examine the dynamics of the estimator and of the associated Riccati difference equation. Our result shows that the stability of the error system depends, as would be expected, on the nature of the nonlinearities and the size of the noise processes. These results can be used to design stable, nonlinear filters, and we illustrate this by designing an EKF observer for the frequency tracking problem. The problem of determining the frequency of a signal has many applications. It occurs in communications problems and in sonar, radar and biological signal processing, as well as in other areas. While it is a common problem, its inherent nonlinearity makes it a difficult one. The problem of estimating the frequency of a signal when the frequency is constant has been found to be more tractable than the problem of tracking a time-varying frequency. There is a myriad of techniques for solving the estimation problem, such as the maximum likelihood estimator described by Quinn and Fernandes [QF] and the adaptive comb filter of Nehorai and Porat [NP], but only a handful of techniques for the tracking problem. Some of these are extensions of estimation techniques (the estimator of Nehorai and Porat [NP] can be modified in this way), while others were designed particularly for the tracking problem, such as the hidden Markov model approach of Streit and Barrett [SB], the well-known phase-locked loop (Kelly and Gupta [KG]) and the EKF (James I-J], Parker and Anderson [PA] and Anderson and Moore [AM]). In Section 2 we describe our signal model for the frequency tracking problem. In Section 3, an EKF observer is constructed for this model. In Section 4 the error dynamics of the EKF are derived. In Section 5 some nonlinear stability results are presented, and in Section 6 these are applied to the error dynamics of the EKF to determine sufficient conditions for its stability. In Section 7 this result is applied to the frequency tracking problem, and methods for improving the design of our EKF observer are discussed.
2. Signal Model Consider the following signal model describing the evolution of noisy sampled quadrature signals having a slowly time-varying frequency:
[xl(k+l)l x2(k+ [c~ 1) =
xa(k + i)
["(k)l Ly=(k)j =
sin x3(k)
0
cos
[ 01 x3(k) 0 lFxl(k)l L ,(k)j 0
0
['o o Oo]r-
-
+
|x2(k)| +
0
, (2.1)
w,(k)
(2.2) Lvdk)J'
where {y(k)} is the received signal, x 3 is the unknown time-varying frequency and xl and x2 are the in-phase and quadrature components. The parameter e s (0, 1) determines the rate of time variation of x 3 and is chosen so that the frequency varies slowly enough that the signal appears periodic over several cycles. The
Conditions for Stability of the Extended Kalman Filter
3
signals {v(k)} and {w(k)} are zero mean, independent noise processes with E [ w ( k ) w ( I ) T] = Qbk,,
(2.3)
E[v(k)v(l) w] = RSkt,
(2.4)
where 6kl is the Kronecker delta function, Q > 0 and R > 0. The frequency of the signal x 3 represents the state of the system that we wish to recover. The xl and x2 components appear only to facilitate the formulation of the problem, and are thus noiseless transformations of the x3 component. If we consider the deterministic form of (1)-(2), written as: x ( k + 1) = f ( x ( k ) ) , y(k) = h(x(k)),
then the system satisfies the conditions given in [N] for strong local observability. That is, for all x ~ R" there exists a neighborhood, U, of x such that for all ~ ~ U, Y~ ~ x, {h(fk(x)): k = 0 . . . . . n - 1} ~ {h(fk(Y~)): k = 0 , . . . , n - 1}. Note that it is not possible to achieve a global observability result for any formulation of the discrete-time frequency tracking problem, due to aliasing effects. However, since it is possible to resolve the state locally without ambiguity in the deterministic case of our formulation, it is reasonable to expect that an observer could be constructed for this model in the stochastic environment which would be stable, given bounds on the size of the initial admissible error. For this model, state estimation coincides with frequency tracking. We will concentrate on extended Kalman filtering approaches to the construction of a state observer. In particular we consider the design variables of the E K F observer, effectively ~, Q, and R, and their effects on the dynamics of frequency capture and tracking. Initially we generate results of general applicability and only introduce the specifics of the frequency tracking formulation to illustrate these results.
3. The EKF Observer
We follow an E K F design for our observer, since it is a standard approach to nonlinear state estimator construction based on the use of a Kalman filter for the linearized signal model. For the estimation of frequency, as opposed to tracking frequencies, it has been shown [S], [J] that the E K F is closely related to the phaselocked loop. Our aim will be to extend the analysis to consider the case of frequency tracking using this procedure, with a focus on the design trade-off between signal-to-noise ratio and slew rate (the rate of change of the frequency). We do not necessarily advocate the E K F as the most suitable observer but, given that there are few other satisfactory methodologies for the development of nonlinear state estimators, we seek to quantify its design rules and performance limitations. In particular we shall make suggestions for the modification of the E K F associated with the signal model (2.1)-(2.2). There is a long history of the application of E K F methods in frequency estimation and tracking, going back at least to Snyder [S]. The analysis of design and
4
B.F. La Scala, R. R. Bitmead,and M. R. James
performance has, however, been lacking. Studies of the behavior of linear Kalman filtering problems [CGS] indicate that stability problems are likely in frequency estimation, because of the potential for uncontrollable signal model modes on the unit circle. Accordingly, we shall first present the E K F for (2.1)-(2.2), and then move on to consider the stability of its associated error system. The E K F is derived by linearizing the signal model about the current predicted state estimate and then using the Kalman filter on this linearized system to calculate a gain matrix. This gain matrix, along with the nonlinear signal model and new signal measurement, is used to produce the filtered state estimate and then to produce an estimate of the state at the next time instant. For a nonlinear signal model of the form x(k + 1) = f(x(k)) + w(k),
(3.1)
y(k) = h(x(k)) + v(k),
(3.2)
where E[w(k)w(k) T] = Q(k) and E[v(k)v(k) r] = R(k), the equations for the E K F are [AM, Chapter 8]: Measurement Update: ~(kJk) = 2(klk - 1 ) - K~(k)[y(k) - h(~(klk - 1))], P~(klk) = [I - K,~(k)Ht,(k)]P~(klk - 1).
(3.3) (3.4)
Time Update: 2(k + l[k) = f(:t(klk)),
(3.5)
P~(k + ilk) = F~(k)P~(klk)F~(k) T + Q(k),
(3.6)
K~(k) = P~(klk - 1)H,~(k)T[H~(k)P~(klk - 1)/-/~(k)T + R(k)] -1,
(3.7)
where
F~(k)
=
He(k)
=
[~Laxsj
,
[~ .=~,,.k-,, LaxjJ
(3.8) (3.9)
and Yc(k[k) is the estimate of the state at time k and :~(k + l l k ) is the prediction of the state at time k + 1 using all the observations up to and including y(k). The matrices Pe(klk) and P~(k + l lk) are approximations of the respective state estimate error covariances}
1 The notation used here explicitly shows the dependence in the EKF equations on a particular trajectory in the state space. This is nonstandard, but will make the later stability arguments clearer.
Conditions for Stability of the Extended Kalman Filter
5
In the case of (2.1)-(2.2) we have
e~(k)
=
-cos(:~3) sin(~3) 0
-- sin(:~a) cos(~3) 0
-#, sin0~3) - ~2 cos?3)) 1 ~1 cos(~a) - x2 sin(x3) / 1- s
] I x=~(klk)
Note:
1. In [BBJ] and [SG], ~f/~x was required to be bounded in R". Clearly, this requirement is not satisfied for this observer. 2. We will construct our E K F observer assuming a diagonal Q of the form Q = diag(ql, ql, q2) where 0 < ql << q2, instead of Q = diag(0, 0, q), as would be suggested by the signal model (2.2), to ensure that the model used to construct the E K F is stabilizable. It is known that the stabilizability of [F, Q x/2] ensures that the Kalman filter is asymptotically stable in the linear filtering case. We shall demonstrate that the design of the E K F with a Q greater than that of the signal model is a key to securing state estimate error bounds. 3. Assume that the observation noise in both channels is of the same magnitude, i.e. R(k) = rI.
4. Error D y n a m i c s of the E K F
In the following sections we restrict our attention to systems with a linear output map, i.e. systems with (3.2) taking the form y(k) = H ( k ) x ( k ) + v(k). Song and Grizzle [SG] have shown that, for deterministic systems and subject to appropriate global controllability and observability conditions, the E K F will operate as a local asymptotic observer. That is, for initial state estimates in a neighborhood of the actual state, asymptotic convergence of the estimate to the correct value can be achieved for the system (3.1)-(3.2) in the absence of noise. Our E K F observer must operate in a different regime, in that the filter error equations are not homogeneous and furthermore do not satisfy a global observability condition. However, we will show that it is still possible to bound the state estimation error in these circumstances. Define the error in the filtered and predicted state estimates as e(klk) and e(k[ k - 1) respectively. Thus:
(4.1)
e(k]k) a-- x ( k ) - ~ ( k l k ) , e(klk-
1)~=x(k)-~(k[k
- 1).
From (3.3) e(klk) = [I - K ~ ( k ) H ( k ) ] e ( k [ k - 1) - K~(k)v(k),
(4.2)
6
B. F. La Scala, R. R. Bitmead,and M. R. James
where
e(k + l l k ) = f(x(k)) + w(k) - f ( & ( k l k ) ) = f(x(k)) + w(k) - f(x(k) - e(klk)) = f(x(k)) + w(k) - f ( x ( k ) ) + ~ ( x ( k ) ) ' e ( k l k ) - xi(x(k), - e ( k l k ) ) = ~ ( x ( k ) ) " e(klk) - x f ( x ( k ) , - e ( k l k ) ) + w(k) and xI is the remainder term from the Taylor series expansion o f f , i.e.
xy(a, b) = f ( a + b) -
f(a) - ~x (a). b.
Therefore:
e(klk) = [ I -
K ~ ( k ) H ( k ) ] F x ( k - 1 ) e ( k - I l k - 1)
- [I-
K~(k)n(k)]xy(x(k-
1), - e ( k -
+ [I - K~(k)H(k)]w(k - 1) - Ke(k)v(k),
Ilk-
1)) (4.3)
where
F.(k) = ~x(X(k)). Thus the dynamics for the filtering error of the E K F may be written as the sum of the error dynamics for the deterministic case, neglecting linearization errors, and nonlinear perturbation terms driven by the noise processes and remainder term from the Taylor series expansion of the nonlinearity in the signal model.
5. Nonlinear Stability Theorems Recall that the E K F error equation satisfies a nonlinear equation (4.3) which has a quasi-linear homogeneous part and additive perturbation terms due to linearization error and the noise processes. The exponential asymptotic stability of the error equations for the Kalman filter is a well-known and understood property [AM]. For the E K F in the discrete time case, Song and Grizzle [SG] have presented sufficient conditions for the exponential asymptotic stability when the signal model is deterministic. The approach used to extend these results makes use of the Total Stability Theorem given by Anderson et al. [ABJ] and related results. In this section, the nonlinear stability theorems necessary to prove later the stability of the error system of the E K F are developed and reviewed. 2
2 Note: the notation rr. 11will be used to represent the matrix or tensor norm, as appropriate, of a function induced by the vector norm I' I.
Conditions for Stability of the Extended Kalman Filter
7
Consider the ordinary difference equation
Theorem 5.1 (Total Stability Theorem).
z(k + 1) = A(k)z(k) + f(k, z(k)) + g(k, z(k)), z(O) = Zo e ~",
where the functions A: N + ~ ~"• conditions:
f : N + x ~" ~ R", g: N+ x R" ~ R" satisfy the
for some r > 0 there exists ~ > 0 and q > 0 such that for all IZll < r, Iz2[ <- r and keN, 1. sup [A(k)l < oo; ken
2. f(k, O) = 0; 3. If(k, zl) - f(k, z2)[ < ([zl - ZEI; 4. Ig(k, z~)l _< qr; 5. Iv(k, zl) - g(k, z2)l -< qlzl - z21. I f the unperturbed linear system ~(k + 1) = A(k)~(k)
(5.1)
is exponentially stable, i.e. the transition matrix of (5.1), (I)~(k2, kl), satisfies
[(I)z(k2, kl)l -< fl~t ~2-k' for all k 2 >_ k 1 >_ 0 for some fl >_ 1 and 0 <_ a < 1, then
Izol<~ r
and
fl((+q)+a
imply that for k >_ 0
Iz(k)l ~ B(~ + O~)klzol -~
Corollary 5.2.
fl~r _
Consider the unperturbed, homogeneous difference equation z(k + 1) = A(k)z(k) + f(k, z(k)), z(0) = Zo e •",
where A(k) and f(k, z) satisfy the conditions of Theorem 5.1 and the unperturbed linear system (5.1) is exponentially asymptotically stable as before, then r
[zol< ~
and
fl~+~
imply that for k >_ 0 Iz(k) _< fl(~ + (fl)klzo[ _ r.
8
B.F. La Scala, R. R. Bitmead, and M. R. James
Note that Theorem 5.1 applies to nonlinear equations which are composed of the sum of a linear component, a nonlinear homogeneous component and a nonlinear nonhomogeneous component. Its corollary applies to the case when the nonhomogeneous component is absent. The following theorem deals with the case when the linear component is absent. The E K F error dynamics are of this latter form. Theorem 5.3.
Consider the nonlinear difference equation x(k + 1) = f(x(k)) + g(x(k)),
x(0) = x0 ~ ~n,
(5.2)
where f e Ci(R n, R n) and # e CI(R ~, ~ ) , and the associated homo#eneous nonlinear equation z(k + 1) = f(z(k)),
z(O) = x o,
(5.3)
and its linearized equation 5(k + 1) = ~(z(k))~(k),
5(0) = Xo.
(5.4)
Suppose there exists an rz > 0 such that for all IXol _< r~: C1. The solution, {z(k): k = O, 1. . . . }, of (5.3) satisfies
Iz(k)l S Bl~lxol, where fli > 1 and 0 < al < 1; and C2. The solution, {~(k): k = 0, 1. . . . }, of (5.4) satisfies
[~'(k)l __ f12~ Ixol, where fl2 >_ l and O < a2 < 1. For some rx > fll r~ define (=~ 2 sup Ixl Srx
~f(x) u~
and t1 > 0 such that
~(x)
_< 89
for all lxl < rx. Then f12(( + r/) + ct2 < 1 and
Ixol s r~
imply /~2~(rx - ~l rz)
for all k >_ O.
by construction
Conditions for Stability of the Extended Kalman Filter
9
Proof. A recursion for the difference between the solution of the homogeneous equation (5.3) and the original, perturbed equation (5.2) will be derived. This recursion is then shown to be in the form of Theorem 5.1. Applying this theorem and condition C1 yields the result. Using Taylor's Theorem write
f(x + a) = f(x) + ~x(x)" a + x:(x, a), where x: is the remainder after the first order expansion of f. From (5.2) we then have x(1) = f(xo) + g(Xo)
~=f(xo) + 6(1), x(2) = f(x(1)) + g(x(1))
= f(f(xo) + 6(1)) + g(x(1)) = f(f(xo)) + ~-x(f(xo))'6(1) + x:(f(xo), 6(1)) + g(x(1)) =~ f2(Xo) + 6(2)
x(k) ~=fk(xo) + 6(k), where the correction term, {6(k)}, between the solution, {x(k)}, of (5.2) and that, {z(k)}, of (5.3) obeys the recursion
6(k + 1) = ~x(fk(xo)).b(k) + K:(fk(xo), 6(k)) + g(x(k)). Using the solution, {z(k)}, of the homogeneous equation (5.3) permits us to rewrite this as 6(k + 1) = ~x(Z(k)). 6(k) + ~:(z(k), 6(k)) + g(z(k) + 6(k)).
(5.5)
Note that (5.5) is now in precisely the form required for the Total Stability Theorem. Note also that 6(0) is zero. Suppose ]Xo[ = IZo[ < rz and let r~ = rx - tilt2. From C1 and C2 we know that (Sf/dx)(z(k)) is a bounded function and its transition matrix, Oz(k2, kl), satisfies
liOn(k2, kl)ll <-/~2~-k,, where f12 ~ 1 and 0 < ~2 < 1, so the linear portion of (5.5) satisfies the conditions of the Total Stability Theorem.
10
B.F. La Scala, R. R. Bitmead, and M. R. James
Define
f(k, 5(k)) ~ ~cy(z(k), 5(k)) = f(z(k) + 5(k)) - f(z(k)) - ~(z(k)).5(k). Then for all 1611 _< r~, [521 -< r~ and k >_ Of(k, O) = O. Now note that
OKt.(z, b) &~
Of
~(z)
- Ux (Z + 5) -
and for all 151 < r~ and [Xo[ < r~ Iz(k) + 61 <_ Iz(k)l + i6l <- flac~tXol + ra <- fllr~ + r~ = r~. Therefore
~
___ ~ ( z + 6 )
+ ~(z)_<~
and hence
If(k, 51) - f ( k , 62)1 < ~15~ - 621. Similarly, let ~(k, 5(k)) & g(z(k) + 5(k)). Then for all [51 [ _< r~, 1521 _< r~ and k >_ 0 I~(k, 61)1 = Io(z(k) + 51)1 -< qra. Define
~a xg(k, 5) a O(z(k) + 6(k)) - g(z(k)) - ~x(z(k))" 5(k). Then as before
I~(k, 51) - ~(k, 52)1 =
[O(z(k) + 51) - g(z(k) +
52)1 _ ~161 - 521.
Thus the nonlinear portions of (5.5) satisfy the boundedness conditions of the Total Stability Theorem provided [Xol < rz. Hence f12(( "3t-/~) "~ 0~2 < 1 and [Xol = tZo[ < rz imply that 16(k)l _
/~2r/rn
< r~.
1 -- (a2 + (f12)
Therefore, for the solution of the original equation (5.2) we have Ix(k)l < Iff(xo)l + 15(k)l = Iz(k)[ + 15(k)l -
fl2 rlr ~ 1 - ( .2 + ~/~2)
whenever f12(( + t/) + ~2 < 1 and [Xol = IZo[ _< rz, which completes the proof.
9
Conditions for Stability of the Extended K a l m a n Filter
11
6. EKF Stability In this section Theorem 5.3 is applied to the E K F error dynamics. In Theorem 6.1 it is shown that condition C1 holds under conditions on the observability and controllability of the signal model given a sufficiently small initial value. In Lemma 6.1 it is shown that condition C2 holds under the same assumptions. In Lemma 6.2 an explicit equation for the bound for the noise and linearization error-based perturbation component of the error dynamics is derived, and in Lemma 6.3 a similar bound is given for the nonlinear, undriven component. The stability result itself is presented in Theorem 6.2.
6.1. Observability and Controllability Define the observability Gramian of [Fz, R - m i l l along the trajectory {z(k)} as k
(9(k, N) = ~
t~(i, k)T H(i)T R(i)-l H(i)O(i, k)
(6.1)
i=k-N
for some N _> 0 and for all k _~ N, where (I)(k2, k:) = F~(k 2 - 1)F~(k - 2)"" F~(kl). Similarly, define the controllability Gramian of [F z, Q] along the trajectory {z(k)} as k-1
(g(k, N) =
~
O(k, i + 1)Q(i)~(k, i + 1) T.
(6.2)
i=k-N
A system is said to be controllable (observable) along some trajectory {z(k)} if there exists N such that for all Rx > 0 there exists 0 < ~, < Rx, ai(R~, e,, N) and bi(R~, er, N), i = 1, 2, such that for some arbitrary sequence {0(k)}, b~b(k)l < R~, and all {v(k)} such that Iv(k)l _< ~,
all>_Cg(k,N)>a2 I,
0
(6.3)
b~l<(9(k,N)
0
(6.4)
where these Gramians are evaluated along the trajectory z(k) = t~(k) - v(k), i.e.
Fz(k) = oO~fx(z(k))= ~(O(k) - v(k)). 6.2. Standing Assumptions on the Signal Model The following assumptions will be assumed to hold for the remainder of this section. The nonlinear signal model has a linear output map, f ~ C3(~ n, R"), (Sf/Ox)(x) is invertible for all x ~ R", and for all k Ix(k)l ___R~;
(6.5)
IIn(k)ll -< Ps;
(6.6)
E[w(k)w(k) T] = O(k) >_ 611 and E[v(k)v(k) T] = R(k) > 521
and
Iw(k)l < IIw[I < ~ ;
(6.7)
Iv(k)l _ Ilvll < ~ .
(6.8)
12
B.F. La Scala, R. R. Bitmead, and M. R. James
Furthermore, it is assumed that we can find N and e, < Rx such that the observability and controllability conditions (6.3) and (6.4) hold. The E K F equations for this system are given by (3.3)-(3.7), and error dynamics of the E K F when applied to such a signal model are given by (4.3). 6.3. Signal M o d e l Bounds
Since f ~ C3(~ n, Rn), we can find Pl, P2, P3 > 0 such that o0~fx(X) < Pl,
(6.9)
~X2(
<-- P2,
(6.10)
~X3(X)O3f
N
(6.11)
Pa
for all Ixl < Rx + e,. Furthermore, by the continuity assumptions on f, there exists a P4 > 0 such that
O0-s 0 - ~xx(X2) ~f ~ p4Ixl -
x21
for all [xll <_ Rx and Ix2[ _< R~, and therefore 0f(x1 ) __ Of
Ux
02f ,
. ,
u x ( X z ) - ~x~x2tXz~'tx~ - x z )
<- 89
- xzl 2
(6.12)
[DS, Chapter 4]. Let 1 p ---- a t -t- - - ,
bl
1 q =--+
b~,
a2
1 s =-- +
b2 + pf61-1.
a2
Consider the equations for the evolution of the EKF gain, K~(k), and the covariance matrices Pz(klk) and Pz(k + ilk) along the arbitrary trajectory z ( k ) = O(k) - v(k), which are given by the equations Pz(klk) = [ I - K z ( k ) n ( k ) ] P z ( k l k - 1), Pz(k + Ilk) = F~(k)Pz(klk)F~(k) r + Q(k), Kz(k) = P~(klk - 1 ) H ( k ) r [ H ( k ) P z ( k l k - 1)H(k) r + R(k)] -1.
These are the same equations as those for a Kalman filter applied to the linear
Conditions for Stability of the Extended Kalman Filter
13
signal model ~(k + 1) = F~(k)~(k) + w(k), Y(k) = H(k)~(k) + v(k), where Fz(k) = (~f/Ox)(~(k) - v(k)). Thus we can use the results of Deyst and Price [ D P ] on the stability of the time-varying Kalman filter to obtain the bounds
q-~ I <<_Pz(k[k) <_pI, q-~I <_ P~(k + l l k ) _< sI which depend on er, R~ and N.
6.4. Preliminary Results The following result gives sufficient conditions for the stability of the E K F when applied to a deterministic signal model when the linearization errors are neglected. This theorem only requires that these properties hold in some subset of the er-ball centered on z = 0.
Theorem6.1.
Consider the nonlinear equation z(k + 1 ) = [ I - K~(k + 1)H(k + 1)]~x (X(k)).z(k ) & f(k, z(k)),
(6.13)
where ~(k) = x ( k ) - z(k), K~(k) = P~(k[k P~(k +
1]k) =
1)H(k)r[H(k)P~(k]k
-
1)H(k) r +
R(k)] -1,
F~(k)P~(klk)F~(k) w + Q(k),
n~(k[k) = [ I - K ~ ( k ) U ( k ) ] n ~ ( k l k
-
1),
F~ = ~ ( x ( k ) - z(k)). Given R x > 0, select N and er < Rx such that the observability and controllability conditions (6.3 and 6.4) hold. Let
e~=min e,,
-Pl+
p2+q s ~ - Y ) )
where 0 < y < 1/sp 2, then
Iz(O)l < (pq) - l/2
;'
(6.14)
14
B. F. La Scala, R. R. Bitmead, and M, R. James
implies Iz(k)l <_ (pq)~/2 ( 1 - - Tq)k/alz(O)l flek Iz(O)l
(6.15)
for all k > O. (Note that, as a consequence, we know that lz(k)l < ~ for all k >_ 0.)
Proof.
We shall prove this result using a Lyapunov stability argument. Let V(k, z) = zT p~(klk)-l z;
then p-1 iz(k)12 _ V(k, z(k)) ~ qlz(k)l 2 for all k and ]z(k)[ <_ e,. Using the equations for the E K F and the matrix inversion lemma, it can be shown that F~(k)Tn~(k + l lk)-lF~(k) = p~(klk) -~ - p~(klk) -~ [Pe(k[k) -~ + F~(k)rQ(k)-~F~(k)]-iP~(klk) -~,
P~(k + lJk)-lK~(k + 1 ) H ( k + 1) = H(k + 1)T[H(k + 1)P~(k + llk)H(k + 1)r + R(k + 1)]-lH(k + 1).
Therefore for [z(k)[ <_ er AV(k, z(k))
= V(k + 1, z(k + 1)) - V(k, z(k)) = z(k)TF~(k)r[I -- K~(k + 1)H(k + 1)]Tp~(k + l[k + 1)-1 x [I - K~(k + 1)H(k + 1)]F~(k)z(k) - z(k)rP~(klk)-lz(k) = z(k)WFx(k)rp~(k + 1 ]k)-lFx(k)z(k) - z(k)rp~(kIk)-~z(k) - z(k)rFx(k)rH(k + 1)[U(k + 1)P~(k + llk)H(k + 1)T + R(k + l ) ] - l H ( k + 1)Fx(k)z(k) <__- z(k) T P~(klk) -1 [P~(klk) -I + F~(k)r O(k) -~ F~(k)]-I n~(klk)-~ z(k) + z(k)TF~(k)vn~(k + 1 ]k)-~B~(k)z(k) + z(k)TB~(k)Tpdk + l l k ) -1F~(k)z(k) + z(k)TB~(k)Tp~(k + l l k ) -~B~(k)z(k),
where B
(k)
=
-
-
z(k))
-
02f
-
zIk))"
z(k).
Conditions for Stability of the Extended Kalman Filter
Therefore
15
{-1
}
AV(k, z(k)) < ~p2 + PlP,~q[z(k)[ 2 + 88
'* [z(k)[ 2.
Now 1
AV(k, z(k)) < -7]z(k)[ 2, 0 < y < sp--~, provided
-1 --+
sp 2
PlP4qiz(k)] 2 + 88
4 < -7
which will hold when
1 1 Iz(k)]_<
-Pl+
2+q
s~-
1/2. ~
Let
0,sp2 and suppose [z(j)] < ez f o r j = 0 . . . . , k - 1 then
AV(k - 1, z(k - 1)) < - ~ ] z ( k - 1)[ 2. Thus
V(k, z(k)) < (1 - 7p)V(k - 1, z(k - 1)) and
V(k, z(k)) < (1 - 7p)RV(0, z(0)).
Thus p-1 ]z(k)12 < (1 - ~p)kq[z(O)l z. 2 Thus, by Now, since 1 - yp < 1 and pq > 1, [z(0)l z < e2/pq implies ]z(k)l 2 _< ~z. induction, ]z(0)l 2 < e2/pq implies AV(k, z(k)) <_ -y]z(k)i 2 for all k > 0. Furthermore the bounds on the L y a p u n o v function give [z(k)l -< (pq)l/2 1 --
[z(O)l _< ez
for all k > 0, which completes the proof. N o w consider the linear equation 2(k + 1) = u~J~(k,z(k))'~(k) oz
(6.16)
16
B.F. La Scala, R. R. Bitmead, and M. R. James
where f a n d z(k) are defined in the previous theorem. Differentiating f(k, z(k)) gives ~-~ = [I - K~(k + 1)H(k + 1)]F~(k)
t~K~(k ~z + 1)H(k + 1)F~(k)z(k).
Therefore (6.16) can be writen as ~(k + 1) = A(k)~(k) + ~(k, g(k)),
(6.17)
where A(k) = [I -- K~(k + 1)H(k + 1)]F~(k) and j~(k, ~) =
t?Ke(k + 1)H(k + 1)F~(k)z(k)~(k). 0z
With the equation in this form we can now apply Corollary 5.2, which gives the following lemma, showing that the linearized, undriven portion of the EKF error dynamics is asymptotically stable when linearization errors are neglected. It shows that the EKF error dynamics under the standing assumptions satisfy condition C2 of Theorem 5.3. Lemma 6.1. Consider (6.17) which is the linearized, undriven portion of the EKF error dynamics, neglecting linearization errors. I f [z(0)[ < ez(pq) -1/2 then the linear system ~(k + 1) = A(k)~(k) is exponentially asymptotically stable and its transition matrix, (I)~(k2, k 1), satisfies HOe(k2, kl)'l -- (pq)i/2 ( 1
__~)k/2.
Also, the function f2 is homogeneous and satisfies a Lipschitz condition in the ez-ball, i.e. 1. f2(k, O) = O, 2. IIj~(k, zl) -J~(k, z2)[[ --< Celzl - z2[, for all I~ll < 8~, I~ll <- ez and k >_O for some (~ > O. Therefore if Iz(O)l < ez(pq) -1/2 and
(pq)l/2(~ + 1 -
< 1,
where 0 < ~ < 1/sp 2, then I~(k)[ < (pq)l/2 for all k > O.
1 --
d- ( ~ ( p q ) l / 2
[~(0)] < ez by construction
Conditions for Stability of the Extended Kalman Filter
17
Proof. It can be shown that the linear portion of (6.17) is expoentially asymptotically stable using the same Lyapunov stability argument used in Theorem 6.1. All that remains in order to apply Corollary 5.2 is to show that for all k and I~ll -< erand l~2l ___~r, 1. j~(k, O) = O; 2. [IJ~(k, N1) - J~(k, N2)II < (e[~l - ~2[. Since
OK~(k +
f2 (k, ~) =
&
1)H(k + 1)F~(k)z(k)~(k)
condition (1) clearly holds. To determine bounds for J~ note that
OK~(k + 1) Oz ~P~(k +
8z
lJk)H(k + 1)T[H(k + 1)P~(k + llk)H(k + 1)T + R(k + 1)1-1
+ Pe(k + llk)H(k + 1)T~[H(k + 1)Pdk + l[k)H(k + 1)T + R(k From (3.6)
OP~(koz + 1 L k ) ~F~zk)p~(k[k)Fe(k)T + F~(k)P~(k]k)~F~k)T -
~x2(X(k)- z(k))P~(klk)F~(kLk)F~(k)T f~2
-
Fe(k)P~(kLk)a-~(x(k) - z(k)). 02-
Thus under the assumptions
t?Pdkoz(k) +l[k)
-< 2plP2P ~=~v"
Furthermore 0
~z[H(k + 1)Ps(k + llk)H(k + 1)T + R(k + 1)3 -1 = -[H(k + 1)P~(k + l[k)H(k + 1)T + R(k + 1)] -1
• [R(k + 1)a (k +z llk).(k + 1)Tj x [H(k + llP~(k + llk)H(k + 1)T + R(k
+ 1)] -1
+ 1)] -1.
18
B. F. La Scala, R. R. Bitmead, and M. R. James
hence
-~[H(k + 1)P~(k + lIk)H(k + l) r + R(k + 1)] -1
__~ p2(~22(~p
and thus
dKe(k + 1) Oz < 6vPs6f~(1 + sPg62~) ~- ~" Therefore IIf2(k, 71) - j~(k, 72)11 ~
S,psp,~zl~i - 7,1 ~ ~ ,
(6.18)
hence condition (2) is also satisfied. Apply Corollary 5.2 completes the proof.
9
The next lemma derives a bound for the noise and linearization error-based perturbation component of the E K F error dynamics. Lemma 6.2. Consider the perturbation terms in the EKF error dynamics (4.3) due to the noise and linearization errors,
~](e(k), k) a [I - Ke(k + 1)H(k + 1)] [w(k) - xi(x(k ), - e(k))] - K~(k)v(k), where K(k) is given in Theorem 6.1. There exists ~ > 0 such that [~(e~, k)l _< ~/8,; and i~(e 1, k) - j(e2, k)[ _< t/[e 1 - e21 for all lel[ -< e,, le21 -< e, and k >_ O. Proof.
The bounds on the error covariance matrices and the noise processes give ]O(e~, k)] _< IIP~(k + 1]k + 1)P~(k + llk)-~[w(k) - xi(x(k ), e(k))][I + IIPe(k + llk + 1)g(k + 1)R(k + 1)-iv(k)ll
<_pq([lw,[
+1~p4e~) 2 + pp,621],vl[.
Now
d~ _ Oe(k)
dK~(k + dK~(k + ) 1)H(k + 1)[w(k) - xi(x(k), -e(k))] 1-v(k) de(k) Oe(k) - [I - K~(k + 1)H(k + l)] d~cf(x(k), - e(k)) de(k)
SO 1
2
~k(Psllwrl + IlvlP + ~p4ps~,) + 2pqpl. Defining 1 2 1 2 ~1a max {pq(tlwll + eP4er ) + PP562111vll, ~Sk(PsIfwll + Ilvll + gP4Pser ) + 2pqPx} (6.19)
completes the result.
9
Conditions for Stability of the Extended Kalman Filter
19
The final lemma derives a bound for the nonlinear, undriven component of the E K F error dynamics. Lemma 6.3.
Consider the function f(k, z(k)) = [I - Ke(k + 1)H(k + 1)]O~(x(k)).z(k)
which is the homogeneous portion of the EKF error dynamics neglecting linearization errors. There exists ( > 0 such that
~
(z(k)) <_
for all iz(k)[ _< er and k >_O. Proofi
Recall that
af Oz
[I - K~(k + 1)H(k + 1)]Fx(k )
OK~(k + 1)H(k + 1)Fx(k)z(k) Oz
SO
02fOZ 2
2 OKe(k + l)H(k + 1)F~(k) --
~Z
02Ke(k + l)H(k + 1)Fk(k)z(k), 07_.2
where
02K~(k + 1) 0z 2 -
02p~(k + l[k)H(k + 1)T[H(k + 1)P~(k + lik)H(k + 1)T + R(k + 1)], ~ Ox2
+
2 02P~(k + 11k)H(k + 1)T~[H(k + 1)P~(k + llk)H(k + 1)T + R(k + 1)] -~ 0z
+ P~(k + llk)H(k + 1 ) T f , [ H ( k + 1)P~(k + l[k)H(k + 1)T + R(k + 1)] -~. 07_,-
Now
02pe(k + l l k ) Ox2
- ~x3(X(k) - z(k))P~(kl k)F~(k) T 02f
02
-- 2~x2(X(k ) - z(k))P~(k[k)o--~2(x(k ) - z(k)) T
~f03 + F~(k)P~(kl k)~-~(x(k) - z(k)) ux-
20
B. F. La Scala, R. R. Bitmead, and M. R. James
and hence
a2P~(k +llk) a-x~
___epIp3pl + p~).
Thus there exists a 6kZ(&, P2, P3, PS, 32, P) > 0 such that c32Ke(k + 1) ~z 2 < 6k2
for all k _> 0. Therefore (6.20)
2fdfiz2 <_ 2pips6 k + plp56k2e,
&(
(6.21)
which completes the proof. 6.5. Main Result
The results of the previous section can be combined to give the following result for the stability of the E K F when applied to a stochastic, discrete time nonlinear system. Theorem 6.2 (EKF Stability). given by the equation
Consider the error dynamics of the E K F which are
e(klk) = [ I - K ~ ( k ) H ( k ) ] F , ( k - 1 ) e ( k - l l k - 1) + [I - K~(k)H(k)]xy(x(l- 1), - e ( k - Ilk - 1)) + [I - K~(k)H(k)] w(k - 1 ) - Ke(k)v(k), where af Xj(X, --e) = f ( x -- e) -- f(x) + ~x (X)" e when the E K F is applied to a signal model with a linear output map which satisfies the standing assumptions (6.5)-(6.8). Select N and 0 < e, < R x such that the observability and controllability conditions (6.3) and (6.4) are satisfied. Then if
fl(~ + t/) + ~ < 1,
(6.22)
fl(~ + c~ < 1,
(6.23)
leol < ez(Pq)-1/2,
(6.24)
where and ez, ~ and fl, ~, q and ( are given by (6.14), (6.15), (6.18), (6.19) and (6.21) respectively, le(kfk)] < #~kFeol + fl(~ + ~fl)*leol + fltl(Rx - fl~z) < ~, 1 -
for all k >>_O.
(~ +
~#)
Conditions for Stability of the Extended Kalman Filter
21
Proof. To prove this result we shall appeal to Theorem 5.3. From Theorem 6.1 and (6.24) we know that the solution of z(k) = [I - K ~ ( k ) n ( k ) ] F x ( k
- 1)z(k),
z(O) = eo,
where ~(k) = x ( k ) - z(k), satisfies
Iz(k)l ___~ i z ( 0 ) l and so condition C1 of Theorem 5.3 is satisfied. From Lemma 6.1 and (6.23) and (6.24) we know that the solution of ~(k + 1) = ~@(k){[l - K d k ) H ( k ) ] F x ( k
-- 1)z(k)}~(k),
~(0) = eo,
z(O) = eo
will satisfy I~(k)l < fl~kI~(0)1 which satisfies condition C2. Now ties < e,, so with rx = e, and rz = ez the bounds on the nonlinear components of the error dynamics are given by Lemma 6.2 and Lemma 6.3. Noting that ~t(klk) = x ( k ) - e(klk) and applying Theorem 5.3 completes the proof. Note that if I<,1 -< 2 then (6.23) is automatically satisfied if (6.22) holds. 9
7. FrequencyTracking Stability We are now in a position to show that our E K F observer for the frequency tracking problem will, in fact, be able to track the underlying frequency of its input signal subject to conditions on the evolution of the target frequency and the design parameters of the EKF. To do this we will show that the observer we designed in Section 3 satisfies Theorem 6.2. For this we need to consider the properties of the received signal and also the properties of the signal model used to design the E K F observer. In order to obtain any meaningful results from filtering we require that the state of the received signal be bounded for all time. The signal model chosen does not ensure this, but for the frequency tracking problem to be well posed we need to sample the received signal fast enough to make 0 < x3(k) < 2n. Hence, in practice the state of the signal will satisfy Ix(k)l -- x/xl(k) 2 + x2(k) 2 + xa(k) 2 < ~ / 1 + 4re2
< 6.4 for all k. Consider now the signal model used to design the EKF. Let II'[I be the induced Euclidean norm. We have IIH(k)lj = 1
for all k.
22
B.F. La Scala, R. R. Bitmead, and M. R. James
From the noise processes used in the design of the E K F observer, we have
Q(k) > q~I, R ( k ) = rl. We assume the noise processes are bounded by some multiple of their standard deviation, i.e.
[Iwll -- cx.,/~, Ilvl[ = cz~,~ for some constants c1 > 0 and c2 > 0. The final conditions on the signal model used to design our observer are that f e C3(~ n, R n) and df/Ox be invertible. In our case the derivatives o f f are continuous and will be bounded in a region, but these bounds depend on the size of the region. That is
~
(x(k) - e(klk))
O2f ~x~x2(X(k) - e(klk))
~
<_ 2(Rx + er), _ x//2(R~ + e,), <
(x(k) - e(kFk)) < v/2(Rx + ~,).
Furthermore the determinant of Of/ax is simply 1 - e and since 0 < e < 1 it is therefore invertible. All that remains in order to apply Theorem 6.2 is to show that we can find region in which the Gramians of the E K F are positive definite and bounded along the trajectories of the EKF. From the definitions of the Gramians and the E K F observer, the controllability Gramian Cg(k, 1) is simply Q(k) and hence
q21 >_ ~(k, 1) > q~I for any positive e,. The observability Gramian of [F, R-1/2H] is 2
-
1
0
r
r
1)=
0
2 /.
--7~(k, k r
1
--72(k, k Y
1)
1)
l {ml(k, k - 1)2 + m2(k, k - 1)2}
Conditions for Stability of the Extended Kalman Filter
23
where k-1
~o(k, i) = ~, x3(J), j=i k
yl(k, i) = .~. (1 - e y - ' { - 2 ~ ( j ) sin (p(k,j) - 22(J) cos q~(k,j)}, J=L
k
?2(k, i) = }-" (1 - e)/-i{21(j) cos @(k,j) - 22(j) sin q3(k,j)}, j=i k
ml(k, i) = ~. (1 - e)i-k{2i(j) sin ~(i,j) + 22(j) COS ~(i,j)}, J=l
k
m21(k, i) = ~ (1 - e)J-k{--2i(j) COS ~(i,j) + 22(j) COS ~(i,j)}, j=i
~(i,j) = q)(k, j) - q)(k, i). This has eigenvalues 2 r'
1 2r {2 + wa --- x / ~
+ 4}'
where
w3 = 2,(k[k) 2 + 22(k[k) 2 = {xi(k ) - el(k)} 2 + {x2(k) - e2(k)} 2. Since (x~(k), x2(k)) is on the unit circle, restricting e, to the range 0 < e, < 1 ensures o- < w 3 < 3 + Rx where a > 0 and arbitrarily small. The m a x i m u m eigenvalue of (9(k, 1) is then 5 )~max < - . r
The minimum eigenvalue of (9(k, 1) is (7 •min > ~ "
Thus for the E K F frequency tracker we can set Rx=7,
0
1,
Pi = 2(Rx + e,),
P2 = w/2(R~ + e,),
P3 = v / 2 ( R . + e,), fii=qt,
62 = r ,
a i = q2,
a2 = q t ,
a bl=~
5 '
b2=-'r
p+ = v/2(R~ + ~,),
P5 = 1,
24
B.F. La Scala, R. R. Bitmead, and M. R. James
To satisfy Theorem 6.2 we need condition (6.22), fl(( + t/) + a < 1 to hold. Recall that the stability parameters a and fl determine the decay rate of the linear portion of the error dynamics. The stability parameter ( is a bound on the nonlinear portion of the dynamics and t/is a bound on the term due to the noise-based perturbations and linearization errors. The size of the parameters will depend proportionally on the size of the ball {e: lel < e,} and, in the case of~/, on the size of the noise processes. Thus if we know the nature of the noise processes and design an E K F observer using those values we can ensure the condition on the stability parameters is satisfied only by considering a sufficiently small region. On the other hand, we can regard r, q~ and q2 as design variables rather than as estimates of the true covariances of the noise processes. The first three stability parameters, a, fl and ~--are functions of these design values only. The stability parameter tt is a function of the properties of the noise in the received signal as well as the design values, through the bounds Ilwll and Ilvll. Analyzing the first two stability parameters as functions of the design variables gives the following table. This table gives indicative results for the properties of the stability parameters with respect to each design variable.
Table 1. Stability parameters as functions of the design variables.
B ql q2 r
decreasing increasing minimized by
decreasing increasing minimized by
r~,
6 2,
Note:
(Sp(q_+_
1. r,, = \
4~q
From this table, and the constraint that ql _< q2, 3 we can see that designing our E K F frequency tracker with Q(k) = diag(q 1, q~, q2), where ql = q2 = q and q is relatively small, will enhance the stability of the filter even though we are supposing that the first two components are obtained via a noiseless transformation of the frequency, x 3. Note that q is an E K F design parameter. If this is taken to be smaller than the value indicated by the maximal slew rate of received signal, the stability parameter t/will be increased.
3 If ql > q2 then ~t and fl will be increasing functions of ql and decreasing functions of q2-
Conditions for Stability of the Extended Kalman Filter
25
8. Conclusion
In this paper we have given sufficient conditions for the stability of the error system of the extended Kalman filter for a general nonlinear signal model with a linear output map. These results give coupled conditions on: a bound on the initial error; bounds on the noise processes; observability of the signal model state; controllability of the process noise with the signal model state map; and smoothness properties of the signal model. Within the regime of satisfaction of the sufficient stability conditions of Theorem 6.2 there is a trade-off between these requirements. These extend the results of Song and Grizzle [SG], which dealt only with the local stability of the unforced error equations. The specific example of an EKF frequency tracker was considered and conditions developed to ensure the tracking error could be maintained within guaranteed bounds. The key features to yield these bounds are: sufficiently small initial frequency estimate error; sufficiently small measurement noise; sufficiently slow slew rate of the actual frequency; larger designed slew rate and measurement noise for the EKF. These augmented design considerations are required partially to account for nonlinear effects on the linearized problem and also to prevent filter divergence (cf. [AM, Chapter 6]). The results reported here represent a natural extension of linear Kalman filter theory to the nonlinear case. That is, they collapse to the linear theory where appropriate. Necessarily they are more restrictive, although evidence in the frequency tracking case IS] indicates that the design criteria and modes of failure are properly identified. Further work could focus on: removing the assumption that the signal state map is invertible; replacing the observability condition with a weaker detectability condition; extending these results to signal models with a nonlinear output map. Each of these extensions would appear to be feasible and the last is easily done. References [ABJ] B. D. O. Anderson, R. R. Bitmead, C. R. Johnson, Jr, P. V. Kokotovic, R. L. Kosut, I. M. Y. Mareels, L. Praly, and B. D. Riedle. Stability of Adaptive Systems: Passivity and Avera#in# Analysis. M.I.T. Press, Cambridge, Massachusetts, 1986. [AM] B. D. O. Anderson and J. B. Moore, Optimal Filtering. Prentice-Hall, Englewood Cliffs, New Jersey, 1979. [BBJ] J. S. Baras, A. Bensoussan, and M. R. James. Dynamic observers as asymptotic limits of recursive filters: Special cases. SIAM J. Appl. Math., 48 (1988), 1147-1158. [CGS] S. W. Chart, G. C. Goodwin and K. S. Sin. Convergence properties of the Riccati difference equation in optimal filtering of nonstabilizable systems. IEEE Trans. Automat. Control, 29 (1984), 110-118. IDS] J. E. Dennis and R. B. Schnabel. Numerical Methods for Unconstrained Optimization and Nonlinear Equations. Prentice-Hall, Englewood Cliffs, New Jersey, 1983. [DP] J. J. Deyst, Jr and C. R. Price. Conditions for asymptotic stability of the discrete minimumvariance linear estimator. IEEE Trans. Automat. Control, 13 (1968), 702-705.
26
B.F. La Scala, R. R. Bitmead, and M. R. James
[J] B. James. Approaches to Multiharmonic Frequency Tracking and Estimation. Ph.D. thesis, Australian National University, Canberra, Australia, 1992.
FKG] C. N. Kelly and S. C. Gupta. The digital phase-locked loop as a near-optimum FM demodulator. IEEE Trans. Comm., 20 (1972), 406-411.
[NP] A. Nehorai and B. Porat. Adaptive comb filtering for harmonic signal enhancement. IEEE Trans. Acoustics, Speech Signal Processing, 34 (1980), 1124-1138.
[N] H. Nijmeijer. Observability of autonomous discrete time non-linear systems: A geometric approach. Internat. J. Control, 36 (1982), 867-874.
[PA] P. J. Parker and B. D. O. Anderson. Frequency tracking of nonsinusoidal periodic signals in noise. Signal Processing, 20 (1990), 127-152.
[QF] B. G. Quinn and J. M. Fernandes. A fast efficient technique for the estimation of frequency. Biometrika, 78 (1991), 489-497.
IS] D. L. Snyder. The State-Variable Approach to Continuous Estimation with Applications to Analog Communications Theory. M.I.T. Press, Boston, Massachusetts, 1969.
[SG] Y. Song and J. W. Grizzle. The extended Kalman filter as a local asymptotic observer for nonlinear discrete-time systems. J. Math. Systems, Estimation Control, $ (1995), 59-78.
[SB] R. L. Streit and R. F. Barrett. Frequency line tracking using Hidden Markov Models. IEEE Trans. Acoustics, Speech Signal Processing, 38 (1990), 586-598.
