BOOKS OF THE NATIONAL ACADEMY OF SCIENCES OF UKRAINE

Methods for the solution of systems of nonlinear algebraic equations and functions’ minimization tasks: elements of theory and applications

Mathematics

Authors:

Zadiraka Valery Konstyantynovich, Academician of the National Academy of Sciences of Ukraine, Professor, Doctor of physical-mathematical sciences. Head of the Numerical Methods Optimization Department 140, Institute of Cybernetics of National Academy of Sciences of Ukraine; Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, Ukraine.

https://orcid.org/0000-0001-9628-0454

 

Semenov Vasyl Yuriyovych, Doctor of physical-mathematical sciences, head of the algorithm research department of “Delta SPE” LLC, seniour researcher at Kyiv Academic University; Kyiv Academic University; Scientific-production enterprise “Delta SPE” LLC, Kyiv, Ukraine.

 

Reviewers:

Khimich Oleksandr Mykolayovych, Academician of NAS of Ukraine, Department of Informatics, Professor, Doctor of Physical and Mathematical Sciences, Deputy Director of V. M. Glushkov Institute of Cybernetics of NAS of Ukraine; V. M. Glushkov Institute of Cybernetics of NAS of Ukraine, Kyiv, Ukraine.

https://orcid.org/0000-0002-8103-4223

 

Bartish Mykhailo Yaroslavovych, Professor, Doctor of Physical and Mathematical Sciences, Professor of the Department of Theory of Optimal Processes, Lviv State University; Lviv State University, Faculty of Applied Mathematics and Informatics, Lviv, Ukraine.

 

Affiliation:

Project: Scientific book

Year: 2023

Publisher: PH "Naukova Dumka"

Pages: 128

DOI:

https://doi.org/10.15407/978-966-00-1800-6

ISBN: 978-966-00-1800-6

Language: Ukrainian

How to Cite:

Zadiraka, V.K., Semenov, V.Yu. (2023) Methods for the solution of systems of nonlinear algebraic equations and functions’ minimization tasks: elements of theory and applications. Kyiv, Naukova Dumka. 128p. [in Ukrainian].

Abstract:

Due to the rapid development of modern telecommunication and information technologies, there is a great need to develop new and improve existing methods for signal demodulation, information encoding and decoding, automatic objects’ recognition etc. A large number of these tasks is reduced to solving systems of nonlinear algebraic equations and problems of minimizing functions.

The monograph presents the methods of localization of all the roots of nonlinear algebraic equations systems based on Jacobian’s non-degeneracy, Kantorovich’s theorem, and Krawchyk’s operator are developed. Based on the method of searching all the roots of systems of nonlinear algebraic equations, the method of global minimization of functions of many variables is developed. Also, based on the developed methods and autoregressive model of speech, the new efficient high-speed methods of calculating the immittance spectral frequencies of speech signals have been developed. It is shown that the method has higher computational efficiency over the methods used in existing communication systems. Conditions for orthogonality and minimization of the Riesz ratio for wavelets based on Jacobi polynomials are established.

Basing on maximizing a posterior probability function, the method of demodulation and estimation of channel parameters on the basis of particle filtering is developed, the method of demodulating signals with a continuous phase is developed, which is based on the use of signal phase values only and the method of blind separation of signals with amplitude-phase modulation. It is shown that the proposed particle filtering demodulator provides an advantage over standard demodulators based on the use of Gardner and Costas loops. The developed method of demodulation of signals with a continuous phase has shown greater resistance to phase and frequency distortions  of the signal in the communication channel as compared to the traditional demodulator.

The method of semi-automatic data classification based on the minimization of Tikhonov functional using discrete Laplacian and the quasi-optimal choice of the regularization parameter has been developed and verified for different data sources. Also a new computationally efficient method for automatic identification of the speaker’s gender based on the Gaussian mixture models was developed based on the maximization of likelihood function. This method is based on the use of information vectors consisting of the pitch period of the speech signal and the set of cepstral coefficients.

Keywords:

systems of nonlinear algebraic equations, Newton method, Kantorovich theorem, Krawchyk operator, signal demodulation, blind signal separation, semi-automatic learning, automatic gender identification.

References:

  1. Besette B., Salami R., Lefebvre R., Jelinek M., Rotola-Pukkila J., Vainio J., Mikkola H., Jarvinen J. (2000) The adaptive multirate wideband speech codec (AMR-WB). Transactions Speech Audio Processing, 10, 19–41.
  2. 3GPP 26.190: Adaptive multi-rate-wideband (AMR-WB) speech codec; Transcoding functions (2005). http://www.3gpp.org.
  3. Arulampalam M. S., Maskell S., Gordon N., Clapp T. Particle-Filtering-Based Approach to Undetermined Blind Separation (2002). IEEE Transactions on Signal Processing, 50, 174–188.
  4. Balakrishnan V, Boyd S., Balemi S. Branch and bound algorithm for computing the minimum stability degree of parameter-dependent linear systems (1991). International journal of robust and nonlinear Control, 1, 295–317.
  5. Balas E. A note on the branch-and-bound principle (1968). Operations Research, 16, 442–445.
  6. Bistritz Y., Peller S. Immittance spectral pairs (ISP) for speech encoding. Proceedings of IEEE International Conference on Acoustics, Speech and Signal Processing (1993). 2, 9–12.
  7. Burkill J.C. Functions of intervals. Proceedings of the London Mathematical Society. (1924). 22, 375–-446.
  8. Byrd R. Large-scale nonlinear optimization, chapter KNITRO: an integrated package for nonlinear optimization (2006). Springer, 35–59.
  9. Chihara T.S. An introduction to orthogonal polynomials (1978). Gordon and Breach, New York, London, Paris.
  10. Chui C.K. An introduction to wavelets (1992). Boston: Academic Press.
  11. Chui C.K., Mhaskar H.N. On trigonometric wavelets (1993). Constructive Approximation, 9, 167–190.
  12. Daubechies I. Ten lectures on wavelets (1992). CBMS-NSF Regional Conference Proceedings. Philadelphia, PA: SIAM, 61.
  13. Dellnitz M., Shutze O., Sertl S. Finding zeros by multilevel subdivision techniques. IMA J. numerical analysis (2002), 22, 167–185.
  14. Dellnitz M., Shutze O., Sertl S. Locating all the zeros of an analytic function in one complex variable. J. Comput. Appl. Math. (2002), 138, 325–333.
  15. Dempster A., Lair N., Rubin D. Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statistic. Soc. (1977), 39, 1–38.
  16. Djuric P. M., Kotecha J. H., Zhang J., Huang Yu., Ghirmai T., Bugallo M. F., Miguez J. Particle filtering. IEEE Signal Proc. Magazine (2003). 20, 19–38.
  17. Dumitrescu B., Tabus I. Predictive LSF computation, Signal Proces. (2002). 81, 2019–2031.
  18. Emiris I.Z., Vershelde J. How to count efficiently all affine roots of a polynomial system. Discrete Appl. Math. (1999). 93, 21–32.
  19. Feigin J. Practical Costas loop design. RF design (2002), 25, 20–36.
  20. Fine H.B. On Newton’s method of approximation. Proc. Nat. Acad. Sci. USA (1916), 2, 546–552.
  21. B. Fischer, J. Prestin, Wavelets based on orthogonal polynomials. Mathematics of computation (1997), 66, 1593–1618.
  22. Fourier J.B.J. Question d’analyse algebraique. Oeuvres Completes (II) (1890) Gauthier-Villars, Paris, 243–253.
  23. Gannot S., Burnstein D., Weinstein E. Iterative and sequential Kalman filter-based speech enhancement algorithms. Transactions Speech Audio Processing (1998). 6, 373–385.
  24. Gardner F. M. A BPSK/QPSK timing error detector for sampled receivers. IEEE Transactions on Communications (1986), 34, 423–429.
  25. Gouldieff V., Palicot J. MISO Estimation of Asynchronously Mixed BPSK Sources. Proc. IEEE Conf. EUSIPCO (2015), 369-373.
  26. Hermansky H., Morgan N. RASTA processing of speech. IEEE Trans. Speech Audio Proces. (1994). 2, 578–589.
  27. Hermansky H. Perceptual Linear Prediction (PLP) analysis of speech. J. Acoust. Soc. Amer. (1990). 87, 1738–1753.
  28. Hua Zh., Youguang Zh., Guoyan Li. Particle-Filtering-Based Approach to Undetermined Blind Separation. Advances in information Sciences and Service Sciences (2012). 4, 305–313.
  29. Itakura F. Line spectrum representation of linear predictive coefficients of speech signals. J. Acoust. Soc. Amer. (1975). 57, Suppl. 1, 35.
  30. Kalovics F. Box valued functions in solving systems of equations and inequalities. Numerical algorithms (1998). 36, 1–12.
  31. Kearfott R.B. Empirical Evaluation of Innovations in Interval Branch and Bound Algorithms for Nonlinear Algebraic Systems. SIAM J. Sci. Comput. (1997). 18 (2), 574–594.
  32. Kabal P., Ramachandran R.P. The computation of line spectral frequencies using Chebyshev polynomials. IEEE Trans. Acoust. Speech Signal Proces. (1980). 28, 562–574.
  33. Kearfott R.B. Rigorous global search: continuous problems (1996). Kluwer Academic Publishers, Dordrecht.
  34. Kilgore T., Prestin J. Polynomial wavelets on the interval. Constr. Approx. (1996). 12, 95–110.
  35. Krawczyk R. Newton-Algorithmen zur Bestimmung yon Nullstellen mit Fehlerschranken. Computing (1969), 4, 187–201.
  36. Lewis R.M., Torczon V., Trosset M.V. Direct search methods: then and now. J. Comp. Appl. Math. (2000). 124, 191–207.
  37. Nickel K. On the Newton method in interval analysis. Math. Res. Center Tech. Rep. 1136. Univ. of Wisc. (1971).
  38. Lim J.S., Oppenheim A.V. All–pole modeling of degraded speech. IEEE Trans. Acoust. Speech Signal Proces. (1978). 26, 197–210.
  39. Linde Y., Buzo A.,Gray R. M. An algorithm for vector quantizer design. IEEE Trans. Com. (1980). 28 (1), 84–95.
  40. Martinez J.M. Practical quasi-Newton methods for solving nonlinear systems. J. Comp. Appl. Math. (2000). 124, 97–121.
  41. McLoughlin I.V. Line Spectral Pairs. Signal Proces. (2008). 88, 448–467.
  42. Meyer Y. Wavelets and operators. Cambridge Studies in Advanced Mathematics. (2003).
  43. Moore R.E. A test for existence of solutions to nonlinear systems. SIAM J. Numer. Anal. (1977). 14, 611–-615.
  44. Moore R.E. Interval arithmetic and automatic error analysis in digital computing. Ph.D. Thesis (1962). Stanford University.
  45. Morgan A.P., Shapiro V. Box bisection for solving second-degree systems and the problem of clustering. ACM Trans. Math. Software (1987). 13, 152–167.
  46. Neculai A. An unconstrained optimization test functions collection. Advanced Modeling and Optimization (2008) 10 (1), 147–161.
  47. Neumaier A., Zuhe S. The Krawczyk operator and Kantorovich theorem. J. Math. Anal. Applications (1990). 149 (2), 437–443.
  48. Neumaier A. Complete Search in Continuous Global Optimization and Constraint Satisfaction. Acta Numerica (2004), 383–408.
  49. Ostrowski A.M. Sur la convergence et l’estimation des erreurs dans quelques procedes de resolution des equations numeriques, in: Collection of Papers in Memory of D.A. Grave, Gosudarstv. Izdat. Tehn.-Teor. Lit., Moscow. (1940), 213–234.
  50. Paliwal K.K., Atal B.S. Efficient vector quantization of LPC parameters at 24 bits/frame. IEEE Trans. Speech Audio Proces. 1993. 1, 3–14.
  51. Pan B., Tu S. Blind separation of two QPSK signals based on lattice reduction. Proc. International Conference on Information Science and Control Engineering (2017) Changsha, 1437-1440.
  52. Pardalos P.M, Romeijn H.E., Tuy H. Direct search methods: then and now. J. Comp. Appl. Math. (2000). 124, 209–228.
  53. Prestin J., Quak E. Trigonometric interpolation and wavelet decompositions. Numerical Algorithms (1993). 9, 293–317.
  54. Punskaya E., Andrieu C., Doucet A., Fitzgerald W. J. Particle Filtering for Demodulation in Fading Channels with Non-Gaussian Additive Noise. IEEE Trans. Comm. (2001). 49, 579–582.
  55. Reynolds D. A., Quatieri T. F., Dunn R. B. Speaker verification using adapted Gaussian mixture models. Digit. Signal Proces. (2000). 10, 19–41.
  56. Reynolds D. A., Rose R, Robust text-independent speaker identification using Gaussian mixture speaker models. IEEE Trans. Speech Audio Proces. (1995). 3, 72–83.
  57. Reynolds D. A. Experimental evaluation of features for robust speaker identification. IEEE Trans. Speech Audio Proces. (1994). 2, 639–643.
  58. Rheinboldt W.C. Numerical continuation methods: a perspective. J. Comp. Appl. Math. (2000). 124, 229–244.
  59. Semenov V. Computation of Immittance and Line Spectral Frequencies Based on Inter-frame Ordering Property. Journal of Computers (2007). 2(7), 75–80.
  60. Semenov V. Method for the calculation of all non-multiple zeros of an analytic function. Comput. Methods Appl. Math. (2011). 11(1), 67–74.
  61. Semenov V. Method for the Calculation of all Zeros of an Analytic Function Based on the Kantorovich Theorem. Comput. Methods Appl. Math. (2014). 14(3), 385–-392.
  62. Shilong T., Hui Zh., Na G. Single-channel blind separation of two QPSK signals using per-survivor processing. Proceedings of IEEE Asia-Pacific Conference on Circuits and Systems (2008). Macao, 473–476.
  63. Szego G. Orthogonal polynomials. AMS Colloquium Publications XXIII, American Mathematical Society (1959) New York.
  64. Wang X., Chang T.-S. A multivariate global optimization using linear bounding functions. J. Global Optim. (1998). 12, 383–404.
  65. Warner E.S., Proudler I.K. Single-channel blind signal separation of filtered MPSK signals. IEE Proceedings – Radar, Sonar and Navigation (2003). 150(6), 396–402.
  66. Wu C. Single-Channel Blind Source Separation of Co-Frequency Overlapped GMSK Signals Under Constant-Modulus Constraints. IEEE Communications Letters (2016). 20(3), 486–489.
  67. Wu C.-H., Chen J.-H. A novel two-level method for the computation of LSP frequencies using a decimation-in-degree algorithm. IEEE Trans. Speech Audio Proces. (1997). 5, 106–115.
  68. Ying X., Katz I.N. A Reliable Argument Principle Algorithm to Find the Number of Zeros of an Analytic Function in a Bounded Domain. Numer. Math. (1988). 53, 143-163.
  69. Yamamoto T. Historical developments in convergence analysis for Newton’s and Newton-like methods. J. Comp. Appl. Math. (2000). 124, 1–23.
  70. Yamamura K., Fujioka T. Finding all solutions of nonlinear equations using the dual simplex method. J. Comp. Appl. Math. (2003). 152, 587–595.
  71. Zeng Y.-M., Wu Z.-Y., Falk T., Chang W.-Y. Robust GMM-based gender classification using pitch and RASTA-PLP parameters of speech. Proc. Int. Conf. Machine Learning and Cybernetics (2006). 3376-3379.
  72. Babenko K.Y. Osnovy chyslennoho analyza (1986). M.: Nauka.
  73. Babych M.D., Shevchuk L.B. Ob odnom alhorytme pryblyzhennoho reshenyia system nelyneinykh uravnenyi. Kybernetyka (1982). 2, 75–79.
  74. Bartish M.Ia. (2006) Metody optymizatsii. Teoriia i alhorytmy. Lviv. Vydavnychyi tsentr LNU im. I.Franka.
  75. Bartish M., Ohorodnyk N. Trykrokovyi iteratsiinyi metod minimizatsii funktsii z kubichnym poriadkom zbizhnosti. Visnyk Lvivskoho universytetu (2013). 20, 3–9.
  76. Bartish M., Kovalchuk O., Ohorodnyk N. Trykrokovi metody rozviazuvannia zadach bezumovnoi minimizatsii. Visnyk Lvivskoho universytetu (2007). 13, 3–10.
  77. Bartish M.Ia., Kovalchuk O.V., Nykolaichuk L.V. Trykrokovyi iteratsiinyi metod rozviazuvannia system neliniinykh rivnian. Matematychne ta Kompiuterne modeliuvannia (fiz.-mat. nauky) (2008). 1, 9–18.
  78. Bakhvalov N.S. (1973) Chyslennye metody. M.: Nauka.
  79. Bernshtein D.N. Chyslo kornei systemy uravnenyi. Funktsyonalnyi analyz y eho prylozhenyia (1975). 9(3), 1–4.
  80. Bulatov V.P. Chyslennye metody poyska vsekh reshenyi system nelyneinykh uravnenyi. Zhurnal vychyslytelnoi matematyky y matematycheskoi fyzyky (2000). 40(3), 348–355.
  81. Van Trys H. (1972) Teoryia obnaruzhenyia, otsenok y moduliatsyy. Tom 1. Teoryia obnaruzhenyia, otsenok y lyneinoi moduliatsyy. M.: Sovetskoe radyo.
  82. Voevodyn V.V., Tyrtyshnykov E.E. (1987) Vychyslytelnye protsessy s teplytsevymy matrytsamy. M.: Nauka.
  83. Vovk Y.V., Semenov V.Yu. Avtomatycheskoe obnaruzhenye y raspoznavanye sukhykh khrypov na osnove analyza ykh avtokorreliatsyonnoi funktsyy. Akustychnyi visnyk (2005). 8(3), 17–23.
  84. Hanshyn H.S. (1987) Metody optymyzatsyy y reshenye uravnenyi. M.: Nauka.
  85. Hrinchenko V. T., Meleshko V. V. (1981) Harmonycheskye ostsylliatsyy y volni na upruhykh telakh. Kyiv: Naukova dumka.
  86. Dennys Dzh., Shnabel R. (1988) Chyslennye metody bezuslovnoi optymyzatsyy y reshenyia nelyneinykh uravnenyi. M.: Myr.
  87. Zadiraka V.K., Oleksiuk O.S. (2003) Kompiuterna aryfmetyka bahatorozriadnykh chysel. Kyiv.
  88. Zadyraka V.K., Melnykova S.S. (1993) Tsyfrovaia obrabotka syhnalov. Kyiv.
  89. Zadyraka V.K. (1983) Teoryia vychyslenyia preobrazovanyia Fure. Kyiv.
  90. Zahuskyn V.L. K voprosu o reshenyy uravnenyi metodom yteratsyi: Vychyslytelnaia skhema dlia uskorennoho vychyslenyia vsekh kornei uravnenyia. Matem. prosv. (1961). 6, 263–265.
  91. Kantorovych L.V. O metode Niutona dlia funktsyonalnykh uravnenyi. Dokl. Akad. Nauk SSSR. (1948) 59, 1237–1240.
  92. Lebedev V.Y. (2006) Funktsyonalnyi analyz y vychyslytelnaia matematyka. M.: Fyzmathyz.
  93. Markel J.D., Gray A.H. (1980) Lyneinoe predskazanye rechy. M.: Radyo y sviaz.
  94. Molchanov Y.N. (2007) Mashynnye metody reshenyia zadach prykladnoi matematyky. Alhebra, pryblyzhenye funktsyi, obyknovennye dyfferentsyalnye uravnenyia. Kyev: Naukova dumka.
  95. Orteha J., Reinboldt V. (1975) Yteratsyonnye metody reshenyia nelyneinykh system uravnenyi so mnohymy neyzvestnymy. M.: Myr.
  96. Prokis J. (2000) Tsyfrovaia sviaz. M.: Radyo y sviaz.
  97. Rabyner L., Shafer R. (1981) Tsyfrovaia obrabotka rechevykh syhnalov. M.: Radyo y sviaz.
  98. Rybakov L. M. K voprosu o reshenyy uravnenyi metodom yteratsyi: Metod posledovatelnoho vychyslenyia vsekh deistvytelnykh kornei uravnenyia. Matem. prosv. (1961). 6, 262–263.
  99. Sage E, Mels J. (1976) Teoryia otsenyvanyia y ee prymenenye v sviazy y upravlenyy. M.:Sviaz.
  100. Semenov V.Iu. (2019) Rozviazannia system neliniinykh alhebraichnykh rivnian ta zadach minimizatsii funktsii: elementy teorii ta zastosuvannia: dys… d-ra fiz.-mat. nauk: spets. 01.05.02. Kyiv.
  101. Semenov V.Iu. Metod nakhozhdenyia vsekh deistvytelnykh nekratnykh kornei systemy nelyneinykh uravnenyi. Zhurnal vychyslytelnoi matematyky i matematycheskoi fyzyky (2007). 9, 1486–1493.
  102. Semenov V. Metod nakhozhdenyia vsekh kornei systemy nelyneinykh alhebraycheskykh uravnenyi, osnovannyi na operatore Kravchyka. Kybernetyka y Systemnyi analyz (2015). 51(5), 169–175.
  103. Semenov V., Prestyn Yu. Yssledovanye uslovyi ortohonalnosty veivletov, osnovannykh na polynomakh Yakoby. Kybernetyka y Systemnyi analyz (2018). 54(4), 182–190.
  104. Semenov V.Iu. Metody vychyslenyia y kodyrovanyia parametrov avtorehressyonnoi modely rechy pry razrabotke vokodera na baze syhnalnoho protsessora s fyksyrovannoi tochkoi. Problemy upravlenyia y ynformatyky (2019). 1, 41–50.
  105. Semenov V., Semenova E. Metod lokalyzatsyy nulei analytycheskykh funktsyi na osnove operatora Kravchyka. Kybernetyka y systemnyi analyz (2019). 55(3) 194–200.
  106. Semenov V.Iu., Semenova Ye.V. Metod hlobalnoi minimizatsii funktsii, zasnovanyi na zastosuvanni operatora Kravchyka. Kybernetyka y Systemnyi analyz (2019). 55(6), 195–202.
  107. Seno P.S. Novyi pidkhid do pobudovy intervalnykh metodiv rozviazuvannia system neliniinykh rivnian. Visn. Lviv. universytetu. (1989), 85–92.
  108. Skliar B. (2003) Tsyfrovaia sviaz. Teoretycheskye osnovy y praktycheskoe prymenenye.
  109. Starkov V.N. (2002) Konstruktyvnye metody vychyslytelnoi fyzyky v zadachakh ynterpretatsyy. Kyiv: Naukova dumka.
  110. Khimich A.N., Molchanov Y.N., Popov A.V., Chystiakova T.V., Yakovlev M.F. (2008) Parallelnye alhorytmy reshenyia zadach vychyslytelnoi matematyky. Kyev: Naukova dumka.
  111. Shakhno S.M., Zbizhnist kombinovanoho metodu Niutona-khord i yedynist rozviazku neliniinykh rivnian. Visnyk TNTU (2013). 69 (1), 243–252.
  112. Shakhno S., Yarmola H. Pro iteratsiini metody dlia rozviazuvannia neliniinykh zadach pro naimenshi kvadraty z dekompozytsiieiu operatora. Visn. Lviv. un-tu. (2018). 26, 20–28.
  113. Shor N.Z. (1979) Metody mynymyzatsyy nedyfferentsyruemykh funktsyi y ykh prylozhenyia / Kyev: Naukova dumka.

Схожі записи

Почніть набирати текст зверху та натисніть "Enter" для пошуку. Натисніть ESC для відміни.

Повернутись вверх