# Iterative and Algebraic Algorithms for the Computation of the Steady State Kalman Filter Gain

Authors: Nicholas Assimakis; Maria Adam
Journal: ISRN Applied Mathematics
 (2014)

---

## Abstract

The Kalman filter gain arises in linear estimation and is associated with linear systems. The gain is a matrix through which the estimation and the prediction of the state as well as the corresponding estimation and prediction error covariance matrices are computed. For time invariant and asymptotically stable systems, there exists a steady state value of the Kalman filter gain. The steady state Kalman filter gain is usually derived via the steady state prediction error covariance by first solving the corresponding Riccati equation. In this paper, we present iterative per-step and doubling algorithms as well as an algebraic algorithm for the steady state Kalman filter gain computation. These algorithms hold under conditions concerning the system parameters. The advantage of these algorithms is the autonomous computation of the steady state Kalman filter gain.


---

## Body

## 1. Introduction

The Kalman filter gain arises in Kalman filter equations in linear estimation and is associated with linear systems. State space systems have been widely used in estimation theory to describe discrete time systems [1–5]. It is known [1] for time invariant systems that if the signal process model is asymptotically stable, then there exists a steady state value of the Kalman filter gain. Thus, the steady state gain is associated with time invariant systems described by the following state space equations:
(1)
x
k
+
1
=
F
x
k
+
w
k
,
z
k
=
H
x
k
+
v
k
,
for k
≥
0, where x
k is the n-dimensional state vector at time k, z
k is the m-dimensional measurement vector at time k, F is the n
×
n system transition matrix, H is the m
×
n output matrix, w
k is the plant noise at time k, and v
k is the measurement noise at time k. Also, {
w
k
} and {
v
k
} are Gaussian zero-mean white random processes with covariance matrices Q and R, respectively.The discrete time Kalman filter [1, 6] is the most well-known algorithm that solves the filtering problem. In fact, Kalman filter faces simultaneously two problems as follows.(i)
Estimation: the aim is to recover at time k information about the state vector at time k using measurements up till time k.
(ii)
Prediction: the aim is to obtain at time k information about the state vector at time k
+
1 using measurements up till time k; it is clear that prediction is related to the forecasting side of information processing.Kalman filter uses the measurements up till time k in order to produce the (one step) prediction of the state vector and the corresponding prediction error covariance matrix P
k
+
1
/
k, as well as producing the estimation of the state vector and the corresponding estimation error covariance matrix P
k
/
k. The Kalman filter equations needed for the computation of the prediction and estimation error covariance matrices are as follows:
(2)
K
k
=
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
,
(3)
P
k
/
k
=
(
I
-
K
k
H
)
P
k
/
k
-
1
,
(4)
P
k
+
1
/
k
=
Q
+
F
P
k
/
k
F
T
,
for k
≥
0, with initial condition P
0
/
-
1
=
P
0 for the time instant, where there are no measurements given. Note that K
k is theKalman filter gain.From (2) to (4), we are able to derive theRiccati equation, which is an iterative equation with respect to the prediction error covariance:
(5)
P
k
+
1
/
k
=
Q
+
F
P
k
/
k
-
1
F
T
-
F
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
F
T
.In the general case, whereR and P
0 are positive definite matrices, using in (5) the matrix inversion lemma:
(6)
[
A
+
B
C
D
]
-
1
=
A
-
1
-
A
-
1
B
[
C
-
1
+
D
A
-
1
B
]
-
1
D
A
-
1
,
the Riccati equation is formulated as
(7)
P
k
+
1
/
k
=
Q
+
F
[
P
k
/
k
-
1
-
1
+
H
T
R
-
1
H
]
-
1
F
T
.The Riccati equation is a nonlinear iterative equation with respect to the prediction error covariance. For time invariant systems, it is well known [1] that if the signal process model is asymptotically stable, then there exists a steady state value P
~
p of the prediction error covariance matrix. In fact, the prediction error covariance tends to the steady state prediction error covariance.The steady state prediction error covariance satisfies thesteady state Riccati equation
(8)
P
~
p
=
Q
+
F
[
P
~
p
-
1
+
H
T
R
-
1
H
]
-
1
F
T
.Then, from (2), it is clear that there also exists a steady state value K
~ of the Kalman filter gain [7]. The steady state gain can be calculated by
(9)
K
~
=
P
~
p
H
T
[
H
P
~
p
H
T
+
R
]
-
1
.Also, from (3), it is clear that there also exists a steady state value P
~
e of the estimation error covariance matrix [7], which can be calculated by
(10)
P
~
e
=
P
~
p
-
P
~
p
H
T
[
H
P
~
p
H
T
+
R
]
-
1
H
P
~
p
=
[
P
~
p
-
1
+
H
T
R
-
1
H
]
-
1
.It is obvious from (9) that the steady state Kalman filter gain can be derived via the steady state prediction error covariance. The covariance matrix in Kalman filter plays an important role in many applications [1, 4, 6, 8–10]. The steady state prediction error covariance can be derived by solving the Riccati equation emanating from Kalman filter. The discrete time Riccati equation has attracted recent attention. In view of the importance of the Riccati equation, there exists considerable literature on its algebraic solutions; for example, in [1, 7, 11, 12], the authors have derived an eigenvector solution, while the author of [13] has included solving scalar polynomials. Other methods are based on the iterative solutions [1, 13–18] concerning per-step or doubling algorithms. The iterative algorithms that provide the steady state Kalman filter gain together with the prediction error covariance are the Chandrasekhar algorithms [1], as well as the iterative algorithm that calculate the Kalman gain only once for a period of the stationary channel, as opposed to each data sample in the conventional filter [19]. A geometric illustration of the Kalman filter gain is given in [20].In this paper, we present algorithms for the steady state Kalman filter gain autonomous computation. These algorithms hold under conditions concerning the system parameters. The paper is organized as follows: two new per-step iterative algorithms, a new doubling iterative algorithm, and an algebraic algorithm for the computation of the steady state Kalman filter gain are presented in Section2. In Section 3, two examples verify the results. Finally, Section 4 summarizes the conclusions.


## 2. New Algorithms for the Steady State Kalman Filter Computation

### 2.1. Assumptions

We assume the general case, whereR and P
0 are positive definite matrices.The Kalman filter gainK
k is a matrix of dimension n
×
m.We define the matrix(11)
G
k
=
K
k
H
.
It is clear that G
k is a nonsymmetric matrix of dimension n
×
n.It is also clear that there exists a steady state value(12)
G
~
=
K
~
H
.Also, we define the matrix(13)
S
=
H
T
R
-
1
H
.
Note that S is an n
×
n symmetric positive semidefinite matrix and S is a positive definite if rank
⁡
(
H
)
=
n; this means that S is a nonsingular matrix in the case, rank
⁡
(
H
)
=
n with m
≥
n, [21].


### 2.2. Indirect Steady State Kalman Filter Gain Computation

In this section, we present algorithms forG
~ computation. Then, we show how to compute the steady state Kalman filter K
~ through G
~
=
K
~
H.


#### 2.2.1. Iterative Algorithms forG
~ Computation

In this section, we present two iterative per-step algorithms and an iterative doubling algorithm forG
~ computation.Per-Step Iterative Algorithm
1. Using (2) and (11), it is derived that
(14)
G
k
=
K
k
H
=
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
=
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
R
R
-
1
H
=
P
k
/
k
-
1
H
T
(
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
×
[
H
P
k
/
k
-
1
H
T
+
R
-
H
P
k
/
k
-
1
H
T
]
)
R
-
1
H
=
P
k
/
k
-
1
H
T
(
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
[
H
P
k
/
k
-
1
H
T
+
R
]
-
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
)
R
-
1
H
=
P
k
/
k
-
1
H
T
(
I
-
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
)
R
-
1
H
=
P
k
/
k
-
1
H
T
R
-
1
H
-
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
R
-
1
H
=
(
P
k
/
k
-
1
-
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
)
×
H
T
R
-
1
H
=
[
P
k
/
k
-
1
-
1
+
H
T
R
-
1
H
]
-
1
H
T
R
-
1
H
=
[
P
k
/
k
-
1
-
1
+
S
]
-
1
S
.Thus, arises(15)
K
k
H
=
[
P
k
/
k
-
1
-
1
+
S
]
-
1
S
.Using the Riccati equation (7), (15), the nonsingularity of S, and some algebra we have
(16)
P
k
+
1
/
k
=
Q
+
F
[
P
k
/
k
-
1
-
1
+
H
T
R
-
1
H
]
-
1
F
T
=
Q
+
F
[
P
k
/
k
-
1
-
1
+
S
]
-
1
F
T
=
Q
+
F
K
k
H
S
-
1
F
T
⟹
P
k
+
1
/
k
S
=
Q
S
+
F
K
k
H
S
-
1
F
T
S
=
Q
F
-
T
S
[
S
-
1
F
-
T
S
]
-
1
+
F
K
k
H
[
S
-
1
F
-
T
S
]
-
1
⟹
P
k
+
1
/
k
S
(
S
-
1
F
-
T
S
)
=
Q
F
-
T
S
+
F
K
k
H
⟹
S
-
1
F
-
T
S
=
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
⟹
K
k
+
1
H
(
S
-
1
F
-
T
S
)
=
K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
.Also, from (2) and (13), we can write
(17)
K
k
(
H
P
k
/
k
-
1
H
T
+
R
)
=
P
k
/
k
-
1
H
T
⟹
K
k
H
P
k
/
k
-
1
H
T
+
K
k
R
=
P
k
/
k
-
1
H
T
⟹
K
k
R
=
P
k
/
k
-
1
H
T
-
K
k
H
P
k
/
k
-
1
H
T
⟹
K
k
R
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
⟹
K
k
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
R
-
1
⟹
K
k
H
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
R
-
1
H
⟹
K
k
H
=
(
I
-
K
k
H
)
P
k
/
k
-
1
S
.Since the matricesP
k
/
k
-
1
,
S are nonsingular, the last equation yields
(18)
K
k
H
S
-
1
P
k
/
k
-
1
-
1
=
I
-
K
k
H
.Substituting in (16) the matrix K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1 by (18), it follows
(19)
K
k
+
1
H
(
S
-
1
F
-
T
S
)
=
K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
=
(
I
-
K
k
+
1
H
)
(
Q
F
-
T
S
+
F
K
k
H
)
=
Q
F
-
T
S
+
F
K
k
H
-
K
k
+
1
H
Q
F
-
T
S
-
K
k
+
1
H
F
K
k
H
,
whereby it is implied that
(20)
K
k
+
1
H
(
S
-
1
F
-
T
S
)
+
K
k
+
1
H
Q
F
-
T
S
+
K
k
+
1
H
F
K
k
H
=
Q
F
-
T
S
+
F
K
k
H
⟹
K
k
+
1
H
(
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
)
=
Q
F
-
T
S
+
F
K
k
H
⟹
K
k
+
1
H
=
(
Q
F
-
T
S
+
F
K
k
H
)
×
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
]
-
1
.Thus, the above equation can be written as(21)
K
k
+
1
H
=
(
Q
F
-
T
S
+
F
K
k
H
)
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
]
-
1
.Combining (21) with (11), the following nonlinear iterative equation with respect to G
k is derived:
(22)
G
k
+
1
=
(
(
Q
F
-
T
S
)
+
(
F
)
G
k
)
×
[
(
S
-
1
F
-
T
S
+
Q
F
-
T
S
)
+
(
F
)
G
k
]
-
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
,
where
(23)
A
=
(
Q
+
S
-
1
)
F
-
T
S
,
B
=
F
,
C
=
Q
F
-
T
S
,
D
=
F
.The algorithm uses the initial conditionG
0
=
K
0
H
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1
H. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0 and so we are to use the initial condition G
0
=
0.It is clear thatG
k tends to a steady state value G
~ and by (22) G
~ satisfies
(24)
G
~
=
(
C
+
D
G
~
)
[
A
+
B
G
~
]
-
1
.Per-Step Iterative Algorithm
2. We rewrite (22) as
(25)
G
k
+
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
=
(
C
A
-
1
A
+
(
D
+
C
A
-
1
B
-
C
A
-
1
B
)
G
k
)
[
A
+
B
G
k
]
-
1
=
(
C
A
-
1
(
A
+
B
G
k
)
+
(
D
-
C
A
-
1
B
)
G
k
)
[
A
+
B
G
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
G
k
[
A
+
B
G
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
A
G
k
-
1
+
B
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
G
k
-
1
+
A
-
1
B
]
-
1
A
-
1
.
Thus, the following nonlinear iterative equation with respect to G
k is derived:
(26)
G
k
+
1
=
c
+
a
[
G
k
-
1
+
b
]
-
1
d
,
where
(27)
a
=
D
-
C
A
-
1
B
=
F
-
Q
[
Q
+
S
-
1
]
-
1
F
,
b
=
A
-
1
B
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
,
c
=
C
A
-
1
=
Q
[
Q
+
S
-
1
]
-
1
,
d
=
A
-
1
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
.
The algorithm uses the initial condition G
0
=
K
0
H
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1
H. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0. In this case, in order to avoid G
0
-
1, we are to use the initial condition G
1
=
c.It is clear thatG
k tends to a steady state value G
~ and by (26) G
~ satisfies
(28)
G
~
=
c
+
a
[
G
~
-
1
+
b
]
-
1
d
.Doubling Iterative Algorithm. Ιn (22), setting
(29)
G
k
=
K
k
H
=
Y
k
X
k
-
1
,
we take
(30)
Y
k
+
1
X
k
+
1
-
1
=
(
C
+
D
Y
k
X
k
-
1
)
[
A
+
B
Y
k
X
k
-
1
]
-
1
=
(
C
X
k
+
D
Y
k
)
[
A
X
k
+
B
Y
k
]
-
1
or
(31)
[
X
k
+
1
Y
k
+
1
]
=
Φ
[
X
k
Y
k
]
,
where
(32)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
is a matrix of dimension 2
n
×
2
n and A, B, C, D as in (23).We are able to use zero initial conditionP
0
=
0, so G
0
=
K
0
H
=
Y
0
X
0
-
1
=
0; that is,
(33)
[
X
0
Y
0
]
=
[
I
0
]
,
and hence
(34)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
.We define(35)
Φ
2
k
=
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
with initial condition
(36)
Φ
2
0
=
[
d
0
-
1
d
0
-
1
b
0
c
0
d
0
-
1
c
0
d
0
-
1
b
0
+
a
0
]
=
Φ
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
.Then,(37)
[
X
(
2
k
)
Y
(
2
k
)
]
=
Φ
2
k
[
I
0
]
,
and, using the doubling principle [1] Φ
2
k
+
1
=
Φ
2
k
Φ
2
k, we have
(38)
[
d
k
+
1
-
1
d
k
+
1
-
1
b
k
+
1
c
k
+
1
d
k
+
1
-
1
c
k
+
1
d
k
+
1
-
1
b
k
+
1
+
a
k
+
1
]
=
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
.Then we are able to derive, after some algebra, the following nonlinear iterative equations:(39)
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
,
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
,
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
,
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
,
with initial conditions
(40)
a
1
=
D
-
C
A
-
1
B
=
F
-
Q
[
Q
+
S
-
1
]
-
1
F
,
b
1
=
A
-
1
B
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
,
c
1
=
C
A
-
1
=
Q
[
Q
+
S
-
1
]
-
1
,
d
1
=
A
-
1
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
.Then, since(41)
[
X
(
2
k
)
Y
(
2
k
)
]
=
Φ
2
k
[
I
0
]
=
[
d
k
-
1
c
k
d
k
-
1
]
,
it is clear that c
k
=
Y
2
k
X
2
k
-
1
=
G
2
k tends to a steady state value G
~.


#### 2.2.2. Algebraic Algorithm forG
~ Computation

In this section, we present an algebraic algorithm forG
~ computation. As in (29), setting
(42)
G
k
=
K
k
H
=
Y
k
X
k
-
1
and using the parameters A, B, C, D by (23), we derive
(43)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
,
which is a matrix of dimension 2
n
×
2
n. Since
(44)
det
⁡
⁡
Φ
=
det
⁡
⁡
(
A
)
det
⁡
⁡
(
D
-
C
A
-
1
B
)
=
det
⁡
⁡
(
(
Q
+
S
-
1
)
F
-
T
S
)
×
det
⁡
⁡
(
F
-
Q
F
-
T
S
[
(
Q
+
S
-
1
)
F
-
T
S
]
-
1
F
)
=
det
⁡
⁡
(
Q
+
S
-
1
)
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
S
)
×
det
⁡
⁡
(
F
-
Q
F
-
T
S
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
F
-
Q
[
Q
+
S
-
1
]
-
1
F
)
×
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
Q
+
S
-
1
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
I
-
Q
[
Q
+
S
-
1
]
-
1
)
×
det
⁡
⁡
(
F
)
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
Q
+
S
-
1
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
(
Q
+
S
-
1
)
-
Q
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
S
-
1
)
=
1
,
it is evident that Φ is a nonsingular matrix and its eigenvalues occur in reciprocal pairs.Thus, (43) can be written
(45)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
=
W
L
W
-
1
,
where
(46)
L
=
[
Λ
0
0
Λ
-
1
]
is a diagonal matrix containing the eigenvalues of Φ, with Λ diagonal matrix with all the eigenvalues of Φ lying outside the unit circle, and
(47)
W
=
[
W
11
W
12
W
21
W
22
]
is the matrix containing the corresponding eigenvectors of Φ, with
(48)
V
=
W
-
1
=
[
V
11
V
12
V
21
V
22
]
.We are able to use zero initial conditionP
0
=
0, so G
0
=
K
0
H
=
Y
0
X
0
-
1
=
0; that is,
(49)
[
X
0
Y
0
]
=
[
I
0
]
,
and hence
(50)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
.Then, from (50) and (45)–(48), we are able to write
(51)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
=
[
W
L
W
-
1
]
k
[
I
0
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
k
0
0
Λ
-
k
]
[
V
11
V
12
V
21
V
22
]
[
I
0
]
;that is,(52)
[
X
k
Y
k
]
=
[
W
11
Λ
k
V
11
+
W
12
Λ
-
k
V
21
W
21
Λ
k
V
11
+
W
22
Λ
-
k
V
21
]
.Substituting in (42) the matrices X
k, Y
k from (52), we have that
(53)
G
k
=
Y
k
X
k
-
1
=
(
W
21
Λ
k
V
11
+
W
22
Λ
-
k
V
21
)
×
[
W
11
Λ
k
V
11
+
W
12
Λ
-
k
V
21
]
-
1
.Furthermore, the diagonal matrixΛ
-
1 contains all the eigenvalues of Φ lying inside the unit circle, which follows that lim
⁡
k
→
∞
⁡
Λ
-
k
=
0. Then, G
k tends to a steady state value G
~ with G
~
=
lim
⁡
k
→
∞
⁡
G
k, and from (53) arises
(54)
G
~
=
W
21
W
11
-
1
.


#### 2.2.3. Steady State Kalman Filter Gain Computation

All algorithms presented in Sections2.2.1 and 2.2.2 compute the steady state value G
~. Taking into account the assumptions of Section 2.1, we are able to conclude that, under the condition rank
⁡
(
H
)
=
n, the steady state gain is
(55)
K
~
=
G
~
[
H
T
H
]
-
1
H
T
.


### 2.3. Direct Steady State Kalman Filter Gain Computation

In this section, we present algorithms for the direct computation of the steady state Kalman filterK
~. The proposed algorithms compute directly the steady state Kalman filter gain, that is, without using G
~
=
K
~
H. All these algorithms hold under the assumption that n
=
m. Note that, since rank
⁡
(
H
)
=
n, H and S are nonsingular matrices.


#### 2.3.1. Iterative Algorithms forK
~ Computation

In this section, we present two iterative per-step algorithms and an iterative doubling algorithm forK
~ computation.Per-Step Iterative Algorithm
1. Using (11), (22), and (13), we are able to derive the following nonlinear iterative equation with respect to the Kalman filter gain K
k:
(56)
K
k
+
1
=
G
k
+
1
H
-
1
=
(
Q
F
-
T
S
+
F
G
k
)
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
G
k
]
-
1
H
-
1
=
(
Q
F
-
T
H
T
R
-
1
H
+
F
G
k
)
×
[
H
-
1
R
H
-
T
F
-
T
H
T
R
-
1
H
+
Q
F
-
T
H
T
R
-
1
H
+
F
G
k
]
-
1
H
-
1
=
(
Q
F
-
T
H
T
R
-
1
H
+
F
K
k
H
)
×
[
R
H
-
T
F
-
T
H
T
R
-
1
H
+
H
Q
F
-
T
H
T
R
-
1
H
+
H
F
K
k
H
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
H
[
R
H
-
T
F
-
T
H
T
R
-
1
H
+
H
Q
F
-
T
H
T
R
-
1
H
+
H
F
K
k
H
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
R
H
-
T
F
-
T
H
T
R
-
1
+
H
Q
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
H
Q
F
-
T
H
T
R
-
1
+
R
H
-
T
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
.The nonsingularity ofS and (13) allow us to write the equality in (56) as
(57)
K
k
+
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
H
Q
F
-
T
H
T
R
-
1
+
H
S
-
1
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
,
where
(58)
A
=
H
Q
F
-
T
H
T
R
-
1
+
H
S
-
1
F
-
T
H
T
R
-
1
A
=
H
(
Q
+
S
-
1
)
F
-
T
H
T
R
-
1
,
B
=
H
F
,
C
=
Q
F
-
T
H
T
R
-
1
,
D
=
F
.The initial condition isK
0
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0 and so we are to use the initial condition K
0
=
0.It is clear thatK
k tends to a steady state value K
~ satisfying
(59)
K
~
=
(
C
+
D
K
~
)
[
A
+
B
K
~
]
-
1
.Per-Step Iterative Algorithm
2. Using (57), we are able to derive the following nonlinear iterative equation with respect to the Kalman filter gain K
k:
(60)
K
k
+
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
=
(
C
A
-
1
A
+
(
D
+
C
A
-
1
B
-
C
A
-
1
B
)
K
k
)
[
A
+
B
K
k
]
-
1
=
(
C
A
-
1
(
A
+
B
K
k
)
+
(
D
-
C
A
-
1
B
)
K
k
)
[
A
+
B
K
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
K
k
[
A
+
B
K
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
A
K
k
-
1
+
B
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
K
k
-
1
+
A
-
1
B
]
-
1
A
-
1
=
c
+
a
[
K
k
-
1
+
b
]
-
1
d
,
where A
,
B
,
C
,
D are given by (58) and
(61)
a
=
D
-
C
A
-
1
B
,
b
=
A
-
1
B
,
c
=
C
A
-
1
,
d
=
A
-
1
.The algorithm uses the initial conditionK
0
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0. In this case, in order to avoid K
0
-
1, we are to use the initial condition K
1
=
c.It is clear thatK
k tends to a steady state value K
~ satisfying
(62)
K
~
=
c
+
a
[
K
~
-
1
+
b
]
-
1
d
.Doubling Iterative Algorithm. Ιn (57), setting
(63)
K
k
=
Y
k
X
k
-
1
,
we take
(64)
Y
k
+
1
X
k
+
1
-
1
=
(
C
+
D
Y
k
X
k
-
1
)
[
A
+
B
Y
k
X
k
-
1
]
-
1
=
(
C
X
k
+
D
Y
k
)
[
A
X
k
+
B
Y
k
]
-
1
or
(65)
[
X
k
+
1
Y
k
+
1
]
=
Φ
[
X
k
Y
k
]
,
where
(66)
Φ
=
[
A
B
C
D
]
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
is a matrix of dimension 2
n
×
2
n and A, B, C, D as in (58).Working as in the doubling iterative algorithm of Section2.2.1 and using zero initial condition P
0
=
0, so K
0
=
Y
0
X
0
-
1
=
0; we are able to derive the following nonlinear iterative equations:
(67)
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
,
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
,
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
,
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
,
with initial conditions
(68)
a
1
=
a
,
b
1
=
b
,
c
1
=
c
,
d
1
=
d
.
It is clear that c
k
=
Y
2
k
X
2
k
-
1
=
K
2
k tends to a steady state value K
~.


#### 2.3.2. Algebraic Algorithm forK
~ Computation

In this section, we present an algebraic algorithm forK
~ computation. Working as in the algebraic algorithm of Section 2.2.2 and using the parameters A, B, C, D by (58), we derive
(69)
Φ
=
[
A
B
C
D
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
0
0
Λ
-
1
]
[
W
11
W
12
W
21
W
22
]
-
1
,
which is a matrix of dimension 2
n
×
2
n.Then, the steady state Kalman filter is(70)
K
~
=
W
21
W
11
-
1
.


### 2.4. Advantages of the Proposed Algorithms

All algorithms for the computation of the steady state Kalman filter gainK
~, presented in Section 2, are summarized in Table 1. It is clear that the direct computation of the Kalman filter gain is feasible only if the following restriction holds: n
=
m. The advantage of the presented algorithms is the autonomous computation of the steady state Kalman filter gain. Especially, the steady state Kalman filter gain is important, when we want to compute the parameters of the steady state Kalman filter
(71)
x
k
+
1
/
k
+
1
=
(
I
-
K
~
H
)
F
x
k
/
k
+
K
~
z
k
+
1
=
(
I
-
G
~
)
F
x
k
/
k
+
K
~
z
k
+
1
.
It is obvious from (71) that the parameters of the steady state Kalman filter are related to the steady state Kalman filter gain.Table 1
Algorithms for the computation of the steady state Kalman filter gainK
~.
Computation ofK
~ through G
~
=
K
~
H
Direct computation ofK
~
System parametersF
,
H
,
Q
,
R
System parametersF
,
H
,
Q
,
R
Restrictionm
≥
n
Restrictionm
=
n
Algorithms parameters
Algorithms parameters
A
=
(
Q
+
(
H
T
R
-
1
H
)
-
1
)
F
-
T
H
T
R
-
1
H
A
=
H
(
Q
+
(
H
T
R
-
1
H
)
-
1
)
F
-
T
H
T
R
-
1
B
=
F
B
=
H
F
C
=
Q
F
-
T
H
T
R
-
1
H
C
=
Q
F
-
T
H
T
R
-
1
D
=
F
D
=
F
a
=
D
-
C
A
-
1
B
a
=
D
-
C
A
-
1
B
b
=
A
-
1
B
b
=
A
-
1
B
c
=
C
A
-
1
c
=
C
A
-
1
d
=
A
-
1
d
=
A
-
1
Per-step iterative algorithm
1
Per-step iterative algorithm
1
G
k
+
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
K
k
+
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
G
0
=
0
K
0
=
0
G
k
→
G
~
K
k
→
K
~
K
~
=
G
~
[
H
T
H
]
-
1
H
T
Per-step iterative algorithm
2
Per-step iterative algorithm
2
G
k
+
1
=
c
+
a
[
G
k
-
1
+
b
]
-
1
d
K
k
+
1
=
c
+
a
[
K
k
-
1
+
b
]
-
1
d
G
1
=
c
K
1
=
c
G
k
→
G
~
K
k
→
K
~
K
~
=
G
~
[
H
T
H
]
-
1
H
T
Doubling iterative algorithm
Doubling iterative algorithm
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
a
1
=
a
,
b
1
=
b
,
c
1
=
c
,
d
1
=
d
a
1
=
a
,
b
1
=
b
,
c
1
=
c
,
d
1
=
d
c
k
→
G
~
c
k
→
K
~
K
~
=
G
~
[
H
T
H
]
-
1
H
T
Algebraic algorithm
Algebraic algorithm
Φ
=
[
A
B
C
D
]
Φ
=
[
A
B
C
D
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
0
0
Λ
-
1
]
[
W
11
W
12
W
21
W
22
]
-
1
=
[
W
11
W
12
W
21
W
22
]
[
Λ
0
0
Λ
-
1
]
[
W
11
W
12
W
21
W
22
]
-
1
G
~
=
W
21
W
11
-
1
K
~
=
W
21
W
11
-
1
K
~
=
G
~
[
H
T
H
]
-
1
H
TIn particular, the steady state prediction error covariance can be computed via the steady state gain and is given by(72)
P
~
p
=
[
I
-
K
~
H
]
-
1
K
~
R
H
[
H
T
H
]
-
1
.Indeed, from (2), arises K
~
=
P
~
p
H
T
[
H
P
~
p
H
T
+
R
]
-
1, which leads to
(73)
K
~
(
H
P
~
p
H
T
+
R
)
=
P
~
p
H
T
⟹
K
~
H
P
~
p
H
T
+
K
~
R
=
P
~
p
H
T
⟹
P
~
p
H
T
-
K
~
H
P
~
p
H
T
=
K
~
R
⟹
(
I
-
K
~
H
)
P
~
p
H
T
=
K
~
R
⟹
P
~
p
H
T
=
[
I
-
K
~
H
]
-
1
K
~
R
⟹
P
~
p
H
T
H
=
[
I
-
K
~
H
]
-
1
K
~
R
H
.
Since rank
⁡
(
H
)
=
n, the matrix H
T
H is nonsingular [21]; thus from the last equation arises immediately the formula of the steady state prediction error covariance in (72).Also, by (3), the steady state estimation error covariance can be computed via the steady state prediction error covariance
(74)
P
~
e
=
[
I
-
K
~
H
]
P
~
p
.


## 2.1. Assumptions

We assume the general case, whereR and P
0 are positive definite matrices.The Kalman filter gainK
k is a matrix of dimension n
×
m.We define the matrix(11)
G
k
=
K
k
H
.
It is clear that G
k is a nonsymmetric matrix of dimension n
×
n.It is also clear that there exists a steady state value(12)
G
~
=
K
~
H
.Also, we define the matrix(13)
S
=
H
T
R
-
1
H
.
Note that S is an n
×
n symmetric positive semidefinite matrix and S is a positive definite if rank
⁡
(
H
)
=
n; this means that S is a nonsingular matrix in the case, rank
⁡
(
H
)
=
n with m
≥
n, [21].


## 2.2. Indirect Steady State Kalman Filter Gain Computation

In this section, we present algorithms forG
~ computation. Then, we show how to compute the steady state Kalman filter K
~ through G
~
=
K
~
H.


### 2.2.1. Iterative Algorithms forG
~ Computation

In this section, we present two iterative per-step algorithms and an iterative doubling algorithm forG
~ computation.Per-Step Iterative Algorithm
1. Using (2) and (11), it is derived that
(14)
G
k
=
K
k
H
=
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
=
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
R
R
-
1
H
=
P
k
/
k
-
1
H
T
(
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
×
[
H
P
k
/
k
-
1
H
T
+
R
-
H
P
k
/
k
-
1
H
T
]
)
R
-
1
H
=
P
k
/
k
-
1
H
T
(
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
[
H
P
k
/
k
-
1
H
T
+
R
]
-
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
)
R
-
1
H
=
P
k
/
k
-
1
H
T
(
I
-
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
)
R
-
1
H
=
P
k
/
k
-
1
H
T
R
-
1
H
-
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
R
-
1
H
=
(
P
k
/
k
-
1
-
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
)
×
H
T
R
-
1
H
=
[
P
k
/
k
-
1
-
1
+
H
T
R
-
1
H
]
-
1
H
T
R
-
1
H
=
[
P
k
/
k
-
1
-
1
+
S
]
-
1
S
.Thus, arises(15)
K
k
H
=
[
P
k
/
k
-
1
-
1
+
S
]
-
1
S
.Using the Riccati equation (7), (15), the nonsingularity of S, and some algebra we have
(16)
P
k
+
1
/
k
=
Q
+
F
[
P
k
/
k
-
1
-
1
+
H
T
R
-
1
H
]
-
1
F
T
=
Q
+
F
[
P
k
/
k
-
1
-
1
+
S
]
-
1
F
T
=
Q
+
F
K
k
H
S
-
1
F
T
⟹
P
k
+
1
/
k
S
=
Q
S
+
F
K
k
H
S
-
1
F
T
S
=
Q
F
-
T
S
[
S
-
1
F
-
T
S
]
-
1
+
F
K
k
H
[
S
-
1
F
-
T
S
]
-
1
⟹
P
k
+
1
/
k
S
(
S
-
1
F
-
T
S
)
=
Q
F
-
T
S
+
F
K
k
H
⟹
S
-
1
F
-
T
S
=
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
⟹
K
k
+
1
H
(
S
-
1
F
-
T
S
)
=
K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
.Also, from (2) and (13), we can write
(17)
K
k
(
H
P
k
/
k
-
1
H
T
+
R
)
=
P
k
/
k
-
1
H
T
⟹
K
k
H
P
k
/
k
-
1
H
T
+
K
k
R
=
P
k
/
k
-
1
H
T
⟹
K
k
R
=
P
k
/
k
-
1
H
T
-
K
k
H
P
k
/
k
-
1
H
T
⟹
K
k
R
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
⟹
K
k
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
R
-
1
⟹
K
k
H
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
R
-
1
H
⟹
K
k
H
=
(
I
-
K
k
H
)
P
k
/
k
-
1
S
.Since the matricesP
k
/
k
-
1
,
S are nonsingular, the last equation yields
(18)
K
k
H
S
-
1
P
k
/
k
-
1
-
1
=
I
-
K
k
H
.Substituting in (16) the matrix K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1 by (18), it follows
(19)
K
k
+
1
H
(
S
-
1
F
-
T
S
)
=
K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
=
(
I
-
K
k
+
1
H
)
(
Q
F
-
T
S
+
F
K
k
H
)
=
Q
F
-
T
S
+
F
K
k
H
-
K
k
+
1
H
Q
F
-
T
S
-
K
k
+
1
H
F
K
k
H
,
whereby it is implied that
(20)
K
k
+
1
H
(
S
-
1
F
-
T
S
)
+
K
k
+
1
H
Q
F
-
T
S
+
K
k
+
1
H
F
K
k
H
=
Q
F
-
T
S
+
F
K
k
H
⟹
K
k
+
1
H
(
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
)
=
Q
F
-
T
S
+
F
K
k
H
⟹
K
k
+
1
H
=
(
Q
F
-
T
S
+
F
K
k
H
)
×
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
]
-
1
.Thus, the above equation can be written as(21)
K
k
+
1
H
=
(
Q
F
-
T
S
+
F
K
k
H
)
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
]
-
1
.Combining (21) with (11), the following nonlinear iterative equation with respect to G
k is derived:
(22)
G
k
+
1
=
(
(
Q
F
-
T
S
)
+
(
F
)
G
k
)
×
[
(
S
-
1
F
-
T
S
+
Q
F
-
T
S
)
+
(
F
)
G
k
]
-
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
,
where
(23)
A
=
(
Q
+
S
-
1
)
F
-
T
S
,
B
=
F
,
C
=
Q
F
-
T
S
,
D
=
F
.The algorithm uses the initial conditionG
0
=
K
0
H
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1
H. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0 and so we are to use the initial condition G
0
=
0.It is clear thatG
k tends to a steady state value G
~ and by (22) G
~ satisfies
(24)
G
~
=
(
C
+
D
G
~
)
[
A
+
B
G
~
]
-
1
.Per-Step Iterative Algorithm
2. We rewrite (22) as
(25)
G
k
+
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
=
(
C
A
-
1
A
+
(
D
+
C
A
-
1
B
-
C
A
-
1
B
)
G
k
)
[
A
+
B
G
k
]
-
1
=
(
C
A
-
1
(
A
+
B
G
k
)
+
(
D
-
C
A
-
1
B
)
G
k
)
[
A
+
B
G
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
G
k
[
A
+
B
G
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
A
G
k
-
1
+
B
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
G
k
-
1
+
A
-
1
B
]
-
1
A
-
1
.
Thus, the following nonlinear iterative equation with respect to G
k is derived:
(26)
G
k
+
1
=
c
+
a
[
G
k
-
1
+
b
]
-
1
d
,
where
(27)
a
=
D
-
C
A
-
1
B
=
F
-
Q
[
Q
+
S
-
1
]
-
1
F
,
b
=
A
-
1
B
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
,
c
=
C
A
-
1
=
Q
[
Q
+
S
-
1
]
-
1
,
d
=
A
-
1
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
.
The algorithm uses the initial condition G
0
=
K
0
H
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1
H. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0. In this case, in order to avoid G
0
-
1, we are to use the initial condition G
1
=
c.It is clear thatG
k tends to a steady state value G
~ and by (26) G
~ satisfies
(28)
G
~
=
c
+
a
[
G
~
-
1
+
b
]
-
1
d
.Doubling Iterative Algorithm. Ιn (22), setting
(29)
G
k
=
K
k
H
=
Y
k
X
k
-
1
,
we take
(30)
Y
k
+
1
X
k
+
1
-
1
=
(
C
+
D
Y
k
X
k
-
1
)
[
A
+
B
Y
k
X
k
-
1
]
-
1
=
(
C
X
k
+
D
Y
k
)
[
A
X
k
+
B
Y
k
]
-
1
or
(31)
[
X
k
+
1
Y
k
+
1
]
=
Φ
[
X
k
Y
k
]
,
where
(32)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
is a matrix of dimension 2
n
×
2
n and A, B, C, D as in (23).We are able to use zero initial conditionP
0
=
0, so G
0
=
K
0
H
=
Y
0
X
0
-
1
=
0; that is,
(33)
[
X
0
Y
0
]
=
[
I
0
]
,
and hence
(34)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
.We define(35)
Φ
2
k
=
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
with initial condition
(36)
Φ
2
0
=
[
d
0
-
1
d
0
-
1
b
0
c
0
d
0
-
1
c
0
d
0
-
1
b
0
+
a
0
]
=
Φ
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
.Then,(37)
[
X
(
2
k
)
Y
(
2
k
)
]
=
Φ
2
k
[
I
0
]
,
and, using the doubling principle [1] Φ
2
k
+
1
=
Φ
2
k
Φ
2
k, we have
(38)
[
d
k
+
1
-
1
d
k
+
1
-
1
b
k
+
1
c
k
+
1
d
k
+
1
-
1
c
k
+
1
d
k
+
1
-
1
b
k
+
1
+
a
k
+
1
]
=
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
.Then we are able to derive, after some algebra, the following nonlinear iterative equations:(39)
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
,
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
,
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
,
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
,
with initial conditions
(40)
a
1
=
D
-
C
A
-
1
B
=
F
-
Q
[
Q
+
S
-
1
]
-
1
F
,
b
1
=
A
-
1
B
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
,
c
1
=
C
A
-
1
=
Q
[
Q
+
S
-
1
]
-
1
,
d
1
=
A
-
1
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
.Then, since(41)
[
X
(
2
k
)
Y
(
2
k
)
]
=
Φ
2
k
[
I
0
]
=
[
d
k
-
1
c
k
d
k
-
1
]
,
it is clear that c
k
=
Y
2
k
X
2
k
-
1
=
G
2
k tends to a steady state value G
~.


### 2.2.2. Algebraic Algorithm forG
~ Computation

In this section, we present an algebraic algorithm forG
~ computation. As in (29), setting
(42)
G
k
=
K
k
H
=
Y
k
X
k
-
1
and using the parameters A, B, C, D by (23), we derive
(43)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
,
which is a matrix of dimension 2
n
×
2
n. Since
(44)
det
⁡
⁡
Φ
=
det
⁡
⁡
(
A
)
det
⁡
⁡
(
D
-
C
A
-
1
B
)
=
det
⁡
⁡
(
(
Q
+
S
-
1
)
F
-
T
S
)
×
det
⁡
⁡
(
F
-
Q
F
-
T
S
[
(
Q
+
S
-
1
)
F
-
T
S
]
-
1
F
)
=
det
⁡
⁡
(
Q
+
S
-
1
)
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
S
)
×
det
⁡
⁡
(
F
-
Q
F
-
T
S
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
F
-
Q
[
Q
+
S
-
1
]
-
1
F
)
×
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
Q
+
S
-
1
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
I
-
Q
[
Q
+
S
-
1
]
-
1
)
×
det
⁡
⁡
(
F
)
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
Q
+
S
-
1
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
(
Q
+
S
-
1
)
-
Q
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
S
-
1
)
=
1
,
it is evident that Φ is a nonsingular matrix and its eigenvalues occur in reciprocal pairs.Thus, (43) can be written
(45)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
=
W
L
W
-
1
,
where
(46)
L
=
[
Λ
0
0
Λ
-
1
]
is a diagonal matrix containing the eigenvalues of Φ, with Λ diagonal matrix with all the eigenvalues of Φ lying outside the unit circle, and
(47)
W
=
[
W
11
W
12
W
21
W
22
]
is the matrix containing the corresponding eigenvectors of Φ, with
(48)
V
=
W
-
1
=
[
V
11
V
12
V
21
V
22
]
.We are able to use zero initial conditionP
0
=
0, so G
0
=
K
0
H
=
Y
0
X
0
-
1
=
0; that is,
(49)
[
X
0
Y
0
]
=
[
I
0
]
,
and hence
(50)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
.Then, from (50) and (45)–(48), we are able to write
(51)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
=
[
W
L
W
-
1
]
k
[
I
0
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
k
0
0
Λ
-
k
]
[
V
11
V
12
V
21
V
22
]
[
I
0
]
;that is,(52)
[
X
k
Y
k
]
=
[
W
11
Λ
k
V
11
+
W
12
Λ
-
k
V
21
W
21
Λ
k
V
11
+
W
22
Λ
-
k
V
21
]
.Substituting in (42) the matrices X
k, Y
k from (52), we have that
(53)
G
k
=
Y
k
X
k
-
1
=
(
W
21
Λ
k
V
11
+
W
22
Λ
-
k
V
21
)
×
[
W
11
Λ
k
V
11
+
W
12
Λ
-
k
V
21
]
-
1
.Furthermore, the diagonal matrixΛ
-
1 contains all the eigenvalues of Φ lying inside the unit circle, which follows that lim
⁡
k
→
∞
⁡
Λ
-
k
=
0. Then, G
k tends to a steady state value G
~ with G
~
=
lim
⁡
k
→
∞
⁡
G
k, and from (53) arises
(54)
G
~
=
W
21
W
11
-
1
.


### 2.2.3. Steady State Kalman Filter Gain Computation

All algorithms presented in Sections2.2.1 and 2.2.2 compute the steady state value G
~. Taking into account the assumptions of Section 2.1, we are able to conclude that, under the condition rank
⁡
(
H
)
=
n, the steady state gain is
(55)
K
~
=
G
~
[
H
T
H
]
-
1
H
T
.


## 2.2.1. Iterative Algorithms forG
~ Computation

In this section, we present two iterative per-step algorithms and an iterative doubling algorithm forG
~ computation.Per-Step Iterative Algorithm
1. Using (2) and (11), it is derived that
(14)
G
k
=
K
k
H
=
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
=
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
R
R
-
1
H
=
P
k
/
k
-
1
H
T
(
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
×
[
H
P
k
/
k
-
1
H
T
+
R
-
H
P
k
/
k
-
1
H
T
]
)
R
-
1
H
=
P
k
/
k
-
1
H
T
(
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
[
H
P
k
/
k
-
1
H
T
+
R
]
-
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
)
R
-
1
H
=
P
k
/
k
-
1
H
T
(
I
-
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
)
R
-
1
H
=
P
k
/
k
-
1
H
T
R
-
1
H
-
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
H
T
R
-
1
H
=
(
P
k
/
k
-
1
-
P
k
/
k
-
1
H
T
[
H
P
k
/
k
-
1
H
T
+
R
]
-
1
H
P
k
/
k
-
1
)
×
H
T
R
-
1
H
=
[
P
k
/
k
-
1
-
1
+
H
T
R
-
1
H
]
-
1
H
T
R
-
1
H
=
[
P
k
/
k
-
1
-
1
+
S
]
-
1
S
.Thus, arises(15)
K
k
H
=
[
P
k
/
k
-
1
-
1
+
S
]
-
1
S
.Using the Riccati equation (7), (15), the nonsingularity of S, and some algebra we have
(16)
P
k
+
1
/
k
=
Q
+
F
[
P
k
/
k
-
1
-
1
+
H
T
R
-
1
H
]
-
1
F
T
=
Q
+
F
[
P
k
/
k
-
1
-
1
+
S
]
-
1
F
T
=
Q
+
F
K
k
H
S
-
1
F
T
⟹
P
k
+
1
/
k
S
=
Q
S
+
F
K
k
H
S
-
1
F
T
S
=
Q
F
-
T
S
[
S
-
1
F
-
T
S
]
-
1
+
F
K
k
H
[
S
-
1
F
-
T
S
]
-
1
⟹
P
k
+
1
/
k
S
(
S
-
1
F
-
T
S
)
=
Q
F
-
T
S
+
F
K
k
H
⟹
S
-
1
F
-
T
S
=
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
⟹
K
k
+
1
H
(
S
-
1
F
-
T
S
)
=
K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
.Also, from (2) and (13), we can write
(17)
K
k
(
H
P
k
/
k
-
1
H
T
+
R
)
=
P
k
/
k
-
1
H
T
⟹
K
k
H
P
k
/
k
-
1
H
T
+
K
k
R
=
P
k
/
k
-
1
H
T
⟹
K
k
R
=
P
k
/
k
-
1
H
T
-
K
k
H
P
k
/
k
-
1
H
T
⟹
K
k
R
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
⟹
K
k
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
R
-
1
⟹
K
k
H
=
(
I
-
K
k
H
)
P
k
/
k
-
1
H
T
R
-
1
H
⟹
K
k
H
=
(
I
-
K
k
H
)
P
k
/
k
-
1
S
.Since the matricesP
k
/
k
-
1
,
S are nonsingular, the last equation yields
(18)
K
k
H
S
-
1
P
k
/
k
-
1
-
1
=
I
-
K
k
H
.Substituting in (16) the matrix K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1 by (18), it follows
(19)
K
k
+
1
H
(
S
-
1
F
-
T
S
)
=
K
k
+
1
H
S
-
1
P
k
+
1
/
k
-
1
(
Q
F
-
T
S
+
F
K
k
H
)
=
(
I
-
K
k
+
1
H
)
(
Q
F
-
T
S
+
F
K
k
H
)
=
Q
F
-
T
S
+
F
K
k
H
-
K
k
+
1
H
Q
F
-
T
S
-
K
k
+
1
H
F
K
k
H
,
whereby it is implied that
(20)
K
k
+
1
H
(
S
-
1
F
-
T
S
)
+
K
k
+
1
H
Q
F
-
T
S
+
K
k
+
1
H
F
K
k
H
=
Q
F
-
T
S
+
F
K
k
H
⟹
K
k
+
1
H
(
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
)
=
Q
F
-
T
S
+
F
K
k
H
⟹
K
k
+
1
H
=
(
Q
F
-
T
S
+
F
K
k
H
)
×
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
]
-
1
.Thus, the above equation can be written as(21)
K
k
+
1
H
=
(
Q
F
-
T
S
+
F
K
k
H
)
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
K
k
H
]
-
1
.Combining (21) with (11), the following nonlinear iterative equation with respect to G
k is derived:
(22)
G
k
+
1
=
(
(
Q
F
-
T
S
)
+
(
F
)
G
k
)
×
[
(
S
-
1
F
-
T
S
+
Q
F
-
T
S
)
+
(
F
)
G
k
]
-
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
,
where
(23)
A
=
(
Q
+
S
-
1
)
F
-
T
S
,
B
=
F
,
C
=
Q
F
-
T
S
,
D
=
F
.The algorithm uses the initial conditionG
0
=
K
0
H
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1
H. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0 and so we are to use the initial condition G
0
=
0.It is clear thatG
k tends to a steady state value G
~ and by (22) G
~ satisfies
(24)
G
~
=
(
C
+
D
G
~
)
[
A
+
B
G
~
]
-
1
.Per-Step Iterative Algorithm
2. We rewrite (22) as
(25)
G
k
+
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
=
(
C
A
-
1
A
+
(
D
+
C
A
-
1
B
-
C
A
-
1
B
)
G
k
)
[
A
+
B
G
k
]
-
1
=
(
C
A
-
1
(
A
+
B
G
k
)
+
(
D
-
C
A
-
1
B
)
G
k
)
[
A
+
B
G
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
G
k
[
A
+
B
G
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
A
G
k
-
1
+
B
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
G
k
-
1
+
A
-
1
B
]
-
1
A
-
1
.
Thus, the following nonlinear iterative equation with respect to G
k is derived:
(26)
G
k
+
1
=
c
+
a
[
G
k
-
1
+
b
]
-
1
d
,
where
(27)
a
=
D
-
C
A
-
1
B
=
F
-
Q
[
Q
+
S
-
1
]
-
1
F
,
b
=
A
-
1
B
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
,
c
=
C
A
-
1
=
Q
[
Q
+
S
-
1
]
-
1
,
d
=
A
-
1
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
.
The algorithm uses the initial condition G
0
=
K
0
H
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1
H. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0. In this case, in order to avoid G
0
-
1, we are to use the initial condition G
1
=
c.It is clear thatG
k tends to a steady state value G
~ and by (26) G
~ satisfies
(28)
G
~
=
c
+
a
[
G
~
-
1
+
b
]
-
1
d
.Doubling Iterative Algorithm. Ιn (22), setting
(29)
G
k
=
K
k
H
=
Y
k
X
k
-
1
,
we take
(30)
Y
k
+
1
X
k
+
1
-
1
=
(
C
+
D
Y
k
X
k
-
1
)
[
A
+
B
Y
k
X
k
-
1
]
-
1
=
(
C
X
k
+
D
Y
k
)
[
A
X
k
+
B
Y
k
]
-
1
or
(31)
[
X
k
+
1
Y
k
+
1
]
=
Φ
[
X
k
Y
k
]
,
where
(32)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
is a matrix of dimension 2
n
×
2
n and A, B, C, D as in (23).We are able to use zero initial conditionP
0
=
0, so G
0
=
K
0
H
=
Y
0
X
0
-
1
=
0; that is,
(33)
[
X
0
Y
0
]
=
[
I
0
]
,
and hence
(34)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
.We define(35)
Φ
2
k
=
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
with initial condition
(36)
Φ
2
0
=
[
d
0
-
1
d
0
-
1
b
0
c
0
d
0
-
1
c
0
d
0
-
1
b
0
+
a
0
]
=
Φ
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
.Then,(37)
[
X
(
2
k
)
Y
(
2
k
)
]
=
Φ
2
k
[
I
0
]
,
and, using the doubling principle [1] Φ
2
k
+
1
=
Φ
2
k
Φ
2
k, we have
(38)
[
d
k
+
1
-
1
d
k
+
1
-
1
b
k
+
1
c
k
+
1
d
k
+
1
-
1
c
k
+
1
d
k
+
1
-
1
b
k
+
1
+
a
k
+
1
]
=
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
[
d
k
-
1
d
k
-
1
b
k
c
k
d
k
-
1
c
k
d
k
-
1
b
k
+
a
k
]
.Then we are able to derive, after some algebra, the following nonlinear iterative equations:(39)
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
,
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
,
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
,
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
,
with initial conditions
(40)
a
1
=
D
-
C
A
-
1
B
=
F
-
Q
[
Q
+
S
-
1
]
-
1
F
,
b
1
=
A
-
1
B
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
,
c
1
=
C
A
-
1
=
Q
[
Q
+
S
-
1
]
-
1
,
d
1
=
A
-
1
=
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
.Then, since(41)
[
X
(
2
k
)
Y
(
2
k
)
]
=
Φ
2
k
[
I
0
]
=
[
d
k
-
1
c
k
d
k
-
1
]
,
it is clear that c
k
=
Y
2
k
X
2
k
-
1
=
G
2
k tends to a steady state value G
~.


## 2.2.2. Algebraic Algorithm forG
~ Computation

In this section, we present an algebraic algorithm forG
~ computation. As in (29), setting
(42)
G
k
=
K
k
H
=
Y
k
X
k
-
1
and using the parameters A, B, C, D by (23), we derive
(43)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
,
which is a matrix of dimension 2
n
×
2
n. Since
(44)
det
⁡
⁡
Φ
=
det
⁡
⁡
(
A
)
det
⁡
⁡
(
D
-
C
A
-
1
B
)
=
det
⁡
⁡
(
(
Q
+
S
-
1
)
F
-
T
S
)
×
det
⁡
⁡
(
F
-
Q
F
-
T
S
[
(
Q
+
S
-
1
)
F
-
T
S
]
-
1
F
)
=
det
⁡
⁡
(
Q
+
S
-
1
)
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
S
)
×
det
⁡
⁡
(
F
-
Q
F
-
T
S
S
-
1
F
T
[
Q
+
S
-
1
]
-
1
F
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
F
-
Q
[
Q
+
S
-
1
]
-
1
F
)
×
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
Q
+
S
-
1
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
I
-
Q
[
Q
+
S
-
1
]
-
1
)
×
det
⁡
⁡
(
F
)
det
⁡
⁡
(
F
-
1
)
det
⁡
⁡
(
Q
+
S
-
1
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
(
Q
+
S
-
1
)
-
Q
)
=
det
⁡
⁡
(
S
)
det
⁡
⁡
(
S
-
1
)
=
1
,
it is evident that Φ is a nonsingular matrix and its eigenvalues occur in reciprocal pairs.Thus, (43) can be written
(45)
Φ
=
[
A
B
C
D
]
=
[
(
Q
+
S
-
1
)
F
-
T
S
F
Q
F
-
T
S
F
]
=
W
L
W
-
1
,
where
(46)
L
=
[
Λ
0
0
Λ
-
1
]
is a diagonal matrix containing the eigenvalues of Φ, with Λ diagonal matrix with all the eigenvalues of Φ lying outside the unit circle, and
(47)
W
=
[
W
11
W
12
W
21
W
22
]
is the matrix containing the corresponding eigenvectors of Φ, with
(48)
V
=
W
-
1
=
[
V
11
V
12
V
21
V
22
]
.We are able to use zero initial conditionP
0
=
0, so G
0
=
K
0
H
=
Y
0
X
0
-
1
=
0; that is,
(49)
[
X
0
Y
0
]
=
[
I
0
]
,
and hence
(50)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
.Then, from (50) and (45)–(48), we are able to write
(51)
[
X
k
Y
k
]
=
Φ
k
[
I
0
]
=
[
W
L
W
-
1
]
k
[
I
0
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
k
0
0
Λ
-
k
]
[
V
11
V
12
V
21
V
22
]
[
I
0
]
;that is,(52)
[
X
k
Y
k
]
=
[
W
11
Λ
k
V
11
+
W
12
Λ
-
k
V
21
W
21
Λ
k
V
11
+
W
22
Λ
-
k
V
21
]
.Substituting in (42) the matrices X
k, Y
k from (52), we have that
(53)
G
k
=
Y
k
X
k
-
1
=
(
W
21
Λ
k
V
11
+
W
22
Λ
-
k
V
21
)
×
[
W
11
Λ
k
V
11
+
W
12
Λ
-
k
V
21
]
-
1
.Furthermore, the diagonal matrixΛ
-
1 contains all the eigenvalues of Φ lying inside the unit circle, which follows that lim
⁡
k
→
∞
⁡
Λ
-
k
=
0. Then, G
k tends to a steady state value G
~ with G
~
=
lim
⁡
k
→
∞
⁡
G
k, and from (53) arises
(54)
G
~
=
W
21
W
11
-
1
.


## 2.2.3. Steady State Kalman Filter Gain Computation

All algorithms presented in Sections2.2.1 and 2.2.2 compute the steady state value G
~. Taking into account the assumptions of Section 2.1, we are able to conclude that, under the condition rank
⁡
(
H
)
=
n, the steady state gain is
(55)
K
~
=
G
~
[
H
T
H
]
-
1
H
T
.


## 2.3. Direct Steady State Kalman Filter Gain Computation

In this section, we present algorithms for the direct computation of the steady state Kalman filterK
~. The proposed algorithms compute directly the steady state Kalman filter gain, that is, without using G
~
=
K
~
H. All these algorithms hold under the assumption that n
=
m. Note that, since rank
⁡
(
H
)
=
n, H and S are nonsingular matrices.


### 2.3.1. Iterative Algorithms forK
~ Computation

In this section, we present two iterative per-step algorithms and an iterative doubling algorithm forK
~ computation.Per-Step Iterative Algorithm
1. Using (11), (22), and (13), we are able to derive the following nonlinear iterative equation with respect to the Kalman filter gain K
k:
(56)
K
k
+
1
=
G
k
+
1
H
-
1
=
(
Q
F
-
T
S
+
F
G
k
)
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
G
k
]
-
1
H
-
1
=
(
Q
F
-
T
H
T
R
-
1
H
+
F
G
k
)
×
[
H
-
1
R
H
-
T
F
-
T
H
T
R
-
1
H
+
Q
F
-
T
H
T
R
-
1
H
+
F
G
k
]
-
1
H
-
1
=
(
Q
F
-
T
H
T
R
-
1
H
+
F
K
k
H
)
×
[
R
H
-
T
F
-
T
H
T
R
-
1
H
+
H
Q
F
-
T
H
T
R
-
1
H
+
H
F
K
k
H
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
H
[
R
H
-
T
F
-
T
H
T
R
-
1
H
+
H
Q
F
-
T
H
T
R
-
1
H
+
H
F
K
k
H
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
R
H
-
T
F
-
T
H
T
R
-
1
+
H
Q
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
H
Q
F
-
T
H
T
R
-
1
+
R
H
-
T
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
.The nonsingularity ofS and (13) allow us to write the equality in (56) as
(57)
K
k
+
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
H
Q
F
-
T
H
T
R
-
1
+
H
S
-
1
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
,
where
(58)
A
=
H
Q
F
-
T
H
T
R
-
1
+
H
S
-
1
F
-
T
H
T
R
-
1
A
=
H
(
Q
+
S
-
1
)
F
-
T
H
T
R
-
1
,
B
=
H
F
,
C
=
Q
F
-
T
H
T
R
-
1
,
D
=
F
.The initial condition isK
0
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0 and so we are to use the initial condition K
0
=
0.It is clear thatK
k tends to a steady state value K
~ satisfying
(59)
K
~
=
(
C
+
D
K
~
)
[
A
+
B
K
~
]
-
1
.Per-Step Iterative Algorithm
2. Using (57), we are able to derive the following nonlinear iterative equation with respect to the Kalman filter gain K
k:
(60)
K
k
+
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
=
(
C
A
-
1
A
+
(
D
+
C
A
-
1
B
-
C
A
-
1
B
)
K
k
)
[
A
+
B
K
k
]
-
1
=
(
C
A
-
1
(
A
+
B
K
k
)
+
(
D
-
C
A
-
1
B
)
K
k
)
[
A
+
B
K
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
K
k
[
A
+
B
K
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
A
K
k
-
1
+
B
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
K
k
-
1
+
A
-
1
B
]
-
1
A
-
1
=
c
+
a
[
K
k
-
1
+
b
]
-
1
d
,
where A
,
B
,
C
,
D are given by (58) and
(61)
a
=
D
-
C
A
-
1
B
,
b
=
A
-
1
B
,
c
=
C
A
-
1
,
d
=
A
-
1
.The algorithm uses the initial conditionK
0
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0. In this case, in order to avoid K
0
-
1, we are to use the initial condition K
1
=
c.It is clear thatK
k tends to a steady state value K
~ satisfying
(62)
K
~
=
c
+
a
[
K
~
-
1
+
b
]
-
1
d
.Doubling Iterative Algorithm. Ιn (57), setting
(63)
K
k
=
Y
k
X
k
-
1
,
we take
(64)
Y
k
+
1
X
k
+
1
-
1
=
(
C
+
D
Y
k
X
k
-
1
)
[
A
+
B
Y
k
X
k
-
1
]
-
1
=
(
C
X
k
+
D
Y
k
)
[
A
X
k
+
B
Y
k
]
-
1
or
(65)
[
X
k
+
1
Y
k
+
1
]
=
Φ
[
X
k
Y
k
]
,
where
(66)
Φ
=
[
A
B
C
D
]
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
is a matrix of dimension 2
n
×
2
n and A, B, C, D as in (58).Working as in the doubling iterative algorithm of Section2.2.1 and using zero initial condition P
0
=
0, so K
0
=
Y
0
X
0
-
1
=
0; we are able to derive the following nonlinear iterative equations:
(67)
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
,
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
,
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
,
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
,
with initial conditions
(68)
a
1
=
a
,
b
1
=
b
,
c
1
=
c
,
d
1
=
d
.
It is clear that c
k
=
Y
2
k
X
2
k
-
1
=
K
2
k tends to a steady state value K
~.


### 2.3.2. Algebraic Algorithm forK
~ Computation

In this section, we present an algebraic algorithm forK
~ computation. Working as in the algebraic algorithm of Section 2.2.2 and using the parameters A, B, C, D by (58), we derive
(69)
Φ
=
[
A
B
C
D
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
0
0
Λ
-
1
]
[
W
11
W
12
W
21
W
22
]
-
1
,
which is a matrix of dimension 2
n
×
2
n.Then, the steady state Kalman filter is(70)
K
~
=
W
21
W
11
-
1
.


## 2.3.1. Iterative Algorithms forK
~ Computation

In this section, we present two iterative per-step algorithms and an iterative doubling algorithm forK
~ computation.Per-Step Iterative Algorithm
1. Using (11), (22), and (13), we are able to derive the following nonlinear iterative equation with respect to the Kalman filter gain K
k:
(56)
K
k
+
1
=
G
k
+
1
H
-
1
=
(
Q
F
-
T
S
+
F
G
k
)
[
S
-
1
F
-
T
S
+
Q
F
-
T
S
+
F
G
k
]
-
1
H
-
1
=
(
Q
F
-
T
H
T
R
-
1
H
+
F
G
k
)
×
[
H
-
1
R
H
-
T
F
-
T
H
T
R
-
1
H
+
Q
F
-
T
H
T
R
-
1
H
+
F
G
k
]
-
1
H
-
1
=
(
Q
F
-
T
H
T
R
-
1
H
+
F
K
k
H
)
×
[
R
H
-
T
F
-
T
H
T
R
-
1
H
+
H
Q
F
-
T
H
T
R
-
1
H
+
H
F
K
k
H
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
H
[
R
H
-
T
F
-
T
H
T
R
-
1
H
+
H
Q
F
-
T
H
T
R
-
1
H
+
H
F
K
k
H
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
R
H
-
T
F
-
T
H
T
R
-
1
+
H
Q
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
H
Q
F
-
T
H
T
R
-
1
+
R
H
-
T
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
.The nonsingularity ofS and (13) allow us to write the equality in (56) as
(57)
K
k
+
1
=
(
Q
F
-
T
H
T
R
-
1
+
F
K
k
)
×
[
H
Q
F
-
T
H
T
R
-
1
+
H
S
-
1
F
-
T
H
T
R
-
1
+
H
F
K
k
]
-
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
,
where
(58)
A
=
H
Q
F
-
T
H
T
R
-
1
+
H
S
-
1
F
-
T
H
T
R
-
1
A
=
H
(
Q
+
S
-
1
)
F
-
T
H
T
R
-
1
,
B
=
H
F
,
C
=
Q
F
-
T
H
T
R
-
1
,
D
=
F
.The initial condition isK
0
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0 and so we are to use the initial condition K
0
=
0.It is clear thatK
k tends to a steady state value K
~ satisfying
(59)
K
~
=
(
C
+
D
K
~
)
[
A
+
B
K
~
]
-
1
.Per-Step Iterative Algorithm
2. Using (57), we are able to derive the following nonlinear iterative equation with respect to the Kalman filter gain K
k:
(60)
K
k
+
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
=
(
C
A
-
1
A
+
(
D
+
C
A
-
1
B
-
C
A
-
1
B
)
K
k
)
[
A
+
B
K
k
]
-
1
=
(
C
A
-
1
(
A
+
B
K
k
)
+
(
D
-
C
A
-
1
B
)
K
k
)
[
A
+
B
K
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
K
k
[
A
+
B
K
k
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
A
K
k
-
1
+
B
]
-
1
=
C
A
-
1
+
(
D
-
C
A
-
1
B
)
[
K
k
-
1
+
A
-
1
B
]
-
1
A
-
1
=
c
+
a
[
K
k
-
1
+
b
]
-
1
d
,
where A
,
B
,
C
,
D are given by (58) and
(61)
a
=
D
-
C
A
-
1
B
,
b
=
A
-
1
B
,
c
=
C
A
-
1
,
d
=
A
-
1
.The algorithm uses the initial conditionK
0
=
P
0
H
T
[
H
P
0
H
T
+
R
]
-
1. It is known [1] that the prediction error covariance tends to the steady state prediction error covariance and that the convergence is independent of the initial uncertainty, that is, independent of the value of the initial condition P
0. Thus, we are able to assume zero initial condition P
0
=
0. In this case, in order to avoid K
0
-
1, we are to use the initial condition K
1
=
c.It is clear thatK
k tends to a steady state value K
~ satisfying
(62)
K
~
=
c
+
a
[
K
~
-
1
+
b
]
-
1
d
.Doubling Iterative Algorithm. Ιn (57), setting
(63)
K
k
=
Y
k
X
k
-
1
,
we take
(64)
Y
k
+
1
X
k
+
1
-
1
=
(
C
+
D
Y
k
X
k
-
1
)
[
A
+
B
Y
k
X
k
-
1
]
-
1
=
(
C
X
k
+
D
Y
k
)
[
A
X
k
+
B
Y
k
]
-
1
or
(65)
[
X
k
+
1
Y
k
+
1
]
=
Φ
[
X
k
Y
k
]
,
where
(66)
Φ
=
[
A
B
C
D
]
=
[
d
-
1
d
-
1
b
c
d
-
1
c
d
-
1
b
+
a
]
is a matrix of dimension 2
n
×
2
n and A, B, C, D as in (58).Working as in the doubling iterative algorithm of Section2.2.1 and using zero initial condition P
0
=
0, so K
0
=
Y
0
X
0
-
1
=
0; we are able to derive the following nonlinear iterative equations:
(67)
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
,
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
,
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
,
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
,
with initial conditions
(68)
a
1
=
a
,
b
1
=
b
,
c
1
=
c
,
d
1
=
d
.
It is clear that c
k
=
Y
2
k
X
2
k
-
1
=
K
2
k tends to a steady state value K
~.


## 2.3.2. Algebraic Algorithm forK
~ Computation

In this section, we present an algebraic algorithm forK
~ computation. Working as in the algebraic algorithm of Section 2.2.2 and using the parameters A, B, C, D by (58), we derive
(69)
Φ
=
[
A
B
C
D
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
0
0
Λ
-
1
]
[
W
11
W
12
W
21
W
22
]
-
1
,
which is a matrix of dimension 2
n
×
2
n.Then, the steady state Kalman filter is(70)
K
~
=
W
21
W
11
-
1
.


## 2.4. Advantages of the Proposed Algorithms

All algorithms for the computation of the steady state Kalman filter gainK
~, presented in Section 2, are summarized in Table 1. It is clear that the direct computation of the Kalman filter gain is feasible only if the following restriction holds: n
=
m. The advantage of the presented algorithms is the autonomous computation of the steady state Kalman filter gain. Especially, the steady state Kalman filter gain is important, when we want to compute the parameters of the steady state Kalman filter
(71)
x
k
+
1
/
k
+
1
=
(
I
-
K
~
H
)
F
x
k
/
k
+
K
~
z
k
+
1
=
(
I
-
G
~
)
F
x
k
/
k
+
K
~
z
k
+
1
.
It is obvious from (71) that the parameters of the steady state Kalman filter are related to the steady state Kalman filter gain.Table 1
Algorithms for the computation of the steady state Kalman filter gainK
~.
Computation ofK
~ through G
~
=
K
~
H
Direct computation ofK
~
System parametersF
,
H
,
Q
,
R
System parametersF
,
H
,
Q
,
R
Restrictionm
≥
n
Restrictionm
=
n
Algorithms parameters
Algorithms parameters
A
=
(
Q
+
(
H
T
R
-
1
H
)
-
1
)
F
-
T
H
T
R
-
1
H
A
=
H
(
Q
+
(
H
T
R
-
1
H
)
-
1
)
F
-
T
H
T
R
-
1
B
=
F
B
=
H
F
C
=
Q
F
-
T
H
T
R
-
1
H
C
=
Q
F
-
T
H
T
R
-
1
D
=
F
D
=
F
a
=
D
-
C
A
-
1
B
a
=
D
-
C
A
-
1
B
b
=
A
-
1
B
b
=
A
-
1
B
c
=
C
A
-
1
c
=
C
A
-
1
d
=
A
-
1
d
=
A
-
1
Per-step iterative algorithm
1
Per-step iterative algorithm
1
G
k
+
1
=
(
C
+
D
G
k
)
[
A
+
B
G
k
]
-
1
K
k
+
1
=
(
C
+
D
K
k
)
[
A
+
B
K
k
]
-
1
G
0
=
0
K
0
=
0
G
k
→
G
~
K
k
→
K
~
K
~
=
G
~
[
H
T
H
]
-
1
H
T
Per-step iterative algorithm
2
Per-step iterative algorithm
2
G
k
+
1
=
c
+
a
[
G
k
-
1
+
b
]
-
1
d
K
k
+
1
=
c
+
a
[
K
k
-
1
+
b
]
-
1
d
G
1
=
c
K
1
=
c
G
k
→
G
~
K
k
→
K
~
K
~
=
G
~
[
H
T
H
]
-
1
H
T
Doubling iterative algorithm
Doubling iterative algorithm
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
a
k
+
1
=
a
k
(
I
-
c
k
[
I
+
b
k
c
k
]
-
1
b
k
)
a
k
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
b
k
+
1
=
b
k
+
d
k
[
I
+
b
k
c
k
]
-
1
b
k
a
k
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
c
k
+
1
=
c
k
+
a
k
c
k
[
I
+
b
k
c
k
]
-
1
d
k
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
d
k
+
1
=
d
k
[
I
+
b
k
c
k
]
-
1
d
k
a
1
=
a
,
b
1
=
b
,
c
1
=
c
,
d
1
=
d
a
1
=
a
,
b
1
=
b
,
c
1
=
c
,
d
1
=
d
c
k
→
G
~
c
k
→
K
~
K
~
=
G
~
[
H
T
H
]
-
1
H
T
Algebraic algorithm
Algebraic algorithm
Φ
=
[
A
B
C
D
]
Φ
=
[
A
B
C
D
]
=
[
W
11
W
12
W
21
W
22
]
[
Λ
0
0
Λ
-
1
]
[
W
11
W
12
W
21
W
22
]
-
1
=
[
W
11
W
12
W
21
W
22
]
[
Λ
0
0
Λ
-
1
]
[
W
11
W
12
W
21
W
22
]
-
1
G
~
=
W
21
W
11
-
1
K
~
=
W
21
W
11
-
1
K
~
=
G
~
[
H
T
H
]
-
1
H
TIn particular, the steady state prediction error covariance can be computed via the steady state gain and is given by(72)
P
~
p
=
[
I
-
K
~
H
]
-
1
K
~
R
H
[
H
T
H
]
-
1
.Indeed, from (2), arises K
~
=
P
~
p
H
T
[
H
P
~
p
H
T
+
R
]
-
1, which leads to
(73)
K
~
(
H
P
~
p
H
T
+
R
)
=
P
~
p
H
T
⟹
K
~
H
P
~
p
H
T
+
K
~
R
=
P
~
p
H
T
⟹
P
~
p
H
T
-
K
~
H
P
~
p
H
T
=
K
~
R
⟹
(
I
-
K
~
H
)
P
~
p
H
T
=
K
~
R
⟹
P
~
p
H
T
=
[
I
-
K
~
H
]
-
1
K
~
R
⟹
P
~
p
H
T
H
=
[
I
-
K
~
H
]
-
1
K
~
R
H
.
Since rank
⁡
(
H
)
=
n, the matrix H
T
H is nonsingular [21]; thus from the last equation arises immediately the formula of the steady state prediction error covariance in (72).Also, by (3), the steady state estimation error covariance can be computed via the steady state prediction error covariance
(74)
P
~
e
=
[
I
-
K
~
H
]
P
~
p
.


## 3. Examples

In this section, two examples verify the results of Section2.Example 1.
A model of dimensionsn
=
1 and m
=
2 is assumed with parameters:
(75)
F
=
0.8
,
H
=
[
1
2
]
,
Q
=
5
,
R
=
[
0.1
0
0
0.4
]
.
In this example, we have rank
⁡
(
H
)
=
n
=
1 with m
>
n.
Using all algorithms presented in Section2.2, we computed
(76)
G
~
=
0.9902
.
Then, using (55), we computed the steady state gain
(77)
K
~
=
[
0.1980
0.3961
]
.Example 2.
A model of dimensionsm
=
n
=
2 is assumed with parameters:
(78)
F
=
[
-
0.9
0.7
-
0.3
0.1
]
,
H
=
[
1
3
2
2
]
,
Q
=
[
1
0
0
3
]
,
R
=
[
0.1
0
0
0.4
]
.
In this example, we have rank
⁡
(
H
)
=
2.
Using all algorithms presented in Section2.2, we computed
(79)
G
~
=
[
0.8382
0.0317
0.0647
0.9841
]
.
Then, using (55), we computed the steady state gain
(80)
K
~
=
[
-
0.4033
0.6207
0.4597
-
0.1975
]
.
We also computed the same steady state gain, using all algorithms presented in Section2.3, since m
=
n
=
2.


## 4. Conclusions

The Kalman filter gain arises in Kalman filter equations in linear estimation and is associated with linear systems. The gain is a matrix through which the estimation and the prediction of the state as well as the corresponding estimation and prediction error covariance matrices are computed. For time invariant and asymptotically stable systems, there exist steady state values of the estimation and prediction error covariance matrices. There exists also a steady state value of the Kalman filter gain.The steady state Kalman filter gain is usually derived via the steady state prediction error covariance by first solving the corresponding Riccati equation. In view of the importance of the Riccati equation, there exists considerable literature on its algebraic or iterative solutions, including the Chandrasekhar algorithms, which are the only iterative algorithms that provide the steady state Kalman filter gain together with the prediction error covariance.Iterative per-step and doubling algorithms as well as an algebraic algorithm for the steady state Kalman filter computation were presented. These algorithms hold under conditions concerning the system parameters. The advantage of these algorithms is the autonomous computation of the steady state Kalman filter gain. This is important if we want to compute only the steady state Kalman filter gain or to compute the parameters of the steady state Kalman filter, which are related to the steady state Kalman filter gain.



---

*Source: 417623-2014-05-04.xml*