Convergence of an iterative algorithm for computing parameters of multi-valued threshold functions | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 39. DOI: 10.17223/20710410/39/10

A k-valued threshold function is defined as f (x₁,..., x_n) = i e {0,1,..., k - 1} ^ ^ b^L (x₁,..., x_n) < b_i+₁ where L (x₁,..., x_n) = a₁x₁ + a₂x₂ + ... + a_nx_n is a linear form in variables x₁,..., x_n with the values in {0,1,..., k - 1} and coefficients a₁,...,a_n in R and b₀,...,b_k are some thresholds for L in R, b₀ < b₁ < ... < b_k. A. V. Burdelev and V. G. Nikonov have created and published in J. Computational Nanotechnology (2017, no. 1, pp. 7-14) an iterative algorithm for computing coefficients a₁,..., a_n and thresholds b₀,..., b_k for any k-valued threshold function f (x₁,..., x_n) given by its values f (c₁,..., c_n) for all (c₁... c_n) in {0,..., k - 1}ⁿ. In computer experiment they showed the convergence of this algorithm on many different examples. Here, we present a theoretical proof of this algorithm convergence on each k-valued threshold function for a finite number of steps (iterations). The proof is very much similar to the geometrical proof of perceptron convergence theorem by M. Minsky and S. Papert.