| | | |

Matemática numérica I

2 Equação com uma incógnita

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 Horner212121William 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)=a1⁢xn+a2⁢xn−1+⋯+an⁢x+an+1, (2.184)

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 x0 e um polinômio de grau n

p⁢(x)=p1⁢xn+p2⁢xn−1+⋯+pn⁢x+pn+1. (2.185)

O método de Horner consiste em computar p⁢(x0) pela iteração

q1=p1, (2.186)
qk=pk+qk−1⁢x0,k=2,3,…,n+1, (2.187)

sendo que, então, p⁢(x0)=qn+1 e, além disso,

p⁢(x)=(x−x0)⁢q⁢(x)+qn+1, (2.188)

com

q⁢(x)=q1⁢xn−1+q2⁢xn−2+⋯+qn−1⁢x+qn. (2.189)

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

(x−x0)⁢q⁢(x)+qn+1=(x−x0)⁢(q1⁢xn−1+q2⁢xn−2+⋯+qn−1⁢x+qn)
+qn+1 (2.190)
=q1xn+(q2−q1x0)xn−1+⋯+(qn+1−qnx0). (2.191)

E, então, igualando a p⁢(x) na forma (2.185), temos as equações (2.186)-(2.187).

Exemplo 2.7.1.

Consideremos o polinômio

p⁢(x)=x3−3⁢x2+4. (2.192)

Para computarmos p⁢(1) pelo método de Horner, tomamos x0=1, q1=p1=1 e

q2=p2+q1⁢x0=−3+1⋅1=−2 (2.193)
q3=p3+q2⁢x0=0+(−2)⋅1=−2 (2.194)
q4=p4+q3⁢x0=4+(−2)⋅1=2. (2.195)

Com isso, temos p⁢(1)=q4=2. Verifique!

Observação 2.7.1.

Ao computarmos p⁢(x0) pelo método de Horner, obtemos a decomposição

p⁢(x)=(x−x0)⁢q⁢(x)+bn+1. (2.196)

Desta forma, temos

p′⁢(x)=q⁢(x)+(x−x0)⁢q′⁢(x), (2.197)

donde temos que p′⁢(x0)=q⁢(x0). Com isso, para computarmos p′⁢(x0) 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)−p⁢(x(k))p′⁢(x(k)), (2.198)

na qual podemos utilizar o método de Horner para computar p⁢(x(k)) e p′⁢(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)=x3−3⁢x2+4, (2.199)

com aproximação inicial x(1)=−2. Na Tabela 2.14 temos os resultados obtidos.

Tabela 2.14: Resultados referentes ao Exemplo 2.7.2.
k x(k) |x(k)−x(k−1)|
1 −2.0000 -x-
2 −1.3333 6.7⁢e−1
3 −1.0556 2.8⁢e−1
4 −1.0019 5.4⁢e−2
5 −1.0000 1.9⁢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)=x3−3⁢x2+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!

Opcional. Preencha seu nome para que eu possa lhe contatar.
Opcional. Preencha seu e-mail para que eu possa lhe contatar.
As informações preenchidas são enviadas por e-mail para o desenvolvedor do site e tratadas de forma privada. Consulte a política de uso de dados para mais informações.

Licença Creative Commons
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.

Pedro H A Konzen
| | | |