2024, випуск 2, c. 47-56
Одержано 13.03.2024; Виправлено 20.04.2024; Прийнято 28.05.2024
Надруковано 09.06.2024; Вперше Online 14.06.2024
https://doi.org/10.34229/2707-451X.24.2.5
Попередня | ПОВНИЙ ТЕКСТ | Наступна
Методи боротьби з накопиченням похибки заокруглення під час розв’язання задач трансобчислювальної складності
В.К. Задірака * , І.В. Швідченко *
Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її., Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Основна увага приділена необхідності врахування оцінок похибок заокруглення під час розв’язання задач трансобчислювальної складності. Серед таких задач можна виділити задачі обчислення систем лінійних алгебраїчних рівнянь з кількістю невідомих у декілька десятків мільйонів, цифрової обробки сигналів, розрахунку ядерних реакторів, моделювання фізичних, хімічних процесів, аеродинаміки, захисту інформації тощо.
Неврахування похибки заокруглення під час їх розв’язання призводить до того, що іноді отримуються комп’ютерні рішення, які не відповідають фізичному змісту задачі.
Мета статті. Показано, як, використовуючи оцінки похибок заокруглення, будувати стійкі до похибок заокруглення обчислювальні алгоритми. При цьому враховуються: правило заокруглення, режим обчислення, якість оцінок похибок заокруглення (непокращувальна оцінка, асимптотична оцінка, ймовірнісна оцінка).
За наявності обчислювальних ресурсів доцільно використовувати асимптотичні оцінки та ймовірнісні як більш точні у порівнянні з мажорантними оцінками.
Результати. Показано, як у сучасних комп’ютерних технологіях використовуються оцінки похибок заокруглення для отримання ε-розв’язку наступних задач прикладної математики:
– обчислення інтегралів від швидкоосцилюючих функцій;
– розв’язання задач цифрової обробки сигналів;
– обчислення дискретного перетворення Фур’є;
– багаторозрядна арифметика;
– комп’ютерна стеганографія.
Найбільша увага приділена T-ефективним алгоритмам обчислення дискретного перетворення Фур’є та розв’язанню задач спектрального і кореляційного аналізу випадкових процесів. Ці класи задач входять як складові під час розв’язання задач двоключової криптографії та комп’ютерної стеганографії.
Висновки. Показана важливість урахування оцінок похибок заокруглення у сучасних комп’ютерних технологіях розв’язання ряду класів задач обчислювальної та прикладної математики.
Ключові слова: похибка заокруглення, комп’ютерна технологія, дискретне перетворення Фур’є, інтегрування швидкоосцилюючих функцій, інформаційна безпека.
Цитувати так: Задірака В.К., Швідченко І.В. Методи боротьби з накопиченням похибки заокруглення під час розв’язання задач трансобчислювальної складності. Cybernetics and Computer Technologies. 2024. 2. С. 47–56. https://doi.org/10.34229/2707-451X.24.2.5
Список літератури
1. Задірака В.К., Швідченко І.В. ε-розв’язок задачі. Збірник матеріалів проблемно-наукової міжгалузевої конференції “Інформаційні проблеми комп’ютерних систем, юриспруденції, енергетики, моделювання та управління” (ICSM-2022), 14–15 липня 2022 р. Надвірна, 2022. С. 29–32.
2. Задирака В.К. Теория вычисления преобразования Фурье. К.: Наукова думка, 1983. 216 с.
3. Задірака В.К., Терещенко А.М. Комп’ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. К.: Наукова думка, 2021. 136 с. https://books-nasu.org.ua/computer-arithmetics-of-multi-digits-numbers-in-sequential-and-parallel-calculation-models/
4. Sergienko I.V., Zadiraka V.K., Lytvyn O.M. Elements of the General Theory of Optimal Algorithms. Springer, 2021. 378 p. https://doi.org/10.1007/978-3-030-90908-6
5. Задірака В.К., Луц Л.В., Швідченко І.В. Теорія обчислень інтегралів від швидкоосцилювальних функцій. К.: Наукова думка, 2023. 472 c. https://doi.org/10.15407/978-966-00-1843-3
6. Задирака В.К., Мельникова С.С. Цифровая обработка сигналов. К.: Наукова думка, 1993. 294 с.
7. Weinstein C. Roundoff noise in floating point fast Fourier transform computation. IEEE Transactions on Audio and Electroacoustics. 1969. 17 (3). P. 209–215. https://ieeexplore.ieee.org/document/1162049
8. Welch P. A fixed-point fast Fourier transform error analysis. IEEE Transactions on Audio and Electroacoustics. 1969. 17 (2). P. 151–157. https://ieeexplore.ieee.org/document/1162035
9. Задірака В.К., Бабич М.Д., Березовський А.І., Бесараб П.М., Гнатів Л.О., Людвиченко В.О. T-ефективні алгоритми наближеного розв’язання задач обчислювальної та прикладної математики. Київ-Тернопіль: «Збруч», 2003. 261 с.
10. Задірака В.К., Швідченко І.В. Використання похибки заокруглення в сучасних комп’ютерних технологіях. Кібернетика та комп’ютерні технології. 2021. № 3. С. 43–52. https://doi.org/10.34229/2707-451X.21.3.4
11. Голд Б., Рейдер К. Цифровая обработка сигналов. М.: Сов. радио, 1973. 368 с.
12. Задирака В.К., Швидченко И.В. Влияние качества оценки погрешности округления стеганоалгоритма на его стойкость. Математичне та комп’ютерне моделювання. Серія: Фізико-математичні науки. 2015. Вип. 12. С. 101–112. http://mcm-math.kpnu.edu.ua/article/view/52691/48742
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | ПОВНИЙ ТЕКСТ | Наступна