Лекция 3 Интерполация и екстраполация. Апроксимация и пресмятане на функции



Дата14.01.2018
Размер91.83 Kb.
ТипЛекция
Лекция 3

Интерполация и екстраполация. Апроксимация и пресмятане на функции.



1. Постановка на задачата. Нека са зададени n на брой точки yi(xi), които могат да се разглеждат като стойности на функцията y за определени стойности на аргумента xi i=1…n. Възниква въпросът за определяне на стойностите на функцията за стойности на аргумента различни от точките xi. Когато се търсят стойности на функцията у за х лежащи вътре в интервала определен от точките xi (т.е. ximinimax) говорим за интерполация, когато х е извън този интервал говорим за екстраполация. По-натам ще говорим само за интерполация. Много от казаното е валидно и за екстраполацията, но с уговорката, че екстраполацията крие по-голям риск от грешки.

Задачата за интерполация възниква като резултат от няколко основни проблема. На първо място точките yi(xi) могат да са резултат от експеримент или взети от някаква таблица със стойности. В такъв случай възниква естественото желание да се определят стойностите на функцията y(x) за стойности на аргумента различни от табличните. Вторият проблем свързан с интерполацията е нуждата от бързо пресмятане на функции чрез други функции. В този случай говорим за апроксимация на функции чрез интерполация. Накрая, интерполацията, и особено интерполационните полиноми, служат като основа за много от числените методи, например числено диференциране и сумиране, числено решаване на диференциални уравнения и др.

Първият въпрос, който трябва да се реши е какъв да е вида на функцията, с която интерполираме. Обикновено за тази цел се използват линейни комбинации от краен брой еднотипни функции, които лесно се пресмятат. Най-често се срещат:
- интерполация с полиноми:

P(x)=anxn+an-1xn-1+…..+a1x+a0


- интерполация с тригонометрични полиноми:

()Σ=++=n1kkk0kxsinbkxcosa2a)x(T


За да бъде тази интерполация ефективна трябва да има бърз алгоритъм за пресмятане на тригонометрични функции. В съвременните компилатори има вградени подпрограми, които ефективно пресмятат тези функции с максимална възможна точност.
- интерполация с рационални функции:

011n1nnn011n1nnnbxb....xbxbaxa...xaxa)x(R++++++++=−−−−


- експоненциални полиноми:

xnx2x1n21ea.....eaea)x(Eααα++=.


Казаното за тригонометричните полиноми важи и за експоненциалните.

От посочените функции за интерполация най-често се използва полиномиалната апроксимация, защото полиномите се пресмятат най-лесно и теорията е най-добре развита. Все пак, в редица случаи тази апроксимация не е най-удобната. Например зависимостта на много физични процеси от времето е експоненциална или близка до експоненциална и в този случай експоненциалната апроксимация с малко членове дава много добри резултати. Интерполацията с тригонометрични полиноми е подходяща за периодични функции, а интерполация с рационална функция е подходяща в много важни за практиката случаи.



2. Пресмятане на полиноми. От казаното до тук е ясно, че е важно да се намери начин за оптимално пресмятане на полиноми. Нека е даден полиномът:

P(x)=anxn+an-1xn-1+…..+a1x+a0. (1)

1

Най-бързият метод, без допълнително пренареждане на събираемите, носи името на Хорнер, въпреки че е бил използван за първи път от Нютон. Полиномът (1) може да се запише по следния начин:



()()()()....xaa.....xaxaxa)x(Pn1n210++++=−.

За пресмятане на полином от n-та степен по правилото на Хорнер са необходими n умножения и n събирания. Правилото на Хорнер е оптималният вариант за пресмятане на полином без значителни изчисления в процеса на групиране. Освен това този метод лесно се програмира. На Фортран например пресмятането се свежда до:

P=A(n)

DO i=1,n



P=P*x+A(n-i)

END DO


3. Полиномиална интерполация. Нека са дадени стойностите на функцията y(x) за n+1 точки, т.е познати са стойностите yi за xi стойности на аргумента, i=1..n+1. В задачата за полиномиална интерполация се изисква да се намери полином от n-та степен Pn(x), такъв, че Pn(xi)=yi. Нека разпишем това условие по-подробно:

anx1n+an-1x1n-1+……….+a1x1+a0=y1

anx2n+an-1x2n-1+……….+a1x2+a0=y2

……………………………………………….. (2)

anxn+1n+an-1xn+1n-1+…..+a1xn+1+a0=yn+1

Системата от n+1 уравнения (2) е линейна спрямо неизвестните n+1 на брой коефициенти ai (i=0..n). Известно е, че една линейна система е определена т.е има едно единствено решение когато детерминантата й е различна от нула. След пренареждане на членовете на уравненията (2) се получава следната детерминанта:

n1n21n11nn22212n12111x..xx1..................x..xx1x..xx1V+++= (3)

Детерминантата V се нарича детерминанта на Вандермонд и се показва, че:

(4). Π=>−=n1iijij)xx(V

От (4) се вижда, че когато точките xi са различни V≠0 и системата (2) има едно единствено решение за коефициентите ai (i=0..n), с което интерполационният полином е намерен.

4. Полиноми на Лагранж. В предната точка беше показано, че през всеки n+1 различни стойности на аргумента xi, за които са известни стойностите на функцията y(xi)=yi може да се прекара полином Pn(x) от n-та степен. Записването на тези полиноми може да стане под различна форма. Една от тях e намирането на коефициентите ai чрез решаване на системата линейни уравнения (2). Друг възможен подход води до т.н. полиноми на Лагранж. Важно е да се подчертае, че полиномите на Лагранж са същите, както получените от (2), но записани по определен начин.

2

Да разгледаме полинома:



)xx)......(xx)(xx)...(xx)(xx()x(1n1i1i21i++−−−−−−=π, (5)

който се получава от умножаването на всички членове (x-xk) освен (x-xi). Тогава . От друга страна ik,0)x(ki≠=π0)x(ii≠π. Нека сега разгледаме полинома:

Σ+=ππ=1n1iiiiin)x()x(y)x(P. (6)

За всяка точка на аргумента xi, (i=1..n+1) всички членове на сумата (6) са нула освен i-тия член, който е равен на yi. За доказване на последното твърдение нека да разпишем този член по-подробно:

)xx)......(xx)(xx)...(xx)(xx()xx)......(xx)(xx)...(xx)(xx(y1ni1ii1ii2i1i1n1i1i21i++−++−−−−−−−−−−− (7)

От подробния запис (7) се вижда, че при x=xi знаменателят и числителят са равни, те се съкращават и остава множителят yi. От друга страна всеки от полиномите πi е от n-та степен, следователно и сумата им е полином от същата степен. Получихме, че един полином от n-та степен минава през n+1 точки y(xi)=yi., което беше задачата. Доказателството, че това решение е единствено е тривиално. Наистина, нека освен Pn(x) съществува и друг полином от степен n Gn(x), който изпълнява същите условия: Gn(xi)=yi; i=1..n+1. Тогава стойностите на полиномите Pn и Gn от степен n съвпадат в n+1 точки. Съществува теорема, която гласи:



Ако полиномите f(x) и g(x), от степен не по-голяма от n, имат еднакви стойности в повече от n различни точки на аргумента х то f(x)≡g(x).

Съгласно тази теорема Pn и Gn съвпадат.

Интерполационният полином записан във вида (6) носи името интерполационен полином на Лагранж. Полиномът на Лагранж се използва често при интерполация, защото има проста форма и е лесен за разбиране и програмиране. В същото време грешките от закръгляне при този начин на пресмятане не са минимални. Съществуват други начини за пресмятане, които минимизират тези грешки.

Апроксимация на функции с полиноми При пресмятанията дотук смятахме, че стойностите yi в точките на аргумента xi са или таблични стойности или получени от експеримент и ние не познаваме стойностите на функцията у за стойности различни от xi. В този случай полиномиалната интерполация е един начин да намерим тези стойности.

Подобен проблем възниква и когато искаме да апроксимираме дадена функция (например sin(x)) с полином от n степен, така че стойностите на полинома и функцията съвпадат в n+1 точки. В този случай мотивът за интерполацията е бързото пресмятане на стойностите на функцията и говорим за апроксимация. В случая ще разгледаме полиномиална апроксимация. По същество задачата е същата: да се намери полином от n-та, който минава през n+1 точки. Разликата е, че можем да подберем точките xi, в които да пресметнем функцията, която ще апроксимираме. Въпросът за избора на тези точки е много съществен, тъй като оптималният им избор помага да минимизираме грешката при апроксимация, но излиза извън рамките на курса и няма да го разглеждаме.

Когато апроксимираме дадена функция f(x) (приемаме, че тя е непрекъсната и с необходимия брой производни) с полинома Pn(x) възниква въпросът за грешката, която правим. За да я определим да запишем по подходящ начин разликата между тях:

)x(K)xx).....(xx)(xx()x(P)x(f1n21n+−−−=−, (8)

където x1..xn+1 са точките, в които функцията и апроксимационния полином съвпадат. От (8) се вижда, че действително в тези точки разликата е нула. К(х) е подходяща функция,

3

която искаме да определим. Да фиксираме дадена стойност на аргумента х* вътре в интервала определен от интерполационните точки и за тази стойност да запишем (8) във вида:



0*)x(K)x*x).....(x*x)(x*x(*)x(P*)x(f1n21n=−−−−−+ (9)

Сега да диференцираме функцията:

*)x(K)xx).....(xx)(xx()x(P)x(f)x(1n21n+−−−−−=Φ (10)

n+1 пъти. Pn(x) е полином от n-та степен, следователно Pn(x)(n+1) =0. От своя страна К(х*) е константа, тъй като х* е фиксирано, а при разкриване на скобите на множителите пред него се вижда, че коефициентът на получения полином пред най-голяма n+1 степен е единица. Резултатът от (n+1) кратното диференциране на този полином е (n+1)!. Следователно:

(11) *)x(K)!1n()x(f)x()1n()1n(+−=Φ++

Както се вижда от (9), (10) и условието за интерполация 1n..1i),x(P)x(fini+== Φ(x) се нулира за x=x*,x1,x2…xn+1, или общо n+2 пъти. От теоремата на Рол за анулиране на производната следва, че Φ(x)΄ се нулира поне n+1 пъти в интервала зададен от точките x1…xn+1. Продължавайки по същия начин ще получим, че Φ(x)(n+1) се нулира поне в една точка. Така намираме, че в посочения интервал съществува точка x такава ,че Φ(x)(n+1)=0 и съгласно (11) можем да запишем:

)!1n()x(f*)x(K)1n(+=+. (12)

Точката х* беше избрана произволно в зададения интервал, следователно вместо (12) можем да запишем:

)!1n()x(f)x(K)1n(+=+ (13)

Разбира се x зависи от избора на х, но за нас е достатъчно да знаем, че x лежи вътре в интервала определен от точките x1…xn+1. Замествайки (13) в (9) получаваме:

)!1n()x(f)xx).....(xx)(xx()x(P)x(f)1n(1n21n+−−−=−++ (14)

Изразът (14) е търсената абсолютна грешка при интерполация с полиноми. Тази грешка зависи от x непосредствено и чрез x. За да я оценим отгоре избираме последната стойност така, че y(n+1)(x) да има максимална стойност в разглеждания интервал.

От (14) се вижда, че когато максималната стойност на производната остава ограничена с увеличаването на n (например при f(x)=sin(x)) повишаването на степента на полинома води до по-добра апроксимация, тъй като знаменателят бързо расте. Съществуват обаче функции, чиито производни растат неограничено при многократно диференциране, и при които увеличаването на степента на полинома не води до намаляване на грешката. Съществуват добре познати функции, при които увеличаването на степента на полинома води до силно нарастване на грешката за някои стойности на х в определения от интерполационните точки интервал. В самите интерполационни точки, разбира се, грешката е нула, което веднага се вижда от (14).

Още за апроксимацията на криви. При апроксимацията на една функция f досега изисквахме тя да съвпада с приближаващата функция f~(полином например) в определен брой точки, но никакви изисквания не бяха поставени за стойността на f~ в останалите точки на аргумента от дадения интервал. В резултат може да се окаже, че за определени стойности на аргумента грешката е много голяма. Възможен е и друг критерий за апроксимация, който се нарича метричен [1], при който се изисква максималното

4

отклонение между приближаваната и приближаващата функции да не надвишава дадена стойност ε в целия интервал [a,b], в който приближението е валидно:



ε<−∈)x(f~)x(fmax]b,a[x (15)

Този критерий се използва най-често при апроксимацията на функции. Едно приближение на sin(x) основано на метричен критерий е:

, )x(x00761.0x16605.0x)xsin(53ε++−=2x0π≤≤, (16)

и 410.2)x(−≤ε. Тук х е в радиани.

Това приближение е по-добро отколкото приближението на sin(x) с първите три члена на реда на Тейлър около нулата, както е показано на Фиг.1

747678808284868890920,9600,9650,9700,9750,9800,9850,9900,9951,0001,0051,010 sin(x)angle(deg)

Фиг.1

На Фиг.1 са дадени “истинската” стойност на sin(x), пресметната със стандартната подпрограма на Matlab (черна непрекъсната линия), стойностите пресметнати с (16) (червени точки) и стойностите пресметнати като се използват само първите три члена от разложението на Тейлър около нулата (прекъсната линия):



!5x!3xx)xsin(53+−≈ . (17)

Както се вижда в този мащаб кривата пресметната с (16) не може да се различи от “истинската” стойност. При същото количество пресмятания приближението (17) дава грешки два порядъка по-големи от (16) при ъгли близки до 2xπ=.



Литература
1. Б. Сендов, В. Попов Числени методи (първа част) София, Университетско издателство 1996 г.
2. Дж. Форсайт, М. Малкълм, К. Молър Компютърни методи за математични пресмятания, София, Наука и изкуство 1985.
3. R. Hamming Numerical methods for scientists and engineers, Dover, New York, 1962
5

http://elearning-phys.uni-sofia.bg/~tvel/lecture_3.pdf
http://209.85.129.132/search?q=cache:atusArE4GBgJ:math.uctm.edu/~angelova/na/node26.html+%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0+%D0%BD%D0%B0+%D0%BB%D0%B0%D0%B3%D1%80%D0%B0%D0%BD%D0%B6+%D0%B7%D0%B0+%D0%B0%D0%BF%D1%80%D0%BE%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D1%86%D0%B8%D1%8F&cd=2&hl=bg&ct=clnk&gl=bg&client=firefox-a

Интерполационни полиноми на Лагранж и Нютон с разделени разлики


Дефиниция 5.2   Нека функцията е дефинирана и ограничена в интервала и са известни нейните функционни стойности в различни точки (възли) от този интервал. Алгабричният полином се нарича интерполационен полином за функцията , построен по възлите , ако е полином от степен по-малка или равна на и , .

Единственост на интерполационния полином се дава със следната теорема.

Теорема 5.2   Нека са изпълнени следните условия:
1. Дадени са различни точки в , като .
2. Известни са стойностите , ,
на функция в тези точки.
3. е полином най-много от степен ,
за който



(виж фигура 5.2).
Тогава интерполационният полином е единствен.




Figure: Интерполационен полином

<<4746>>

Subsections



  • Формула на Лагранж

  • Формула на Нютон с разделени разлики

Лагранж:


Нютон





Каталог: 2010
2010 -> Ноември, 2010 Г. Зад Кое е неизвестното число в равенството: (420 Х): 3=310 а) 55 б) 66 в) 85 г) 504 За
2010 -> Регионален инспекторат по образованието – бургас съюз на математиците в българия – секция бургас дванадесето състезание по математика
2010 -> Януари – 2010 тест зад Резултатът от пресмятане на израза А. В, където
2010 -> Библиографски опис на публикациите, свързани със славянските литератури в списание „Панорама” /1980 – 2011
2010 -> Специалисти от отдел кнос, Дирекция „Здравен Контрол при риокоз русе, извършиха проверки в обектите за съхранение и продажба на лекарствени продукти за хуманната медицина на територията на град Русе
2010 -> 7 клас отговори на теста
2010 -> Конкурс за научно звание „професор" по научна специалност 05. 02. 18 „Икономика и управление" (Стопанска логистика) при унсс, обявен в дв бр. 4/ 15. 01. 2010
2010 -> Код на училище Име на училище


Поделитесь с Вашими друзьями:




База данных защищена авторским правом ©obuch.info 2020
отнасят до администрацията

    Начална страница