Математический словарь
" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

ИТЕРАЦИОННЫЙ АЛГОРИТМ

Значение ИТЕРАЦИОННЫЙ АЛГОРИТМ в математической энциклопедии:

- рекурсивный алгоритм, реализующий в нек-ром топологич. пространстве Vпоследовательность точечно-множественных отображений Ak: V-> V, при помощи к-рых по начальной

точке вычисляют последовательность точек согласно формулам

Операцию (1) наз. итерацией, а последовательность uk- итерационной последовательностью.

И. а. (или методы последовательных приближений) применяют как для нахождения решения операторного уравнения

или минимума нек-рого функционала, или собственных значений и элементов уравнения Au=luи т. п., так и для доказательства существования решений этих задач. И. а. (1) наз. сходящимся при начальном приближении и 0 к решению иупомянутых задач, если

при

Операторы Ak для решения уравнения (2), заданного в линейном метрич. пространстве V, обычно строят по формулам

где Hk(V->V)- некоторая, определяющая тип И. а., последовательность операторов. В основе построения И. а. типа (1), (3) лежат или сжатых отображений принцип и его обобщения, или вариационные методы минимизации нек-рого связанного с задачей функционала. При этом используются различные методы построения операторов Ak, напр, варианты Ньютона метода, или спуска метода. Операторы Н k стараются выбрать так, чтобы быстрая сходимость uk к иобеспечивалась при условии, что численная реализация операции Akuk при заданном объеме памяти ЭВМ была достаточно проста, нетрудоемка по количеству операций и "устойчива к ошибкам округления.

Хорошо разработаны и исследованы И. а. решения линейных задач. И. а. делятся при этом на линейные и нелинейные. К линейным относятся, напр., Гаусса метод, Зейделя метод, верхней релаксации метод, И. а. с чебышевскими параметрами; к нелинейным - вариационные методы: наискорейшего спуска метод, сопряженных градиентов метод, минимизации невязок метод и т. д. Одним из эффективных И. а. является метод с использованием чебышевских параметров, когда А- самосопряженный оператор со спектром на отрезке [ т, М], где М>m>0. Этот метод дает оптимальную (при данной информации о границах спектра) оценку сходимости на заранее задаваемом N-м шаге. Записывается метод в виде

где

N-ожидаемое число итераций, в нем используется xN=(j1, j2, ..., jN)- специальная перестановка N-гo порядка, хорошо перемешивающая для устойчивости счета корни многочлена Чебышева. Для N=2n перестановку xN можно построить, напр., так: х 2=(1, 2), и если известна перестановка х 2i-1= (j1, j2, ..., i2i-1), то х 2i=(j1, 2i+1-j1, j2, 2i+1-j2, ...). При N=16 эта перестановка имеет вид: (1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11).

Существуют И. а., использующие rпредыдущих приближений и k, uk-1, ..., uk-r+1;они наз. r-шаговыми и обладают повышенной скоростью сходимости.

И. а. широко применяются при решении многомерных задач математич. физики, для нек-рых классов таких задач существуют специальные быстросходящиеся И. а. Напр., переменных направлений метод, метод, изложенный в [7] для эллиптических краевых задач, нек-рые методы для задач переноса частиц или излучений (см. [1] - [7]).

Лит.:[1] Канторович Л. В., Авилов Г. П., Функциональный анализ, 2 изд., М., 1977; [2] Коллатц Л., Функциональный анализ и вычислительная математика, пер. с нем., М., 1969; [3] Марчук Г. И., Лебедев В. И., Численные методы в теории переноса нейтронов, М., 1971; [4] Бахвалов Н. С, Численные методы, 2 изд., М., 1975; [5] Красносельский М. А. и др., Приближенное решение операторных уравнений, М., 1969; [6] Лебедев В. И., в кн.: Тр. института кибернетики АН УССР, К., 1972, с. 109- 135; [7] Федоренко Р. П., "Успехи матем. наук", 1973, т. 28, в. 2, с. 121 - 82.

В. И. Лебедев.