WEB-ресурс научно-практических конференций

Семчишин Л.М.

Чортківський інститут підприємництва і бізнесу Тернопільського національного економічного університету, Україна

АНАЛІЗ ОБЧИСЛЮВАЛЬНОЇ СТІЙКОСТІ АЛГОРИТМІВ РОЗВ'ЯЗАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ

Розв'язування систем лінійних алгебраїчних рівнянь (СЛАР) є одним із актуальних питань обчислювальної математики. При їх розв'язуванні часто виникають похибки, пов'язані з неточністю початкових даних чи похибки заокруглення [4; 5]. Крім того, майже завжди виникають помилки при проведенні обчислень вже в межах самої задачі ( внаслідок неточного виконання арифметичних операцій). Помилки цього типу (так звані обчислювальні) в багатьох випадках в сукупності рівносильні точному розв’язку такої ж задачі, але зі зміненими вхідними даними.

При реалізації алгоритму на ЕОМ виникають похибки заокруглення даних, сумарний ефект яких необхідно враховувати при розв ’ язуванні задачі .

Метою цієї роботи є провести аналіз обчислювальної стійкості алгоритмів розв'язання систем лінійних алгебраїчних рівнянь .

Нехай обчислювальна задача з початковими даними розв’язується з допомогою деякого точного алгоритму . Результат розв’язання задачі запишемо у вигляді: .

При реалізації алгоритму на ЕОМ всі його операції будуть замінені машинними псевдоопераціями, а сам алгоритм – деяким машинним алгоритмом , результат виконання якого запишемо у вигляді _.

Такий метод врахування сумарної похибки заокруглення називається прямим аналізом похибок. Для багатьох числових методів похибки проміжних обчислень в сукупності рівносильні випадку, коли б ті ж методи (в нашому випадку алгоритм ) точно розв’язували б кожен свою задачу, попередньо змінивши вхідні дані (наприклад, на ): .

Останню рівність запишемо у вигляді: , можна розглядати як розв’язок тієї ж задачі із збуреними на вхідними даними. Для отримання кількісної оцінки впливу похибок заокруглення використовують так званий зворотній аналіз похибок [1].

Розглянемо процес зведення щільно заповнених систем рівнянь з матрицями до звичайних лінійних алгебраїчних систем з числовими елементами. В результаті деяких перетворень [2] виникає система стрічкового вигляду несиметричної структури. Порядок системи дорівнює , а максимальна ширина стрічки становить . Застосувавши обчислювальну схему другого методу відсічених систем [2] для розв'язку одержаної стрічкової системи -го порядку ( ) , одержимо рекурентні співвідношення

(1)

та

(2)

З точки зору обчислювальної стійкості дана схема практично не відрізняється від звичайного методу відсічених систем [3] . Тому для еквівалентних збурень елементів чисельної матриці , що відповідають реалізації алгоритму на ЕОМ, запишемо

(3)

для обчислень з одинарною точністю і

(4)

у випадку, якщо застосовується накопичення скалярних добутків.

Отже, проаналізовано обчислювальну стійкість алгоритмів розв'язання систем лінійних алгебраїчних рівнянь. Запропонований аналіз алгоритму може ефективно використовуватися в системах комп’ютерної алгебри та для аналітично-числового розв’язування інженерних прикладних задач.

Список літератури:

1. Григорків В.С . Моделювання економіки. Ч.2: Навч . посібник / В.С. Григорків . — Чернівці: Рута, 2006. — 100 с.

2. Заборовець М.О. Сучасні методи розв'язування систем лінійних алгебраїчних рівнянь / М.О. Заборовець , Ф.А. Левченко , М.Г Охріменко – К..: КНЕУ, 2006. – 76 с.

3. Недашковський М.О. Обчислення з – матрицями. / М.О. Недашковський, О.Я. Ковальчук – К.: Наукова думка, 2007. – 294 с.

4. Цегелик Г.Г. Чисельні методи / Г.Г. Цегелик Л.: Видавничий центр ЛНУ імені Івана Франка, 2004. – 408 с.

5. Шахно С.М. Чисельні методи лінійної алгебри / С.М. Шахно Л.: Видавничий центр ЛНУ імені І. Франка, 2007. – 245 с.