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

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

- рекурсивный алгоритм, реализующий в нек-ром топологич. пространстве 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.

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


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Смотреть что такое "ИТЕРАЦИОННЫЙ АЛГОРИТМ" в других словарях:

  • Алгоритм Штрассена — предназначен для быстрого умножения матриц. Он был разработан Штрассеном в 1969 году как обобщение метода умножения Карацубы на матрицы. В отличие от традиционного алгоритма умножения матриц (по формуле cik = Σaijbjk), работающего за время Θ(n³) …   Википедия

  • ЧЕБЫШЕВСКИЙ ИТЕРАЦИОННЫЙ МЕТОД — итерационный алгоритм нахождения решения линейного уравнения учитывающий информацию о принадлежности Sр(A) спектра оператора А нек рому множеству и использующий свойства и параметры многочленов, наименее отклоняющихся от нуля на множестве и… …   Математическая энциклопедия

  • Метод главных компонент — (англ. Principal component analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих областях,… …   Википедия

  • Истинное ортогональное разложение — Метод Главных Компонент (англ. Principal components analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих… …   Википедия

  • Метод Главных Компонент — (англ. Principal components analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих областях, таких как… …   Википедия

  • Преобразование Карунена-Лоэва — Метод Главных Компонент (англ. Principal components analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих… …   Википедия

  • Преобразование Кархунена-Лоэва — Метод Главных Компонент (англ. Principal components analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих… …   Википедия

  • Преобразование Карунена - Лоэва — Метод Главных Компонент (англ. Principal components analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих… …   Википедия

  • Преобразование Кархунена - Лоэва — Метод Главных Компонент (англ. Principal components analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих… …   Википедия

  • Преобразование Хотеллинга — Метод Главных Компонент (англ. Principal components analysis, PCA)  один из основных способов уменьшить размерность данных, потеряв наименьшее количество информации. Изобретен К. Пирсоном (англ. Karl Pearson) в 1901 г. Применяется во многих… …   Википедия

Книги



Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»