Matemática Numérica I

2 Equação com uma incógnita 2.6 Método da secante 3 Métodos para Sistemas Lineares

Ajude a manter o site livre, gratuito e sem propagandas. Colabore!

2.7 Raízes de polinômios

Em revisão

Nesta seção, veremos como o método de Newton pode ser aplicado de forma robusta a polinômios com o auxílio do método de Horner²¹²¹21William George Horner, 1786 - 1837, matemático britânico. Fonte: Wikipédia: William George Horner. A questão central é que dado um polinômio de grau $n$ escrito na forma

p(x)=a_{1}x^{n}+a_{2}x^{n-1}+\cdots+a_{n}x+a_{n+1},

(2.173)

o procedimento de avaliá-lo em um ponto requer $n! n$ multiplicações e $n$ adições. Desta forma, a aplicação do método de Newton para obter as raízes de $p$ torna-se computacionalmente custosa, por requer a avaliação de $p$ e de sua derivada a cada iteração. Agora, o método de Horner nos permite avaliar $p$ em um ponto qualquer usando apenas $n$ multiplicações e $n$ adições, reduzindo enormemente o custo computacional.

2.7.1 Método de Horner

Em revisão

Sejam dados um número $x_{0}$ e um polinômio de grau $n$

p(x)=p_{1}x^{n}+p_{2}x^{n-1}+\cdots+p_{n}x+p_{n+1}s.

(2.174)

O método de Horner consiste em computar $p(x_{0})$ pela iteração

	$\displaystyle q_{1}$	$\displaystyle=p_{1},$		(2.175)
	$\displaystyle q_{k}$	$\displaystyle=p_{k}+q_{k-1}x_{0},\quad k=2,3,\dotsc,n+1,$		(2.176)

sendo que, então, $p(x_{0})=q_{n+1}$ e, além disso,

p(x)=(x-x_{0})q(x)+q_{n+1},

(2.177)

com

q(x)=q_{1}x^{n-1}+q_{2}x^{n-2}+\cdots+q_{n-1}x+q_{n}.

(2.178)

De fato, a verificação de (2.177) é direta, uma vez que

$\displaystyle(x-x_{0})q(x)+q_{n+1}$	$\displaystyle=(x-x_{0})(q_{1}x^{n-1}+q_{2}x^{n-2}+\cdots+q_{n-1}x+q_{n})$
	$\displaystyle+q_{n+1}$	(2.179)
	$\displaystyle=q_{1}x^{n}+(q_{2}-q_{1}x_{0})^{n-1}+\cdots+(q_{n+1}-q_{n}x_{0}).$	(2.180)

E, então, igualando a $p(x)$ na forma (2.174), temos as equações (2.175)-(2.176).

Exemplo 2.7.1.

Consideremos o polinômio

p(x)=x^{3}-3x^{2}+4.

(2.181)

Para computarmos $p(1)$ pelo método de Horner, tomamos $x_{0}=1$ , $q_{1}=p_{1}=1$ e

$\displaystyle q_{2}$	$\displaystyle=p_{2}+q_{1}x_{0}=-3+1\cdot 1=-2$	(2.182)
$\displaystyle q_{3}$	$\displaystyle=p_{3}+q_{2}x_{0}=0+(-2)\cdot 1=-2$	(2.183)
$\displaystyle q_{4}$	$\displaystyle=p_{4}+q_{3}x_{0}=4+(-2)\cdot 1=2.$	(2.184)

Com isso, temos $p(3)=q_{4}=4$ (verifique!).

Observação 2.7.1.

Ao computarmos $p(x_{0})$ pelo método de Horner, obtemos a decomposição

p(x)=(x-x_{0})q(x)+b_{n+1}.

(2.185)

Desta forma, temos

p^{\prime}(x)=q(x)+(x-x_{0})q^{\prime}(x),

(2.186)

donde temos que $p^{\prime}(x_{0})=q(x_{0})$ . Com isso, para computarmos $p^{\prime}(x_{0})$ podemos aplicar o método de Horner a $q(x)$ .

2.7.2 Método de Newton-Horner

Em revisão

A implementação do método de Newton a polinômios pode ser feita de forma robusta com o auxílio do método de Horner. Dado um polinômio $p$ e uma aproximação inicial $x^{(1)}$ para uma de suas raízes reais, a iteração de Newton consiste em

x^{(k+1)}=x^{(k)}-\frac{p(x^{(k)})}{p^{\prime}(x^{(k)})},

(2.187)

na qual podemos utilizar o método de Horner para computar $p(x^{(k)})$ e $p^{\prime}(x^{(k)})$ .

Exemplo 2.7.2.

Consideremos o caso de aplicar o método de Newton para obter uma aproximação da raiz $x=-1$ de

p(x)=x^{3}-3x^{2}+4,

(2.188)

com aproximação inicial $x^{(1)}=-2$ . Na Tabela 2.11 temos os resultados obtidos.

Tabela 2.11: Resultados referentes ao Exemplo 2.7.2.

$k$	$x^{(k)}$	$\|x^{(k)}-x^{(k-1)}\|$
1	$-2.0000$	-x-
2	$-1.3333$	$6.7\mathrm{e}\!-\!1$
3	$-1.0556$	$2.8\mathrm{e}\!-\!1$
4	$-1.0019$	$5.4\mathrm{e}\!-\!2$
5	$-1.0000$	$1.9\mathrm{e}\!-\!3$

2.7.3 Exercícios

Em revisão

E. 2.7.1.

Use o método de Newton-Horner para computar a aproximação da raiz de $p(x)=x^{3}-3x^{2}+4$ no intervalo $[1,3]$ . Observe que $p$ tem um zero duplo deste intervalo.

$2$

Envie seu comentário

Aproveito para agradecer a todas/os que de forma assídua ou esporádica contribuem enviando correções, sugestões e críticas!

Este texto é disponibilizado nos termos da Licença Creative Commons Atribuição-CompartilhaIgual 4.0 Internacional. Ícones e elementos gráficos podem estar sujeitos a condições adicionais.

Política de uso de dados

Política de uso de dados

Matemática Numérica I

2.7 Raízes de polinômios

2.7.1 Método de Horner

Exemplo 2.7.1.

Observação 2.7.1.

2.7.2 Método de Newton-Horner

Exemplo 2.7.2.

2.7.3 Exercícios

E. 2.7.1.

Envie seu comentário