Выбор интерполирующей функции к заданной и ее построение

Министерство науки и образования Украины

Сумской государственный университет

кафедра информатики

 

 

 

 

 

 

 

 

Численные методы

 

Курсовая работа

на тему:

 

“ Выбор интерполирующей функции к заданной и ее построение ”

 

 

 

 

 

 

 

 

 

 

 

Сумы 2006

 

Содержание

 

Постановка задачи.

1. Введение.

2. Теоретическая часть. 

3. Практическая реализация: 

3.1 Программа на языке Pascal.

3.2 Решение в Excel.

4. Выводы. 

Список использованной литературы.

Приложение.

 

 

Постановка задачи

 

Найти значение функции у в точке х=0.47 , используя интерполяционную схему Эйткина, проверить правильность решения с помощью кубического сплайна. Значения функции у приведены в таблице:

 

i	0	1	2	3	4	5
xi	0,4	0,5	0,6	0,7	0,8	0,9
yi	0,38942	0,47943	0,56464	0,64422	0,71736	0,78333
x=	0,47

 

 

Введение

 

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

 

.

 

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

 

 

Теоретическая часть

 

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

 

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

 

 (*)

 

С формулы видно, что степень многочлена равна , и многочлен Логранжа удовлетворяет все условия задачи интерполяции.

Если расстояние между всеми соседними узлами интерполирования одинаково, то есть , формула (*) значительно упрощается. Введем новую переменную , тогда Теперь интерполяционный полином Лагранжа имеет вид:

 

. (**)

Тут .

 

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

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

 

, (***)

где .

 

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

 

Разделенными разностями называются соотношения вида:

- первого порядка:

 

 

- второго порядка:

 (5.15)

…………………………………………………;

- n- го порядка:

 

С помощью разделенных різностей можно построить многочлен:

 

 (5.16)

 

Он называется интерполяционным многочлен Ньютона для заданной функции. Эта форма записи более удобна для использования, поскольку при добавлении к узлам x0, x1, …, xn нового xn+1 все вычесленные раньше члены остаются без изменений, а в формулу добавляется только одно слогаемое. При использовани формулы Логранжа нужно вычислять все заново.

Если значения функции заданы для равноотстоящих значений аргумента (постоянную величину , i=0,1,…,n называют шагом интерполяции), то интерполяционный многочлен принимает вид:

 

 (5.17)

 

Здесь - конечные разности к-го порядка. Они определяются по формуле где -биномиальные коэффициенты.

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

 

 (5.18)

 

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

 

 (5.19)

 

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

 

(5.20)

 

Разделенные разности можно выразить через конечные разности, если воспользоваться возможностью переставлять в них аргументы, и соотношением (5.18), откуда следует:

 

;

 

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

 

. 

 

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

Отметим, что операция екстраполирования, вообще говоря, менее точная чем операция интерполяции.

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

 

Схема Эйткина

 

Пусть дана f задана таблично в точках хi она принимает значения уi= f(хi) (i=0,1,…,n). Требуется вычислить значение функции f в некоторой точке х , не совпадающей с точками хi. В таком случае нет необходимости строить общее выражение многочленна Лагранжа явно, а требуется только вичислить его значение в точке х. Эти вычисления удобно выполнить по интерполяционной схеме Эйткина. Характерной чертой этой схемы является единообразие вичислений.

Если функция f задана в двух точках х0 и х1 значениями у0 и у1, то для вычисления ее значения в точке х можно воспользоваться формулой:

 

(*) линейного интерполирования.

 

Обозначив значение функции в точке x через , формулу (*) можно представить в таком виде:

 

,

 

Где в правой части стоит определитель 2-го порядка. Эта формула эквивалентна формуле (*). Кроме того, , .

Пусть функция f задана в трех точках х0, х1 и х2 своими значениями у0, у1 и у2 и требуется вычислить ее значение в точке х . В этом случае по схеме Эйткина в точке х вычисляют сначала значения двух линейных многочленов

 

 и  ,

 

а затем значение квадратичного многочлена вида:

 

.

 

Непосредственной подстановкой убеждаемся, что ,

 

; , , .

 

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

 

,

 

то, раскрывая определитель, получаем:

 

Эта схема обобщается на более высокие степени. Если функция f задана в четырех точках, то кубическое интерполирование выполняется по формуле

 

,

 

Где и - значения квадратичных многочленов в точке х . Непосредственной проверкой убеждаемся, что и . Кроме того совпадает с кубическим интерполяционным многочленом Лагранжа:

 

.

 

Вообще, если в (n+1)-й точке хi (i=0,1,…,n) функция f принимает значения yi (i=0,1,…,n), то значение интерполяционного многочлена Лагранжа степени n в точке х можно вычислить по формуле

 

,

 

где и - значения интерполяционных многочленов, вычисленных в точке х на предшествующем шаге. Ясно, что для вычисления значения многочлена степени n в точке х необходимо по схеме Эйткина вычислить в этой точке значения n линейных, n-1 квадратичных, n-2 кубических многочленов и т. д., два многочлена степени n-1 и, наконец, один многочлен степени n. Все эти многочлены выражаются через определитель 2-го порядка, что делает вычисления единообразными.

Отметим то, что схема Эйткина применима и в случае неравноотстоящих узлов интерполирования.

 

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

 

В инженерной практике график функции y(xi) (i=0,N) строят в основном с помощью лекал. Если точки размещены редко, то пользуются гибкой линейкой (spline), ставят ее на ребро и изгибают так, чтобы она одновременно проходила через все точки.

Поскольку приближенное уравнение изгиба пружинистого бруса имеет вид , то можно допустить, что ее форма между узлами есть алгебраический полином 3-й степени.

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

 

 (*)

.

 

Неизвестные коэффициенты ai, bi, ci, di найдем с условий в узлах интерполяции.

Поскольку полиномы совпадают с табличными значениями функции y(xi) (i=1,N) в узлах интерполяции, то:

 

 (А)

 (В)

 

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

С условий непрерывности производных у внутренних узлах имеем:

 

 (С)

 (D)

 

Найдем выражения для производных от сплайна S(i)(x):

 

 (Е)

 (F)

 

и подставим их в выражения (С) и (D). Как следствие, имеем 6

 

 (G)

 (H)

 

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

 

 (I)

 (J)

 

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

Уравнения (A), (B), (G)-(J) составляют полную СЛАУ для определения 4N неизвестных коэффициентов. Если эту СЛАУ преобразовать, то ее решение значительно упростится.

Очевидно, . Кроме того, из выражения (J)

 

 (K)

 

а из выражения (H) –

 

 (L)

 

Подставив уравнение (L) в формулу (В) учитывая, что , получим

 

  ; (М)

 (N)

 

Извлекая из (G) bi и bi+1 с помощью (М), а di – на основании (L), придем к такой СЛАУ относительно ci:

 

 (**)

 

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

Вообще-то можно рассмотреть задачу о нахождении сплайна n-й степени:

 

 

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