Основы теории оптимизации (стр. 89 )

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

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

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

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

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

Приложения

Приложение 1

Метод решения задача Коши

1.1 Постановка задачи

При решении многих задач естествознания в качестве математической модели ис­пользуется задача Коши для обыкновенных дифференциальных уравнений. Напри­мер задачи динамики системы взаимодействующих тел (в модели материальных точек), задачи химической кинетики, электрических цепей. Ряд важных уравнений в частных производных в случаях, допускающих разделение переменных, приводит к задачам для обыкновенных дифференциальных уравнений — это, как правило, краевые задачи (задачи о собственных колебаниях упругих балок и пластин, определения спектра собственных значений энергии частицы в сферически-симметричных полях и многие другие).

Мы ограничимся рассмотрением лишь задачи Коши. Полученная в общем случае задача для ОДУ (обыкновенных дифференциальных уравнений) с помощью замены переменных сводится к нормальной системе дифференциальных уравнений. Задача Коши для последней формулируется так:

Определить дифференцируемую функцию и(х), для которой

(1)

и выполнено начальное условие

и(х0) = и0. (2)

Здесь х0, и0 - заданные величины: и = { и1, и2, …, иN} - искомая вектор-функпия; — вектор правых частей. Относительно задачи (1-2) будем предполагать выполненными достаточные условия существования на отрезке |х — х0| < а решения и(х) задачи (1)-(2).

Эйлеру принадлежит идея и рассмотрение простейшего численного метода, осно­ванного на возможности получить разложение по формуле Тейлора для искомого решения и(х) в окрестности точки хп

(3)

где hn = xn+l - xn. При этом необходимые производные функции и(х) можно найти дифференцируя в силу уравнения (1) функцию f(x,u(x)) нужное число раз

(4)

Однако использовать разложение (3) с большим числом членов невыгодно: и из-за громоздкости формул (4), и из-за того, что, как правило, правая часть в (1) известна лишь приближённо и её явное численное дифференцирование нежелательно.

1.2 Метод Рунге-Кутта

Идея Рунге метода Рунге-Кутта состоит в том, чтобы используя метод неопределённых коэффициентов аппроксимировать с тем же порядком точности О(hsn) мно­гочлен Тейлора в формуле (3). Представим приращение функции и(х) в точке хп в виде

Обозначим текущий шаг hп≡h. Речь идёт об аппроксимации многочлена

с порядком О(hs). Ограничимся рассмотрением простейшего случая s=2. Тогда у многочлена первого порядка

необходимо со вторым порядком аппроксимировать производную и"п.

Пусть у(х) - приближенная функция, дающая такую аппроксимацию. Для аппроксимации производной df/dх мы используем разностное отношение с неопределенными пока х, у. В таком случае приращение функции у имеет вид

Здесь α, β, γ и δ — параметры, значения которых нужно определить. Разложим полученное приращение ∆уп в ряд по степеням h, получим

(*)

Выберем параметры α, β, γ и δ так, чтобы разложение для функции у с тем же по­рядком аппроксимировало разложение истинного решения и. Для этого приравнивая коэффициешы в главных порядках по h полученной формулы (*) и формулы (3), найдём

Выражая все параметры через α, получим однопараметрическое семейство двучлен­ных схем Рунге-Кутта второго порядка точности

(5)

где 0 < α ≤ 1.

Замечания:

1) Выбрать параметр α так, чтобы схема (5) давала бы аппроксимацию третьего порядка невозможной.

2) Приведем без доказательства теорему. Если f(x,и) непрерывна и ограничена вместе со своими вторыми производными, то решение, полученное по схеме (5), равномерно сходится к точному решению с погрешностью О(max h2п), т. е. двучленная схема Рунге-Кутта имеет второй порядок точности.

3) Формула (5) используется на практике обычно либо при α = 1, либо при α = 1/2. При α = 1 схема имеет особенно простой вид

(6)

Поясним её смысл. Сначала, вычислив наклон интегральной кривой уpaвнения (1) fn = f(xn,yn), делаем половинный шаг но схеме ломанных, т. е. по касательной данного наклона, и находим

Затем в найденной точке опреде­ляем наклон интегральной кривой

По этому наклону определяем приращение функции на целом шаге

Схемы подобною типа называют "предиктор-корректор".

Задача. Дать аналогичную интерпретацию случаю схемы с α = 1/2.

Метод Рунге-Кутта позволяет строить схемы различною порядка гочиосли. При аппроксимации многочлена Тейлора второго порядка

с точностью О(h3) получают наиболее употребительную схему четвёртого порядка точности (точнее семейство четырёхчленных схем указанного порядка точности)

(7)

Схемы Рунге-Кутта обладают важными достоинствами: все они имеют хорошую точность; они являются явными; допускают расчет с переменным шагом; легко обоб­щаются на случай систем дифференциальных уравнений. Имеено эти свойства осо­бенно ценны при расчетах на ЭВМ.

Рекомендации:

1) Если правая часть дифференциального уравнения (1) ограничена, вместе со своими производными до четвёртого порядка, то схема (7) дает хорошие результаты благодаря малому коэффициенту в остаточном члене и быстрому возрастанию точ­ности схемы при уменьшении шага. Если же указанных производных у правой части нет, то не худшую точность имеют схемы и меньшего порядка точности (5).

2) Шаг сетки при расчетах следуем выбирать настолько малым, чмобы обеспечить требуемую точность расчета. Других, ограничительных условий на шаг схемы в методе Рунге-Купа нет.

3) Выражения остаточных членов для формул Рунге-Купа достаточно громоздки, поэтому трудно получить априорную оценку точности метода, однако, про­водя расчеты на сгущающихся сетках, можно дать апостериорную оценку точности по методу Рунге.

Приложение 2

ЭЛЕМЕНТЫ ТЕОРИИ РАЗНОСТНЫХ СХЕМ

1. Метод конечных разностей в прикладных задачах

1.1 Общая постановка задачи

Универсальным методом приближённого решения, применимым для широкого кpyгa задач математической физики, является метод конечных разностей. Как правило задачи матаматической физики представляют собой системы нелинейных уравнений в частных производных, рассматриваемых в некоторой t-цилиндрической обласхи D: