Exercicio_ex6

Autor: Gladys
Data: 24/04/2009

Convolução

A) Convolução baseado na Interpolação de Lagrange. Um algoritmo de convolução linear para multiplicação polinomial baseado sobre o teorema de “Interpolação de Lagrange”.

. Teorema de Interpolação Lagrange :

Dado β0, ..., βn uma serie de n+1 pontos deferentes, e dado ƒ(βi), para i = 0,1,...,n . Há exatamente um polinômio ƒ(p) de ordem “n” o menos que o valor ƒ(βi) quando é evaluado em βi para i = 0,1,...n. O qual esta dado por :

** Falta inserção da Equação**

Consideremos uma seqüência de N-pontos h = {h0 , h1 , ..., hN-1} e uma seqüência de L_pontos x = {x0 , x1 ,...xL-1 }. A convolução linear de h e x pode ser expressado no termos da uma multiplicação polinomial como:

S(p) = h(p) * x(p)

Onde:
h(p) = hN-1 pN-1 + ...+ h1p + h0 x(p) = xl-1 pL-1 + ...+ x1p + x0 s(p) = sL+N-2 pL+N-2 + ...+ s1p + s0

O polinômio da saída s(p) tem grado L+N – 2 e tem L+N-1 pontos deferentes.

S(p) pode ser unicamente determinado por seus L+ N – 1 valores de pontos deferentes. Dado { β0, β1,..., βL+N-2 }que é L+N-1 números reais diferentes.

Se s(p) para i = {0,1,...,L+N-2}, então computado usando o Teorema de Interpolação de Lagrange como:

s(p) = Isto pode ser provado dado os valores de s(βi) , para i = {0,1,..., L+N-2}

Descrição do algoritmo:(Seudo Codigo)

  1. Escolher L+N-1 números reais diferentes β0, β1,..., βL+N-2
  2. Computar h(βi ) e x(βi), para i= {0,1,...L+N-2}
  3. Computar s(βi) = h(βi)*x(βi), para i = {0,1,...L+N-2}
  4. Computar s(p) usando a equação do teorema de Interpolação Lagrange

O ALGORITMO MODIFICADO DO TEOREMA DE INTERPOLAÇÃO DE LAGRANGE

Reduce o numero de operações de adição em convoluções lineares.

Esta dada pela equação:

S’ (P) = S(P) – SL+N-2 PL+N-2

Descrição do algoritmo:(Seudo Codigo)

  1. Escolher L+N-2 números reais diferentes β0, β1,..., βL+N-3
  2. Calculo de h(βi ) e x(βi), para i= {0,1,...L+N-3}
  3. Calculo de S(βi) = h(βi)*x(βi), para i = {0,1,...L+N-3}
  4. Calculo de S’(βi )= S(βi) - SL+N-2 βiL+N-2 para i = {0,1,..., L+N-3}
  5. Calculo de S’(p )= usando S’(P) =
  6. Calculo de S(P) = S’(P) + SL+N-2 PL+N-2