Название: Информатика - Алгоритмы и программы (Н.В. Усольцев)

Жанр: Информатика

Просмотров: 1278


4. задание к работе

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

Разработать подпрограмму-функцию для поиска мин/макс методом прямого перебора с использованием при завершении параболической интерполяции. Если п.1 не выполнялся, использовать функцию IntClassic() из лабораторной работы № 8. Проанализировать зависимость результата поиска от числа разбиений.

Разработать  подпрограмму-функцию, реализующую метод трихотомии.

Разработать  подпрограмму-функцию, реализующую метод Фибоначчи.

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

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

Разработать подпрограмму-функцию для поиска мин/макс функции двух переменных методом простого перебора.

Разработать подпрограмму-функцию для поиска мин/макс функции двух переменных методом покоординатного изменения.

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

при определении направления градиента на каждом шаге;

при определении направления градиента при достижении мин/макс в выбранном направлении.

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

Указание: Для тестирования работы и отладки разрабатываемых в п.п. 7 – 10 подпрограмм рекомендуется использовать функцию вида             ,

где  и  - координаты мин/макс, заданные заранее.

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

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

Результаты работы функций должны быть графически иллюстрированы. Для функции одной переменной график строится либо Edgraf'ом, либо Origin'ом, а для функции двух переменных - Origin'ом в виде карты равных значений (лучше черно-белой).

 

5. Литература

4, 6, 7, 17,18 из списка литературы.

Список литературы

Березин Б.И., Березин С.Б. Начальный курс С и С++. М.: «Диалог-МИФИ», 1997  и последующие.

Подбельский В.В. Фомин С.С. Программирование на языке Си. М.: Финансы и статистика. 1999 и последующие.

Подбельский В.В. Язык C++.  М.: Финансы и статистика. 1999 и последующие.

Турчак Л.И. Основы численных методов. М.: Наука, 1987.

Самарский А.А., Гулин А.В.  Численные методы. М.: Наука, 1989.

Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. М.: Мир. 1998.

Мудров А.Е.  Численные методы для ПЭВМ на языках  БЭЙСИК, ФОРТРАН и ПАСКАЛЬ. Томск, МП "Раско",1992.

Форсайт Дж., Малькольм М., Моулер К.  Машинные методы математических вычислений. М.,Мир,1980.

Калиткин Н.Н. Численные методы. М.: Наука, 1978.

Aproxy.doc. Описание функций модуля Aproxy и их алгоритмов. Электронный документ.

Polynom.doc. Описание функций модуля Polynom и их алгоритмов. Электронный документ.

Spline.doc. Описание функций модуля Spline и их алгоритмов. Электронный документ.

Integral.doc. Описание функций модуля Integral и их алгоритмов. Электронный документ.

Simpson.doc. Описание функций модуля Simpson и их алгоритмов. Электронный документ.

Datafile.doc. Описание функций модуля Datafile и их алгоритмов. Электронный документ.

Root.doc. Описание функций модуля Root и их алгоритмов. Электронный документ.

Edgraf.doc. Руководство по работе с построителем графиков Edgraf. Электронный документ.

Origin.doc. Руководство по работе с построителем графиков Origin. Электронный документ.

Приложение 1

 

Обоснование алгоритма расчета

коэффициентов кубического сплайна

 

Индексация

 

Кубический сплайн строится для функции, заданной набором точек xi, yi. В традиционно принятой в интерполяционных задачах индексации минимальное значение x имеет индекс 0 (x0), а максимальное – n (xn). Значения xi предполагаются равноотстоящими:

,   (i = 1, 2, …, n).

Таким образом, число точек xi, yi составляет n+1, а число элементарных интервалов интерполяции – n.

Индекс сплайна, работающего на соответствующем интервале, совпадает с индексом правой границы этого интервала. Аналитическое выражение для сплайна имеет вид:

.                                      (1)

 

Алгоритм определения коэффициентов сплайнов

 

Исходными для определения коэффициентов n кубических сплайнов, интерполирующих функцию на интервале (x0, xn), являются следующие уравнения:

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

,             (i = 1,2, …, n);

                        ,        (i = 1,2, …, n);                                 (2)

· уравнения сшивки первых производных сплайнов на границах интервалов:

,   (i = 1,2, …, n – 1)                            ;                  (3)

· уравнения сшивки вторых производных сплайнов на границах интервалов:

,            (i = 1,2, …, n – 1).                                                  (4)

Два недостающих уравнения получаются из условия свободного закрепления концов сплайна:

               ;                                          (5)

                                     .                                         (6)

            Продифференцируем выражение (1) и подставим полученные выражения производных в (2 – 6):

;                                                                      (7)

;                                                                                                                      (8)

                                                        (i = 1,2, …, n)                                  ;                                (9)

                   (i = 1,2, …, n)                                  ;                (10)

    (i = 1,2, …, n – 1);                                  (11)

                                               (i = 1,2, …, n – 1)                        ;                    (12)

   

                                                                                                                                               (13)

                                                                                                                       (14)

 

Дальнейшие преобразования призваны исключить из уравнений (9) – (12) коэффициенты a, b, и d. Из (12) и (14) следует, что

                                                             (i = 1,2, …, n – 1);                                       (15)

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

Подставим (9) и (15) в (10):

Откуда следует, что

        (16)

 

Увеличим индексы этого выражения на единицу:

                                                                                                       (17)

а затем подставим (15) – (17) в (11):

В этом выражении остались только коэффициенты c. Перенесем в левую часть все члены, содержащие c, а в правую– содержащие y.  После приведения подобных членов получим:

или

                   (i = 1,2, …, n – 1).                                    (18)

Выражение (18) при разворачивании индекса i от 1 до n – 1 представляет собой систему линейных алгебраических выражений (СЛАУ) с трехдиагональной матрицей (в первом уравнении которой учтено, что  из (13) , а в последнем – что ):

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

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

1. Определение коэффициентов :

 

                                                            (i = 1,2, …, n)       .

 

2. Формирование матрицы коэффициентов и вектора свободных членов СЛАУ (18):              

· элементы главной диагонали

· элементы побочных диагоналей

· компоненты вектора свободных членов

3. Решение СЛАУ относительно                                                                    (i = 2, 3, …, n) и дополнение массива коэффициентов С элементом  .

4. Расчет коэффициентов :

                           (i = 2, 3, …, n).

5. Расчет коэффициентов :

                                                             (i = 2, 3, …, n).

 

Приложение 2

 

Работа с программой графической

обработки данных Origin

 

Origin представляет собой мощное программное средство научной и технической графики, совместимое с программными продуктами Microsoft, в частности, с Word и Excel. Это позволяет использовать его для создания качественных иллюстраций книг, статей, отчетов, инструкций и т.п.

В следующем далее тексте приводится вид окон Origin, соответствующий среде Windows-95/98.

 

Запуск Origin и завершение сеанса работы

 

Запуск Origin осуществляется двойным щелчком мыши на ярлыке (пиктограмме) Origin 4.1. После загрузки появляется окно (рис.1).

Завершается сеанс работы с Origin  одним из следующих способов:

            · последовательным выбором команд: File, Exit в верхнем меню;

· нажатием комбинации клавиш <Alt>+<F4>;

· закрытием окна Origin соответствующей кнопкой.

 

 

 

 

Рис. 1. Окно Origin после загрузки

Ввод табличных данных в ручном режиме

 

В основном окне Origin после загрузки имеется отдельное окно данных со стандартным именем Data1. Оно содержит рабочую таблицу (Worksheet) со столбцами A(X) и B(Y). В клетки этой таблицы можно вносить данные в ручном режиме. Нужная клетка выбирается курсором мыши или клавишами со стрелками. Число строк таблицы первоначально составляет 30, но автоматически увеличивается при вводе данных.

Число столбцов можно добавлять командами меню: Column, Add New Column. Удалить лишний столбец можно командами меню: Edit, Delete, предварительно выделив столбец щелчком мыши на его заголовке.

 

Ввод табличных данных из файла

 

Origin позволяет считывать и отстраивать данные, предварительно записанные в кодах ASCII в файл данных в виде двух и более столбцов. Файл  должен иметь расширитель *.dat, *.txt

или *.csv.

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

 

Построение двумерных  графиков

 

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

Если в таблице более двух столбцов, один из которых содержит значения аргумента, а другие – значения функций и все эти функции необходимо построить на одном графике, то нужно поступить следующим образом. Сначала построить график одной зависимости. Затем выделить в рабочей таблице другой столбец, щелчком мыши снова сделать активным окно графика и выполнить команды меню: Plot, Add Plot to Layer, Line .

 

 

 

 

Рис. 2. Окно Origin с окнами рабочей таблицы и графика

 

После этого на графике появится следующая кривая (рис. 3). Если не сделать активным окно графика перед выполнением команд, то команда Add Plot to Layer будет недоступна, а выполнение команды Line откроет новое окно с графиком второй зависимости, как показано на рис.4.

Если данные разных кривых, которые нужно построить на одном графике, находятся в разных файлах, то необходимо сначала от-строить одну кривую как обычно, а затем (при активном окне графика) выполнить команды меню: File, Import ASCII, Single File. Можно открыть сразу несколько файлов и добавить несколько кривых командой Multiple Files, выполняемой вместо Single File.

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

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

 

 

 

 

Рис. 3. Прорисовка двух кривых на одном графике

 

 

 

 

 

Рис. 4. Окно Origin с двумя окнами графиков

Построение трехмерных графиков

 

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

После формирования таблицы необходимо третий столбец обозначить как Z (выделить его и задать команды меню: Columns, Set as Z). Затем можно выполнить самую простую прорисовку в виде набора точек в изометрическом изображении трехмерного пространства координат (команды меню: Plot, 3D Charts, Scatter или Trajectory). При выполнении Trajectory точки будут соединены линией (рис. 5).

 

 

 

 

Рис. 5. Прорисовка трехмерного графика командами

Plot, 3D Charts, Trajectory

 

Более приемлемым является представление зависимости от двух аргументов в виде поверхности. Для получения гладкой поверхности данные предварительно обрабатываются. Для этого выполняется операция построения сетки (Gridding) командами меню: Edit, Convert to Matrix, Random XYZ. После задания последней появляется окно параметров Gridding, в котором можно менять число строк и столбцов создаваемой матрицы сетки. Чем больше эти числа, тем более гладкой получается прорисовываемая поверхность. После окончания Gridding в окне Origin появляется окно Matrix (рис. 6). Затем выполняется собственно прорисовка командами меню: Plot3D, 3D-Color Fill Surface. Результат прорисовки показан на рис. 7.

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

 

 

 

 

 

Рис. 6. Окно Origin с активным окном Matrix

 

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

вания.

 

 

 

 

 

Рис. 7. Окно Origin с прорисовкой трехмерного графика

в виде гладкой поверхности

 

Сохранение данных

 

Origin сохраняет свои данные в полном комплекте всех окон (рабочих таблиц, матриц, графиков) в виде Проектов. При этом записывается файл с расширением  *.opj. Для первоначального сохранения проекта необходимо выполнить команды меню: File, Save Project As, после чего откроется стандартное окно Windows поиска каталога для записи файла. Запись следует производить в свой рабочий каталог, а не в каталог Origin. Последующие сохранения под тем же именем можно выполнять командой Save Project.

 

Перенос графиков в Microsoft Word

 

Перенос графиков между различными приложениями Windows осуществляется через буфер обмена. Окончательно отредактированный график нужно скопировать в буфер командами меню: Edit, Copy Page. После этого следует запустить Word или развернуть его окно (если он уже был запущен) и выполнить вставку из буфера командами Правка, Вставить или соответствующей кнопкой. Размеры вставленного рисунка можно изменять, выделив вставленный объект и растягивая его стороны или углы. Можно производить и графическое редактирование как рисунка Word.