Developing an algorithm with improved relevance for the localization of vector’s coordinates for intelligent sensors

Abstract

There are sensors of vector quantities whose field characteristics are described by the equations of quadrics. These sensors have improved sensitivity and smaller dimensions, the "payment" for which is, in fact, the non-linearity of field characteristics. In order to use such sensors, one has to solve the system of three quadric equations. Given the labor-intensity of this process, the sensors are designed intelligent – a finished device includes microcontrollers or other units that are able to process results of measurements. These devices are characterized by "curtailed" software and hardware capacities that necessitate the development of algorithms and their implementations with regard to these constraints.

Classic algorithms for solving the systems of polynomial equations are not appropriate because of their violating the requirements to minimal resource consumption. The search for solutions of the systems of quadric equations is carried out in two stages – first, numerical fields that potentially contain intersections are localized, and then in these regions the search is conducted for accurate solutions by numerical methods. The success of using numerical methods depends on the quality of the conducted localization of solutions. The means of localization are not sufficiently worked out. Earlier, an algorithm was developed using interval arithmetic, the implementation of which by a microcontroller of the ARM Cortex-M4 architecture proved its capacity to find all, without exception, regions with the sought solutions of a system of equations, however, in addition to the "useful" regions, this algorithm finds as well the regions that do not actually contain the solutions. This fact led to unnecessary waste of time trying to find exact solutions in the regions where they do not exist.

Thus, there was a need to search for alternative ways to the localization of solutions for the systems of quadrics equations. It is natural to search for these methods, based on the properties of quadrics in particular and continuous differentiable functions in general. A foundation of the proposed algorithm is the fact that a function in a closed region acquires its maximum or minimum value either at the borders or in critical points. If we accept, as a closed region, a rectangular parallelepiped, then its boundaries are its six sides, the boundaries of sides are its edges, and the boundaries of edges are the tops of parallelepiped. On the sides of the parallelepiped, function of three variables is reduced to function of two variables, on the edges – to functions of one variable. In the case of quadrics, finding the critical points of function on the edges comes down to solving a linear equation, and the critical points of function on the sides – to solving a system of two linear equations with two unknowns. Therefore, it is sufficient to check the signs of function at the tops of rectangular parallelepiped and those critical points of function that belong to the examined region. If in all these points the signs of function are the same, then there is no any point inside where function takes the 0 value. Thus, checking the signs of all functions that represent the left parts of the quadrics equation allows us to "reject" the regions, where there possible may not be any points of intersection. Instead of remembering the values of functions (valid numbers), it is sufficient to keep the signs of functions (one bit), which provides for the less consumption of operative memory. The tests proved that the proposed new algorithm is applicable for the implementation in the micro programming software, thus providing for a higher relevance of the found regions in comparison with the algorithm-analogue. An increase in relevancy is explained by the fact that interval arithmetic always implies overstated evaluations because, as the lower boundaries of intervals, the minimum permissible values are accepted, and as the upper limits – maximum permissible values. Checking the signs of functions in the selected points is free from the revaluation of results. The new algorithm somewhat deteriorated performance of permanent memory and execution time, however, these costs are compensated for by the further search for the solutions for a smaller number of irrelevant regions.