Analog computing implementing arbitrary non-linear functions using Chebyshev-polynomial-interpolation schemes and methods of use

Abstract

The inventive disclosures described herein pertain to an improved physical analog computer that features the ability to evaluate arbitrary non-linear functions using an interpolation method based on Chebyshev polynomials. What has been developed is an improved method for non-linear-function generation in hybrid computing that relies on Chebyshev interpolation. The method requires an initial computation of the interpolation coefficients, which is to be carried out in the digital domain. These coefficients, along with the domain of definition of the non-linear function to be generated, are used during the programming of the analog domain to set multiplier and summer elements.

Claims

1. An improved physical electronic hybrid computer, comprising at least one non-linear-function generator, wherein with respect to a non-linear function of interest, and with respect to a desired level of accuracy, said at computer is adapted to perform the following steps: with respect to Chebyschev polynomial interpolation, selecting a degree of interpolation; digitally calculating interpolation coefficients for the function of interest to the selected degree of interpolation, thereby giving rise to an interpolant; carrying out by means of digital calculation a comparison between the interpolant and the function of interest, by means of an error metric, arriving at an error value; if the error value is consistent with the desired level of accuracy, then loading the interpolation coefficients into the function generator, and carrying out analog computation in which analog values are received as inputs to the function generator and analog values are yielded as outputs from the function generator; or if the error value is inconsistent with the desired level of accuracy, then selecting a higher degree of interpolation and repeating the steps set forth above.

2. The improved physical electronic hybrid computer of claim 1 wherein the error metric is a root-means-squared measure.

3. The improved physical electronic hybrid computer of claim 1, wherein said non-linear function of interest is selected from the group consisting of sine, cosine, logarithm and exponential.

4. A method for use with an improved physical electronic hybrid computer, the hybrid computer comprising at least one non-linear-function generator, the method carried out with respect to a non-linear function of interest, and with respect to a desired level of accuracy, the method comprising the steps of: with respect to Chebyschev polynomial interpolation, selecting a degree of interpolation; digitally calculating interpolation coefficients for the function of interest to the selected degree of interpolation, thereby giving rise to an interpolant; carrying out by means of digital calculation a comparison between the interpolant and the function of interest, by means of an error metric, arriving at an error value; responsive to the error value being consistent with the desired level of accuracy, loading the interpolation coefficients into the function generator, and carrying out analog computation in which analog values are received as inputs to the function generator and analog values are yielded as outputs from the function generator.

5. A method for use with an improved physical electronic hybrid computer, the hybrid computer comprising at least one non-linear-function generator, the method carried out with respect to a non-linear function of interest, and with respect to a desired level of accuracy, the method comprising the steps of: with respect to Chebyschev polynomial interpolation, selecting a first degree of interpolation; digitally calculating interpolation coefficients for the function of interest to the first degree of interpolation, thereby giving rise to an interpolant; carrying out by means of digital calculation a comparison between the interpolant and the function of interest, by means of an error metric, arriving at an error value; responsive to the error value not being consistent with the desired level of accuracy by selecting a second degree of interpolation, the second degree being higher than the first degree, digitally calculating interpolation coefficients for the function of interest to the second degree of interpolation, thereby giving rise to the interpolant; carrying out by means of digital calculation a comparison between the interpolant and the function of interest, by means of an error metric, arriving at an error value; responsive to the error value being consistent with the desired level of accuracy, loading the interpolation coefficients into the function generator, and carrying out analog computation in which analog values are received as inputs to the function generator and analog values are yielded as outputs from the function generator.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 depicts one embodiment of a Chebyshev interpolation example. The graph shows three curvesthe original function that is being approximated by the function generator (interpolator), an interpolation with order M=4, and an interpolation with order M=10. (The original function, assuming the horizontal axis to be the variable u, is cos(u).sup.3e.sup.0.2u.) The curve showing the original function and the curve showing the interpolation with order M=10 are so close together that the two curves almost cannot be distinguished in the figure. Said differently, what may be seen is that the M=4 interpolation is fairly close but the M=10 interpolation is extremely close when compared with the original function.

(2) FIG. 2 depicts one embodiment of a Chebyshev interpolation error. The error plot is for the example function plotted in FIG. 1 and the interpolation is of the order M=10. The error is positive when the interpolant is larger than the interpolated function.

(3) FIG. 3 depicts one embodiment of a simplified diagram of a Chebyshev-based non-linear function generator. The input is the value u, and the output is the value of the interpolant I(u). The first stage is a scaling stage that maps the value u to the [1, 1] interval. The second stage is the non-linear-function generator itself.

(4) FIG. 4 depicts one embodiment of the implementation of a non-linear-function generator. The implementation is based on Equation 10, takes as input the value T.sub.0(x)=1 and T.sub.1(x)=x (so these values are not real inputs), and produces the output (x)=I(u).

(5) FIG. 5 depicts one embodiment of a Chebyshev-polynomial-evaluator diagram. The Chebyshev-polynomial evaluator is the implementation of the recurrence relationship given in Equation 4. The Chebyshev-polynomial evaluator takes as inputs the values T.sub.n1(x), T.sub.n(x), and x, and produces as outputs the values T.sub.n(x) and T.sub.n+1(x). The value x is also part of the outputs so that these evaluators can easily be chained.

DETAILED DESCRIPTION

I. Overview

(6) The inventive disclosures described herein pertain to an improved physical analog computer that features the ability to evaluate arbitrary non-linear functions using an interpolation method based on Chebyshev polynomials. What has been developed is an improved method for non-linear-function generation in hybrid computing that relies on Chebyshev interpolation. The method requires an initial computation of the interpolation coefficients, which is to be carried out in the digital domain. These coefficients, along with the domain of definition of the non-linear function to be generated, are used during the programming of the analog domain to set adder elements and multipliers elements.

(7) Saying this in a different way, the sequence of steps includes:

(8) Identify a function that it is desired to generate in the analog computer;

(9) Define the domain of the function for purposes of the application;

(10) Decide how accurate the function generator needs to be for a particular application;

(11) Work out the order (here, the value of M) required to arrive at the desired level of accuracy;

(12) Arrive at interpolation coefficients by means of digital computation;

(13) In the function generator of the analog computer, set up multipliers and summers and coefficient values to bring about the function generator result;

(14) And after all of this has been done, carry out an analog computation making use of the function generator resulting from the steps just mentioned.

II. Terminology

(15) The terms and phrases as indicated in quotes ( ) in this Section are intended to have the meaning ascribed to them in this Terminology Section applied to them throughout this document, including the claims, unless clearly indicated otherwise in context. Further, as applicable, the stated definitions are to apply, regardless of the word or phrase's case, to the singular and plural variations of the defined word or phrase.

(16) The term or, as used in this specification, drawings, and any appended claims, is not meant to be exclusive; rather, the term is inclusive, meaning either or both.

(17) References in the specification to one embodiment, an embodiment, a preferred embodiment, an alternative embodiment, a variation, one variation, and similar phrases mean that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least an embodiment of the invention. The appearances of the phrase in one embodiment and/or in one variation and similar phrases in various places in the specification are not necessarily all meant to refer to the same embodiment.

(18) The term analog computer, as used in this specification, drawings, and any appended claims, refers to a type of computer that uses the continuously changeable aspects of physical phenomena such as electrical, mechanical, or hydraulic quantities to model a problem being solved. In contrast, digital computers represent varying quantities symbolically, as their numerical values change. Because an analog computer does not use discrete values, but rather uses continuous values, processes cannot necessarily be reliably repeated with exact equivalence. However, unlike digital-signal processing in digital computers, analog computers do not suffer from the discrete error caused by quantization noise. Analog computers are subject to signal errors/perturbations from induced electronic noise. Analog computers and/or hybrid analog-digital computers (hybrid computers) are often used in scientific and industrial applications to perform control and protective functions. For the purposes of the disclosures contained herein, all references to analog computers are intended to also encompass hybrid computers.

III. An Improved Analog Computer Using Interpolation of Chebyshev Polynomials to Evaluate Non-Linear Functions

(19) This Section III is directed generally to an improved analog computer that features the ability to evaluate arbitrary non-linear functions in real-world applications using an interpolation method based on Chebyshev polynomials in real-world applications. Refer to FIGS. 1 through 5.

(20) A. Overview of Mathematical Framework for Chebyshev Interpolation

1. Chebyshev Polynomials

(21) Chebyshev polynomials of the first kind can be written as:
T.sub.n(x)=cos(n arccos(x))(Equation 1)

(22) Where:

(23) X is a real variable in the range [1, 1]; and

(24) n is a positive integer (n=0, 1, 2, . . . ) indexing the polynomials (there is an infinite amount of them).

(25) These polynomials are referred to as the Chebyshev polynomials hereinafter.

(26) The zeros of the Chebyshev polynomials are of particular interest for interpolation. A given Chebyshev polynomial, T.sub.n, has n zeros denoted x.sub.k.sup.0 and given by:

(27) $\begin{array}{cc}{x}_k^0=\cos \left(\frac{2k+1}{2n}\right)& \left(\mathrm{Equation}2\right)\end{array}$

(28) Where:

(29) k=0, 1, . . . , n=1.

(30) Therefore, by definition:
T.sub.nx.sub.k.sup.0=0(Equation 3)

(31) Hereinafter, the values x.sub.k.sup.0 will be referred to as the Chebyshev nodes. An interesting property of the Chebyshev polynomials is that they can be related through the following three-term recurrence relation:
T.sub.n+1(x)=2T.sub.n(x)T.sub.n1(x)(Equation 4)

(32) for any integer n1, and

(33) with the initial values T.sub.0(x)=1 and T.sub.1(x)=x.

(34) Finally, the discrete form of the orthogonality relation between Chebyshev polynomials, without further detail is given by:

(35) $\begin{array}{cc}\underset{i=0}{\overset{i=n}{.Math.}}{T}_p\left(x_i^0\right)T_q\left(x_i^0\right)=K_p{}_{\mathrm{pq}}& \left(\mathrm{Equation}5\right)\end{array}$

(36) Where:

(37) n is a strictly positive integer;

(38) p and q are positive integers such that pn and qn;

(39) x.sub.i.sup.o are the zeros of the Chebyshev polynomial T.sub.n+1(x) as defined in Equation 2, above.

(40) In this expression, K.sub.o=(n+1) and K.sub.p=(n+1)/2.

(41) The .sub.pq refers to the so-called Kronecker delta defined as being zero except when p=q when it equals 1.

(42) This result shows that Chebyshev polynomials are an orthogonal basis on the interval [1,1], which makes it possible to project an arbitrary function onto them.

2. Chebyshev Interpolation

(43) Consider an arbitrary real function f(u) defined in the interval [a,b]. The goal of an interpolation scheme is to derive a function I(u) that approximates the function f(u) over the interval [a,b]. The quality of approximation can be measured in various ways and is discussed later in this disclosure.

(44) The various results for the Chebyshev interpolation strategy are developed and later leveraged for non-linear functions generation in an improved analog computer.

(45) a. Range Transformation

(46) The Chebyshev polynomials are defined in the [1,1] interval, but the function to be interpolated is defined in an arbitrary [a,b] interval. A linear transformation of variables is now defined that makes it possible to map these two intervals. The variable u is defined in [a,b], and the corresponding variable x is defined in [1,1]. The mapping from x to u is given by:

(47) $\begin{array}{cc}u\left(x\right)=\frac{a+b}{2}+\frac{b-a}{2}x& \left(\mathrm{Equation}6\right)\end{array}$

(48) The mapping between u to x is given by:

(49) $\begin{array}{cc}x\left(u\right)=\frac{2u}{b-a}-\frac{a+b}{b-a}x& \left(\mathrm{Equation}7\right)\end{array}$

(50) For the function to be interpolated; that is, f(u) as defined in [a,b], the following can be written:

(51) $\begin{array}{cc}f\left(u\right)=f\left(\frac{a+b}{2}+\frac{b-a}{2}x\right)=\hat{f}\left(x\right)& \left(\mathrm{Equation}8\right)\end{array}$

(52) That is, function {circumflex over (f)}(x) is defined in [1,1], which is equal to the original function f(u). This implies that the interpolation of {circumflex over (f)}(x) is denoted by (x) (the interpolant).

3. Interpolation Order and Nodes

(53) The quality and accuracy of the interpolation is controlled by the interpolation order, which relates to the number of Chebyshev polynomials that will be used in the interpolant. The order of the interpolation is denoted by M; that is, the first M+1 Chebyshev polynomials in the interpolation (from T.sub.0 to T.sub.M) are used. An interpolation is always defined with respect to set of discrete values, referred to as the interpolation nodes, at which the original function is evaluated. The zeros of T.sub.M+1(x) are used as the interpolation nodes and these zeros are defined as (as derived from Equation 2 above):

(54) $\begin{array}{cc}{x}_k^0=\cos \left(\frac{2k+1}{2\left(M+1\right)}\right)& \left(\mathrm{Equation}9\right)\end{array}$

(55) Where:

(56) k=0, 1, . . . , n1.

(57) a. Projection onto Chebyshev Polynomials

(58) Assuming that interpolant (x) is of the form:

(59) $\begin{array}{cc}\hat{I}\left(x\right)=\underset{i=0}{\overset{i=M}{.Math.}}{c}_i{T}_i\left(x\right)& \left(\mathrm{Equation}10\right)\end{array}$

(60) Where:

(61) The interpolant is a linear combination of the first M+1 Chebyshev polynomials; and

(62) The equations form a linear system with respect to coefficients c.sub.i.

(63) As a result, a linear system of M+1 equations can be built by requiring that at the interpolation nodes the interpolant value is equal to the function value, that is:

(64) $\begin{array}{cc}\hat{I}\left(x_k^0\right)=\underset{i=0}{\overset{i=M}{.Math.}}{c}_i{T}_i\left(x_k^0\right)=\hat{f}\left(x_k^0\right)& \left(\mathrm{Equation}11\right)\end{array}$

(65) Where:

(66) k=0, 1, . . . , M; and

(67) M+1 equations form a linear system with respect to coefficients c.sub.i.

(68) Because Chebyshev polynomials form an orthogonal basis, this linear system has a well-defined unique solution. With the help of the orthogonality relation given in Equation 5, above, the following can be expressed:

(69) $\begin{array}{cc}\underset{j=0}{\overset{j=M}{.Math.}}\hat{f}\left(x_j^0\right)T_p\left(x_j^0\right)=\underset{j=0}{\overset{j=M}{.Math.}}\underset{i=0}{\overset{i=M}{.Math.}}{c}_i{T}_i\left(x_j^0\right)T_p\left(x_j^0\right)& \left(\mathrm{Equation}12a\right)\\ \underset{i=0}{\overset{i=M}{.Math.}}{c}_i{K}_i{}_{\mathrm{ip}}& \left(\mathrm{Equation}12b\right)\\ c_p{K}_p.& \left(\mathrm{Equation}12c\right)\end{array}$

(70) This implies that the coefficients c.sub.i introduced earlier can be calculated from the function to be interpolated {circumflex over (f)}(x) using the following formulas:

(71) 0$\begin{array}{cc}{c}_0=\frac{1}{M+1}\underset{j=0}{\overset{j=M}{.Math.}}\hat{f}\left(x_j^0\right)T_0(x_j^0=\frac{1}{M+1}\underset{j=0}{\overset{j=M}{.Math.}}\hat{f}\left(x_j^0\right)& \left(\mathrm{Equation}13a\right)\\ c_k=\frac{2}{M+1}\underset{j=0}{\overset{j=M}{.Math.}}\hat{f}\left(x_j^0\right)T_k(x_j^0=\frac{1}{M+1}\underset{j=0}{\overset{j=M}{.Math.}}\hat{f}\left(x_j^0\right),1kM& \left(\mathrm{Equation}13b\right)\end{array}$

4. Remarks

(72) The results derived in this Section III provide the necessary definitions for an improved non-linear-function-generation method applied to hybrid computing. The following are a few related remarks:

(73) Choosing the Chebyshev nodes as the interpolation nodes is designed to prevent Runge oscillations;

(74) Interpolation error (with respect to the original function) will exhibit oscillations; however, the minimum-maximum values of these oscillations can be controlled by adjusting the interpolation order; and

(75) For common functions (e.g., cosine and sine) the improved method leads to accurate results at relatively low interpolation order; for example, with M=6, the cosine function can be approximated with a maximum error of 0.25%.

5. Example

(76) Consider the following function in the interval [1,4]:
f(u)=cos(u).sup.3 exp(0.20u)(Equation 14)

(77) Refer to FIGS. 1 and 2. Interpolation examples for orders M=4 and M=10 are shown in FIG. 1. What is shown in FIG. 1 are three curvesthe function being approximated, the result using an interpolation of order M=4, and the result using an interpolation of order M=10. As it turns out, the curve for the interpolation M=10 is very nearly visually indistinguishable (in this graph) from the original function. The error in the interpolant for M=10 is shown in FIG. 2.

(78) B. Non-Linear-Function Generation for Hybrid Computing

(79) This Subsection III.B presents an improved method for non-linear-function generation in hybrid computing applications. Within this improved method, and for a given non-linear function, the computation of the interpolant coefficients is performed in the digital domain. Once this initial computation is done, the analog domain can be programmed to generate the requested non-linear function.

(80) The improved method also considers an arbitrary function f(u) defined in the interval [a,b]. The goal of the improved method is to provide a scheme so that part of the analog domain can be programmed to generate a function I(u) that approximates the function f(u).

(81) 1. Interpolant Computation in the Digital Domain

(82) This process should be part of the overall programming of an improved hybrid computer for a problem that would require a non-linear function in the analog domain.

(83) The following steps are performed in the digital domain:

(84) i. Define the function {circumflex over (f)}(x) as the mapping of f(u) to the interval [1,1] (see Equation 7, above);

(85) ii. For a given interpolation order M, compute the interpolant (x) using Equations 13 and 2, above;

(86) iii. Compare (x) and {circumflex over (f)}(x) using an error metric: If the error is below some pre-determined threshold, then the process is complete; otherwise, go back to Step ii and increase the interpolation order.

(87) The comparison Step iii above requires an error metric, and a typical choice would be the root-mean-squared error, which can be defined as:

(88) $\begin{array}{cc}\mathrm{RMS}=\left(\hat{f},\hat{I}\right)=\sqrt{\frac{1}{2}}{}_{-1}^1\stackrel{\_}{{\left(\hat{f}\left(x\right)-\hat{I}\left(x\right)\right)}^2\mathrm{dx}}& \mathrm{Equation}15\end{array}$

(89) The process then requires as input a maximum error value, and if the root-means-square (RMS) is below this maximum error value, then the interpolation is considered valid. In plain language, by this we mean that the order that was selected turned out to give rise to a generated output that tracked the true value of the function sufficiently closely. It should be noted that it is straightforward to show that the RMS value computed in [1,1] is strictly equal to the value that would be computed in the interval [a,b]. The outputs of this process are the following data (and are required for the programming of the analog domain):

(90) The values a and b defining the interval of the original function f(u); and

(91) The M+1 coefficients for the calculation of the interpolant.

(92) 2. Non-Linear-Function Programming in the Digital Domain

(93) An embodiment of the overall non-linear-function generator in the analog domain is shown in FIG. 3. It takes as input the value u, which is the value for which the non-linear function f(u) is to be evaluated, and produces as output the value of the interpolant I(u). Because the interpolant is designed to reproduce the original function up to a certain accuracy, the non-linear-function generator will be accurate up to this accuracy.

(94) As shown in FIG. 3, there is an initial stage, which is a scaling stage, and which simply implements Equation 7, above. This scaling stage is programmed with the values a and b, defining the interval of the original function.

(95) The second and last stage is the non-linear-function generator itself, which is programmed with the values of the coefficients c.sub.0, . . . , c.sub.M, which has been computed in the digital domain (see above).

(96) a. Non-Linear-Function Generator

(97) An embodiment of the implementation of the non-linear-function generator in the analog domain is shown in FIG. 4. The implementation relies on the recurrence relationship introduced earlier (see Equation 4, above) to calculate the interpolant value.

(98) As shown in FIG. 4, the only input is the value x, which is obtained as output of the scaling stage (see FIG. 3). The values T.sub.0(x) and T.sub.1(x) are not real inputs: T.sub.0(x)=1 and can be programmed directly, while T.sub.1(x)=x, which implies that x is used as input twice. The programming of the non-linear-function generator requires the values of the M+1 coefficients c.sub.0, . . . , c.sub.M obtained during the computation of the interpolation. The output of the non-linear-function generator is the value of the interpolant as a linear combination of Chebyshev polynomials.

(99) b. Chebyshev Polynomial Evaluator

(100) An embodiment of the implementation of the Chebyshev polynomial evaluator block from FIG. 4 is shown in FIG. 5. This block is a direct implementation of the recurrence relation given in Equation 4, above, and no specific programming is required.

(101) Notably, the above implementation can be simplified by pre-calculating 2x and using this value as inputs of the various blocks (this reduces the number required multiplier elements). It should also be noted that similar methods can be implemented for other families of polynomials (e.g., Laguerre polynomials). However, it is generally accepted in the industry that Chebyshev polynomials are the best choice for dealing with polynomial interpolation.

IV. Alternative Embodiments and Other Variations

(102) The various embodiments and variations thereof described herein, including the descriptions in any appended Claims and/or illustrated in the accompanying Figures, are merely exemplary and are not meant to limit the scope of the inventive disclosure. It should be appreciated that numerous variations of the invention have been contemplated as would be obvious to one of ordinary skill in the art with the benefit of this disclosure.

(103) Hence, those ordinarily skilled in the art will have no difficulty devising myriad obvious variations and improvements to the invention, all of which are intended to be encompassed within the scope of the Description, Figures, and Claims herein.