Интерполирование функций с помощью полиномов Ньютона
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное
бюджетное образовательное
“Восточно-Сибирский
государственный университет
(ФГБОУ ВПО ВСГУТУ)
Институт устойчивого развития
Эколого-гуманитарный факультет
Кафедра “Прикладная математика”
Курсовая работа
по дисциплине “Численные методы ”
на тему: “ Интерполирование функций с помощью полиномов Ньютона”
Исполнитель: студентка
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):
Интерполяционным многочленом Ньютона называется многочлен
Рассмотренная форма полинома Ньютона носит название первой интерполяционной формулы Ньютона, и используется, обычно, при интерполировании в начале таблицы.
Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции yi, 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[
end;
L:=L+P*y[0];
end;
Polinom:=l;
end;
где
n – количество узлов
x[i],y[i] – табличные значения функции
D – точка, в которой необходимо вычислить значение l
Схематически программа представляется в виде последовательности восьми разделов:
- Заголовок программы
- Описание внешних модулей, процедур и функций
- Описание меток
- Описание констант
- Описание типов переменных
- Описание переменных
- Описание функций и процедур
- Раздел операторов
2.2 Разработка программы по схеме алгоритма
При разработке программы
в данной работе используются следующие
операторы и стандартные
Program - Заголовок программы
Uses – раздел подключения модулей
Begin – открывающая логическая скобка
End – закрывающая логическая скобка
:= - оператор присваивания
Crt - (Cathod ray tube - электронно-лучевая трубка) один из наиболее часто используемых модулей. Он содержит процедуры обслуживания процессов вывода информации на экран, ввода с клавиатуры, а также процедуры и функции вывода звуковых сигналов, работы с окнами на экране и вывода цветных текстовых строк на экран.
Graph – графический модуль для вывода базовых графических элементов, таких как точки, отрезки прямых линий, дуги и целые окружности и других графических элементов, называемых графическими примитивами
Var – раздел описания переменных
Writeln, Write – операторы вывода информации
Readln, Read – операторы ввода информации
If <условие> then <оператор>– оператор условного перехода
For <параметр>:=<нач.знач.> to <конечн.знач.> do <оператор> – оператор цикла с параметром
Repeat <оператор> until <условие> - оператор цикла с постусловием
Clrscr – очистка экрана
Initgraph – процедура инициализации графического режима
Closegraph – процедура закрытия графического режима
Line (x1, y1, x2, y2) – соединение двух точек отрезком
Putpixel (x, y, c) – построение точки (x, y) цветом с
Readkey – оператор считывание кода клавиш
Outtextxy (x, y, st) – вывод строки st, начиная с точки (x,y)
Getmaxx – результатом этой функции будет max значение x в данном видеорежиме
Goto – перейти к
+ - арифметическая операция сложения
- - арифметическая операция вычитания
* - арифметическая операция умножения
/ - арифметическая операция деления
Описание переменных и констант используемых в алгоритме
n – количество узлов в таблице, не считая начальную точку ;
i, j – счётчики;
- значения узлов записанных в одномерные массивы;
D – переменная, используемая для нахождения значения полинома Ньютона в этой точке;
L – переменная значения полинома Ньютона
k, step – константы используемые для построения графика полинома;
u – переменная шага деления графика;
Для описания алгоритма в данной курсовой работе были пронумерованы символы.
2.3 Инструкция пользования программой
Для запуска программы необходимо дважды щелкнуть на ярлыке с именем Newton.exe. После этого на экран будет выведен титульный лист. Чтобы продолжить надо нажать клавишу Enter.
Следующим шагом в окне программы будет показана строка с текстом «Показать пояснения к программе (1/0)?», чтобы увидеть их следует нажать 1 и подтвердить ввод нажатием клавиши Enter. Чтобы продолжить надо нажать клавишу Enter. Сразу после этого в диалоговом окне появится строка «Введите количество уpлов n (N=n+1)», где нужно указать количество (N-1) узлов таблицы и нажать Enter. Далее надо будет ввести значения из таблицы, по окончанию ввода нажать Enter.
На экран будет выведена введённая таблица значений. Затем пользователю будет предложено «Введите x ». Нужно ввести x для которого необходимо найти приближённое значение. После этого программа вычислит значение и предложит найти значения для другого x.
Потом программа спросит «повторить вычисления полинома для другой функции?» Чтобы начать заново нужно нажать 1, чтобы закончить работу с программой нажать 0 и после ввода подтвердить выбор клавишей Enter.
2.4 Исходные данные и результат решения контрольного примера
|
0 |
1 |
2 |
3 |
4 |
|
0 |
0.5 |
0.866 |
1 |
0.866 |
Вычислим значение таблично заданной функции в точке x=1.5
Получили значение 0.707 которое мало отличается от точного значения.
.
ЗАКЛЮЧЕНИЕ
В процессе выполнения данной курсовой работы была рассмотрена только первая формула полинома Ньютона, которая используется вблизи начала таблицы. Интерполяционный полином в форме Ньютона удобно использовать, если точка интерполирования находится вблизи начала таблицы. Этот полином интересен тем, что каждая частичная сумма первых m слагаемых есть интерполяционный полином m-1 степени, построенный по m первым табличным точкам. Поэтому интерполяционные полиномы Ньютона удобно использовать при последовательном увеличении степени интерполяционного многочлена.
К недостатку формулы Ньютона можно отнести то, что при вычислениях в таблице с постоянным шагом при увеличении количества узлов не всегда удается добиться повышения точности вычислений. Это обусловлено тем, что равноотстоящие узлы не являются лучшими с точки зрения уменьшения погрешности интерполирования. Если имеется возможность выбора узлов интерполирования, то их следует выбирать так, чтобы обеспечить минимум погрешности интерполяции.
В процессе выполнения курсовой работы были закреплены приобретенные за период обучения навыки и умения самостоятельного составления алгоритмов и программ на языке программирования Turbo Pascal 7.0 для решения простых типовых математических задач. Эта работа ещё раз подтвердила полезность использования ЭВМ для решения прикладных математических задач. Полученные знания и накопленный опыт решения простых задач в будущем позволят разрабатывать гораздо более сложные программы и алгоритмы, облегчат разбиение сложных задач на простые элементы.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
- Введение в численные методы/ А.А. Самарский – М.: наука, 1982.
- Начала программирования на языке Паскаль/С.А. Абрамов – М., 1987.
- Практическое руководство по методам вычислений с приложением программ для персональных компьютеров/ В.И. Ракитин – М.: Высш. шк., 1998.
- Программирование в среде Турбо Паскаль/Д.Б. Поляков – М., 1992.
- Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ/ В.П. Дьяконов – М.: Наука, 1987.
- Турбо Паскаль 7.0/В.В. Фаронов – М., 1998.
- Численные методы анализа/Б.П. Демидович – М.: Государственное издательство физико-математической литературы, 1962.
- Численные методы /Калиткин Н.Н. – М.: 1996
- Немнюгин С.A. Turbo Pascal - СПб.: Питер, 2002.- 496 с,
ПРИЛОЖЕНИЕ
Листинг программы
program interpol;
uses crt;
const
MAXCOUNT=30;
type
per = array [0..MAXCOUNT] of real;
var
X,y :per;
n,i :integer;
l,D,f :real;
label Lp, Lt;
{procedura vivoda titulnogo lista}
Procedure Titul;
begin
Clrscr;
GoToXY(23,2);
Writeln('FEDERALNOE AGENSTVO PO OBRAZOVANIYU');
GoToXY(22,3);
Writeln('ESSTU');
GoToXY(28,4);
Writeln('KAFEDRA PRIKLADNOI MATEMATIKI');
GoToXY(14,8);
Writeln('METOD NEWTONA.');
GoToXY(34,12);
Writeln('TEMA 1');
GoToXY(24,17);
Writeln('STUDENT GR.740 ZHAMBALOVA S.B.');
GoToXY(20,19);
Writeln('RUKOVODITEL NAZAROVA L.I.');
GoToXY(33,23);
Writeln('ULAN-UDE, 2013 g.');
readkey;
clrscr;
end;
{procedura vivoda poyasneniya k programme}
Procedure help;
begin
clrscr;
writeln ('programma po по znacheniyam funkcii f(x) zadannoi tablichno v neskolkyh tochkah otrezka nahodit ee znacheniya v ' +
+ 'ostalnyh tochkah dannogo otrezka. Tochki s koordinatami (xi, yi) nazyvayutsya uzlovymi tochkami ili uzlami.');
writeln ('kolichestvo uzlov v tablichnoi funkcii dolzhno byti ravno N=n+1. ');
writeln (' posle vvoda kolichestva uzlov n (nachalnaya tochka (x[0],y[0]) ne yavlyaetsya uzlom) nuzhno vvodit uzlovie tochki +'
+' funkcii. posle etogo programma smozhet nahodit znacheniya dannoi funkcii v ostalnyh tochkah otrezka (x[0]..x[n]).');
readkey;
clrscr;
end;
{procedura vvod tablichnyh znachenii}
procedure Enter(var X,y: per);
var
i: integer;
label mp;
begin
mp: for i:=0 to n do
begin
write('X[',i,'] = '); readln(x[i]);
write('y[',i,'] = '); readln(y[i]);
end;
for i:=0 to n-1 do
if x[i+1]-x[i]<=0 then
begin
writeln ('oshibka. povtorite vvod.');
goto mp
end;
end;
{procedura vivoda tablichnyh znachenii}
procedure Print(n: integer; X,y: per); var
i: integer;
begin
for i:=0 to n do
begin
write(x[i]:12:6);
end;
writeln;
for i:=0 to n do
begin
write(y[i]:12:6);
end;
writeln;
end;
{funkciya formuly Newtona}
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[
end;
L:=L+P*y[0];
end;
POlinom:=l;
end;
{osnovnoi tekst programmy}
begin
TextMode(3);
TextBackground(1);
TextColor(14);
Titul;
writeln ('vivesti poyasnenie k programme? (da-1,net-0)');
read (f);
if f=1 then help else
lp:clrscr;
writeln('vvedite kolichestvo uzlov n (N=n+1)');
read(n);
Enter(X,y);
Print(n,X,y);
repeat
lt:Writeln('vvedite X (ot ',x[0]:4:2,' do ',x[n]:4:2,')');
read(d);
if d<x[0] then begin
writeln('oshibka. x ne mozhet byti menshe',x[0]:4:2);
goto lt; end;
if d>x[n] then begin
writeln('oshibka. x ne mozhet byti bolshe ',x[n]:4:2);
goto lt; end;
writeln(Polinom (n,d,X,y):6:3);
writeln('naiti znacheniya dlya drugoi tochki X?(da-1,net-0)');
read(f)
until f=0;
readkey;
clrscr;
writeln('povtorit dlya drugoi funkcii? (da-1,net-0)');
read(f);
if f=1 then goto lp else end.
- Интерполирование функций. Формула Лагранжа и Эрмита
- Интерполяционная задача Абеля-Гончарова
- Интерполяционная задача Абеля-Гончарова
- Интерполяция кубическими сплайнами
- Интерполяция сплайнами
- Интерполяция функции с разрывом производной
- Интерпретатор фиксированной XML-структуры в SQL-запросы
- Интернет-трейдинг
- Интернет-трейдинг в России
- Интернет – услуги кредитных организаций
- Интернет-феномены в рекламе
- Интернет-центр в гостинице
- Интернет-экономика
- Интерперсональный контекст депрессии
