Кіріспе
Интерполяция түрі
Сандық талдауда полиномиялық интерполяция – берілген екі айнымалы деректер жиынын, дерек жиынының нүктелері арқылы өтетін ең төменгі мүмкін дәрежедегі полином арқылы интерполяциялау. Егер n + 1 дерек нүктелерінің жиыны болса, және екі нүкте бірдей болмаса, онда полиномдық функция деректерді интерполяциялайды, егер әрбір үшін . Мұндай полином әрқашан бірегей болады және көбінесе Лагранж полиномдары және Ньютон полиномдары деп аталатын екі нақты формуламен беріледі.
In numerical analysis, polynomial interpolation is the interpolation of a given bivariate data set by the polynomial of lowest possible degree that passes through the points of the dataset. Given a set of n + 1 data points , with no two the same, a polynomial function is said to interpolate the data if for each
There is always a unique such polynomial, commonly given by two explicit formulas, the Lagrange polynomials and Newton polynomials.
Қолданбалар
Интерполяциялық полиномиалдар бастапқыда табиғи логарифм және тригонометриялық функциялар сияқты маңызды трансценденттік функциялардың мәндерін жуықтау үшін қолданылған. Бірнеше дәл есептелген дерек нүктесінен бастап, сәйкес интерполяциялық полиномиал функцияны кездейсоқ жақын нүктеде жуықтайды. Полиномиалдық интерполяция сандық квадраттау (Симпсон ережесі) және сандық қарапайым дифференциалдық теңдеулер (мультисеткалық әдістер) алгоритмдерінің негізін құрайды. Компьютерлік графикада полиномиалдар бірнеше берілген нүктелерді, мысалы, типографиядағы әріптердің пішіндерін сипаттайтын күрделі жазықтық қисықтарды жуықтау үшін пайдаланылуы мүмкін. Бұл әдетте интерполяциялық полиномиалдардың (белгіленген тангенстермен және белгіленген нүктелермен) қарапайым жалпылануы болып табылатын Безиер қисықтарымен жасалады. Сандық талдауда полиномиалдық интерполяция субквадраттық көбейту мен квадраттауды орындау үшін маңызды, мысалы, Каратсуба көбейтуі және Тум-Кук көбейтуі, онда өнім полиномиалдың нүктелері арқылы интерполяция қажетті нақты өнімді береді. Мысалы, a = f(x) = a0x0 + a1x1 + ··· және b = g(x) = b0x0 + b1x1 + ··· берілген жағдайда, ab көбейтіндісі W(x) = f(x)g(x) функциясының нақты мәні болып табылады. W(x) бойымен x-тің кіші мәндеріндегі нүктелерді оңай табуға болады, ал осы нүктелерге негізделген интерполяция W(x) функциясының мүшелерін және нақты ab көбейтіндісін береді. Каратсуба көбейтуінде айтылғандай, бұл әдіс тіпті шағын көлемді деректер үшін де, әсіресе параллель аппараттық құралдарда квадраттық көбейтуден едәуір жылдам. Компьютерлік ғылымда полиномиалдық интерполяция көп тарапты қауіпсіз есептеулер және құпия бөлісу алгоритмдеріне де алып келеді.
Қорытынды
Егер – ең көп дегенде -дәрежелі полиномиал болса, онда –нің –нің ерекше нүктелеріндегі интерполяциялық полиномиалы – өзі болады.
Вандермонд емес алгоритмдер
n дәрежелі көпмүшелердің P(n) векторлық кеңістігінде p(x) интерполяциялық көпмүшесін табу үшін, P(n) үшін стандартты мономиалды негізді қолданып, Гаусс жою арқылы Вандермонд матрицасын инверттеуге болады, бұл O(n³) операциялық есептеу шығындарын тудырады. Бұл алгоритмді жақсарту үшін P(n) үшін ыңғайлы негіз коэффициенттерді есептеуді жеңілдетеді, оларды кейін мономиалды негізге қайта аудару қажет. Бір әдіс – интерполяциялық көпмүшені Ньютон түрінде (яғни Ньютон негізін пайдалану) жазу және коэффициенттерді құру үшін бөлінген айырмашылықтар әдісін қолдану, мысалы Невилл алгоритмі. Бұл O(n²) операциялық шығынға ие. Сонымен қатар, егер деректер жиынтығына қосымша нүкте қосылса, сізге тек O(n) қосымша жұмыс қажет, ал басқа әдістер үшін есептеуді толығымен қайта жасау қажет болады. p(x) көпмүшесінің коэффициенттерін есептеу мақсаты болмағанда, тек бастапқы деректер жиынтығына жатпайтын x = a нүктесінде p(a) мәнін есептеу үшін басқа әдіс артықшылықты болады. Лагранж түрі p(a) мәнін O(n²) күрделілігімен есептейді. Бернштейн түрі Бернштейннің Вейерштрасс жуықтау теоремасының конструктивті дәлелінде қолданылды және Безиер қисықтары түрінде компьютерлік графикада маңызды рөл атқарады.
Интерполяциялық қате: Лагранж қалдықтар формуласы
Функция f-ты x0, …, xn түйіндерінде n дәрежелі полиномиалмен интерполяциялағанда, қателік мына түрде шығады:
where is the (n+1)st divided difference of the data points Furthermore, there is a Lagrange remainder form of the error, for a function f which is n + 1 times continuously differentiable on a closed interval , and a polynomial of degree at most n that interpolates f at n + 1 distinct points For each there exists such that
This error bound suggests choosing the interpolation points xi to minimize the product , which is achieved by the Chebyshev nodes.
мұндағы – деректер нүктелерінің (n+1)-ші бөлінген айырмасы. Сонымен қатар, жабық аралықта n+1 рет үздіксіз дифференциалданатын және n+1 түрлі нүктеде f функциясын интерполяциялайтын, ең көп n дәрежелі полиномиал үшін Лагранж қалдық түріндегі қателік бар. Әрбір үшін, осындай бар, оған:
where is the (n+1)st divided difference of the data points Furthermore, there is a Lagrange remainder form of the error, for a function f which is n + 1 times continuously differentiable on a closed interval , and a polynomial of degree at most n that interpolates f at n + 1 distinct points For each there exists such that
This error bound suggests choosing the interpolation points xi to minimize the product , which is achieved by the Chebyshev nodes.
теңдігі орындалады.
where is the (n+1)st divided difference of the data points Furthermore, there is a Lagrange remainder form of the error, for a function f which is n + 1 times continuously differentiable on a closed interval , and a polynomial of degree at most n that interpolates f at n + 1 distinct points For each there exists such that
This error bound suggests choosing the interpolation points xi to minimize the product , which is achieved by the Chebyshev nodes.
Бұл қателік шегі, көбейтіндіні азайту үшін интерполяциялық нүктелерді таңдауды ұсынады, және бұл Чебышев түйіндері арқылы қол жеткізіледі.
where is the (n+1)st divided difference of the data points Furthermore, there is a Lagrange remainder form of the error, for a function f which is n + 1 times continuously differentiable on a closed interval , and a polynomial of degree at most n that interpolates f at n + 1 distinct points For each there exists such that
This error bound suggests choosing the interpolation points xi to minimize the product , which is achieved by the Chebyshev nodes.
Лебегтік тұрақтылар
Біз интерполяция түйіндерін x0, ..., xn және барлық интерполяция түйіндерін қамтитын [a, b] интервалын бекітеміз. Интерполяция процесі f функциясын p көпмүшеге бейнелейді. Бұл [a, b] аралығындағы барлық үздіксіз функциялар кеңістігі C([a, b]) үшін X бейнелеуін анықтайды, ол өзін-өзіне бейнелейді. X бейнелеуі сызықты және ол n дәрежесі немесе одан төменгі көпмүшелердің кіші кеңістігіне проекция болып табылады. Лебег тұрақтысы L, X операторының нормасы ретінде анықталады. Бізде бар (Лебег леммасының ерекше жағдайы):
Басқаша айтқанда, интерполяциялық көпмүше ең жақсы жақындаудан (L + 1) факторға дейін нашарлайды. Бұл L-ді кіші қылатын интерполяция түйіндері жиынтығын іздеуге ұсыныс береді. Атап айтқанда, Чебышев түйіндері үшін:
Сонымен, Чебышев түйіндері полиномдық интерполяция үшін өте жақсы таңдау екеніне қайтадан қорытындылаймыз, себебі тең қашықтықтағы түйіндер үшін n-нің өсуі экспоненциалды. Дегенмен, бұл түйіндер ең жақсысы емес.
Қарым-қатынас ұғымдары
Рундж құбылысы n-нің жоғары мәндерінде интерполяциялық полиномның дерек нүктелері арасында күрт қозғалыстар тудыруы мүмкін екенін көрсетеді. Бұл мәселе көбінесе сплайн интерполяциясын қолдану арқылы шешіледі. Мұнда интерполянт полином емес, бірақ сплайн: төмен дәрежелі бірнеше полиномдардың тізбегі. Кезеңдік функцияларды гармоникалық функциялармен интерполяциялау Фурье түрлендіруі арқылы жүзеге асырылады. Бұл гармоникалық базалық функциялары бар полиномдық интерполяцияның бір түрі ретінде қарастырылуы мүмкін, тригонометриялық интерполяция және тригонометриялық полиномдарды қараңыз. Гермит интерполяциясы мәселелері – бұл түйіндердегі полином p-нің мәндері ғана емес, сонымен қатар белгілі бір ретке дейінгі барлық туындылар берілген жағдайлар. Бұл бір мезгілдегі көпмүшелік сәйкестіктер жүйесіне тең болып шығады және оны полиномдар үшін қытайлық қалдық теоремасы арқылы шешуге болады. Биркгофф интерполяциясы – бұл 0-ден k-ға дейінгі барлық реттер міндетті емес, тек кейбір реттердің туындылары белгіленген одан әрі жалпылау. Дифференциалдық және интегралдық теңдеулерді шешуге арналған коллокациялық әдістер полиномдық интерполяцияға негізделген. Рационалды функцияларды модельдеу техникасы – полиномдық функциялардың қатынастарын қарастыратын жалпылау. Соңында, жоғары өлшемдер үшін көпөлшемді интерполяция.
Collocation methods for the solution of differential and integral equations are based on polynomial interpolation. The technique of rational function modeling is a generalization that considers ratios of polynomial functions. At last, multivariate interpolation for higher dimensions.