Глава 3 построение моделей систем 53

3.1.Понятие модели системы 53

3.2.Способы описания систем Модель черного ящика 54

3.3.Анализ и синтез - методы исследования систем 60

Глава 4 ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ - МЕТОД ПРОВЕДЕНИЯ СИСТЕМНЫХ ИССЛЕДОВАНИЙ 67

Глава 5 75

ТЕОРИЯ ПОДОБИЯ - МЕТОДОЛОГИЯ ОБОСНОВАНИЯ ПРИМЕНЕНИЯ МОДЕЛЕЙ 75

[р,:і=ша'[лр'[м]\ 80

[c]=[Mf[Lfm\ 80

7С, = : : 81

7С, = 81

р. 85

шр = J Ч(к^к 85

°р = J K2Zp(K)^K-Wp2, 85

ZprCO= JJ /, (*,)/2 (f2Vfc1A1 = 86

Глава 6 92

ЭКСПЕРИМЕНТ - СРЕДСТВО ПОСТРОЕНИЯ МОДЕЛИ 92

Глава 7 110

ПАРАМЕТРИЧЕСКИЕ МЕТОДЫ ОБРАБОТКИ ЭКСПЕРИМЕНТАЛЬНОЙ ИНФОРМАЦИИ 110

1Lt, 128

Ь, = (в, Ґ 138

мм>.го>=П[ j*-JШГ 152

^,B)= ртам, 170

J p*~m+I(l-p)mdp 175

J pk-m(l-p)mdp 175

т{т'у>’шга«~кг‘щцтг- 210

241

AJ 241

=0=8= - A 283

8^==8 •■• ^8 - *8= •■ 287

Для того чтобы процедура вычисления была реализуема, необхо­димо, чтобы интегрируемая функция была ограничена и убывала на гра­ницах интегрирования. Изложение способа замены бесконечного пре­дела конечным числом покажем на примере одного из пределов. Для других случаев процедура вычисления будет аналогичной. Нарис. 12.2. видно, что функция стремится к нулю при стремлении аргумента к бес-

4. Методы поиска оптимального значения функции

Рис. 12.2. Замена бесконечности в пределе интегрирования конечным числом

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

Для определения числа Вна первом этапе необходимо попытаться оценить максимальное значение интегрируемой функции, которое она принимает на интервале интегрирования. Пусть это значениеравно f_mm. Предположим, что данное значение функция приобретает в точке х₀. Далее зададимся числом6, которое будет определять точность прове­дения вычислений, обычно это малое число. Например,5 = IO'⁴- IO'⁶. Определим значение функции, ограничивающее процесс вычисления.Z_maxS. Значениями функции, оказавшимися меньше данного значения, пренебрежем. На следующем этапе необходимо найти такое минималь­ное значение аргумента х*,для которого будет выполняться условие

/(**) ^/„J*- (12.19)

Для этого необходимо, задаваясь некоторым шагом Ах, двигаться в сторону уменьшения интегрируемой функции (в случае, представлен­ном на рис. 12.2 необходимо двигаться вправо), вычисляя в каждой точке значения интегрируемой функции и сравнивая результат вычисления/(X_j) со значением, ограничивающим процесс интегрирования/_тах5. Пер­вое значение аргумента, для которого будет выполнено соотношение

19. , принимается в качестве верхнего предела интегрирования ус­ловно заменяющего бесконечность, т.е.х’=В.Определение нижнего предела интегрирования осуществляется аналогично, с той лишь раз­ницей, что движение осуществляется влево от точки максимума функ­ции. Если интегрируемая функция отрицательна, определяют ее мини­мум и осуществляют движение в сторону ее увеличения, соответственно вправо или влево, в зависимости от того, какой предел подлежит опре­делению.

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

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

Метод деления отрезка пополам. Простейшим методом мини­мизации функции одной переменной, не требующим вычисления произ­водной, является метод деления отрезка пополам. Рассмотрим данный метод. Будем предполагать, что минимизируемая функцияF(x) унимодаль­на на рассматриваемом отрезке[а, Ь].Поиск минимума на [а,Ь\начи­нается с выбора двух точек х,= (а+ Ъ-8)/2 иX₂ = (а+ Ъ+ 8)/2, где8 - постоянная, являющаяся параметром метода,0 <8 < b - а.Вели­чина8 является параметром, определяющим точность решения. Точ­ки X,иX₂ располагаются симметрично на отрезке[а, Ь\относительно его середины и при малых5 делят его почти пополам. После выбора точекX₁ и х₂вычисляют значенияF(X₁) иF(X₁) и сравнивают их между собой. ЕслиF(X₁) <F(X₂), то полагаюта,= а, Ь_{ -х₂; еслиF(X₁) >F(X₂), тоа,=X₁, ^_i= Ь.ПосколькуF(x) унимодальна на [а,Ь],ясно, что точка минимума попадет на отрезок[а_р6,]. Длина этого отрезка будет равна

Ь₁-а₁= (Ь-а-5)/2 + 5 .

Данная процедура повторяется до тех пор, пока не будет достигну­та заданная точность решения. При этом на к-ишаге точки для нового разбиения интервала выбираются по правилуX_{2t l} = (а_к1+ Ь_ы- 8)/2,^xIк ⁼ (^ак-1 ⁺ ^k i ⁺ &У2, к > 2. Далее вычисляются значения функции в этих точкахF(x_lk,)иF(X₁₁). Затем определяются точки нового интер­вала. ЕслиF(X_{lk l}) < F(x_lk), то полагаема_к= а_кЛ, Ь_к= х_2к,если же

F(^x2k-\) ^>F(^xu)> ^t0 полагаемa = x_2lx, b_k = b_kr Полученный отрезок срав­нивается с параметром, задающим точность вычисленияЪ_к - а_к<е. Если данное неравенство удовлетворяется, процесс вычисления оста­навливают. Следует отметить, чтоє >5; можно привести также сле­дующие соотношения: количество разбиений определяется числомк >log₂((6 -а-5)/(е-8)). Поскольку каждое деление пополам требу­ет двух вычислений значений функции, то для достижения заданной точ­ности требуетсяп = 2к>2log₂((Z> -а-8)/(є -8)) таких вычислений.

После определения отрезка [а_к,в качестве приближения к зна­чению аргумента, в котором функция принимает минимальное значе­ние,можновзять точкуX_n = X_{2k l} приF(X_{2k l}) < F(x_lk) иX_n = х_2кприF(X_2k ) >F(x_u), а значениеF(x_n) может служить приближением для ис­комого минимального значения. Точность приближения в данном слу­чае может быть оценена выражением(Ь-а)2~^п11л.Однако существу­ют методы, которые за такое же количество итераций позволяют полу­чить решение с большейточностью. Однимиз таких методов являет­ся методзолотого сечения.

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

Золотое сечение отрезка [а, Ъ\производится двумя точками

X₁ = а +(3-л/5)(Ь-а)/2

и

х₂ =а + (у/5-1)(Ь-а)/2,

расположенными симметрично относительно середины отрезка, причем

а< х₍< х₂<Ь.

Следует обратить внимание на одно обстоятельство, а именно то, что точка X₁, в свою очередь производит золотое сечение отрезка[а, х₂], аналогично точка х₂ производит золотое сечение отрезка[х , Ъ\. Используя данное свойство золотого сечения, разработан следующий метод минимизации унимодальной функции на отрезке[а, Ь].На пер­вом этапе производят золотое сечение указанного отрезка и вычисля­ют значения минимизируемой функции в точкахх , х₂: F(X₁) иF(X₁). Далее, еслиF(X₁) <F(x₂), то за новый отрезок принимается[а,х₂], т.е.я, = а, = х₂, еслиF(X₁) > F(x₂), тоа_х = X₁, Ъ_х = Ь. Затем процесс деле-388 ния отрезка методом золотого сечения продолжается и вычисляются значения минимизируемой функции в каждой новой точке. Данная про­цедура выполняется до тех пор, пока не получим на некотороми-м шаге отрезокЬ_п- а_п<є, гдеє - заданная точность. В качестве решения выбирают значение функции, удовлетворяющее условию

F(x') = min(F(a_n),F(b_n)).

На этом процесс минимизации унимодальной функции заканчивается.

Метод прямого поиска. Рассмотрим еще один метод определе­ния оптимального значения унимодальной функции на отрезке [а, Ь\и нахождения значения аргумента, соответствующего оптимальному зна­чению. В отличие от предыдущих случаев рассмотрим поиск макси­мального значения. Суть метода заключается в следующем. На пер­вом шаге необходимо определить направление поиска оптимального значения функции. Для этого произвольным образом выбираем две точ­киX₁ и х₂(рис.12.3), в этих точках вычислим значения оптимизируе­мой функцииF(X₁) иF(x₂). Затем сравним вычисленные значения друг с другом. ЕслиF(X₁) < F(x₂) и при этомX₁ > х₂, то двигаться в поиске максимума необходимо влево, еслиF(x_f) >F(x₂) при том же соотноше­нии между аргументами, то двигаться необходимо вправо. Положим, чтоX₁ -х₂ = Ах. ПустьF(X₁) < F(x₂) так, как показано на рис.12.3. Тог­да максимум функции находится слева от точких₂. Находим точкух₃ следующим образомх₃ = х₂ -Ax и вычисляем значение функции в данной точкеF(x₃). Сравним значения функций между собой. Если вы­полняется неравенствоF(X₂) < F(X_j), то продолжаем двигаться в том же направлении. Пусть путем описанных вычислений достигнута точ-

Рис. 12.3. Метод прямого поиска оптимального значения функции

ка х._+гВычисляем значение функции в данной точке и проводим срав­нение со значением в предыдущей точке, получаемF(x) > F(x._+l). Ре­зультат сравнения показывает, что в неравенстве знак поменялся на обратный. Это говорит о том, что в процессе вычислений значение максимума функции осталось справа, т.е. его проскочили. В этом слу­чае необходимо изменить величину шага и поменять направление дви­жения. ПоложимAx = -Ах/2и определим новую точкуx_j+2 = х._+]+ Ах. Поскольку новое значение шага берется с обратным знаком, движение теперь осуществляется в другую сторону, в данном случае вправо. Теперь движение в этом направлении продолжаем до тех пор, пока вы­полняется соотношениеF(X_j) <F(x_j+]). Как только в данном неравен­стве знак меняется на обратный, необходимо опять уменьшить шаг и изменить его знакAx - -Ax/2. Путем таких итераций процесс будет все ближе и ближе сходиться к точке, в которой функция имеет максималь­ное значение. Условием остановки процесса вычислений будет дости­жение заданной точности, которое можно сформулировать путем зада­ния соотношения\х_к+х -xj< є. Полученное значениех_к+хпринимается за аргумент, в котором функция достигает максимума, а значение фун­кции в данной точке за оценку максимального значения.

5. Методы прямого поиска решений уравнений

Рассмотрим задачу вычисления корней уравнения в случае, коща исследуемая функция в общем случае имеет трансцендентный вид. Относительно вида функции сделаем одно предположение: будем счи­тать, что функция монотонна на рассматриваемом участке. Пусть имеем уравнение

Fix) = 0. (12.20)

Такая запись имеет достаточно общий вид, например, если имеет­ся уравнение в виде/(х)= g(x), то перенося правую часть влево, при­ходим к выражению(12.20). Один из методов решения уравнений вида

19. - метод последовательных приближений - был рассмотрен в п. 12.2. В методе последовательных приближений делалось предполо­жение относительно дифференцируемости функции. В излагаемом ме­тоде такого предположения делать не будем.

Итак, изложим метод поиска решения уравнения, аналогичного методу поиска оптимального значения функции, рассмотренного в пре­дыдущем параграфе. Пояснение метода поиска решения показано на рис. 12.4.

Рис. 12.4. Метод прямого поиска решений уравнений

На первом шаге произвольно выбираем точку X_i и вычисляем зна­чение функцииF(x_f). Вначале определяем квадрант, в который попало вычисленное значение функции. Пусть получили, как изображенонарис.

4. я,>0, значение функции также больше нуля. Далее выбираем шаг, с которым будем осуществлятьпоиск решения, и вычисляем точкуX₂: х₂= X₁ -Ах.В этой точке также вычисляем значение функцииF(X₂). Далее определяем направление поиска решения. Если значение функ­ции в точкеX₂ больше чем в точкеX₁, то пересечение функции сосью ординат будет находиться справа от первоначально выбранной точки. Соответственно двигаться в поиске решения необходимо вправо. Если же значение функции в точкеX₂ меньше чем в точкеX₁, то пересечение функции с осью ординат будет находиться слева от первоначально выб­ранной точки. И, следовательно, двигаться в поискерешения необхо­димо влево, так, как это изображено на рис.12.4. Определив направле­ние поиска, осуществляем движение с шагомAx до тех пор, пока зна­чение функции не станет меньше нуля, т.е. пока функция не изменит свой знак. Как только произошло изменение знака функции на противополож­ный (точка х₍₊₁) необходимо изменить направление движения, при этом необходимо также изменить шаг, с которым осуществляется поиск ре­шения:Ax = -Ах/2.Теперь начинаем двигаться в противоположную сторону с меньшим шагом. Движение в эту сторону также идет до тех пор, пока значение функции не изменило свой знак. Как только произошло изменение знака функции, необходимо снова изменить направление по­иска решения и уменьшить шаг. Ясно, что в процессе такого поиска решение все ближе и ближе сходится к нулю. Условием остановки про­цесса вычислений будет достижение заданной точности, которое мож­но сформулировать путем задания соотношенияIx_fcfl -x_t| <є. Осуще­ствляя данную процедуру, находим решение уравнения(12.20).

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

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

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

а) имеется опасность замены исходной задачи задачей, не имею­щей отношения к исходной постановке;

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

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