1 Proprietăți și structura algoritmului
1.1 Descrierea generală a algoritmului
Problema integrării numerice unidimensionale constă în calcularea aproximativă a unui integral definit pe un interval: este necesar să se calculeze
unde [math] f (x) [/ math] este o funcție integrabilă definită pe intervalul [math] [a, b] [/ math].
Integrarea numerică se realizează utilizând formule de cvadratură - egalitatea aproximativă a formei
[matematica] I \ aproxima \ sum \ limits_ ^ n C_i f (x_i). [/ math]
Suma din dreapta se numește suma cvadratură; diferite puncte [math] x_i [/ math] ale segmentului [math] [a, b] [/ math] se numesc noduri, iar numerele [math] C_i [/ math] sunt coeficienții formulei de cvadratură.
Valoarea sumei de cvadratură, luată ca o valoare aproximativă a integrului, depinde de alegerea nodurilor [math] x_i [/ math] și a coeficienților [math] C_i [/ math]. Atunci când se calculează valoarea sumei de cvadratură, costurile principale de timp sunt de a calcula valorile integranei la noduri.
Eroarea în formula de cvadratură este diferența
Dacă funcția [math] f (x) [/ math] este astfel încât [math] R_n (f) = 0 [/ math]. atunci formula quadrature se spune că este exactă pentru funcția [math] f (x) [/ math].
Integer [matematica] k \ Ge0 [/ math] numit algebrică formula precizie cuadratură, dacă formula de cuadratură este exact pentru orice polinom de grad la [matematică] K [/ matematica] și nu exactă pentru un polinom de grad [matematica] K + 1 [ / matematică].
Dacă formula quadrature cu nodurile [math] n [/ math] are un grad algebric de precizie [math] k [/ math]. apoi [math] k \ le 2n-1 [/ math].
Formule de cuadratură larg cunoscute obținute prin schimbarea integrantul [matematica] f (x) [/ math] algebrică polinom de interpolare ale cărui valori coincid cu valori ale funcțiilor în [matematica] n [/ matematica] noduri [matematica] x_i [/ matematica]; astfel de formule de cvadratură sunt numite formule de interpolare. Pentru eroarea formulei de cvadratură de interpolare,
unde [math] M_n = \ max \ limits_ | f ^ (x) | [/ math]. [math] \ omega_n (x) = \ prod \ limits_ ^ n (x-x_i) [/ matematică].
Dacă formula de cvadratură de interpolare cu nodurile [math] n [/ math] are un grad algebric de precizie [math] k [/ math]. apoi [math] k \ ge n-1 [/ math].
1.1.1 Formule Newton-Cotes
Newton-Cotes numit interpolare formula cvadratură, [matematică] n [/ math] care nodurile sunt setate echidistant: [matematica] x_1 = \ frac2 [/ math] la [matematică] n = 1 [/ math] și [matematică] x_i = a + (i-1) \ frac, 1 \ le i \ le n [/ math] la [matematică] n \ GT1 [/ matematică].
Numele lor a fost dat în memorie faptului că ei au fost considerați într-o formă destul de generală de către Isaac Newton, iar coeficienții lor au fost găsiți de Roger Cotes la 1 ianuarie 10 [/ math].
Cele mai renumite formule Newton-Cotes sunt formulele dreptunghiurilor medii ([math] n = 1 [/ math])
și formula trapezoidală ([math] n = 2 [/ math])
Gradul de precizie algebric al fiecăruia este egal cu 1, iar pentru erorile lor estimările
Formulele Newton-Cotes cu [math] n = 3 [/ math] și [math] n = 4 [/ math]
care se mai numește formula parabolică și formula de trei optzeci
al cărui nume provine de la coeficientul 3/8; Gradul de precizie algebric al fiecăruia este egal cu 3, iar pentru erorile lor estimările
grad algebrică de precizie Formula Cotes Newton cu [matematică] n [/ math] noduri este egal [matematica] n-1 [/ math] pentru chiar [matematică] n [/ matematica] și egal cu [matematică] n [/ math] pentru nui [math] n [/ math].
Coeficienții formulelor Newton-Cotes sunt pozitivi pentru [math] 1 \ le n \ le8 [math] și [math] n = 10 [/ math]. iar la coeficienții [math] n = 9 [/ math] și matematicieni există coeficienți pozitivi și negativi.
Pozitivitatea coeficienților formulei de cvadratură este importantă pentru aplicarea sa practică. Faptul este că atunci când se calculează suma integrală, efectul de rotunjire a erorilor asupra acurateței rezultatului este mai puternic, cu atât mai mare, cu atât mai mult [matematică] sumă \ limits_ ^ n | C_i | [/ math]. Pentru formulele Newton-Cotes, această sumă crește neîngrădit cu [math] n \ to \ infty [/ math]. Prin urmare, pentru formulele mari [math] [/ math], formulele Newton-Cotes se dovedesc a fi practic inadecvate.
Astfel, pentru a folosi formulele de cvadratură cu un număr mare de noduri, este necesar să se refuze fie că formula de cvadratură se interpolează, fie că nodurile sunt setate la distanțe egale.
1.1.2 Formule compozite de cvadratură
Formulele de cvadratură sunt numite compuse, ale căror construcții se efectuează după cum urmează. Segmentul de integrare [math] [a, b] [/ math] este împărțit în segmente [math] m [/ math] de lungime egală [math] h = \ dfracm [/ math]. Apoi, prin proprietatea aditivității, integralele pot fi calculate ca suma integralelor peste segmentele partiției. Pentru calcularea aproximativă a fiecărui termen al acestei sume, se folosește aceeași formulă de cvadratură, numită cea inițială.
Gradul de precizie algebrică a unei formulări compozite de cvadratură coincide cu gradul algebric al preciziei celui original.
Dacă formula dreptunghiurilor medii, formula trapezoidală sau formula Simpson este aleasă ca formulă de cvadratură inițială, se vor obține următoarele formule de cvadratură compuse:
formula compusă din dreptunghiuri medii
[math] I \ aproximativ h \, (\ suma \ limite_ ^ m f (a + ih- \ frac)) [/ math]cu numărul de noduri [math] m [/ math] și estimarea erorii
compoziție trapezoidală
cu numărul de noduri [math] m + 1 [/ math] și estimarea erorii
formula compusă de Simpson
[math] I \ aproxima \ frac \, (f (a) + f (b) +2 \ suma \ limits_ ^ f (a + ih) +4 \ suma \ limits_ ^ mf (a + ih- \ frac)) [/ math]cu numărul de noduri [math] 2m + 1 [/ math] și estimarea erorii
1.1.3 Formulele Gauss cu cvadratură
După cum sa menționat mai sus, dacă formula de cvadratură cu nodurile [math] n [/ math] este interpolare, atunci gradul său de precizie algebric nu este mai mic decât [math] n-1 [/ math]; pentru orice nod dat, construirea formulei de cvadratură de interpolare se realizează prin alegerea coeficienților [math] n [/ math]. Prin alegerea nodurilor [math] n [/ math] a nodurilor formulei de cvadratură de interpolare, putem asigura că are cel mai înalt grad de acuratețe algebric posibil, și anume [math] 2n-1 [/ math].
Problema construirii unei astfel de formulări de cvadratură a fost luată în considerare de Carl Friedrich Gauss; el și-a dovedit solvabilitatea.
O formulă de cvadratură cu noduri [math] n [/ math] al căror grad algebric de precizie este [math] 2n-1 [/ math]. se numește formula de cvadratură Gauss sau formula de cvadratură cu gradul cel mai înalt algebric de precizie.
În cazul unui segment [math] [- 1,1] [/ math], formula de cvadratură
[math] \ int \ limits_ ^ 1 f (t) \, dt \ aproxima \ sum \ limits_ ^ n c_i f (t_i) [/ math]
este o formulă de tip quadrature Gaussian dacă și numai dacă este o formulă de interpolare, iar nodurile [math] t_i [/ math] sunt rădăcinile polinomului Legendre
În special, pentru formulele de cvadratură Gaussiană pentru segmentul [math] n = 2 [/ math] și [math] n = 3 [/ math] [-] [/ math]
[Math] \ int \ limits_ ^ 1 f (t) \, dt \ approx f \ stânga (- \ frac1 \ dreapta) + f \ left (\ frac1 \ dreapta) [/ matematica] [matematica] \ int \ limits_ ^ 1 f (t) \, dt \ approx \ frac59 \; f \ stânga (- \ sqrt \ dreapta) + \ frac89 \; f (0) + \ frac59 \; f \ stânga (\ sqrt \ dreapta) [. / math]
Pentru a obŃine formula de cadre Gaussian pentru un interval arbitrar [math] [a, b] [/ math]. este necesar să se facă o modificare a variabilei
ca urmare a acestui fapt
Folosind formula Gauss pentru intervalul [math] [- 1,1] [/ math]. obținem formula de cadran Gaussian pentru intervalul [math] [a, b] [/ math].
[math] I \ ca \ frac2 \ suma \ limits_ ^ n c_i f (x_i), [/ math]
unde [math] x_i = 0,5 (a + b + (b-a) t_i) [/ math]. [math] t_i [/ math] sunt rădăcinile polinomului Legendre [matematică] P_n (t) [/ math].
Pentru eroarea nodurilor formulei cvadraturii Gauss c [math] n [/ math], estimarea
Coeficienții formulelor de cvadratură Gaussian sunt pozitivi. Prin urmare, folosirea formulelor de cvadratură Gaussiană cu un număr mare de noduri nu conduce la complicațiile care apar atunci când se utilizează formulele Newton-Cotes.
1.2 Descrierea matematică a algoritmului
Dacă formula de cvadratură este aleasă, atunci algoritmul de calcul aproximativ al integrului constă în calcularea sumei de cvadratură, adică în calcularea valorilor funcției în nodurile [math] n [/ math], înmulțirea lor cu coeficienții corespunzători și însumarea numerelor obținute.
Datele inițiale: funcția [math] f (x) [/ math] și două matrice unidimensionale [math] n [/ math] numere - o matrice de noduri și o serie de coeficienți.
Date calculate: un număr care reprezintă valoarea sumei de cvadratură și reprezintă o valoare aproximativă a integrala.