cours-polynomes2
11
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
11
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
6Polyn^omes et racinesChristophe Ritzenthaler1 Methodes generales1.1 Evaluation d’un polyn^ omenSoit P (X) = a X +::: +a X +a 2 R[X]. Nous allons nous preoccuper du nombren 1 0d’operations elementaires (multiplication et addition) necessaires pour evaluerP en un nombrereel. Si on e ectue le calcul de maniere basique, on a 2 n 1 multiplications et n additions.1.1.1 Methode de HornerEcrivonsna x +::: +a x +a = ((::: (a x +a )x +a ):::)x +a :n 1 0 n n 1 n 2 0On obtient n multiplications et additions.1.1.2 Methode du produitQSiP (x) =a (x ) avec tous les reels, on a egalement besoin den multiplications0 i iet additions.1.1.3 Forme orthogonalePnOn ecrit P (x) = b Q (x) ou les polyn^ omes Q satisfontk k ik=0Q = (A x +B )Q (x) C Q (x); A = 0; Q = 1; Q = 0:i+1 i i i i i 1 i 0 1L’evaluation requiert 3n 1 multiplications et additions. Parmi les familles de polyn^ omesorthogonaux, on a les polyn^ omes de Chebyshev, T qui sont le meilleur choix en termend’e cacite de l’evaluation. Rappelons que les polyn^ omes de Chebyshev satisfont T (cos(x)) =ncos(nx) et sont donnes par la recurrence A = 2 pour i 1, A = 1 et B = 0;C = 1 pouri 0 i ii 0.1.1.4 Pre-processingSi on desire evaluer le polyn^ ome en plusieurs points, il peut ^etre interessant de s’autoriserune modi cation des coe cients avant le debut des calculs a n de simpli er ces derniers.Ceci s’appelle le pre-processing. Considerons le cas d’un polyn^ ome de degre 4. On ...
Voir
Publié par
Langue
Catalan
1
Polynˆomesetracines
Christophe Ritzenthaler
M´ethodesge´ne´rales
1.1Evaluationd’unpolynˆome n SoitP(X) =anX+. . .+a1X+a0∈R[Xoeccpurensuops´rdunombreN.]nollasuo d’op´erationse´le´mentaires(multiplicationetaddition)ne´cessairespour´evaluerPen un nombre re´el.Sioneffectuelecalculdemanie`rebasique,ona2n−1 multiplications etnadditions.
1.1.1M´ethodedeHorner Ecrivons
n anx+. . .+a1x+a0= ((. . .(anx+an−1)x+an−2). . .)x+a0.
On obtientnmultiplications et additions.
1.1.2M´ethodeduproduit Q SiP(x) =a0(x−αi) avec tous lesαidesoinntbelemee´ago,aneesl´rnmultiplications et additions.
1.1.3 Forme orthogonale P n One´critP(x) =bkQk(x)o`ulespoylˆnmoseQisatisfont k=0 Qi+1= (Aix+Bi)Qi(x)−CiQi−1(x), Ai6= 0, Q0= 1, Q−1= 0.
L’e´valuationrequiert3n−1 multiplications et additions. orthogonaux,onalespolynˆomesdeChebyshev,Tnqui d’efficacit´edel’´evaluation.Rappelonsquelespolynˆomesde cos(nxencreurecr´laarpse´nnodtnoste)Ai= 2 pouri≥ i≥0.
Parmilesfamillesdepolynˆomes sont le meilleur choix en terme Chebyshev satisfontTn(cos(x)) = 1,A0= 1 etBi= 0, Ci= 1 pour
1.1.4Pre´-processing Siond´esire´evaluerlepolynˆomeenplusieurspoints,ilpeutˆetreinte´ressantdes’autoriser unemodificationdescoefficientsavantled´ebutdescalculsafindesimplifiercesderniers. Ceci s’appelle lesingp´r-erpcosetceir.Consid´eroncels’dsaopnuˆnyledomegede4r´n´.O 4 3 2 a4x+a3x+a2x+a1x+a0 =a4((x(x+α0) +α1)(x(x+α0) +x+α2) +α3) (1) 4 3 2 =a4x+a4(2α0+ 1)x+a4(α1+α2+α0(α0+ 1))x +a4((α1+α2)α0+α1)x+a4(α1α2+α3).
1
On peut alors trouver lesαien fonction des coefficientsai. La forme de (1) utilise 3 multipli-cationset5additions.Si,commec’estsouventlecas,lesmultiplicationssontpluscouˆteuses quelesadditions,cetalgorithmepre´sentedoncunavantagesurlam´ethodedeHorner.
1.1.5Quelquesr´esultatsth´eoriques Denombreuxre´sultatssontconnussurcequ’onpeutfairedemieuxpourceproble`me. The´ore`me1.1.Toutalgoritmh´evelaautnnuopemoˆnylPe´rgedednaisgnesocpre-r´spans besoin d’au moinsnmultiplications etnadditions. Ainsi dans ce cas l’algorithme de Horner est optimal.
Aucontrairesionacceptelepre´-processing,onaler´esultatsuivant. The´or`eme1.2.emxeirhtlaogetnuexisIlitaulave´’lruop)galaBedee(iticplno’dnuopylˆnmoe enb(n+ 1)/2c+ 1multiplications etn+ 1additions. Il n’existe pas d’algorithme avec moins deb(n+ 1)/2cmultiplications ou moins denadditions. Onnesaitpassileseuilpeutˆetreatteintounon.L’algorithmedeBelagapeutavoir besoin de coefficients complexes. Il en existe un autre (l’algorithme de Pan) enbn/2c+ 2 multiplications etnadditions qui pour des coefficients de+ 1 Pers`mten‘s’eluratrapaesad re´els.ParlasuiteRabinetWinogradontdonn´euneme´thodeendn/2e+O(logn) multipli-cations/divisions etn+O(nee´r.slcieffitsentdencoesucinuqmeitnoasev)addi
1.1.6Unequestionauxiliaire:lastabilit´eetleconditionnement Grossi`erement,unalgorithmeestditnum´eriquementtsnielbaesedreersdurrr’ali’se´rc-on disquiaugmententdemanie`reincontrˆole´.Unautreconceptestlemauvais conditionnement. Unalgorithmeestmalconditionne´siunepetiteincertitudesurlesdonn´eesd’entr´eespeut cre´erunegrandeincertitudesurlere´sultat.Letableauci-dessousr´esumecespropri´et´espour lesalgorithmesd’e´valuation. FormeConditionnementstabilit´e Hornerpeutˆetremalconditionn´epeutˆetreinstable Formeproduitassezbiencondition´estable Chebyshevbienconditionn´estable Belagapeuteˆtremalconditionn´epeutˆetretr`esinstable PanConj.:sipetitsPancoef.alorsbienconditionne´peuteˆtretre`sinstable.
1.2Interpolation.Spline.CourbesdeBe´zier 1.2.1 Interpolation de Lagrange 2 Soient (x0, y0), . . . ,(xn, yn)∈Cavec lesxinˆomeiquepolyetsinunu.stcxelIdiinstF∈ C[X] tel queF(xi) =yioitte.Sivanresue`inamaledtiurtsontcescii-luCe. Q n (X−xj) j=0 bi=, i= 0, . . . , n. X−xi Cespolynˆomesformentunebasedespolynˆomesdedegr´eauplusnet ona facilement n X yi F(X) =bi(X). bi(xi) i=0 Remarque 1.esingerdvisauren’drooisnlotaetpr.reeuri´eupesdrpeOnbiutsˆen
2
1.2.2 Spline 2 Soient (x0, y0), . . . ,(xn, yn)∈Ravec lesxicroissants distincts. Sur chacun des intervalles [xi, xi+1o,cn]olyneunpd`eronsimelleutibah(emoˆ(),e3r´egedtdenPi)i=0,...,n−1tqiuv´erifien lesproprie´te´ssuivantes: 0 0 00 00 , P(x) =P(x), P(x) =P(x). Pi(xi) =yi, Pi(xi+1) =yi+1i i+1i+1i+1i i+1i+1i+1 Cesconditionssontdesconditionsnaturellesderecollement.Onsupposeparfoisquelade´rive´e secondeestnulleauxextre´mite´sdel’intervallepourpermettredeprolongerparunefonction affine en dehors de l’intervalle. Cesfonctionssontutilise´esdanslesmode´lisationsdecourbesplanes. Remarque 2.cnofnoitnahcenegLeoispsontla`ueremtnelpsiotndsseontpasn´ecessai controˆle.C’esticiunesimplification.
1.2.3CourbesdeB´ezier voir texte.
2
Racinesd’unpolynˆome
2.1 Calcul exact Rappelonsqu’iln’yapasdeformulepermettantd’exprimerdemanie`reg´en´eraleles racinesd’unpolynˆomededegr´e5ouplus.Cere´sultatestobtenuparlath´eoriedeGalois. Remarque 3.tnel´sqeauitnodsedegr´eOuepndestanemrqdelluesoes5rapselr´esolub 5 radicaux.Toute´equationirre´ductiblededegr´e5peut se mettre sous la formex+ax+b= 0. Celle-ci admet des solutions (Carl Runge, 1885) par radicaux si et seulement si il existe des rationnelsu, vtels que 4 5 5u(4v4+ 3) u(2v+ 1)(4v+ 3) a=, b=. 2 2 v+ 1v+ 1 5 4 3 2 Par exemplex−5x−10x−10x−5x−1ionr´eelleocmmueinuqselotuetdmax= √ √ √ √ 5 5 5 5 5 1 + 2 + 4 + 8 + 16ntua`aQ.x−5x+ 12ssuoitnoosuldtseemenegalmet´leadels formes de radicaux mais demande600sirer.ourl’´ecymbolesp
2.1.1Degre´2 Rappelonslere´sultatconnu. 2 Proposition 2.1.Soitax+bx+cge´rdedeeunomnˆlypo2semsearL.sdeccineynˆoepol sont √ 2 −b±b−4ac . 2a
2.1.2Degre´3 3 2 Passonsaudegr´e3.Soitx+ax+bx+ctanieuomnˆlypounenO.3e´rgedederiueffect le changement de variablex=z−a/iebtunnt3enotoudnoepytqe´eitau 3 2 3 z+pz+q= 0, p=b−a /3, q= 2a /27−ab/3 +c. On a deux cas possibles :
3
