4.3. ИДЕЯ АЛГОРИТМА

Для иллюстрации идеи алгоритма рассмотрим следующую простую задачу

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

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

Самый лучший из возможных алгоритмов для задачи (4.1) использует функцию

При этом задача решается за один шаг.

Другой алгоритм этого же типа использует функцию

Если отправляться от точки 2, то получается последовательность Для этого алгоритма благодаря соотношению в каждой итерации следующей точкой является расстояния, оставшегося

до нуля, и алгоритм сходится, так как пределом последовательности является оптимальная точка

Отображения точка—множество. Рассмотренный выше класс алгоритмов, которые используют функцию для рекурсивного процесса, не является достаточно общим потому, что функция требует, чтобы была единственной точкой в пространстве V. Более общий класс алгоритмов для рекурсивного процесса использует точечно-множественное отображение в котором образ любой точки является подмножеством V.

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

Пусть дано точечно-множественное отображение Тогда, если дана точка то последующая точка При этом в качестве последующей точки можно выбирать любое

В качестве примера рассмотрим точечно-множественное отображение где

Здесь может быть или или любая другая точка из Другой пример, где отображение имеет вид

Здесь также может быть любой точкой из

Если дано точечно-множественное отображение для любой точки представляет собой единственную точку в V, то это отображение сводится к точечно-точечному отображению — к функции. Действительно, если А — функция, например то мы можем определить эквивалентное точечно-множественное отображение: . В последующих рассмотрениях часто функция будет интерпретироваться как эквивалентное ей точечно-множественное отображение.

Автономные и неавтономные отображения. До сих пор отображения А для алгоритмов зависели только от точки 2. Такие отображения называются автономными. Часто отображения будут неавтономными в том смысле,

что они зависимы от номера итерации или же от предшествовавших точек Чтобы выразит эту зависимость от предыстории в явной форме, мы будем вместо А писать или

Когда предыстория может быть не учтена и отображение зависит только от 2, мы будем опускать нижний индекс и писать А или

Алгоритм. Теперь можно точно определить понятие алгоритма. Алгоритм — это итеративный процесс, состоящий из последовательности точечно-множественных отображений Если дана точка 21, то с помощью рекурсии где любая точка множества представляет собой возможную последующую точку строится последовательность точек

Отображения называются алгоритмическими отображениями. Если для всех то само А будет рассматриваться как алгоритмическое отображение. Первоначально мы рассмотрим алгоритмы, которые зависят от единственного автономного отображения А. Алгоритмы, отображения которых зависят от предыстории, рассмотрены в последующих разделах книги.

Пример. Вернемся к задаче (4.1). Пусть алгоритм определяется алгоритмическим отображением где

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

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

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