Построение интерполяционного многочлена и вычисление по нему значения функции для заданного аргумента

Построение интерполяционного многочлена и вычисление по нему значения функции для заданного аргумента

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Международная «Лига развития науки и образования» (Россия)

Международная ассоциация развития науки, образования и культуры России

(Италия)

Международный «ИНСТИТУТ УПРАВЛЕНИЯ»

(г. Архангельск)

КУРСОВАЯ РАБОТА

ПО ДИСЦИПЛИНЕ

«Информатика и программирование»

Тема : «Построение интерполяционного многочлена и вычисление по нему

значения функции для заданного аргумента»

|Выполнил: студент экономического |

|факультета, группы 12-И Воробьев |

|А.А. |

|Проверил: Горяшин Ю.В. |

| |

Архангельск

2004

Аннотация

Цель курсовой: для функции заданной в таблице построить интерполяционный

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

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

высокого уровня (С++) для вычисления заданного интерполяционного

многочлена. В программе предусмотреть возможности ввода любого числа

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

линейного списка.

Содержание

1. Аннотация

2. Содержание

3. Глава №1

4. Глава №2

5. Заключение

6. Список литературы

7. Приложение

8. Программа

Введение.

Возможность постановки вычислительного эксперимента на ЭВМ приводит к

существенному ускорению процессов математизации науки и техники, к

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

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

деятельности, что приводит к расширению круга профессий, для которых

математическая грамотность становится необходимой. Однако, развитие науки и

техники, современная технология производства ставят перед специалистами

задачи, для которых либо не возможно, либо крайне громоздко и сложно

получение алгоритма классическими методами математического анализа. Отсюда

стремление использовать различные численные методы, разрабатываемые

вычислительной математикой и позволяющие получить конечный числовой

результат с приемлемой для практических целей точностью.

Численный метод решения задачи - это определенная последовательность

операций над числами, т.е. вычислительный алгоритм, языком которого

являются числа и арифметические действия. Такая примитивность языка

позволяет реализовать численные методы на ЭВМ, что делает их мощными и

универсальными инструментами исследования. Численные методы используются в

тех случаях, когда не удается найти точное решение возникающей

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

решение обычно не выражается в привычных для нас элементах или других

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

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

случаях основным инструментом решения многих математических задач выступают

численные методы, позволяющие свести решение задачи к выполнению конечного

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

также в виде числовых значений.

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

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

слишком сложных задач, и только с появлением высоко производительных ЭВМ

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

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

мощное математическое средство решения практических задач в различных

областях науки и техники.

Интерполирование, интерполяция,- приближенное или точное нахождение

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

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

или приближенное) по известным ее значениям или значениям ее производных в

заданных отрезках.

Основное применение интерполяции - это вычисление значении

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

поэтому интерполяцию часто называют «искусством чтения таблиц между

строками». (П.Ф. Фильчаков)

Глава 1

Основные направления исследования: разрешимость задачи

интерполирования, простейших интерполяционных формул, применение

интерполяции для построения приближенных интерполяционных формул,

применение интерполяции для построения приближенных и численных методов

решения различных задач математики и ее приложений.

Приближенное представление функций. Интерпояционные функции [pic] на

отрезке [pic] по значениям ее в узлах [pic] сетка [pic]- означает постоение

другой функции [pic] такой, что [pic] В более общей постановке задача

интерполирования функции [pic] состоит в постоении [pic] не только из

условий совпадения значений функций [pic] и [pic] на стеке [pic], но и

совпадения в отдельных узлах производных до какого-то порядка или некоторых

других соотношений, связанных [pic] и [pic].

Обычно [pic] стоится в виде

[pic],

где [pic]- некоторая заранее выбранная система линейно независимых функций.

Такое интерполирование называется л и н е й н ы м относительно системы

[pic], а [pic] интерполяционным многочленом по системе [pic].

Выбор системы [pic] определяется свойством класса функций, для

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

для приближения [pic]- периодической функции на [pic] за [pic]

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

полу оси [pic] ограниченных или возрастающих функции- систему рациональных

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

бесконечности и т.д.

Чаще всего используя а л г е б р а и ч е с к о е интерполирование:

[pic]. Существует ряд явных представлений алгебраических интерполяционных

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

[pic]

В задаче приближения функции и на всём отрезке [pic] алгебраическое

интерполирование высокого порядка выполняется сравнительно редко.

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

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

интерполированием по узлам [pic] и [pic] на каждом отрезке [pic] или

квадратичным по трем узлам [pic],[pic],[pic] на отрезке [pic].

Эффективным аппаратом приближения функции являются интерполяционные

сплайны, но их построение в ряде частных случаях требует значительных

вычислительных затрат.

На практике чаще всего используются параболические или кубические

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

функции [pic] относительно сетки [pic] называет функцию [pic], являющуюся

многочленом 3-й степени на каждом из отрезков [pic], принадлежащую классу

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

[pic].

При таком определении кубического сплайна, он имеет еще свободных

параметра, для нахождения которых на сплайн налагаются дополнительные

краевые условия. Например [pic] или [pic] и [pic], или некоторые другие.

Полиномиальный интерполяционный сплайн произвольной степени m

дефекта r определяется как функция [pic], удовлетворяющая, кроме условий

[pic] и [pic], еще дополнительно условиям совпадения в узлах сетки значений

функции [pic] и интерполированной функции [pic] и их производных до

некоторого порядка.

Часто при обработке эмпирических данных [pic] коэффициенты [pic] в

[pic] определяют исходя из требования минимизации суммы

[pic]

[pic]- заданные числа, [pic].

Такое построение функции называют интерполированием по методу

наименьших квадратов.

Интерполирование функций многих переменных имеет ряд принципиальных

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

интерполяционный многочлен Лагранжа фиксированной степени, вообще говоря,

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

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

степени не выше n может быть построен по узлам [pic] лишь при условии, что

эти узлы не лежат на алгебраической кривой порядка n.

Другой поход к интерполированию функции многих переменных [pic] стоит

в том, что сначала интерполируется функция по переменной [pic] при

фиксированных [pic] потом по следующей переменной при фиксированных [pic] и

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

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

случаем.

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

используется:

1. для замены сложно вычисляемой функции другой, вычисляемой проще

2. для приближенного восстановления функции на всей области задания по

значениям её в отдельных точках или по другим известным величинам

3. для получения сглаживающих функций

4. для приближенного нахождения предельных значений функции

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

вопросах.

Общие идеи построения интерполяционных методов решения уравнения

[pic]=0 и систем уравнения [pic], одни и те же. Трудности задачи

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

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

числа уравнений. В основу получении интерполяционных методов решения

уравнения [pic]=0 положена замена функции [pic] ее интерполяционным

многочленом [pic] и последующим решением уравнения [pic]=0 берутся за

приближенные решении уравнения [pic]=0 интерполяционный многочлен [pic]

используется так же при построении итерационных методов решения уравнения

[pic]=0.

Например взяв за [pic] корень линейного интерполяционного

алгебраического многочлена, построенного по значениям [pic] и [pic] в узле

[pic] или по значениям [pic] и [pic] в узлах [pic] и [pic], приходят

соответственно к методу Ньютона и метода секущих

[pic],

где [pic]- разделенная разность функций для узлов [pic] и [pic].

Другой подход к построению численных методов решения уравнения

[pic]=0 основан на интерполировании обратной функции [pic]. Пусть в

качестве интерполяционной формулы для функции [pic] взят интерполяционный

алгебраический многочлен Лагранжа [pic], построенный по узлам [pic] Тогда

за следующее приближению к корню [pic] уравнения [pic]=0 берется величина

[pic].

Численное интегрирование. Аппарат интерполирования функции лежит в

основе построения многих квадратурных и кубатурных формул. Такого рода

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

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

последующим интегрированием этих многочленов. Например квадратурные формулы

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

формулы Гаусса:

[pic]

где [pic]- знакопостоянная весовая функция, получаемая в результате замены

функции [pic] интерполяционным алгебраическим многочленом, построенным по

корням [pic] ортогонального относительно веса [pic] многочлена степени n.

Изложенная выше схема построения формул для приближенного вычисления

интегралов применима и в многомерном случае

Формулы численного дифференцирования, в основе которых лежит

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

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

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

узлах шаг интерполирования должен согласоваться с погрешносьтью значений

функций. Поэтому на практике нередки случаи, когда известная на густой

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

редкой сетке.

При численном решении интегральных уравнений, известная функция [pic]

заменяется в интегральном уравнении каким-либо интерполяционным

приближением (интерполяционным алгебраическим многочленом, интерполяционным

сплайном и т.д.) с узлами интерполирования [pic], а приближенные значения

[pic] для [pic] находятся из системы, полученной после подстановке вместо

независимости переменной x узлов интерполирования [pic]. В случае

нелинейных интегральных уравнений приближенные значения [pic] находятся

соответственно из нелинейной системы.

Интерполяционная формула- для приближенного вычисления значений

функции [pic], основанного вычисления на замене приближаемой функции [pic]

более простой в каком- то смысле функцией

[pic]

|[pic] |[pic] |

наперед заданного класса, причем параметры [pic] выбираются так чтобы

значения [pic] совпадали с известными заранее значениями [pic] для данного

множества [pic]попаро различных значений аргумента:

такой способ приближенного представления функций называется

интерполированием, а точки [pic], для которых должны выполняться условия

[pic], - узлами интерполяции.

В ряде случаев (например, при интерполировании алгебраическими

многочленами) параметры [pic] могут быть явно выражены из системы [pic], и

тогда [pic]непосредственно используется для приближенного вычисления

значений функции [pic].

Интерполяционный процесс- процесс получения последовательности

интерполирующих функций [pic] при неограниченном возрастании числа n узлов

интерполирования. Если интерполирующие функции [pic] представлены в виде

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

называется интерполяционным рядом. Целью построения интерполяционного

полинома чаще всего является, по крайней мере в простейших первоначальных

задачах интерполирования, приближение в каком- то смысле по средствам

интерполирующих функций [pic], о которой или имеется неполная информация,

или форма которой слишком сложна для непосредственного использования.

Интерполяционная формула Эверетта:

Интерполяционные формулы Грегори- Ньютона построенные по нисходящим или

восходящим разностям, наиболее целесообразно применять в начале или конце

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

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

значений функции [pic] или [pic]. Поэтому на средних участках таблицы лучше

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

разностей, то есть разностей, которые ближе всего расположены к центральной

сотке, содержащей [pic].

К интерполяционным формулам с центральными разностями относятся

формулы Гаусса, Стирлинга, Бесселя, Эверетта и многие другие; формула

Эверетта получила наибольшее распространение, она была получена 1900 г.:

[pic]

где [pic]; [pic]; [pic].

Формуле Эверетта так же можно придать форму, наиболее удобную для

вычисления:

[pic]

если для ее коэффициентов ввести обозначения

[pic] [pic] [pic] [pic]

[pic] [pic] [pic]

Коэффициенты [pic] удобнее всего вычислять по следующей рекуррентной

формуле, которая непосредственно вытекает из [pic]:

[pic]; [pic]; [pic]

Таблица разностей:

|x |y |[pic|[pic]|[pic]|[pic]|[pic]|

| | |] | | | | |

|[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]|

|c] |c] |] | | | | |

|[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]|

|c] |c] |] | | | | |

|[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]|

|c] |c] |] | | | | |

|[pi|[pi|[pic|[pic]|[pic]|[pic]|[pic]|

|c] |c] |] | | | | |

|[pi|[pi|[pic|[pic]|[pic]|[pic]| |

|c] |c] |] | | | | |

|[pi|[pi|[pic|[pic]|[pic]| | |

|c] |c] |] | | | | |

|[pi|[pi|[pic|[pic]| | | |

|c] |c] |] | | | | |

|[pi|[pi|[pic| | | | |

|c] |c] |] | | | | |

|[pi|[pi| | | | | |

|c] |c] | | | | | |

Таблицу можно продолжать строить, в нашем случае до последнего [pic], число

разностей зависит от количества значений y. Таблица разностей высчитывается

[pic], и так далее(можно заметить такую систему в приведенной выше

таблице)

Тестовый пример.

П р и м е р. Функция [pic] задана таблицей на сегменте [pic].

Определим при помощи интерполяции значение [pic].

Р е ш е н и е. По данным значениям функции составляем таблицу

разностей (табл. 1), из которых видно, что четвертые разности в данном

примере практически равны постоянны, а пятые разности практически равны

нулю, и поэтому мы их в дальнейших вычислениях не будем принимать во

внимание.

Принимаем [pic]=0,85; [pic]=0,9; [pic]=0,874.

Тогда [pic]=0,8273695; [pic]=0,8075238, и, далее, так как шаг таблицы

[pic]=0,05, то

[pic]

Т а б л и ц а 2

|x |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |

|0.6|0.9120049|-0.014873|-0.001057|0.000029|0.000002|-0.000000|

|0 | |3 |4 |5 |1 |4 |

|0.6|0.8971316|-0.015930|-0.001027|0.000031|0.000001|0.0000002|

|5 | |7 |9 |6 |7 | |

|0.7|0.8812009|-0.016958|-0.000996|0.000033|0.000001|-0.000000|

|0 | |6 |3 |3 |9 |5 |

|0.7|0.8642423|-0.017954|-0.000963|0.000035|0.000001|0.0000001|

|5 | |9 |0 |2 |4 | |

|0.8|0.8462874|-0.018917|-0.000927|0.000036|0.000001| |

|0 | |9 |8 |8 |5 |[pic] |

|0.8|0.8273695|-0.019845|-0.000891|0.000038| | |

|5 | |7 |0 |3 | | |

|0.9|0.8075238|-0.020736|-0.000852| | | |

|0 | |7 |7 | | | |

|0.9|0.7867871|-0.021589| | | | |

|5 | |4 | | | | |

|1.0|0.7651977| | | | | |

|0 | | | | | | |

Т а б л и ц а 2

|Эверетта |

|[p|[pic] |[pic] |

|ic| | |

|] | | |

|0 |0.52000|0.8227369|

|1 | |5 |

|2 |-0.0632|-0.000927|

| |3 |8 |

| |0.01179|0.0000014|

|0 |0.48000|0.8075238|

|1 | | |

|2 |-0.0615|-0.000891|

| |7 |0 |

| |0.01160|0.0000015|

|[pic][pic] |

Все вычисления по формуле Эверетта представлены в табл. 2.

Все необходимые значения разностей(и самой функции, которые мы в

табл. 2 обозначили как разности нулевого порядка [pic]) взяты из табл. 1.

Первые три строки в табл. 2 заполнены значениями [pic] для [pic] и [pic], а

последующие три строки соответственно значениями [pic] для [pic] и [pic].

Перемножив (не снимая промежуточных результатов) коэффициенты [pic] на

расположенные в той же строке [pic], мы и получим искомое значение функции

[pic], как сумму произведений

Проверка производится непосредственно при помощи степенного ряда для

рассматриваемой функции Эверетта [pic] согласно которому получим [pic]

ГЛАВА №2

MAIN[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

[pic]

Заключение

Удалось построить интерполяционный многочлен и вычислить по нему

значение функции для заданного значения аргумента. Составлена блок схема

алгоритма и программа на языке С++ (Приложение) для вычисления заданного

интерполяционного многочлена. В программе предусмотрена возможность ввода

любого числа значений функции для чего организованно хранение ее значения

при помощи линейного списка.

Список литературы

1. Архангельский Н.А. Вычислительные методы алгебры в приемах и

задачах. М.: МАИ, 1976.

2. Васильев Ф.П. Численные методы решения экстремальных задачь. М.:

Наука,1988.

3. Васильков Ф.В., Василькова Н.Н. Компьютерные технологии

вычислений в математическом моделировании: Учеб. Пособие. М.:

Финансы и статистика, 1999.

4. Фильчаков П.Ф., Справочник по высшей математике. Киев: Наукова

думка, 1974.

5. Фильчаков П.Ф., Численные методы. Киев: Наукова думка, 1976.

6. Большая математическая энциклопедия. М.: Олма-Пресс, 2004

7. Демидович Б.П., Марон И.А. Основы вычислительной математики. М.:

Наука, 1970.

8. Тихонов А.Н., Вводные лекции по прикладной математике. М.:

Наука, 1984.

9. Калиткин Н.Н., Численные методы. М.: Наука, 1987.

10. Корн Г., Корн Т. Справочник по математике. М.: Наука, 1984.

-----------------------

Начало

l_msp=NULL;l_fll=NULL;l_f=NULL;

w_u=NULL;r_u=NULL;l_u=NULL;

w_v=NULL;r_v=NULL;l_v=NULL;

h=FileFunction();

w_f=l_f;

TableMin();

TableMax();

BBEDuTE X=

x

u=UX(x,h);

VX(u);

p=Summa();

«OTBET: »

p

Конец

Начало

!feof(in)

l_f==NULL

l_w=w_f

R_f->radr=w_f

Нет

да

fscanf(in,"%f",&w_f->x); fscanf(in,"%f",&w_f->y);

R_f=w_f;

W_f=l_f;

W_f=l_f->radr;

H=(w_f->x)-(l_f->x)

FileFunction()

TableMin

Начало

s=w_f->y;

w_f=w_f->radr;

s1=w_f->y;

p=s1-s;

L_msp==NULL

L_msp=w_msp;

R_msp->radr1=w_msp

да

нет

l_fll==NULL

R_msp->radr1=w_msp

L_msp=w_msp;

да

нет

w_fll->a=p;r_fll=w_fll;

w_msp->z=p;r_msp=w_msp;

w_f!=r_f

нет

w_msp=l_msp;

да

r_msp=w_msp;

w_msp=l_msp;

w_msp!=r_msp

w_msp->z=p;

w_msp->z=p;l_msp=w_msp;

L_msp==NULL

s=c;

w_msp=w_msp->radr1;

c=w_msp->z;

s1=w_msp->z;

p=s1-s;

r_fll->radr2=w_fll;

w_fll->a=p;r_fll=w_fll;

r_msp->radr1=w_msp;

c=w_msp->z;

l_msp=NULL;

i=1;iradr;i++;

I=(i/2)

w_f=l_f;i>=1;i--

w_f=w_f->radr;

u=(x-(w_f->x))/h;

l_u=w_u;

w_u->u=u;

r_u=w_u;

i=1;iu);

r_u->uadr=w_u;

w_u->u=u1;

r_u=w_u;

Конец

VX(float u)

Начало

v=1-u;

l_v=w_v;

r_v->vadr=w_v;

w_v->v=v;

r_v=w_v;

i=1;iv);

r_v->vadr=w_v;

w_v->v=v1;

r_v=w_v;

Конец

Summa()

Начало

i=1;

w_f=l_f;

w_fll=l_fll;

w_u=l_u;

w_v=l_v;

w_f!=r_f

w_f=w_f->radr;i++;

I=i/2

w_f=l_f;i>=1;i--

w_f=w_f->radr;

s=(w_f->y)*(w_v->v);

w_f=w_f->radr;

s1=(w_f->y)*(w_u->u);

w_f=l_f;

w_f!=r_f

w_f=w_f->radr;i++;

i++;

j=i;

;i>=1;i--

w_fll=w_fll->radr2;

i=j;

i=((i/2)-1);i>=1;i--

w_fll=w_fll->radr2;

w_v=w_v->vadr;

s=s+(w_fll->a)*(w_v->v);

i=j;

i=((i/2));i>=1;i--

w_fll=w_fll->radr2;

w_fll!=r_fll

i==0

j--;

i=j;

j=i-1;

i=j;

w_fll=l_fll;

w_f=l_f;

Конец

p=s1+s;

w_u!=r_u

i=j*2;

w_fll=w_fll->radr2;

i=((i/2));i>=1;i--,j++

w_u=w_u->uadr;

s1=s1+(w_fll->a)*(w_u->u);

i=j-1;

j=0;

i=i-1;

i=j-1;

w_fll=w_fll->radr2;

;i>=1;i--

j=i;

j=i;

w_u=l_u;

w_f=w_f->radr;i++;

w_f!=r_f

Конец