Содержание

                     Введение

1. Постановка  задачи…………………………………………………….....5

2. Математическая формулировка задачи………………………...………6

3. Алгоритмизация  задачи ………………………………………..…...…...8

4. Идентификаторы программы…………………………………………..10

5. Блок –  схема алгоритма………………………………………………...11

6. Текст исходной  программы…………………………………………….20

7. Результаты  выполнения программы…………………………………...25

8. Анализ  результатов……………………………………………………..28

9. Инструкция  по работе с программой………………………………….29

                 Заключение

                 Список использованных источников

                                        Введение

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

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

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

В данной пояснительной записке приводится описание последовательности шагов  по составлению программы на алгоритмическом  языке Turbo Pascal 7.0 и результаты применения этой программы.

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

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

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

                       f(x₁,x₂)=(x₁²+x₂²-1)²+(x₁³-x₂)²                              (1)

  Программа должна обеспечивать выбор метода пользователем посредством меню. Вид функции задаётся в подпрограмме –функции. Определить минимум функции (1).

Таким образом, программа должна обеспечивать возможность:

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

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

В результате сформулируем следующую задачу по созданию программы:

• программа после загрузки должна выводить на дисплей исходное окно-заставку, в которой отображаются общие сведения о статусе программы и её авторах;
• после выполнения указанной в строке подсказки процедуры перехода должно выводиться вертикальное меню с пунктами: «Справка», «Метод спирального координатного спуска», «Метод квадратичной интерполяции-экстраполяции» и «Выход»;
• при выборе в меню пункта «Справка» должна выводиться краткая, справка о назначении программы и порядке работы с ней;
• после выбора в меню пункта метода решения должно открываться отдельное окно, в котором будут выводиться запросы программы об исходных данных   и в этом же окне после ввода исходных значений будет выводиться результат вычисления виде функции;
• при выборе пункта меню «Выход» программы должна завершать работу.

2. Математическая формулировка  задачи

      Многомерная оптимизация заключается в поиске экстремумов функций многих переменных F(x₁,x₂) (рис. 1).

Рис.1 Поиск  экстремумов функции.

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

Пусть задана функция n переменных:

                                                   F(x₁,x₂, . . ., x_n).                                (2)

Поиск минимального значения начинаем с некоторой начальной точки  X_k и начального шага d(предельное значение для шага h). :

         d _{1 k}=h.                                                    (3)

Определяется  направление минимизации целевой  функции f(x)=f(x⁽¹⁾,x⁽²⁾,…,x⁽ⁿ⁾) в базисной точке:

                                                                                   (4)

  Для этого  последовательно дают приращение  переменным x^(j) в точке х_к. Присвоим z=x_k. Циклически даем приращение переменным x^(j) и формируем z^(j)=x_k^(j)+h, если f(z)<f(x_k), если же нет, то z^(j)=x_k^(j)-h, если f(z)<f(x_k), иначе z^(j)=x_k^(j). Так для всех j(j=1,2,…,n).

      Вычисляем значение функции в точках

F(X₁,...,X_k-h,...,P_n),                                   (5)

F(X₁,...,X_k,...,X_n),                                      (6)

F(X₁,...,X_k+h,...,x_n).                                  (7)

      Если из этих трех значений функция минимальна в крайней точке, то принимаем ее за начальную, если в средней точке (X₁,...,X_k,...,X_n), то она принимается за начальную, а размер шага по x_k уменьшается на коэффициент r и становится равным по k-му аргументу:

     h_{1 k}=h_{1 k} r.                                                 (8)

Вычисления прекращаются, если размер шага по всем аргументам становится меньше d-заданное или количество вычислений функции F становится больше m₂.

Метод квадратичной интерполяции-экстраполяции.

При использовании  метода квадратичной интерполяции-экстраполяции в качестве интерполяционной функции на каждом отрезке [x_i-1, x_i+1] принимается квадратный трехчлен. Уравнение квадратного трехчлена:

y=a_ix² + b_ix+c_i, x_i-1£x£x_i+1 (9)

содержит коэффициенты a_i, b_i, c_i для определения которых необходимы три уравнения. Ими служат условия для прохождения параболы (1) через три точки (x_i-1, y_i-1), (x, y_i), (x_i+1, y_i+1). Эти условия можно записать в виде:

a_ix_i-1² + b_ix_i-1 + c_i = y_i-1 

                                     a_ix_i² + b_ix_i + c_i = y_i                        (10)

a_ix_i+1² + b_ix_i+1 + c_i = y_i+1 

Отсюда находятся коэффициенты a_i, b_i, c_i:

где h=(x_i+1-x_i+1)/2.

Таким образом, абсцисса точки минимума

x_m=-b/(2c)      (13)

 Интерполяция для любой точки  проводится по трем ближайшим  к ней узлам. 

.

3. Алгоритмизация задачи

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

Алгоритм  работы головной программы следующий:

1. Скрыть курсор с использованием подпрограммы - процедуры скрытия курсора и вывести в специальном окне заставку программы, содержащую сведения о назначении программы, исполнителе и руководителе курсовой работы, а также подсказку для пользователя о последующих действиях, с использованием подпрограммы - процедуры заставки.
2. Запустить подпрограмму-процедуру вертикального меню при нажатии  любой клавиши .
3. Запустить подпрограмму-процедуру справки и вывести в специальном окне справочные сведения о работе с программой при выборе пункта меню «Справка» с использованием  строки-подсказки о возврате в меню.
4. Запустить подпрограмму-процедуру ввода  начальных условий: h-начального шага,  (x_1, x_{2 ,} x₃ )-начальных значений и точности результата-e. 
5. Запустить подпрограмму-процедуру поиска минимума функции и вывода результатов вычислений, а также строки-подсказки о возврате в меню.
6. Завершить работу программы при выборе пункта меню «Выход».

Алгоритм нахождения минимума функции методом координатного спуска в подпрограмме-процедуре включает следующие шаги:

1. Создать окно для ввода исходных данных и вывода результатов вычисления.
2. В подпрограмме-процедуре организовать ввод значений: начального шага поиска(δ=h), точности результата(е), в цикле ввести начальные значения x_i (i=1…2);
3. Вычислить значения функции в подпрограмме-функции в начальных заданных точках F(X₁+h,...,X_i,...,X_n);
4. Проверяем условие : если F(X₁,...,X_i,...,X_n)- F(X₁+h,...,X_i,...,X_n)<0, то переходим к п.4 и увеличиваем следующее начальное значение на шаг h: x_i=x_i+h;
5. Если не выполняется п.5, то меняем знак на противоположный и уменьшаем шаг на коэффициент R: h:=-h/R;
6. Проверяем условие: если |h|>e/5 , то идём к п.5;
7. Вывести результаты вычислений в том же окне;
8. Вывести в окне запрос о переходе к меню;

Алгоритм нахождения минимума функции методом квадратичной интерполяции-экстраполяции в подпрограмме-процедуре включает следующие шаги:

1.Создать окно для ввода исходных данных и вывода результатов вычисления.

2. В подпрограмме-процедуре организовать ввод значений: начального шага поиска(δ=h), точности результата(е), в цикле ввести начальные значения x_i (i=1…2);

3.   Организовываем цикл

     for i:=1 to n do

4. Вычисляем  два смежных  значения  аргумента F(x): x₀=x_i-h и x₂=x_i+h.
5. Вычисляем три значения F(x): F(x₀)=F₀ , F(x_i)=F_i и F(x₂)=F₂.
6. Вычисляем коэффициенты:

C=1/2h²*(F₀-2F_i+F₂),

D=((-F₀(2x_i+h)+4F_ix_i-F₂(2x_i-h)))/2h²,

и по ним  вычисляем аналитически положение  экстремума:

x_mi=-D/2C; 

7. Проверяем условие (x_mi-x_i)<E_. Если оно выполняется , задаём xi=x_mi и идём к п.3. Если выполняется то считаем x_mi найденным с заданной точность E, вычисляем F(x_m) и останавливаем счет.
8. Вывести результаты вычислений в том же окне;
9. Вывести в окне запрос о переходе к меню;