Задачи интерполирования функции означают что необходимо

системе узлов [math]x_0 \lt x_1 \lt x_2 \lt \ldots \lt x_n[/math] такие, что

Требуемый полином [math]L_n(x)[/math] найден.

Замечание: из формулы для фундаментальных полиномов [math]\Phi_j(x)[/math] легко записать в развёрнутом виде:

Трактовки и другие задачи [ править ]

Теперь другая задача: «Дана функция [math]f[/math] и система узлов. Требуется найти полином [math]L_n[/math] степени не выше [math]n[/math] такой, что [math]\forall x_j: j = \overline<0..n>\quad L_n(x_j) = f(x_j)[/math] »

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

Теорема Лагранжа [ править ]

Тогда для соответственного интерполяционного полинома Лагранжа выполняется равенство

Следствие [ править ]

Замечание [ править ]

Следует понимать, что на самом деле какую бы систему узлов мы не взяли на [math]\langle a; b \rangle[/math] как по числу точек в ней, так и по характеру распределения значений, для этого промежутка всегда можно построить непрерывную функцию, для которой ее интерполяционный многочлен будет отличаться от неё сколь угодно много.

Источник

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

Лекция 8

ОБРАБОТКА ДАННЫХ. ЧИСЛЕННЫЕ МЕТОДЫ ПРИБЛИЖЕНИЯ ФУНКЦИЙ. ИНТЕРПОЛЯЦИЯ

Содержание

· Области применения задачи приближения функций.

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

· Постановка задачи интерполяции.

· Метод неопределенных коэффициентов

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

· Интерполяционный полином Ньютона.

· Погрешность полиномиальной интерполяции.

8.1. Области применения задачи приближения функций

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

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

· функция задана в виде таблицы, и необходимо знать значения функции для промежуточных значений аргументов, расположенных в таблице между узлами x_i, i = 0,…. n, а также для аргументов, расположенных вне таблицы;

· известно лишь табличное представление функции и требуется определить ее аналитическое выражение;

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

можно заменить подынтегральную функцию f(x) некоторой приближенной функцией P(x) в виде многочлена. Тогда

.

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

Разберемся с рядом терминов, используемых в литературе при описании технологии приближения функций. Итак, пусть некоторая функция f(x)определена рядом своих узловых точек (x_i, y_i) на некотором отрезке [a, b]. Под интерполяцией мы будем подразумевать вычисление значений f(x) в любом промежутке [x_i, x_i+1] в пределах отрезка [a, b]. Соответственно, любое вычислениеf(x)вне отрезка [a, b] является экстраполяцией.

Наиболее распространены следующие виды интерполяции:

· линейная интерполяция, при которой промежуточные точки, расположенные между двумя узловыми точками (x_i, y_i) и (x_i+1, y_i+1), лежат на отрезке прямой, соединяющей две ближайшие узловые точки;

· квадратичная интерполяция, при которой промежуточные точки между узловыми точками (x_i, y_i), (x_i+1, y_i+1) и (x_i+2, y_i+2) лежат на отрезке параболы, соединяющей эти узловые точки;

· полиномиальная интерполяция, при которой промежуточные точки вычисляются как значение некоторого многочлена p_n(x), имеющего значения в узловых точках точно совпадающие с f_i(x_i);

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

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

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

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

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

Пусть на отрезке xÎ[a, b] задана функция f(x), с помощью которой построена сеточная функция (табл. 8.1) или задана экспериментальная таблица (табл. 8.1).

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

Определение 2.Процесс вычисления значений функции F(x) в точках отличных от узлов интерполирования называется интерполированием функции f(x). Если xÎ[x₀, x_n], то задача вычисления приближенного значения функции в точке х называется интерполированием, иначе — экстраполированием.

Геометрически задача интерполирования функции одной переменной означает построение кривой, проходящей через заданные точки (x₀, y₀), (x₁, y₁), …, (x_n, y_n) (рис. 8.1).

8.3.1. Метод неопределенных коэффициентов

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

При сглаживании функции (или экспериментальной таблицы) с помощью интерполяции в соответствии с условием интерполяции (8.2) значение интерполирующей функции и значение заданной функции в узлах сетки должны быть одинаковыми, следовательно, погрешность интерполяции в узлах x_i, i = 0,…, n равна нулю (рис. 8.1).

Рис. 8.1. Иллюстрация процедуры интерполяции

В общем случае задача интерполяции имеет не единственное решение, но в случае использования в качестве интерполирующей функции многочлена n-й степени (требующий n+1 узел интерполяции) задача интерполяция табличной функции вида (8.1) имеет единственное решение, т.е. коэффициенты a₀,…, a_n (в количестве n+1) определяются единственным образом.

Действительно, используя табл. 8.1, можно составить систему из n+1 линейных уравнений (СЛАУ) относительно неизвестных коэффициентов a₀,…, a_n:

(8.6)

Матрица коэффициентов этой СЛАУ (8.6) носит специальное название — матрицы Вандермонда. Ее определитель не равен нулю, поскольку все значения узлов интерполяции различны между собой и ни одна из строк не является линейной комбинацией других строк, т.е.

(8.7)

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

Дата добавления: 2016-04-22 ; просмотров: 5089 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ

Источник

Электронная библиотека

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

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

В связи с интерполяцией рассматриваются три основные проблемы.

1) выбор интерполяционной функции L(x);

2) оценка погрешности интерполяции R(x);

3) размещение узлов интерполяции для обеспечения наивысшей возможной точности восстановления функции (x₁, x₂,…,x_n).

Специальные методы интерполяции позволяют определить искомое значение функции без непосредственного прямого построения интерполяционной функции. В принципе все интерполяционные методы, базирующиеся на использовании в качестве интерполяционной функции полиномов, дают одни и те же результаты, но с разными затратами. Это объясняется тем, что полином n-й степени, содержащий n+1 параметр и проходящий через все заданные n+1 точки, — единственный. Кроме того, полином можно представить как усеченный ряд Тейлора, в который разложили исходную дифференцируемую функцию. Это, пожалуй, одно из главных достоинств полинома как интерполяционной функции. Поэтому чаще первая проблема интерполяции решается выбором в качестве интерполяционной функции именно полинома, хотя могут применяться и другие функции (например, тригонометрические полиномы, другие функции, выбранные из неформальных условий содержательной задачи).

Рис. 3.2 Иллюстрация интерполяции

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

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

Простейшим и часто используемым видом локальной интерполяции является линейная интерполяция. Она состоит в том, что заданные точки М(x_i, y_i) (i = 0, 1, …, n) соединяются прямолинейными отрезками, и функция f(x) приближается к ломаной с вершинами в данных точках (рис. 3.3).

Рис. 3.3 Линейная интерполяция

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

На рисунке 3.4 представлен пример использования линейной интерполяции в программе MathCAD. Для линейной интерполяции используется функция linterp(x,y,z). Здесь x, y – исходные данные, z – точка, в которой находится значение функции.

Рис. 3.4. Линейная интерполяция

В случае квадратичной интерполяции в качестве интерполяционной функции на отрезке (x_{i — 1},x_{i + 1}) принимается квадратный трехчлен. Уравнения квадратного трехчлена имеет вид

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

Интерполяция для любой точки x [x₀, x_n] проводится по трем ближайшим точкам.

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

Рассмотренные выше методы локальной интерполяции, по существу, является простейшим сплайном первой степени (для линейной интерполяции) и второй степени (для квадратичной интерполяции).

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

В общем случае для функции y = f(x) требуется найти приближение y= j(x) таким образом, чтобы f(x_i) = j(x_i) в точках x = x_i, a в остальных точках отрезка [a, b] значения

функций f(x) и j(x) были близкими между собой. При малом числе экспериментальных точек (например, 6-8) для решения задачи интерполяции можно использовать один из методов построения интерполяционных полиномов. Однако при большом числе узлов интерполяционные полиномы становятся практически непригодными. Это связано с тем, что степень интерполяционного полинома лишь на единицу меньше числа экспериментальных значений функций. Можно, конечно, отрезок, на котором определена функция, разбить на участки, содержащие малое число экспериментальных точек, и для каждого из них построить интерполяционные полиномы. Однако в этом случае аппроксимирующая функция будет иметь точки, где производная не является непрерывной, т. е. график функции будет содержать точки “излома”.

Кубические сплайны лишены этого недостатка. Исследования теории балок показали, что гибкая тонкая балка между двумя узлами достаточно хорошо описывается кубическим полиномом, и поскольку она не разрушается, то аппроксимирующая функция должна быть, по меньшей мере, непрерывно дифференцируемой. Это означает, что функции j(x), j’(x), j»(x) должны быть непрерывными на отрезке [a, b].

Кубическим интерполяционным сплайном, соответствующим данной функции f(x) и данным узлам x_i, называется функция y(x), удовлетворяющая следующим условиям:

функция y(x), а также ее первая и вторая производные непрерывны на отрезке [a,b],

Кубический сплайн склеивается из полиномов третьей степени, которые для i-го участка записываются так:

Для всего интервала будет соответственно п кубических полиномов, отличающихся коэффициентами а_i, b_i, c_i, d_i. Чаще всего узлы при сплайновой интерполяции располагают равномерно, т.е. х_i+1 -х_i =const = h (хотя это и необязательно).

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

Первое условие соответствует прохождению полинома через начальную точку, второе — через конечную точку. Найти все коэффициенты из этих уравнений нельзя, так как условий меньше, чем искомых параметров. Поэтому указанные условия дополняют условиями гладкости функции (т.е. непрерывности первой производной) и гладкости первой производной (т.е. непрерывности второй производной) в узлах интерполяции. Математически эти условия записываются как равенства соответственно первой и второй производных в конце i-го и в начале (i+1)-го участков.

Получилась система линейных уравнений (для всех участков), содержащая 4n — 2 уравнения с 4n неизвестными (неизвестные a₁, a₂,…, a_n, b₁,…, d_n — коэффициенты сплайнов). Для решения системы добавляют два граничных условия одного из следующих видов (чаще применяют 1):

Совместное решение 4n уравнений позволяет найти все 4n коэффициента.

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

Решим задачу об интерполяции с помощью программы MathCAD. Для этого воспользуемся встроенной функцией interp(VS,x,y,z). Переменные x и y задают координаты узловых точек, z является аргументом функции, VS определяет тип

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

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

pspline(VX, VY) возвращает вектор VS вторых производных при приближении к опорным точкам к параболической кривой;

lspline(VX, VY) возвращает вектор VS вторых производных при приближении к опорным точкам прямой;

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

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

Рис. 3.5 Кубическая сплайн интерполяция

Если функция задана дискретно, то для интерполяции задаются матрицы данных.

При глобальной интерполяции наиболее часто используется интерполяция полиномом n-ой степени или интерполяция Лагранжа.

Классический подход основывается на требовании строгого совпадения значений f(х) и j(х) в точках х_i (i = 0, 1, 2, … n).

Будем искать интерполяционную функцию j(х) в виде полинома степени n.

Этот полином имеет n + 1 коэффициент. Естественно предположить, что n + 1 условий

наложенные на полином

позволяют однозначно определить его коэффициенты. Действительно, требуя для j(х) выполнение условий (3.4), получаем систему n + 1 уравнений с n + 1 неизвестными:

Решая эту систему относительно неизвестных a₀, a₁, …, a_n мы получим аналитическое выражение полинома (3.5). Система (3.6) всегда имеет единственное решение, т.к. её определитель

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

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

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

Пусть известны значения некоторой функции f(х) в п+1 различных произвольных точках y_i = f(x_i), i = 0,…, п. Для интерполирования (восстановления) функции в какой-либо точке х, принадлежащей отрезку [х₀,х_п], необходимо построить интерполяционный полином n-го порядка, который в методе Лагранжа представляется следующим образом:

Причем нетрудно заметить, что Q_j(x_i) = 0, если i¹j, и Q_j(x_i) =1, если i=j. Если раскрыть произведение всех скобок в числителе (в знаменателе все скобки — числа), то получим полином n-го порядка от х, так как в числителе содержится n сомножителей первого порядка. Следовательно, интерполяционный полином Лагранжа не что иное, как обычный полином n-го порядка, несмотря на специфическую форму записи.

Оценить погрешность интерполяции в точке х из [х₀,х_n] (т.е. решить вторую

проблему интерполяции) можно по формуле

В формуле — максимальное значение (n+1)-й производной исходной функции f(х) на отрезке [х₀,х_n]. Следовательно, для того чтобы оценить погрешность интерполяции, необходима некоторая дополнительная информация об исходной функции (это должно быть понятно, так как через заданные исходные точки может проходить бесчисленное количество различных функций, для которых и погрешность будет разной). Такой информацией является производная n+1 порядка, которую не так просто найти. Ниже будет показано, как выйти из такого положения. Отметим также, что применение формулы погрешности возможно, только если функция дифференцируема n +1 раз.

Для построения интерполяционной формулы Лагранжа в MathCAD удобно использовать функцию if.

Возвращает значение х, если cond отличен от 0 (истина). Возвращает значение у, если cond равен 0 (ложь) (рисунок 3.6).

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Источник

• через какое время делают повторное эко →