Материал: Методичка

Итак, в вычислительной машине в силу ряда причин невозможно как точно представить исходные числа, так и реализовать арифметические операций с их использованием. Возникает естественный вопрос о том, как ошибка в исходных числах или в результатах арифметических операций распространяется далее в ходе вычислений. Становится ее влияние больше или меньше по мере того, как производятся последующие операции?

1.6. Графы вычислительных процессов

Для оценки общей (итоговой) погрешности (ошибки) выполнения некоторой последовательности арифметических операций существует достаточно удобный способ, основанный на использовании графов вычислительных процессов. Граф вычислительного процесса позволяет наглядно изобразить последовательность арифметических операций и легко определить вклад любой ошибки, возникшей в процессе вычислений, в общую ошибку. Пусть вершинами графа являются значения переменных или результатов арифметических операций, а его дуги указывают направление вычислений и нагружены коэффициентами, оценивающими распространение ошибок. Граф вычислительного процесса строится для анализа процесса распространения относительных ошибок в арифметических выражениях, его следует читать в направлении дуг. Сначала выполняются операции, расположенные на каком-либо горизонтальном уровне, затем операции расположенные на более высоком уровне и т.д. На рис.1.3. представлены графы вычислительных процессов арифметических операций.

Рис. 1.3. Графы вычислительных процессов основных арифметических операций.

Правило подсчета общей ошибки с использованием графа вычислительного процесса можно сформулировать следующим образом: относительная ошибка результата любой операции (вершины) входит в результат следующей операции, умножаясь на коэффициент у дуги, соединяющей эти две операции.

В качестве примера рассмотрим выражение и задачу оценки общей погрешности результата его вычисления с учетом ошибок округления результатов выполнения арифметических операций. Предположим, что , и – относительные погрешности округления чисел , и при представлении их в памяти ЭВМ, а и – относительные ошибки округления соответственно результатов операций сложения и умножения. Учитывая последовательность операций, для рассматриваемого выражения граф вычислительного процесса будет иметь вид, представленный на рис. 1.4.

Рис. 1.4. Граф вычислительного процесса для выражения .

Исследуем граф, представленный на рис. 1.4. Рассмотрим операцию сложения (уровень II), использующую числа и , заданные с относительными погрешностями и . Каждая из погрешностей входит в результат выполнения операции, умноженной на соответствующий коэффициент и . Тогда ошибку операции сложения можно оценить величиной , к которой следует прибавить ошибку округления. В результате формула расчета относительной ошибки операции сложения будет выглядеть следующим образом:

.

Результат выполнения операции сложения используется в операции умножения (уровень I), при этом погрешности передаются в результат выполнения операции умноженными на соответствующие коэффициенты . Тогда, с учетом погрешности округления, общая относительная погрешность вычисления значения может быть рассчитана следующим образом:

.

Поскольку причина ошибок округления и представления чисел в памяти ЭВМ одна – ограниченность ее разрядной сетки, – то для относительных ошибок можно положить . Тогда формулу расчета общей погрешности вычисления значения можно упростить:

.

Полученная формула позволяет дать верхнюю оценку общей погрешности: . Вывод формулы оценки итоговой ошибки выполнения ряда арифметических операций с помощью графа вычислительного процесса для произвольного алгоритма может являться сложной задачей. Кроме того, в процессе вычислений в алгоритмах могут использоваться стандартные или специальные подпрограммы, для которых не известны значения и оценки погрешностей вычисления. В то же время, оценить погрешность арифметических операций можно в результате проведения вычислительного эксперимента.

1.7. Вопросы для самопроверки

1. Перечислите основные этапы исследования и математического моделирования явлений реального мира, раскройте их содержание.

2. Охарактеризуйте взаимосвязь этапов исследования и математического моделирования явлений, укажите их связь с численными методами.

3. Дайте определение численных методов, охарактеризуйте аналитические и приближенные методы.

4. Перечислите основные этапы решения математических задач с применением ЭВМ, раскройте их содержание и взаимосвязь.

5. Сформулируйте и поясните основные проблемы вычислительной математики.

6. Сформулируйте общую постановку задачи вычисления, дайте определение корректной задачи, раскройте ее содержание.

7. Охарактеризуйте понятие устойчивости решения задачи.

8. Перечислите основные источники погрешностей и раскройте их сущность.

9. Дайте определение абсолютной и относительной погрешности, приведите примеры.

10. Дайте определение значащих и верных цифр в записи чисел, приведите примеры.

11. Запишите формулы расчета абсолютной и относительной погрешности результата сложения чисел и , где и – их погрешности.

12. Запишите формулы расчета абсолютной и относительной погрешности результата вычитания чисел и , где и – их погрешности.

13. Запишите формулы расчета абсолютной и относительной погрешности результата умножения чисел и , где и – их погрешности.

14. Запишите формулы расчета абсолютной и относительной погрешности результата деления чисел и , где и – их погрешности.

15. Запишите формулы расчета абсолютной и относительной погрешности вычисления значения функции, зависящей от одного аргумента.

16. Объясните принцип представления чисел с плавающей точкой в памяти ЭВМ.

17. Каковы особенности выполнения арифметических операций над машинными числами?

18. Что является вершинами и дугами графа вычислительного процесса, значения каких параметров соответствуют его вершинам и дугам?

19. Приведите примеры графов вычислительных процессов основных математических операций, какие параметры соответствуют их дугам?

20. Объясните принцип расчета общей погрешности результата выполнения арифметических операций с помощью соответствующего графа вычислительного процесса, приведите пример.

Глава 2. Решение нелинейных уравнений с одной переменной

Решение нелинейных уравнений с одним неизвестным (одной переменной) является одной из важных математических задач, возникающих в различных разделах экономических и технических наук. В общем случае нелинейное уравнение с одним неизвестным можно записать в виде:

, (2.1)

где – некоторая непрерывная функция аргумента , имеющая ограниченную или неограниченную область определения.

Всякое число , обращающее функцию в ноль, называется корнем уравнения (2.1). Как правило, при решении научных и инженерных задач функция содержит ряд параметров и исследователя интересует поведение решений уравнения (изменение значений его корней) в зависимости от изменения параметров , . В таких случаях, не нарушая общности задачи, можно поменять местами неизвестное и любой из параметров , то есть решать уравнение относительно другой неизвестной величины.

Нелинейные уравнения с одним неизвестным подразделяются на алгебраические и трансцендентные (далее в тексте данные виды уравнений обобщены понятием нелинейных уравнений).

Уравнение (2.1) называется алгебраическим, если функция является алгебраической функцией . Алгебраическое уравнение всегда может быть представлено в канонической форме:

,

где – коэффициенты уравнения, а максимальный показатель степени – степень алгебраического уравнения.

Всякий многочлен степени имеет корней, действительных или комплексных. Комплексным называется число , где и – вещественные числа, а – мнимая единица, .

Если функция не является алгебраической, то уравнение (2.1) называется трансцендентным, причем в зависимости от вида оно называется тригонометрическим, логарифмическим, показательным. Например, , , . В некоторых случаях решение трансцендентных уравнений можно свести к решению алгебраических уравнений. Заметим, что уравнения и называются равносильными (эквивалентными), если множества их решений совпадают.

Методы решения нелинейных уравнений подразделяются на прямые (аналитические, точные) и итерационные (численные). Прямые методы позволяют записать решение в виде некоторого соотношения (формулы). При этом значения корней могут быть вычислены по данной формуле за конечное число арифметических операций. Подобные методы развиты для решения тригонометрических, логарифмических, показательных, а также простейших алгебраических уравнений.

Однако подавляющее большинство нелинейных уравнений, встречающихся на практике, не удается решить прямыми методами. Даже для алгебраического уравнения выше четвертой степени с целыми или вещественными коэффициентами не удается получить аналитическое решение в радикалах (в виде формулы с конечным числом арифметических действий). В таких случаях приходится обращаться к численным методам, позволяющим получить приближенные значения корней с некоторой заданной точностью. К таким случаям следует отнести также те, в которых формулы для получения точного решения существуют, но столь громоздки, что использование приближенных методов оказывается предпочтительным (например, решение алгебраических уравнений третьей, четвертой и последующих степеней).

При применении численных методов задача решения нелинейного уравнения разбивается на два этапа: локализация (отделение) корней, то есть нахождение таких отрезков на оси (в области определения функции), в пределах которых содержится единственный корень, и уточнение корней, то есть вычисление приближенных значений корней с заданной точностью. Фактически решить нелинейное уравнение (2.1) означает: установить, имеет ли оно корни, определить число корней, установить отрезки локализации корней и найти значения корней с заданной точностью.