Algoritmo Paramétrico

Um polinómio ou função polinomial é uma expressão sob a forma

$P(x)=\lambda _{n}\,x^{n}\,+\,\lambda _{n-1}\,x^{n-1}\,+\,\lambda _{n-2}\,x^{n-2}\,+\,\lambda _{n-3}\,x^{n-3}\,+\,...\,+\,\lambda _{3}\,x^{3}\,+\,\lambda _{2}\,x^{2}\,+\,\lambda _{1}\,x\,+\,\lambda _{0}$

Qualquer polinómio é suscetível ao processo de divisão,

${\frac {\text{dividendo}}{\text{divisor}}}={\text{quociente}}+{\text{resto}}$

Querendo encontrar um binómio divisor do tipo $(x+\pi ),\,\pi \in \mathbb {Q}$, que devolva um quociente com um polinómio de grau inferior e resto zero, ou seja,

$P'(x)=\lambda '_{n-1}\,x^{n-1}\,+\,\lambda '_{n-2}\,x^{n-2}\,+\,\lambda '_{n-3}\,x^{n-3}\,+\,\lambda '_{n-4}\,x^{n-4}\,+\,...\,+\,\lambda '_{3}\,x^{3}\,+\,\lambda '_{2}\,x^{2}\,+\,\lambda '_{1}\,x\,+\,\lambda '_{0}$

deve-se satisfazer o valor de $\pi$ de modo a que se obtenha a igualdade

$P(x)=(x+\pi )\,P'(x)\quad {\text{(1)}}$

Trabalhando com o segundo membro, desenvolve-se a expressão,

$(x+\pi )\,P'(x)=xP'(x)+\pi P'(x)=$

$=(x\lambda '_{n-1}\,x^{n-1}\,+\,x\lambda '_{n-2}\,x^{n-2}\,+\,x\lambda '_{n-3}\,x^{n-3}\,+\,x\lambda '_{n-4}\,x^{n-4}\,+\,...\,+\,x\lambda '_{3}\,x^{3}\,+\,x\lambda '_{2}\,x^{2}\,+\,x\lambda '_{1}\,x\,+\,x\lambda '_{0})\ +\ (\pi \lambda '_{n-1}\,x^{n-1}\,+\,\pi \lambda '_{n-2}\,x^{n-2}\,+\,\pi \lambda '_{n-3}\,x^{n-3}\,+\,\pi \lambda '_{n-4}\,x^{n-4}\,+\,...\,+\,\pi \lambda '_{3}\,x^{3}\,+\,\pi \lambda '_{2}\,x^{2}\,+\,\pi \lambda '_{1}\,x\,+\,\pi \lambda '_{0})=$

Como uma das parcelas é $x$ a multiplicar pelo polinómio $P'(x)$, este sobre de grau,

$=(\lambda '_{n-1}\,x^{n}+\,\lambda '_{n-2}\,x^{n-1}\,+\,\lambda '_{n-3}\,x^{n-2}\,+\,\lambda '_{n-4}\,x^{n-3}\,+\,...\,+\,\lambda '_{3}\,x^{4}\,+\,\lambda '_{2}\,x^{3}\,+\,\lambda '_{1}\,x^{2}\,+\,\lambda '_{0}x)\ +\ (\pi \lambda '_{n-1}\,x^{n-1}\,+\,\pi \lambda '_{n-2}\,x^{n-2}\,+\,\pi \lambda '_{n-3}\,x^{n-3}\,+\,\pi \lambda '_{n-4}\,x^{n-4}\,+\,...\,+\,\pi \lambda '_{3}\,x^{3}\,+\,\pi \lambda '_{2}\,x^{2}\,+\,\pi \lambda '_{1}\,x\,+\,\pi \lambda '_{0})=$

Agrupando as incógnitas do mesmo grau,

$=\lambda '_{n-1}\,x^{n}\,+\,(\lambda '_{n-2}\,x^{n-1}\,+\,\pi \lambda '_{n-1}\,x^{n-1})\,+\,(\lambda '_{n-3}\,x^{n-2}\,+\,\pi \lambda '_{n-2}\,x^{n-2})\,+\,(\lambda '_{n-4}\,x^{n-3}\,+\,\pi \lambda '_{n-3}\,x^{n-3})\,+\,\,...\,+\,(\lambda '_{2}\,x^{3}\,+\,\pi \lambda '_{3}\,x^{3})\,+\,(\lambda '_{1}\,x^{2}\,+\,\pi \lambda '_{2}\,x^{2})\,+\,(\lambda '_{0}\,x\,+\,\pi \lambda '_{1}\,x)\,+\,\pi \lambda '_{0}=$

Colocando as incógnitas em evidência,

$=\lambda '_{n-1}\,x^{n}\,+\,(\lambda '_{n-2}\,+\,\pi \lambda '_{n-1})\,x^{n-1}\,+\,(\lambda '_{n-3}\,+\,\pi \lambda '_{n-2})\,x^{n-2}\,+\,(\lambda '_{n-4}\,+\,\pi \lambda '_{n-3})\,x^{n-3}\,+\,...\,+\,(\lambda '_{2}\,+\,\pi \lambda '_{3})\,x^{3}\,+\,(\lambda '_{1}\,+\,\pi \lambda '_{2})\,x^{2}\,+\,(\lambda '_{0}\,+\,\pi \lambda '_{1})\,x\,+\,\pi \lambda '_{0}$

Daqui, igualam-se os termos de igual ordem do primeiro e segundo membro da equação,

$P(x)=(x+\pi )\,P'(x)\Leftrightarrow$

$\Leftrightarrow {\begin{cases}\lambda _{n}\,x^{n}=\lambda '_{n-1}\,x^{n}\\\lambda _{n-1}\,x^{n-1}=(\lambda '_{n-2}+\pi \lambda '_{n-1})\,x^{n-1}\\\lambda _{n-2}\,x^{n-2}=(\lambda '_{n-3}+\pi \lambda '_{n-2})\,x^{n-2}\\\lambda _{n-3}\,x^{n-3}=(\lambda '_{n-4}+\pi \lambda '_{n-3})\,x^{n-3}\\\lambda _{n-4}\,x^{n-4}=(\lambda '_{n-5}+\pi \lambda '_{n-4})\,x^{n-4}\\\vdots \\\lambda _{4}\,x^{4}=(\lambda '_{3}+\pi \lambda '_{4})\,x^{4}\\\lambda _{3}\,x^{3}=(\lambda '_{2}+\pi \lambda '_{3})\,x^{3}\\\lambda _{2}\,x^{2}=(\lambda '_{1}+\pi \lambda '_{2})\,x^{2}\\\lambda _{1}\,x=(\lambda '_{0}+\pi \lambda '_{1})\,x\\\lambda _{0}=\pi \lambda '_{0}\\\end{cases}}\quad \Leftrightarrow$ $\quad {\begin{cases}\lambda _{n}=\lambda '_{n-1}\\\lambda _{n-1}=\lambda '_{n-2}+\pi \lambda '_{n-1}\\\lambda _{n-2}=\lambda '_{n-3}+\pi \lambda '_{n-2}\\\lambda _{n-3}=\lambda '_{n-4}+\pi \lambda '_{n-3}\\\lambda _{n-4}=\lambda '_{n-5}+\pi \lambda '_{n-4}\\\vdots \\\lambda _{4}=\lambda '_{3}+\pi \lambda '_{4}\\\lambda _{3}=\lambda '_{2}+\pi \lambda '_{3}\\\lambda _{2}=\lambda '_{1}+\pi \lambda '_{2}\\\lambda _{1}=\lambda '_{0}+\pi \lambda '_{1}\\\lambda _{0}=\pi \lambda '_{0}\\\end{cases}}\quad {\text{(I)}}\quad \Leftrightarrow \quad$ Igualando os coeficientes $\lambda '$ por ordem crescente, $\quad \Leftrightarrow {\begin{cases}\displaystyle \lambda '_{0}={\frac {\lambda _{0}}{\pi }}\\\displaystyle \lambda '_{1}={\frac {\lambda _{1}-\lambda '_{0}}{\pi }}\\\displaystyle \lambda '_{2}={\frac {\lambda _{2}-\lambda '_{1}}{\pi }}\\\displaystyle \lambda '_{3}={\frac {\lambda _{3}-\lambda '_{2}}{\pi }}\\\displaystyle \lambda '_{4}={\frac {\lambda _{4}-\lambda '_{3}}{\pi }}\\\vdots \\\displaystyle \lambda '_{n-4}={\frac {\lambda _{n-4}-\lambda '_{n-5}}{\pi }}\\\displaystyle \lambda '_{n-3}={\frac {\lambda _{n-3}-\lambda '_{n-4}}{\pi }}\\\displaystyle \lambda '_{n-2}={\frac {\lambda _{n-2}-\lambda '_{n-3}}{\pi }}\\\displaystyle \lambda '_{n-1}={\frac {\lambda _{n-1}-\lambda '_{n-2}}{\pi }}=\lambda _{n}\\\displaystyle \lambda '_{n}={\frac {\lambda _{n}-\lambda '_{n-1}}{\pi }}\\\end{cases}}\quad {\text{(II)}}$

Estas equações paramétricas mostram os coeficientes do polinómio quociente $P'(x)$ que satisfazem a condição inicial, $P(x)=(x+\pi )\,P'(x)$, quando o polinómio dividendo, $P(x)$, é dividido por um binómio divisor na forma $(x+\pi )$ com resto zero. Como $\pi$ tende a ser um número inteiro (mas não necessariamente), o algoritmo paramétrico em oposição à regra de Ruffini permite logo selecionar quais os números inteiros, $\pi \in \mathbb {Z}$, que podem ser solução das equações paramétricas geradoras de $P'(x)$, pois logo a primeira equação, $\displaystyle \lambda '_{0}={\frac {\lambda _{0}}{\pi }}$, implica forçosamente um número inteiro, ou seja, um mínimo múltiplo comum com $\lambda _{0}$.

Este algoritmo permite verificar qual o valor de $\pi$ sem ter de completar todos os cálculos sobre os coeficientes, ao contrário da regra de Ruffini, bastando parar quando não se obtém um número inteiro. Pode-se também verificar que o coeficiente de maior grau do polinómio $P'(x),\,\lambda '_{n-1}$, é igual ao coeficiente de maior grau do polinómio $P(x),\,\lambda _{n}$, tal como esperado (verifica-se noutros métodos de divisão). Podemos ver também que como $P'(x)$ é um grau inferior a $P(x)$, o termo $\lambda '_{n}$ é igual a zero, pelo que a última equação paramétrica serve de controlo, já que o seu resultado tem de ser forçosamente nulo, $\lambda _{n}-\lambda '_{n-1}=0$.

Exemplos

Verifiquemos a seguinte equação polinomial: $P(x)=2x^{4}+5x^{3}+7x^{2}+3x-1\quad {\text{(A)}}$

O coeficiente $\lambda _{0}$ é $-1$, então o valor de $\pi$ poderá ser $\left\{-1,1\right\}$. Verifiquemos,

${\begin{cases}\pi \rightarrow -1\\\displaystyle \lambda '_{0}={\frac {-1}{-1}}=1\\\displaystyle \lambda '_{1}={\frac {3-1}{-1}}=-2\\\displaystyle \lambda '_{2}={\frac {7+2}{-1}}=-9\\\displaystyle \lambda '_{3}={\frac {5+9}{-1}}=-14\\\displaystyle \lambda '_{4}={\frac {2+14}{-1}}=-16\\\end{cases}}\qquad$ $\quad {\begin{cases}\pi \rightarrow 1\\\displaystyle \lambda '_{0}={\frac {-1}{1}}=-1\\\displaystyle \lambda '_{1}={\frac {3-1}{1}}=4\\\displaystyle \lambda '_{2}={\frac {7-4}{1}}=3\\\displaystyle \lambda '_{3}={\frac {5-3}{1}}=2\\\displaystyle \lambda '_{4}={\frac {2-2}{1}}=0\\\end{cases}}$

Uma vez que $\lambda '_{3}=\lambda _{4}$ ou $\lambda '_{4}=0$, então o binómio divisor terá $\pi =1$ e pode-ser verificar a seguinte igualdade em relação ao polinómio dividendo: $P(x)=(x+1)(2x^{3}+3x^{2}+4x-1)$.

Seguindo com outro exemplo, podemos constatar que este algoritmo para procurar quocientes de resto zero (ou seja, raízes do polinómio dividendo) é mais pragmático e eficiente que a regra de Ruffini. Considerando a seguinte função, $P(x)=2x^{4}-15x^{3}-23x^{2}-38x+18\quad {\text{(B)}}$

conhecendo as propriedades paramétricas do algoritmo, sendo $\lambda _{0}=18$, então o binómio $(x+\pi )$ terá um $\pi \in \left\{\pm 1,\pm 2,\pm 3,\pm 6,\pm 9,\pm 18\right\}$. Verificando as soluções possíveis, encontramos

${\begin{cases}\pi \rightarrow -9\\\displaystyle \lambda '_{0}={\frac {18}{-9}}=-2\\\displaystyle \lambda '_{1}={\frac {-38+2}{-9}}=4\\\displaystyle \lambda '_{2}={\frac {-23-4}{-9}}=3\\\displaystyle \lambda '_{3}={\frac {-15-3}{-9}}=2\\\displaystyle \lambda '_{4}={\frac {2-2}{-9}}=0\\\end{cases}}\qquad$Que devolve a solução $P(x)=(x-9)(2x^{3}+3x^{2}+4x-2)$.

Embora trabalhoso, pois analiticamente há um conjunto de soluções possíveis que têm de ser verificadas, é possível logo à partida delimitar o intervalo de procura e excluir alguns pares que de outro modo teriam de ser verificados, neste caso $\left\{\pm 4,\pm 5,\pm 7,\pm 8\right\}$, que constituiriam 50% do esforço em análise.

Quanto maior o grau do polinómio, $n$, e maior o termo independente, $\lambda _{0}$, maior tenderá a ser o esforço analítico, como em qualquer outro algoritmo de divisão polinomial.

Note-se que essa não é uma regra. O polinómio $x^{8}-4x^{7}+x^{6}+5x^{5}+6x^{4}-10x^{3}+3x^{2}+12x-20$ tem um $\pi =-2$. O polinómio $4x^{8}-24x^{7}+37x^{6}-24x^{5}+7x^{4}+34x^{3}+8x^{2}-56x+96$ tem um $\pi =-4$. Há uma dilatação do conjunto de soluções possíveis, mas não necessariamente do volume de cálculo.

Monómio do Resto

Uma propriedade que o algoritmo paramétrico devolve em oposição a outras ferramentas de divisão polinomial é o monómio do resto: enquanto os restantes algoritmos devolvem o monómio de menor grau, um coeficiente sem variável (ou $x^{0}$), este devolve o monómio de maior grau, o coeficiente de $x^{n}$.

Repare-se que a procura por um monómio divisor que dê resto zero começa com a procura de um mínimo múltiplo comum do termo de menor grau do polinómio dividendo, $\lambda _{0}$, mas o par $\left\{\pm 1\right\}$ será sempre uma solução possível, já que devolverá sempre números inteiros, pelo que o coeficiente de maior grau do polinómio quociente, $\lambda '_{n}$, que é zero quando o resto é zero, não será nulo. Por exemplo, no polinómio anterior (B), cujo $\pi =-9$, ao proceder ao algoritmo para $\pi =\left\{\pm 1\right\}$, irão obter-se coeficientes inteiros que não fornecerão um $\lambda '_{n}$ nulo, já que o par $\left\{\pm 1\right\}$ não é solução para resto zero. Assim, a igualdade que deu início ao algoritmo paramétrico ${\text{(1)}}$, que subentende resto zero, deve ser reescrita como

$\qquad P(x)=(x+\pi )\,P'(x)+R\quad {\text{(2)}}$

com um $R$ relacionado ao coeficiente de maior grau do polinómio quociente, $\lambda '_{n}$. Quando é nulo, a equação (2) ganha a forma em (1). Deve-se então perceber que valor toma $R$ quando é não nulo. Olhando para as equações paramétricas em (I), a primeira equação tem subentendida uma parcela nula e que não foi escrita, mas seguindo a sequência numérica das outras equações pode-se completar o padrão escrevendo $\lambda _{n}=\lambda '_{n-1}+\pi \lambda '_{n}$, com $\pi \lambda '_{n}=0$ quando procuramos quocientes de resto zero (que é o interesse deste algoritmo para divisão de polinómios). Então, a última parcela da equação paramétrica é o valor do resto, pelo que (2) se pode reescrever

$\qquad P(x)=(x+\pi )\,P'(x)+\pi \lambda '_{n}\quad {\text{(3)}}$

Realizando o algoritmo para o polinómio (B) no conjunto $\left\{\pm 1\right\}$ temos,

${\begin{cases}\pi \rightarrow -1\\\displaystyle \lambda '_{0}={\frac {18}{-1}}=-18\\\displaystyle \lambda '_{1}={\frac {-38+18}{-1}}=20\\\displaystyle \lambda '_{2}={\frac {-23-20}{-1}}=43\\\displaystyle \lambda '_{3}={\frac {-15-43}{-1}}=58\\\displaystyle \lambda '_{4}={\frac {2-58}{-1}}=56\\\end{cases}}\qquad$$\quad {\begin{cases}\pi \rightarrow 1\\\displaystyle \lambda '_{0}={\frac {18}{1}}=18\\\displaystyle \lambda '_{1}={\frac {-38-18}{1}}=-56\\\displaystyle \lambda '_{2}={\frac {-23+56}{1}}=33\\\displaystyle \lambda '_{3}={\frac {-15-33}{1}}=-48\\\displaystyle \lambda '_{4}={\frac {2+48}{1}}=50\\\end{cases}}\quad$$\qquad {\begin{array}{l}{\text{Escrevendo as soluções, fica}}\\\pi \rightarrow -1\Longrightarrow P(x)=(x-1)(58x^{3}+43x^{2}+20x-18)-56x^{4}\\\pi \rightarrow 1\Longrightarrow P(x)=(x+1)(-48x^{3}+33x^{2}-56x+18)+50x^{4}\end{array}}$

Polinómios Incompletos

Como seria de esperar, o algoritmo paramétrico mantém-se válido quando os polinómios têm coeficientes nulos e por conseguinte termos omissos. Segue-se exemplo, $P(x)=5x^{4}-3x^{2}+x-1\quad {\text{(C)}}$

Como $\lambda _{0}=-1$, então $\pi =\left\{\pm 1\right\}$:

${\begin{cases}\pi \rightarrow -1\\\displaystyle \lambda '_{0}={\frac {-1}{-1}}=1\\\displaystyle \lambda '_{1}={\frac {1-1}{-1}}=0\\\displaystyle \lambda '_{2}={\frac {-3-0}{-1}}=3\\\displaystyle \lambda '_{3}={\frac {0-3}{-1}}=3\\\displaystyle \lambda '_{4}={\frac {5-3}{-1}}=-2\\\end{cases}}\qquad$ $\quad {\begin{cases}\pi \rightarrow 1\\\displaystyle \lambda '_{0}={\frac {-1}{1}}=-1\\\displaystyle \lambda '_{1}={\frac {1+1}{1}}=2\\\displaystyle \lambda '_{2}={\frac {-3-2}{1}}=-5\\\displaystyle \lambda '_{3}={\frac {0+5}{1}}=5\\\displaystyle \lambda '_{4}={\frac {5-5}{1}}=0\\\end{cases}}\quad$ $\quad {\begin{array}{l}{\text{Portanto}}\\\pi \rightarrow -1\Longrightarrow P(x)=(x-1)(3x^{3}+3x^{2}+x-1)+2x^{4}\\\pi \rightarrow 1\Longrightarrow P(x)=(x+1)(5x^{3}-5x^{2}+2x-1)\end{array}}$

Neste caso houve um aumento do monómios, que pode ou não ser útil, mas nem sempre é assim e obtém-se uma simplificação, que é sempre desejada: $P(x)=x^{4}+x^{3}+x+1\quad {\text{(D)}}$

Sendo $\lambda _{0}=1$, logo $\pi =\left\{\pm 1\right\}$:

${\begin{cases}\pi \rightarrow -1\\\displaystyle \lambda '_{0}={\frac {1}{-1}}=-1\\\displaystyle \lambda '_{1}={\frac {1+1}{-1}}=-2\\\displaystyle \lambda '_{2}={\frac {0+2}{-1}}=-2\\\displaystyle \lambda '_{3}={\frac {1+2}{-1}}=-3\\\displaystyle \lambda '_{4}={\frac {1+3}{-1}}=-4\\\end{cases}}\qquad$ $\quad {\begin{cases}\pi \rightarrow 1\\\displaystyle \lambda '_{0}={\frac {1}{1}}=1\\\displaystyle \lambda '_{1}={\frac {1-1}{1}}=0\\\displaystyle \lambda '_{2}={\frac {0-0}{1}}=0\\\displaystyle \lambda '_{3}={\frac {1-0}{1}}=1\\\displaystyle \lambda '_{4}={\frac {1-1}{1}}=0\\\end{cases}}\quad$ $\quad {\begin{array}{l}{\text{Então}}\\\pi \rightarrow -1\Longrightarrow P(x)=(x-1)(-3x^{3}-2x^{2}-2x-x)+4x^{4}\\\pi \rightarrow 1\Longrightarrow P(x)=(x+1)(x^{3}+1)\end{array}}$

$\pi$ fracionário

O mesmo se dá com números fracionários, embora o trabalho da descoberta seja maior, como em qualquer método analítico não automatizado. Sendo $P(x)=2x^{4}+x^{3}-4x-2\quad {\text{(E)}}$

Como $\lambda _{0}=-2$, então $\pi =\left\{\pm 1,\pm 2\right\}$, mas este conjunto não devolve um resto igual a zero, mas antes um $\pi \lambda '_{n}$, pelo que não há solução com $\pi \in \mathbb {Z}$. Procurando solução no conjunto dos números facionários, $\mathbb {Q}$, encontramos um $\pi ={\frac {1}{2}}$ que devolve resto zero.

${\begin{cases}\displaystyle \pi \rightarrow {\frac {1}{2}}\\\\\lambda '_{0}=2\,(-2)=-4\\\lambda '_{1}=2\,(-4+4)=0\\\lambda '_{2}=2\,(0-0)=0\\\lambda '_{3}=2\,(1-0)=2\\\lambda '_{4}=2\,(2-2)=0\\\end{cases}}\quad$$\quad {\begin{array}{l}{\text{Verifica-se então}}\\\pi \rightarrow {\frac {1}{2}}\Longrightarrow P(x)=(x+{\frac {1}{2}})(2x^{3}-4)\end{array}}$

O algoritmo embora válido para $\forall \,\pi \!\in \!\mathbb {Q}$, a procura analítica pode ser exaustiva e não devolver uma solução mesmo quando ela exista, então deve-se recorrer a outros métodos de divisão polinomial ou a ferramentas gráficas, como o teorema do resto.

Exemplo de código fonte

import java.útil.Scanner;

public class Interpolation {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Obter o número de pontos
        System.out.print("Digite o número de pontos: ");
        int n = scanner.nextInt();

        double[] x = new double[n];
        double[] y = new double[n];

        // Obter os pontos
        for (int i = 0; i < n; i++) {
            System.out.printf("Digite o ponto %d (x, y): ", i + 1);
            x[i] = scanner.nextDouble();
            y[i] = scanner.nextDouble();
        }

        // Obter o valor de x para o qual se deseja encontrar o valor de y
        System.out.print("Digite o valor de x para o qual deseja encontrar o valor de y: ");
        double xValue = scanner.nextDouble();

        // Calcular o valor de y usando o algoritmo paramétrico
        double yValue = 0;
        for (int i = 0; i < n; i++) {
            double term = y[i];
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    term *= (xValue - x[j]) / (x[i] - x[j]);
                }
            }
            yValue += term;
        }

        // Exibir o resultado
        System.out.printf("O valor de y para x = %.2f é %.2f", xValue, yValue);

        scanner.close();
    }
}

Ver também

• Divisão polinomial
• Algoritmo de Briot-Ruffini
• Teorema do resto
• Teorema fundamental da álgebra