Интерполация полином каноничен

Интерполация - приближава една функция в друга функция.

От самото начало, бих искал да отбележа, че ние правим интерполация функции. вместо възли. Разбира се, интерполация се извършва в определен брой точки, но ние ги изберете сами.

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

Полином в каноничен формата

Известно е, че всеки непрекъснат върху интервала [а, Ь] е функция (X) може да бъде добре приблизително от полином Pn (х). Ние следното теорема (Вайерщрас): За всеки> 0 съществува полином Pn (х) степента, така че

Както притискащото функцията ще избере полином от степен н в каноничен вид:

Коефициентите на полинома се определят от условията Лагранжевите, като се вземе предвид, че предишната експресията дава система от линейни алгебрични уравнения с п +1 неизвестни:

Ние означаваме системата уравнения звездичка (*) и да го пренапише, както следва:

или в матрица форма: = \ mathbf "> където" > - вектор колона. съдържащ неизвестни коефициенти "> - колона векторни състои от стойностите на таблицата на функция, и матрица" > е формата:

Системата от линейни алгебрични уравнения (*) за неизвестни има уникален разтвор ако детерминанта "> не е нула.

Детерминанта на матрицата "> се нарича Vandermonde детерминанта, може да се изчисли по следната формула:

Броят на интерполация полином единици трябва да бъде един повече от неговата степен. Това става ясно от интуитивни съображения: 2 точки може да побере един ред през 3 - единичен парабола и т.н. Но полином може да получи и по-малко. Т.е. ако 3-те точки лежат на една линия, а след това да ги премине през един единствен първа степен полином (но това не противоречи на всичко: коефициент на най-висока степен е нула).

С достатъчно лекота на прилагане на метода той има основен недостатък: Броят на състоянието на матрицата расте бързо с броя на интерполация точки, които могат да бъдат показани на следната графика

Поради болен инсталация на матрицата се препоръчва да се използват и други техники за интерполация (например, Lagrange интерполация полином). Важно е да се осъзнае, че в теоретичен те използват различни методи водят до същия резултат, т.е. ние получаваме една и съща полином.

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

Метод за изчисляване на полином в точка

За да се изобразяват графично притискащото полином, е необходимо да се изчисли стойността му в няколко точки. Това може да стане по следните начини.

Първият метод. Можете да се изчисли стойността на А1 х и пъти с a0. На следващо място, намери а2 х 2. определя резултата, и така нататък. По този начин, етапът на й-то се изчислява стойност ай х J и се добавя към вече изчислява сума.

Изчисляване на стойността на ай х й й изисква операциите умножение. Т.е. за да се изчисли полином на изисква дадена точка (1 + 2 +. + п) = N (N + 1) / 2 умножения и п допълнения. Общо операции в този случай: ОР1 = п (п + 1) / 2 + п.

Вторият метод. Полином може също така лесно да се изчислява с помощта на така наречените Horner схема:

За да се изчисли стойността на вътрешните скоби х + ан-1 изисква един умножение операция и една допълнение операция. За изчисляване на стойностите в следните скобите (х + с-1) х + един-два отново изисква един умножение операция и една операция допълнение, тъй х + един-1 е изчислен и т.н.

След това, в този метод, изчисляване на Pn (х) изисква п умножения и п добавки, т.е. изчислителната сложност OP2 = п + п = 2n. Ясно е, че OP2 <

метод за анализ

сложността на изчисленията

Сложността Оценка функция интерполация се състои от броя на операциите за решаване на система от линейни алгебрични уравнения (SLAE) и намиране на стойността на полином в точка.

Сложността на решаване на линеен, например, методът Гаус за размер п хп матрица. 2n 3/3, т.е. О (п 3).

За да намерите полинома в даден момент изисква н умножения и н допълнения. В резултат на метода на сложност: О (п 3).

интерполация грешка

Да предположим, че интервалът на интерполация [а, Ь] функция F на (х) п пъти непрекъснато диференцируема. Интерполация грешка се състои от грешка на грешките метода и закръгляване.

сближаване функция грешка е (х) полином на п-тия интерполация степен Pn (х) в точка х се определя от разликата: Rn (х) = F (х) - Pn (х).

Точност Rn (х) се определя от следното равенство:

Тук (\ XI) "> - производно на (п + 1) -ти функция цел е (х) в определен момент се определя като функция

Ако максималната стойност на производно F п + 1 (х) е "> за оценка на интерполация грешка следва:

При изпълнението на този метод на компютър грешка En интерполация (х), ние приемаме, максималното отклонение от оригиналния полином функция в избрания интервал:

Избор на интерполация точки

Ясно е, че изборът на компоненти на интерполира функцията пряко влияе колко добре ще е полином приближение.

Представяме следното определение. Chebyshev полином е полином на формата

Той е известен (вж. Препратката на литературата), че ако x0 на интерполация точки. x1. хп са корените на Chebyshev полином от степен п + 1. Тя получава стойността на най-малката възможна стойност, в сравнение с който и да е друг набор от интерполация точки за този.

Очевидно е, че в случай к = 1 функцията Т1 (х). Всъщност, първа степен полином като Т1 (х) = COS (ARccOS х) = х.

В случай на к = 2 Т2 (х) е полином от втора степен. Лесно е да се провери. Използвайте известен тригонометрични идентичност: cos2θ = 2cos²θ - 1, удар θ = ARccOS х.

След това се получава следната зависимост: T2 (х) = 2x² - 1.

Използване тригонометрични идентичности COS (к + 1) θ = 2cosθ coskθ - COS (к - 1) лесно да се покаже, че съотношението на rekkurentnoe полиноми на чебишов:

С това съотношение може да се получи от формулата за полиномите Chebyshev от всяка степен.

Полиноми на чебишов корени nahodyatya лесно от уравнението: Tk (х) = COS (к ARccOS х) = 0. установят, че уравнението е к различни корени разположени върху интервала [-1,1], и което трябва да бъде избрано като възли интерполация.

Лесно е да се види, че корените на [-1,1] са разположени симетрично и равномерно - колкото по-близо до ръба на сегмента, корените са разположени плътно. Максималната стойност на Chebyshev полином на модула е равно на 1 и се постига при точките

Ако приемем, че за коефициент на най-висока степен на полином ωk (х) е равно на 1,

Известно е, че за всеки полином пк (х) на степен к от коефициента равна на единство на най-високо производно неравенството т.е. Chebyshev полиноми са полиноми, най-малкото отклонение от нулата.

Computing експеримент

За да изпълни задачата, програма в C ++ е написано, че дадена функция носи каноничната си полином. Разбира се, трябва да укажете възли, чрез които ще се проведат на полином, както и стойността на функцията на тези възли.

След това, линеен алгебрични система уравнение се решава чрез Гаус. Изходът е коефициентите за полином сближаване и грешката.

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

Пример: интерполация синус

Опитват да интерполира функция у = грях (х) в интервала [1, 8,5]. Ние избираме точките интерполация:

Получената полином интерполация картирани на фигурата (синьо показва графика на у = грях (х), червено - интерполация полиноми)

Интерполация грешка в този случай: 0.1534

Нека да видим какво се случва, ако изберем единни стоящи единици за една и съща функция на същия интервал.

На интервала [3, 6] подход, без съмнение, е най-добрият. Въпреки това, разпръснати в много големи маржове. интерполация грешка: 2.3466.

И накрая, ние избираме точките интерполация в съответствие с алгоритъма Chebyshev. Ние ги получите по следната формула (просто да направите промяната на променлива):

В този случай, [а, Ь] - интервала [1, 8,5], у = cosx. п + 1 - броят на възли.

Остава открит въпросът колко единици от които да избирате.

Ако стойността н е по-малко от 3 грешки приближение, получена през 10.6626.
Когато п = 4 по-добро приближение (грешка, равна на 1,0111)
когато п = 5. сближаване грешка 0.2797

Графика функции, когато п = 4, е както следва:

Когато п = 7 грешка приближение се най-малката от стойностите, получени по-рано (за даден интервал): 0,0181. Графика синус (посочено в синьо) и полином сближаване (посочено в червено) е показано в следващата таблица:

Какво е интересно, ако един и същ брой възли, за да ги изберете от интервала [1, 8], грешката на сближаване е още по-малък. 0.0124. Графиката в този случай е, както следва:

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

приближени грешки ще нарасне само с броя на възлите.

Както можете да видите, най-доброто сближаване се получава чрез избора на възлите на метод Chebyshev. Въпреки това, препоръките на която броят на възлите е оптимално, не - това се определя само от експеримент.

препоръки програмист

Програмата е написана на C ++, използвайки UBlas линейна алгебра библиотека, която е част от колекцията на Boost библиотека. Изтеглете изходния код тук [2.55Kb].

предварителните тинктури

За да използвате програмата, трябва да направите следното: 1. Решете на функцията, която ще се интерполира 2. Създайте текстов файл (например, vec.txt), на първия ред се поставя чрез възли празнина интерполация, а вторият - стойността на избраната функция в тези възли.

Например, функция у = грях (х):

3. В файла .cpp програма функция двойно F (двойно х), вместо стойност регистър низ връщане върнат от оригиналната функция. Например, за функция у = грях (х):

4. INT Функцията главната () на изходния код, присвоен на променливата Чар * flname пътека до файла с въвеждане на данни. В нашия случай, знак * flname = "vec.txt";

С помощта на програмата

Програмата предвижда следните основни функции:

двойно е (двойна х). разкритието на който е дадено по-горе
вътр натоварване (Чар * името на файла, вектор х, вектор у) - зареждане на интерполация възли в променливата х и стойността на функцията на тези възли към променлива у текстов файл името на файла на. В случай на успешно зареждане на данни от функцията файл връща 0.
невалидни matrix2diag (матрица А, вектор у) - матрица води до триъгълна форма. Y - дясната колона (също се променя с матрица А).
невалидни SolveSystem (матрица А, вектор у, вектор коеф) - реши SLAE (А - триъгълна матрица, у - страничен колона дясната коеф - този вектор се съхранява в разтвор SLAE)
двойно errapprox (вектор коеф, двойно по-, двойно б, двойно з) - извежда грешка полином сближаване на оригиналната функция.

Функцията вход служи за следните параметри:

- вектор коеф - вектор интерполация полином коефициенти, която се получава в хода на решаване на линейни
- удвояване на двойно б - граница интерполация интервал [а, Ь]
- двойно ч - етап че "работи" интервал [а, Ь]

Int outpolyn (овъгляване ** файла, вектор коеф) - спестява коефициентите на полином коеф в името на файла на файла. В случай на успешно опазване връща функцията '0'.

След стартиране на програмата на екрана се появи коефициентите на полином интерполация и приближение грешката.

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

Отбелязва се също, че изборът на интерполацията възли в пряка зависимост от качеството на интерполация. Минималната допустима грешка при интерполация се постига, когато "Chebyshev" възли.