Розвинення технології довгої арифметики при побудові алгоритмів дослідження лінійних систем

Автор(и)

  • Volodymyr Kudin Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033, Україна https://orcid.org/0000-0002-5665-0868
  • Viacheslav Onotskyi Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033, Україна https://orcid.org/0000-0002-1920-0905
  • Ali Al-Ammouri Національний транспортний університет вул. М. Омеляновича-Павленка, 1, м. Київ, Україна, 01010, Україна https://orcid.org/0000-0002-0375-6108
  • Lyudmyla Shkvarchuk Національний університет «Львівська політехніка» вул. С. Бандери, 12, м. Львів, Україна, 79013, Україна https://orcid.org/0000-0001-7241-3961

DOI:

https://doi.org/10.15587/1729-4061.2019.157521

Ключові слова:

метод базисних матриць, точні обчислення, погано обумовлена система лінійних рівнянь

Анотація

Розвинуто застосування алгоритмів методу базисних матриць, які оснащені технологією довгої арифметики для покращення точності виконання основних операцій при дослідженні погано обумовлених лінійних систем, зокрема, систем лінійних алгебраїчних рівнянь (СЛАР). Встановлення факту поганої обумовленості системи є досить трудомісткою обчислювальною процедурою. Закладено проведення контролю входження обчислень в стан некоректності та унеможливлення накопичення похибок обчислень, що є бажаною властивістю методів та алгоритмів розв’язання практичних задач.

В сучасних ЕОМ, як правило, використовуються стандарті типи цілих чисел, розмір яких не перевищує 64 байта. Було подолано це апаратне обмеження програмним шляхом, а саме, розробкою власного типу даних у вигляді спеціальної бібліотеки Longnum мовою С++ з використанням стандартної бібліотеки шаблонів STL(Standard Template Library). Програмна реалізація була розвинута на проведення обчислень за методами базисних матриць (МБМ) та Гауса, тобто використано довгу арифметику для моделей з раціональними елементами. Запропоновано алгоритми та комп´ютерну реалізацію методів типу Гауса та штучних базисних матриць (варіант методу базисних матриць) в середовищах Мatlab та Visual С++ з використанням технології точних обчислень елементів методів, в першу чергу, для погано обумовлених систем різної розмірності. Розроблено бібліотеку Longnum з типами довгих цілих чисел (longint3) та раціональних чисел (longrat3) із чисельником та знаменником типу longint3. Арифметичні операції над довгими цілими числами реалізовано на основі сучасних методів: зокрема, методу Штрасена множення. Наведено результати обчислювального експерименту за згаданими методами, в якому тестові моделі систем генерувались, зокрема, на основі матриць Гільберта різної розмірності, які характеризуються як “незручні”

Біографії авторів

Volodymyr Kudin, Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033

Доктор технічних наук, професор

Кафедра інтелектуальних та інформаційних систем

Viacheslav Onotskyi, Київський національний університет імені Тараса Шевченка вул. Володимирська, 60, м. Київ, Україна, 01033

Кандидат фізико-математичних наук, асистент

Кафедра обчислювальної математики

Ali Al-Ammouri, Національний транспортний університет вул. М. Омеляновича-Павленка, 1, м. Київ, Україна, 01010

Доктор технічних наук, професор

Кафедра інформаційно-аналітичної діяльності та інформаційної безпеки

Lyudmyla Shkvarchuk, Національний університет «Львівська політехніка» вул. С. Бандери, 12, м. Львів, Україна, 79013

Доктор економічних наук, професор

Кафедра фінансів

Посилання

  1. Kahaner, D., Mouler, K., Nesh, S. (2001). Chislennye metody i programmnoe obespechenie. Moscow: Mir, 575.
  2. Demmel', Dzh. (2001). Vychislitel'naya lineynaya algebra. Teoriya i prilozhenie. Moscow: Mir, 430.
  3. Han, D., Zhang, J. (2007). A comparison of two algorithms for predicting the condition number. Sixth International Conference on Machine Learning and Applications (ICMLA 2007). doi: https://doi.org/10.1109/icmla.2007.8
  4. Ebrahimian, R., Baldick, R. (2001). State Estimator Condition Number Analysis. IEEE Power Engineering Review, 21 (5), 64–64. doi: https://doi.org/10.1109/mper.2001.4311389
  5. Nishi, T., Rump, S., Oishi, S. (2013). A consideration on the condition number of extremely ill-conditioned matrices. 2013 European Conference on Circuit Theory and Design (ECCTD). doi: https://doi.org/10.1109/ecctd.2013.6662260
  6. BLAS (Basic Linear Algebra Subprograms). Available at: http://www.netlib.org/blas/sblat1
  7. Li, H., Yang, H., Shao, H. (2010). A note on the perturbation analysis for the generalized Cholesky factorization. Applied Mathematics and Computation, 215 (11), 4022–4027. doi: https://doi.org/10.1016/j.amc.2009.12.009
  8. The GNU Multiple Precision Arithmetic Library. Available at: https://gmplib.org/
  9. Multiple Precision Integer Library (MPI). Available at: https://github.com/servo/nss/tree/master/lib/freebl/mpi
  10. OpenSSL Cryptographic Toolkit. Available at: http://openssl.org
  11. Large Integer Package. Available at: https://github.com/luckyaibin/BigInt/tree/master/freelip
  12. Denis, T., Rose, G. (2006). BigNum Math. Implementing Cryptographic Multiple Precision Arithmetic. Syngress, 291. doi: https://doi.org/10.1016/b978-1-59749-112-9.x5000-x
  13. Galovic, Ya. (2018). C++17 STL. Standartnaya biblioteka shablonov. Sankt-Peterburg: Piter, 432.
  14. Kudin, V. I., Lyashko, S. I., Hritonenko, N. M., Yacenko, Yu. P. (2007). Analiz svoystv lineynoy sistemy metodom iskusstvennyh bazisnih matric. Kibernetika i sistemniy analiz, 4, 119–127.
  15. Bohaienko, V. O., Kudin, V. I., Skopetskyj, V. V. (2009). Analysis of computational schemes for basic matrix method. Komp'yuternaya matematika, 2, 3–13.
  16. Bogaenko, V. A., Kudin, V. I., Skopeckiy, V. V. (2009). Analiz vychislitel'nyh skhem modelirovaniya processov geogidrodinamiki. Probl. upr. i informatiki, 4, 62–72.
  17. Bogaenko, V. A., Kudin, V. I., Skopeckiy, V. V. (2012). Ob osobennostyah organizacii vychisleniy na osnove metoda bazisnyh matric. Kibernetika i sistemniy analiz, 48 (4), 146–155.
  18. Bogainenko, V., Kudin, V. (2014). Building preconditioners using basis matrix method. International journal Information Content and Processing, 1 (2), 182–187.
  19. Knut, D. (2000). Iskusstvo programmirovaniya. Vol. 2. Moscow: Izdatel'skiy dom «Vil'yams», 788.
  20. Krendall, R., Pomerans, K. (2011). Prostye chisla: Kriptograficheskie i vychislitel'nye aspekty. Moscow: URSS, 664.
  21. Straustrup, B. (2006). Yazyk programmirovaniya C++. Special'noe izdanie. Sankt-Peterburg-Moscow: «Nevskiy dialekt» - «BINOM», 1104.
  22. Kudin, V. I., Onotskyi, V. V. (2011). Rozvynennia tekhnolohiyi dovhoi aryfmetyky pry pobudovi alhorytmiv doslidzhennia zadachi liniynoho prohramuvannia. Zhurnal obchysliuvalnoi ta prykladnoi matematyky, 1, 77–84.

##submission.downloads##

Опубліковано

2019-02-26

Як цитувати

Kudin, V., Onotskyi, V., Al-Ammouri, A., & Shkvarchuk, L. (2019). Розвинення технології довгої арифметики при побудові алгоритмів дослідження лінійних систем. Eastern-European Journal of Enterprise Technologies, 1(4), 14–22. https://doi.org/10.15587/1729-4061.2019.157521

Номер

Том 1 № 4 (2019): Математика та кібернетика - прикладні аспекти

Розділ

Математика та кібернетика - прикладні аспекти

Ліцензія

Авторське право (c) 2019 Volodymyr Kudin, Viacheslav Onotskyi, Ali Al-Ammouri, Lyudmyla Shkvarchuk

Creative Commons License

Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.

Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.

Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.