на тему- ІНТЕРПОЛЯЦІЯ ФУНКЦІЙ МНОГОЧЛЕНАМИ

Работа добавлена на сайт samzan.net:

МІНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

СУМСЬКИЙ ДЕРЖАВНИЙ УНІВЕРСИТЕТ

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

на тему:
«ІНТЕРПОЛЯЦІЯ ФУНКЦІЙ МНОГОЧЛЕНАМИ»

                                                                                      

                                                                                          Виконав:

                                                                                                                              ст. групи ІН-52

             Новіков Віталій

                                                                                                                         Вікторович

                                                                                               Перевірила:

             Глущенко Л.О.

Суми 2007

Зміст

1.  Теорія

               Інтерполяційний многочлен Лагранжа

               Інтерполяційний поліном Ньютона

               Інтерполяція за допомогою  сплайнів

                       Кубічні сплайни

1.  Постановка  задачі
2.  Реалізація алгоритму мовою програмування Pascal
3.  Отримання результату
4.  Висновок
5.  Література

Інтерполяційний многочлен Лагранжа.

На відрізку  задано N точок , що називаються вузлами інтерполяції , і значення деякої функції  в цих точках: . Потрібно побудувати функцію  ( функцію , що інтерполює ) , яка б збігалася з  у вузлах інтерполяції і наближала її між ними, тобто таку,що . Геометрична інтерпретація задачі інтерполяції полягає в тому, що потрібно знайти таку криву  певного типу, що проходить через задану систему точок  За допомогою цієї кривої можна знайти наближене значення , де  Задача інтерполяції стає однозначною, якщо замість довільної функції  шукати многочлен  степеня не вище , що задовольняє умови

.

Інтерполяційний многочлен  завжди однозначний, оскільки існує тільки один многочлен степеня , що в даних точках набуває заданих значень. Існує декілька способів побудови інтерполяційного многочлена.

Інтерполяційний многочлен Лагранжа, що набуває у вузлах інтерполяції  відповідно значень  має вигляд

         (1)

З формули безпосередньо випливає , що степінь многочлена  дорівнює , і многочлен Лагранжа задовольняє всі умови задачі інтерполяції.

Якщо відстань між всіма сусідніми вузлами інтерполювання є однаковою, тобто , формула (1.1) суттєво спрощується. Введемо нову змінну , тоді   Інтерполяційний поліном Лагранжа набуде такого вигляду:

.               (2)

Тут . Коефіцієнти, що стоять перед величинами  у формулі (2), не залежать ні від функції  ні від кроку , а лише від величин  Тому таблицями, що складені для різних значень , можна скористатися при розв’язуванні різноманітних задач інтерполювання для рівновіддалених вузлів.

Виникає питання, наскільки близько многочлен Лагранжа наближається до функції  в інших точках (не вузлових), тобто наскільки великий залишковий член .На функцію  накладають додаткові обмеження. А саме: припускають, що в розглянутій області  зміни , що містить вузли інтерполяції, функція  має усі похідні  до -го порядку включно. Тоді оцінка для абсолютної похибки інтерполяційної формули Лагранжа має вигляд

,        (3)

де  .

 Інтерполяційний поліном Ньютона

Поділеними різницями називають співвідношення вигляду:

- першого порядку:..

 

- другого порядку:

         (4)

……………………………………………………………;

- n- го порядку:

За їх допомогою можна побудувати многочлен

                        (5)

Він називається інтерполяційним поліномом Ньютона для заданої функціії . Ця форма запису більш зручна для застосування, оскільки при додаванні до вузлів x0, x1, …, xn нового xn+1 всі обчислені раніше члени залишаються без зміни, а у формулу додається тільки один доданок. При застосуванні ж формули Лагранжа треба робити всі обчислення знову.

Якщо значення функції задані для рівновіддалених значень аргументу  (постійну величину , i=0,1,…,n називають кроком інтерполяції), то інтерполяційний поліном набуде вигляду

                   (6)

Тут - скінченні різниці к-го порядку. Вони визначаються за формулою   де -біноміальні коефіцієнти.

Порівнюючи цю формулу з попередньою, легко встановити, що при   скінчені і поділені різниці пов'язані співвідношенням вигляду

                              (7)

Для практичного використання формулу (6) записують у перетвореному вигляді. Для цього введемо нову змінну , поклавши  де  - кількість кроків , необхідних для досягнення точки  із точки . Таким чином отримаємо першу інтерполяційну формулу Ньютона для інтерполювання вперед, тобто на початку таблиці значень:

 (8)

Припустимо, що точка інтерполяції розташована поблизу кінцевої точки  таблиці. У цьому випадку вузли інтерполяції слід брати у порядку  Формула Ньютона для інтерполювання назад тоді матиме вигляд

(9)

Поділені різниці можна виразити через скінчені різниці, якщо скористатися можливістю переставляти в них аргументи, та співвідношенням (7), із яких випливає

;     

Введемо змінну , поклавши  дістанемо для  другу інтерполяційну формулу Ньютона для інтерполювання в кінці таблиці

Як перша, так і друга інтерполяційні формули Ньютона можуть бути використані для екстраполяції функції, тобто для знаходження значень функції , значення аргументів  якої лежать поза таблицею. Якщо  і значення  близьке до , то вигідно використовувати перший інтерполяційний поліном Ньютона, тоді  і  Таким чином, перша інтерполяційна формула Ньютона застосовується для інтерполювання вперед та екстраполювання назад, а друга – навпаки, для інтерполювання назад та екстраполювання вперед.

Зазначимо, що операція екстраполювання, взагалі кажучи, менш точна, ніж операція інтерполювання.

Інтерполяційні формули Ньютона вигідні, оскільки при до-даванні  нових вузлів інтерполяції потрібні додаткові обчислення тільки для  нових членів, без зміни старих.

Інтерполяція за допомогою  сплайнів

Підвищення точності інтерполювання вимагає збільшення вузлів інтерполяції. Це призведе до зростання степеня інтерполяційних многочленів. Але в умовах відсутності додаткової інформації про задану таблично функцію останні дають досить значну похибку. В цьому випадку більш ефективним є використання сплайнів, що на проміжку між вузлами інтерполювання є поліномом невисокого степеня. На всьому проміжку інтерполяції  сплайн - це функція, що склеєна з різних частин поліномів. Отже, розглянемо на відрізку  систему вузлів . Сплайном  називається функція, що визначена на , має на ньому неперервні похідні  порядку і на кожному частковому відрізку  збігається з деяким многочленом степеня не вище . При цьому хоча б на одному з відрізків степінь многочлена дорівнює . Якщо , то це  інтерполюючий сплайн.

Лінійний сплайн – це ламана, що проходить через вузли інтерполювання. Рівняння ламаної для  

.                          (10)

                               y

                                                                                               *

                                                                                        *

                                                            *

                                                      *

                                               *

                                                         *

                                        *

                              O                                                  x

 

 Кубічні сплайни

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

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

Тут  .  Для їх визначення  накладають умови неперервності другої похідної в точці  та обмеження на значення сплайна і його похідних на кінцях проміжку  - крайові умови. Тобто потрібна додаткова інформація про функцію, для якої є потреба в інтерполюванні.

Випадки використання кубічного сплайна.

При побудові інтерполяційного кубічного сплайну найчастіше використовуються граничні (крайові) умови чотирьох типів. Вибір граничних (крайових) умов є однією з центральних проблем при інтерполяції функцій. Він особливо важливий при потребі забезпечити високу точність апроксимації функції  сплайном  поблизу кінців відрізка . Граничні значення суттєво впливають на поведінку сплайна  поблизу точок а та b. Цей вплив швидко слабшає при відході від них.

Якщо на кінцях відрізка  відомі значення 1-ї похідної , то природно скористатися граничними (крайовими) умовами 1-го типу.

1.  Граничні (крайові) умови 1-го типу. Якщо відомо, що , то для визначення  маємо систему рівнянь

                      (11)

Якщо на кінцях відрізка  відомі значення 2-ї похідної , то природно скористатися граничними (крайовими) умовами 2-го типу.

1.  Граничні (крайові) умови 2-го типу. Якщо відомо

, то відповідна система рівнянь

                     (12)

Якщо є можливість вибору між граничними (крайовими) умовами 1-го та 2-го типу, то перевагу слід надати умовам 1-го типу.

У випадку, коли ніякої додаткової інформації про поведінку апроксимованої функції нема, часто використовують так звані природні граничні (крайові) умови .Однак слід мати на увазі, що при такому виборі граничних (крайових) умов точність апроксимації функції  сплайном  поблизу кінців відрізка  різко знижується. Іноді користуються граничними (крайовими) умовами 1-го або 2-го типу, але не з точними значеннями відповідних похідних, а з їх різницевими апроксимаціями. Точність такого підходу невисока.

Практичний досвід розрахунків показує, що в такій ситуації найбільш доцільним є вибір природних граничних ( крайових) умов.

Якщо  - періодична функція, то слід зупинитися на граничних (крайових) умовах 3-го типу.

1.  Граничні (крайові) умови 3-го типу. Якщо  - періодична функція , то  і система рівнянь має вигляд

             (13)

 

Апроксимаційні властивості кубічного сплайну

Апроксимаційні властивості кубічного сплайну залежать від гладкості функції - чим вище гладкість інтерпольованої функції, тим вище порядок апроксимації при подрібленні сітки та тим швидшою є збіжність.

Якщо інтерпольована функція  неперервна на відрізку , тобто , то

    при .

Якщо інтерпольована функція  має на відрізку  неперервну першу похідну, тобто , а  - інтерполяційний сплайн, що задовольняє граничні умови 1-го або 3-го типу, то при  маємо

   

В цьому випадку не тільки сплайн збігається до інтерпольованої функції, але і похідна сплайна збігається до похідної цієї функції.

В випадку якщо , сплайн  апроксимує на відрізку  функцію , а його 1-а та 2-а похідні апроксимують відповідно функції  та : при цьому

 

 Для  отримання результатів ми використаємо інтерполяцію многочленна Лагранжа, а також  дані по сплайну.

Постановка  задачі

    Для функції  y=f(x)  обчислити в заданій точці  x* ,значення інтерполяційний многочлена і  сплайна.

Значення	x*
x        0             1           2            3             4	1,6
y        1             2           7          10             5

 

Реалізація алгоритму мовою програмування Pascal:

 program spline_legrange;

uses wincrt;

const eps=0.0001;

     n=5;

     h=1;

type mas=array[1..n]of real;

var m,m1,b,d,summ,x,y:mas;

   i,j,l:integer;

   norm,Mm,Delta,x0,splin,s1,s2,z:real;

   A,C:array[1..n,1..n]of real;

procedure lagrange(y,x:mas;x0:real;var z:real);

var i,j:integer;

   g,f:real;

begin

for i:=1 to 5 do

begin

f:=1;

g:=1;

for j:=1 to 5 do

begin

if (i<>j) then

begin

f:=f*(x0-x[j]);

g:=g*(x[i]-x[j]);

end;

end;

z:=z+f*y[i]/g;

end;

end;

function zeidel1(x:mas):real;

begin

zeidel1:=C[1,2]*x[2]+C[1,3]*x[3]+C[1,4]*x[4]+C[1,5]*x[5]+D[1]

end;

function zeidel2(x:mas):real;

begin

zeidel2:=C[2,1]*x[1]+C[2,3]*x[3]+C[2,4]*x[4]+C[2,5]*x[5]+D[2]

end;

function zeidel3(x:mas):real;

begin

zeidel3:=C[3,1]*x[1]+C[3,2]*x[2]+C[3,4]*x[4]+C[3,5]*x[5]+D[3]

end;

function zeidel4(x:mas):real;

begin

zeidel4:=C[4,1]*x[1]+C[4,2]*x[2]+C[4,3]*x[3]+C[4,5]*x[5]+D[4]

end;

function zeidel5(x:mas):real;

begin

zeidel5:=C[5,1]*x[1]+C[5,2]*x[2]+C[5,3]*x[3]+C[5,4]*x[4]+D[5]

end;

{max norma}

function max(x,x1:mas):real;

var s:real;

begin s:=abs(x[1]-x1[1]);

    for i:=2 to 5 do   if abs(x[i]-x1[i])>s then s:=abs(x[i]-x1[i]);

max:=s;

end;

{--------}

begin

writeln('   vvedite to4ky:');

write('x=');

readln(x0);

x[1]:=0; x[2]:=1; x[3]:=2; x[4]:=3; x[5]:=4;

y[1]:=1;y[2]:=2;y[3]:=7;y[4]:=10;y[5]:=5;

a[1,1]:=2; a[1,2]:=1;  for i:=3 to n do a[1,i]:=0;

a[2,1]:=1; a[2,2]:=4; a[2,3]:=1; a[2,4]:=0; a[2,5]:=0;

a[3,1]:=0; a[3,2]:=1; a[3,3]:=4; a[3,4]:=1; a[3,5]:=0;

a[4,1]:=0; a[4,2]:=0; a[4,3]:=1; a[4,4]:=4; a[4,5]:=1;

for i:=1 to 3 do a[5,i]:=0; a[5,4]:=1; a[5,5]:=2;

b[1]:=3;  b[2]:=18; b[3]:=24; b[4]:=-6; b[5]:=-15;

  for i:=1 to n do

    for j:=1 to n do

      begin

        if (i=j) then c[i,j]:=0

        else c[i,j]:=-a[i,j]/a[i,i];

      end;

  for i:=1 to n do

  d[i]:=b[i]/a[i,i];

  Mm:=0;

 for i:=1 to n do

   begin

    if (abs(C[i,1])+abs(C[i,2])+abs(c[i,3])+abs(c[i,4]))>Mm

    then Mm:=abs(c[i,1])+abs(c[i,2])+abs(c[i,3])+abs(c[i,4]);

   end;

 norm:=Mm;

     Delta:=(1-norm)*eps/norm;

     for i:=1 to n do

     m[i]:=1;

repeat

for i:=1 to n do

 begin

     m1[i]:=m[i];

 end;

m[1]:=zeidel1(m);

m[2]:=zeidel2(m);

m[3]:=zeidel3(m);

m[4]:=zeidel4(m);

m[5]:=zeidel5(m);

until max(m,m1)<delta;

for i:=1 to 4 do

if ((x0>x[i])or(x0=x[i])) and ((x0<x[i+1])or(x0=x[i+1])) then l:=i;

s1:=(sqr(x[l+1]-x0)*(2*(x0-x[l])+h)*y[l]+sqr(x0-x[l])*(2*(x[l+1]-x0)+h)*y[l+1])/h*h*h;

s2:=(sqr(x[l+1]-x0)*(x0-x[l])*m[l]+sqr(x0-x[l])*(x0-x[l+1])*m[l+1])/h*h;

splin:=s1+s2;

writeln('   spline:');

writeln('S(x)=',splin:1:4);

lagrange(y,x,x0,z);

writeln('   polinom Lagranga:');

writeln('L(x)=',z:2:4);

end.

Ми отримаємо:

А також для перевірки правильності ми реалізуємо програму в Maple:

ПоліномЛагранжа:

> restart;

x:=array(1..5):

y:=array(1..5):

x0:=1.6;

L:=0:

x[1]:=0: x[2]:=1: x[3]:=2: x[4]:=3:  x[5]:=4:

y[1]:=1: y[2]:=2: y[3]:=7: y[4]:=10:  y[5]:=5:

for i from 1 by 1 to 5 do

b:=1:   

a:=1:

for j from 1 by 1 to 5 do

   if (i<>j) then a:=a*(x0-x[j]):

   b:=b*(x[i]-x[j]):

  end if:

  end do:

L:=L+a*y[i]/b:

end do:

lagrange;

L;

> restart;

s:={2*m1+m2=3,m1+4*m2+m3=18,m2+4*m3+m4=60,m3+4*m4+m5=138,m4+2*m5=93}:

R := solve( s ):

m:=array(1..5):

x:=array(1..5):

y:=array(1..5):

m[1]:=-0.2: m[2]:=3.4: m[3]:=4.6: m[4]:=2.2: m[5]:=-19.4:

x[1]:=0: x[2]:=1: x[3]:=2: x[4]:=3:  x[5]:=4:

y[1]:=1: y[2]:=2: y[3]:=7: y[4]:=10:  y[5]:=5:

x0:=1.6;

h:=1:

for i from 1 by 1 to 4 do

if ((x0>x[i])or(x0=x[i])) and ((x0<x[i+1])or(x0=x[i+1])) then l:=i: end if:

spl:=((x[l+1]-x0)^2*(2*(x0-x[l])+h)*y[l]+(x0-x[l])^2*(2*(x[l+1]-x0)+h)*y[l+1])/h*h*h+((x[l+1]-x0)^2*(x0-x[l])*m[l]+(x0-x[l])^2*(x0-x[l+1])*m[l+1])/h*h:

end do:

spline;

spl;

   

Висновок

         При використанні програми ми отримали результат, який при перевірці цих самих даних іншою програмою видав ці самі результати. Ми можемо сказати, що дані котрі нам даються можна обчислити різними способами.  За допомогою різних програм можна отримати ці самі результати.

Література

•  Роганин А.М. Основные формулы высшей математики. – Х.:Торсинг, 2002
•  http://www.intuit.ruldepartment/calculate/........ 
•  Статья «Maple», автор Андрей Топляв
•  Чисельні методи «Методичка»

-

-

4.749700000

1. з курсу Основи філософських знань I
2. Фамилия как в паспорте IVNOV свою фамилию 2
3. останню колонку таблички сильних і неправильних дієслів Префікс ge не отримують- Дієслова з невід
4. В процессе развития каждый сегмент тела приобретает соответствующий спинномозговой нерв
5. Лекция II. Криминологическая характеристика тяжкой насильственной преступности План лекции 1
6. тема нормативного регулирования бухгалтерской отчетности
7.  Государственный бюджет и его структура
8. Письма - Приглашения Приветствия Поздравления
9. минус средние издержки в т
10. фактору; наличие сведений о вирусологическом обследовании; отсутствие взвеси и хлопьев
11. Note down- the speker~s reltionship to the victim e
12. тема Внедрение компьютерной технологииведения бухгалтерского учёта
13. Юриспруденция ПОНЯТИЯ ЦЕЛИ И ЗАДАЧИ
14. Статья- Концепция русской государственности Карамзина.html
15. Кремль9 Приятного чтения Алексей Пиманов Сталин
16. Задержка мочи острая
17. Основні поняття та сутність інформаційноаналітичного забезпечення безпеки підприємства
18. ru Все книги автора Эта же книга в других форматах Приятного чтения Джон Рональд Руэл Толкин
19. Верблюды
20.  САВЕЛЬЕВА Анна Савельева юрисконсульт

Материалы собраны группой SamZan и находятся в свободном доступе