cours-polynomes2
11 pages
Catalan

cours-polynomes2

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

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 ...

Sujets

Informations

Publié par
Nombre de lectures 44
Langue Catalan
1
Polynˆomesetracines
Christophe Ritzenthaler
M´ethodesge´ne´rales
1.1Evaluationdunpolynˆome n SoitP(X) =anX+. . .+a1X+a0R[Xoeccpurensuops´rdunombreN.]nollasuo dop´erationse´le´mentaires(multiplicationetaddition)ne´cessairespour´evaluerPen un nombre re´el.Sioneectuelecalculdemanie`rebasique,ona2n1 multiplications etnadditions.
1.1.1M´ethodedeHorner Ecrivons
n anx+. . .+a1x+a0= ((. . .(anx+an1)x+an2). . .)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)CiQi1(x), Ai6= 0, Q0= 1, Q1= 0.
Le´valuationrequiert3n1 multiplications et additions. orthogonaux,onalespolynˆomesdeChebyshev,Tnqui decacit´edel´evaluation.Rappelonsquelespolynˆomesde cos(nxencreurecr´laarpse´nnodtnoste)Ai= 2 pourii0.
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´ressantdesautoriser unemodicationdescoecientsavantled´ebutdescalculsandesimpliercesderniers. Ceci s’appelle lesingp´r-erpcosetceir.Consid´eroncelsdsaopnuˆ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,commecestsouventlecas,lesmultiplicationssontpluscouˆteuses quelesadditions,cetalgorithmepre´sentedoncunavantagesurlam´ethodedeHorner.
1.1.5Quelquesr´esultatsth´eoriques Denombreuxre´sultatssontconnussurcequonpeutfairedemieuxpourceproble`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(iticplnodnuopylˆ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.LalgorithmedeBelagapeutavoir 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`mtenseluratrapaesad re´els.ParlasuiteRabinetWinogradontdonn´euneme´thodeendn/2e+O(logn) multipli-cations/divisions etn+O(nee´r.slcietsentdencoesucinuqmeitnoasev)addi
1.1.6Unequestionauxiliaire:lastabilit´eetleconditionnement Grossi`erement,unalgorithmeestditnum´eriquementtsnielbaesedreersdurrralise´rc-on disquiaugmententdemanie`reincontrˆole´.Unautreconceptestlemauvais conditionnement. Unalgorithmeestmalconditionne´siunepetiteincertitudesurlesdonn´eesdentr´eespeut cre´erunegrandeincertitudesurlere´sultat.Letableauci-dessousr´esumecespropri´et´espour lesalgorithmesde´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.stcxelIdiinstFC[X] tel queF(xi) =yioitte.Sivanresue`inamaledtiurtsontcescii-luCe. Q n (Xxj) j=0 bi=, i= 0, . . . , n. Xxi Cespolynˆomesformentunebasedespolynˆomesdedegr´eauplusnet ona facilement n X yi F(X) =bi(X). bi(xi) i=0 Remarque 1.esingerdvisaurendrooisnlotaetpr.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,...,n1tqiuv´erien 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´sdelintervallepourpermettredeprolongerparunefonction affine en dehors de l’intervalle. Cesfonctionssontutilise´esdanslesmode´lisationsdecourbesplanes. Remarque 2.cnofnoitnahcenegLeoispsontla`ueremtnelpsiotndsseontpasn´ecessai controˆle.Cesticiunesimplication.
1.2.3CourbesdeB´ezier voir texte.
2
Racinesdunpolynˆome
2.1 Calcul exact Rappelonsquilnyapasdeformulepermettantdexprimerdemanie`reg´en´eraleles racinesdunpolynˆ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 exemplex5x10x10x5x1ionr´eelleocmmueinuqselotuetdmax= √ √ √ √ 5 5 5 5 5 1 + 2 + 4 + 8 + 16ntua`aQ.x5x+ 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±b4ac . 2a
2.1.2Degre´3 3 2 Passonsaudegr´e3.Soitx+ax+bx+ctanieuomnˆlypounenO.3e´rgedederiueect le changement de variablex=za/iebtunnt3enotoudnoepytqe´eitau 3 2 3 z+pz+q= 0, p=ba /3, q= 2a /27ab/3 +c. On a deux cas possibles :
3