IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 42, NO.

4, APRIL 1997 581

[3] J. B. Lasserre, A trace inequality for the matrix product, IEEE Trans. The EKF consists of using the classical Kalman filter equations
Automat. Contr., vol. 40, pp. 15001501, 1995. to the first-order approximation of the nonlinear model about the
[4] M. Mrabti and M. Benseddik, Bounds for the eigenvalues of the last estimate. The literature is vast about this subject, and we refer
solution of the unified algebraic Riccati matrix equation, Syst. Contr.
Lett., vol. 24, pp. 345349, 1995. the reader to [7], [11], [15], [16], and [19] and the references therein.
[5] A. W. Marshall and I. Olkin, Inequalities: Theory of Majorization and However, few works have been performed to analyze the stability and
Its Applications. Orlando, FL: Academic, 1979. convergence of the filter. The main difficulty arises from the fact that
[6] R. T. Rockafellar, Convex Analysis. Princeton, NJ: Princeton Univ. the EKF equations are only approximate ones. So, the corresponding
Press, 1970.
propagation equations are available only if the estimate belongs to a
neighborhood of the actual state.
An interesting study of asymptotic behavior of the EKF, used
for the joint parameter and state estimation of linear time-invariant
systems, was developed by Ljung in [11]. For this particular case,
Convergence Analysis of the Extended Kalman some modifications, such as coupling between parameters vector
Filter Used as an Observer for Nonlinear and the Kalman gain, were introduced to enhance convergence of
Deterministic Discrete-Time Systems the EKF. More recently, in a synthesis work on nonlinear discrete-
time systems, sufficient conditions of the EKF for noisy systems
M. Boutayeb, H. Rafaralahy, and M. Darouach used as a local asymptotic observer for the deterministic case have
been established by Song et al. [15]. They have also shown that
conditions needed to ensure the uniform boundedness of certain
AbstractIn this paper, convergence analysis of the extended Kalman Riccati equations are related to the observability properties of the
filter (EKF), when used as an observer for nonlinear deterministic
discrete-time systems, is presented. Based on a new formulation of the considered nonlinear system.
first-order linearization technique, sufficient conditions to ensure local Recently, Cicarrella et al. [18] have developed a robust observer,
asymptotic convergence are established. Furthermore, it is shown that which uses n output values and the inverse of the observabil-
the design of the arbitrary matrix, namely Rk in the paper, plays an ity matrix at each step, and the local convergence analysis for a
important role in enlarging the domain of attraction and then improving
multi-input/single-output (MISO) nonlinear discrete-time system was
the convergence of the modified EKF significantly. The efficiency of this
approach, compared to the classical version of the EKF, is shown through studied.
a nonlinear identification problem as well as a state and parameter Motivated by the identification problem of time-invariant nonlinear
estimation of nonlinear discrete-time systems. systems [3], [4], we address here the problem of stability and the
Index TermsConvergence analysis, deterministic nonlinear discrete- convergence of the EKF when used as a deterministic observer
time systems, extended Kalman filter, Lyapunov approach. for multi-input/multi-output nonlinear discrete-time systems written
in their general form. Based on a new formulation for the exact
linearization technique, we introduce instrumental time-varying ma-
I. INTRODUCTION trices for the stability and convergence analysis. It is pointed out
Since the 1960s, many research activities have been developed that, under mild conditions, asymptotic behavior of the EKF may
to deal with the problem of state estimation for nonlinear dynamical be improved significantly even for bad first-order approximation.
systems. The main motivation for doing so is that most physical To show accuracy and performances of this technique, we use the
processes are described by nonlinear mathematical models. Thus, modified EKF at first as a parameter estimator for the Hammerstein
several nonlinear state estimation methods have been performed to model and secondly as a simultaneous state and parameter estimator
increase the accuracy and performances of the control system design. of a nonlinear model.
Generally, we distinguish two approaches for nonlinear observers
design. The first one is based on some nonlinear state transformation II. PROBLEM FORMULATION
using the Lie algebra. This approach brings the original system
The nonlinear systems considered here are of the form
into a canonical form from which the design of state observers is
performed using linear techniques in the new coordinates. Necessary x k+1 = f (xk ; uk ) (1a)
and sufficient conditions for a standard nonlinear system to be state yk = h(xk ; uk ) (1b)
equivalent to the nonlinear canonical form, for both continuous and
discrete-time cases, have been established in [2], [8], [9], and [14]. where uk 2 Rr and yk 2 Rp are the input and output vectors at time
We notice that only a few classes of forced nonlinear systems are instant k: We assume that f (xk ; uk ) and h(xk ; uk ) are differentiable
considered by this nonlinear transformation. on Rn : The EKF for the associated noisy system that we use here
The second approach is without transformation and is based on the as an observer of (1a), (1b) is:
linearized model. In spite of the local convergence of this method, it 1) measurement update
is widely used in practice and generally gives good results under less
restrictive conditions than the first approach [6], [7], [12], [13], [16]. ^k
x +1 = x^k+1=k + Kk+1 ek+1 (2)
One of the most popular estimation techniques largely investigated T T
Kk+1 = Pk+1=k Hk+1 (Hk+1 Pk+1=k Hk+1 + Rk+1 )
01 (3)
Pk+1 = (I 0 Kk+1 Hk+1 )Pk+1=k
for state estimation of nonlinear systems is the extended Kalman (4)
filter (EKF).
2) time update
Manuscript received June 5, 1995; revised October 17, 1995.
The authors are with the CRAN CNRS URA, Cosnes et Romain 54400,
France.
^k
x +1=k = f (^xk ; uk ) (5)
T
Publisher Item Identifier S 0018-9286(97)02050-3. Pk+1=k = Fk Pk Fk + Qk (6)

00189286/97$10.00 1997 IEEE

582 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 42, NO. 4, APRIL 1997

where The exact equality represented here by (15) and (16) is the key
ek+1 = yk+1 0 h(^xk+1=k ; uk+1 )
point of our approach since the convergence study will be performed
without any approximation while eik+1 and x
(7)
~jk+1=k are written in
Fk = F (^xk ; uk ) = @f (xk ; uk ) (8) a first-order representation. Now if we introduce the signal vector,
@xk x =^
x we obtain

Hk+1 = H (^xk+1=k ; uk+1 ) = @h (xk+1 ; uk+1 )

: k+1 ek+1 = Hk+1 x~k+1=k (17)
@xk+1 x =^x x~k+1=k = k Fk x~k (18)
(9)
where k+1 2 R and k 2 Rn1n are unknown
p1p
time-varying
When used as an observer for linear deterministic systems, Qk and diagonal matrices
Rk are arbitrarily chosen, for example, as 0n and Ip , respectively. In
the case of linear stochastic systems, optimal filtering in the maximum k+1 = diagf1k+1 ; 1 1 1 ; pk+1 g (19)
likelihood sense is obtained when Qk and Rk are the covariance ma-
trices of the system and measurement noises, respectively. However, and
for nonlinear noisy systems, optimality has not been proved, but in
general we continue to consider Qk and Rk as covariance matrices.
k = diagf1 ; 1 1 1 ; nk g: (20)
Hereafter, we will show that the design of Rk plays an important By subtracting both sides of (2) from xk+1 ; we obtain
role in improving the convergence of the EKF when used as an
observer of (1a), (1b). However, since (1a), (1b) is a deterministic x~k+1 = x~k+1=k 0 Pk+1=k Hk+1 (Hk+1 Pk+1=k HkT+1
system, we set Qk = 0: 01
+ Rk+1 ) ek+1 : (21)

III. CONVERGENCE ANALYSIS On the other hand, from (3) and (4), we have
In this section we give a simple approach for setting up the Pk+1 HkT+1 Rk0+1
1
convergence analysis of the considered nonlinear systems. It is T T
= Pk+1=k Hk+1 (Hk+1 Pk+1=k Hk+1 + Rk+1 )
01 (22)
emphasized that under the local reconstructibility condition [19], the
asymptotic convergence of the EKF is ensured when the arbitrary and
matrix Rk is adequately chosen.
Let us note by x ~k+1 and x ~k+1=k the state estimation and state Pk0+1
1 = P 01 + H T R01 Hk+1 :
k+1=k k+1 k+1 (23)
prediction error vectors respectively defined by
Substituting (22) into (21) and (21) into (12), the quadratic function
x~k+1 = xk+1 0 x^k+1 (10) becomes
x~k+1=k = xk+1 0 x^k+1=k
Vk+1 = (~xk+1=k 0 Pk+1 HkT+1 Rk0+1
1 ek+1 )T
(11)

and the candidate Lyapunov function Vk+1 as 1 Pk0+11 (~xk+1=k 0 Pk+1 HkT+1 Rk0+1
1 ek+1 ) (24)
Vk+1 = x~Tk+1 Pk0+1
1 x~k+1 : (12)
or
Our aim here is to determine conditions for which fVk gk=1111 is
a decreasing sequence and to show the EKF limitations when the
Vk+1 = x~k+1=k Pk0+1
1 x~
k+1=k 0 x
T T 01
~k+1=k Hk+1 Rk+1 ek+1

first-order approximation is used. One classical approach consists of 0 ekT+1 Rk0+1

1 Hk+1 x~
k+1=k
using the convergence analysis performed in the linear case when T 0 1 T 01
+ ek+1 Rk+1 Hk+1 Pk+1 Hk+1 Rk+1 ek+1 (25)
ek+1 and x~k+1=k are approximated as
ek+1  Hk+1 x~k+1=k
and substituting (23) into (25)
(13)
Vk+1 = Vk+1=k + x~Tk+1=k HkT+1 Rk0+1
1 Hk+1 x~
k+1=k
0 x~k+1=k Hk+1 Rk+1 ek+1 + ek+1 Rk0+1
0
and
T T 1 T 1 Hk+1 x~
k+1=k
x~k+1=k  Fk x~k : (14) T 0 1 T 01
+ ek+1 Rk+1 Hk+1 Pk+1 Hk+1 Rk+1 ek+1 (26)
However, this approximation is available only if x ^k+1=k and x ^k
belong to a neighborhood of xk+1 and xk , respectively, otherwise with
the EKF diverges.
Vk+1=k = x~Tk+1=k Pk0+1
1 x~
=k k+1=k :
For a rigorous convergence study we have to show that fVk gk=1111
(27)
decreases without any approximation. We notice that there always From (17) and (18), (26) becomes
exist residues, due to the first-order linearization technique, of each
output error prediction component eik+1 (i = 1; 1 1 1 ; p) of ek+1 Vk+1 = Vk+1=k + ekT+1 (k+1 Rk0+1
1 k+1
and each state error prediction component x ~jk+1=k (j = 1; 1 1 1 ; n) 0 k+1 R0k+1
1 0 R01 k+1
k+1
of x~k+1=k ; for all k: To take these residues into account, in order 01 T 01
+ Rk+1 Hk+1 Pk+1 Hk+1 Rk+1 )ek+1 : (28)
to obtain an exact equality, we introduce here unknown diagonal
matrices k+1 and k so that On the other hand, Vk+1=k may be written as
Hik+1 x~k+1=k = ik+1` eik+1 (15)
Vk+1=k = x~Tk FkT k (Fk Pk FkT )01 k Fk x~k : (29)
x~jk+1=k = jk Fjk x~k : (16)
fVk gk=1111 means that
A decreasing sequence
Hik+1 and Fjk are the ith and j th rows of Hk+1 and Fk ,
respectively. Vk+1 0 Vk = Vk+1 0 Vk+1=k + Vk+1=k 0 Vk  0 (30)
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 42, NO. 4, APRIL 1997 583

or equivalently As Rk0+1
1 and R01 Hk+1 Pk+1 H T R01 are symmetric matrices
k+1 p 0 k+1; k+1p 0
Vk+1 0 Vk = eTk+1 (k+1 Rk0+1
1 k+1 and as the interval 0 ]1 1 1 1 + 1 1 [ ]0 2[
k+1 k+1  ; ; this
2 0
implies that 2ik+1 0 ik+1 < ; and (40) yields to
0 k+1 Rk+1 0 Rk0+1
0 1 1 k+1
max ((ik+1 0 2ik+1 )Rk+1 + Rk0+1
2 0 1 1 Hk+1 Pk+1 H T R01 )
k+1 k+1
+ Rk0+11 Hk+1 Pk+1 HkT+1 Rk0+11 )ek+1 2 01
 0(ik+1 0 2ik+1 )max (Rk+1 )
+ x~Tk (FkT k (Fk Pk FkT )01 k Fk + max(Rk0+11 Hk+1 Pk+1 HkT+1 Rk0+11 ) (41)
0 Pk01 )~xk  0: with
A sufficient condition to ensure that is
Rk0+1
1 Hk+1 Pk+1 H T R01
k+1 k+1
k+1 R01 01 01
k+1 k+1 0 k+1 Rk+1 0 Rk+1 k+1 = Rk0+11 Hk+1 Pk+1=k HkT+1(Hk+1 Pk+1=k HkT+1 Rk+1 )01 :
+ Rk0+11 Hk+1 Pk+1 HkT+1 Rk0+11  0 (31) (42)
and Therefore, under (33) and by the use of (41) and (42), it follows
FkT k (
Fk Pk FkT )01 k Fk 0 P 01  0:
k (32)
that (31) is satisfied.
Lemma 2: If we assume that
Before we give sufficient conditions to ensure convergence of the Fk is a bounded nonsingular matrix (43)
EKF, two lemmas are established for intermediate results.
Lemma 1: If we assume that each ik+1 satisfies the following and each jk satisfies the following condition:
condition:
01  jk  1 for j = 1; 1 1 1 ; n (44)
1 0 1 0 1k+1 < ik+1 < 1 + 1 0 1k+1 then (32) is verified.
for i = 1; 1 1 1 ; p (33) Proof: As k is a diagonal matrix, its eigenvalues are given by
with jk and verify
k+1 = max (Rk+1 )max (Rk0+1
1 Hk+1 P T
k+1=k Hk+1 k mj = jk mj (45)
1 (Hk+1 Pk+1=k HkT+1 + Rk+1 )01 ) (34) and
()
where max 1 represents the maximum eigenvalue and Rk+1 is mjT k = jk mTj for j = 1; 1 1 1 ; n (46)
1 1
chosen such that k+1  ; then (31) is verified.
where mj is the associated eigenvector.
Proof: As k+1 is a diagonal matrix, its eigenvalues are given
by ik+1 and verify Under assumption (43), (32) is equivalent to

k+1 si = ik+1 si (35)

k Fk0T Pk01 Fk01 k 0 Fk0T Pk01 Fk01  0: (47)
Pre- and post-multiplying the left side of (47) by mjT and mj ,
and
respectively
siT k+1 = ik+1 sTi for i = 1; 1 1 1 ; p (36)
mjT (k Fk0T Pk01 Fk01 k 0 Fk0T Pk01 Fk01 )mj  0: (48)
where si is the associated eigenvector. Using (45) and (46) in (48) yields
Pre- and post-multiplying the left side of (31) by siT and si , 2 F 0T P 01 F 01 0 F 0T P 01 F 01  0
respectively jk k k k k k k (49)

siT (k+1 Rk0+1

1 k+1 0 k+1 R01 0 R01 k+1
k+1 k+1
thus under assumption (44), it is easy to show that (32) is also verified.
+ Rk0+11 Hk+1 Pk+1 HkT+1 Rk0+11 )si  0 (37)
Unfortunately, the convergence of the EKF is not ensured even if
fVk gk=1111 is a decreasing sequence. So, some additional conditions
and using relations (35) and (36) in (37) yields to in relation to the reconstructibility are needed. For nonlinear systems,
2 R01 0 2ik+1 R01
siT (ik
the local reconstructibility may be defined in the same way as in the
+1 k+1 k+1 linear case [19]. Let us recall this property, which will be partly
+ Rk0+11 Hk+1 Pk+1 HkT+1 Rk0+11 )si  0 (38) investigated in our developments. Under (43), if there exist positive
real numbers 1 and 2 so that for all k  M and for some finite
or 0
M  we have
2 01 01
ik+1 Rk+1 0 2ik+1 Rk+1 1 In  OeT (k 0 M; k)<(k 0 M; k)Oe (k 0 M; k)  2 In (50)
+ Rk0+11 Hk+1 Pk+1 HkT+1 Rk0+11  0: (39) with
By using the measure of matrix properties [17], corresponding to Hk0M Fk001M Fk001M +1 1 1 1 Fk0011
norm 2, the left side of (39) can be bounded as Hk0M +1 Fk0M +1 1 1 1 Fk01
Oe (k 0 M; k) = 1
((2ik+1 0 2ik+1 )Rk0+1
1 + R01 Hk+1 Pk+1 H T R01 ) (51)
k+1 k+1 k+1 1
 ((2ik+1 0 2ik+1 )Rk0+1
1) Hk
+ (Rk0+11 Hk+1 Pk+1 HkT+1 Rk0+11 ) (40) <(k 0 M; k) =Diag(Rk001M ; 1 1 1 ; Rk01) (52)

where (1) is the measure of matrix defined by where Fk and Hk are defined by (8) and (9), respectively, then the

A + AT :
^ ^
system (and its associated EKF for xi=i01 and xi sufficiently close
(A) =  max to the true state xi ) is said to be reconstructible. Thus, we obtain the
2 following lemma.
584 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 42, NO. 4, APRIL 1997

Lemma 3: If we assume that (1a), (1b) is reconstructible (50), Some Concluding Remarks
then we have ik and jk are unknown factors introduced to evaluate the lin-
lim
k!1
min (P 01 ) = 1
k (53)
earity of the model and, consequently, to control the gain matrix
Kk+1 by an adequate choice of Rk in order to ensure stability
= ~
of the algorithm, particularly when ek+1 6 Hk+1=k xk+1=k and
and
~ = ~
xk+1=k 6 Fk xk : Indeed, the sufficient conditions (33) and (44)
max (Pk01 ) mean that fVk g is a decreasing sequence for all approximations
Sup klim
!1  (P 01 ) < 1: (54)
min k
in the form

Proof: From (23) and under (43) it is easy to show, by induction, ik+1 eik+1 = Hik+1 x~k+1=k and x~jk+1=k = jk Fjk x~k
that with
P 01
k+1 = OeT (1; k + 1)<(1; k + 1)Oe (1; k + 1) + 9(0; k) (55) ik+1 2 ]1 0 1 0 1k+1 ; 1 + 1 0 1k+1 [
and jk 2 [01; +1]:
with
As ik+1 and jk are unknown
p factors, Rkp+1 have to be chosen
9(0; k) = Fk0T Fk00T1 1 1 1 F00T P001 F001 1 1 1 Fk0011 Fk01: (56) so that the interval ]1 0 1 0 1k+1 ; 1 + 1 0 1k+1 [ is large
enough to fulfil (33). An a priori choice of Rk+1 is to set it
Oe (1; k +1) and <(1; k +1) are defined in (51) and (52), respectively. much higher than Hk+1 Pk+1=k HkT+1 : Notice that within the
On a horizon time kM; if the reconstructibility Gramian
OeT (1; kM )<(1; kM )Oe (1; kM ) is decomposed into k block
maximum limits we have

matrices of horizon M; we obtain ]1 0 1 0 1k+1 ; 1 + 1 0 1k+1 [!]0; 2[:

k
01
PkM =
[OeT ((i 0 1)M + 1; iM )<((i 0 1)M However, setting high values of Rk+1 leads to a very slow
i=1 convergence rate (the gain matrix Kk+1 goes to zero). A tradeoff
+ 1; iM )Oe((i 0 1)M + 1; iM )] + (0; kM 0 1): (57) between stability and rate of convergence of the proposed
algorithm leads us to set (in our numerical simulations)
01 0 9(0; kM 0 1) is the sum of k reconstructibility
Since PkM
Gramians, then under (50) we obtain the following inequalities:
Rk+1 = Hk+1 Pk+1=k HkT+1 + Ip where  > 0 and
01 0 9(0; kM 0 1))  k2 :  > 0 are fixed by the user:
o < k1  (PkM (58)
For MISO nonlinear systems, Rk is a positive scalar, and then
01 0 9(0; kM 0 1)) is bounded by k1 and k2 , it is
Thus, as (PkM (33) becomes
easy to show that (53) and (54) follow from (58), where  represents
the eigenvalue symbol of PkM 01 0 9(0; kM 0 1): 1k+1 = Hk+1 Pk+1=k HkT+1 (Hk+1 Pk+1=k HkT+1 + Rk+1 )01
Now, we propose a simple method to prove local convergence of with 1 0 1k+1 > 0 for all k:
the EKF applied to deterministic nonlinear systems. For linear time-varying systems we have k = 1 and k = In :
Theorem: Suppose that (33), (44), and (50) hold, then the EKF Then (31) and (32) become
(2)(6), when used as an observer for the nonlinear discrete-time 01 + Hk+1 Pk+1=k HkT+1 (Hk+1 Pk+1=k HkT+1 + Rk+1 )01  0
system (1a)(1b), ensures that
and
lim (xk 0 x^k ) = 0:
k!1 FkT (Fk Pk FkT )01 Fk 0 Pk01  0:
Proof: Under (33) and (44), it has been shown (according to
Lemmas 1 and 2) that fVk gk=1111 is a decreasing sequence which For Rk > 0; fVk g is a decreasing sequence.
converges to a positive scalar V , i.e.,

lim
k!1
Vk = V: IV. NUMERICAL EXAMPLES
In order to show the efficiency of the proposed approach, we
On the other hand, we have consider two numerical examples.
01
[Pk ]~xk x~k  0:
Example 1: The first example concerns the identification prob-
 min
T
Vk lem of nonlinear time-invariant systems described by the MISO
tr(Pk01) n [P 01 ]
max k
(59)
Hammerstein model. This kind of model is composed by a static
nonlinearity followed by a linear dynamic system. Here we consider
According to (53) one obtains two interconnected subsystems (high order and high values of gik )
lim tr(Pk01) = 1
k!1
(60) with the following pulse transfer functions:
V1k = g11 u1k + g12 u12k + g13 u13k + g14 u14k + g15 u15k
then
V2k = g21 u2k + g22 u22k + g23 u23k
min [Pk01 ]~xTk x~k + g24 u24k + g25 u25k + g26 u26k
lim
k!1 n [P 01] = 0 (61)
max k B1 = q01 + b11 q02
thus (54) yields to A1 1 + a11 q01 + a12 q02
B2 = q01 + b21 q02 + b22 q03
lim x~k = 0:
k!1
(62)
A2 1 + a21 q01 + a22 q02
IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 42, NO. 4, APRIL 1997 585

where q 01 is the delay operator and uik is the ith input of the system
at time instant k; i = 1; 2; with
a11 = 0:4; a12 = :65; a21 = 0:75; a22 = 0:9
b11 = 0:5; b21 = 00:6; b22 = 0:7
g11 = 5:2; g12 = 02:0; g13 = 5:2; g14 = 03:5
g12 = 6:5; g21 = 6:3; g22 = 2:8; g23 = 00:02
g24 = 3:1; g25 = 02:3; g26 = 5:6:
Parameters of the static nonlinearity V1 and V2 are independent of
those of A1 ; A2 ; B1 ; and B2 :
The invariant parameter vector x (i.e., xk+1 = xk ) to be estimated
from the input output data (yk ; u1k ; u2k )k=1;111 ; is defined as
x = (a11 a12 a21 a22 b11 b21 b22 g11
k 0 x kExample 1.
Fig. 1. Rate of convergence of x
^k
1 1 1 g15 1 1 1 g21 1 1 1 g26 )T 2 R18 :
k

A nonlinear state-space representation of the inputoutput Ham-

merstein model may be written as
xk+1 = f (xk ; u1k ; u2k ) = xk
yk = h(xk ; u1k ; u2k )
= 0(a11 + a21 )yk01 0 (a11 a21 + a22 + a12 )yk02

0 (a11 a22 + a21 a12 )yk03 0 a12 a22 yk04

+ V1k01 + (b11 + a21 )V1k02

+ (b11 a21 + a22 )V1k03

+ b11 a22 V1k04 + V2k01 + (b21 + a11 )V2k02

+ (b21 a11 + a12 + b22 )V2k03

+ (a11 b22 + b21 a12 )V2k04 + a12 b22 V2k05 : k 0 x kExample 2.

Fig. 2. Rate of convergence of x
^k k

In order to fulfil (33) and (44) with a good convergence rate, we

take Figs. 1 and 2 show the rate of convergence of the state error norm
kx^ 0 x k with respect to samples k when R
k k k is adequately chosen
Rk+1 = 2Hk+1 Pk+1=k H +1 + 1:
T
k for both examples, while the classical EKF diverges for Rk = 1: We
Owing to a lack of space here, we consider a worst case of very notice that in spite of bad initialization and with a large scale system
bad initialization. x
^0 = 100, i.e., all parameters are initialized at (example 1), we obtain excellent results with our approach: the actual
100 with P0 = 107I 18 : The input signals (u1k ) and (u2k ) are zero values of parameters are reached approximately at 800 samples for
mean white noise sequences with standard deviations 1 = 0:3 and the first example and at 80 samples for the second one.
2 = 0:4, respectively. As we expect, the reconstructibility condition for nonlinear systems
Example 2: The second numerical example, which was worked in depends closely on the input signals especially for identification of
[18], consists of a combined parameter and state estimation of the nonlinear systems. We notice that in the case of parameter estimation,
following discrete-time system: reconstructibility of the system is equivalent to the persistently
exciting condition since xi+1 = xi (for time-invariant systems where
x1k+1 x2k
xi represents the parameters vector to be estimated), and therefore
x2k+1 0a0 x1k 0 a1 x2k + buk we have Fi = Fi01 = I; I is the identity matrix, for all i, and
x3k+1 = x3k
x4k+1 x4k Hk0M Fk001M Fk001M +1 1 1 1 Fk0011
x5k+1 x5k Hk0M +1 Fk0M +1 1 1 1 Fk0011
yk = x1k x2k with Oe (k 0 M; k) = 1
a0 = 0:3 + 0:1 sin(x3k ) 1
Hk
a1 = 1:1 + 0:1 sin(x4 k) Hk0M
b = 2:4 + 0:1 sin(x5k ) Hk0M +1
and = 1 :
uk = 5 + 2 sin(0:8k ) + 2 sin(1:8k ):
1
Hk
The initial conditions are
x10 = 4; x20 = 5; x30 = 0; x40 = 0; x50 = 0 V. CONCLUSION
x^10 = 20; x^20 = 20; x^30 = 1; x^40 = 1; x^50 = 1 In this paper, convergence analysis of the EKF used as an observer
for nonlinear deterministic discrete-time systems was considered.
with It is shown, from the theoretical point of view, that under mild
Rk+1 = 3Hk+1 Pk+1=k HkT+1 + 1 and P0 = 1020I 5 conditions and with an appropriate choice of the arbitrary matrix Rk ;
586 IEEE TRANSACTIONS ON AUTOMATIC CONTROL, VOL. 42, NO. 4, APRIL 1997

convergence of the EKF may be improved significantly in the sense Dynamics and Convergence Rate of Ordinal Comparison
that the domain of attraction is enlarged. One of the main results in of Stochastic Discrete-Event Systems
this paper consists of introducing instrumental matrices k and k to
evaluate the linearity of the model in order to control both stability Xiaolan Xie
and convergence of the EKF.
AbstractThis paper addresses ordinal comparison in the simulation
ACKNOWLEDGMENT of discrete-event systems. It examines dynamic behaviors of ordinal
comparison in a fairly general framework. It proves that for regenerative
systems, the probability of obtaining a desired solution using ordinal
The authors wish to thank the anonymous referees for their comparison approaches converges at exponential rate, while the variances
insightful comments. of the performance measures converge at best at rate O(1=t2 ); where t
is the simulation time. Heuristic arguments are provided to explain that
exponential convergence holds for general systems.
REFERENCES
I. INTRODUCTION
[1] J. S. Baras, A. Bensoussan, and M. R. James, Dynamic observers as
asymptotic limits of recursive filters: Special cases, Siam J. Appl. Math., Optimization in discrete solution space becomes more and more
vol. 48, no. 5, pp. 11471158, 1988. important for discrete-event dynamic systems. The only general tool
[2] D. Bestle and M. Zeitz, Canonical form observer design for non linear
for evaluating such systems is the simulation. A straightforward and
time-variable systems, Int. J. Contr., vol. 38, pp. 419431, 1983.
[3] M. Boutayeb and M. Darouach, Recursive identification method for widely used approach consists of simulating all candidate designs to
Hammerstein modelExtension to the nonlinear MISO case, Contr. obtain accurate estimation of the performance measures and selecting
Theory Advanced Technol., vol. 10, no. 1, pp. 5772, 1994. the best design. Its main drawback is the requirement of a long
[4] , Recursive identification method for MISO Wiener-Hammerstein simulation run to obtain accurate performance estimators. Variances
of performance measures converge typically at rate O(1=t) in time
model, IEEE Trans. Automat. Contr., vol. 40, no. 2, pp. 287291, 1995.
[5] J. J. Deyst and C. F. Price, Conditions for asymptotic stability of
the discrete minimum-variance linear estimator, IEEE Trans. Automat. t. and these rates are usually unsatisfactory when the number of
Contr., pp. 702705, 1968. candidate designs is important.
[6] A. Gelb, Applied Optimal Estimation. Cambridge, MA: MIT Press, Ordinal optimization approaches first proposed in [10] (see also
1974.
[11] for an overview) reduce the computation burden by combining
[7] A. H. Jaswinski, Stochastic Processes and Filtering Theory. New York:
Academic, 1970. some mind-set changes concerning the problem of optimization
[8] A. J. Krener and A. Isidori, Linearization by output injection and of discrete-event systems. The primary concern of the ordinal op-
nonlinear observers, Syst. Contr. Lett., vol. 3, pp. 4752, 1983. timization is the rankings of candidate solutions instead of their
[9] A. J. Krener and W. Respondek, Nonlinear observers with linearizable criterion values. Simulations conducted by various authors for a wide
error dynamics, Siam J. Contr. Optim., vol. 23, pp. 197216, 1985.
[10] H. J. Kushner, Approximations to optimal nonlinear filters, IEEE range of problems have shown that the rankings stabilize before the
Trans. Automat. Contr., vol. AC-12, no. 5, pp. 546556, 1967. convergence of performance estimates. To achieve further reduction
[11] L. Ljung, Asymptotic behavior of the extended Kalman filter as a of simulation time, ordinal optimization approaches typically relax
parameter estimator for linear systems, IEEE Trans. Automat. Contr., the goal of optimization to the isolation of a set of good candi-
AC-24, pp. 3650, 1979.
date solutions. Experiments indicate that it is possible to determine
[12] T. P. McGarty, Stochastic Systems and State Estimation. New York:
Wiley, 1973. whether a solution is good or bad very early in the simulation with
[13] R. K. Mehra, A comparison of several nonlinear filters for reentry ve- high probability. Recent research [2], [3], [12] has demonstrated that
hicle tracking, IEEE Trans. Automat. Contr., vol. AC-16, pp. 307319, impressive improvement in computation efficiency can be achieved
1971. using ordinal optimization approaches.
[14] H. Nijmeijer, Observability of autonomous discrete-time nonlinear
systems: A geometric approach, Int. J. Contr., vol. 36, pp. 867874, The purpose of this paper is to provide theoretical evidence of the
1982. efficiency of ordinal optimization approaches. It is an extension of a
[15] Y. Song and J. W. Grizzle, The extended Kalman filter as a local recent work [4] which considers the convergence of the probability
asymptotic observer for nonlinear discrete-time systems, in Proc. Amer. that the best observed design is indeed a good design. We consider
Contr. Conf., 1992, pp. 33653369.
the following fundamental indicator: the probability that at least k of
[16] Special issue on applications of Kalman filtering, IEEE Trans. Automat.
Contr., vol. AC-28, no. 3, 1983. the observed top-s designs are the actual top-g designs (i.e., satis-
[17] M. Vidyasagar, Nonlinear Systems Analysis, 2nd ed. Englewood Cliffs, factory designs). It is called alignment probability and is meaningful
NJ: Prentice-Hall, 1993. in the perspective of simulation budget allocation. Our contributions
[18] G. Ciccarella, M. Dalla Mora, and A. Germani, A robust observer for include:
discrete time nonlinear systems, Syst. Contr. Lett., vol. 24, pp. 291300,
1995. 1) monotonicity properties of the alignment probability with re-
[19] P. E. Moraal and J. W. Grizzle, Observer design for nonlinear systems spect to s; g; and k are established. They show that goal
with discrete-time measurements, IEEE Trans. Automat. Contr., vol. relaxation improves the computation efficiency;
40, no. 3, 1995.
2) the association, a kind of positive correlation, of simulated
systems improves the convergence rate of the probability that
the observed best design is the actual best one;
3) informal arguments of the exponential convergence rate of the
alignment probability in the general case;
Manuscript received July 14, 1995; revised June 12, 1996.
The author is with INRIA, Technopole Metz 2000, 57070 Metz, France.
Publisher Item Identifier S 0018-9286(97)02044-8.

00189286/97$10.00 1997 IEEE