BCM0505-15 - Processamento da Informação

Aula A05 – 08/05: Polinômios em Vetores

• Polinômios em uma variável: avaliação, adição, multiplicação, derivação e integração simbólicas.
• Aplicações e método de Newton-Raphson para cálculo de raízes.

Representando e Operando com Polinômios

Um polinômio $P$ de grau $n\geq 0$ em uma variável $x$ é uma expressão da forma $$P = p_{n}x^{n} + p_{n-1}x^{n-1} + \cdots + p_{1}x + p_0,$$ em que os coeficientes $p_i\in\mathbb{R}$ e $p_n\neq 0$. Denotamos o grau de $P$ por $\mathsf{deg}(P)=n$.

Ao polinômio $P$, podemos associar a função polinomial $P(x):\mathbb{R}\to\mathbb{R}$ que avalia $P$ em um ponto $x\in\mathbb{R}$.
Uma representação simples para $P$ consiste em utilizar uma lista $p[0\,..n]$ de pontos flutuantes tal que $p[i]=p_i$.
Observe que, com esta representação, temos len (p)$\,=n+1=\mathsf{deg}(P)+1$.

Exemplo: se $P(x) = 2x^3-x^2+4x-1$, temos que $p=[-1,4,-1,2]$; além disso, $P(0)=-1$ e $P(1)=2-1+4-1=4$.

Problema A5.1: Dados uma lista $p[0\,..n]$ representando um polinômio $P$ e um ponto $x\in\mathbb{R}$, avalie $P$ em $x$.

def poly_eval (p: [float], x: float) -> float:
  r, y = 0.0, 1.0
  for a in p:
    r += a*y
    y *= x
  return r

O tempo consumido pelo algoritmo acima é $\Theta(n)$.

Podemos re-escrever $P(x)$ de maneira recorrente como $$P(x) = p_0 + x(p_1 + x(p_2 + x(p_3 + \cdots + x(p_{n-1} + xp_n) \cdots ))),$$ conhecida como forma de Horner. Podemos, então, escrever a avaliação de $P(x)$ como segue.

def poly_horner (p: [float], x: float) -> float:
  r = p[-1]
  for a in reversed (p[:-1]):
    r = a + x*r
  return r

Claramente, o tempo consumido pela avaliação na forma de Horner também é $\Theta(n)$, mas somente metade do número de multiplicações são realizadas.

Nota: Em Python, podemos indexar uma lista de trás para frente utilizando índices negativos. O acesso p[-1] equivale a p[len(p)-1], p[-2] equivale a p[len(p)-2], e assim sucessivamente, até p[-len(p)] == p[0].

Problema A5.2: Dados im polinômio $P$ e um ponto flutuante $c$, determine $cP$.

def poly_scalar (p: [float], c: float) -> [float]:
  for i in range (len (p)): p[i] *= c
  return p

Claramente, o tempo consumido pelo algoritmo acima é $\Theta(n)$.

Problema A5.3: Dados dois polinômios $P$ e $Q$, representados respectivamente por $p[0\,..m-1]$ e $q[0\,..n-1]$, determine $P+Q$.

Temos que $P+Q$ é um polinômio de grau $\max\{\mathsf{deg}(P),\mathsf{deg}(Q)\}=\max\{m,n\}-1$.

def poly_sum (p: [float], q: [float]) -> [float]:
  m, n = len (p), len (q)
  r = [0] * max (m, n)
  for i in range (min (m, n)):
    r[i] = p[i] + q[i]    
  if m <= n: R[m:n] = Q[m:n] 
  else     : R[n:m] = P[n:m]
  return r

O tempo consumido pelo algoritmo acima é $\Theta(\max\{m,n\})$.

Problema A5.4: Dados dois polinômios $P$ e $Q$, representados respectivamente por $p[0\,..m-1]$ e $q[0\,..n-1]$, determine $P*Q$.

Temos que $P*Q$ é um polinômio de grau $\mathsf{deg}(P) + \mathsf{deg}(Q) = m+n-2$.
Versão semelhante à multiplicação de dois inteiros (aprendida na escola).

def poly_product (p: [float], q: [float]) -> [float]:
  m, n = len (p), len (q)
  r = [0] * (m + n - 2)
  for i in range (m):
    for j in range (n):
      r[i+j] += p[i] * q[j]
  return r

O tempo consumido pelo algoritmo acima é $\Theta(mn)$.

Prestando atenção, vemos que o coeficiente do termo de grau $k$ em $R=P*Q$ é dado por $$r[k] = \sum_{i=0}^{k} p[i]*q[k-i],$$ se supormos que $p[i]=0$ quando $i>m-1$ e que $q[k-i]=0$ quando $k-i>n-1$.
Temos então uma versão baseada em convoluções.

def poly_product (p: [float], q: [float]) -> [float]:
  m, n = len (p), len (q)
  r = [0] * (m + n - 2)
  for k in range (m + n - 1):
    for i in range (k + 1):
      r[k] += (p[i] if i < m else 0) * (q[k-i] if k-i < n else 0)
  return r

Não é difícil construir uma versão mais elegante que elimina os ifs às custas de um cálculo mais preciso dos limites das convoluções.

def poly_product (p: [float], q: [float]) -> [float]:
  m, n = len (p), len (q)
  r = [0] * (m + n - 2)
  for k in range (m + n - 1):
    for i in range (k - min (k, n-1), min (k, m-1) + 1):
      r += p[i] * q[k-i]
  return r

Exercício 1: Mostre que

range (k - min (k, n-1), min (k, m-1) + 1) == range (max (0, k-n+1), min (k+1, m))

podendo o lado direito ser substituído no lugar do lado esquerdo código acima.

O tempo consumido pela variante utilizando convoluções também é $\Theta(mn)$. A estrutura, no entanto, é mais interessante pois permite calcularmos o coeficiente de uma determinada potência sem ter de calcular os coeficientes das demais.

Nota: É possível computar $P*Q$ em tempo $O(\ell\log\ell)$, com $\ell=\max\{m,n\}$, utilizando-se a Transformada Rápida de Fourier.

Problema A5.5: Dado um polinômio $P$ de grau $n$ em uma variável $x$, determine a derivada simbólica de $P$ com relação a $x$, $$P'(x) = \frac{d}{dx}P(x) = \sum_{i=1}^{n} ip_ix^{i-1} = p_1 + 2p_2x + 3p_3x^2 + \cdots + np_nx^{n-1}.$$

Temos que $P'$ é um polinômio de grau $\mathsf{deg}(P) - 1$.

def poly_derivative (p: [float]) -> [float]:
  return [(i*p[i]) for i in range (1, len (p))]

Claramente, o tempo consumido pelo algoritmo acima é $\Theta(n)$.

Problema A5.6: Dados um polinômio $P$ de grau $n$ em uma variável $x$ e uma constante $c\in\mathbb{R}$, determine a integral simbólica de $P$ com relação a $x$, $$\widetilde{P}(x) = \int P(x)dx = c + \sum_{i=0}^{n} \frac{p_i}{i+1}x^{i+1} = c + p_0x + \frac{p_1}{2}x^2 + \frac{p_2}{3}x^3 + \cdots + \frac{p_n}{n+1}x^{n+1}.$$

Temos que $\widetilde{P}$ é um polinômio de grau $\mathsf{deg}(P) + 1$.

def poly_integral (p: [float], c: float) -> [float]:
  r = [(p[i]/(i+1)) for i in range (len (p))]
  r.insert (0, c)  
  return r

Claramente, o tempo consumido pelo algoritmo acima é $\Theta(n)$.

Cálculo de Raízes via Newton-Raphson

Problema A5.7: Dados um polinômio $P$ de grau $n$ em uma variável $x$ e um valor inicial $x_0\in\mathbb{R}$, determine uma aproximação para uma raiz real da equação $P(x)=0$ na “vizinhança” de $x_0$ via método de Newton-Raphson.

O método consiste na avaliação da seguinte equação de diferenças: $$x_{k} = x_{k-1} - \frac{P(x_{k-1})}{P'(x_{k-1})},$$ em que $x_0$ é dado e $P'$ é a derivada de $P$ com relação a $x$. Iterativamente, geramos a sequência $$x_0,x_1,x_2,\ldots,x_{k-1},x_{k},\ldots$$ Se $|x_{k}-x_{k-1}|\to 0$, temos que $x_{k}\to y$, em que $P(y)=0$; isto é, $x_k$ converge para uma raiz de $P$.
As condições técnicas necessárias para garantia de convergência do método não serão consideradas neste problema.

Como de costume, esperamos receber um fator de precisão $0<\varepsilon\ll 1$ e calcular $x_k$ até que $|x_{k}-x_{k-1}|<\varepsilon.$ Para o caso em que não ocorra convergência a uma raiz de $P$, vamos receber um inteiro positivo $\ell$ para limitar superiormente o comprimento da sequência gerada.

def poly_newton_raphson (p: [float], xj: float, l: int, eps: float) -> float:
  dp = poly_derivative (p)
  while l > 0:
    xk = xj - poly_horner (p, xj) / poly_horner (dp, xj)
    if abs (xk - xj) < eps: break
    xj, l = xk, l-1
  return xk, l

Caso o valor $\ell$ devolvido seja não nulo, $x_k$ é uma aproximação a uma raiz de $P$ na vizinhança de $x_0$. Caso $\ell=0$, o laço chegou ao final; ou o valor de $\ell$ fornecido foi muito pequeno e precisa ser aumentado, ou a sequência diverge.

Problema A5.8: Dados um inteiro $n\geq 1$ e um $z\in\mathbb{R}$, calcule $\sqrt[n]{z}$, a raiz $n$-ésima de $z$.

Temos que $$x=\sqrt[n]{z} \iff x^n = z \iff x^n - z = 0.$$ Claramente, $x^n-z$ é um polinômio de grau $n$ e queremos determinar, assim, uma raiz de uma equação polinomial.

def nth_root (n: int, z: float) -> float:
  p = [0] * (n+1)
  p[0], p[n] = -z, 1
  return poly_newton_raphson (p, z, 100, 1e-8)

No código acima, 100 é o limite superior no número de passos e 1e-8$\,= 10^{-8}$ implica em precisão na oitava casa decimal.

A título de exemplo, compare os valores impressos pelo código abaixo:

>>> print (nth_root (2,2))
(1.4142135623730951, 96)
>>> print (math.sqrt (2))
1.4142135623730951

Observe que nth_root determinou o valor em $5$ passos.

Polinômios Esparsos

O método de representação utilizado até então é conveniente quando o polinômio $P$ é denso, isto é, tem poucos coeficientes iguais a zero. Caso $P$ seja esparso, como no Problema A5.8, a representação é custosa em excesso.

Nota: Formalmente, um polinômio $P$ de grau $n$ em uma variável é esparso se, para toda constante $c>0$, o número de coeficientes diferentes de zero é menor que $cn$.

Uma representação alternativa e mais econômica neste caso consiste em uma lista ordenada de pares: para cada termo $p_ix^i$ de $P$, armazena-se o par $(i, p_i)$ na lista $p$. A lista $p$ é mantida em ordem crescente via $i$.

Exemplo: se $P(x) = 2x^{20}-x^5+4x-1$, temos que $p=[(0,-1),(1,4),(5,-1),(20,2)]$.

Nesta representação, o grau de $P$ é obtido por: p[-1][0].
O [-1] refere-se ao último elemento de $p$, o par $(20,2)$, e o [0] refere-se ao primeiro elemento do par, $20$ no caso.

Não é difícil construir variações às funções de avaliação, soma, multiplicação, derivação e integração de polinômios nesta representação. Aliás, elas serão focos de exercícios. Observe que, uma vez feito isso, a função poly_newton_raphson não precisa ser modificada (a menos da anotação de tipo p: [float]). Claramente, isso se deve ao fato da função não utilizar diretamente a representação do polinômio passado como parâmetro. Temos aqui um primeiro exemplo dos conceitos de abstração e encapsulamento, comuns a tipos de dados e programação orientada a objetos.