Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010



страница1/6
Дата28.11.2012
Размер0.52 Mb.
ТипКурс лекций
  1   2   3   4   5   6


ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Бийский технологический институт (филиал)

государственного образовательного учреждения

высшего профессионального образования

«Алтайский государственный технический университет

им. И.И. Ползунова»

В.Г. Ефимов, Ю.Н. Ложкова

АЛГОРИТМЫ И МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
Курс лекций

Бийск

Издательство Алтайского государственного технического
университета им. И.И. Ползунова

2010

УДК 519.254 (075.8)

Е 91

Рецензенты: профессор кафедры МСИА БТИ АлтГТУ

В.А. Абанин;

в.н.с. ФГУП «ФНПЦ «Алтай»,

к.т.н. В.П. Карих

Е 91

Ефимов, В.Г.

Алгоритмы и методы обработки информации: курс лекций /
В.Г. Ефимов, Ю.Н. Ложкова; Алт. гос. техн. ун-т, БТИ. ЁC Бийск: Изд-во Алт. гос. техн. ун-та, 2010. ЁC 83 с.
Курс лекций дает обобщенное и систематизированное изложение методов обработки информации, в том числе с помощью прикладных пакетов программ. Изложены методы сглаживания, выравнивания и фильтрации, необходимые для обработки экспериментальных данных.

Пособие предназначено для студентов специальностей 080801 «Прикладная информатика в экономике» и 230201 «Информационные системы и технологии» по дисциплине «Алгоритмы и методы обработки информации».

 

УДК 519.254 (075.8)

Рассмотрено и одобрено на заседании научно-методического

совета Бийского технологического института.

Протокол № 4 от 28.01.2010 г.


© Ефимов В.Г., Ложкова Ю.Н., 2010

© БТИ АлтГТУ, 2010

СОДЕРЖАНИЕ
ЛЕКЦИЯ 1. ЦЕЛИ И ЗАДАЧИ КУРСАЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK51.1Освоение компьютерных технологий

интерполяцииЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..51.2Интерполяция как математический аппарат

моделирования при обработке данных

экспериментаЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK...51.3Компьютерная технология решения прикладных

задачЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK.61.4Теоретические основы компьютерной технологииЎK.61.5Основные элементы Maple 6ЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..7ЛЕКЦИЯ 2. МЕТОДЫ СГЛАЖИВАНИЯ ИСХОДНЫХ

ДАННЫХЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..112.1Сглаживание скользящим среднимЎKЎKЎKЎKЎKЎKЎK...112.2Сплайн-функцииЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK.13ЛЕКЦИЯ 3. МЕТОДЫ ИНТЕРПОЛЯЦИИЎKЎKЎKЎKЎKЎKЎKЎK...163.1Интерполяция точная в узлахЎKЎKЎKЎKЎKЎKЎKЎKЎK....163.2Интерполяционные полиномыЎKЎKЎKЎKЎKЎKЎKЎKЎK..173.3Интерполяционная формула ЛагранжаЎKЎKЎKЎKЎKЎK193.4Табличные разностиЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK...203.5Интерполяционная формула НьютонаЎKЎKЎKЎKЎKЎK..203.6Представление функции интерполяции

полиномамиЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK.22ЛЕКЦИЯ 4. ФОРМУЛЫ ИНТЕРПОЛЯЦИИЎKЎKЎKЎKЎKЎKЎK...244.1Интерполяционная формула Ньютона
при неравноотстоящих узлахЎK.ЎKЎKЎKЎKЎKЎKЎKЎKЎK244.
2Сплайн-интерполяцияЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK254.3Интерполяция нелинейными функциямиЎKЎKЎKЎKЎK.264.4Интерполяция, приближенная в узлахЎKЎKЎKЎKЎKЎK..28ЛЕКЦИЯ 5. МЕТОДЫ АППРОКСИМАЦИИЎKЎKЎKЎKЎKЎKЎK..315.1Функция interpЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK.315.2Метод наименьших квадратов (МНК)ЎKЎKЎKЎKЎKЎK..325.3Аппроксимация ПадеЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..355.4Аппроксимация Паде с помощью полиномов

ЧебышеваЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK.....36ЛЕКЦИЯ 6. КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ

МНОГОПАРАМЕТРИЧЕСКОЙ ИНТЕРПОЛЯЦИИЎKЎKЎKЎK..376.1Многопараметрическая интерполяция точная

в узлахЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK.ЎKЎKЎKЎKЎKЎK.

39ЛЕКЦИЯ 7. ПРИМЕРЫ ИСПОЛЬЗОВАНИЯ

МНОГОПАРАМЕТРИЧЕСКОЙ ИНТЕРПОЛЯЦИИЎKЎKЎKЎK..42ЛЕКЦИЯ 8. АВТОМАТИЗАЦИЯ РЕШЕНИЯ ЗАДАЧ

ИНТЕРПОЛЯЦИИЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..458.1Программа TableCurve 2DЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..458.2Выбор формулы интерполяции ProcessЎKЎKЎKЎKЎKЎK47ЛЕКЦИЯ 9. ВЫБОР ОПТИМАЛЬНОГО РЕШЕНИЯЎKЎKЎKЎK.48ЛЕКЦИЯ 10. КОМПЬЮТЕРНЫЕ ТЕХНОЛОГИИ

В ЗАДАЧАХ ФИЗИКИ И ЭКОНОМИКИЎKЎKЎKЎKЎKЎKЎKЎK....5010.1Компьютерные технологии в задачах физикиЎKЎKЎK.5010.2Интерполяция в экономических задачах ЎKЎKЎKЎKЎK.5110.3Транспортная многопараметрическая задачаЎKЎKЎK..53ЛЕКЦИЯ 11. ЗАДАЧА МАССОВОГО ОБСЛУЖИВАНИЯЎK...5611.1Оценка надежности техники по опытным даннымЎK.58ЛЕКЦИЯ 12. ВЫБОР ФУНКЦИИ ИНТЕРПОЛЯЦИИЎKЎKЎKЎK6012.1Выбор метода интерполяцииЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK.60ЛЕКЦИЯ 13. ОПРЕДЕЛЕНИЕ ПОКАЗАТЕЛЕЙ
НАДЕЖНОСТИ ПО ДАННЫМ ЭКСПЛУАТАЦИИ

ВОССТАНАВЛИВАЕМОЙ ТЕХНИКИЎKЎKЎKЎKЎKЎK................62ЛЕКЦИЯ 14. РЕЙТИНГ-СИСТЕМЫЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK65ЛЕКЦИЯ 15. КОМПЬЮТЕРНЫЕ ТХНОЛОГИИ ОЦЕНКИ

ЗНАНИЙЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK...............6815.1Закономерность получения знаний по закону

ПаретоЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..68ЛЕКЦИЯ 16. ФУРЬЕ-ПРЕОБРАЗОВАНИЕЎKЎKЎKЎKЎKЎKЎKЎK7316.1Оконное преобразование ФурьеЎKЎKЎKЎKЎKЎKЎKЎKЎK7416.2Быстрое преобразование ФурьеЎKЎKЎKЎKЎKЎKЎKЎKЎK75ЛЕКЦИЯ 17. ОСНОВНЫЕ ЭЛЕМЕНТЫ И СВОЙСТВА ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK...7617.1Результаты вейвлет-преобразования.............................7817.2Достоинства и недостатки вейвлетных

преобразованийЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK...81ЛИТЕРАТУРАЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎKЎK..82


ЛЕКЦИЯ 1. ЦЕЛИ И ЗАДАЧИ КУРСА
1.1 Освоение компьютерных технологий интерполяции
Этапами процесса открытий законов природы являются: наблюдения, размышления, эксперимент, открытие. Результатом эксперимента могут быть таблицы, графики, диаграммы, которые не являются физическими законами. Только математическая модель объекта в виде формулы может быть законом.

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

1. Выбор вида функции интерполяции.

2. Определение степени многочлена, если функция интерполяции является многочленом µ §-ой степени.

3. Выбор вида и метода интерполяции.

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

5. Вычисление погрешности математической модели.

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

Необходимость моделирования определяется следующими моментами:

объект слишком велик или мал;

объект удален от исследователя;

объект недосягаем во времени;

эксперимент слишком дорог.

Интерполяция, теория размерностей и теория подобия ЁC это научные основы моделирования, а широта использования, практическая направленность и значимость определяют основные черты интерполяции.

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

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

моделирования при обработке данных эксперимента
В таблице 1 представлены основные области применения и задачи, решаемые с помощью интерполяции.
Таблица 1 ЁC Области применения и задачи интерполяции

ОбластьЗадачаСущностьТеоретическая физикаОтыскание
законов

физических явленийНахождение по данным эксперимента модели объекта, который является физическим законом и который нужно доказать теоретическиЭкономикаЦенообразование, плата за услуги, транспортные задачиПолучение модели путем решения задачи интерполяции. Замена активного эксперимента пассивнымТехникаОтказы элементовПолучение законов распределения отказов по данным эксплуатации и характеристик надежностиСистемы
управленияАнализ сложных системПредставление сложной функции в узком диапазоне аргументов более простой

1.3 Компьютерная технология решения прикладных задач
Компьютерная технология ЁC это последовательность выполнения функций и команд компьютера для решения задач интерполяции. Технология включает:

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

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

оценка адекватности модели.

Необходимо знать:

способы построения графиков функций;

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

способы вычислений значений функции и ее табулирование;

операции с векторами и матрицами;

решение систем линейных и нелинейных функций.
1.4 Теоретические основы компьютерной технологии
Основы компьютерных технологий можно представить с помощью следующих составных элементов:

формулирование задачи;

исходные данные;

данные, которые необходимо определить;

допустимая погрешность интерполяции;

выбор метода интерполяции;

выбор вида функции интерполяции;

решение задачи с помощью универсального программного средства;

оценка адекватности модели.
1.5 Основные элементы Maple 6
Система Maple, первые версии которой появились в начале 90-х годов, является системой компьютерной алгебры, сочетающей в себе символьные вычисления, численные методы расчетов и широкие возможности графической визуализации результатов. Maple ЁC интегрированная программная система, объединяющая следующие основные блоки:

язык программирования;

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

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

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

библиотеки встроенных функций;

словарь математических понятий и терминов;

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

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

средства для объектного программирования (Maplets);

удобная справочная система с огромным количеством примеров.
1. Основная операция evalf <выражение>

evalf(-1/2*cos(6)+1/2);

exp(5)/2+1/4; µ §

evalf(%);

sqrt(2); µ §

evalf(%);
2. Решение системы уравнений

s:={x+3*y=2,-2*x+y=7}; µ §

z:=solve(s,{x,y});
3. Проверка решения

subs(z,s); µ §
4. Упрощение выражений

a:=(x+y)^3:

> expand(a); x^3+3*x^2*y+3*x*
5. Табулирование функции ѓЪ(х) и сравнение с исходными данными.

Табулирование функции ЁC это вычисление значений функции при изменении аргумента от некоторого начального значения до некото-рого конечного значения с определенным шагом. Именно так сос-тавляются таблицы значений функций, отсюда и название ЁC табу-лирование. Необходимость в табулировании возникает при решении достаточно широкого круга задач. Например, при численном решении нелинейных уравнений f(x)=0 путем табулирования можно отделить (локализовать) корни уравнения, т.е. найти такие отрезки, на концах которых функция имеет разные знаки. С помощью табулирования можно, хотя и очень грубо, найти минимум или максимум функции. Иногда случается так, что функция не имеет аналитического предс-тавления, а ее значения получаются в результате вычислений, что часто бывает при компьютерном моделировании различных процесс-сов. Если такая функция будет использоваться в последующих расчетах (например, она должна быть проинтегрирована или продиф-ференцирована и т.п.), то часто поступают следующим образом: вы-числяют значения функции в нужном интервале изменения аргумента, т.е. составляют таблицу (табулируют), а затем по этой таблице строят каким-либо образом другую функцию, заданную аналитическим выра-жением (формулой). Необходимость в табулировании возникает также при построении графиков функции на экране компьютера.

Проверка правильности решения задачи интерполяции можно осуществить путем табулирования функции µ §

Здесь µ § ЁC функция интерполирования; µ § ЁC значения аргумента µ §. Имеем функцию, которую необходимо протабулировать:

seq(2.3*x^2+1.35*x+3.6,x={1,2,3,4,5});
7.25; 15.50; 28.35; 45.80; 67; 85.
Сравнивая эти данные с исходными, можно судить о правиль-ности решения задачи интерполяции.
6. Проверка правильности решения основана на использовании графических образов. Функция plot.

Пусть функция y(х) задана в виде:
х123456µ §2,53,76,24,12,92

и функция интерполяции является полиномом:

µ §,

тогда функция plot имеет вид:
Plot({[[1,2.5],[2,3.7],[3,6.2],[4,4.1],[5,2.9],[6,2]],-
0.45*x^2+3*x+0.05},x=0...7);
На рисунке 1 представлено графическое отображение проведенного процесса.
y


Рисунок 1 ЁC Графическое отображение проведенного процесса

7. Погрешность интерполяции

µ §,

где n ЁC число узлов;

µ §.

Последовательность:

1. Представить в векторной форме µ § и (x).

2. Для представления (x) выполнить табулирование функции с помощью функции seq.

3. Найти разность векторов.

4. Найти сумму квадратов разности.

5. Извлечь корень квадратный и разделить на n.

Для вычисления суммы квадратов разности используется функция evalm(A&*B). Эта функция загружается командой with(linalg).

Пример. Функция µ § взята из пункта 5. Протабулируем вектор функции: µ §.
>seq(-0.45*x^2+3*x+0.05,x={1,2,3,4,5,6});

µ §

with(linalg);

y1:=[2.5,3.7,6.2,4.1,2.9,2]; y1:=[2.5, 3.7, 6.2, 4.1, 2.9,2]

y2:=[2.6,4.25,5,4.85,3.8,1.85]; y2:=[2.6, 4.25, 5, 4.85, 3.8, 1.85]

e:=evalm((y1-y2)&*(y1-y2)); e:=3.1475
Среднеквадратичная погрешность

> E:=sqrt(e)/6;


ЛЕКЦИЯ 2. МЕТОДЫ СГЛАЖИВАНИЯ
ИСХОДНЫХ ДАННЫХ
2.1 Сглаживание скользящим средним
Имеем истинное значение функции µ § и наложенную статистическую ошибку µ §. Цель сглаживания ЁC уменьшение этой ошибки. Одним из эффективных методов является использование формул простого скользящего среднего.

- Простое скользящее среднее:

µ §.

Основные свойства:

1. Уменьшение нерегулярности колебаний в ряде.

2. Смещение сглаженных значений.

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

- Взвешенное среднее:

µ §.

- Неискажающие пятичленные формулы Гильдебранда:

µ §;

µ §;

µ §.
Первая формула предназначена для основной части, вторая и третья ЁC для последних значений таблицы.

Веса для оптимальных сглаживающих формул приведены в таблице 2. Формулы симметричны, коэффициент µ § соответствует центральному «весу», а µ § ЁC каждому из весов, примыкающих к центральному, и т.д.

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

Таблица 2 ЁC Веса для оптимальных сглаживающих формул

Число членов в формуле5791113К00,5594410,4125870,3311400,2779450,240057К10,2937060,2937060,2665570,2386930,214337К2-0,0734270,0587410,1184700,1412670,147356К3-0,058741-0,0098730,0357230,065492К4-0,040724-0,0267920,000000К5-0,027864-0,027864К6-0,019350

Таблица 3 ЁC Сглаживающий эффект девятичленной формулы

µ §Наблюдаемое значение µ §Сглаженное значение µ §35953663837191384193927833740381413844266543477

µ §
Рисунок 2 иллюстрирует сглаживающий эффект девятичленной формулы.

Рисунок 2 ЁC Сглаживающий эффект девятичленной формулы
2.2 Сплайн-функции
Задачу подбора многочлена, кривая которого проходит через n заданных точек, удается решать с помощью сплайнов. Сплайн ЁC это функция, кривая которой состоит из отрезков полиномиальных кривых. Эти отрезки состыкованы так, что производные заданной функции (до порядка µ §) непрерывны на всем рассматриваемом промежутке. Сплайн обеспечивает непрерывность производных интерполяционной функции при условии, что степень многочленов, используемых для сглаживания исходных данных, ниже степени того единственного многочлена, кривая которого проходит через все заданные точки.

Имеем µ § и предположим, что имеется многочлен степени три или менее, кривая которого проходит через точки µ § и µ §. Нужно подобрать многочлен третьей степени:
  1   2   3   4   5   6

Похожие:

Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconМетодические рекомендации для студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы» Бийск
Издательство Алтайского государственного технического университета им. И. И. Ползунова
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconМетодические рекомендации по самостоятельной работе студентов специальностей 080801 «Прикладная информатика в экономике», 230201 «Информационные системы и технологии» Бийск
Издательство Алтайского государственного технического университета им. И. И. Ползунова
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconМетодические рекомендации по выполнению лабораторной работы по дисциплине «Статистические методы в управлении качеством»
Издательство Алтайского государственного технического университета им. И. И. Ползунова
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconGeneral ciкадры если и не решают все, то очень многое
Коршунов Лев Александрович депутат Государственной Думы, зам председателя комитета по делам Федерации и региональной политике. Зав...
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconУчебное пособие «Политическая система кнр» для студентов специальностей «Регионоведение», «Международные отношения» Издательство
Олитическая система кнр обсуждена и одобрена на заседании кафедры востоковедения Алтайского государственного университета. Пособие...
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconИнвестиционный паспорт г. Бийск Алтайского края
Алтайского края. Благодаря запуску проектов по созданию в крае особых туристской и игорной экономических зон Бийск становится стратегической...
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconПрактикум по физике Издательство Иркутского государственного технического университета 2008 удк 53(075. 8) Ббк 22. 3
Рецензенты: зав. Кафедрой физики Иркутского государственного университета, д физ мат наук, профессор Щербаченко Л. А
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconКурс лекций по высшей геодезии раздел «теоретическая геодезия»
Курс лекций ведется на кафедре прикладной геодезии и фотограмметрии Полоцкого государственного университета для студентов специальности...
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 iconПрограмма-минимум кандидатского экзамена по специальности [Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей] по физико-математическим и техническим наукам
Московского государственного университета им. М. В. Ломоносова, Московского авиационного института (государственного технического...
Курс лекций Бийск Издательство Алтайского государственного технического университета им. И. И. Ползунова 2010 icon05. 02. 04 «Трение и износ в машинах» по техническим наукам
Института машиноведения им. А. А. Благонравова ран, Российского Государственного университета нефти и газа им И. М. Губкина, Ростовского...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org