Размещено на http://www.allbest.ru/

Содержание

• Введение
• 1. Методы расчета процессов кристаллизации металлов и сплавов
• 2. Методы оптимизации
• 3. Практика организации и проведения вычислительных экспериментов
• 3.1 Сфера применения. Вычислительный эксперимент занимает промежуточное положение между натурным экспериментом и аналитическим исследованием
• 3.2 Цикл вычислительного эксперимента. В цикле вычислительного эксперимента можно выделить следующие этапы (рис.3.1)
• 3.3 Особенности программирования
• 4. Математические основы методов элементов конечных разностей и метода контрольных объемов
• 5. Методы решения задач вычислительной гидрогазодинамики
• Заключение
• 6. Результаты расчета
• Заключение
• Литература

Введение

Основная задача литейного производства - повышение эффективности производства и улучшение качества продукции.

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

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

Курсовая работа представляет собой работу студента, которая выполняется на основе теоретических и практических знаний, накопленных в процессе обучения по дисциплинам: "Математическое моделирование", "Компьютерное проектирование", "Детали машин", "Информатика" и т.д. Она позволяет привить студентам навыки и умения сбора, анализа, обобщения информации по данной предметной области, решения конкретной прикладной задачи с применением обоснованно выбранной компьютерной системы.

1. Методы расчета процессов кристаллизации металлов и сплавов

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

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

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

где J - скорость зародышеобразования;

- скорость роста кристаллов;

л агл - скорость роста кристаллов за счет агломерации;

л дробл - скорость дробления кристаллов.

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

1. определенное процентное содержание требуемого гран состава кристаллического продукта,

2. определенная чистота продукта, иначе минимальный процент примесей.

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

Скорость зародышеобразования можно описать двумя зависимостями: аналитической зависимостью (2) и функциональной зависимостью (3).

J = K (C-C0) ^m (2)

где К, m - постоянные, зависящие от физико-химических свойств растворенного вещества и растворителя, например, таких как произведение валентностей ионов вещества, число молекул кристаллогидратной воды, тип кристаллической решетки и т.д.;

С0 - абсолютная растворимость вещества, или концентрация пересыщенного раствора для данных условий;

С - действительная концентрация вещества в пересыщенном растворе.

(3)

где П_с = С - Со = f (C, Со) - величина пересыщения,

П_t = (t_нас - t_д) = f (t_нас,t_д) - величина переохлаждения,

t_нас - температура насыщения раствора;

t_д - действительная температура при данном пересыщении (температура раствора);

П_c (ц) = f (t_р, Со, П_вал., М_квg, КР) - устойчивость пересыщения;

t_p - температурный коэффициент растворимости;

П_вал - произведение валентностей ионов составляющих соль;

М_квg - число молекул кристаллогидратной воды;

КР - тип кристаллической решетки;

t0C = tд - температура раствора;

И_пр - количество и физико-химические свойства примесей, снижающих качество продукта, а, следовательно, влияющих на надежность процесса;

V_пер - скорость перемешивания.

трехмерное моделирование литейный процесс

Скорость роста кристаллов является функцией устойчивости пересыщения, скорости перемешивания раствора и его температуры, скорости инкрустации, если она имеет место, а также количества и свойств примесей.

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

(4)

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

Скорость перемешивания V_пер раствора как один из параметров процесса кристаллизации, влияет на скорость диффузии вещества из раствора к граням кристалла Д, а это, в свою очередь, влияет как на скорость роста, так и на форму кристаллов.

Л.А. Разумовский использует в своей работе [2] для описания кинетики роста среднего кристалла следующее уравнение:

(5)

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

Взаимосвязьопределяет основное условие надежности процесса по показателю "размер кристалла".

Согласно выводам Л.А. Разумовского [2] уравнение 5 в координатах

дает прямую линию, k = 3 и не зависит от режима работы кристаллизатора. Итак, один из показателей надежности процесса кристаллизации и работы кристаллизационного оборудования можно всегда поддерживать на должном уровне, зная время роста кристаллов до требующегося размера.

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

Уравнение, описывающее процесс инкрустации, запишется в виде функциональной зависимости:

F_инкр = f (П_t,V_пер,Q_пр, С_{т. ф)} (6)

где С_{т. ф} - комплекс величин, которые определяют пристеночный эффект.

С_{т. ф} = ц (Дt, x, о) (7)

Величина С_{т. ф} должна непосредственно отражать теплопроводность через слой l (пристеночаая зона), в котором проходит инкрустация.

Дt - градиент температур в пристеночной зоне;

х - координата фронта охлаждения;

о - положение границы раздела фаз;

д - толщина стенки;

t_д > t_{воздуха}; t0С = t_ж = t2; t_ст = t_т = t1

Класс задач, связанный с фазовыми превращениями с выделением тепла или его поглощением (это характерно для процесса ивкрустации), относится к типу задач Стефана. Такая задача формулируется как задача о сопряженности температурных полей двух фаз (1 - твердой, 2 - жидкой) при наличии особого граничного условия на движущейся границе раздела фаз (уравнения 12, 13). Решение приведенной задачи (8 - 13) в данной математической постановке предложено В.Т. Меламедом [1], который учитывал теплоту фазовых превращений в виде непрерывно распределенных на фронте кристаллизации источников тепла. Это особый метод решения, т.к. условие на границе фаз (8,9) относит задачу Стефана к классу нелинейных и решить её обычный путем не представляется возможным. Уравнение теплопроводности:

Дополнительные условия:

где а1, а2 - температуропроводность соответственно твердого и жидкого слоев;

л - теплопроводность;

Q - количество теплоты кристаллизации в 1 м3;

т - время кристаллизации.

В функциональной зависимости (1) одним из аргументов роста кристаллов является л_агл, т.е. параллельно основному процессу - росту кристаллов, увеличение их размеров может происходить еще за счет агломерации кристаллов.

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

В общем виде скорость процесса агломерации можно выразить следующим уравнением:

(14)

где И_пер - интенсивность перемешивания;

т - время кристаллизации (среднее время пребывания кристалла в слое);

V_t - скорость охлаждения раствора;

d_о, V - размер (средний диаметр, объем) соответственно зародыша и кристалла;

у - поверхностные силы натяжения;

С_кр - концентрация кристаллов в слое.

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

л_дробл = f (V_пер, V_t, V, С_кр,T) (15)

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

Итак, анализируя уравнение скорости выхода годной продукции (1) можно установить следующее:

Не все величины, входящие в это уравнение, оказывают положительное воздействие на процесс кристаллоращения и степень их влияния не одинакова.

Такие факторы, как наличие примесей Q_пр, протекание процессов дробления л_др и инкрустации F_инкр оказывают полное отрицательное воздействие на основной процесс, то есть снижают его надежность пропорционально величинам Q_пр, л_др, F_инкр.

Такие параметры, как М_квд, t°С, V_пер, т, С_кр и процесс агломерации Х_агл, могут оказывать нежелательное воздействие на основной процесс, если не поддерживать их на оптимальном уровне.

2. Методы оптимизации

Методы условной оптимизации

Вначале рассмотрим методы поиска min f (x1,…,xn) при условиях (2.1).

Постановка задачи: Найти вектор, доставляющий минимум функции f (x1,x2,…,xn) при условиях, j=1,2,…,m. Другими словами, см. рисунок 2.20, требуется найти точку, в кото-рой функция f (x1,x2,…,xn) достигает минимума, но эта точка должна при-надлежать области D значений x1,x2,…,xn, в которой справедливы все ограничения (2.1). Число ограничений m может быть как больше, так и меньше числа переменных n (рисунок 2.2).

Рисунок 2.1 Иллюстрация к постановке задачи условной оптимизации

Рисунок 2.2 а) пять ограничений вида aix1+bix2+ci ? 0 б) одно ограничение вида

(x1-a) 2+ (x2-b) 2-r2 ? 0

Наиболее популярными методами поиска min f (x₁,x₂,…,x_n) при условиях (2.1) являются методы штрафных функций, прямого поиска с возвратом, возможных направлений, случайных направлений, сравнения значений функции на сетке значений аргументов.

Метод штрафных функций

Рисунок 2.3 Идея метода штрафных функций

Идея метода (рисунок 2.3):

Наличие ограничений учитывается путем изменения целевой функции - введения в нее штрафа за нарушение ограничений.

Одним из методов безусловной оптимизации осуществляется поиск минимума функции

F (x₁,…,x_n) =f (x₁,…,x_n) + Ш (x₁,…,x_n), (2.2)

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

, j= 1,2,…,n.

Функцию штрафа обычно записывают в виде

Ш (x₁,x₂,…,x_n) = , (2.3), где

.

Если ограничение одно (m=1), то необходимо найти минимум функции

F (x₁,…,x_n) = f (x₁,…,x_n) + k [g (x₁,…,x_n)] ²,

где , >> 0.

В области D функция F (x₁,x₂,…,x_n) совпадает с функцией f (x₁,x₂,…,x_n) и процесс поиска ее минимума протекает так же, как и при отсутствии ограничений. В момент выхода за допустимую область функция Ш (x₁,x₂,…,x_n) изменяет направление градиента функции F (x₁,x₂,…,x_n) и осуществляется возврат в допустимую область (рисунок 2.4). Заметим, что возврат осуществляется не по нормали к линии ограничения, а под некоторым углом к ней в сторону уменьшения значений исходной целевой функции f (x₁,x₂,…,x_n).

Рисунок 2.4 Иллюстрация к алгоритму метода штрафных функций

При использовании метода штрафных функций очень важен правильный выбор значения . При слишком малом значении может быть найдена точка за пределами допустимой области, а при слишком большом - функция F (x₁,x₂,…,x_n) образует овраг вдоль поверхности g (x₁,x₂,…,x_n) =0. Метод не чувствителен к выбору начальной точки поиска: если она окажется за пределами допустимой области, то штраф будет включен сразу.

Наиболее популярный алгоритм метода штрафных функций предусматривает формирование функции Ш (x₁,x₂,…,x_n) в начальной точке и использование для поиска min F (x₁,x₂,…,x_n) метода градиента с постоянным шагом, где после каждого изменения значений x₁,x₂,…,x_n вновь формируется функция Ш (x₁,x₂,…,x_n).

Метод прямого поиска с возвратом

В области D допустимых значений аргументов поиск min f (x₁,x₂,…,x_n) осуществляется любым методом безусловной оптимизации (чаще всего используют метод градиента с постоянным шагом и наискорейшего спуска).

При нарушении в ходе поиска хотя бы одного из неравенств (2.1) поиск прекращается и осуществляется возврат в область D по направлению векторной суммы градиентов соответствующих функций .

Другими словами, возврат в область D выполняется по градиенту функции

G (x₁,x₂,…,x_n) =, (2.4)

где , т.е. значения параметров задачи изменяются следующим образом:

. (2.5)

Рисунок 2.5 Иллюстрация к методу прямого поиска с возвратом

Здесь - точка, в которой нарушаются ограничения, h - текущее значение шага поиска в области D. Дробление шага производится, когда значение функции в допустимой области увеличивается. Признак окончания поиска - выполнение неравенства h < . Так же, как и метод штрафных функций, метод прямого поиска с возвратом не чувствителен к выбору начальной точки поиска: движение из точки на рисунке 2.5 начнется сразу с применения формулы (2.5).

Рисунок 2.6 Прямой поиск с возвратом при ограничении x₂ x₂^max

На практике ограничения часто задаются в виде: .

При нарушении некоторых из них для возврата в область D по нормали к линии ограничения нет необходимости использовать соотношение (2.5) - достаточно уменьшить или увеличить соответствующие параметры на величину шага поиска (рисунок 2.6).

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

Алгоритм метода прямого поиска с возвратом предусматривает проверку выполнения ограничений (2.1) в начальной точке и после каждого изменения значений x₁,x₂,…,x_n. В случае невыполнения некоторых из них согласно (2.4) формируется функция G (x₁,x₂,…,x_n) и значения x₁,x₂,…,x_n изменяются в соответствии с соотношением (2.5) до тех пор, пока не будет обеспечено выполнение всех ограничений (2.1).

Метод возможных направлений.

Определения: а) _{0 -} конус допустимых направлений поиска min f (x₁,x₂,…,x_n) при условиях , j=1,2,…,m - все направления в окрестности текущей точки, не приводящие к выходу за область D; б) ₁ - конус подходящих направлений - все направления, вдоль которых функция f (x₁,x₂,…,x_n) убывает в окрестности текущей точки; в) ₀₁ - конус возможных направлений - пересечение конусов допустимых и подходящих направлений (все направления, вдоль которых функция f (x₁,x₂,…,x_n) убывает при выполнении ограничений).

Для любой точки (x₁,x₂,…,x_n), лежащей на поверхности ограничений, в центре конуса ₁ находится вектор [ - grad f (x₁,x₂,…,x_n)], в центре конуса ₀ - вектор gradG (x₁,x₂,…,x_n) (функция G (x₁,x₂,…,x_n) формируется согласно (2.4)). Центру конуса возможных направлений будет соответствовать векторная сумма [-grad f (x₁,x₂,…,x_n)] и gradG (x₁,x₂,…,x_n), т.е. направление

, i= 1,…,n (2.6)

В точке условного минимума функции , см. рисунок 2.26, конусы допустимых и подходящих направлений не пересекаются, т.е. ₀₁ = Ш: векторы [-grad f (x₁,x,…,x_n)] и gradG (x₁,x₂,…,x_n) лежат на одной прямой и направлены в противоположные стороны.

Алгоритм поиска условного минимума функции f (x₁,x₂,…,x_n) методом возможных направлений сводится к следующему: из начальной точки внутри области D осуществляется поиск min f (x₁,x₂,…,x_n) любым методом безусловной оптимизации (более предпочтителен метод градиента с постоянным шагом); при выходе за пределы области D поиск с предыдущей точки ведется в направлении, определяемом формулой (2.6); дробление шага поиска осуществляется, когда движение в центре конуса возможных направлений приводит к возрастанию целевой функции, либо когда первый же шаг в этом направлении приводит к нарушению ограничений; окончания поиска - при выполнении неравенства h <.

Рисунок 2.7 Иллюстрация к методу возможных направлений

Замечания:

1. Величина шага поиска в направлении, определяемом (2.6), должна быть постоянной (равной h), т.е. значения переменных x₁,x₂,…,x_n следует изменять в соответствии с выражением

, i=1,…,n; k=0,1,…, (2.7)

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

2. Метод возможных направлений чувствителен к выбору начальной точки поиска за - пределами области допустимых значений параметров x₁,x₂,…,x_n возможные направления отсутствуют и алгоритм метода неработоспособен.

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

В заключение остановимся на методике поиска экстремума функции многих переменных при наличии связей

Постановка задачи: Найти вектор X^* = (x₁^*,x₂^*,…,x_n^*), доставляющий минимум функции f (x₁,x₂,…,x_n) при условиях (2.2), т.е. , k = 1,2,…,p.

Рисунок 2.8 Поиск min f (x₁,x₂) при условии h (x₁,x₂) =0

При решении подобных задач связи , k=1,…,p заменяются ограничениями

,k=1,…, р, (2.8)

см. рисунок 2.8, и задача решается методом штрафных функций, прямого поиска с возвратом или возможных направлений. Чем меньше значения _k, тем ближе решение новой задачи к исходной, но сложнее поиск. Обычно задают начальные значения _k, k=1,2,…, р (не слишком маленькие), находят решение новой задачи, а затем постепенно уменьшают _k, пока они не станут меньше заданной точности. Так же поступают со связями в случае решения задачи условной оптимизации при наличии и ограничений и связей.

Для нахождения начальной точки поиска, удовлетворяющей неравенствам (2.8), рекомендуется найти значения x₁,x₂,…,x_n, доставляющие минимум функции

.

Методы безусловной оптимизации

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

Требуется найти вектор = , доставляющий минимум функции с заданной точностью е, используя численный метод решения. Здесь . Отсутствие ограничений позволяет соотнести задачу с методами безусловной оптимизации.

Особенности поиска экстремума функции многих переменных

Задачи отыскания экстремумов в многомерном случае существенно осложняются. Возникают следующие качественно новые стороны рассматриваемой задачи:

1. Функция F (X) может иметь сложную форму. Для графической интерпретации поверхности принято изображать ее с помощью линий уровня. Линия уровня - это кривая в 2-х мерном сечении пространства параметров, значение функции, на которой константа.

Поверхность, соответствующая зависимости F (X) может иметь: "овраги" или "гребни" (поверхности уровня имеют структуру, сильно отличающуюся от сферической); "плато" (плоские горизонтальные участки); особые точки типа "седло".

Это не имеет себе аналогий в классе одномерных функций. ("Седло" - точка гладкой поверхности, вблизи которой поверхность лежит по разные стороны от своей касательной плоскости.

В окрестности седла имеются 4 интегральные кривые, которые входят в особую точку. Между ними располагаются интегральные кривые типа гипербол).

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

3. Переменные х₁, х₂,., х_n могут быть взаимосвязаны.

4. В многомерном случае область допустимых значений имеет бесчисленное множество форм.

Стратегия методов безусловной оптимизации

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

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

Большинство применяемых на практике прямых методов решения задач математического программирования являются итеративными.

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

Общее правило построения последовательности численными методами безусловной оптимизации записывается в виде:

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

Стратегия предполагает на очередной итерации следующие шаги:

1. Задание начальной точки поиска, из которой производится спуск к минимуму.

2. Выбор направления поиска очередной точки (на основании исследования локальных свойств целевой ф-ии).

3. Выбор величины шага до новой точки вдоль выбранного направления.

4. Переход в очередную точку итерационного процесса.

5. Проверка критерия окончания итерационного процесса.

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

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

Критерии для завершения поиска

На основании сравнения результатов расчетов двух или нескольких последовательных итераций. Наиболее распространены:

(норма разности 2 последовательных итераций)

(норма разности 2 последовательных значений критериев оптимальности)

(модуль градиента этого критерия)

(1) - недостаточна, т.к. функция может иметь поведение типа скачка (резкое изменение критерия оптимальности).

(2) - основана на предположении монотонного убывания величины в зависимости от числа итераций. При пологом характере F (X) вблизи оптимума, разность может мало меняться даже при большом шаге, поэтому (1) + (2).

(3) - характеризует скорость убывания критерия оптимальности и обращается в нуль в точке локального минимума. Поэтому по этой скорости можно судить о приближении к оптимуму.

Оценка эффективности методов оптимизации

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

1. Точность поиска - значение окрестности локального оптимума, в которую приводит алгоритм после выполнения заданного числа итераций.

2. Скорость сходимости - число итераций, необходимое для достижения заданной точности.

3. Время счета - время поиска на ЭВМ локального оптимума с заданной точностью, отнесенное к коэффициенту сложности задачи (или к быстродействию ЭВМ).

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

5. Надежность - свойство алгоритма приводить к оптимуму при многократном повторении поиска из разных начальных точек.

Для сравнения алгоритмов по этим критериям следует производить расчеты в одинаковых или близких условиях.

Классификация методов на основании порядка производных при выборе направления

1) методы нулевого порядка - используют лишь значения функции;

2) методы первого порядка - используют значения функции и векторы первых производных;

3) методы второго порядка, в которых определяются матрицы вторых производных;

4) методы более высоких порядков обычно не применяются.

Классификация методов на основании выбора метода аппроксимации целевой функции

1) линейные методы, в которых используется локальная аппроксимация функции в окрестности точки линейным полиномом с помощью вектора - градиента F^/ (X);

2) квадратичные методы, в которых принята локальная квадратичная аппроксимация с помощью F^/ (X) и матрицы вторых производных F ^{// (}X);

Методы нулевого порядка

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

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

1. Метод покоординатного спуска (Гаусса-Зейделя).

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

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

Направления, конечно, фиксированы.

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

.

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

2. Метод Розенброка

Метод Розенброка направлен на ликвидацию одного из недостатков метода покоординатного спуска - высокую чувствительность к выбору системы координат. Метод сводится по сути к отысканию "удачной" системы координат путем поворота исходных осей координат. После чего осуществляется поиск поочередно по всем переменным последовательно. Первый цикл поиска совпадает с Г. - З. А далее поворот в зависимости от вектора смещения точки поиска.

3. Симплексный метод (метод деформируемого многогранника)

Симплексом в n - мерном пространстве называют фигуру, содержащую n+1 вершину. На плоскости - треугольник, в трехмерном пространстве - тетраэдр и т.д. Если все вершины симплекса равно удалены друг от друга, то такой симплекс называется регулярным. В организации алгоритма поиска используется важное свойство симплекса: против каждой вершины находится одна грань.

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

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

4. Метод параллельных касательных

Из двух произвольных точек, не лежащих на одной прямой заданного направления, проводят два спуска по направлению и находят две точки оптимума (х11, х21).

Далее оптимум (х31) ищут на прямой линии, соединяющей эти точки. Во всех поисках по направлению могут применяться любые одномерные методы поиска. Затем - в направлении прямой (х11, х31),….

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

Градиентная оптимизация

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

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

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

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

Показано, что значение можно определять по некоторым характеристикам функции f (x). Например, если существует такая константа R, что для любых точек

Если известна оценка М сверху максимального собственного числа матрицы , то рекомендуется принять .

Однако, значения R и M обычно заранее неизвестны.

Разработаны различные методы, относящиеся к группе градиентного спуска. Среди них: с постоянным шагом, с дробным шагом и наискорейшего спуска.

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

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

В этом методе направление из касается линии в

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

Все градиентные методы плохо работают в овражных функциях.

Условия окончания итерационного поиска в градиентных методах связывают обычно с величиной градиента (критерий с номером 3).

Градиентные методы относятся к группе методов 1 порядка, т.к. опираются на вычисления первой производной. Более эффективными могут быть методы второго порядка, которые в том числе используют вторые производные. Однако, здесь могут возникнуть трудности с вычислением и исследованием матрицы вторых производных (матрицы Гессе).

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядков с исключением их недостатков.

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

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

Для квадратичной функции (очень эффективен) значение оптимума этим методом можно получить за n шагов, где n - размерность задачи.

Метод тяжелого шарика

Метод базируется на аналогии с движением тяжелого материального шарика по наклонной поверхности.

Скорость шарика при движении вниз будет возрастать, и он будет стремиться занять нижнее положение, т.е. точку минимума.

X_i+1 = X_i - (X_i - X_i-1) - h gradF (X_i)

При = 0 - метод превращается в обычный градиентный. При 0 < < 1 можно получать различную эффективность метода, которая будет зависеть и от h. Вдали от оптимума поиск будет ускоряться, а вблизи возможны колебания около минимума.

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

Метод Ньютона

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

Метод случайного поиска

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

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

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

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

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

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

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

- относительное время.

3. Практика организации и проведения вычислительных экспериментов

Вычислительный эксперимент - метод изучения устройств или физических процессов с помощью математического моделирования. Он предполагает, что вслед за построением математической модели проводится ее численное исследование, позволяющее "проиграть" поведение исследуемого объекта в различных условиях или в различных модификациях [Самарский, 1979; Горбунов-Посадов, 1990].

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

3.1 Сфера применения. Вычислительный эксперимент занимает промежуточное положение между натурным экспериментом и аналитическим исследованием

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

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

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

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

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

3.2 Цикл вычислительного эксперимента. В цикле вычислительного эксперимента можно выделить следующие этапы (рис.3.1)

Рис. 3.1 Этапы вычислительного эксперимента

Этап 1. Построение математической модели (составление уравнений, описывающих исследуемое явление).

Этап 2. Выбор численных методов расчета (построение дискретной модели, аппроксимирующей исходную математическую задачу, построение разностной схемы, разработка вычислительного алгоритма и т.д.).

Этап 3. Создание программы, реализующей вычислительный алгоритм.

Этап 4. Проведение расчетов и обработка полученной информации.

Этап 5. Анализ результатов расчетов, сравнение (если это возможно) с натурным экспериментом.

Обычно на последнем (5-м) этапе исследователь приходит к заключению о том, что необходимо внести определенные изменения в решения, принятые на этапах 1, 2 или 3.

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

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

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

3.3 Особенности программирования

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

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

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

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

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