Fibonacci sequence, golden section, Kalman

lter and optimal control

A. Benavoli
1
, L. Chisci
2
and A. Farina
3
1
Istituto Dalle Molle di Studi sullIntelligenza Articiale,
Manno, Switzerland, email:benavoli@gmail.com
2
DSI, Universit`a di Firenze, Firenze, Italy
e-mail: chisci@dsi.uni.it
3
Engineering Division, SELEX - Sistemi Integrati S.p.A., Rome, Italy
e-mail: afarina@selex-si.com
Abstract
A connection between the Kalman lter and the Fibonacci sequence is developed.
More precisely it is shown that, for a scalar random walk system in which the two
noise sources (process and measurement noise) have equal variance, the Kalman lters
estimate turns out to be a convex linear combination of the a priori estimate and of
the measurements with coecients suitably related to the Fibonacci numbers. It is
1
also shown how, in this case, the steady-state Kalman gain as well as the predicted
and ltered covariances are related to the golden ratio =

5+1
2
. Furthermore, it is
shown that, for a generic scalar system, there exist values of its key parameters (i.e.
system dynamics and ratio of process-to-measurement noise variances) for which the
previous connection is preserved. Finally, by exploiting the duality principle between
control and estimation, similar connections with the linear quadratic control problem
are outlined.
Keywords: Kalman lter; Linear Quadratic Control; golden section/ratio; Fibonacci
sequence; random walk.
1 Introduction
The Fibonacci numbers and the golden section are ubiquitous in nature and art as well as
in science and engineering. Is there any link between the Nautilus shell, the layout of the
sunowers seeds and the proportions of the Botticellis Venus ? The answer to this question is
the irrational number = 1.618033988749895..., known as golden ratio [1], which is perhaps
the rst irrational number ever discovered. The number has interesting properties. Its
square is equal to +1, its reciprocal (called golden section) is equal to 1 and, further, is
intimately connected to the sequence of Fibonacci numbers {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . }.
The Fibonacci sequence, starting from 0 and 1, is dened by recurrence by taking each
subsequent number as the sum of the two previous ones. It can easily be checked that the
ratio between a number of the sequence and the previous one converges to the golden ratio.
The goal of this paper is to show the existence of a connection between the Fibonacci
2
sequence and the golden section/ratio on one side and the Kalman lter on the other side.
By applying the duality principle between estimation and control, a connection with the
linear quadratic control problem is also derived. Before proceeding, it should be pointed out
that this connection must be regarded as a mere mathematical curiosity which, however,
makes the history of even more fascinating.
The rest of the paper is organized as follows. Section 2 reviews some historical notes;
section 3 displays the connection between the Fibonacci sequence and the Kalman lter and,
nally, section 4 lists the conclusions.
2 Historical notes
2.1 Golden Section
The rst mathematical denition of Golden Ratio traces back to the famous Greek mathe-
matician Euclid who, in the 3d century B.C., introduced it [2] to solve a geometrical problem
called the problem of division of a line segment in extreme and mean ratio. The essence of
the problem is the following. A line segment AB must be divided with a point C into two
parts so that the ratio between the longer part CB and the shorter one AC is equal to the
ratio between the whole line segment AB and the longer part CB, i.e.:
AB
CB
=
CB
AC
(2.1)
3
Exploiting the relationship AB = AC + CB, equation (2.1) can be written in the following
form:
x =
CB
AC
=
AB
CB
=
AC + CB
CB
= 1 +
AC
CB
= 1 +
1
x
(2.2)
Hence, the equation to calculate the ratio x is:
x
2
x 1 = 0 (2.3)
The positive root of the equation (2.3) is the solution of the problem of division of a line
segment in extreme and mean ratio. This solution is just the golden ratio:
=
1 +

5
2
1.618 (2.4)
The discovery of the number , however, cannot be attributed to Euclid but probably to
Pythagoras or to Hippasus of Metapontum (a disciple of Pythagoras) in the 5th century B.C.
[1]. In fact, the ancient philosopher Pythagoras chose the pentagram (a regular star with
5 vertices) as the symbol of the secret fraternity of which he was both leader and founder
and the construction of a pentagram is based on the golden ratio. The pentagram can be
seen as a geometric shape consisting of 5 straight lines arranged as a star with 5 points. The
intersection of the lines naturally divides each line into 3 parts. The smaller part (which
forms the pentagon inside the star) is proportional to the longer parts (which form the points
of the star) by a ratio of 1 : . For the connection between Pythagoreans and the pentagram
it is reasonable to believe that the Pythagoreans were the rst to discover and so the rst
to discover the existence of irrational numbers. The mathematical history of went on and
4
today many interesting things about this number are known. A list of the mathematical
properties of is given below:
can be expressed as a continuous fraction with only 1;
= 1 +
1
1 +
1
1+
1
1+
1
1+...
can be expressed as a continuous square root;
=

1 +
_
1 +
_
1 +

1 + . . .
Any power of is equal to the sum of the two immediately preceding powers:

n
=
n1
+
n2
.
It is worth pointing out that has many other mathematical and geometrical properties,
but the most interesting is certainly the connection with the Fibonacci sequence.
2.2 Leonardo Pisano Fibonacci
Leonardo Pisano (1170-1250), better known by his nickname Fibonacci, was born in Italy
but was educated in North Africa where his father, Guilielmo, held a diplomatic post [3]. His
fathers job was to represent the merchants of the Republic of Pisa who were trading in Bugia,
later called Bougie and now called Bejaia (Algeria). Fibonacci was taught mathematics in
5
Figure 1: Leonardo Pisano Fibonacci
Bugia and travelled widely with his father and recognised the enormous advantages of the
mathematical systems used in the countries they visited.
Fibonacci ended his travels around the year 1200 and at that time he returned to Pisa
[3]. There he wrote a number of important texts which played an important role in reviving
ancient mathematical skills and he made signicant contributions of his own.
The most important book of Fibonacci, Liber abaci (the book of calculations) [4], was
published in 1202 after Fibonaccis return to Italy. The book was based on the arithmetic
and algebra that Fibonacci had accumulated during his travels. The book, which went on
to be widely copied and imitated, introduced the Hindu-Arabic place-valued decimal system
and the use of Arabic numerals into Europe [3].
The book begins with the following premise: The nine Indian gures
1
are: 9, 8, 7, 6, 5, 4, 3, 2, 1.
With these gures, and with the sign 0... any number may be written, as is demonstrated
below.
Although Liber Abaci is mainly a book about the use of Arab numerals, it contains also
1
Arabic numerals
6
the solution of important problems. In fact, the second section of Liber abaci contains a
large collection of problems aimed at merchants. They relate to the price of goods, how
to calculate prot on transactions, how to convert between the various currencies in use in
Mediterranean countries, and problems which had originated in China [3]. A problem in
the third section of Liber abaci led to the introduction of the Fibonacci numbers and the
Fibonacci sequence for which Fibonacci is best remembered today: A certain man puts a
pair of rabbits in a place surrounded on all sides by a wall. How many pairs of rabbits can
be produced from that pair in a year if it is supposed that every month each pair begets a
new pair which from the second month on becomes productive? The resulting sequence, in
which each number is the sum of the two preceding numbers, is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . .
The Fibonacci sequence was forgotten until the famous astronomer Kepler rediscovered
the sequence in the 1611 A.D. Further, he made a remarkable discovery about the ratios
of consecutive terms of the Fibonacci sequence. He guessed that these ratios approximate
what he calls the divine proportion and what is now called the golden ratio. That is he saw
that the ratios 1/1, 2/1, 3/2, 5/3, . . . rapidly approach = 1.618 . . . .
The Fibonacci sequence has proved extremely fruitful and appears in many dierent areas
of mathematics and science. Some interesting mathematical properties are given below.
The sequence of nal digits in Fibonacci numbers repeats in cycles of 60.
The last two digits repeat in cycles of 300, the last three in 1500, the last four in
15, 000, etc.
Let f
i
be the i-th element of the Fibonacci sequence then:
1. f
n
divides f
nm
for any positive integers n and m;
7
Figure 2: Sunower
2. gcd(f
n
, f
m
) = f
gcd(m,n)
, where gcd is the greatest common divisor;
3. f
1
+ f
3
+ f
5
+ + f
2n1
= f
2n
Fibonacci numbers seem to appear also in nature. For example, many types of owers
have a Fibonacci number of petals: daisies tend to have 34 or 55 petals, sunowers have 89 or
144 [12]. Similarly, the numbers of rings on the trunks of palm trees, the scales on the surface
of a pineapple and the genealogy of the male bee all follow a sequence of Fibonacci numbers.
The arrangement of plant leaves, or phyllotaxis, unfolds to the same pattern because this
seems to be an optimal solution in terms of the spacing of the leaves or the amount of light
that can reach them.
The history of the Fibonacci numbers and the golden ratio is also related to art and
architecture. The golden section seems to appear in many of the proportions of famous
ancient buildings, as the Parthenon in Athens or Palazzo della Signoria in Florence [13], Also
the proportions of famous paintings seem to be designed according to the golden section, for
examples the Botticellis Venus in the painting La Primavera or the Vergine delle Rocce of
Leonardo Da Vinci. However, there is no original documentary evidence that these buildings
8
and paintings were deliberately designed using the golden section.
3 Fibonacci sequence, Kalman lter and optimal con-
trol
A Fibonacci characterization of the best linear unbiased estimator has been presented in [5] by
following a non recursive least-squares approach. Hereafter a more complete characterization
is provided by following a recursive Riccati equation approach, which is the fundamental core
of the Kalman algorithm and Linear Quadratic (LQ) control.
3.1 Kalman Filter and Fibonacci sequence
Consider the scalar stochastic dynamical system
_

_
x(t + 1) = x(t) + w(t)
y(t) = x(t) + v(t)
(3.1)
with process noise w(t) and measurement noise v(t) having the same variance
2
. Let us
hereafter denote by p(t|t 1) and p(t|t) the a priori and, respectively, a posteriori state
variance normalized by the common noise variance
2
.
For the system (1), the Kalman lter propagates the estimate according to [6]
x(t) = x(t 1) + k(t) [y(t) x(t 1)] = [1 k(t)] x(t 1) + k(t)y(t) (3.2)
9
where the Kalman gain is given by
k(t) =
p(t|t 1)
1 + p(t|t 1)
. (3.3)
Further, the state covariance is updated by:
p(t|t) = p(t|t 1)
p
2
(t|t 1)
1 + p(t|t 1)
=
p(t|t 1)
1 + p(t|t 1)
= k(t)
p(t + 1|t) = 1 + p(t|t) = 1 +
p(t|t 1)
1 + p(t|t 1)
(3.4)
Let us now introduce the Fibonacci sequence:
_

_
f
0
= 0
f
1
= 1
f
k
= f
k1
+ f
k2
k 2
(3.5)
It is easy to see that, given the prior state variance p(1|0) = p
0
, from (3.3) and (3.4) one
gets
k(t) = p(t|t) =
f
2t2
+ f
2t1
p
0
f
2t1
+ f
2t
p
0
t 1 (3.6)
In fact,
k(1) = p(1|1) =
p
0
1 + p
0
=
f
0
+ f
1
p
0
f
1
+ f
2
p
0
10
Next, by induction, if (3.6) holds then
k(t + 1) =
p(t + 1|t)
1 + p(t + 1|t)
=
1 + p(t|t)
2 + p(t|t)
=
1 + k(t)
2 + k(t)
=
f
2t1
+ f
2t2
+ (f
2t1
+ f
2t
) p
0
2f
2t1
+ f
2t2
+ (2f
2t
+ f
2t1
) p
0
=
f
2t
+ f
2t+1
p
0
f
2t+1
+ f
2t+2
p
0
i.e. (3.6) holds also for t + 1 and hence for all t 1. It is well known that the Fibonacci
sequence satises the limit properties:
lim
i
f
i1
f
i
= =

5 1
2
0.618
lim
i
f
i+1
f
i
= =
1

= 1 + =

5 + 1
2
1.618
(3.7)
where and are the so called golden section and, respectively, golden ratio. Using the
properties (3.7), it can be checked that, irrespective of the initial condition p
0
,
k

= lim
t
k(t) = lim
t
p(t|t) =
p

= lim
t
p(t + 1|t) = 1 + =
(3.8)
i.e. the Kalman gain and the normalized a posteriori state variance converge to the golden
section while the normalized a priori state variance converges to the golden ratio . The
same result could be obtained by nding the positive solution of the algebraic Riccati equation
p = 1 +
p
1 + p
= p
2
p 1 = 0 =p

5 + 1
2

= = k

5 1
2

=
It can be checked that, propagating (3.2) forward in time, one gets the following expres-
11
sion for the estimate x(t) in terms of the initial estimate x(0) and the measurements
{y(1), y(2), . . . , y(t)}:
x(t) = w
0
(t) x(0) +
t

i=1
w
i
(t)y(i) (3.9)
where the weights w
i
(t) of the data fusion at time t are given by
w
0
(t) =
1
f
2t1
+ f
2t
p
0
w
i
(t) =
f
2i2
+ f
2i1
p
0
f
2t1
+ f
2t
p
0
i = 1, 2, . . . , t
(3.10)
In fact, (3.10) can be proved by induction. It holds true for t = 1 since
x(1) = [1 k(1)] x(0) + k(1)y(1) =
1
f
1
+ f
2
p
0
x(0) +
f
0
+ f
1
p
0
f
1
+ f
2
p
0
y(1)
Further, if (3.9) holds then
x(t + 1) = [1 k(t + 1)] x(t) + k(t + 1)y(t + 1)
= [1 k(t + 1)] w
0
(t) x(0) +
t

i=1
[1 k(t + 1)] w
i
(t)y(i) + k(t + 1)y(t + 1)
= w
0
(t + 1) x(0) +
t+1

i=1
w
i
(t + 1)y(i)
since
w
i
(t + 1) = [1 k(t + 1)] w
i
(t) i = 0, 1, . . . , t
w
t+1
(t + 1) = k(t + 1)
In the case in which no a priori information on the initial state is available, i.e. p
0
, it
12
turns out from (3.10) that w
0
(t) 0 and w
i
(t) f
2i1
/f
2t
; hence
for p
0
: x(t)
t

i=1
f
2i1
f
2t
y(i) (3.11)
wherein the coecients of the data fusion are ratios of Fibonacci numbers.
Summarizing the above connection between Kalman ltering, Fibonacci sequence and
golden section/ratio, related to the system (3.1) with process noise covariance equal to the
measurement noise covariance, the following facts hold.
1. The steady-state Kalman lter turns out to be
x(t) = (1 ) x(t 1) + y(t)
where

=
1
2
_
5 1
_
0.618 is the golden section, and the associated steady-state
ltered covariance is times the noise covariance.
2. The steady-state predicted covariance converges to times the noise covariance, where
=
1

=
1
2
_
5 + 1
_
1.618 is the golden ratio.
3. In general, the current estimate x(t) is related to the initial estimate x(0), to the
measurements {y(1), y(2), . . . , y(t)} and to the initial covariance p
0
by the expression
x(t) =
1
f
2t1
+ f
2t
p
0
x(0) +
t

i=1
f
2i2
+ f
2i1
p
0
f
2t1
+ f
2t
p
0
y(i)
which involves the Fibonacci sequence {f
k
}.
4. Provided that the initial covariance is large, i.e. p
0
, the current estimate x(t)
13
is a combination of all measurements y(i) with coecients f
2i1
/f
2t
equal to ratios of
Fibonacci numbers.
The previous results can be extended to a generic rst order system:
_

_
x(t + 1) = a x(t) + w(t)
y(t) = x(t) + v(t)
(3.12)
where the process noise w(t) and measurement noise v(t) have generic variances q and,
respectively, r. The objective is to investigate for which values of the parameters a, q, r the
steady-state Kalman lter correction (measurement update)
x(t|t) = (1 ) x(t|t 1) + y(t)
has gain equal to either the golden section or its complement 1 . This amounts
to weighting the predicted estimate and the current measurement according to a golden
section-like data fusion. Using the gain formula = p(r + p)
1
and the Riccati equation
p
2
+
_
r ra
2
q
_
p qr = 0
it is a straightforward exercise to show what follows.
1. For the variance ratio r/q > , or equivalently q/r < , there exist two symmetric
values
a =

(1 + )
_
1
1

q
r
_
(3.13)
14
such that the resulting correction gain is = 1 and, hence, the estimate correction
is
x(t|t) = x(t|t 1) + (1 ) y(t).
2. For the variance ratio r/q > , or equivalently q/r < , there exist two symmetric
values
a =

(1 + )
_
1
1

q
r
_
(3.14)
such that the resulting correction gain is = and, hence, the estimate correction is
x(t|t) = (1 ) x(t|t 1) + y(t).
Notice that the case so far considered of equal variances, i.e. r/q = 1 > , corresponds to
the latter situation. From (3.14) it turns out that the golden section update is obtained only
for the two values a = 1, of which a = 1 corresponds to the studied random walk system.
Further notice that for r/q < , i.e. for a suciently small variance of the measurement noise
compared to the variance of the process noise, a golden section data fusion is not possible
for any value of the parameter a.
3.2 Linear Quadratic Control
It is well known that the Linear Quadratic (LQ) control and the Kalman lter are dual
mathematical problems. This result was rst described in [6]. Therefore, obviously, the
previous results hold also for the LQ control problem when the dual systems of (3.1) or
(3.12) are considered. For instance, the dual of the estimation problem given in section 3.1
15
can be formulated as follows. Given the dynamical system
x(t + 1) = x(t) + u(t)
(3.15)
nd the admissible control strategy {u(t) : 0 t < N}, which drives the initial state x(0)
to the nal state x(N), minimizing the following quadratic loss function:
J
N
= q
0
x
2
(N) +
N1

t=0

2
(x
2
(t) + u
2
(t)) (3.16)
Notice that, in the dual problem, the parameters q
0
> 0 and
2
play the same role as p
0
and,
respectively,
2
dened in section 3.1. An admissible control strategy is such that u(t) is a
function of the information available at time instant t only. Assuming that the state x(t) is
fully known at time instant t and that the control strategy u(t) is a function of x(t), the loss
function (3.16) is then minimized by the control strategy
u(t) = g(t)x(t) t = 0, 1, . . . , N 1 (3.17)
where g(t) is equal to k(N t) given in (3.3)-(3.6) on condition that p
0
and
2
are replaced
with q
0
and, respectively,
2
. Therefore, also in this case, as t the gain g(N t) = k(t)
converges to the golden section .
A more general case of linear quadratic control is when the state x(t) is not available for the
16
computation of u(t), and instead corrupted measurements of the state are available:
_

_
x(t + 1) = x(t) + u(t) + w(t)
y(t) = x(t) + v(t)
(3.18)
where the noises w(t) and v(t) are the same as in (3.1). This is the so called Linear Quadratic
Gaussian (LQG) control problem [10]. The objective is to minimize the average quadratic
loss function:
J
N
= E
_
q
0
x
2
(N) +
N1

t=0

2
(x
2
(t) + u
2
(t))
_
(3.19)
It is well-known that, in this case, the loss function (3.19) is minimized by the following
control strategy
u(t) = g(t) x(t) (3.20)
where the estimate x(t) is given by the Kalman lter (3.2). The LQG control problem has
the property that estimation and control are separated problems. Because of the separation
principle of the LQG control, the previous connection between the Fibonacci sequence and
both the Kalman lter and Linear Quadratic control carries over also to this case. In
particular, both the gains k and g converge to the golden section = (

5 1)/2. Similar
results can obviously be obtained for the generic scalar system given in (3.12) by exploiting,
also in this case, the duality principle.
17
4 Conclusions
The Fibonacci sequence and the golden ratio exhibit interesting mathematical properties
which, in turn, make them appear in nature (e.g. the golden spiral built according to the
golden ratio rules the growing patterns of shells, owers [12], hurricanes and galaxies), have
several uses in art and music (e.g. golden proportions in buildings [13], human gures in
paintings and music compositions) as well as have many successful applications in engineering
(e.g. in signal processing [7], [14]-[18], in image processing [8], in computer science [9], in
optimization [11]). This paper has explored a further connection with two of the most
widely used techniques in engineering, i.e. the best linear minimum mean squared error state
estimator better known as Kalman lter and the linear quadratic controller. It has been
shown that for a scalar random walk system with the two noise sources having the same
power, the recursive and steady-state Kalman lters are fully governed by Fibonacci and,
respectively, golden numbers. Furthermore, it has been shown that, for a generic scalar
system, there exists a relationship between the system dynamics and the ratio of process-to-
measurement noise variances for which the connection between the Fibonacci sequence and
the Kalman lter is preserved. Finally, by exploiting the duality principle between control
and estimation, a similar connection between the Fibonacci numbers and the linear quadratic
controller has been outlined.
5 Acknowledgments
The authors wish to thank Professor Anil Arya of the Ohio State University, Professor
Antonio De Maio of the Universit`a di Napoli Federico II, Dr. Peter J. Costa of the Cytyc
18
Corporation, Mr. F. Castella of JHU-APL, Professor M. Barkat of the American University
of Sharjah and the anonymous reviewers for constructive suggestions.
References
[1] M. Livio. The Golden Ratio, Broadway Books, 2002.
[2] T.L. Heath. Euclids Elements, Green Lion Press, Santa Fe, 2002.
[3] J. OConnor, E.F. Robertson. Fibonacci, The MacTutor History of Mathematics
Archive, http://www-history.mcs.st-andrews.ac.uk/history/.
[4] L.E. Sigler. Fibonaccis Liber Abaci, Springer, New York, 2002.
[5] A. Arya, J. Fellingham, D. Schroeder, J. Glover. A Fibonacci characterization of a BLU
estimator, submitted to Fibonacci Quarterly.
[6] R.E. Kalman. A new approach to linear ltering and prediction problems, Journal of
Basic Engineering, Trans. ASME, Series D, vol. 82, pp. 35-45, 1960.
[7] J.C. Belore, G. Rekaya, E. Viterbo. The Golden Code: A 2 x 2 Full-Rate SpaceTime
Code With Nonvanishing Determinants, IEEE Trans. on Information Theory, vol 51,
pp. 1432-1436, 2005.
[8] C. He, YF. Zheng, S. Ahalt. Object Tracking Using the Gabor Wavelet Transform and
the Golden Section Algorithm, IEEE Trans. on Multimedia, vol. 4, pp.528-538, 2002.
19
[9] N. Lopez, M. N unez, I. Rodrguez, F. Rubio. Introducing the Golden Section to Com-
puter Science, Proc. of the First IEEE International Conference on Cognitive Informat-
ics (ICCI02), 2002.
[10] M. Athans. The role and use of the stochastic linear-quadratic Gaussian problem in
control system design. IEEE Trans. on Automatic Control, vol. AC-16, pp. 529-552,
1971.
[11] T. Fine. Optimum search for the location of the maximum of a unimodal function, IEEE
Trans. on Information Theory, vol 12, pp. 103-111, 1996.
[12] J.N. Ridley. Packing eciency in sunower heads, Mathematical Biosciences, vol. 58,
pp 129-139, Elsevier North Holland, 1982.
[13] M.T. Bartoli. The Sequence of Fibonacci and the Palazzo della Signoria in Flo-
rence, pp. 31-42, in Nexus V: Architecture and Mathematics, ed. Kim Williams
and Francisco Delgado Cepeda, Fucecchio (Florence): Kim Williams Books, 2004.
http://www.nexusjournal.com/conferences/N2004-Bartoli.html.
[14] R. Ward. On Robustness Properties of Beta Encoders and Golden Ratio Encoders,
IEEE Transactions on Information Theory, pp. 4324-4334, 2008.
[15] V.S. Dimitrov, T.V. Cosklev, B. Bonevsky. Number theoretic transforms over the golden
section quadratic eld, IEEE Transactions on Signal Processing, vol. 43, pp. 1790-1797,
1995.
20
[16] K. Egiazarian, J. Astola. Generalized Fibonacci cubes and trees for DSP applications,
Circuits and Systems, 1996. ISCAS 96., Connecting the World, 1996 IEEE Interna-
tional Symposium on, vol. 2, pp. 445-448, 12-15 May 1996.
[17] M. S. Aslan, A. Saranli, B. Baykal. Optimal tracker-aware radar detector threshold
adaptation: A closed-form solution, 11th International Conference on Information Fu-
sion, pp. 1-8, July, 2008.
[18] F. Hill. Gentle diversions: PhiA precious jewel, IEEE Communications Magazine, vol.
16 pp. 35-37, 1978.
21