The text of the simulation program Example

First non-demanded idea

Topic of non-demanded idea is dedicated to scientific ideas and methods that are published, tested and found very effective but on unknown reasons are not used by engineers.

Discrete Urysohn Operator

This topic is generalization of linear regression to non-linear discrete integral operator. Linear regression is simple mathematical model of some process:

xn+1 = xn*kn + xn-1*kn-1 + ... + x0*k0                   (1)

where xi are observed instantaneous values of the process and ki is set of coefficients that constitute mathematical model. Formula (1) presumes that such dependence make physical sense at least approximately. Having large set of such equations with different xi it is possible to identify coefficients ki although it is not as simple as it looks. The model (1) can still be used in case of weak non-lineartiy but becomes useless when non-linearity is significant. The construction of robust non-linear model of physical object is an art. There are many researched non-linear models that can be taken as a prototype. We consider here one of them that is very simple, effective and is generalization of linear model. That means it works in every case (1) works and provides additional functionality that equation (1) is not capable to provide. In its generic form it may scare engineers away from this site
                        (2)
and looks like mathematical abstraction. This is integral equation introduced by Russian mathematician Pavel Urysohn. It is called equation because there is unknown function y(s) inside the integral expression and mathematical task is to find this function that turns (2) into equality, provided that U is given. We replace y(s) by another function x(s), which we consider as input to some system and y(t) is the reaction on this input.
                        (3)
If variable t denotes time we have to change the equation (3) to reflect cause-and-effect connection between input and output
                        (4)
In the modern digital systems both input and output values are known for discrete time intervals and take only quantized values. Considering this we convert (4) into a discrete form
                        (5)
Since x is quantized the system is fully defined by matrix U, wich is subject to identification given long enough sequences of input and output values. Although construction of model (5) needs identification of matrix and model (1) needs only a vector, it is much more easy to build (5). This is win-win situation more effective model by less complicate identification process. The identification technique is so simple that can be implemented in real time observation system in some type of 5 to 10 elementary instructions or few lines in computer program. On unknown to me reasons this method is not used by engineers and even is not taught in universities although there is huge volume of technical information about all topics related to linear regression (1).




Pavel Urysohn

Application to identification of dynamic systems

Typically in identification problem we consider a system as a black box with observed input and output signals
In our case
input and output are known as discrete and quantized sequences xi, yi. The model represents matrix with unknown elements, that can be geometrically interpreted as set of columns.
Every fragment of input signal is plotted at the bottom of shown above 3D chart as it is shown at the right. The heights of the columns that fall into x path are added together and constitute one discrete output value y. In real-life identification problem both input and output known with certain approximation and unknown matrix is much larger (such as 100*100).

Identification of discrete Urysohn operator is not a computational problem from the course of linear algebra. We have set of equations where we know the positions of the matrix elements that are added and the result of addition but the elements is to be indentified. Before I show elementary and effective solution for this problem let us find out how this operator is related to linear regression. In case matrix U is of the first rank, it can be reduced to outer product of two vectors H * GT where H is a column and GT is row. In case all components of vector column H fall into a straight line, that means linearly dependent on each other, we have linear regression model.

Prediction

In the theory of automatic control under prediction people understand calculation of the output signal given the input signal and a model. We consider it here to resolve all questions about functionality of discrete Urysohn operator. Since it is only a numerical illustration we limit our operator to the sizes 3*4 and show matrix elements in the table below

Line #Operator
01452
10371
21130

According to our operator input sequence must take quantized values 0,1,2. In the next table we show fragment of input and computed output signals

xi2 1 0 1 2 0
yi.........10119

In the classical theory of automatic control fragments of input signals are included into integral equations as inverted backwards, which signifies cause-and-effect connection between input and output. Since our operator is non-linear we do not need this inversion, we simply presume that our operator is already recorded in a convenient way. First computed output value is 10. It is computed using sequence 2,1,0,1 when moving along the operator matrix. The row is taken according to value x, the column is taken according to position of x value in the sequence. Next values of output signal are computed in the same way.

Identification

Identification of dynamic systems is a big topic that requires a book to be addressed. For identification researcher needs recorded inputs and outputs (presumably large enough) and has to construct an operator, which is in our case matrix U. We can mention two types of identification process, which is computation in laboratory using recorded samples when the object is no longer functioning or even exists and real time identification inside a microprocessor chip, which collects information about input/output during normal functioning of the object and adjust the model in real time during short interval between reading the next data sample. In spite of second problem sounds much more complicated than the first one it is elementary. We start from arbitrary operator (all zero values, for example) and do successive correction on every step. The process is amazingly simple and computationally stable. We compute output value for available operator and distribute an error evenly between the involved elements of the operator. For example, if our initial operator contain all zeros, the computed output is 0.0. The known output is 10.0. After we distribute evenly difference between 4 elements we have an operator shown below

Line #Operator
0002.50
102.502.5
22.5000


If we continue this process for long enough and diversified enough input signal we shall reconstruct an operator for approximately known input/output signals. In case input signal is relatively short the identification may include repeated runs through the signal, that means starting from the beginning again when the end is reached.

General remarks

If we need computational program that makes identification of dynamic object with one input and output we need only few lines of code for implementation. In spite of all simplicity I never met a single engineer working in industry familiar with discrete Urysohn operator although all engineers are familiar with linear regression and can mention several techniques for estimation of coefficients of regression model. Urysohn operator is much more powerful tool for data modeling. It may significantly improve dynamic models of such objects as aircrafts and ships, where engineers try to use linear regressions or overcomplicated non-linear differential equations. Obviously, all written in this article so far is not novel. It is published and used by narrow circle of researchers leaving big masses of engineers unaware about advantages of the Urysohn operator. Application of this operator to modeling of mechanical objects is pretty simple. In case of flying aircraft we may construct a model between the thrust and aircraft speed (relatively to the air) when aircraft is flying straight on the same altitude without changing aero-configuration (flats, rudder, ailerons). In the same way we may easy to identify moving ship considering angular speed of propeller and motion relatively to the water.

The identification of mechanical objects by Urysohn operator is so simple that does not require special software for implementation. However, for those who interested I can offer my program that I wrote about 10 years ago when learning how to use MFC for windows programming. One GUI sketch of this program is shown below. You can see fragment of output process and identified operator. The program has convenient controls for monitoring data.



To obtain the program, please contact me over e-mail andrewpolar@bellsouth.net

Linearization

When learning the theory of automatic control I read somewhere a remark that nothing is linear but everything can be linearized. Discrete Urysohn operator fall under this rule. This mentioned above iterational identification is slow and may not satisfy needs of some research where it has to be done in a fraction of a second. If we stretch all elements of matrix U in a vector column

(1 0 1 4 3 1 5 7 3 2 1 0) T

and construct another vector-row of the same size holding only binary elements as follows

001 010 100 010

we can see that their inner product is the same as if input (2,1,0,1) is applied to original matrix operator. The above binary vector is constructed on a very simple rule that may not need an explanation. We can construct system of linear algebraic equations based on input signal and solve it using some regularization technique because the data matrix is expected to be sparse and poorly conditioned. The example of such program can be found under the link shown at the top. I used least square method to estimate elements of U. Since all elements of known matrix are binary the multiplication with transpose can be significantly simplified and keeping all data in the memory is not necessary. The details can be found in the program. Those who wish to use this program do not need to understand details and can use it as a function call passing experimental data and getting the operator U back as a result of computation.

Andrew Polar, April 23, 2009.