Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Реферат - Компьютерное имитационное моделирование - файл n1.doc


Реферат - Компьютерное имитационное моделирование
скачать (768.5 kb.)

Доступные файлы (1):

n1.doc769kb.21.12.2012 14:41скачать

Загрузка...

n1.doc

Реклама MarketGid:
Загрузка...
Компьютерное имитационное моделирование


Компьютерное имитационное моделирование. Статистическое имитационное моделирование.

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

  1. построении математических моделей для описания изучаемых процессов;

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

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

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

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

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

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

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

"Имитационное моделирование" (ИМ)- это двойной термин. "Имитация" и "моделирование" - это синонимы. Фактически все области науки и техники являются моделями реальных процессов. Чтобы отличить математические модели друг от друга, исследователи стали давать им дополнительные названия. Термин "имитационное моделирование" означает, что мы имеем дело с такими математическими моделями, с помощью которых нельзя заранее вычислить или предсказать поведение системы, а для предсказания поведения системы необходим вычислительный эксперимент (имитация) на математической модели при заданных исходных данных.

Основное достоинство ИМ:

  1. возможность описания поведения компонент (элементов) процессов или систем на высоком уровне детализации;

  2. отсутствие ограничений между параметрами ИМ и состоянием внешней среды РПС;

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

Эти достоинства обеспечивают имитационному методу широкое распространение.

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

  1. Если не существует законченной постановки задачи исследования и идет процесс познания объекта моделирования. Имитационная модель служит средством изучения явления.

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

  3. Когда кроме оценки влияния параметров (переменных) процесса или системы желательно осуществить наблюдение за поведением компонент (элементов) процесса или системы (ПС) в течение определенного периода.

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

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

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

  7. Когда изучаются новые ситуации в РПС. В этом случае имитация служит для проверки новых стратегий и правил проведения натурных экспериментов.

  8. Когда особое значение имеет последовательность событий в проектируемых ПС и модель используется для предсказания узких мест в функционировании РПС.

Однако ИМ наряду с достоинствами имеет и недостатки:

  1. Разработка хорошей ИМ часто обходится дороже создания аналитической модели и требует больших временных затрат.

  2. Может оказаться, что ИМ неточна (что бывает часто), и мы не в состоянии измерить степень этой неточности.

  3. Зачастую исследователи обращаются к ИМ, не представляя тех трудностей , с которыми они встретятся и совершают при этом ряд ошибок методологического характера.

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

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

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

В вероятностных аналитических моделях влияние случайных факторов учитывается с помощью задания вероятностных характеристик случайных процессов (законы распределения вероятностей, спектральные плотности или корреляционные функции). При этом построение вероятностных аналитических моделей представляет собой сложную вычислительную задачу. Поэтому вероятностное аналитическое моделирование используют для изучения сравнительно простых систем.

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

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

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

При реализации на ЭВМ статистического имитационного моделирования возникает задача получения на ЭВМ случайных числовых последовательностей с заданными вероятностными характеристиками. Численный метод, решающий задачу генерирования последовательности случайных чисел с заданными законами распределения, получил название "метод статистических испытаний" или "метод Монте-Карло".

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

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

Метод Монте-Карло - это численный метод, моделирующий на ЭВМ псевдослучайные числовые последовательности с заданными вероятностными характеристиками.

Методика статистического моделирования состоит из следующих этапов:

  1. Моделирование на ЭВМ псевдослучайных последовательностей с заданной корреляцией и законом распределения вероятностей (метод Монте-Карло), имитирующих на ЭВМ случайные значения параметров при каждом испытании;

  2. Преобразование полученных числовых последовательностей на имитационных математических моделях.

  3. Статистическая обработка результатов моделирования.

Обобщенный алгоритм метода статистических испытаний представлен на рис. 5.1.

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

Компьютерное моделирование и вычислительный эксперимент как новый метод научного исследования заставляет совершенствовать математический аппарат, используемый при построении математических моделей, позволяет, используя математические методы, уточнять, усложнять математические модели. Наиболее перспективным для проведения вычислительного эксперимента является его использование для решения крупных научно-технических и социально-экономических проблем современности (проектирование реакторов для атомных электростанций, проектирование плотин и гидроэлектростанций, магнитогидродинамических преобразователей энергии, и в области экономики – составление сбалансированного плана для отрасли, региона, для страны и др.).

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

Для проверки адекватности математической модели и реального объекта, процесса или системы результаты исследований на ЭВМ сравниваются с результатами эксперимента на опытном натурном образце. Результаты проверки используются для корректировки математической модели или решается вопрос о применимости построенной математической модели к проектированию либо исследованию заданных объектов, процессов или систем.

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

В задачах проектирования или исследования поведения реальных объектов, процессов или систем математические модели, как правило, нелинейны, т.к. они должны отражать реальные физические нелинейные процессы, протекающие в них. При этом параметры (переменные) этих процессов связаны между собой физическими нелинейными законами. Поэтому в задачах проектирования или исследования поведения реальных объектов, процессов или систем чаще всего используются математические модели типа ДНА.

Согласно классификации приведенной в лекции 1:

Д – модель детерминированная, отсутствует (точнее не учитывается) влияние случайных процессов.

Н – модель непрерывная, информация и параметры непрерывны.

А – модель аналитическая, функционирование модели описывается в виде уравнений (линейных, нелинейных, систем уравнений, дифференциальных и интегральных уравнений).

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

Все методы решения математических задач можно разделить на 2 группы:

  1. точные методы решения задач;

  2. численные методы решения задач.

В точных методах решения математических задач ответ удается получить в виде формул.

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





или, например, вычисление производных функций:



или вычисление определенного интеграла:



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

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

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

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



где

x1=a – нижний предел интегрирования;

xn+1=b – верхний предел интегрирования;

n – число отрезков, на которые разбит интервал интегрирования (a,b) ;

– длина элементарного отрезка;

f(xi) – значение подынтегральной функции на концах элементарных отрезков интегрирования.

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

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

Численные методы решения математических задач известны давно, еще до появления ЭВМ, но ими пользовались редко и только в сравнительно простых случаях в силу чрезвычайной трудоемкости вычислений. Широкое применение численных методов стало возможным благодаря ЭВМ.
Компьютерное моделирование при обработке опытных данных.
Любому специалисту в своей практической деятельности приходится изучать зависимости между различными параметрами исследуемых объектов, процессов и систем.

Например: зависимость числа оборотов двигателя от нагрузки, т.е. n=f(Мкр.) ; зависимость силы резания при обработке детали на металлорежущем станке от глубины резания, т.е. P=f(t), и т.д.

Из всех способов задания зависимостей наиболее удобным является аналитический способ задания зависимости в виде функции n=f(Мкр.), P=f(t), y=f(t).

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

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

Далее с этой табличной функцией необходимо вести научно-исследовательские расчеты. Например, необходимо проинтегрировать или продифференцировать табличную функцию и т.д.

Рассмотрим две задачи по обработке опытных данных:

  1. задачу интерполирования,

  2. задачу аппроксимации.

Интерполирование функций


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

i

x

y




0

x0

y0




1

x1

y1




2

x2

y2




 ...

 ...

 ...




i

xi

yi




 ...

 ...

 ...




n

xn

yn






(11.1)

Точки с координатами (xi, yi) называются узловыми точками или узлами.

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

N=n+1.

На графике табличная функция представляется в виде совокупности узловых точек (рис. 11.1).

Рис. 11.1. 

Длина участка [x0, xn] равна (xn - x0).

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

Задача интерполирования функции (или задача интерполяции) состоит в том, чтобы найти значения yk табличной функции в любой промежуточной точке хк, расположенной внутри интервала [x0, xn], т.е.



и



Задача экстраполирования функции (или задача экстраполяции) состоит в том, чтобы найти значения yl табличной функции в точке хl, которая не входит в интервал [x0, xn], т.е.



Такую задачу часто называют задачей прогноза.

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



Для определенности задачи искомую функцию F(x) будем искать из класса алгебраических многочленов:



(11.2)

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



(11.3)

Поэтому степень многочлена n зависит от количества узловых точек N и равна количеству узловых точек минус один, т.е. n=N-1.

Многочлен вида (11.2), который проходит через все узловые точки табличной функции называется интерполяционным многочленом.

Интерполирование с помощью алгебраических многочленов называется параболическим интерполированием.

Таким образом, для решения задачи интерполирования прежде всего необходимо решить задачу, которую можно сформулировать следующим образом:

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



где

n -степень многочлена, равная количеству узловых точек N минус один,т.е. n=N-1.

В результате, в любой другой промежуточной точке хk, расположенной внутри отрезка [x0,xn] выполняется приближенное равенство Pn(xk) = f(xk) = yk. (рис.11.2)

Рис. 11.2. 

Построение интерполяционного многочлена в явном виде


Для построения интерполяционного многочлена вида (11.2) необходимо определить его коэффициенты a0, a1, :, an, т.е. ai i=0,1,2,:,n. Количество неизвестных коэффициентов равно

n+1=N,

где

n-степень многочлена (11.2),

N-количество узловых точек табличной функции (11.1).

Для нахождения коэффициентов, используем свойство (11.3) интерполяционного многочлена (11.2). На основании этого свойства интерполяционный многочлен должен пройти через каждую узловую точку (xi, yi) таблицы (11.1), т.е.,



(11.4)

Подставляя в (11.4) каждую узловую точку таблицы (11.1) получаем систему линейных уравнений:



(11.5)

Неизвестными системы (11.5) являются a0, a1, a2, :, an т.е. коэффициенты многочлена (11.2). Коэффициенты при неизвестных системы (11.5) легко могут быть определены на основании данных таблицы (11.1).

Интерполяция по Лагранжу


Интерполяционный многочлен может быть построен при помощи специальных интерполяционных формул Лагранжа, Ньютона, Стерлинга, Бесселя и др.

Интерполяционный многочлен по формуле Лагранжа имеет вид:



(11.6)

Докажем, что многочлен Лагранжа является интерполяционным многочленом, проходящим через все узловые точки, т.е. в узлах интерполирования xi выполняется условие Ln(xi) = yi. Для этого будем последовательно подставлять значения координат узловых точек таблицы (11.1) в многочлен (11.6). В результате получим:

если x=x0, то Ln(x0) = y0,

если x=x1, то Ln(x1) = y1,

:::::

если x=xn, то Ln(xn) = yn.

Это достигнуто за счет того, что в числителе каждой дроби при соответствующем значении уj, j=0,1,2,:,n отсутствует сомножитель (x-xi), в котором i=j, а знаменатель каждой дроби получен заменой переменной х на соответствующее значение хj.

Таким образом, интерполяционный многочлен Лагранжа приближает заданную табличную функцию, т.е. Ln(xi) = yi и мы можем использовать его в качестве вспомогательной функции для решения задач интерполирования, т.е. .

Чем больше узлов интерполирования на отрезке [x0,xn], тем точнее интерполяционный многочлен приближает заданную табличную функцию (11.1), т.е. тем точнее равенство:



Однако с увеличением числа узлов интерполирования возрастает степень интерполяционного многочлена n и в результате значительно возрастает объем вычислительной работы. Поэтому при большом числе узлов необходимо применять ЭВМ. В этом случае удобно находить значения функции в промежуточных точках, не получая многочлен в явном виде.

При решении задачи экстраполирования функции с помощью интерполяционного многочлена вычисление значения функции за пределами отрезка [x0,xn] обычно производят не далее, чем на один шаг h, равный наименьшей величине



так как за пределами отрезка [x0,xn] погрешности, как правило, увеличиваются.

Программирование формулы Лагранжа


Свернем формулу Лагранжа (11.6). В результате получим



где



но при этом обязательно выполнение условия .

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

Внешним циклом накапливаем сумму .

Внутренним циклом накапливаем произведение .

Алгоритм (рис.11.3) не предусматривает получение интерполяционного многочлена в явном виде, а сразу решает задачу интерполирования функции в заданной точке, x=D.

Обозначения в алгоритме:

n - степень интерполяционного многочлена Лагранжа (11.6), равная количеству узловых точек N минус один, т.е. n=N-1.

D - значение аргумента в точке, для которой решается задача интерполирования табличной функции (11.1).

L - значение многочлена (11.6).

Рис. 11.3.  Схема алгоритма интерполяции по Лагранжу

Интерполяция по Ньютону


Дана табличная функция:

i

xi

yi

0

x0

y0

1

x1

y1

2

x2

y2

 ...

 ...

...

n

xn

yn

или



(11.1)

Точки с координатами (xi, yi) называются узловыми точками или узлами.

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

N=n+1.

Необходимо найти значение этой функции в промежуточной точке, например, x=D, причем .

Для решения задачи строим интерполяционный многочлен.

Интерполяционный многочлен по формуле Ньютона имеет вид:



(11.7)

где

n - степень многочлена,

- разделенные разности 0-го, 1-го, 2-го,:., n-го порядка, соответственно.

Разделенные разности


Значения f(x0), f(x1), : , f(xn), т.е. значения табличной функции в узлах, называются разделенными разностями нулевого порядка (k=0).

Отношение называется разделенной разностью первого порядка (k=1) на участке [x0, x1] и равно разности разделенных разностей нулевого порядка на концах участка [x0, x1], разделенной на длину этого участка.

Для произвольного участка [xi, xi+1] разделенная разность первого порядка (k=1) равна



Отношение называется разделенной разностью второго порядка (k=2) на участке [x0, x2] и равно разности разделенных разностей первого порядка, разделенной на длину участка [x0, x2].

Для произвольного участка [xi, xi+2] разделенная разность второго порядка (k=2) равна



Таким образом, разделенная разность k -го порядка на участке [xi, xi+k] может быть определена через разделенные разности (k-1) -го порядка по рекуррентной формуле:



(11.8)

где





n - степень многочлена.

Максимальное значение k равно n. Тогда i =0 и разделенная разность n -го порядка на участке [x0,xn] равна , т.е. равна разности разделенных разностей (n-1) -го порядка, разделенной на длину участка [x0,xn].

Разделенные разности являются вполне определенными числами, поэтому выражение (11.7) действительно является алгебраическим многочленом n -й степени. При этом в многочлене (11.7) все разделенные разности определены для участков [x0, x0+k], .

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



Докажем это. Пусть х=х0, тогда многочлен (11.7) равен



Пусть х=х1, тогда многочлен (11.7) равен



Пусть х=х2, тогда многочлен (11.7) равен



Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции yi, i=0,1,:n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (11.7). Это удобно на практике и ускоряет процесс вычислений.

Программирование формулы Ньютона


Для построения многочлена Ньютона по формуле (11.7) организуем циклический вычислительный процесс по . При этом на каждом шаге поиска находим разделенные разности k -го порядка. Будем помещать разделенные разности на каждом шаге в массив Y.

Тогда рекуррентная формула (11.8) будет иметь вид:



(11.9)

В формуле Ньютона (11.7) используются разделенные разности k -го порядка, подсчитанные только для участков [x0, x0+k], т.е. разделенные разности k -го порядка для i=0. Обозначим эти разделенные разности k-го порядка как у0. А разделенные разности, подсчитанные для I > 0, используются для расчетов разделенных разностей более высоких порядков.

Используя (11.9), свернем формулу (11.7). В результате получим



(11.10)

где

у0 - значение табличной функции (11.1) для x=x0.

- разделенная разность k-го порядка для участка [x0, x0+k].



Для вычисления Р удобно использовать рекуррентную формулу P = P(x - xk-1) внутри цикла по k.

Схема алгоритма интерполяции по Ньютону представлена на рис.11.4.

Рис. 11.4.  Схема алгоритма интерполяции по Ньютону

Пример интерполяции по Ньютону


Дана табличная функция:

i

xi

yi

0

2

0,693147

1

3

1,098613

2

4

1,386295

3

5

1,609438

Вычислить разделенные разности 1-го, 2-го, 3-го порядков (n=3) и занести их в диагональную таблицу.

Разделенные разности первого порядка:



Разделенные разности второго порядка:



Разделенная разность третьего порядка:



Таблица 11.1. Диагональная таблица разделенных разностей

i

xi

Разделенная разность

0-го пор.

1-го пор.

2-го пор.

3-го пор.

0

2

0,693147

 

 

 

 

 

 

0,405466

 

 

1

3

1,098613

 

-0,058892

 

 

 

 

0,287682

 

0,00887416

2

4

1,386295

 

-0,0322695

 

 

 

 

0,223143

 

 

3

5

1,60943

 

 

 

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



Далее полученный интерполяционный многочлен Ньютона можно привести к нормальному виду



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

Сплайн-интерполяция


Сплайны стали широко использоваться в вычислительной математике сравнительно недавно. В машиностроительном черчении они применяются уже давно, так как сплайны - это лекала или гибкие линейки, деформация которых позволяет провести кривую через заданные точки (xi, уi).

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

Например, для некоторых функций (рис.11.5) необходимо задать все кубические функции q1(x), q2(x), :qn(x).

В наиболее общем случае эти многочлены имеют вид:



где kij - коэффициенты, определяемые описанными ранее условиями, количество которых равно 4n. Для определения коэффициентов kij необходимо построить и решить систему порядка 4n.

Рис. 11.5. 

Первые 2n условий требуют, чтобы сплайны соприкасались в заданных точках:



Следующие (2п-2) условий требуют, чтобы в местах соприкосновения сплайнов были равны первые и вторые производные:



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



При построении алгоритма метода первые и вторые производные удобно аппроксимировать разделенными разностями соответствующих порядков.

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

Аппроксимация опытных данных


В результате проведения натурного эксперимента получена табличная функция:

i

X

Y

0

xo

yo

1

x1

y1

2

x2

y2

3

x3

y3

:

:

:

n

xn

yn

где

N-количество узловых точек в таблице,

n=N-1.

Задача аппроксимации заключается в отыскании аналитической зависимости y=f(x) полученной табличной функции.

В настоящее время существует 2 способа аппроксимации опытных данных:

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



(11.12)

Однако этот способ аппроксимации опытных данных имеет недостатки:

  1. Точность аппроксимации гарантируется в небольшом интервале [x0, xn] при количестве узловых точек не более 7-8.

  2. Значения табличной функции в узловых точках должны быть заданы с большой точностью.

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

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

Второй способ. На практике нашел применение другой способ аппроксимации опытных данных - сглаживание опытных данных. Сущность этого метода состоит в том, что табличные данные аппроксимируют кривой F(x), которая не обязательно должна пройти через все узловые точки, а должна как бы сгладить все случайные помехи табличной функции.

Сглаживание опытных данных методом наименьших квадратов


В этом методе при сглаживании опытных данных аппроксимирующей кривую F(x) стремятся провести так, чтобы ее отклонения от табличных данных (уклонения) по всем узловым точкам были минимальными (рис 11.6), т.е.



(11.6)

Рис. 11.6. 

Избавимся от знака уклонения. Тогда условие (11.6) будет иметь вид:



(11.7)

Суть метода наименьших квадратов заключается в следующем: для табличных данных, полученных в результате эксперимента, отыскать аналитическую зависимость F(x), сумма квадратов уклонений которой от табличных данных по всем узловым точкам была бы минимальной, т.е.



(11.8)

Для определенности задачи искомую функцию F(x) будем выбирать из класса алгебраических многочленов степени m:



(11.9)

Назовем многочлен (11.9) аппроксимирующим многочленом. Аппроксимирующий многочлен не проходит через все узловые точки таблицы. Поэтому его степень m не зависит от числа узловых точек. При этом всегда m < n. Степень m может меняться в пределах .

Если m=1, то мы аппроксимируем табличную функцию прямой линией. Такая задача называется линейной регрессией.

Если m=2, то мы аппроксимируем табличную функцию квадратичной параболой. Такая задача называется квадратичной аппроксимацией.

Если m=3, то мы аппроксимируем табличную функцию кубической параболой. Такая задача называется кубической аппроксимацией.

Уточним метод наименьших квадратов: для табличной функции, полученной в результате эксперимента, построить аппроксимирующий многочлен (11.9) степени m, для которого сумма квадратов уклонений по всем узловым точкам минимальна, т.е.



(11.10)

Изменим вид многочлена Pm. Поставим на последнее место слагаемые, содержащие xm. На предпоследнее - слагаемые, содержащие xm-1 и т.д. В результате получим:



(11.11)

или



При этом изменим индексы коэффициентов многочлена. Тогда условие (11.8) будет иметь вид:



где

xi и yi - координаты узловых точек таблицы,

aj, -неизвестные коэффициенты многочлена (11.11).

Необходимым условием существования минимума функции S является равенство нулю ее частных производных по каждой aj.



В результате получили систему линейных уравнений. Раскрывая скобки и перенося свободные члены в правой части уравнений, получим в нормальной форме систему линейных уравнений:



(11.12)

где

aj - неизвестные системы линейных уравнений (11.12),

- коэффициенты системы линейных уравнений (11.12),

- свободные члены системы линейных уравнений (11.12),

Порядок системы равен m+1.

При ручном счете коэффициенты ck и свободные члены dj удобно определять, пользуясь таблицей 11.2:

Таблица 11.2.

i

xi0

xi1

xi2

...

xi2m

xi0 yi

xi1 yi

...

xim

0

1

 

 

 

 

 

 

 

 

1

1

 

 

 

 

 

 

 

 

2

1

 

 

 

 

 

 

 

 

...

...

 

 

 

 

 

 

 

 

N

1

 

 

 

 

 

 

 

 



c0

c1

c2

...

c2m

d0

d1

...

dm

Программирование метода наименьших квадратов (МНК)


Изменим индексацию в системе (11.12). В результате получим:



(11.13)

где

- неизвестные системы линейных уравнений (11.13),

- коэффициенты системы линейных уравнений (11.13),

- свободные члены системы линейных уравнений (11.13),

(xi, yi) - координаты узловых точек табличной функции, ,

N - количество узловых точек,

m - степень аппроксимирующего многочлена вида:



(11.14)

Алгоритм задачи:


  1. Строим систему линейных уравнений (11.13). Определяем коэффициенты ck,j и свободные члены dk. Т.к. система (11.13) симметрична относительно главной диагонали, то достаточно определить только наддиагональные элементы системы.

  2. Решаем систему (11.13) методом Гаусса. Находим коэффициенты aj многочлена (11.14).

  3. Строим аппроксимирующий многочлен (11.14) и определяем его значение в каждой узловой точке Pi = Pm(xi).

  4. Находим уклонение каждой узловой точки .

  5. Находим сумму квадратов уклонений по всем узловым точкам .

  6. Находим остаточную дисперсию .

Для построения аппроксимирующего многочлена (11.11) и вычисления его значения в каждой узловой точке используем рациональную форму многочлена:



(11.15)

Тогда для вычисления значения многочлена (11.15) удобно пользоваться схемой Горнера. Рекуррентная формула по схеме Горнера имеет вид:



Укрупненная схема алгоритма МНК представлена на рис.11.7. Схемы алгоритмов основных блоков представлены на рисунках 11.8-11.10.

Рис. 11.7.  Укрупненная схема алгоритма аппроксимации методом наименьших квадратов

Обозначения в блоке 2:

m - степень аппроксимирующего многочлена, N - количество узловых точек таблицы (11.2), X, Y - массивы значений x и y таблицы (11.2).

Рис. 11.8.  Схема алгоритма блока 3. Определение коэффициентов системы (11.13)

Рис. 11.9.  Схема алгоритма блока 4. Определение свободных членов системы (11.13)

Рис. 11.10.  Схема алгоритма блока 6. Схема Горнера


Скачать файл (768.5 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации