Cursul 11

Aproximarea funciilor

APROXIMARE UNIFORM Definire polinom minimax.

Norma aproximrii uniforme se definete ca:

Cel mai bun polinom de aprxoximare uniform de ordin n (aproximant uniform sau polinom minimax) al

unei funcii fC([a,b]) este acel polinom pn(x)n

care se ndeprteaz cel mai puin, n sensul normei de

funcia dat, adic

xfmaxf

b,ax

xpxfmaxminpfminpf

nb,axp

np

nnnnn

APROXIMARE UNIFORM.

Teorema de caracterizare Polinomul pn(x)este

aproximant uniform de ordin , dac e(x)=f(x)-pn(x) atinge de n+2 ori valoarea extrem +E sau

-E, cu alternane de semn ntre dou extreme

consecutive.

Exist deci n+2 puncte x0, x1,...,xn,xn+1

astfel

Teorem Cel mai bun polinom de aproximare

uniform este unic.

1n:0k,E1xpxfxe kknkk

xpxfmaxE

nb,ax

APROXIMARE UNIFORM.

Teorem-Dac funciile 1,x,x2,...,xn,f sunt

liniar independente i genereaz un spaiu vectorial V i dac orice element din V are n+2

zerouri n [a,b] atunci

10. f-pn posed exact n+2 extreme alternante

20. a i b i fac parte dintre punctele extreme;

30. ntre punctele extreme nu exist alte extreme;

40. f-pn este strict monoton ntre dou puncte

extreme alternante consecutive.

Proprieti ale polinoamelor Cebev 10. Tn(x)=cos(n.arccos x)

x=cos , [0,] Tn(cos)=cosn

APROXIMARE UNIFORM.

x[-1,1] i Tn[-1,1] adic:

Tn:[-1,1][-1,1]

20. Polinomul Tn(x) este un polinom de gradul n n

x avnd coeficientul puterii dominante 2n-1:

Tn(x)=2n-1xn+...

30. Relaia de recuren:

Tp+1(x)=2xTp(x)-Tp-1(x), T0(x)=1, T1(x)=x

Rezult din identitatea trigonometric:

cos(n+1)+cos(n-1)=2cos.cosn

40. Zerourile polinomului Cebev:

cos nk=0 k=(2k+1)/2n

xk=cos k=cos[(2k+1)/2n]

APROXIMARE UNIFORM.

50. Punctele de extrem ale polinomului Cebev

Tn(xp)=1 , p=0:n

Pe mulimea C([-1,1]) a funciilor continue pe intervalul [-1,1], putem defini produsul scalar

unde joac rolul de pondere, i pe

aceast baz se introduce conceptul de ortogonalitate, n sensul c f i g sunt ortogonale

dac =0

60.Ortogonalitatea polinoamelor Cebev

n

pcosx

p

1

12

1

120

dx

x1

xfxfdx

x1

xgxflimg,f

2x1

1xw

APROXIMARE UNIFORM.

se deduc din identitatea trigonometric cosp.cosq=(cos(p+q) +cos(p-q))/2

70.Dezvoltare n serie de polinoame Cebev

.0qp

,0qp2

,qp0

dx

x1

)x(T)x(T1

12

qp

)x(Ta)x(fp

0p

p

,1p,dx

x1

)x(T)x(f

2a

,dx

x1

)x(f

1a

1

12

p

p

1

12

0

APROXIMARE UNIFORM

i se obine din dezvoltarea n serie Fourier a

funciei:

Polinomul Cebev monic de gradul n (avnd

coeficientul puterii maxime 1) se obine din

polinomul Cebev corespunztor prin mprire cu 2n-1

pcosa)(cosf0p

p

.1p,dpcos)(cosf

2a

,d)(cosf

1a

0

p

0

0

APROXIMARE UNIFORM

Relaia de recuren pentru polinoame Cebev

monice

Polinoamele Cebev monice au aceleai zerouri i aceleai puncte n care prezint extreme ca i polinoamele Cebev corespunztoare.

Valorile extremelor sunt ns diferite i anume

1n

n~

n2

xTxT

0)x(T4

1)x(Tx)x(T

~

1p

~

p

~

1p

.n:0psin

pcosxcu

2

)1()x(T

p1n

p

p

~

n

APROXIMARE UNIFORM

Teorem Dintre polinoamele monice de ordin n

definite pe [-1,1], polinomul monic Cebev

Tn~(x) are norma aproximrii uniforme minim i

Teorema precedent ne permite s gsim abscisele x0,x1,...,xn din [-1,1] care minimizeaz

eroarea interpolrii Lagrange

Restul interpolrii este minimizat n sensul aproximrii uniforme pentru R~n+1=T

~n+1, adic

~

nnn1,1x

~

n1,1x

1nPxPmaxxTmax

2

1

)!1n(

)(f)x(R)x(P

)!1n(

)(f)xx()xx()x(P)x(f

)1n(

~

1nn

)1n(

n0n

APROXIMARE UNIFORM

pentru punctele

i n acest caz avem majorarea

Intervalul de interpolare poate fi extins la [a,b]

cu schimbarea de variabil:

Determinarea polinomului minimax al unei funcii

Pentru funcia fC([a,b]) se face mai inti o

schimbare liniar de variabil pentru a se trece n

domeniul [-1,1].

2n2

1k2cosx

k

)x(fmax)!1n(2

1)x(P)x(fmax

)1n(

]1,1[xnn

]1,1[x

2

abx

2

abt

APROXIMARE UNIFORM

n cazul particular n care funcia f este un

polinom de grad n+1:

cel mai bun polinom de aproximare uniform de ordin n este

Intr-adevr diferena

satisface teorema de caracterizare, prezentnd

alternane , n punctele

ab

abt

ab

2tx

0

n

n

1n

1naxaxaxf

)x(T2

a)x(f)x(p

1nn

1n*

n

xT2

axpxf

1nn

1n*

n

1n:0k,1n

kcosx

k

APROXIMARE UNIFORM

n cazul general, n care f este o funcie continu

oarecare, o aproximare a polinomului minimax se

determin pornind de la dezvoltarea n serie de

polinoame Cebev a funciei obinndu-se

Dac dezvoltarea n serie a lui este rapid

convergent, putem considera

atunci, dac se ia pentru polinomul minimax

dezvoltarea trunchiat

n

0p 2np

pp1n1npp

*

n)x(Tc)x(Tc)x(Tc)x(p)x(fxe

2np

pp0)x(Tc

n

0p

p

p

n

0p

pp

*

nxa)x(Tc)x(p

APROXIMARE UNIFORM

se constat c diferena prezint proprietatea de

oscilaie din teorema de caracterizare.

Aproximaii bune ale polinomului minimax se obin

folosind algoritmii lui Rms.

n algoritmul 1 Rms, n locul rezolvrii sistemului

cu necunoscutele i E, obinut din

1n:0k),x(fE)1(xak

kn

0k

k

ii

n:0i,ai

.xa)x(p

,1n:0kE)1()x(p)x(f

n

0k

k

iik

*

n

k

k

*

nk

APROXIMARE UNIFORM

se construiesc polinoamele de interpolare Lagrange Rn+1(x) i Sn+1(x) ale funciilor f(x) i (-1)

k.

cu care se face aproximarea

Valoarea se determina impunnd coeficientul puterii

s fie 0 an+1=rn+1-Esn+1=0 de unde i

1n:0k,xfxRkk1n

kk1n

1xS

xESxRxp1n1n

*

n

1n

1n

s

rE

n:0i,ss

rra

i

1n

1n

ii

APROXIMARE UNIFORM

Algoritmul 2 Rms pornete de la polinomul astfel determinat i stabilete valoarea extrem a funciei f(x); fie

xM abscisa pentru care se atinge acest extrem. function [a, x, y] = Remes1(n, f, nrapel)

% Intrri:

% n = gradul polinomului minimax

% f = funcia aproximat de polinomul minimax

% nrapel = indicator al primului apel n care

% se iniializeaza tabelele x i y

% apelurile urmtoare se fac din Remes2

% modific o singur component din x i y

% Ieiri:

% a = tabel coefic. polinom minimax

% x= abscise puncte de oscilaie

% y = ordonate puncte de oscilaie

APROXIMARE UNIFORM

if nrapel == 0

x=0:pi/(n+2):pi;

x=cos(x);

y=f(x);

z=ones(n+2,1);

for k=1:2:n+2

z(k)=-1;

end

%calcul coef.r pol Lagrange n (x, y);

r=CoefLagr(x,z);

%calcul coef s pol Lagrange n (x, z);

s=CoefLagr(x,z);

E=r(n+1) / s(n+1)

a(0:n)=r(0:n) - E*s(0:n);

end

APROXIMARE UNIFORM

Dac xM este unul din punctele iniiale, determinarea polinomului minimax s-a ncheiat, n caz contrar se ncadreaz ntre dou puncte consecutive xp

APROXIMARE UNIFORM

nrapel 0

[a,x,y]=Remes1(n, f, nrapel)

repet

%cauta xm a. |f(xm)-pn(xm)| maxim

%dac xm difer de abscisele x atunci

ncadreaz x(p) < xm < x(p+1)

if (y(p)-pn(x(p)))* (f(xm)-pn(xm)) > 0

x(p) = xm;

y(p) = ym;

else

x(p+1) = xm;

y(p+1) = ym;

end

rapel = nrapel + 1;

[a,x,y]=Remes1(n, f, nrapel);

pin cnd xm este una din abscisele x;

APROXIMARE UNIFORM

Economizare Cebev

Polinoamele Cebev se pot folosi pentru a

reduce gradul polinomului de aproximare, cu o

pierdere minim de precizie.

Funciile se aproximeaz prin polinoame Taylor:

cu restul aproximrii

cu

Polinoamele Taylor produc o aproximare bun n vecintatea lui x0 , dar precizia lor scade rapid pe

msur ce x se indeprteaz de x0.

)x(f!n

)xx()x(f

!2

)xx()x(f

!1

)xx()x(f)x(P

0

)n(

n

0

0

2

0

0

0

0n

1n

0

)1n(

n)xx(

)!1n(

)(f)x(P)x(f

00xxx

APROXIMARE UNIFORM

Intruct polinoamele Cebev prezint un minim al

normei aproximrii uniforme; ele pot fi folosite

pentru reducerea gradului polinomului Taylor fr a

depi tolerana impus erorii.

n polinomul Taylor Pn se nlocuiete puterea cea

mai mare xn cu o combinaie de polinoame Cebev

i se neglijeaz termenul coninnd pe Tn(x) ,

comind prin aceasta o eroare care se majoreaz

prin:

De exemplu pentru funcia f(x)=ex, pentru care se

admite o toleran a erorii Emax=0.005, polinomul

Taylor de grad 4 pentru o dezvoltare n vecintatea

lui 0 este:

nnna)x(Ta

APROXIMARE UNIFORM

Majorarea erorii pentru x[-1,1] este:

Pentru a reduce gradul polinomului de aproximare, nlocuim puterea cea mai mare x4 cu

o combinaie de polinoame Cebev:

24

x

6

x

2

xx1)x(P

432

4

05.0023.0120

e

!5

x)(f)x(P)x(f

5)5(

4

)x(T8

1)x(T

2

1)x(T

24

1

6

x

2

xx1)x(P

420

32

4

)x(T192

1)1x2(

48

1

64

1

6

x

2

xx1

4

2

32

)x(T192

1

6

xx

24

13x

192

1914

3

2

APROXIMARE UNIFORM

Prin neglijarea termenului T4(x) se comite o

eroare majorat de:

nu depete tolerana admis.

005.0192

1)x(T

192

14

05.0E028.0005.0023.0)x(T192

1)x(R

max44