Interpolarea canonic polinomul

Interpolarea - se apropie de o funcție la o altă funcție.

De la început, aș dori să rețineți că facem funcții de interpolare. mai degrabă decât noduri. Desigur, interpolarea este efectuată într-un număr finit de puncte, dar le alege pe noi înșine.

In acest studiu, problema este studiată funcția de interpolare a unui singur polinom canonic polinomial variabilă, care trebuie luat în considerare este precizia de aproximare, și modul în care, prin varierea nodurile prin care trec polinomului de interpolare pentru a obține o precizie maximă.

Polinomului sub forma canonică

Este cunoscut faptul că orice continua pe intervalul [a, b] f funcție (x) poate fi bine aproximată printr-un polinom Pn (x). Am următoarea teoremă (Weierstrass): Pentru orice> 0 există un polinom Pn (x), în măsura în care astfel de

Deoarece funcția aproximându va alege un polinom de gradul n în forma canonică:

Coeficienții polinomului sunt determinate de condițiile Lagrange, ținând cont de faptul că expresia anterioară oferă un sistem de ecuații algebrice liniare cu n +1 necunoscutele:

Notăm sistemul de ecuații un asterisc (*) și rescrie-l, după cum urmează:

sau sub formă de matrice: = \ mathbf "> unde" > - un vector coloană. care conțin coeficienți necunoscuți „> - vector coloană compusă din valorile din tabel funcție și matricea“ > are forma:

Sistemul de ecuații algebrice liniare (*) pentru necunoscutele are o soluție unică dacă determinantul „> nu este zero.

Determinantul matricei „> este numit determinant Vandermonde, aceasta poate fi calculată folosind următoarea formulă:

Numărul de unități de polinoame de interpolare ar trebui să fie una mai mult decât gradul său. Este clar din considerente intuitive: 2 puncte poate deține o singură linie prin intermediul 3 - un singur parabole etc. Dar polinomul poate obține și mai puțin. Ie în cazul în care cele 3 puncte se află pe o singură linie, apoi trece-le printr-un singur polinom de gradul întâi (dar acest lucru nu contrazice nimic: un coeficient de cel mai înalt grad este zero).

Cu suficientă ușurință de punere în aplicare a metodei are un dezavantaj major: numărul starea matricei crește rapid cu numărul de puncte de interpolare, care poate fi prezentată în graficul următor

Din cauza problemelor de condiționarea a matricei este recomandată utilizarea altor tehnici de interpolare (de exemplu, Lagrange de interpolare polinomiale). Este important să se înțeleagă că teoretic folosesc diferite metode conduc la același rezultat, adică, vom obține același polinomul.

Cu toate acestea, realizarea practică a polinoame, vom obține o precizie de aproximare diferită din cauza erorii tehnicii de calcul.

O metodă de calcul a unui polinom într-un punct

Pentru a descrie grafic polinomul aproximându, este necesar să se calculeze valoarea sa într-un număr de puncte. Acest lucru se poate face în următoarele moduri.

Prima metodă. Puteți calcula valoarea lui x a1 și ori cu A0. În continuare, găsiți a2 x 2. stabilește rezultatul, și așa mai departe. Astfel, etapa j-se calculează valoarea aj x j și se adaugă la suma deja calculată.

Calcularea valorii aj x j j necesită operații de multiplicare. Ie pentru a calcula un polinom la un anumit punct necesar (1 + 2 +. + n) = n (n + 1) / 2 înmulțiri și n adaosuri. Total operațiuni în acest caz: Op1 = n (n + 1) / 2 + n.

A doua metodă. Un polinom poate fi calculat cu ușurință folosind așa-numitul schema Horner:

Pentru a calcula valoarea parantezelor interne un x + o-1 necesită o operație de multiplicare și o operație de adăugare. Pentru a calcula valorile în următoarele paranteze (un x + o-1) x + o-2 din nou necesită o operație de multiplicare și o singură operație plus, deoarece un x + o-1 a fost calculat, etc.

Apoi, în această metodă, calcularea Pn (x) necesită n înmulțiri și n adiții, adică Op2 complexitate de calcul = n + n = 2n. În mod evident, Op2 <

metoda de analiză

complexitate computațională

Funcția de interpolare Complexitatea Estimarea este compus din numărul de operații pentru a rezolva sistemul de ecuații liniare algebrice (SLAE) și găsirea valorii polinomului la un punct.

Complexitatea rezolvării exemplu, metoda Gauss pentru matrice xn dimensiune n liniar,. 2n 3/3, adică O (n 3).

Pentru a găsi polinomul la un anumit punct, necesită n înmulțiri și n adăugări. Ca urmare, metoda de complexitate: O (n 3).

eroare de interpolare

Să presupunem că intervalul de interpolare [a, b] Funcția f (x) n continue. eroare interpolarea constă dintr-o eroare a erorilor metodei și rotunjire.

aproximare funcția de eroare f (x) polinom de gradul de interpolare a n-Pn (x) la punctul x este determinat de diferența: Rn (x) = f (x) - Pn (x).

Acuratețea Rn (x) este definită de următoarea relație:

Aici (\ xi) „> - derivat al (n + 1) -lea funcția comandă f (x) la un anumit punct este definit ca o funcție

Dacă valoarea maximă a f derivat n + 1 (x) este „> pentru estimarea erorii de interpolare urmează:

La punerea în aplicare această metodă pe o eroare de calculator En interpolare (x), presupunem deviația maximă de la funcția polinomială original în intervalul selectat:

Selectarea punctelor de interpolare

Este clar că alegerea componentelor funcției interpolate afectează în mod direct cât de bine va fi o aproximare polinom.

Vom introduce următoarea definiție. Cebîșev polinom este un polinom de forma

Se cunoaște (vezi. Referința literaturii) că, în cazul în care punctele de interpolare x0. x1. xn sunt rădăcinile polinomului Cebîșev de gradul n + 1. Acesta primește valoarea cea mai mică valoare posibilă în comparație cu orice alt set de puncte de interpolare pentru acest lucru.

Evident că, în cazul în care k = 1 funcția T1 (x). Intr-adevar, un prim polinom de gradul ca T1 (x) = cos (ARccOS x) = x.

În cazul k = 2 T2 (x) este, de asemenea, un polinom de gradul al doilea. Este ușor de verificat. Utilizați identitatea trigonometrice cunoscute: cos2θ = 2cos²θ - 1, punând θ = ARccOS x.

Apoi obținem următoarea relație: T2 (x) = 2x² - 1.

Folosind identități trigonometrice cos (k + 1) θ = 2cosθ coskθ - cos (k - 1) ușor pentru a arăta că raportul pentru rekkurentnoe polinoame Chebyshev:

Cu acest raport poate fi obținut cu formula pentru polinoamele Chebyshev de orice grad.

Chebyshev rădăcini polinomiale nahodyatya cu ușurință din ecuația: Tk (x) = cos (k ARccOS x) = 0. Considerăm că ecuația este k rădăcini distincte dispuse pe intervalul [-1,1], și care ar trebui să fie selectat ca nodurile de interpolare.

Este ușor de observat că rădăcinile de pe [-1,1] sunt dispuse simetric și uniform - cel mai aproape de marginea segmentului, rădăcinile sunt situate dens. Valoarea maximă a polinomului Cebîșev a modulului este egal cu 1 și se realizează la punctele

Dacă presupunem că pentru coeficientul de cel mai înalt grad de ωk polinomul (x) este egal cu 1,

Este cunoscut faptul că pentru orice pk polinom (x) de grad k de coeficientul egal cu unitatea la cea mai mare inegalitate derivat adică polinoamele Chebyshev sunt polinoame, cel mai puțin se abat de la zero.

experimentul Computing

Pentru a realiza sarcina, programul în C ++ a fost scris, că funcția dată aduce polinom canonică. Desigur, trebuie să specificați nodurile prin care va avea loc polinom și valoarea funcției la aceste noduri.

Apoi, un sistem liniar ecuații algebrice este rezolvată de Gauss. Ieșirea este coeficienții pentru aproximarea polinomial și eroarea.

Așa cum sa arătat mai sus, și după cum vom vedea mai târziu, alegerea unităților depinde de precizia cu care polinomul va mări funcția.

Exemplu: Interpolare sinus

Încercați să interpola funcția y = sin (x) în intervalul [1, 8,5]. Am ales punctele de interpolare:

Polinomului de interpolare care rezultă cartografiat în figură (albastru prezintă un grafic al y = sin (x), roșu - Interpolarea polinomială)

eroare Interpolarea în acest caz: 0.1534

Să vedem ce se întâmplă dacă vom alege unități uniforme permanente pentru aceeași funcție pe același interval.

Pe intervalul [3, 6] abordare, fără îndoială, a fost cel mai bun. Cu toate acestea, repartizate pe o marje foarte mari. Eroare interpolare: 2.3466.

În cele din urmă, vom alege punctele de interpolare, în conformitate cu algoritmul Cebîșev. Noi le obține prin următoarea formulă (doar a face schimbarea de variabilă):

În acest caz, [a, b] - intervalul [1, 8,5], y = cosx. n + 1 - numărul de noduri.

Rămâne o întrebare deschisă cât de multe unități de a alege.

Dacă valoarea n este mai mică de 3 eroare de aproximare obținută peste 10.6626.
Când n = 4. mai bună aproximare (eroare egală cu 1.0111)
când eroarea n = 5. aproximare 0.2797

Funcții Grafic când n = 4 este după cum urmează:

Când n = 7 eroare de aproximare are cea mai mică dintre valorile obținute anterior (pentru un anumit interval): 0,0181. sinus grafic (indicat în albastru) și o aproximare polinomiala (indicat în roșu), este prezentat în graficul de mai jos:

Ceea ce este interesant, în cazul în care același număr de noduri pentru a le selecta pe intervalul [1, 8], eroarea de aproximare este chiar mai mic. 0,0124. Graficul în acest caz, este următoarea:

Când selectați un număr mai mare de noduri, situația se înrăutățește: încercăm să aducă prea cu exactitate funcția inițială:

eroare de aproximare va crește doar cu numărul de noduri.

După cum puteți vedea, cea mai bună aproximare se obține prin alegerea nodurile metodei Cebîșev. Cu toate acestea, recomandările pe care numărul de noduri este optimă, nu - este determinată doar de experiment.

recomandări programator

Programul este scris în C ++ folosind UBlas bibliotecii algebra liniara, care face parte din colecția bibliotecii Boost. Descărcați codul sursă aici [2.55Kb].

tincturi preliminare

Pentru a utiliza acest program, trebuie să faceți următoarele: 1. Decide cu privire la funcția pe care urmează să interpola 2. Creați un fișier text (de exemplu, vec.txt), prima linie este plasat prin nodurile decalaj de interpolare, iar al doilea - valoarea funcției selectate în aceste noduri.

De exemplu, funcția y = sin (x):

3. În fișierul Cpp funcție de program f dublu (dublu x) în loc de o valoare de registru întoarcere șir de caractere returnat de funcția inițială. De exemplu, pentru o funcție y = sin (x):

4. Funcția int main () din codul sursă atribuit unui char * cale flname variabilă la fișierul de date de intrare. În cazul nostru, char * flname = "vec.txt";

Utilizarea programului

Programul oferă următoarele funcții principale:

f dublu (double x). a căror divulgare a fost prezentată mai sus
sarcină int (char * nume de fișier, vector x, vector y) - încărcarea nodurile de interpolare în variabila x și valoarea funcției la aceste noduri la variabila y numele de fișier fișier text. În cazul datelor de încărcare de succes dintr-o funcție fișier returnează 0.
void matrix2diag (matrice A, vector y) - O matrice duce la o formă triunghiulară. y - coloana din partea dreaptă (de asemenea, modificări cu matricea A).
void SolveSystem (matrice A, vector y, vector coef) - decid SLAE (A - o matrice triunghiulară, y - coloana din partea dreaptă, coef - acest vector este stocat în soluție SLAE)
double errapprox (vector coef, dublu a, dublu b, dublu h) - returnează o aproximare polinom eroare a funcției inițiale.

Funcția de intrare servește următorii parametri:

- coef vector - interpolare vector coeficienți polinomiali, care se obține în cursul rezolvării liniare
- dubla a, dublu b - intervalul de interpolare de delimitare [a, b]
- dublu h - pasul care "funcționare" interval [a, b]

int outpolyn (char ** nume de fișier, vector coef) - salvează coeficienții polinomului coef în numele fișierului de fișiere. În cazul în care „0“ o conservare de succes funcția întoarce.

După pornirea programului pe ecran apar coeficienții erorii de interpolare și aproximare polinomială.

A fost investigat și software-ul metoda funcțiilor de interpolare polinomiale canonice puse în aplicare. Studiile au constatat că eroarea de interpolare se obține ca urmare a erorilor de calcul și din cauza erorii metodei.

Este de remarcat faptul că, de asemenea, alegerea nodurilor de interpolare depinde direct de calitatea interpolării. Eroarea minimă de interpolare se realizează atunci când „Chebyshev“ noduri.