Интерполирование функций с помощью полиномов Ньютона

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

Федеральное государственное  бюджетное образовательное учреждение высшего профессионального образования

“Восточно-Сибирский  государственный университет технологий и управления”

(ФГБОУ ВПО ВСГУТУ)

Институт устойчивого развития

Эколого-гуманитарный факультет

Кафедра “Прикладная  математика”

 

Курсовая работа

по дисциплине “Численные методы ”

на тему: “ Интерполирование функций с помощью полиномов Ньютона”

 

 

 

 

 

Исполнитель: студентка 740 гр._______________________Жамбалова С.Б.

Руководитель работы ________________________________ Назарова Л.И.

Нормоконтролер _____________________________________Назарова Л.И.

 

 

 

 

 

 

 

2013 г.

ВОСТОЧНО-СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ ТЕХНОЛОГИЙ И УПРАВЛЕНИЯ

ЭКОЛОГО-ГУМАНИТАРНЫЙ ФАКУЛЬТЕТ

Кафедра «Прикладная  математика»

 

  ЗАДАНИЕ

на курсовую работу

 

Дисциплина: Численные методы

Тема: Интерполирование функций с помощью полиномов Ньютона

Исполнитель: Жамбалова С.Б.

Руководитель: Назарова Л.И.

Краткое содержание проекта:  В курсовой работе рассматривается интерполирование

функций с помощью полиномов  Ньютона

Глава 1: Постановка задачи интерполяции

Глава 2: Реализация интерполирования функций с помощью полиномов Ньютона

Сроки выполнения проекта  по графику:

Теоретический раздел      -  к  __ неделе.

2. Основной раздел. Проектирование    -   к  __ неделе.

3. Основной раздел. Кодирование  -   к __ неделе.

4. Экспериментальный раздел -   к __ неделе.

5. Защита -  к ___ неделе.

Требования к оформлению:

1. Расчетно-пояснительная записка курсового проекта должна быть представлена  в

электронной и твердой копиях.

2. Объем  РПЗ  должен быть  не менее 20 машинописных страниц  без учета приложений.

3. РПЗ оформляется по ГОСТу  7.32-91 и подписывается  у ответств. за нормоконтроль.

 

 

Руководитель проекта___________________

Исполнитель              _____________________

Дата выдачи           "___" ____________201_ г.

СОДЕРЖАНИЕ

Введение…………………………………………………..…………….…..…..…

Глава 1. Постановка задачи интерполяции

1.1 Постановка задачи………………………………..………………………

1.2 Интерполяция по Ньютону ……………………….…………………..……

Глава 2. Реализация интерполирования функций с помощью полиномов Ньютона

     2.1 Программирование функции формулы Ньютона ………………………

2.2 Разработка программы по схеме алгоритма …………………………....

2.3 Инструкция пользования программой…………………………………

2.4 Исходные данные и результат  решения контрольного примера……..

Заключение………….…….……………………………………..…………..…..

Список использованных источников…………..…………..…………..………

Приложения………………………..…….………….………………..………….

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

В вычислительной математике существенную роль играет интерполяция функций, т.е. построение по заданной функции другой (как  правило, более простой), значения которой  совпадают со значениями заданной функции в некотором числе точек. Причем интерполяция имеет как практическое, так и теоретическое значение. На практике часто возникает задача о восстановлении непрерывной функции по ее табличным значениям, например полученным в ходе некоторого эксперимента. Для вычисления многих функций оказывается эффективно приблизить их полиномами или дробно-рациональными функциями. Теория интерполирования используется при построении и исследовании квадратурных формул для численного интегрирования, для получения методов решения дифференциальных и интегральных уравнений.

В нашем случае для  более полного раскрытия данной темы подробно рассмотрим для начала само понятие интерполяции, далее  интерполирование с помощью полиномов Ньютона.

 

 

 

 

 

 

 

 

 

 

 ГЛАВА 1. ПОСТАНОВКА ЗАДАЧИ ИНТЕРПОЛЯЦИИ

При выполнении курсовой работы была выбрана следующая математическая модель:

Интерполяция и приближение  функций.

1.1 Постановка  задачи.

Одной из основных задач  численного анализа является задача об интерполяции функций. Часто требуется  восстановить функцию для всех значений на отрезке если известны ее значения в некотором конечном числе точек этого отрезка. Эти значения могут быть найдены в результате наблюдений (измерений) в каком-то натурном эксперименте, либо в результате вычислений. Кроме того, может оказаться, что функция задается формулой и вычисления ее значений по этой формуле очень трудоемки, поэтому желательно иметь для функции более простую (менее трудоемкую для вычислении) формулу, которая позволяла бы находить приближенное значение рассматриваемой функции с требуемой точностью в любой точке отрезка. В результате возникает следующая математическая задача.

Пусть на отрезке задана сетка

 

 

 

и в ее узлах заданы значения функции  , равные

 

.

 

Требуется построить интерполянту — функцию , совпадающую с функцией в узлах сетки:

 

  .

 

Основная цель интерполяции — получить быстрый (экономичный) алгоритм вычисления значений для значений , не содержащихся в таблице данных.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.2 Интерполяция по Ньютону

Дана табличная функция:

i
0
1
2
..	..	..
n

 

 

 

 

 

 

 

Или

 

, (1)

 

Точки с координатами называются узловыми точками или узлами.

Количество узлов в  табличной функции равно N=n+1.

Необходимо найти значение этой функции в промежуточной  точке, например, , причем . Для решения задачи используется интерполяционный многочлен.

Интерполяционный многочлен  по формуле Ньютона имеет вид:

 

 

где n – степень многочлена,

Интерполяционная формула  Ньютона формула позволяет выразить интерполяционный многочлен  через значение в одном из узлов и через разделенные разности функции , построенные по узлам .

Сначала приведем необходимые  сведения о разделенных разностях.

Пусть в узлах

 

,

 

известны значения функции  . Предположим, что среди точек , , нет совпадающих. Разделенными разностями первого порядка называются отношения

 

, , .

 

Будем рассматривать  разделенные разности, составленные по соседним узлам, т. е. выражения

 

.

 

По этим разделенным  разностям первого порядка можно  построить разделенные разности второго порядка:

 

,

,

 

Таким образом, разделённая  разность -го порядка на участке может быть определена через разделённые разности -го порядка по рекуррентной формуле:

 

. (3)

 

где , , - степень многочлена.

Максимальное значение равно . Тогда и разделенная разность n-го порядка на участке равна

 

,

 

т.е. равна разности разделенных  разностей  -го порядка, разделенной на длину участка .

Разделенные разности

 

 

 

являются вполне определенными  числами, поэтому выражение (1) действительно  является алгебраическим многочленом -й степени. При этом в многочлене (1) все разделенные разности определены для участков , .

При вычислении разделенных  разностей принято записывать их в виде таблицы

			•
		•	•	•
■	•	•	•
•	•	•
•	•

 

Разделенная разность -го порядка следующим образом выражается через значения функции в узлах:

 

. (1)

 

Эту формулу можно  доказать методом индукции. Нам потребуется  частный случай формулы (1):

 

 

Интерполяционным многочленом Ньютона называется многочлен

 

 

 

Рассмотренная форма  полинома Ньютона носит название первой интерполяционной формулы Ньютона, и используется, обычно, при интерполировании в начале таблицы.

Заметим, что решение  задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции y_i, i=0,1,…n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (2). Это удобно на практике и ускоряет процесс вычислений.

 

 

 

 

 

 

 

 

 

 

 

 

ГЛАВА 2. РЕАЛИЗАЦИЯ ИНТЕРПОЛИРОВАНИЯ ФУНКЦИЙ С ПОМОЩЬЮ ПОЛИНОМОВ НЬЮТОНА

2.1 Программирование  функции формулы Ньютона

Для построения многочлена Ньютона по формуле (1) организуем циклический вычислительный процесс по . При этом на каждом шаге поиска находим разделенные разности k-го порядка. Будем помещать разделенные разности на каждом шаге в массив Y.

Тогда рекуррентная формула (3) будет иметь вид:

 

(4)

 

В формуле Ньютона (2) используются разделенные разности -го порядка, подсчитанные только для участков т.е. разделенные разности -го порядка для . Обозначим эти разделенные разности k-го порядка как . А разделенные разности, подсчитанные для , используются для расчетов разделенных разностей более высоких порядков.

Используя (4), свернем  формулу (2). В результате получим

 

(5)

 

где – значение табличной функции (1) для .

– разделенная разность -го порядка для участка .

 

.

 

Для вычисления Р удобно использовать рекуррентную формулу внутри цикла по .

 

Схема алгоритма интерполяции по Ньютону представлена на рисунке:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Function Polinom(n: integer; d:real; x,y :per):real;

var

l:real;

k,i:integer;

p: real;

begin

L:=y[0];

P:=1;

for k:=1 to n do begin

P:=P*(D-X[k-1]);

for i:=0 to (n-k) do begin

Y[i]:=(y[i+1]-y[i])/(x[i+k]-x[i]);

end;

L:=L+P*y[0];

end;

Polinom:=l;

end;

 

где    

n – количество узлов

x[i],y[i] – табличные значения функции

D – точка, в которой необходимо вычислить значение l

Схематически программа  представляется в виде последовательности восьми разделов:

1. Заголовок программы
2. Описание внешних модулей, процедур и функций
3. Описание меток
4. Описание констант
5. Описание типов переменных
6. Описание переменных
7. Описание функций и процедур
8. Раздел операторов