cours-polynomes2

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

Informations

• Publié par: Zyof
• Nombre de lectures: 44
• Langue: Catalan

Extrait

1

Polynˆomesetracines

Christophe Ritzenthaler

M´ethodesge´ne´rales

1.1Evaluationd’unpolynˆome n SoitP(X) =a n X+. . .+a 1 X+a 0 ∈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 a n x+. . .+a 1 x+a 0 = ((. . .(a n x+a n−1 )x+a n−2 ). . .)x+a 0 .

On obtientnmultiplications et additions.

1.1.2M´ethodeduproduit Q SiP(x) =a 0 (x−α i ) avec tous lesα i desoinntbelemee´ago,aneesl´rnmultiplications et additions.

1.1.3 Forme orthogonale P n One´critP(x) =b k Q k (x)o`ulespoylˆnmoseQ i satisfont k=0 Q i+1 = (A i x+B i )Q i (x)−C i Q i−1 (x), A i 6= 0, Q 0 = 1, Q −1 = 0.

L’e´valuationrequiert3n−1 multiplications et additions. orthogonaux,onalespolynˆomesdeChebyshev,T n qui d’efficacit´edel’´evaluation.Rappelonsquelespolynˆomesde cos(nxencreurecr´laarpse´nnodtnoste)A i = 2 pouri≥ i≥0.

Parmilesfamillesdepolynˆomes sont le meilleur choix en terme Chebyshev satisfontT n (cos(x)) = 1,A 0 = 1 etB i = 0, C i = 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 a 4 x+a 3 x+a 2 x+a 1 x+a 0 =a 4 ((x(x+α 0 ) +α 1 )(x(x+α 0 ) +x+α 2 ) +α 3 ) (1) 4 3 2 =a 4 x+a 4 (2α 0 + 1)x+a 4 (α 1 +α 2 +α 0 (α 0 + 1))x +a 4 ((α 1 +α 2 )α 0 +α 1 )x+a 4 (α 1 α 2 +α 3 ).

1

On peut alors trouver lesα i en fonction des coefficientsa i . 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 (x 0 , y 0 ), . . . ,(x n , y n )∈Cavec lesx i nˆomeiquepolyetsinunu.stcxelIdiinstF∈ C[X] tel queF(x i ) =y i oitte.Sivanresue`inamaledtiurtsontcescii-luCe. Q n (X−x j ) j=0 b i =, i= 0, . . . , n. X−x i Cespolynˆomesformentunebasedespolynˆomesdedegr´eauplusnet ona facilement n X y i F(X) =b i (X). b i (x i ) i=0 Remarque 1.esingerdvisauren’drooisnlotaetpr.reeuri´eupesdrpeOnbiutsˆen

2

1.2.2 Spline 2 Soient (x 0 , y 0 ), . . . ,(x n , y n )∈Ravec lesx i croissants distincts. Sur chacun des intervalles [x i , x i+1 o,cn]olyneunpd`eronsimelleutibah(emoˆ(),e3r´egedtdenP i ) i=0,...,n−1 tqiuv´erifien lesproprie´te´ssuivantes: 0 0 00 00 , P(x) =P(x), P(x) =P(x). P i (x i ) =y i , P i (x i+1 ) =y i+1i i+1 i+1 i+1i i+1 i+1 i+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