Data processing: measuring – calibrating – or testing – Measurement system in a specific environment – Electrical signal parameter measurement system
Reexamination Certificate
1997-12-17
2001-04-03
Wachsman, Hal (Department: 2857)
Data processing: measuring, calibrating, or testing
Measurement system in a specific environment
Electrical signal parameter measurement system
C702S057000, C702S183000, C700S286000
Reexamination Certificate
active
06212478
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to computer programs used to estimate values describing the state of complex systems such as commercial electrical transmission and distribution networks and the like, and in particular to a computer program that reduces the amount of time necessary for estimation of such values on current electronic computers.
BACKGROUND OF THE INVENTION
A common set of problems normally solved with the aid of an electronic digital computer are those in which measurements of a complex physical system are used to derive or estimate other values that cannot be measured directly. For example, in an electrical transmission and distribution network with known topology and electrical characteristics, the amount of power delivered to the network by some of the generating stations and certain of the line flows may be measured. From these measurements of generator power and line flows, the voltages on the network at the various sites may be derived or estimated. This in turn permits the estimation of almost any other quantity of interest, such as other unmetered flows and voltages. Measuring every flow and voltage is not practical and/or reliable.
Problems such as these may be expressed in the following matrix form
Ax=z
(1)
Where z is a set of measured values, such as power input from generators or line flows, x is a set of unknowns, such as voltages, and A is a matrix of coefficients, based for example on the network topology and electrical characteristics, and relating the currents z to the voltages x.
Equation (1) provides a set of simultaneous equations which may be solved for values of x. Typically, the number of measured values, and hence equations, will be greater than the number of unknown values. Thus some of the measurements are redundant. Further, to the extent that the measurements are inaccurate or the physical system is not well characterized, the equations will conflict with each other. Thus, the values x will be a best fit to inconsistent measurements.
The matrix equation (1) requires that the relationships between the measured values and the unknown values be linear, however in those situations where linear relationships are not present, the equation (1) may often be used by approximating the relationship with linear equations.
A number of computerized techniques are known for estimating or optimizing values of x based on values of z and A. In one method known as “orthogonal factorization”, a set of orthogonal matrices Q
1
. . . Q
n
are selected that produce the matrix A when multiplied by an upper triangular matrix R, that is:
Q
&tgr;
. . . Q
3
,Q
2
,Q
1
R=A
(2)
or
QR=A
(2′)
where Q
&tgr;
. . . Q
3
,Q
2
,Q
1
=Q (
2′)
The orthogonal matrices Q
1
through Q
&tgr;
, when factored from A, concentrate the data of matrix A into the upper right hand side of the matrix as an upper triangular matrix R. In some cases, the product of those Q matrices can be combined into a single orthogonal matrix Q. An upper triangular matrix is a matrix where all non-zero coefficients are on or above the diagonal from the northwest corner of the matrix to the southeast corner of the matrix. The upper triangular matrix R can be readily solved for values of x using the technique of back substitution as will be described below and as is well known in the art.
Thus, for example, a simple physical system may have unknown variables x
1
through x
4
, and measured variables z
1
through z
5
, having values of 1, −1, 1, −1, and 1, respectively. The properties of the physical system may be described by coefficients (in this case values of one or zero) in a matrix A of four columns and five rows as shown in equation (3) below.
[
1
1
1
1
1
1
1
1
]
[
x
1
x
2
x
3
x
4
]
=
[
1
-
1
1
-
1
1
]
(
3
)
For clarity, coefficients of zero in matrix A are omitted.
Following the normal rules for matrix multiplication, equation (3) represents the following simultaneous linear equations:
x
1
=
1
(4a)
x
2
=
-
1
(4b)
x
3
=
1
(4c)
x
4
=
-
1
(4d)
x
1
+
x
2
+
x
3
+
x
4
=
1
(4e)
Note that these equations are conflicting in that the values of x
1
through x
4
provided in the first four equations (4a)-(4d), if summed, do not equal the value of the fifth equation.
To solve the equations (4a)-(4e) for values of x (in this case, values of x that are in “least squares” best agreement with the conflicting equations (4a)-(4e)), the matrix A may be factored by a matrix Q as follows:
Q
=
[
-
0.7071
0.4082
0.2287
0.2236
-
0.4472
0
-
0.8165
0.2887
0.2236
-
0.4472
0
0
-
8.660
0.2236
-
0.4472
0
0
0
-
0.8944
-
0.4472
-
0.7071
-
0.4082
-
0.2887
-
0.2236
-
0.4472
]
(
5
)
Where Q is determined by techniques well known in the art and described generally in Philip E. Gill et al.,
The Orthogonal Factorization of a Large Sparse Matrix
, in “Sparse Matrix Computations”, edited by J. R. Bunch et al., Academic Press (1976), hereby incorporated by reference. This orthogonal factorization produces an upper triangular matrix R as follows:
R
=
[
-
1.4142
-
0.7071
-
0.7071
-
0.7071
-
1.2247
-
0.4082
-
0.4082
-
1.1547
-
0.2887
-
1.1180
]
(
6
)
where the information from matrix A has been concentrated into the upper diagonal half of the matrix R. R may be used to solve for the values of x by back substitution. From equations (1) and (2′):
QRx=z
(7)
Rx=Q′z
(8)
where Q′ is the transposition of Q which for orthogonal matrixes is equal to the inverse of Q. In this case:
w
=
Q
′
z
=
[
-
1.4142
0.8165
-
1.1547
0.8944
0.4472
]
(
9
)
Hence
:
[
-
1.4142
-
0.7071
-
0.7071
-
0.7070
-
1.2247
-
0.4082
-
0.4082
-
1.1547
-
0.2887
-
1.1180
]
[
x
1
x
2
x
3
x
4
]
=
[
-
1.4142
0.8165
-
1.1547
0.8944
0.4472
]
(
10
)
Following the rules of matrix multiplication, the lower most row of matrix R provides the expression 1.1180x
4
=0.8944. Thus x
4
may be readily solved and substituted into an equation produced by the next to the last row of matrix R and so forth for all the equations represented by expression (10).
In this example, the following values of x
1
through x
4
are produced:
x
1
=1.2
x
2
=−0.8
x
3
=1.2
x
4
=−0.8
Note that these values differ from those indicated by equations (4a)-(4d) because they are a least squares approximation satisfying all of equations (4a)-(4e).
The process of solving for the values of x
1
-x
4
by back substitution of the matrix R requires ten multiplications because there are ten non-zero coefficients in R. In some current electronic computers, multiplications are a time consuming operation especially if high precision is required. Accordingly it is desirable to reduce the number of multiplication operations necessary to solve these types of problems.
SUMMARY OF THE INVENTION
The present invention adds rows and columns to the coefficient matrix A prior to solving for the unknown values x. Although this makes the matrix A larger, for many matrices representing complex physical systems, the larger matrix A ultimately requires fewer multiplications by the electronic computer and hence is significantly faster.
Specifically, the invention provides a program for controlling an electronic computer communicating with a computer memory. The program instructs the computer to store in the computer memory a series of measured values of a physical system as a multi-row measurement array z. The program also instructs the computer to store in the computer memory a series of coefficients, as a coefficient matrix A having multiple rows and columns, relating the measured values z to a plurality of unmeasured values x such that Ax=z. The rows of the coefficient matrix A are then scanned for rows having a greater than a predetermined minimum number of non-zero coefficients. These rows are bro
Quarles & Brady
Wachsman Hal
Wisconsin Alumni Research Foundation
LandOfFree
Computer program for rapid estimation of system values from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer program for rapid estimation of system values from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer program for rapid estimation of system values from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2463552