Лекция №9
3.9. Методы построения конечных алгоритмов.
В математике существуют итерационные вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Численный метод, в котором производится последовательное, шаг за шагом, уточнение первоначально грубого приближения называется методом итераций. Каждый шаг в таком методе называется итерацией.
Итерационные процедуры описывают бесконечный вычислительный процесс, К ним относятся задачи, связанные с вычислением сумм рядов, численным интегрированием, решением уравнений итерационными методами и т.п. Алгоритм, реализующий в чистом виде такую процедуру, не представляет практического интереса, так как он не обладает свойством результативности. Однако если процесс прервать искусственно, например, введя условие вида "Закончить вычислительный процесс, когда погрешность результата будет меньше некоторого заданного малого числа", то получится алгоритм вычисления с заданной погрешностью.
На этом принципе основан общий метод построения многих вычислительных процессов: строится бесконечный, сходящийся к некоторому решению процесс; он обрывается на некотором шаге и полученное значение результата принимается за приближенное решение рассматриваемой задачи. Очевидно, что точность полученных результатов в такой вычислительной процедуре зависит от числа шагов. При этом возникает проблема, связанная со способом определения текущей пегрешности (обозначим ее ЕТ).
Замечание. При проведении расчетов на ЭВМ с использованием вещественных чисел результаты вычислений всегда получаются приближенными. Это связано с наличием погрешности округления Е0 вещественных чисел, обусловленной конечной длинной мантиссы. Погрешностью Е0 можно управлять путем изменения длины ячеек памяти, используемых для хранения переменных вещественного типа. Обычно эта погрешность настолько мала, что ею можно пренебречь. Поэтому при рассмотрении указанных выше алгоритмов нас будет интересовать только текущая погрешность, обусловленная методом решения задачи.
Различают два типа циклических процессов: арифметические и итерационные. Арифметическим называется циклический процесс для которого заранее известно количество циклов. К итерационным относятся циклические процессы, для которых заранее неизвестно, сколько циклов надо выполнить, и только в процессе выполнения цикла выясняется, когда он закончится. Алгоритмы, использующие принудительное окончание вычислительного процесса по текущей погрешности, реализуются в виде итерационных циклических процессов. Недостатком итерационного цикла является то, что он может потерять свойство конечности из-за ошибок в данных. Для повышения надежности программы в подобных циклах необходимо предусматривать средства контроля количества циклов.
С этой целью обычно итерационный цикл преобразуют в арифметический путем ограничения количества циклов достаточно большим числом. Если решение не будет найдено за установленное максимальное число шагов, то цикл завершается и вырабатывается признак ошибки. Этот признак можно использовать для принятия решения о дальнейшем ходе вычислительного процесса и, в частности, для вывода соответствующего диагностического сообщения.
Пусть ЕЗ – заданная погрешность. Тогда итерационный цикл прекращаем как только выполнится условие
| ЕТ | < | ЕЗ | .
При этом возникает проблема – как определить текущую погрешность ЕТ . В данном случае возможны две ситуации.
Ситуация 1 – для вычисления ЕТ известна аналитическая формула. Такая ситуация имеет место, в частности, при вычислении сумм рядов и решении нелинейных уравнений.
Ситуация 2 – нет аналитической формулы для определения текущей погрешности. Такая ситуация имеет место при численном расчете интегралов, численном решении дифференциальных уравнений и т.п. В этом случае можно использовать алгоритмический метод определения ЕТ, а именно, в качестве текущей погрешности брать разность значений искомой функции на двух соседних итерациях, то есть итерационный процесс продолжать до тех пор пока не выполнится условие
ЕТ = | YK+1-YK| < EЗ,
где к – номер итерации.