2.5. Графи обчислювальних процесів

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

Граф обчислювального процесу дозволяє наочно зобразити послідовність арифметичних операцій у деякому обчисленні. З його допомогою легко визначити внесок будь–якої похибки, що виникла в процесі обчислень, у загальну похибку.

Нехай вершини графу є змінні або арифметичні операції. Дуги графу вказують напрямок обчислень і вони позначені коефіцієнтами, що оцінюють поширення помилок.

Граф обчислювального процесу будується для аналізу процесу поширення відносних похибок в арифметичних виразах. Його слід читати знизу вгору в напрямку дуг графу. Спочатку виконуються операції, розташовані на будь–якому горизонтальному рівні, потім операції розташовані на більш високому рівні, і т.д. На рис. 2.1. представлені графи обчислювальних процесів основних арифметичних операцій.

Правило підрахунку загальної похибки з використанням графу обчислювального процесу таке: відносна похибка результату будь–якої операції входить в результат наступної операції, збільшуючись на коефіцієнт у стрілки, що з'єднує ці дві операції.

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

Д

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

Спочатку розглянемо операцію додавання (II рівень). Операція додавання використовує числа і y, задані з відносними похибками і . Кожна з похибок входить у результат помноженою на відповідні коефіцієнти і , тоді похибку операції додавання можна оцінити величиною  +  , до якої слід додати похибку округлення, тобто відносна похибка операції додавання буде виглядати

 +  + .

Вхідні дані (числа та їх похибки) беруть участь ще в одній операції – множення (I рівень графа), куди вони передаються помножуючись на коефіцієнти +1 і +1, тоді, з урахуванням похибки округлення, маємо

.

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

.

(2.25)

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

.

(2.26)

Величина відносної похибки округлення методом «відкидання» молодших розрядів можна оцінити (t – розрядність розмірної сітки комп’ютера), тоді .

2.6. Контрольні питання

1. Наведіть основні джерела і класифікацію похибок під час розв’язання практичних задач.

2. Дайте визначення абсолютної похибки.

3. Яку похибку називають відносною?

4. Які цифри числа називають значущими та вірними значущими? Наведіть приклад.

5. Наведіть та обґрунтуйте рівняння визначення похибок суми та різниці.

6. Наведіть та обґрунтуйте рівняння похибки добутку. Як визначити число вірних знаків добутку?

7. Наведіть та обґрунтуйте рівняння похибки частки. Визначте число вірних знаків частки.

8. Наведіть рівняння обчислення похибок степеня і кореня.

9. Поясніть, з якою метою застосовують графи обчислювальних процесів.

10. Наведіть графи обчислювальних процесів основних арифметичних операцій.

11. Наведіть граф довільного обчислювального процесу і обрахуйте загальну похибку результату.