Работа с программой EUREKA


Сдавался/использовался	1996г.
	Загрузить архив:
	Файл: eureka1b.zip (41kb [zip], Скачиваний: 82) скачать

Лабораторная работа N1

6───────────────────────────

Знакомство с оболочкой системы Eureka. Решение

систем линейных уравнений.

Цель работы

6────────────────

Приобретение навыков работы с оболочкой системы Eureka. Решение

систем линейных уравнений при помощи системы Eureka.

Теоретическое введение.

а) Интегрированная многооконная система Eureka предназначена для

автоматизации наиболее массовых математических расчетов не очень высо-

кой сложности. Она объединяет: редактор, вычислитель, верификатор

(проверяет правильность вычислений), генератор отчетов и простой гра-

фопостроитель. Система ориентирована на ПК класса IBM PC XT и AT и мо-

жет размещать на одном гибком диске с объемом хранимой информации до

360 Кбайт. Нормальная работа системы обеспечивается при ОЗУ 512 Кбайт

и выше. Система может работать на ПК без математического сопроцессора,

однако его использование значительно повышает скорость работы.

Eureka имеет следующие ограничения:

- максимальная длина идентификаторов до 40 символов, из них 10 яв-

ляются основными;

- число определенных пользователем функций не более 10;

- число используемых числовых констант не более 200;

- число переменных не более 12;

- число подстановок одних переменных в другие до 6.

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

все файлы, входящие в нее, на рабочий диск в одну директорию. Запуска-

ющим файлам системы является файл eureka.exe.

После запуска на экране монитора появляется табло оболочки систе-

мы. Экран оказывается разделенным на четыре окна.

Edit - для ввода и редактирования текста задачи;

Solution - для вывода результатов;

Report - для вывода отчета о вычислениях на экран, принтер или в

файл с расширением log;

Verify - для проверки точности результата.

Окно в пассивном состоянии обведено одинарной рамкой, а в актив-

ном - двойной. Курсор располагается в активном окне. Кроме окон, табло

оболочки содержит верхнюю и нижнюю строки меню. Нижняя строка меню

представляет возможности работы с ключевыми клавишами (hot keys). Ee

содержимое может менятся в зависимости от режима работы системы. Наи-

больший интерес эта строка представляет в режиме редактирования. В

этом случае она предлагает следующие команды:

F1 - Help - помощь по контексту (можно получать в любой позиции

меню и подменю);

F2 - Save - запись текущего файла на диск;

F3 - Load - загрузка файла с диска;

F5 - Zoom - расширение активного окна на весь экран и возвращение

его (при повторном нажатии) к исходным размерам.

F6 - Next - переключение активности окон (по циклу);

F7 - Beg.Bek - отметка начала блока;

F8 - EndBek - отметка конца блока

SCROOL - Size/move - изменение размера и положения окна.

Нажатие клавиши Ctrl и Alt приводят к высвечиванию иных ключевых

клавиш. Имеет смысл взять на вооружение еще hotkeys такие как:

Esc - отмена команды (переход в вышестоящее меню);

Alt+E - переход в окно редактирования;

Alt+S - начать рещение задачи;

Alt+C - включить встроенный калькулятор;

Alt+X - выход из системы.

В верхней строке оболочки перечисляются позиции основного меню

системы:

File - работа с файлами;

Edit - редактирование текущего файла;

Solve - запуск вычислителя;

Commands - выбор команды управления;

Report - подготовка отчета;

Graph - вывод графиков и таблиц;

Options - задание опций системы;

Window - работа с окнами.

Если активировать в верхней строке позицию File, то после нажатия

клавиши Enter откроется подменю со следующим пунктами:

Load - загрузка файла;

New - подготовка к заданию нового файла;

Save - запись текущего файла;

Directory - просмотр директории;

Change dir - смена текущей директории;

New directory - создание новой директории;

Rename - переименование текущего файла;

OS shell - временный выход в MS DOS (возврат по команде Exit);

Quit - выход из системы по окончании работы.

Если активизировать вторую позицию верхней строки и нажать клави-

шу Enter, то мы окажемся в окне редактирования задач.

Третьей позицией верхней строки является команда Solve. После то-

го как редактирование задачи окончено нужно нажать Esc (для попадания

в верхнюю строку меню) и активизировав пункт меню Solve, запустить за-

дачу на счет нажатием клавиши Enter. Если в описании задачи ошибок с

точки зрения системы нет, то начнется процесс решения. По окончании

этого процесса результат работы будет представлен в окне Solution.

Четвертая позиция верхней строки - Commands. При активизации этой

позиции и нажатии клавиши Enter открывается следующее подменю:

Verify - проверка решения (результат работы этой команды выводит-

ся в одноименное окно);

Calculate - включение калькулятора (для выключения - Esc);

Find other - поиск другого решения (Т.к. итерационные методы при-

водят только к одному из возможных решений, то для нахождения других

надо исключить найденное и заново решить задачу. Именно это и делает

данная команда);

Iterate - пуск итераций после остановки решения (Команда исполь-

зуется для уточнения найденного решения при условии, что заданная точ-

ность не достигнута, а время отведенное на процесс решения закончено).

Пятая позиция верхней строки (Report) открывает следующее подменю:

Go - составление отчета (результат этой команды появляется в окне

Report);

Output - направление вывода отчета (экран, принтер);

Formatted - форматирование отчета;

Capture - запись отчета в файл eureka.log (По запросу EUREKA.LOG

EXIST.A TO ERASE этот файл можно дополнить или стереть. При включенной

команде в строке переключений будет стоять ON, иначе OFF);

Logfile name - изменение имени log-файла.

Подменю шестой позиции верхней строки (Gragh) состоит из четырех

пунктов.

Plot - построение графика (После ввода значений левой и правой

границ аргумента, если, конечно, функция предварительно описана при

помощи команды Function, будет построен график функции состоящий из

текстовых символов псевдографики. При нажатии F5 этот график перестра-

ивается в графическом режиме с высоким разрешением);

Output - вывод графика на экран или принтер;

List - вывод таблицы (После вывода начального значения, шага вы-

числений и количества точек в которых вычисляются значения функций вы-

водится таблица со значениями аргумента и функции, если, конечно,

функция предварительно описана при помощи команды Function или в окне

Edit);

Function - задание функции, которую надо построить.

6Опишем последовательность действий необходимых для построения гра-

6фика функции более подробно.

6Способ N 1

7\\\\\\

6Активизируйте (т.е. подведите курсор и нажмите Enter) пункт верх-

6него меню под названием - Graph. В открывшемся подменю активизируйте

6пункт - Function. В появившуюся после этого строку введите название

6вашей фунуции (например y(x) или ab) и нажмите Enter. Во вновь появив-

6шуюся строку введите определение вашей функции (например sin(x)+x^2)

6и нажмите Enter. После этого активизируйте пункт подменю с названием

6- Plot. В появившуюся строку введите начало интервала построения гра-

6фика и нажмите Enter. Во вновь появившееся окно введите конец интерва-

6ла и0 6нажмите Enter.0 6 В результате всех перечисленных действий на дисп-

6лее появится окно содержащее график выполненный символами псевдогра-

6фики. Если теперь нажать0 6F5, то график перерисуется на весь экран

6при помощи истинной графики.0 6Повторное нажатие F5 приводит к воз-

6вращению экрана в состояние0 6 существовавшее до первого нажатия этой

6клавиши.0 6График может быть перерисован на весь экран в сиволах псевдо-

6графики,0 6если преред F5 была нажата клавиша F4.0 6 При этом, для того

6чтобы вернуться в режим позволяющий использовать0 6истинную графику

6необходимо нажать F7.

6Способ N 2

7\\\\\\

6Войдите в окно Edit. Запишите в нем определение одной или несколь-

6ких функций (например:

6z(x)=sin(x)+x^2

6p(x)=deriv(deriv(5*cos(x),x),x)0

6m(x)=1/x )

6и любую вычислительную задачу (например t=z(1)).

6Поднимитесь в верхнюю строку меню и активизируйте в ней пункт Solve.

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

6меню Graph. В открывшемся подменю активизируйте пункт Plot. При этом

6появится меню, позволяющее выбрать функцию (из числа определенных в

6окне Edit) для построения графика. Выбор функции осуществляется при

6помощи курсора. Его надо подвести к названию функции и нажать Enter.

6Далее выполняются те же действия, что и в I5ом6 способе после активиза-

6ции пункта Plot.

6Если возникает потребность в построении графика другой функции (из

6числа определенных в окне Edit), то необходимо: войти в окно Edit,

6выйти из этого окна (при этом редактировать записи не обязательно),

6активизировать пункт Solve и далее повторить описанные выше действия.

6Примечание

7\\\\\\

6Для вывода на экран функции в табличном виде пригодны оба описан-

6ных выше способа. Отличием является только то, что вместо пункта Plot

6активизируется пункт List. При этом Eureka потребует ввести: начало

6интервала вычислений, шаг вычисления и число точек, в которых вычис-

6ляются значения функции.

Седьмая позиция верхней строки (Options) имеет следующее подменю:

Variables - изменение значений переменных без вхождения в редак-

тор;

Settings -задание установок системы (к примеру: accuracy - зада-

ние погрешности вычислений; complex [5yes4no0] - разрешает вычисления с

комплексными числами; casefold [5yes4no0] с параметром yes отменяет имею-

щееся по умолчанию различия между прописными и строчными буквами; di-

gits - определяет число цифр у результатов вычислений; substlevel N -

задает количество преобразований переменных, в ходе которых одни пере-

менные автоматически выражаются через другие. При N=0 такие преобразо-

вания не выполняются. Допустимые значения N от 0 до 6. В некоторых

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

результат). Кроме перечисленных этот пункт подменю содержит еще ряд

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

шей F1 (т.е. help).

Сolors - установка окраски окон; рамок и текстов;

Directories - установка директории (Система и отдельные файлы мо-

гут храниться в разных директориях. В этом случае нужно указать систе-

ме, где находятся ее файлы и файлы с примерами расчетов.);

LoadSETUP - загрузка установочного файла;

WriteSETUP - запись установочного файла.

Восьмая позиция верхней строки (Window) также имеет подменю:

Open - открывает указанное окно;

Close - закрывает указанное окно;

Next - делает активным следующее окно;

Zoom - расширяет активное окно;

Tile - делает размеры окон равными;

Stack - располагает окна друг за другом;

Goto - переход в активное окно из меню.

в) Системы линейных алгебраических уравнений можно решать как с по-

мощью прямых , так и с помощью итерационных методов. Т.к. о прямых ме-

тодах решения таких , как метод Крамера или метод Гаусса , рассказыва-

лось в курсе математики, то рассмотрим здесь только некоторые итераци-

онные методы. Итерационные методы представляют для нас интерес еще и

потому , что Eureka решает системы линейных уравнений ( как и нелиней-

ных ) итерационными методами. При этом может использоваться подстанов-

ка одних переменных в другие, нередко сводящая задачу к точному реше-

нию.

Итерационные методы применяются на практике к большим системам с

разреженными матрицами. Разработано большое число разлиных итерацион-

ных методов, каждый из которых ориентирован на решение сравнительно

узкого класса задач. Рассмотрим два наиболее простых и извесных итера-

ционных метода.

_Метод простой итерации

Для того чтобы применить метод простой итерации к решению системы

линейных уравнений

Ах=b4 0 (1)

c квадратной не вырожденной матрицей А, необходимо преобразовать эту

систему к виду

4^ ^

х=Ах+b4 0 (2)

4^ ^

Здесь А - квадратная матрица (nxn), а b - вектор столбец длины n. Са-

мый простой способ привести систему (1) к виду (2) выразить х410 из пер-

вого уравнения системы (1)

4-1

6x416=a4116(-a4126x426-a4136x436-...-a41n6x4n6)

х420 из второго уравнения и т.д. В результате получаем систему6:

4^ ^ ^ ^

6x416= -a4126x426-a4136x436-...-a41n6x4n6+b41

4^ ^ ^ ^

6x426=-a4216x416-4 6-a4236x436-...-a42n6x4n6+b42

6.....................................

4^ ^ ^ ^ 6 4^

6x4n6=-a4n16x416-a4n26x426-a4n36x436-a4n46x446-...+b4n

у которой на главной диагонали матрицы А находятся нулевые элементы.

Остальные элементы вырожаются по формулам6 :

4^ ^

6a4ij6=a4ij6/a4ii6 и b4i6=b4i6/a4ii6 .

4(0) (0) (0) (0)

Выберем начальное приближение6 x4 6=4 6(x41 6,4 6x42 6,4 6...4 6,x4n 6).

Часто в качестве началь6н0ого приближения выбирают столбец свободных

членов (b410, b420,...b4n0). Подставляя его в правую часть системы (2) нахо-

дим первое приближение

4(1) ^ 5 4(0) 5 4^

6x4 6=4 6A4 6x4 6+4 6b

6П0родолжая этот процесс далее, получим последовательность

х5(0)0,5 0х5(1)0,5 0х5(2)0,5 0...,5 0х5(k)0, ... 6 0приближений, вычисляемых по формуле

4(k+1) ^ (k) ^

6x4 6=4 6A4 6x4 6+4 6b , k=0,1,2,...

Спра6в0едли6в0а следующая теорема о сходимости метода простой итерации.

_Теоремма

Пусть выполнено одно из условий :

4n6 4n

6────┐4 ────6┐

4M6 4A6 4X6 │ 4^6 4 6│ │ 4 6│ 4 6 4 6 │ 4 6│

617,6i7,6n 7 4 6/4 6│ a4ij 6│ = q < 1 <=> │ a4ii6 │ >4 6 / 4 6│ a4ii6 │4 ,6i=1,...,n

6────┘ ────┘

6j=1 4 6j=1

6i7-6j

или

4n n

4────6┐4 ────6┐

4M6 4A6 4X6 4 64 │ ^ │ │ │ 64 │ │

617,6j7,6n7 4 6/4 │ 6a4ij │ 6=4 6q4 6< 14 6<=>4 │ 6a4jj │ 6>4 6/4 │ 6a4ij │6 ,j=1,...,n

4────6┘4 ────6┘

6i=1 i=1

6i7-6j

Тогда:

(I) решение Х системы (2) существует и единственно;

(II) при произвольном начальном приближении х5(0)0 справедлива оценка

погрешности6:

4(k) - k (0) -

4M A X │6 x4i 6-4 6x4i6 │ <= q4 M A X │6 x4i 6-4 6x4i6 │ .

617,6i7,6n4 7 617,6i7,6n

Замечание 1

При помощи понятия нормы теорема о сходимости метода простой ите-

рации для системы линейных уравнений может быть сформулирована в более

общем виде.

Замечание 2

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

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

оценка6:

4(k) - (k) (k-1)

4M A X │ 6x4i 6-4 6x4i │ <=6 q/(1-q)4 6 4M A X │6 x4i 6-4 6x4i6 4 6│

617,6i7,6n4 617,6i7,6n

_Метод Зейделя

Этот метод является модификацией метода простой итерации. Основ-

ная идея модификации состоит в том, что при вычислении очередного

(к+1)-го приближения к неизвестному 6x4i0 при 6i0>1 используются уже найден-

4- -

ных (к+1)-е приближения 6к 0неизвестным 6x410 ,...6,x4i-10 , а не к-е прибли6-

жения, как в предыдущем методе.

На (к+1)-ой итерации i-ая компонента вычисляется по форм6у0ле6:

4(k+1) ^ (k+1) ^ (k+1) ^ (k) ^ (k) ^

6x4i 6=4 6-a4i,16x41 6-4 6...4 6-a4i,i-16x4 6-a4i,i+16x4 6-...-a4i,n6x4 6+4 6b

Достаточное условие сходимости метода Зйделя совпадает в приве-

денной формулировке с условием сходимости метода простои итерации.

2) Eure6k0a позволяет решать системы линейных уравнений (как и мно-

гие другие задачи) без составления каких-либо программ. К примеру для

решения системы линейных уравнений6:

6┌ ┐ ┌ ┐

62x416+3x426+5x436=31 │ 2 3 5 │ │ 31 │

6-x416+3x436=11 т.е. Ax=b, где A=│-1 0 3 │ b=│ 11 │

6x416-7x426+5x436=0 │ 1 -7 5 │ │ 0 │

6└ ┘ └ ┘

6н0ужно сделать в окне Edit любую из двух приведенных ниже записей (Eu6-

re6k0a воспримет эти записи практически одинаково6 ).

6I)0 6││ II)

6││

62*X1+3*X2+5*X3=31 ││ 2*X1+2*X3+3*X2+3*X3-31=0

6-1*X1+3*X3=11 ││ -X1+3*X3=0

6x1-7*X2+5*X3=0 ││ X1-5*X2+5*X3-2*X2=0

6││

После чего подняться в верхнюю строку меню (при помо6щ0и ESC)

и6 0 подведя6 0курсор к пункту Solve 6 0нажать Enter. Если 6 0матрица6 0 системы

вырождена, то попытка 6 0решения 6 0не 6 0преведет к успеху. 6 0В нашем 6 0случае

6det A7-60 0и поэтому в окне решений (Solution) появятся результаты, полу6-

ченные с заданной точностью:

6X1=1.00000000 X2=3.000000000 X3=4.000000000

Eure6k0a позволяет решать системы линейных уравнений не только с

дествительными, но и с комплексными коэффициентами. К решению таких

уравнений сводятся, например, задачи на вычисление напряжений и токов

у электро- и радиотехнических цепей при их работе на переменном токе.

Далее приводится пример записи в окне Edit системы линейных уравнений

с комплексными коэффиециентами6:

6$ complex=yes

6i^2=-1

6(2+i)*X1+7*X2+(7-i)*X3=0

6(5-i)*X1+i*X2+3*i*X3=2

6(3-i)*X1+2*X2+5*X3=4

6Задание

6───────────

а) Проверьте при помощи встроенного в Eure6k0a калькулятора может

ли быть решена ваша система методом простой итерации.

б) Проверьте при помощи окна Edit и пункта меню Solve не является

ли ваша система вырожденной.

в) Решите вашу систему. Сделайте проверку решения при помощи окна

Verify. Под6го0т6о0вьте отчет о решении в окне Report.

г) Найдите матрицу, обратную к матрице вашей системы. Для этого,

используя равенство 6AA5-16=E0,6 составьте n526 уравнений с n526 неизвестными,

6где n*n размер исходной матрицы.

6d) Используя равенство AA5-16=E , проверьте является ли0 найденн6ая

в пункте 6(0г6) матрица обратной к A.

Лабораторная работа N2

6──────────────────────────

Язык и функци6и0 системы Eure6k0a. Решение нелинейных

уравнений. 6 0Решение систем нелинейных уравнений.

Вычисление экстремум6а0 функций от одной переменной.

6Цель работы

6──────────────

Приобретение навыков решения нелинейных уравнений и систем нели-

нейных уравнений при помощи систем Eure6k0a.

_Теоретическое введение

a) Алфавит системы Eure6k0a содержит стандартный набор символов.

Это латинские прописные (от А до Z) и строчные (от а до z) буквы, а

также ряд спецзнаков.

: - разделитель для выражений размещенных в одной строке;

; - отмечает начало строки комментария;

{} - внутри скобок размещается комментарий;

[] - используется для работы с размерными комментариями;

$ - указывает, что следующее слово-директива;

= - операция присваивания;

:= - задание (определение) функции пользователя или начальных

значений переменных.

Длинные выражения после символа арифм6е0тической операции можно пе-

реносить на другую строку.

Директивы, относящиеся к установкам, могут быть заданы в окне

Edit в виде блока.

_Пример

$ settings

acuracy=0.000001

digits=5

$ end

Eureca может производить следующие операции:

+ сложение; - вычитание; * умножение; / деление; ^ возведение в

степень; () изменение приоритета операций; . отделение целой части

числа от дробной; ,отделение переменных друг от друга в списках; <

меньше; > больше; <= меньше или равно; >= больше или равно.

Приоритет операций определяется как и в языках Бейсик, Паскаль и

т.д.

Eure6k0a имеет функции re(z) и im(z), возвращающие действительную и

мнимую части комплексного числа z=x+iy. Перед применением этих функций

обходимо ввести директиву: $ complex=yes и обозначить мнимую ед6и0ницу

i^2=-1.

Алгебраическ6ие0 функци6и

abs(z) - модуль ; exp(z) - вычисление e=2,71828... в степени z;

floor(x) - целая часть х; ln(z) - вычисление натурального логарифма z;

log 10(z) - вычисление десятичного логарифма z; sqrt(z) - вычисление

корня квадратного из z; pos(x) - возвращает х при х>0 и 0 в противном

случае; sgn(x) - возвращает: 1 при х>0, -1 при х<0 и 0 при x=0

_Тригонометрические и гиперболические функции

atan2(y,x) - вычисление арктангеса по координатам x и у (угол

заключенный между осью Ох и отрезком, концы которого -(0,0) и (х,у));

polar(x,y) - преобоазование декартовых координат в полярные;

sin(z), cos(z), tan(z) - вычисление синуса, косинуса и тангеса z;

sinh(z), cosh(z), tanh(z) - вычисление гиперболических синуса,

косинуса и тангеса z.

Кроме перечисленных выше функций Eure6k0a имеет еще ряд функций и

процедур:

deriv(f(x),x) - вычисление производной ф-ции f(x);

integ (f(x),x,a,b) - вычисление определенного интеграла от f(x) в

пределах от а до b.

fact(n) - вычисление факториала числа n;

ncum(x) - вычисляет специальную функцию ошибок Р(х) для нормаль-

ного распределения;

poly(x,an,...,a0) - вычисляет значение всех действительных и

комплексных корней полинома an*x^n+...a1*x+a0 и позволяет задать функ-

цию P(x) вычисляющую значение полинома в точке х.

sum(f(i),i,n,k) - вычисляет сумму f(i) при 6 0индекс6е0 i, меняющемся

от n до k.

В системе Eure6k0a пользователь имеет возможность задавать необхо-

димые ему функции через имеющиеся встроенные. Функции пользователя за-

даются в виде:

Имя ф-ции (список переменных)=выражения

или

Имя ф-ции (список переменных):=выпажение

Вторая форма используется если заданная функциональная зависи-

мость рассматривается как приближения.

б) Eureca не вычисляет производные (и инегралы) в аналитической

форме. Она может вычислять значения производной в точке численным ме-

тодом. С помощью системы Eure6k0a можно вычисл6я0ть и производные более

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

sin(x), достаточно написать:

F=deriv(deriv(sin(x),x),x).

Ниже приводится запись в окне Edit. Комментарии помогают понять

смысл записи.

;Вычисление производной

$ settings ; Установка

digits=12 ; числа знаков

$ end ; результата

; Задана функция d(x)=d(sin(x))/dx

d(x)=deriv(sin(x),x)

d1=d(4.3) ; Вычислена функция d(x)=cos(x)

; в точке x=4.3

После этого для получения решения надо подняться в верхнюю строку

меню и активизировать пункт Solve. При этом используя пункт меню

6G0raph можно построить график d(x).

в) Пусть f(x) - функция, определенная на отрезке [a,b]. Предполо-

жим, что на этом отрезке содержится единственная точка x локального

минимума f(x), причем функция строго убывает при 7 0x7,0x и строго возрас-

тает 7 0при 7 0x7.0x. Такая функция называется унимодальной. Заметим, что

достаточно рассмотреть задачу минимизации функции f(x), так как макси-

мизация сводится к минимизации с помощью введения новой функции

g(x)=-f(x). Таким образом будут решены оба варианта экстремальной за-

дачи.

Ряд методов минимизации основан на сравнении значений функции

f(x), вычисляемых в точках x1,x2,...,x4n0. Эти методы часто называют ме-

тодами прямого поиска, а точки x4i0 - пробными точками. Одним из наибо-

лее эффективных методов из этого ряда является метод золотого сечения.

Золотым сечением отрезка называется такое разбиение отрезка на

две неравные6 части ,что отношение0 длины всего отрезка к длине 6 0его бо6-

льшей части равно отношению длины 6 0большей части к длине меньшей части

отрезка.

Золотое сечение отрезка [a,b] осуществляется каждой из двух сим-

метрично расположенных относительно центра отрезка точек:

62 2

7a6=a + ───────── ( b - a )7 b6=a + ───────── ( b - a )

7|\6 7|\\

63 + 7?6 5 1 + 7?6 5

При этом точка 7a0 осуществляет золотое сечение не только отрезка

[a,b], но и отрезка [a,7b0 ]. Кроме того точка7 b0 осуществляет золотое се6-

чение не только отрезка [a,b], но и отрезка [ 7a0,b].

Очередная (к+1)6 0 интерации 6 0производится следующим образом. 6 0Точки

7a5(k)0 и 7b5(k)0 7 0находятся по формулам:

62 5 62

7a5(k)6=a5(k)6 + ──────────7 D5(k)7 b5(k)6=a5(k)6 + ────────── 7D5(k)

7|\\6 5 7|\\

63 + 7?6 5 5 61 + 7?6 5

6г0де 7D5(k)0 - длина отрезка локализации экстремума при к5ой0 интерации.

Если 6f(7a5(k)6)5 7,5 6f(7b5(k)6) , то

6┌ ┐ ┌ ┐

6x5(k+1)0 6принадлежит 0 6│0 6a5(k+1)4,6b5(k+1)6│5=6│0 6a5(k)4,7b5(k)6│0 7`

6└ ┘ └ ┘

6и x5(k+1)6=7a5(k)

Если 6f(7a5(k)6) > f(7b5(k)6) , то

6┌ ┐ ┌ ┐

6x5(k+1)6 принадлежит │ a5(k+1)6,b5(k+1)6│=│ 7a5(k)6,b5(k)6│

6└ ┘ └ ┘

6и x5(k+1)=7b5(k)

Заметим, что точка 6x5(k)0 отстоит от концов отрезка [a5(k)0, b5(k)0] на

вел6и0чину, не превышающую 62

6──────────7 D5(k)

7|\\6 .

61 + 7?6 5

Поэтому верна оценка:

6│ x5(k) - 6x5* │7 ,6 ──────────7 D5(k)6 =7 D5(k+1)

7|\\6 .

61 + 7?6 5

7|\

7?0 65 + 1

Т.к. каждая интерация сокращает длину отрезка 6 0в6 ─────────────

6раз,0 то справедлива следующая оценка погрешности:

6┌ ─┐5k+1

6│ 2 │

6│ x5(k)6 - x5* │7 , 6│ ─────────── │5 (b - a)

6│ 7|\\6 │

6└ 1 + 7?6 5 7 6┘

Таким образом, метод золотого сечения сходится со скоростью гео-

метрической прогрессии, знаменатель которой

g5 0=5 ───────────7 ~6 0.62

7|\\

615 6+5 7?6 5

Существуют методы, которые могут оказаться более эффективными,

если минимизируемая функция достаточно гладкая. Часть из них является

просто модификациями методов решения нелинейных уравнений применитель-

но к уравнению f(x)=0.

г) Eure6k0a позволяет решать задачу поиска экстремума функции при

помощи задания директив:7 0$min и $max. При этом если функция имеет нес-

колько экстремумов, то для нахождения того который нужен имеет смысл

нарисовать график функции и исходя из этого графика задать начальное

приближение и ограничени6я0 для поиска экстремума. В противном случае

поиск экстремума будет происходить от начальных значений заданных сис-

темой Eure6k0a по умолчанию и может привести не к тому экстремуму, кото-

рый хотелось бы найти. Ниже приводится пример 6записи из окна Edit. Эта

6запись позволяет найти экстремум.

$ max (T)

V(x)=5*x*exp(-x/2)*(2+sin(3*x))

x:=2

V(x)>10

T=V(x)

В результате решения получается: T=10.629942, x=2.58050146.

д) Корень х5*0 уравнения f(x)=0 называется простым, если f(x5*0)=0 и

f'(x5*0)7-00. В противном случае корень называется кратным. Целое число m

называется кратностью корня x5*0, если f5(k)0(x5*0)=0 для к=0,1,2,...m-1 и

f5(m)0(x5*0)7-00.7 0Геометрически7 0корень 7 0x соответствует 7 0точке 7 0пересечения

графика 7 0функции y=f(x) с осью O6x0. Решение 7 0задачи 7 0отыскания корней

нелинейного уравнения осуществляет в два этапа. Первый этап называ6-

ется этапом локализации корней, второй - этапом итерационного уточ6-

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

средств системы Eure6k0a. 6 0На втором этапе для 6 0вычисления каждого из

корней с точностью 6e0>0 используют какой-либо из итерационных 6 0методов,

позволяющих 5 0построить последовательность 6x5(0)0,6x5(1)0,..,6x5(n)0...5 0прибли6-

жений,6 0сходящуюся 5 0к5 0 корню 6 x5*0. 6 0Сформулируем6 0 один из6 0этих 6 0методов

в6 0виде теоремы.

6Теорема0 61.0(о сходимости метода Ньютона)

6───────────────────────────────────────────

Пусть 6x5*0- простой вещественный корень уравнения f(x)=0 и пусть

f'(x)7-00 в окрестности U4r0(x5*0)={x:6│0x-x5*6│0

рерывна в U4r0(x5*0) и

6причем

6M │x5(0)6 - x5*│

6q = ──────────────5──6 < 1 .

62 m

Тогда, если 5 0начальное приближение 5 6x5(0) 6принадлежит 5 0U4r0(x5(*)0),6 0то

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

6f(x5(k)6)

6x5(k+1)6=x5(k) 6-5 ────6────── , где k=0,1,2,... сходится к x5(*)6,

6f'(x5(k)6)

причем6 0для6 0погрешности 6 0справедлива оценка

6│ x5(k) 6- x5*6 │7 ,6 q5t-1 │ 6x5(0)6 - x5* │6 , где t=25k 6.

_Замечание 1.

Аналогичные теоремы существуют для случая кратных и комплексных

корней.

_Замечание 2.

Как известно, экстремумы функции f(x) находятся в точках, где

f'(x)=0. Поэтому если для g(x)=f'(x) выполняются условия приведенной

выше теоремы, то итерационный процесс, приближающий к точке экстрему-

ма6 f(x)0, будет иметь вид:

6f'(x5(k)6)

6x5(k+1)=6x5(k)6 - ──────────── , где k=0,1,2,....

6f''(x5(k)6)

е) Задача отыскания решения системы из N-нелинейных уравнений с N

неи6з0вестными, имеющая вид

f410 (6x410, 6x420, ..., 6x4n0)=0

f420 (6x410, 6x420, ..., 6x4n0)=0 6 0 (1)

......................

6f0n (6x410, 6x420, ..., 6x4n0)=0

встречается 6 0очень 6 0часто, т.к. в 6 0реальных 6 0исследованиях определя-

ются 6 0сотни 6 0или 6 0даже 6 0тысячи 6 0параметров. Первым 6 0этапом6 0 решения

так6 0же,6 0как6 0и 6 0в6 0одно6мер0ном 6 0случае, 6 0является 6 0локализация 6 0решения

x5*0=(6x410,...,6x4n0)6 0,6 0т.е. подбор множества содержащего 6x5*0.

(Здесь далее нижний индекс будет означать номер компоненты векто-

ра, а верхний - номер интерации). Часто в качестве такого множества

выступает параллепипед или шар в N - мерном пространстве. Во многих

случаях полное решение задачи локализации невозможно и ее можно счи-

тать решенной удовлитворительно, если из каких либо соображений удает6-

ся 6 0найти хорошее 6 0начальное приближение 6x5(0)0. 6 0В 6 0простейших 6 0случаях

(для систем двух уравнений с двумя неизвестными) могут быть использо-

ваны графические методы.

На втором эт6а0пе для 6вычисления 0решения с заданной точностью ис-

пользуют один из итерационных методов. Рассмотрим в качестве примера

метод, называемый методом простой итерации. Преобразуем систему (1) к

следующему эквивалетному виду ( к виду удобному для интераций):

6x41=7F416(x41,6x42,....,6x4n6)

6x426=7F426(x416,x426,....,x4n6)

6.................... (2)

6x4n6=7F4n6(x416,x426,....,x4n6)

Если ввести вектор-функцию,6 7 F6=(7F416,7F426,....,7F4n6)5T6, 0то6 0 система (2)

запишется так:

6x=7F6(x) (3)

Пусть начальное приближение 6x5(0)=(6x415(0)0,6x425(0)0,...,6x4n5(0)0)5T0 задано.

Подставляя6 его 0в правую6 0часть 6 0системы (3),6 0 получим6 x5(1)6=7F6(x5(0)6)0.

Подставляя 6 x5(1)0 в 6 0 правую часть (3),6 0найдем 6x5(2)6=7F6(x5(1)6) и 0т.д.

Продолжая 6 0вычисления 6 0по формулам6 x5(k+1)6=7F6(x5(k)6) ,0 6k7.600 получим пос6-

ледовательность 6x5(0)0,6x5(1)0,...,6x5(k)0,... приближений к решению 6x5*0.

6┌ ┐

6│ d7 F416(x) 7 6d7F416(x) │

6│4 ─────────6─ ...... ───────── │

6│ dx416 7 6 7 6dx4n6 │ - матрица ( частных

6│.............................│

Пусть 7F6'(x) =0 6│.............................│ производных ) Якоби

6│ │

6│ 7 6d7F4n6(x) 7 6d7F4n6(x)4 6 │ соответствующая7 F6(x).

6│ ───────── ....... ───────── │

6│ 7 6dx416 7 6dx4n 6 │

6└ ┘

6Сф0ормулируем теорему о сходимости метода простых интераций.

6Теорема 2 .

6───────────────

Пусть в некоторой 4 7s 0- окрестности 4 0решения 4 6x5*0 функции4 0 7F4i6(x)

(i=1,2,...,n) дифференцируемы и выполнено неравенство

6──────┐ │ │

6m a x 0 6 │ 7 6d7F4i6(x) │

617,6i7,6n0 6/ │─────────│7 ,6 q5 6, где 07,6q<1 и q - постоянная .

6──────┘ │ 7 6dx4j6 │

6j=1 │ │

Тогда независимо от выбора начального приближения 6x5(0)0 из указан-

ной 7s 0- окрестности 7 0корня 7 0итерационная последовательность не выходит

из этой окрестности, метод сходится со скоростью гео6м0етрической прог6-

рессии и справедлива следующая оценка погрешности:

6m a x │ x4j5(k)6 - x4j5*6 │7 ,6 q5k6 m a x │ x4j5(0)6 - x4j5*6│

617,6j7,6n 17,6j7,6n

(При помощи понятия нормы теорема 2 может быть сформулирована в

более общем виде).

_Замечание 3.

В условиях теоремы 2 верна апостериорная оценка погрешности:

6m a x │ x4j5(k)6 - x4j5*6 │ 7,6 ──────── m a x │ x4j5(k)6 - x4j5(k-1)6 │

617,6j7,6n0 5 61 - q 17,6j7,6n

При наличии достаточно хорошего начального приближения 6x5(0)0 можно

считать, что

6──────┐ │ 5 6│

6q7 ~6 m a x │ 5 7 6d7F4i6(x5(0)6) │

617,6i7,6n0 6/ │────────────5─6│

6──────┘ │ 5 7 6dx4j6 5 │6 .

6j=1 │5 │

_Пример

В результате визуального анализа графиков кривых f1 и f2 из сис-

темы нелинейных уравнений

6f(x416,x426) = x41534 6+ x42536 - 8x416x426 = 0

6(4)

6f(x416,x426) = x416ln(x426) - x426ln(x416) = 0

обнаружилось,5 0что5 0 одно из ее решений4 0находится вблизи точки 5 0(3.86;02).

Проверить сходимость 5 0метода простых итераций для 5 0системы (4),5 0если в

качестве 5 0начального 5 0приближения 5 0взята точка6 x415(0)6=3.8 и x425(0)6=2.

Преобразуем систему к виду убдобному для применения метода прос-

тых итераций.

437|\\\\\\

6x416 = 7?6 8x416x426 - x4253 =7 F416(x416,x426)

6x426 x41

6x42 6= x426 + ──────── - ──────── =7 F426(x416,x426)

6ln(x426) ln(x416)

Для вычисления q воспользуемся системой Eure6k0a. Сделаем в окне

Edit следующую запись:

x=3.8 : y=2

a=deriv ((16*x-8)^(1/3),x)

b=deriv ((30.4*y-y^3)^(1/3),y)

c=deriv (2+2/ln(2)-x/ln(x),x)

d=deriv (y+y/ln(y)-3.8/ln(3.8),y)

K=abs(a)+abs(b) : p=abs(c)+abs(d)

В результате решения получаем p

Cледовательно, метод простой итерации в данном случае сходится.

ж) Для того, чтобы найти оговоренное выше решение системы (4) при

помощи среды Eure6k0a, достаточно сделать в окне Edit cледующую запись

x^3+y^3=8*x*y

x*ln(y)=y*ln(x)

x:=3.8 : y:=2

и отдать среде команду Solve.

6Задание

6──────────

а) Проверьте при помощи графика и таблицы из среды Eure6k0a наличие

корня y предложенного вам уравнения f(x)=0 на указанном отрезке лока-

лизации корня.

б) Найдите при помощи системы Eure6k0a m и M. Проверьте выполнение

условия

6M │ x5(0) 6- x5*6 │

6─────────────────5 6 < 1

62 m

(из теоремы о сходимости метода Ньютона) для вашего уравнения

f(x)=0.

в) Решите ваше уравнение при помощи системы Eure6k0a.

г) Изобразите на миллиметровке графики кривых из предложенной вам

системы нелинейных уравнений в указанном прямоугольнике локализации

корня. Выберите начальное приближение корня. Представьте систему в ви-

де 6x=7F6(x).

д) Используя систему Eureka, вычислите

6─────┐ │ 5 6│

6 │ 7 6d7F4i6(x5(0)6) │

6/ │──────────5───6│

6─────┘ │ 4 7 6dx4j6 5 6│

6j=1 │ 5 6│

для каждой i-ой строки 6 0Якобиана (i=1,2, ..., 6n0). 6 0На основании 6 0этого

проверьте выполнение условий теоремы о сходимости метода простой ите6-

рации.

е) Решите вашу систему при помощи Eureka.

Лабораторная работа N3

6───────────────────────────────

Экстремумы функции многих переменных. Задача линейного

программирования.

Цель работы.

6───────────────

Приобретение навыков вычисления экстремумов функции многих пере-

менных и решения задачи линейного программирования при помощи системы

E6u0reka.

Теоритическое введение.

6────────────────────────

а) Пусть f(x)=6f0(x410, ...,x4n0) - функция от n действительных пере-

менных, минимизируемая на некотором множестве Х. Если Х=R5n0, то говорят

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

условной 6 0минимизации. Как 6 0и для функции 6 0одной 6 0переменной, 6 0задача

максимизации функции f(x) сводится к задаче минимизации функ6-

ции g(x)=-f(x).

Из курса математики известно, что градиент функции f(x), опреде-

ляемый в точке а=(а410, ..., а4n0) как вектор

6┌ 7 6df(a) 7 6df(a) ┐

6u(a) = │────────,...., ─────────│ , указывает направление

6└ 7 6dx416 7 6dx4n6 ┘

наискорейшего 6 0возрастания6 0 функции f(x) в точке а. 6 0Вектор -u(a), на6-

зываемый антирадиентом, указывает 6 0направление наискорейшего6 0 убывания

функции f(x) в точке а. Точка а называется стационарной точкой функции

f(x), если в этой точке выполняются n равенств:

726 df(a)

726 ──────── = 0

726 7 6dx41

7*6..............

726 df(a)

726 ──────── = 0

794 6dx4n

Пусть f(x) дважды6 0 непрерывно дифференцир6уема0. Тогда достаточным

условием того, чтобы стационарная точка а была точкой локального мини-

нума, является положительная определенность матрицы:

6┌ 4 6┐

6│ 4 6│

6│ d526f(a)7 6 d526f(a)7 4 6│

6│ ────────,.....,────────4 6│

4^6 │ dx416dx416 dx416dx4n6 │

6А(x) = │.........................│

6│ │

6│ 7 6d526f(a) 7 6d526f(a)7 6│

6│ 4────────6,.....,4────────6 │

6│ dx4n6dx416 dx4n6dx4n6 │

6└ ┘

4^ ^

Матрица А называется матрицей Гессе. Напомним, что матрица А4 0по6-

4^ ^

ложительно определена, если 6(Ax,x)>00 6 0при6 x7-600 6 0и 6 (Ax,x)=00 6 0при 6 x=0,

где 6x=(x416,...,x4n6)5T6.

Сущесвует большое количество различных методов нахождения безус-

ловного минимума функции многих переменных. Рассмотрим в качестве при-

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

является одним из представителей большого семейства итерационных мето-

дов. Пусть х5(k) 0- приближение к точке минимума х, а u5(k)0=u(x5(k)0) -зна6-

чение 5 0градиента в точке х5(k)0. 5 0Напомним еще раз, что в малой 5 0окрест-

ности точки х5(к)0 направление наискорейшего убывания функции f(x) зада-

ется антиградиентом 5 0-u5(k)0. Исходя из этого итерационную формулу мето-

дом наискорейшего спуска записывают в виде:

6x5(k+1)6 = x5(k) 6-5 7a4k6u5(k) 4 6 4 6(1)

Здесь - 7a4к0 шаг спуска, выбираемый из соображений минимизации функции

от одной скалярной переменной 7f4k6(7a6) = f(x5(k) 6-5 7a6u5(k)6) 0при8 5 7a0>0. 5 0Т.е.

6в 0качестве 7 a4к6 0выбираем6 7 a0 для которого 7 f4k6(7a4k6) =7 6min 7f4k6(7a6)0 6при 0 7a6>0.

Рассмотрим применение этого метода для минимизации квадратичной

функции f(x410, ..., x4n0)=f(x), где

6n n4 6n

61 ────┐ ────┐ 4 6────┐

6f(x) = ─── a4ij6x4i6x4j6 - b4i6x4i6 (2)

62 / / 4 6/

6────┘ ────┘ 4 6────┘

6i=1 j=1 i=1

Коэффициенты а4ij0 являются элементами симметричной положительно

определенной матрицы А. Используя матричные обозначения, запишем f(x)

так:

6f(x) = ───(Ax,x) - (b,x) 4 6 4 6(3)

Вычислим градиент и матрицу Гессе для функции (2).

6┌ n n 4 6┐'4 ┌6 n 4 6 ┐'

6d f(x)0 610 6│ ─────┐ ─────┐ 4 6│4 │6 ─────┐ 4 6 │

6───────0 6= 4───6│ a4ij6x4i6x4j6 │4 6-4 │ 6 b4i6x4i6 │

6d x4k6 0 62 │ / / 4 6│4 6 4 │6 / 4 6│ =

6│ ─────┘ ─────┘ 4 6│4 │6 ─────┘ 4 6│

6└ i=1 j=1 4 6┘x4k └6 i=1 4 6 ┘x4k

4(6 где k=1,....,n)

6┌ n 4 6 n4 6 n4 6 4 6┐'

610 6│ ─────┐ 4 6 4 6 ─────┐ 4 6 ─────┐ 4 6│

6=0 6───│ a41j6x416x4j 6+..+ a4kj6x4k6x4j6 +..+ a4nj6x4n6x4j6│ - b4k6 =

620 6│ / 4 6 4 6 / 4 6/ 4 6│

6│ ─────┘ 4 6 4 6─────┘ 4 6─────┘ 4 6│

6└ j=1 4 6 4 6j=1 j=14 6 4 6┘x4k

61 ┌ 4 6 4 6┐

6= ───│ a41k6x416 +..+ (a4k16x416 +..+ 2a4kk6x4k6 +..+ a4kn6x4n6) +..+ a4nk6x4n6 │ - b4k6 =

62 └ 4 6 4 6┘

61 ┌ 4 6 4 6 4 6┐

6= ───│ (a41k6 + a4k16)x416 +..+ 2a4kk6x4k6 +..+ (a4kn6 + a4nk6)x4n6 │ - b4k6 =

62 └ 4 6 4 6 4 6┘

6( т.к. матрица A симметричная )

61 ┌ 4 6 4 6┐ 4 6─────┐

6= ───│ 2a4k16x416 +..+ 2a4kk6x4k6 +..+ 2a4kn6x4n6 │ - b4k6 = a4kj6x4j6 - b4k

62 └ 4 6 4 6┘ 4 6 /

6─────┘

6j=1

Окончательно получаем:

6df(x) ─────┐

6─────── = a4kj6x4j6 - b4k (4)

6dx4k6 /

6─────┘

6j=1

Тогда в матричной форме можно записать:

6u(x) = Ax - b (5)

Дифференцируя обе части равенства (4) по х4р0 (р=1, ...n), получаем4 0:

6d526f(x)

6───────── = a4pk

6dx4p6dx4k

Таким образом, матрица Гессе А(х) не зависит от х и равна А.

6Т0еперь благодаря формуле (5) формулу (1) можно записать в виде:

6x5(k+1)6 = x5(k)6 -7 a4k6(Ax5(k) 6-5 6b) (6)

Заметим, что5 6:

7f4k6(7a6) = ───(A(x5(k) 6-5 7a6u5(k)6),x5(k)6 -7 a6u5(k)6) -5 6(b,x5(k)6 -7 a6u5(k)6) =

6(*)

61 5 6 5 61

6= ───(Au5(k)6,u5(k)6 )7a526 - (u5(k)6,u5(k)6)7a6 + ───(Ax5(k)6,x5(k)6) - (b,x5(k)6)

62 5 62

6( Доказательство формулы (*) см. в конце лабораторной работы N 3 )

Эта функция является квадратичной функцией параметра8 7a0 и достига-

ет минимума при таком значении8 7a0=7a4к,0 для которого

7f4k5'6(7a4k6) = (Au5(k)6,u5(k)6)7a4k6 - (u5(k)6,u5(k)6) = 0

Таким образом, применительно к минимизации квадратичной функции

(3) метод наискорейшего спуска эквивалентен расчету по формуле (6),

где

6(u5(k)6,u5(k)6)

7a4k6 = ────────────5───6 (7)

6(Au5(k)6,u5(k)6)

Имеет место следующая теорема.

_Теорема

Пусть А - симметричная, положительно определенная матрица, и мини-

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

приближения метод наискорейшего спуска (6), (7) сходится и верна сле-

дующая оценка погрешности

7|\\\6 ┌ ┐5n

7/ l4max6 │7 l4max7 6-7 l4min6 │

6│ x5(k)6 - x5* 6│7 ,6 7/ 6──────── │───────────────│5 │ 6x5(0)6 - x5* │

7? l4min6 │7 l4max7 6+7 l4min6 │

6└ ┘

Здесь 7l4min7 0и 7l4max7 0- минимальное и максимальное собственные зна6-

чения матрицы А.

б) Система Eureka решает задачи на поиск минимума (максимума)

функции 6 0нескольких 6 0переменных. При 6 0этом могут быть заданы ограни6-

чения и удобные для поиска 6 0начальные значения. 6 0Для проверки 6 0способ6-

ности системы Eureka решать оптимизационные задачи разработан ряд тес6-

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

функции Розенброка. 6Э0та функция 6 0двух переменных образует в трехмер6-

ном пространстве " овраг ", затрудняющий поиск. Далее приводится за6-

пись из окнa Edit, позволяющая минимизировать функцию Розенброка.

6$ min (F)

6f(x,y)=100*(y-x^2)^2+(1-x)^2

6F=f(x,y)

6x:=-1.2

6y:=0

Начальное значение переменных далеки от решения х=y=1 и F=0.

Еще одна тестовая задача содержит ограничения.

6$ min (F)

6f(x,y)=(x-2)^2+(y-1)^2

6F=f(x,y)

6-x^2+y>=0

6-x-y+2>=0

Точное решение: F=1, x=1, y=1.

При решении оптимизационных задач с ограничениями Eure6k0a выводит

в окне Solution сообщение о том, насколько полно удовлетворены ограни-

чения. В идеальном случае выводится 100 %. Если это число значительно

меньше чем 100 %, то это может служить признаком неточного нахождения

экстремума. Пока не существует программа, которая была бы способна ре-

шить любую оптимизационную задачу. Поэтому надо быть готовым к тому,

что Eureka может не справиться с предложенным ей заданием.

в) При решении ряда технологических и экономических проблем воз-

никает задача вида:

найти max Z(x) или min Z(x)

6─────┐

если6 Z(x) = c4j6x4j6 + c40

6─────┘

6j=1

при ограничениях

6─────┐

6 a4ij6x4j7 ,6 b4i6 ( i=1,m416 )

6─────┘

6j=1

6─────┐

6 a4ij6x4j6 = b4i6 ( i=m416+1,m426 )

6─────┘

6j=1

6─────┐

6 a4ij6x4j7 .6 b4i6 ( i=m426+1,m )

6─────┘

6j=1

6x4j7.6v4j7.60 4 6 4 6(4 6j=1,n41 6)

6x4j7,6w4j7,60 4 6 4 6(4 6j=n416+1,n4 6)

Такие задачи называются задачами линейного программирования. Для

решения этих задач создан специальный метод, называемый симплекс-мето-

дом. Изучение задач линейного программирования является предметом спе-

циального курса, поэтому рассмотрим здесь часный случай. Пусть n=2

(т.е. Z(x)=с410х410+с420х420+с400 ) и при этом заданы следующие ограничения

─────┐

6 a4ij6x4j7 ,6 b4i6 ( i=1,m )

─────┘

6j=1

6x4j7.6v4j7.60 4 6 ( j=1,2 )

В этом случае решение задачи имеет наглядную геометрическую инт6ер0-

претацию. 6 0Исходя из заданных ограничений 6 0строится многоугольник до-

пустимых решений. Далее, для каждой точки плоскости функция Z(x)

принимает 6 0фиксированное 6 0значение Z4т0. 6 0Множество6 0всех 6 0точек, в кото6-

рых, 6 0Z(x)=Z4т0 есть 6 п0рямая 6 0с410х410+с420х420+с400=Z4т0 6 0перпендикулярная 6 0вектору

6C0=(с410,с420), выходящему 6 0из начала 6 0координат. Если эту прямую предви6-

гать 6 0параллельно 6 0самой 6 0себе 6 0по 6 0направлению вектора с, то линейная

функция Z(x) будет возрастать, а в противоположном направлении - убы6-

вать. Пусть при движении прямой Z по направлению вектора 6C0 она впервые

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

Зафиксируем это положение прямой Z. В этой точке функция Z(x) примет

минимальное значение.

При дальнейшем движении прямой Z по направлению вектора 6C0 она

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

шений. В этой точке функция Z(x) примет максимальное значение.

Вообще говоря, прямая Z может иметь с многоугольником допустимых

решений (на входе и на выходе ) либо одну общую точку (выршину многоу-

гольника), либо бесконечное множество точек (сторону многоугольника).

Если область допустимых решений незамкнута, то минимума и (или) макси-

мума Z(x) можем не быть совсем.

Рассмотрим типичную задачу линейного программирования. Пусть не-

кий цех с про6и0зводительностью 450 тонн продукта в месяц способен про-

изводить три разновидности этого продукта. Согласно договорам цех дол-

жен изготовить не менее 40-ка тонн первой, 60-ти тонн второй, 80-ти

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

разновидностей продукта используются четыре материала в различных со-

отношениях. Цех располагает следующими запасами материалов: первого -

100 тонн, второго - 150 тонн, третьего - 120 тонн и четвертого - 180

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

разновидности продукта сведены в таблицу.

┌─────────────────┬─────────────┬───────────┬───────────┬────────────┐

│6──┐Расход матери-0│ │ │ │ │

6│ └──┐ала на0 6одну0│ │ │ │ │

6│Раз-0 6└──┐тонну0 6│0 I-го │ II-го │ III-го │ IV-го │

│6новидно-└───┐0 6│0 │ │ │ │

│6сти продукта└────0│ │ │ │ │

├─────────────────┼─────────────┼───────────┼───────────┼────────────┤

│первая │ 0.3 тонны │ 0.2 тонны │ 0.4 тонны │ 0.4 тонны │

│вторая │ 0.2 тонны │ 0.1 тонны │ 0.3 тонны │ 0.6 тонны │

│третья │ 0.2 тонны │ 0.5 тонны │ 0.2 тонны │ 0.3 тонны │

└─────────────────┴─────────────┴───────────┴───────────┴────────────┘

Требуется найти оптимальное (в смысле максимизации прибыли) коли-

чество каждого вида изготавливаемого продукта при условии, что стои-

мости 6 0разновидностей 6 0этого 6 0продукта 6 0равны: 6 0первого - 13.5, второ6-

го -11.36 и0 третьего - 8.2 денежные единицы за тонну.

Для решения приведенной выше задачи при помощи системы Eureka

нужно сделать следующую запись в окне Edit.

6$ max (f)

6Z(x,y,v)=13.5*x+11.3*y+8.2*v

60.3*x+0.2*y+0.2*v 7,6 100

60.2*x+0.1*y+0.5*v 7,6 150

60.4*x+0.3*y+0.2*v 7,6 120

60.4*x+0.6*y+0.3*v 7,6 180

6x7 . 640 : y7 . 660 : v7 . 680

6x+y+v 7, 6450

6f=Z(x,y,v)

После решения получаем следующие результаты.

6f 7~6 4538.9983 , x 7~6 90.001006 , y 7~6 119.99876 , v 7~6 239.99985

6x+y+v 7~6 499.9996

6Поcле подстановки получаем:

60.3*x+0.2*y+0.2*v 7~6 99.000023

60.2*x+0.1*y+0.5*v 7~6 150.00000

60.4*x+0.3*y+0.2*v 7~6 120.00000

60.4*x+0.6*y+0.3*v 7~6 179.99961

_Вывод формулы (*)

6───(A(x - 7a6u),x -7 a6u) - (b,x -7 a6u) =

61 1

6= ───(A(x -7 a6u),x) - ───(A(x - 7a6u),7a6u) - (b,x) + (b,u)7a6 =

62 2

61 ┌ ┐

6= ───│ (Ax,x) - (Au,x)7a6 - (Ax,u)7a6 +5 6(Au,u)7a526 │- (b,x) + (b,u)7a6 =

62 └ ┘

6─────────────────────────────────────────────────────────────────────

Заметим,6 0что (Au,x)6 0=6 0(Ax,u). 6 0Действительно,6 0(Au6,0x)6 0=6 0(6u0,6Ax0)

6т.к. 0А - симметричная матрица6 и (u,Ax) = (Ax,u) по свойству скалярно-

6го произведения .

61 ┌5 ┐

6= ───│ (Ax,x) + (Au,u)7a52 │6 - (Ax,u)7a6 - (b,x) + (b,u)7a6 =

62 └5 ┘

6( т.к. u = Ax - b , то Ax = u + b )

61 ┌5 ┐

6= ───│ (Ax,x) + (Au,u)7a52 │ - 6(u + b,u)7a6 - (b,x) + (b,u)7a6 =

62 └5 ┘

617 6┌ ┐

6= ───│ (Ax,x) + (Au,u)7a526 │ - (u,u)7a6 - (b,u)7a6 - (b,x) + (b,u)7a6 =

62 └ ┘

61 1

6= ───(Au,u)7a52 -6 (u,u)7a6 + ───(Ax,x) - (b,x) .

62 2

6Задание

6───────────

а) Составьте матрицу А для предложенной вам квадратичной функции.

Проверьте при помощи критерия Сильвестра положительную определенность

матрицы А. Найдите

6(7l4max6 -4 7l4min6)

6q = ───────────────

6(7l4max6 -7 l4min6)

являющееся знаменателем геометрической прогрессии со скоростью которой

сходится 6 0метод 6 0наискорейшего 6 0спуска. (Для этого составьте уравнение

6det (A -7 l6E) = 0 и решите его используя процедуру 4 6poly(x,a4n6,...,a406)4.

б) Придумайте пример задачи линейного программирования и решите

эту задачу при помощи системы Eureka. Измените коэффициенты целевой

функции и ограничения. Решите задачу заново. Придумайте трактовку по-

лученным результатам.

Лабораторная работа N4

4─────────────────────────

Приближение функций. Вычисление определенных

интервалов. Решение дифференциальных уравнений.

6Цель работы

6──────────────

Приобретение навыков вычисления определнных интегралов, реше-

ния диф. уравнений и приближения функций методом наименьших квад-

ратов при помощи системы Eure6k0a.

6Теоретическое введение

6─────────────────────────

I)6 Вычисление определенных интегралов

7\\\\\\\\\\\\\\\\\\\\

Разобъем отрезок интегрирования [a,b] на отрезки [x4i-10,x4i0]

точками a=x400

интегралов:

6n x4i

6────┐ ────┐7 !

6I = I4i6 = 7 26 f(x) dx (1)

6/ /7 2

6────┘ ────┘7 1

6i=1 x4i-1

6Обозначим: f4i6=f(x4i6) , f4i-1/26=f(x4i-1/26)4 ,6 где x4i-1/26=(x4i-1 6+ x4i6)/2

Шаг h=x4i0- x4i-10 будем считать постоянным.

а) Заменим 6 0приближенно 6 0каждый 6 0интеграл из формулы (1) пло-

щадью прямоугольника, основание 6 0которого 6 0отрезок6 0 [x4i-10,x4i0], а вы-

сота равна f4i-1/20. Тогда мы получим приближенное равенство:

6─────┐

6I 7~6 h f4i-1/26 = I4пр6 4 6 (2)

6─────┘

6i=1

Формула (2) называется составной6 0 квадратной 6 0формулой6 0 прямоу-

гольников.

б) Заменим приближенно каждый интеграл6 0 из6 0 формулы (1)6 0 пло-

щадью 4 0трапеции, стороны 4 0которой6 4 6 [x4i-16,x4i6] , [x4i-16,(x4i-16,f4i-16)] ,

6[(x4i-16,f4i-16),(x4i6,f4i6)] и0 6[x4i6,(x4i6,f4i6)] .0 При 6 0этом мы получим прибли6-

женное равенство:6

6┌ ─────┐ ┐

6│ f406 + f4n6 f4i6 │

6I7 ~6 h │───────── + / │ = I4тр6 (3)

6│ 2 ─────┘ │

6└ i=1 ┘

Формула (3) называется составной квадратной формулой трапеций.

в) Заменим приближенно 4 0каждый интеграл 4 0из формулы (1) пло6-

щадью 6 0фигуры, расположенной 6 0под парабалой, проходящей через точки:

6(x4i-16,f4i-16) , (x4i-1/26,f4i-1/26) 0и 6(x4i6,f4i6)0. 6 0После6 4 6 0интегрирования6 4 0и

соответствующих преобразований получается приближенное равентство:

6n 4 6 n-1

6┌ 4 6 4 6 ─────┐ 4 6 ─────┐ ┐

6h0 6│ 4 6 4 6 4 6 │

6I7 ~6 ─── │ f40 6+ f4n6 + 4 / f4i-1/26 + 2 / f4i6 │ = I4с6 (4)

660 6│ 4 6 4 6─────┘ 4 6 ─────┘ │

6└ 4 6 4 6i=1 4 6i=1 ┘

Формула (4) называется составной квадратной формулой Симпсона.

г) П6р0иведенны6е0 выше способы в5 0ычисления5 0 определенного интегра-

ла 5 0дают достаточно х5 0орошую 5 0точность. Погрешености 5 0этих способов

таковы:

6M42 6(b - a) M426 (b - a)

6│ I - I4пр 6│ 7,6 ────────────4 6h52 6 и │ I - I4тр6 │7 ,6 ──────────── h526 ,

624 12

6где M426 = m a x │ f5''6(x) │

5[a,b]

6M446 (b - a)

6│ I - I4с6 │7 ,6 ───────────── h546 , где M446 = m a x │ f5''''6(x) │

628805 [a,b]

д) С помощью системы Eure6k0a можно вычислять определенные интегра6-

лы численным методом с контролем погрешности результата. Чем меньше

заданная погрешность, тем длинее 6 0процесс вычислений.6 0 Далее приво6-

дится запись, которую необходимо сделать в окне Edit для вычисления6

интеграла:

7! |\\\\

72 /5 6 x53

72 /5 7\\\\\6 dx

71 ?6 5 6x546 + 31

57.3

6( Запись в окне Edit )

6y(x)=sqrt(x^3/(x^4+31))

6z=integ(y(x),x,7.3,9)

После этого для получения решения6 0 надо 6 0подняться6 0 в верхнюю

строку меню и активизировать пункт Solve.

Следующий 6 0пример иллюстрирует задание6 0 функции 6 0пользователя,

содержащей 6 0вычисление 6 0опрделенного 6 0интеграла. 6 0В данном случае вы-

числяется 6 0путь, пройденной объектом6 0с 6 0постоянным ускорением. При

такой 6 0записи 6 0задачи 6 0используя пункт меню Graph 6 0можно 6 0построить

график пройденного пути.

v(t)=7*t+5

s1=integ(v(t),t,0,4)

s(tp)=integ(7*t+5,t,0,tp)

Если с помощью функций вычисления6 0 интегралов 6 0и 6 0производных

задаются 6 0функции6 0пользователя, то6 0 нужно 6 0необходимые6 0 функциональ-

ные 6 0зависимости задавать после открывающей 6 0скобки 6 0списка6 0 аргу-

ментво.6 0 В 6 0противном6 0 случае могут6 0 возникать6 0 больше погрешности

из-за неучета особого статуса переменных.

С6 0 помощью6 0 системы 6 0Eure6k0a 6 0можно 6 0вычислять и кратные интегралы.

При6 0 этом может потребоваться6 0 использование 6 0команды 6 0Interate 6 0для

уточнения 6 0вычислений, заканчивающих6 0из-за 6ис0черпания лимита6 0времени.

Для вычисления кратных интегралов:

46 8 6 42 4 6

7! ! 6 7! ! !

72 26 e5xy6 dxdy и7 6 72 2 26 xyz dxdydz

71 1 6 71 1 1

55 7.3 6 51 3 5

в окне редактирования должна быть записана следующая информа-

ция:

6I=integ(integ(exp(x*y),x,7.3,8),y,5,6)

6P=integ(x*integ(y*integ(z,z,1,2),y,3,4),x,5,6)

II) Приближение функций методом наименьших квадратов.

7\\\\\\\\\\\\\\\\\\\\\\\\\\\

а) Пусть 7 0функция 7 0y=f(x) задана 7 0таблицей 7 0приближенных значений

y4i7~0f(x4i0),7 0i=0,1,...,n4 0полученных с ошибкой 7e4i0=y4i5*0-y4i0, где6 y4i5*6=f(x4i6)

Используем для аппроксимации функции f линейную модель:

6y7 6=7 F4m6(x)7 =6 a407f406(x) + a417f416(x) +...+ a4m7f4m6(x)

Здесь 6 7f406(x),7f416(x),...,7f4m6(x) 0- 6система фундаментальных функций,

6a406,a416,...,a4m6 -0 6искомые 0параметры 6 0модели, 6 0являющиеся коэффициентами

обощенного многочлена7 F4m6(x).

Теперь мы можем записать систему приближенных неравенств:

6a407f406(x406) + a417f416(x406) +...+ a4m7f4m6(x406) 7~6 y40

6a407f406(x416) + a417f416(x416) +...+ a4m7f4m6(x416) 7~6 y41

6.......................................

6a407f406(x4n6) + a417f416(x4n6) +...+ a4m7f4m6(x4n6) 7~6 y4n

6и0ли в матричном виде : Pa=y.

В 6 0качестве 6 0критерия 6 0для 6 0выбора 6 0параметров 6 0a400,a410,...,a4m 0в

методе наименьших квадратов используется min S(a,y), где

6n0 6┌ m ┐52

6────┐ │ ────┐ │

6S(a,y) = │ a4j7f4j6(x4i6) - y4i6│ , где a=(a406,a416,...,a4m6)

6/ │ / │

6────┘ │ ────┘ │

6i=00 6└ j=0 ┘

Простейший6 0 способ 6 0решения 6 0этой задачи 6 0состоит в использовании

необходимого условия экстремума 6функции S 0:

6dS

6──── = 0 , k=0,1,...,n

6da4k

6Вычисляя частные производные и меняя порядок суммирования при-

6ходим к системе линейных алгебраических уравнений :

6m0 6┌ n 4 6┐ n

6─────┐ │ ─────┐ 4 6 │ ─────┐

6 │ 7 f4j6(x4i6)7f4k6(x4i6)│ a4j6 = 4 6 y4i7f4k6(x4i6) , (k=0,1,...,n)

6/ │ / 4 6 │ 4 6/

6─────┘ │ ─────┘ 4 6│ 4 6─────┘

6j=00 6└ i=0 4 6┘ i=0

которая 4 0называется нормальной системой метода наименьших4 0квадратов.

В матричном виде эту систему можно записать так:

6P5T6Pa = Py 5 6Обозначим:5 6 P5T6P = Г и P5T6y = b , тогда

6Гa = b (5)

Искомые параметры 6a406,a416,...,a4m0 являются решении системы (5).

Если6 0 при аппроксимации6 0 функции y=f(x) используется6 0 модель

g(x,a), 6 0где g(x,a)6 0нелинейно зависит 6 0от 6 0параметров 6 0a400,a410,...,a4m0,

то применение критерия наименьших квадратов приводит к задаче оп-

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

6─────┐ ┌ 4 6┐52

6S(a,y) = │ g(x4i6,a) - y4i6│

6/ │ 4 6│

6─────┘ └ 4 6┘

6i=0

Такая4 0 задача 4 0весьма трудна для решения и требует4 0специальных

методов 4 0минизации для 4 0нахождения 4 0параметров, однако 4 0в некоторых

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

мер, зависимость y от x ищется в виде y=ae5bx0, где a>0. 4 0Логарифмируя

это 6 0равенство, 6 0 приходим 6 0к 6 0линейной 6 0зависимости 6 0ln6(0y6)0=ln6(a)+bx

велечины 6 Y0=ln6(0y6) 0 от6 0 x.

б) Рассмотрим несколько примеров решения указанной выше 6 0задачи в

системе Eure6k0a.

_Пример1

Пусть имеется ряд точек 6 0(x410,y410),(x420,y420),...(x4n0,y4n0) и надо 6 0подо6-

брать коэффициенты a и b линейной зависимости:

6y(x)=a+bx т.е.7 f406(x)=1,7 f416(x)=x (6)

такими, чтобы 6 0 прямая 6 0y(x)6 0 прошла в "облаке" 6 0точек 6 0с 6 0наименьшим

6общим 0среднеквадратичным 6 0отключением от них. Зависимость (6) приб-

лиженная 6 0поэтому 6 0вместо знака 6 0точного равенства 6 0надо использовать

знак :=.6 0 Чтобы 6 0отдать системе 6 0команду 6 на0 решения методом наимень-

ших 6 0квадратов 6 0необходимо 6 0указать 6 0директиву $ substlevel=0. Пусть

координаты 6 0заданных точек таковы6 0:6 0(7,46.05),(9,7),(11,8),(15,96.07),

тогда в окне Edit должна быть сделана следующая запись

f(x):=a+b6*x

f(7)=4.5:f(9)=7:f(11)=8:f(15)=9.7

$ substlevel=0

После 6 0этого для6 0получения решения6 0 6н0адо подняться 6 0в верхнюю6 0стороку

меню и активизировать пункт Solve.

_Пример 2

Заданная линейная зависимость иммет более сложный вид:

y(x)=ax530+be5x0+c6(1/x)7 6 0 т.е. 7f400(x)=x530, 7f410(x)=e5x0, 7f420(x)=1/x

При этом записать в окне Edit будет иметь следующий вид:

f(x):=a*f1(x)+b*f2(x)+c*f3(x)

f1(x)=x^34 0:4 0f2(x)=exp(x)4 0:4 0f3(x)=1/x

f(3)=74 0:4 0f(4)=5.74 0:4 0f(5)=4.74 0:4 0f(6.3)=6.4

f(8.1)=7.544 0:4 0f(9)=8.74

$ substlevel=0

_Пример 3

Заданная 6 0нелинейная 6 0зависимость6 0имеет6 0вид:6 0y(x)=e5t6,5 6где t=ax5n6+b

Ecли в окне Edit сделана запись:

f(x):=exp(a*x^n+b)

f(1)=1.49:f(2)=2.35:f(3)=4.26

f(4)=8.59:f(5)=19.01

$ substlevel=0

, то в качестве ответа будут получены значения:

a=0.25247859 6, 0b=0.14432727 6, 0 6n0=1.4951058

6C0истема7 0 Eure6k0ca находит неизвестные параметры и для7 0 более

сложных зависимостей например y(x)=ae5-bx0+ab.

Eще один выжный вид аппроксимационной зависимости6 0-6 0полиномальная

зависимость y(x)=a4m0x5m0+...a410x+a400. Количество пар 6задан0ных точек должно

превышать6 0 m+1. Если 6 0оно 6 0равно 6 0этой 6 0велечине, то 6 0реализуется6 0 не

регрессия, а обчная полиномиальная аппроксимация.

6III) Решение дифференциальных уравнений.

7\\\\\\\\\\\\\\\\\\\\\

а) Система Eure6k0a 6 0не приспособлена для 6 0решения диф. уравнений.

Однако, в некоторых случаях система может решать задачу Кош6и0 6 0методом

Э6й0лера. При 6 0этом6 0прийдется6 0 ограничит6ь0ся несколькими (7-8) точками,

поскольку в6 0 противном6 0случае6 в0озможности6 0 системы6 0 преобразовывать

переменные и подставлять их друг в друга будут исчерпаны.6 0Отсутствие

в языке системы операторов6 организации циклов усложняет задачу. Кроме

6того переменные в системе Eureka переопределить нельзя, что иллюстри-

6руется примером. Пусть в окне Edit записана приведенная ниже информа-

6ция.

6y=7

6p(y)=sin(y)*exp(y)

6p1=p(4)

6y1=y

6y=847

6y2=y

6При этом в окне Solution после решения появляются следующие зна-

6чения переменных : y=7 , y1=7 и y2=7. Значение p1=p(4) будет вычис-

6лено верно.

6б) Приближенное решение задачи Коши методом Эйлера заключается

6в приближенном решении диф. уравнения y4x5'6=f(x,y(x)), удовлетворяющем

6начальному условию y(x406)=y406. Сеточное решение задачи состоит в пост-

6роении 4 6таблицы 4 6приближенных 4 6значений 4 6y416,y426,...,y4n 6 4 6в4 6 точках

6x416,x426,...,x4n6.4 6Чаще всего x4i6=x406+ih4 6, i=1,2,...,n. Точки x4i6 называются

6узлами сетки, a h - шагом сетки (h>0).

6В методе Эйлера y4i+16 вычисляется по формуле:

6y4i+1 6=4 6y4i 6+4 6hf(x4i6,y4i6) , i=0,1,.....

6Этот метод относится к группе одношаговых методов, в которых для

6расчета точки (x4i+16,y4i+16) требуется информация только о последней вы-

6численной точке (x4i6,y4i6).

6Метод имеет простую геометрическую интерпритацию. Предположим, что

6известна точка (x4i6,y4i6) на искомой интегральной кривой. Тогда каса-

6тельная к этой кривой, проходящая через точку (x4i6,y4i6) определяется

6уравнением:

6z(x)=y4i 6+ y4x5'6(x4i6)(x-x4i6) ,а т.к. 5 6y4x5'6(x4i6)=f(x4i6,y4i6) 4 6и4 6 x4i+16-x4i6=h ,

6то z(x4i+16) = y4i6+ hf(x4i6,y4i6)=y4i+1

6в) Запишем в качестве примера следующее диф. уравнение: y5'6-y = e5x

6с начальными условиями x406=3 , y(x406)=y406=4e536 , где e7 ~6 2.71828....

6Точным решением этого диф. уравнения является функция 5 6y = (x + 1)e5x6.

6Выберем шаг сетки h = 0.05 . В этом случае для решения диф. уравне-

6ния методом Эйлера в окне Edit должна быть сделана следующая запись:

6f(x,y)=exp(x)+y

6h=0.05 : x0=3 : y0=4*exp(3)

6y1=y0+h*f(x0,y0) : x1=x0+h

6y2=y1+h*f(x1,y1) : x2=x1+h

6y3=y2+h*f(x2,y2) : x3=x2+h

6y4=y3+h*f(x3,y3) : x4=x3+h

6y5=y4+h*f(x4,y4) : x5=x4+h

6y6=y5+h*f(x5,y5) : x6=x5+h

6y7=y6+h*f(x6,y6) : x7=x6+h

6Задание

6───────────

6а) Найдите точное решение предложенного вам диф. уравнения.

6б) Найдите при помощи системы Eureka сетечное решение

6диф. уравнения методом Эйлера.

6в) Получите приближенное решение диф. уравнения в аналитичес-

6кой форме используя для этого предложенную вам аппроксимационную за-

6висимость.

6г) Определите площадь, заключенную между графиком точного и

6графиком0 6приближенного решения на отрезке сеточного решения.

6д) Определите площадь, заключенную между графиком точного ре-

6шения и осью 0x на отрезке сеточного решения.

6e) Определите в процентах отношение площади, вычисленной в

6пункте (г), к площади, вычисленной в пункте (д).