МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ
ФЕДЕРАЦИИ
Международная «Лига развития науки и
образования» (Россия)
Международная ассоциация развития
науки, образования и культуры России (Италия)
Международный «ИНСТИТУТ УПРАВЛЕНИЯ»
(г. Архангельск)
КУРСОВАЯ РАБОТА
ПО ДИСЦИПЛИНЕ
«Информатика и программирование»
Тема : «Построение интерполяционного
многочлена и вычисление по нему значения функции для заданного аргумента»
Выполнил:
студент экономического факультета, группы 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
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.