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

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

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

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

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

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

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

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

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

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

Архангельск

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

Т а б
л и ц а 2

            Все
вычисления по формуле Эверетта представлены в табл. 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.