3.2.43 Polinômio interpolador é o nome dado ao polinômio de grau (n-1) determinado por (e que passa através de) n pontos, ( x_{i}, y_{i} ) com todos os x_{i} distintos. Esse polinômio interpolador forma uma base para quadraturas numéricas.
(a) Mostre que exigir que um polinômio de grau (n-1) em x passe por cada um dos n pontos ( x_{i}, y_{i} ) com todos os x_{i} distintos resulta em n equações simultâneas da forma
\sum_{j=0}^{n-1} a_{j} x_{i}^{j}=y_{i}, \quad i=1,2, \ldots, n
(b) Escreva um programa de computador que lerá n pontos de dados e retornará os n coeficientes a_{j}. Se houver uma sub-rotina disponível, use-a para resolver equações simultâneas.
(c) Reescreva o conjunto de equações simultâneas como uma equação matricial
\mathbf{X A}=\mathbf{Y} .
(d) Repita o cálculo de computador da parte (b), mas, desta vez, resolva para o vetor \mathbf{A} invertendo a matriz X (novamente, usando uma sub-rotina).

Passo 1

O enunciado pede para construir o polinômio interpolador de grau n-1 que passa pelos pontos (x_i,y_i), com todos os x_i distintos, e aí
1. Mostrar que isso gera n equações lineares em \{a_j\}.
2. Escrever um pseudocódigo que leia os n pontos e devolva os coeficientes a_j usando uma sub-rotina de solução de sistemas.
3. Reescrever esse sistema na forma matricial \mathbf X\,\mathbf A=\mathbf Y.
4. Resolver o mesmo usando inversão de \mathbf X.

Passo 2

Para um polinômio de grau n-1 escrevemos
p(x)=\sum_{j=0}^{n-1}a_j\,x^j.
Exigir p(x_i)=y_i para cada i=1,2,\dots,n dá exatamente
\sum_{j=0}^{n-1}a_j\,x_i^j = y_i,\quad i=1,2,\dots,n,
ou seja, n equações lineares em n incógnitas \{a_j\}.

Passo 3

Um pseudocódigo simples que lê n pontos e retorna o vetor de coeficientes \mathbf{A}=(a_0,\dots,a_{n-1})^\mathsf{T} é:
ler \(n\)
para \(i\) de \(1\) até \(n\)
  ler \(x[i], y[i]\)
para \(i\) de \(1\) até \(n\)
  para \(j\) de \(0\) até \(n-1\)
    M[i][j+1] \leftarrow x[i]^j
chamar subrotina \(solve\_linear\_system\)(M, y, A)
imprimir A
Aqui solve\_linear\_system(M,y,A) preenche o vetor A tal que M \cdot A = y.

Passo 4

Definindo o vetor coluna
\mathbf A = \begin{pmatrix}a_0\a_1\\vdots\a_{n-1}\end{pmatrix},\quad \mathbf Y = \begin{pmatrix}y_1\y_2\\vdots\y_n\end{pmatrix},
e a matriz de Vandermonde
\mathbf X = \begin{pmatrix} 1 & x_1 & x_1^2 & \cdots & x_1^{\,n-1}\\\\ 1 & x_2 & x_2^2 & \cdots & x_2^{\,n-1}\\\ \vdots & \vdots & \vdots & & \vdots\\\\ 1 & x_n & x_n^2 & \cdots & x_n^{\,n-1} \end{pmatrix},
o sistema fica simplesmente
\mathbf X\,\mathbf A = \mathbf Y.

Passo 5

Em vez de chamar diretamente uma subrotina de sistema linear, podemos inverter \mathbf{X} (supondo-a não singular) e computar
\mathbf{A} = \mathbf{X}^{-1} \, \mathbf{Y}.
No pseudocódigo, bastaria trocar
chamar \(solve\_linear\_system\)(M,y,A)
por
invX \leftarrow chamar subrotina \(invert\_matrix\)(M)
A   \leftarrow invX \cdot y

Resposta

(a) Substituindo p(x)=\sum_{j=0}^{n-1}a_jx^j em p(x_i)=y_i obtemos
\sum_{j=0}^{n-1}a_j\,x_i^j = y_i,\quad i=1,\dots,n.
(b) Pseudocódigo:
ler \(n\)
para \(i\) de \(1\) até \(n\)
  ler \(x[i], y[i]\)
para \(i\) de \(1\) até \(n\)
  para \(j\) de \(0\) até \(n-1\)
    M[i][j+1] \leftarrow x[i]^j
chamar \(solve\_linear\_system\)(M, y, A)
imprimir A
(c) Na forma matricial, com \mathbf{A}=(a_0,\dots,a_{n-1})^T, \mathbf{Y}=(y_1,\dots,y_n)^T e \mathbf{X} a matriz de Vandermonde, temos
\mathbf{X}\,\mathbf{A} = \mathbf{Y}.
(d) Resolvendo por inversão:
\mathbf{A} = \mathbf{X}^{-1}\,\mathbf{Y},
usando uma sub-rotina de inversão de matriz.

Exercícios de Livros Relacionados