Построение интерполяционного многочлена и вычисление по нему значения функции для заданного аргумента
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ
ФЕДЕРАЦИИ
Международная «Лига развития науки и
образования» (Россия)
Международная ассоциация развития
науки, образования и культуры России (Италия)
Международный «ИНСТИТУТ УПРАВЛЕНИЯ»
(г. Архангельск)
КУРСОВАЯ РАБОТА
ПО ДИСЦИПЛИНЕ
«Информатика и программирование»
Тема : «Построение интерполяционного
многочлена и вычисление по нему значения функции для заданного аргумента»
Выполнил:
студент экономического факультета, группы 12-И Воробьев А.А.
Проверил:
Горяшин Ю.В.
|
Архангельск
2004
Аннотация
Цель курсовой: для функции заданной в таблице построить
интерполяционный многочлен и вычислить по нему значение функции для заданного
значения аргумента. Составить блок схему алгоритма и программу на одном из
языков высокого уровня (С++) для вычисления заданного интерполяционного
многочлена. В программе предусмотреть возможности ввода любого числа значений
функции для чего организовать хранение ее значении при помощи линейного списка.
Содержание
1.
Аннотация
2.
Содержание
3.
Глава №1
4.
Глава №2
5.
Заключение
6.
Список
литературы
7.
Приложение
8.
Программа
Введение.
Возможность постановки
вычислительного эксперимента на ЭВМ приводит к существенному ускорению
процессов математизации науки и техники, к постоянному расширению области
приложения современных разделов математики. Количественные методы внедряются
практически во все сферы человеческой деятельности, что приводит к расширению
круга профессий, для которых математическая грамотность становится необходимой.
Однако, развитие науки и техники, современная технология производства ставят
перед специалистами задачи, для которых либо не возможно, либо крайне громоздко
и сложно получение алгоритма классическими методами математического анализа.
Отсюда стремление использовать различные численные методы, разрабатываемые
вычислительной математикой и позволяющие получить конечный числовой результат с
приемлемой для практических целей точностью.
Численный метод решения
задачи - это определенная последовательность операций над числами, т.е.
вычислительный алгоритм, языком которого являются числа и арифметические
действия. Такая примитивность языка позволяет реализовать численные методы на
ЭВМ, что делает их мощными и универсальными инструментами исследования.
Численные методы используются в тех случаях, когда не удается найти точное
решение возникающей математической задачи. Это происходит главным образом,
потому, что искомое решение обычно не выражается в привычных для нас элементах
или других известных функциях. Даже для достаточно простых математических
моделей иногда не удается получить результат решения в аналитической форме. В
таких случаях основным инструментом решения многих математических задач
выступают численные методы, позволяющие свести решение задачи к выполнению
конечного числа арифметических действий над числами, при этом результаты
получаются также в виде числовых значений.
Многие численные методы
разработаны давно, однако при ручных вычислениях они могли использоваться лишь
для решения узкого круга не слишком сложных задач, и только с появлением высоко
производительных ЭВМ начался период бурного развития методов вычислительной
математики и их внедрения в практику. Численные методы приобрели важнейшее
значение как мощное математическое средство решения практических задач в
различных областях науки и техники.
Интерполирование,
интерполяция,- приближенное или точное нахождение какой-либо величины по
известным отдельным значениям или других величин, связанных с ней. В
первоначальном понимании- восстановление функции (точное или приближенное) по
известным ее значениям или значениям ее производных в заданных отрезках.
Основное применение
интерполяции - это вычисление значении табулированной функции для неузловых
(промежуточных) значений аргумента, поэтому интерполяцию часто называют
«искусством чтения таблиц между строками». (П.Ф. Фильчаков)
Глава 1
Основные направления исследования:
разрешимость задачи интерполирования, простейших интерполяционных формул,
применение интерполяции для построения приближенных интерполяционных формул,
применение интерполяции для построения приближенных и численных методов решения
различных задач математики и ее приложений.
Приближенное
представление функций. Интерпояционные функции на
отрезке по значениям ее в узлах сетка -
означает постоение другой функции такой, что В более общей постановке задача интерполирования
функции состоит в постоении не только из условий совпадения значений
функций и на
стеке , но и совпадения в отдельных узлах производных
до какого-то порядка или некоторых других соотношений, связанных и .
Обычно стоится в виде
,
где -
некоторая заранее выбранная система линейно независимых функций. Такое
интерполирование называется л и н е й н ы м относительно системы , а интерполяционным
многочленом по системе .
Выбор системы определяется свойством класса функций,
для приближения которого предназначаются интерполяционные формулы. Например,
для приближения - периодической функции на за естественно
взять тригонометрическую систему функций, для приближения на полу оси ограниченных или возрастающих функции-
систему рациональных или показательных функций, учитывающих поведение
приближаемых функций на бесконечности и т.д.
Чаще всего используя а л г е
б р а и ч е с к о е интерполирование: .
Существует ряд явных представлений алгебраических интерполяционных многочленов.
Например интерполяционный многочлен Лагранжа имеет вид:
В задаче приближения функции
и на всём отрезке алгебраическое интерполирование
высокого порядка выполняется сравнительно редко. Алгебраический интерполяционный
процесс не является сходящимся в классе непрерывных на функций.
Обычно ограничиваются линейным интерполированием по узлам и на
каждом отрезке или квадратичным по трем узлам
,, на отрезке .
Эффективным аппаратом
приближения функции являются интерполяционные сплайны, но их построение
в ряде частных случаях требует значительных вычислительных затрат.
На практике чаще всего
используются параболические или кубические полиноминальные сплайны. Интерполяция
кубическим сплайном дефекта 1 для функции относительно
сетки называет функцию ,
являющуюся многочленом 3-й степени на каждом из отрезков , принадлежащую классу дважды непрерывно
дифференцируемых функции и удовлетворяющую условиям
.
При таком определении
кубического сплайна, он имеет еще свободных параметра, для нахождения которых
на сплайн налагаются дополнительные краевые условия. Например или и , или некоторые другие.
Полиномиальный
интерполяционный сплайн произвольной степени m дефекта r определяется как функция , удовлетворяющая,
кроме условий и , еще
дополнительно условиям совпадения в узлах сетки значений функции и интерполированной функции и их производных до некоторого порядка.
Часто при обработке
эмпирических данных коэффициенты в определяют
исходя из требования минимизации суммы
-
заданные числа, .
Такое построение функции
называют интерполированием по методу наименьших квадратов.
Интерполирование функций
многих переменных имеет ряд принципиальных и алгебраических трудностей.
Например в случае алгебраической интерполяции интерполяционный многочлен
Лагранжа фиксированной степени, вообще говоря, не существует для произвольной
схемы различных узлов интерполяции. В частности для функций двух переменных такой многочлен суммарной
степени не выше n может
быть построен по узлам лишь при условии, что эти узлы
не лежат на алгебраической кривой порядка n.
Другой поход к интерполированию
функции многих переменных стоит в том, что
сначала интерполируется функция по переменной при
фиксированных потом по следующей переменной
при фиксированных и т.д. интерполяционные
сплайны для функций многих переменных определяются по многомерной сетке при
соответствующих изменениях по аналогии с одномерным случаем.
Интерполирование функций
и численные методы. Интерполирование функции используется:
1. для замены сложно вычисляемой функции
другой, вычисляемой проще
2. для приближенного восстановления функции
на всей области задания по значениям её в отдельных точках или по другим
известным величинам
3. для получения сглаживающих функций
4. для приближенного нахождения
предельных значений функции
5. в задачах ускорения сходимости последовательностей
и рядов и в других вопросах.
Общие идеи построения
интерполяционных методов решения уравнения =0 и
систем уравнения , одни и те же. Трудности
задачи интерполирования функций многих преременных особенно сказывается при
исследовании и практическом использовании такого рода методов для большого
числа уравнений. В основу получении интерполяционных методов решения уравнения =0 положена замена функции ее интерполяционным многочленом и последующим решением уравнения =0 берутся за приближенные решении
уравнения =0 интерполяционный многочлен используется так же при построении итерационных
методов решения уравнения =0.
Например взяв за корень линейного интерполяционного
алгебраического многочлена, построенного по значениям и
в узле или
по значениям и в
узлах и ,
приходят соответственно к методу Ньютона и метода секущих
,
где -
разделенная разность функций для узлов и .
Другой подход к построению
численных методов решения уравнения =0 основан на интерполировании
обратной функции . Пусть в качестве
интерполяционной формулы для функции взят интерполяционный
алгебраический многочлен Лагранжа , построенный по узлам
Тогда за следующее приближению к корню уравнения =0 берется
величина .
Численное интегрирование.
Аппарат интерполирования функции лежит в основе построения многих квадратурных
и кубатурных формул. Такого рода формулы строятся путем замены интегрируемой
функции на всей области или на её составных частях интерполяционными
многочленами того или иного вида и последующим интегрированием этих
многочленов. Например квадратурные формулы наивысшей алгебраической степени
точности, так называемые квадратурные формулы Гаусса:
где -
знакопостоянная весовая функция, получаемая в результате замены функции интерполяционным алгебраическим
многочленом, построенным по корням ортогонального
относительно веса многочлена степени n.
Изложенная выше схема
построения формул для приближенного вычисления интегралов применима и в
многомерном случае
Формулы численного
дифференцирования, в основе которых лежит интерполирование, получаются в
результате дифференцирования интерполяционных многочленов. Ввиду неустойчивости
задачи численнго дифференцирования относительно ошибок использования значений
функций в узлах шаг интерполирования должен согласоваться с погрешносьтью
значений функций. Поэтому на практике нередки случаи, когда известная на густой
сетке функция используется в данной задаче не во всех точках, а на более редкой
сетке.
При численном решении
интегральных уравнений, известная функция заменяется
в интегральном уравнении каким-либо интерполяционным приближением
(интерполяционным алгебраическим многочленом, интерполяционным сплайном и т.д.)
с узлами интерполирования , а приближенные значения
для находятся
из системы, полученной после подстановке вместо независимости переменной x узлов интерполирования . В случае нелинейных интегральных
уравнений приближенные значения находятся
соответственно из нелинейной системы.
Интерполяционная формула-
для приближенного вычисления значений функции ,
основанного вычисления на замене приближаемой функции более
простой в каком- то смысле функцией
|
наперед заданного класса, причем
параметры выбираются так чтобы значения совпадали с известными заранее
значениями для данного множества попаро различных значений аргумента:
такой способ приближенного
представления функций называется интерполированием, а точки , для которых должны выполняться условия , - узлами интерполяции.
В ряде случаев (например,
при интерполировании алгебраическими многочленами) параметры могут быть явно выражены из системы , и тогда непосредственно
используется для приближенного вычисления значений функции .
Интерполяционный процесс- процесс получения
последовательности интерполирующих функций при
неограниченном возрастании числа n узлов
интерполирования. Если интерполирующие функции представлены
в виде частных сумм некоторого функционального ряда, то последний иногда
называется интерполяционным рядом. Целью построения
интерполяционного полинома чаще всего является, по крайней мере в простейших
первоначальных задачах интерполирования, приближение в каком- то смысле по
средствам интерполирующих функций , о которой или
имеется неполная информация, или форма которой слишком сложна для
непосредственного использования.
Интерполяционная формула
Эверетта:
Интерполяционные формулы Грегори-
Ньютона построенные по нисходящим или восходящим разностям, наиболее
целесообразно применять в начале или конце таблицы. При этом для достижения высокой
степени точности иногда приходится рассматривать разности, отстоящие достаточно
далеко от интересующих нас значений функции или . Поэтому на средних участках таблицы
лучше результаты дают интерполяционные формулы, построенные на базе центральных
разностей, то есть разностей, которые ближе всего расположены к центральной
сотке, содержащей .
К интерполяционным формулам
с центральными разностями относятся формулы Гаусса, Стирлинга, Бесселя,
Эверетта и многие другие; формула Эверетта получила наибольшее распространение,
она была получена 1900 г.:
где ; ; .
Формуле Эверетта так же
можно придать форму, наиболее удобную для вычисления:
если для ее коэффициентов ввести
обозначения
Коэффициенты удобнее всего вычислять по следующей
рекуррентной формуле, которая непосредственно вытекает из :
; ;
Таблица разностей:
Таблицу можно продолжать строить, в
нашем случае до последнего , число разностей
зависит от количества значений y. Таблица
разностей высчитывается
, и
так далее(можно заметить такую систему в приведенной выше таблице)
Тестовый
пример.
П р и м е р. Функция задана таблицей на сегменте . Определим при помощи
интерполяции значение .
Р е ш е н и е.
По данным значениям функции составляем таблицу разностей (табл. 1), из которых
видно, что четвертые разности в данном примере практически равны постоянны, а
пятые разности практически равны нулю, и поэтому мы их в дальнейших вычислениях
не будем принимать во внимание.
Принимаем =0,85; =0,9; =0,874.
Тогда =0,8273695; =0,8075238,
и, далее, так как шаг таблицы =0,05, то
Т а б
л и ц а 2
x
|
|
|
|
|
|
|
0.60
0.65
0.70
0.75
0.80
0.85
0.90
0.95
1.00
|
0.9120049
0.8971316
0.8812009
0.8642423
0.8462874
0.8273695
0.8075238
0.7867871
0.7651977
|
-0.0148733
-0.0159307
-0.0169586
-0.0179549
-0.0189179
-0.0198457
-0.0207367
-0.0215894
|
-0.0010574
-0.0010279
-0.0009963
-0.0009630
-0.0009278
-0.0008910
-0.0008527
|
0.0000295
0.0000316
0.0000333
0.0000352
0.0000368
0.0000383
|
0.0000021
0.0000017
0.0000019
0.0000014
0.0000015
|
-0.0000004
0.0000002
-0.0000005
0.0000001
|
Т а б
л и ц а 2
Эверетта
|
|
|
0
1
2
|
0.52000
-0.06323
0.01179
|
0.82273695
-0.0009278
0.0000014
|
0
1
2
|
0.48000
-0.06157
0.01160
|
0.8075238
-0.0008910
0.0000015
|
|
Все
вычисления по формуле Эверетта представлены в табл. 2.
Все
необходимые значения разностей(и самой функции, которые мы в табл. 2 обозначили
как разности нулевого порядка ) взяты из табл. 1.
Первые три строки в табл. 2 заполнены значениями для и , а
последующие три строки соответственно значениями для и .
Перемножив (не
снимая промежуточных результатов) коэффициенты на
расположенные в той же строке , мы и получим искомое
значение функции , как сумму произведений
Проверка
производится непосредственно при помощи степенного ряда для рассматриваемой
функции Эверетта согласно которому получим
ГЛАВА
№2
MAIN
Заключение
Удалось построить
интерполяционный многочлен и вычислить по нему значение функции для заданного
значения аргумента. Составлена блок схема алгоритма и программа на языке С++ (Приложение)
для вычисления заданного интерполяционного многочлена. В программе
предусмотрена возможность ввода любого числа значений функции для чего
организованно хранение ее значения при помощи линейного списка.
Список литературы
1. Архангельский Н.А. Вычислительные
методы алгебры в приемах и задачах. М.: МАИ, 1976.
2. Васильев Ф.П. Численные методы
решения экстремальных задачь. М.: Наука,1988.
3. Васильков Ф.В., Василькова Н.Н.
Компьютерные технологии вычислений в математическом моделировании: Учеб.
Пособие. М.: Финансы и статистика, 1999.
4. Фильчаков П.Ф., Справочник по высшей
математике. Киев: Наукова думка, 1974.
5. Фильчаков П.Ф., Численные методы.
Киев: Наукова думка, 1976.
6. Большая математическая энциклопедия.
М.: Олма-Пресс, 2004
7. Демидович Б.П., Марон И.А. Основы
вычислительной математики. М.: Наука, 1970.
8. Тихонов А.Н., Вводные лекции по
прикладной математике. М.: Наука, 1984.
9. Калиткин Н.Н., Численные методы. М.:
Наука, 1987.
10. Корн Г., Корн Т. Справочник по математике. М.: Наука,
1984.