Построение интерполяционного многочлена и вычисление по нему значения функции для заданного аргумента
Работа из раздела: «
Программирование и комп-ры»
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
Международная «Лига развития науки и образования» (Россия)
Международная ассоциация развития науки, образования и культуры России
(Италия)
Международный «ИНСТИТУТ УПРАВЛЕНИЯ»
(г. Архангельск)
КУРСОВАЯ РАБОТА
ПО ДИСЦИПЛИНЕ
«Информатика и программирование»
Тема : «Построение интерполяционного многочлена и вычисление по нему
значения функции для заданного аргумента»
|Выполнил: студент экономического |
|факультета, группы 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;i<=8;i++
Начало
TableMax()
UX(floatx, float y)
Начало
I=1;
W_f=l_f;
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;
u=(x-(w_f->x))/h;
l_u=w_u;
w_u->u=u;
r_u=w_u;
i=1;i<=3;i++
u1=-(i*i-u*u)/((i*2)*((i*2)+1));
u1=u1*(w_u->u);
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;i<=4;i++
v1=-(i*i-v*v)/((i*2)*((i*2)+1));
v1=v1*(w_v->v);
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
Конец
