ОПТИМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ

ОПТИМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ

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

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


наз. погрешностью метода тна классе задач Р, а


- оптимальной на классе Роценкой погрешности методов из множества М. Если существует метод такой, что


то этот метод наз. оптимальным. Такая схема рассмотрения проблемы О. в. а., восходящая к А. Н. Колмогорову [2], изучает множество задач вычисления интеграла


при условии - множество всевозможных квадратур ,


каждая квадратура задается совокупностью 2N чисел Cj и х j. Задача о минимальном количестве информации (см. [2], [3]), необходимой для запоминания функции из данного класса с требуемой точностью, также может быть уложена в эту схему. Рассматривается [4] более сложная постановка проблемы, где трудоемкость реализации алгоритма в определенном смысле увязывается с объемом используемой памяти. Оптимальные алгоритмы построены для незначительного числа задач типа [1].

Однако для большого числа вычислительных задач построены методы, по своим асимптотич. характеристикам близкие к оптимальным (см. [5]-[8]).

Исследование характеристик оптимальных на классах вычислительных алгоритмов решения задач (см. [5], [7]) складывается из двух частей: построение конкретных методов решения с возможно лучшими характеристиками и получение оценок снизу характеристик вычислительных алгоритмов (см. [2]-[4], [9]). По существу первая часть вопроса является основной проблемой теории численных методов и в большинстве случаев рассматривается независимо от проблемы оптимизации. Получение оценок снизу обычно сводится к оценке снизу e-энтропии или поперечников соответствующих пространств; иногда оно проводится независимо, но с использованием техники, аналогичной технике получения указанных оценок.

Вычислительные алгоритмы условно делят на пассивные и активные. В первом случае алгоритм решения задачи не зависит от получаемой в ходе решения задачи информации, а во втором - зависит. При вычислении интеграла используемая информация о функции есть обычно информация о ее значениях в Nточках. В случае пассивного алгоритма интеграл вычисляется по формуле


где веса С j и Pj из области W определения f задаются заранее. Активные алгоритмы вычисления интеграла укладываются в следующую схему: задается точка . и функции


гдо yj, SN- числа, . Последовательно вычисляют

f(P1), Р 2 = Ф 21; f(P1)), f(Р 2), Р 3 = Ф 31, Р 2; f(P1), f(P2)),..., f(PN).и полагают

I(f) SN(P1, ..., PN; f(P1), ..., f(PN).

В случае выпуклых классов подинтегральных функций, центрально симметричных относительно функции , оптимальная оценка на классе пассивных алгоритмов совпадает с оптимальной оценкой на классе активных алгоритмов (см. [10], [11]).

В практике численного интегрирования активные алгоритмы типа алгоритмов интегрирования с автоматич. выбором шага (см. [10]) показали свое превосходство над пассивными алгоритмами. Это подтверждает общепринятую точку зрения о том, что формальная схема О. в. а. зачастую не охватывает специфики реальных задач. При решении задач оптимизации (в частности, задач минимизации) пассивные алгоритмы практически не употребляются (см. [12], [13]). Выше за единицу трудоемкости алгоритма неявно принимается трудоемкость вычисления одного значения функции из нек-рого класса F. Возможны и другие подходы к оценке оптимальности характеристик алгоритма. Напр., за единицу трудоемкости принимается трудоемкость вычисления нек-рого функционала l(f).из множества функционалов L(f). В этом случае оценка снизу трудоемкости алгоритмов производится с помощью теории поперечников (см. [14], [15]). Трудоемкость алгоритма складывается не только из трудоемкости получения информации об исходных данных, но и из трудоемкости обработки полученной информации. В настоящее время, по-видимому, нельзя привести примеров классов реальных вычислительных задач, где бы были получены оценки снизу трудоемкости алгоритмов, отличные от информационных оценок рассматриваемого типа. Однако для ряда задач невычислительного характера такого типа оценки известны (см. Алгоритма сложность).

В случае, когда исследование проблемы О. в. а. имеет своей целью решение задач на ЭВМ, проблема О. в. а. приобретает дополнительные оттенки, связанные с устойчивостью алгоритма к вычислительной погрешности, с ограничением на объем разных видов используемой памяти (см. Вычислительный алгоритм). Выше задача О. в. а. рассматривалась как задача О. в. а. на классах задач. Существенный интерес для практики представляет задача О. в. а. на конкретной задаче (см. [10], [16]). Постановка проблемы оптимизации (см. [16]) заключается в следующем. Дифференциальное уравнение интегрируется методом Рунге - Кутта с переменным шагом. Производится оценка главного члена оценки погрешности. Затем эта оценка оптимизируется по распределению узлов интегрирования (при общем заданном числе узлов). Такой подход к проблеме оптимизации оказал существенное влияние на развитие теории и практики активных алгоритмов численного интегрирования.

Лит.:[11 Никольский С. М., Квадратурные формулы, 3 изд., М., 1979; [2] Колмогоров А. Н., "Докл. АН СССР", 1956, т. 108, № 3, с. 385-88;[3] Колмогоров А. Н., Тихомиров В. М., "Успехи матем. наук", 1959, т. 14, в. 2, с. 3-86; [4] Витушкин А. Г., Оценка сложности задачи табулирования, М., 1959; [5] Бабушка И., Соболеве. Л., "Aplikace mat.", 19B5, t. 10, s. 96-129; [6] Бахвалов Н. С., там же, 1968, t. 13, s. 27-38: [7] его же, в кн.: Международный конгресс математиков в Ницце. 1970. Доклады советских математиков, М., 1972, с. 27-33; [8] его же, в кн.: Численные методы решения дифференциальных и интегральных уравнений и квадратурные формулы, М., 1964, с. 3-63; [9] его же, "Матем. заметки", 1972, т. 12, в. 6, с. 655-64; [10] его же, Численные методы, 2 изд., М., 1975; [11] его же, "Ж. вычислит, матем. и матем. физ.", 1971, т. 11, № 4, с. 1014-18; [12] Уайлд Д.- Д ж ., Методы поиска экстремума, пер. с англ., М., 1967; [13] Васильев Ф. П., Численные методы решения экстремальных задач, М., 1980; [14] Оганесян Л. А., Руховец Л. А., Вариационно-разностные методы решения эллиптических уравнений, Ер., 1979; [15] Тихомиров В. М., Некоторые вопросы теории приближений, М., 1976; [16] Тихонов А. Н., Горбунов А. Д., "Ж. вычислит, матем. и матем. физ.", 1964, т. 4, № 2, с. 232-41. Н. С. Бахвалов.


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

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

  • ОПТИМИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОГО МЕТОДА — обычно то же, что оптимизация вычислительных алгоритмов. Иногда, однако, эти понятия трактуются различно. Напр., можно говорить об оптимальности конкретного сеточного метода решения краевой задачи на нек ром классе задач, имея в виду, что он… …   Математическая энциклопедия

  • Эксплуатация вычислительных комплексов — ЭКСПЛУАТАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ КОМПЛЕКСОВ, СИСТЕМ И СЕТЕЙ Содержание 1 Ввод 2 Системотехническое обслуживание 3 Настройка операционной системы …   Википедия

  • Бахвалов Николай Сергеевич — (р. 1934), математик, академик РАН (1991). Труды по дифференциальным уравнениям и вычислительной математике. Государственная премия СССР (1985). * * * БАХВАЛОВ Николай Сергеевич БАХВАЛОВ Николай Сергеевич (р. 1934), российский математик, академик …   Энциклопедический словарь

  • Бахвалов, Николай Сергеевич — (род. 29.5.1934) советский математик, чл. кор. АН СССР (1981). Род. в Москве. Сын С. В. Бахвалова. Окончил Моск. ун т (1955), д р физико матем. наук (1964), проф. (1965). С 1957 работает в МГУ. Осн. труды по теории дифференциальных ур ний,… …   Большая биографическая энциклопедия

  • Вычислительный центр им. А. А. Дородницына РАН — (ВЦ РАН) Международное название Dorodnicyn Computing Centre, RAS (CC RAS) Основан 1955 Директор ак. Ю. Г. Ев …   Википедия

  • Гибридный компьютер — У этого термина существуют и другие значения, см. Гибридная вычислительная система. Гибридный компьютер, гибридная вычислительная машина, аналого цифровая система  вид гибридной вычислительной системы (ГВС), сочетающий в себе свойства… …   Википедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

  • система — 4.48 система (system): Комбинация взаимодействующих элементов, организованных для достижения одной или нескольких поставленных целей. Примечание 1 Система может рассматриваться как продукт или предоставляемые им услуги. Примечание 2 На практике… …   Словарь-справочник терминов нормативно-технической документации

  • Генетический алгоритм — (англ. genetic algorithm)  это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих… …   Википедия

  • Gerasim@Home — Платформа BOINC Объём загружаемого ПО 2 МБ Объём загружаемых данных задания 1 КБ Объём отправляемых данных задания 150 КБ Объём места на диске 2 МБ Используемый объём памяти 10 МБ Графический интерфейс нет Среднее время расчёта задания д …   Википедия

Книги



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

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