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