Основные методы построения интерполяционных моделей

МОДЕЛИРОВАНИЕ СИСТЕМ

ЛАБОРАТОРНЫЕ РАБОТЫ №№ 1, 2, 3, 4

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ

Для студентов специальности 220201

МОСКВА 2011

Составители: А.В. Алешин

В.В. Болдов

Редактор А.В. Кочемасов

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

Материал предназначен для студентов 4 курса дневного отделения факультета "Кибернетика" специальности 220201 «Управление и информатика в технических системах». Методические указания содержат описание и порядок выполнения лабораторных работ, в которых изучаются методы построения и использования математических моделей при анализе и проектировании технических систем.

Печатаются по решению редакционно-издательского совета Московского государственного института радиотехники, электроники и автоматики (технического университета).

Рецензенты: М.Х. Дорри,

Лабораторная работа №1

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

Цель работы

Цель предлагаемой лабораторной работы — показать главные идеи в области вычислений и изучить методы интерполяции для построения математических моделей устройств автоматических систем. Первые работы для решения задачи моделирования обычно связаны с вычислением значений функции. Главными инструментами здесь являются «общее чутье» и «маленькие хитрости».

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

Основные методы построения интерполяционных моделей

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

Например, в способе Ньютона для нахождения нуля функции y=f(x) дается приближенное значение х₁ и вместо кривой используется прямая

которая касается графика функции в точке (x ₁ у ₁ ). Подставляя

у = 0, получаем значение х, являющееся корнем этой новой функции,

Это новое значение х ₁ используется как следующее приближенное значение корня.

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

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

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

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

Какие узлы будут использованы?

Какой класс приближающих функций будет использован?

Какой критерий согласия будет применен?

Какую точность нужно получить?

2.1 Интерполяция многочленами с произвольно

расположенными узлами

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

Интерполяционные многочлены

Многочлен степени n,

(1.1)

имеет n +1 коэффициент. Естественно полагать, что n +1 условие, наложенное на многочлен в общем виде, позволит однозначно определить коэффициенты. В частности, можно потребовать, чтобы многочлен проходил через n +1 точку (x_i _, y_i) (i= 1,2, …, n +1) с x_i _,≠ x_j. То, что многочлен проходит через точки (x_i _, y_i) означает выполнение условий

(1.2)

Определитель для этих n +1 линейных уравнений относительно неизвестных а_к есть определитель Вандермонда, который не равен нулю, если x_i _,≠ x_j для i ≠ j

(1.3)

Возвращаясь к главной задаче о нахождении многочлена по n +1 точке (x_i, y_i) очевидно, что ее всегда можно решить и найти коэффициенты а_к по правилу Крамера или другим способом.

Все изложенное можно подытожить, сказав, что если есть n + 1 узловая точка функции, то можно найти многочлен степени п, который совпадает (пренебрегая ошибками округления) с функцией в узловых точках. Предположив, что они близки, можно использовать многочлен вместо функции в дальнейших аналитических процессах: интегрировании, дифференцировании, отыскании нулей и т. д.

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

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

(1.4)

(где i ≠ j у знака произведения означает «исключая j значение») является требуемым многочленом степени п; он равен 1, если x=x_j и 0, когда x=x_i, i ≠ j.

Многочлен принимает значение y_i в i -й узловой точке и

равен нулю во всех других узлах. Из этого следует, что

(1.5)

есть многочлен степени п, проходящий через п + 1 точку

(x_i, y_i). Таким образом, можно сделать следующее важное замечание: если дана п + 1 узловая точка, то соответствующий многочлен степени п, проходящий через эти точки, однозначно (в пределах ошибок округления) определен, независимо от того, как он строится и какие обозначения использованы.

2.2 Интерполяция многочленами с равноотстоящими

узлами. Конечные разности

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

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

Такое предположение обычно имеет место при интерполировании функций, заданных в виде таблиц с постоянным шагом, где x₁ = x₀+h, x₂=x₀+2h, x_m= x₀+mh. Разность h арифметической прогрессии и называется шагом таблицы. Построение интерполяционных формул в этом случае значительно упрощается. Прежде чем перейти к рассмотрению этого вопроса, вводится понятие конечных разностей.

Пусть значения функции f(x) заданы в точках х₀, х₁ = х₀ + h,..., х_п = х₀ + nh (узлы интерполяции).

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

y₁ ─ y₀ =

y₂ ─ y₁ = (1.6)

……………..

Y_n ─ y_n-1 =

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

Δ^ky_m = Δ^k^-1y_m_-1─ Δ^k^-1y_m (1.7)

Эти последовательные разности обычно располагают в форме таблицы

x_i	y_i	Δ¹y_m	Δ²y_m	Δ³y_m	Δ⁴y_m	Δ⁵y_m
x₀	y₀	Δ¹y₀
х₁	y₁	Δ¹y₁	Δ²y₀
x₂	y₂	Δ¹y₂	Δ²y₁	Δ³y₀
x₃	y₃	Δ¹y₃	Δ²y₂	Δ³y₁	Δ⁴y₀
x₄	y₄	Δ¹y₄	Δ²y₃	Δ³y₂	Δ⁴y₁	Δ⁵y₀

Пусть значения функции y=f(x ) заданы для равноотстоящих значений аргумента x₀, x₁=x₀ + h, x₂ = x₀ +2 h,…, x_n=x₀ + nh. Значения y обозначаются соответственно y₀ = f(x₀), y₁ = f(x₁), …, y_n=f(x_n). Существует единственный многочлен F (х) степени п, такой, что F (x_k)=y_k (k = 0, 1 ,…, п ). Предлагается другой способ записи и отыскания этого многочлена, который, в конечном счете, совпадает с многочленом, полученным по формуле Лагранжа. Записывается искомый многочлен в виде

(1.8)

Для определения коэффициентов а₀,а₁,...,а_п пологаем
х=x_о. Тогда Далее, полагая х=х₁, получаем

Так как (x₁ ̣─ x₀)= h то откуда

Продолжая вычисление коэффициентов, полагается
х=х₂. Тогда

Заменяя найденные коэффициенты а₀, а₁ их значениями

Воспользовавшись формулой, выражающей разности через значения функции, получается

Точно так же определяется

Аналогичные дальнейшие вычисления позволяют записать общую формулу для отыскания коэффициентов

(1.9)

Подставив найденные выражения коэффициентов в
формулу 1.8, находится

(1.10)

Полученную формулу и называют первой интерполяцион-
ной формулой Ньютона.

Теперь ясно видно различие между формулами Ньютона и Лагранжа. В формуле Лагранжа (4.13) каждое из слагаемых представляет многочлен п-й степени и все эти слагаемые равноправны. Поэтому заранее нельзя (т. е. до производства вычислений) пренебрегать какими-либо из них. В формулу же Ньютона входят в качестве слагаемых многочлены повышающихся степеней, причем коэффициентами при них служат последовательные конечные разности, деленные на факториалы. Очевидно, последовательные разности обычно довольно быстро уменьшаются. Это положение дает возможность не учитывать в формуле Ньютона тех слагаемых, коэффициенты при которых становятся пренебрежимо малыми. Благодаря этому можно вычислять промежуточные значения функции достаточно точно, пользуясь простыми интерполяционными формулами.

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

или x=x₀+ th (1.11)

Множители, входящие в формулу (2.16), выразятся через t следующим образом

……………………………………………..

Подстановка этих выражений в формулу (1.10), приводит ее квиду

(1.12)

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

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

Для интерполирования в конце таблицы применяется иная формула. Искомый интерполяционный многочлен представляется в форме

(1.13)

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

(1.14)

После подстановки в (1.13) полученных значений коэффициентов формула примет вид

(1.15)

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

Используя замену или x = x_n + th

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

(1.16)

Формулу (7.16) называют второй интерполяционной формулой Ньютона или интерполяционной формулой Ньютона для интерполирования назад.