TC 708 Análise Numérica Capitulo – IV : Interpolação ... · 1 TC – 708 Análise Numérica Capitulo – IV : Interpolação Polinômios de Bernstein, Lucas Máximo Alves Prof

1

TC TC –– 708 An708 Anáálise Numlise NumééricaricaCapitulo Capitulo –– IV : InterpolaIV : Interpolaçção ão

Polinômios de Bernstein,Polinômios de Bernstein,

Lucas MLucas Mááximo Alvesximo AlvesProf. Antonio Marques CarrerProf. Antonio Marques Carrer

Universidade Federal do ParanUniversidade Federal do Paranáá –– UFPRUFPR

a

b

c

d

2

ConteConteúúdodo•• 1. 1. IntroduIntroduççãoão•• 2.2. Problemas na InterpolaProblemas na Interpolaççãoão PolinomialPolinomial•• 3. Motiva3. Motivaçção ão -- Surgimento Surgimento •• 4. Polinômios de4. Polinômios de BernsteinBernstein•• 5. Propriedades dos Polinômios5. Propriedades dos Polinômios•• 6.6. CCáálculos de Interpolalculos de Interpolaçção e Exemplosão e Exemplos•• 7.7. AplicaAplicaçções e Conclusãoões e Conclusão•• 8. Referências8. Referências

3

1 1 -- INTRODUINTRODUÇÇÃOÃO

•• InterpolaInterpolaççãoão: Linear, : Linear, QuadrQuadrááticatica, , CCúúbicabica

•• EscolhaEscolha dada ordemordem do do polinômiopolinômio de de interpolainterpolaççãoão

4

1 1 -- INTRODUINTRODUÇÇÃOÃO

•• FormaFormageomgeoméétricatricade alguns de alguns

dos dos polinômios polinômios

jjááaprendidosaprendidos

5

2 2 -- PROBLEMAS NA PROBLEMAS NA INTERPOLAINTERPOLAÇÇÃO POLINOMIALÃO POLINOMIAL

•• A interpolaA interpolaçção polinomial ão polinomial éé um metodo fum metodo fáácil e cil e úúnico para descrevercurvasnico para descrevercurvasque contque contéém alguns atributos geomm alguns atributos geoméétricos tricos „„satisfatsatisfatóóriosrios““““..

•• A interpolaA interpolaçção polinomial não polinomial nàào o éé o mo méétodo de escolha dentro de aplicativos todo de escolha dentro de aplicativos como o CAD devido a descricomo o CAD devido a descriçções melhores de curvas (como serões melhores de curvas (como seráá visto mais visto mais tarde).tarde).

Razão:Razão: A interpolaA interpolaçàçào polinômial pode oscilaro polinômial pode oscilar

6

2 2 -- PROBLEMAS DE PROBLEMAS DE INTERPOLAINTERPOLAÇÇÃO POLINOMIALÃO POLINOMIAL

O polinômio interpolante pode oscilar mesmo quando O polinômio interpolante pode oscilar mesmo quando pontos de dados pontos de dados normais normais e os valores dos parametros e os valores dos parametros são usados.são usados.

•• O polinômioO polinômio interpolante não preserva a forma.interpolante não preserva a forma. Isto não Isto não tem nada a ver com os efeitos numtem nada a ver com os efeitos numééricos, ele ricos, ele éé devido devido ao processo de interpolaao processo de interpolaçção.ão.

•• Para processos de interpolaPara processos de interpolaçção de alto custo:ão de alto custo: uma uma enorme quantidade de operaenorme quantidade de operaçções necessões necessáárias para a rias para a construconstruçàçào e co e cáálculo do interpolante.lculo do interpolante.

7

3 3 –– MOTIVAMOTIVAÇÇÃOÃO

•• Este Este éé o Sr. o Sr. BernsteinBernstein

8

3 3 –– MOTIVAMOTIVAÇÇÃOÃO

ObjetivoObjetivo:: MelhorMelhor controlecontrole sobresobre a forma das a forma das curvascurvas

InfraestruturaInfraestrutura: : ComputadoComputado--com com suportesuporte de design de design parapara automautomóóveisveise e areonavesareonaves

BBéézierzier (Renault) e (Renault) e de de CasteljauCasteljau ((CitrCitrööenen) ambos ) ambos foramforam desenvolvidosdesenvolvidosindependentementeindependentemente um do um do outrooutro emem tornotorno dos dos anosanos de 1960/65 de 1960/65 parapara descridescriççõesões de de curvacurva com com osos seguintesseguintes atributosatributos::

•• SubstituSubstituççãoão de de padrõespadrões de de desenhodesenho feitosfeitos pelopelo CADCAD•• ManipulaManipulaççãoão flexflexíívelvel de de curvascurvas com com garantiagarantia e e controlecontrole de forma de forma dada

curvacurva resultanteresultante•• IntroduIntroduççãoão de de pontospontos de de controlecontrole queque nãonão necessariamentenecessariamente

estendeestende--se se sobresobre a a curvacurva

9

CurvasCurvas SuavesSuaves

•• Como Como criarcriar curvascurvas suavessuaves??

10


•• Como Como criarcriar curvascurvas suavessuaves??

•• CurvasCurvas paramparaméétricastricas com com polinômiospolinômios

)(),()( tytxtp

11


•• ControlandoControlando a forma a forma dada curvacurva

32

32

)()(

htgtftetydtctbtatx

12



321)()(

ttttyttx

13


ControlandoControlando a forma a forma dada curvacurva

323)()(

ttttyttx

14



321)()(

ttttyttx

15



321)()(

ttttyttx

16



321)()(

ttttyttx

17



3231)()(

ttttyttx

18



321)()(

ttttyttx

19



321)()(

ttttyttx

20



321)()(

ttttyttx

Os coeficiente de bases de Potências não são intuitivos para o controle da forma da curva!!!

21

3 3 -- SURGIMENTOSURGIMENTO

•• FFóórmula do Binômio de Newtonrmula do Binômio de Newton

n

i

iinn bain

ba0

)(

22

4 4 -- POLINÔMIOS DE BERNSTEINPOLINÔMIOS DE BERNSTEIN

•• DefiniDefiniçção dos Polinômios de Bernsteinão dos Polinômios de BernsteinOs Os PolinômiosPolinômios de Bernstein de de Bernstein de graugrau n n qualquerqualquer sãosão definidosdefinidos parapara

qualquerqualquer graugrau n = 0, 1, 2, n = 0, 1, 2, ……, N,, N,

( ) (1 ) com 0,1 , 0,...,n n i ii

nB t t t t i n

i

! 0!( )!

0 0

n para i nn ni n i

i ipara i n

com com coeficientescoeficientesbinomiaisbinomiaisdado dado porpor::

23

4 4 -- POLINÔMIOS DE BERNSTEINPOLINÔMIOS DE BERNSTEIN

•• ExistemExistem n+1 n+1 PolinômiosPolinômios de Bernstein de de Bernstein de graugraun. n. PorPor exemploexemplo, Os , Os PolinômiosPolinômios de Bernstein de Bernstein de de grausgraus 1, 2, e 3 1, 2, e 3 sãosão::

-- PreferePrefere--se se sobresobre outrasoutras interpolainterpolaççõesões polinomiaispolinomiaisporqueporque: : ÉÉ maismais eficienteeficiente

-- OutrosOutros polinômiospolinômios de altos de altos grausgraus sãosãocomputacionalmentecomputacionalmente maismais caroscaros-- ErrosErros pequenospequenos-- A A curvacurva interpolanteinterpolante éé maismais suavesuave

24

4.1 4.1 -- Bernstein de grau 1Bernstein de grau 1

1 1 0 10

1 1 1 11

1( ) (1 )

0

1( ) (1 )

1

B t t t t

B t t t t

25


2 2 0 20

2 2 1 11

2 2 2 2 22

2( ) (1 ) (1 )

02

( ) (1 ) 2(1 )1

2( ) (1 )

2

B t t t t

B t t t t t

B t t t t

26


3 3 0 30

3 3 1 1 21

3 3 2 2 22

3 3 3 3 33

3( ) (1 ) (1 )

0

3( ) (1 ) 3(1 )

1

3( ) (1 ) 3(1 )

2

3( ) (1 )

3

B t t t t

B t t t t t

B t t t t t

B t t t t

27

5 5 -- PROPRIEDADES DOS PROPRIEDADES DOS POLINÔMIOSPOLINÔMIOS

5.3 5.3 –– RecursividadeRecursividade

( ) (1 )n ni n iB t B t

11( ) (1 ) ( ) ( )n n k n

k k kB t t B t t B t

1,0,0, 1,0)( tnintB ni

5.2 5.2 –– SimetriaSimetria

5.1 5.1 –– IntervaloIntervalo

28

5 5 -- PROPRIEDADES DOS PROPRIEDADES DOS POLINOMIOS DE BERNSTEINPOLINOMIOS DE BERNSTEIN

5.4 5.4 -- PartiPartiççãoão dada unidadeunidade: a : a soma vale soma vale umauma unidadeunidadeparapara qualquerqualquer tt emem [0,1] [0,1] ondeonde ii--vezes nulo em t=0, vezes nulo em t=0, (n(n--i)i)--nulo nulo em t=1nulo nulo em t=1

Prova:Prova:

0,1t 1)(0 n

ini tB

0 0

1 1

1 ( )

n

n nn i i nii i

t t

nt t B t

i

29

n n-1 n-1n! = = + i i i-1i!(n - i)!

00 : : 1

01 1

1: , : 1 + 10 12 2 2

2 : , , : 1 + 2 + 10 1 23 3 3 3

3: , , , : 1 + 3 + 3 +10 1 2 34 4 4 4

4 : , , ,0 1 2

4, : 1 + 4 + 6 + 4 + 1

3 1:

n n n n n n: , ,...., , , ,...., : 1,(n-1)+(i-1),(n-1+i),...,1

0 1 k-1 k k+1 ni

••5.4 5.4 -- nn escolhasescolhas I do I do TrianguloTriangulo de de Pascal Pascal

1: 11,1: 1 + 11,2,1: 1 + 2 + 11,3,1: 1 + 3 + 3 +11,4,6,4,1: 1 + 4 + 6 + 4 + 1:1, n, ...,(n-1)+(i-1),(n-1+i),...,1

30

5.5 5.5 -- ConstruConstruççãoão do do PolinômiosPolinômiosde Bernsteinde Bernstein

Bin(t) = (1-t)Bi

n-1(t) + tBin--1

1(t)

= +

=

B02(t) = (1-t) B0

1(t)

=

B12(t) = (1-t) B1

1(t) + t B01(t)

B22(t) = t B1

1(t)

11( ) (1 ) ( ) ( )n n k n

k k kB t t B t tB t

31

5.6 5.6 -- CCáálculo Recursivolculo Recursivo1

1

0

( ) : (1 ) ( ) ( )1 para i = 0

( ) : 0 para i 0

r r ri i i

i

B t t B t t B t

B t

i n-ii,n

i n-i i n-i

i,n-1 i-1,n-1

nB ( ) = t (1-t)

i

n-1 n-1= t (1-t) + t (1-t)

i i-1= (1-t)B ( ) + tB ( )

t

t t

5.6 5.6 -- GrausGraus maismais altos altos lerpslerps de de grausgraus inferioresinferiores

32

5.6 5.6 -- Base de FunBase de Funçções dos ões dos Polinômios dePolinômios de BernsteinBernstein

Exemplo: Polinômios de Bernstein de Graus 1-3

33

Metodos de AproximaMetodos de Aproximaçção:ão: Curvas e Curvas e Polinômios BPolinômios Béézierzier

6. C6. CÁÁLCULO DE INTERPOLALCULO DE INTERPOLAÇÇÃOÃO

De acordo com De acordo com esta definiesta definiçção as ão as curvas de Bcurvas de Béézierziersão calculadassão calculadascom a ajuda dos com a ajuda dos polinômios de polinômios de Bernstein.Bernstein.

ExemploExemplo de uma curva cde uma curva cúúbicabica BBéézierzier

34


•• Dado Dado umauma sséérierie de de pontospontos de de controlecontroleondeonde

•• DefiniDefiniççãoão: : UmaUma curvacurva Bezier de Bezier de graugrau N N éé::

OndeOnde parapara i = 0, 1, i = 0, 1, ……, N, , N, sãosãoosos polinômiospolinômios de Bernstein de de Bernstein de graugrau N.N.

-- P(tP(t) ) éé a a curvacurva de Bezier.de Bezier.

-- UmaUma vezvez queque::

•• ÉÉ ffáácilcil modificarmodificar as as curvascurvas se se osos pontospontossãosão acrescentadosacrescentados

,0

( ) ( )N

i n ii

x t x B t

,0

( ) ( )N

i n ii

y t y B t

( , )i i iP x y

0N

i iP

,0

( ) ( )B

i n ii

P t PB t

, ( )n iB t

6.1 6.1 -- InterpolaInterpolaççãoão de de umauma curvacurva BezierBezier

35


•• ProblemaProblema: : Ache a Ache a curvacurva Bezier Bezier queque possuipossui osos seguintesseguintes pontospontos de de controlecontrole {({(x,yx,y)={ (2,2), (1,1.5), (3.5,0), (4,1)}.)={ (2,2), (1,1.5), (3.5,0), (4,1)}.

•• SoluSoluççãoão:: SubstituiSubstitui--se as se as coordenadascoordenadas xx-- e ye y-- dos N=3 dos N=3 pontospontos de de controlecontrole dentrodentro das das ffóórmulasrmulas x(tx(t) e ) e y(ty(t):):

3 3 3 30 1 2 33 3 3 30 1 2 3

( ) 2 ( ) 1 ( ) 3.5 ( ) 4 ( )

( ) 2 ( ) 1.5 ( ) 0 ( ) 1 ( )

x t B t B t B t B t

y t B t B t B t B t

36


( ) [ ]( ) / [ ]( ) /( ) [ ]( ) / [ ]( ) /

/( )/

x t P x t dy dy dt dP x t dty t P y t dx dx dt dP y t dt

dy dt dyy x y dx dxdx dt dx

•• CCáálculandolculando o o polinômiopolinômio quequeajustaajusta a a funfunççãoão::

y = y = f(xf(x))

37

6.1. Exemplo6.1. Exemplo

38


39


40


41


42

7 7 -- APLICAAPLICAÇÇÕES E CONCLUSÃOÕES E CONCLUSÃO

•• CCáálculo por Matrizes lculo por Matrizes –– ResoluResoluçção de ão de Sistemas LinearesSistemas Lineares

•• Ver Exemplo MAPLEVer Exemplo MAPLE

43

6.1 6.1 -- InterpolaInterpolaççãoão CCúúbicabica: : MatrizMatriz4x44x4

3 2 2 30 1 2 3

0

13 2

2

3

( ) (1 ) [3 (1 ) ] [3 (1 )]

?1

F t P t P t t P t t PtPPM

t t tPP

44

6.1 6.1 -- InterpolaInterpolaççãoão CCúúbicabica: : MatrizMatriz4x4 4x4

3 2 2 30 1 2 3

0

13 2

2

3

( ) (1 ) [3 (1 ) ] [3 (1 )]1 3 3 1

3 6 3 01

3 3 0 01 0 0 0

F t P t P t t P t t PtPP

t t tPP

45

•• Ache um Ache um polinômiopolinômio queque passapassa pelospelosvaloresvalores especificadosespecificados

32)( dtctbtaty

InterpolaInterpolaççãoão

y

t

46

InterpolationInterpolation


y

t

32)( dtctbtaty 3)0( ay

1)1( dcbay3842)2( dcbay12793)3( dcbay

47



y

t

32)( dtctbtaty

1313

27931842111110001

dcba

48

InterpolationInterpolation


y

t

32)( dtctbtaty

31

320

6

3

dcba

49



y

t

Controle intuitivo de curvasusando “pontos de controles”!!!

50


•• ExecutaExecuta a a interpolainterpolaççãoão parapara cadacada componentecomponenteseparadamenteseparadamente

•• CombinaCombina o o resultadoresultado parapara obterobter a a curvacurva parametricaparametrica

y

)(),()( tytxtp

51


•• ExecutaExecuta a a interpolainterpolaççãoão parapara cadacada componentecomponenteseparadamenteseparadamente

•• CombinaCombina o o resultadoresultado parapara obterobter a a curvacurvaparametricaparametrica

y

)(),()( tytxtp

52

InterpolaInterpolaççãoão•• ExecutaExecuta a a interpolainterpolaççãoão parapara cadacada componentecomponente

separadamenteseparadamente•• CombinaCombina o o resultadoresultado parapara obterobter a a curvacurva

parametricaparametrica

y

x

)(),()( tytxtp

53

7.1 7.1 -- AplicaAplicaççãoão nana ComputaComputaççãoãoGrGrááficafica

Interpolation Interpolation BezierBezier

54

7.2 7.2 –– AplicaAplicaççãoão nana ComputaComputaççãoãoGrGrááficafica

•• DesenhosDesenhos 3D (Pipeline)3D (Pipeline)Rendering

(Criando, sombreando imagensa partir da geometria, iluminando, materiais)

Modelagem (CriandoGeometrias 3D)

55

7.3 7.3 -- AplicaAplicaçção na Indão na IndúústriastriaAplicaAplicaçções Tões Tíípicas são:picas são:•• Design de Carros,Design de Carros, Aeronaves,Aeronaves, e Naviose Navios•• SimulaSimulaççãoão dede MovimentosMovimentos•• AnimaAnimaçções,ões, IndIndúústria de Cinema e Computastria de Cinema e Computaçção Grão Grááficafica

Modelagem de objetos com superfícies de formas livres

56

8 8 -- REFERÊNCIASREFERÊNCIAS

•• http://www.sbg.ac.at/mat/staff/revers/revhttp://www.sbg.ac.at/mat/staff/revers/revers07.htmlers07.html

•• http://www.cse.uiuc.edu/iem/interpolationhttp://www.cse.uiuc.edu/iem/interpolation/brnstein//brnstein/

•• http://en.wikipedia.org/wiki/Bernstein_polhttp://en.wikipedia.org/wiki/Bernstein_polynomialynomial

•• KennethKenneth I. I. JoyJoy, Bernstein , Bernstein PolynomialsPolynomials, On, On--Line Line GeometricGeometric NotesNotes

57

OBRIGADO!OBRIGADO!BEVAKASHA!BEVAKASHA!

58

i,n0

0,3 1,3 2,3 3,3

B ( )=0 + 1/3 + 2/3 =1

p(t)=aB ( )+bB ( )+cB ( )+dB ( )

n

it

t t t t

59


Metodos de AproximaMetodos de Aproximaçção:ão: Polinômios BPolinômios Béézierzier

De acordo com esta De acordo com esta definidefiniçção as curvas de ão as curvas de BBéézierzier são calculadassão calculadascom a ajuda dos com a ajuda dos polinômios de polinômios de Bernstein.Bernstein. ExemploExemplo de uma curva cde uma curva cúúbicabica BBéézierzier

Documents

TC 708 Análise Numérica Capitulo – IV : Interpolação ... · 1 TC – 708 Análise Numérica Capitulo – IV : Interpolação Polinômios de Bernstein, Lucas Máximo Alves Prof