A PROGRAM FOR LINEAR APPROXIMATION OF FUNCTIONS SPECIFIED BY DISCRETE POINTS

I. G. VINTIZENKO

(Presented by the scientific seminar of the Department of Computer Engineering, TPI)

Small-scale automation of labor-intensive processes associated with the preparation of problems for solution on analog computers considerably facilitates, simplifies, and accelerates the solution process, makes it possible to choose scales more qualitatively and with better justification, to represent a nonlinear function more accurately by a broken line, and so on.

For this purpose, a number of algorithms have been prepared and programs have been written on the Promin electronic digital computer for the linear approximation of specified functions [1]. Let us consider one of the algorithms that makes it possible to approximate a function specified by discrete points. The method of specifying a function in the form of a set of points \(\{x_j, F_j\}\) is most often encountered in the processing of experimental data.

The approximation problem consists in the following:

1) through the set of points \(\{x_j, F_j\}\), draw a broken line \(F^*\) so that the deviations

\[ \Delta_j = |F_j - F_j^*| \]

for all \(j\) are less than a prescribed value \(\varepsilon\) (the permissible approximation error), and the number of segments of the broken line is minimal (Fig. 1);

Fig. 1.

2) convert the points \(\{x_j, F_j^*\}\) satisfying this condition (1) into voltages that control the nonlinear-function setting unit on the universal functional converter of an analog computer. In this case the transformation is carried out by the known formulas [1]:

\[ U_{ij}=100\left(2\frac{x_j-x_{\min}}{x_{\max}-x_{\min}}-1\right)=M_x x_j-D_x, \tag{1} \]

\[ U_{0j}=100\left(2\frac{F_j^*-F_{\min}}{F_{\max}-F_{\min}}-1\right)=M_F F_j^*-D_F, \tag{2} \]

where

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

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

so that

\[ \begin{aligned} F_{\max} &\to +100\ \text{V}, \qquad &F_{\min} &\to -100\ \text{V},\\ x_{\max} &\to +100\ \text{V}, \qquad &x_{\min} &\to -100\ \text{V}. \end{aligned} \]

The scales \(M_F\) and \(M_x\), as well as the shifts of the coordinate origin by \(D_F\) and \(D_x\), are needed in order to compute the scales for the entire problem; therefore, after being computed, they are printed.

The shift of the coordinate origin and the selected scaling (3–6) make it possible to use the scale of the universal functional converter of the analog computer as fully as possible and, consequently, to reduce the error in implementing the nonlinear function on the UFC.

The program consists of the following main blocks:

1) the block for selecting \(F_{\max}\) and \(F_{\min}\); for this purpose all \(F_j\) written in the memory cells are read sequentially and compared, and the minimum and maximum values are written into the corresponding cells;

2) the block for computing \(M_x, M_F, D_x\), and \(D_F\) and converting the obtained \(\{x_j, F_j^*\}\) into \(\{U_{ij}, U_{0j}\}\);

3) the approximation block, in which, through \(F_j\) and \(F_{j+1}\) (at \(x_j\) and \(x_{j+1}\)), a straight line is drawn with slope \(k_l\)

\[ k_l=\frac{F_{j+1}-F_j}{x_{j+1}-x_j} \]

and with the point of intersection of this line with the \(F\)-axis

\[ c_l=F_j-k_l x_j . \]

Then it is checked whether the next point \((x_{j+2}, F_{j+2})\) lies on the obtained straight line; for this purpose

\[ F_{j+2}^{*}=k_l x_{j+2}+c_l \]

is found, as well as the deviation

\[ \Delta_{j+2}=\left|F_{j+2}-F_{j+2}^{*}\right|. \]

The value \(\Delta\) is compared with the prescribed approximation accuracy \(\varepsilon\). If \(\Delta>\varepsilon\), then the point \((x_{j+1}, F_{j+1})\) is regarded as a break point of the approx-

Fig. 2. Flowchart:

• Restoration
• Selection of \(F_{\max}, F_{\min}\)
• Determination of \(M_x, M_F, D_x, D_F\)
• Determination of \(k, C\)
• \(j+1 \to j\)
• Are all \(j\)?
• yes → Stop
• no → Determination of \(F^*\)
• Determination of \(\Delta\)
• \(\Delta \le 0\)
• \(\Delta<0\) loops back
• \(\Delta>0\) → Conversion and printing
  \(x_l \to U_{ij}\)
  \(F_l \to U_{0j}\)
• \(j-1 \to l\)

approximating broken line; through it and the point \((x_{j+2}, F_{j+2})\) the next, \((l+1)\)-st straight line is drawn with slope \(k_{l+1}\), constant \(c_{l+1}\), etc. If \(\Delta \leqslant \varepsilon\), then it is assumed that the point \((x_{j+2}, F_{j+2})\) lies on the straight line \(l\), and the next point \((x_{j+3}, F_{j+3})\), etc., is selected for checking, up to the last point \([x_{\max}, F(x_{\max})]\).

The flowchart of the entire program is shown in Fig. 2. The memory capacity of the “Promin” computer makes it possible to approximate a curve when the number of points specifying it does not exceed 30. With a larger number of points, the approximation can be carried out in several stages, with the last breakpoint of the first computation being taken as the initial point in the second computation, and so on.

REFERENCES

1. I. G. Vintizenko. “A Program for Piecewise-Linear Approximation of Functions Specified by a Formula” (this collection).