A PROGRAM FOR PIECEWISE-LINEAR APPROXIMATION OF FUNCTIONS DEFINED BY A FORMULA

I. G. VINTIZENKO

(Presented by the scientific seminar of the UVD TPI)

The advantages of analog computing technology—the visual clarity of the results obtained, the simplicity of preparing and solving problems, etc.—are offset by certain laborious and time-consuming tasks (calculation of scales, preparation of functions for setting on universal converters, and others). To speed up these tasks, programs are used for calculating scales and approximating functions, compiled for implementation on electronic digital computers (the APACHE code [2], standard programs for the Ural-2 digital computer [1], and others). However, powerful machines are not always available, and machine time is expensive. This gives rise to the need to write algorithms and corresponding programs for small, widely used digital machines, such as, for example, the Promin digital computer. The use of small digital computers in analog laboratories can considerably accelerate preparatory operations.

The most common case of specifying nonlinearities in analog computing technology is the method of specifying—let us call it the analytic specification method—a combination of elementary functions, such as, for example,

\[ F(x)=\frac{\exp(-\alpha x)+\sin \beta x}{\cos \gamma x} \qquad F(x)=\frac{\ln(\alpha x)}{\cos^2 \beta x}+\exp(\gamma x)\ \text{etc.} \]

The presence in the small digital computer “Promin” of a large number of “wired-in” standard subroutines for trigonometric, exponential, hyperbolic, and other functions, the possibility of generating special functions by subroutines, and also the simplicity of programming on this machine determined its choice for implementing a digital program that performs piecewise-linear approximation of an analytically specified function \(F(x)\).

The program consists of several blocks that perform the following operations:

1) conversion of the original coordinates of the problem into the electrical voltages of the UFP so that the maximum value of the function \(F(x)\) is equal to \(+100\) V, the minimum to \(-100\) V, the left extreme value of the argument \(x_{\min}\) (minimum) to \(-100\) V, and the right extreme value \(x_{\max}\) (maximum) to \(+100\) V;

\[ U_i=100\left(2\frac{x-x_{\min}}{x_{\max}-x_{\min}}-1\right)=M_xx-D_x, \]

\[ U_0=100\left(2\frac{F(x)-F_{\min}}{F_{\max}-F_{\min}}-1\right)=M_FF(x)-D_F, \]

\[ M_x=\frac{200}{x_{\max}-x_{\min}}, \qquad D_x=100+x_{\min}M_x, \]

\[ M_F=\frac{200}{F_{\max}-F_{\min}}, \qquad D_F=100+F_{\min}M_F, \]

so that the function being approximated is inscribed inside the rectangle \((-100,+100\) in \(U\), \(-100,+100\) in \(U_0)\) and touches all the boundaries of the rectangle;

2) piecewise-linear approximation of the function \(F(x)\), with printout of the opening voltages \(U_{ij}\) of the diode elements and of the values of the function at the breakpoints of the approximating broken line \(U_{0i}\).

Fig. 1

The process of constructing the approximating broken line is illustrated in Fig. 1. The entire interval \([x_{\min}, x_{\max}]\) is divided into \(n\) equal steps \(h\), so that

\[ h=\frac{x_{\max}-x_{\min}}{n}. \]

The number \(n\) is specified by the operator (with allowance for the form of the function, the required accuracy, etc.).

Compute \(F(x_1)\equiv F_1\) for \(x_1=x_{\min}+h\); draw a straight line through the points \(F(x_{\min})\) and \(F_1\), determine its slope \(k_1\), and the intersection point of the line with the \(y\)-axis, \(c_1\):

\[ k_1=\frac{F_1-F(x_{\min})}{h} \]

\[ c_1=F(x_{\min})-k_1x_{\min}. \]

Next, at the point \(x_2=x_1+h\), compute the true value of the function \(F(x_2)\equiv F_2\) and the approximate value \(F_2^*\), obtained from the formula

\[ F_2^*=k_1x_2+c_1, \]

find their difference in absolute value

\[ \Delta_2=|F_2-F_2^*| \]

and compare it with the specified approximation accuracy \(\varepsilon\). If \(\Delta_2>\varepsilon\), then the point

\[ (x_1,F_1) \]

is regarded as a breakpoint of the approximating broken line; in this case \(x_1\) and \(F_1\) are recorded in the corresponding arrays \(\{x_j\}\) and \(\{F_j\}\).

The construction of any subsequent segment of the approximating broken line begins at the point \(x_j, F_j\); \(h\) is added to \(x_j\), \(F_{j+1}\) is determined, as are the slope of the new segment of the broken line \(k_l\), the constant \(c_l\), etc.

If \(\Delta_2 \leqslant \varepsilon\), then to \(x_2\) we add the step \(h\), find \(F_3^*\), \(F_3^* = k_1 x_3 + c_1\), and \(\Delta_3 = |F_3 - F_3^*|\). We compare the new \(\Delta_3\) with the specified accuracy \(\varepsilon\), proceed according to the rules indicated above in the cases \(\Delta > \varepsilon\) and \(\Delta \leqslant \varepsilon\), etc., up to \(x = x_{\max}\). The program flowchart is given in Fig. 2.

Text in Fig. 2:

• Restoration \(x_{\min} \to x_j\)
• \(F(x)\)
• \(F(x_{\min})\)
• \(x_j + h \to x_j\)
• \(F_l, k_l\)
• \(x_j + h \to x_j\)
• \(F_{l+1}\)
• \(x_j + h \to x_j\)
• \(x_j \geq x_{\max}\)
• \(>\)
• \(<\)
• Determination \(M_x, D_x, M_F, D_F\)
• \(\{x_l\} \to \{U_{il}\}\)
  \(\{F_l\} \to \{U_{0l}\}\)
• Stop
• \(F_{l+1}^*, \Delta_{l+1}\)
• \(\Delta \geq \varepsilon\)
• \(>\)
• \(\leq\)
• \(x_l \to \{x_l\}\)
  \(F_l \to \{F_l\}\)
• Selection block \(F_{\max}\), \(F_{\min}\)
• \(-h + x_j \to x_j\)
  \(F_{l+1} \to F_l\)

Fig. 2

1. After determining the ordinates of all break points \(\{F_l\}\), where \(l = 1, 2, \ldots, m\), the maximum and minimum values \(F_{\max}(x_l)\) and \(F_{\min}(x_l)\) of the array of ordinates are selected. For this purpose a block for selecting \(F_{\max}\) and \(F_{\min}\) is introduced into the program. From them \(M_F\) and \(D_F\) are determined. After this, the entire array of ordinates is converted into voltages \(\{U\}\), at which the approximated broken line “breaks,” and the array \(\{x_l\}\) is converted into voltages \(\{U_{il}\}\), at which it is necessary to open the diodes of the UFP. The final setting table, printed by the output device, will contain \(M_x, D_x, M_F, D_F\), and the arrays \(\{U_{il}\}\) and \(\{U_{0l}\}\).

Preparation of functions of this kind for setting on the universal function converter of an analog computer with the aid of small digital computers is signifi-

significantly reduces the overall time required for preparing the problem, does not require graphical constructions, and provides the highest accuracy of approximation (in comparison with other methods of preparing the curve). The program was used in preparing functions for the universal functional converter NU-1 of the MN-14 AVM when solving nonlinear differential equations.

REFERENCES

1. A. Kh. Bereslavskii, G. S. Goldenberg, Yu. A. Redkov, E. P. Yakovenko. “Problems in automating the mathematical preparation of problems for setup on continuous-action machines.” In the collection Mathematical Modeling and Electrical Circuits. Kiev, Naukova Dumka, 1966, pp. 129—139.

2. Debroux, H. d’Hoop, C. Green. L’autoprogrammation des calculateurs analogiques par le code APACHE, “Revue A”. 1962, v. 4, No. 3, p. 128—134.