Exercício 25 - Newton + Horner

Aplique o Método de Newton com avaliação de p\left(x_{k}\right) e p\left(x_{k}\right) via Horner duplo ao polinômio p(x)=x^{4}-10 x^{3}+35 x^{2}-50 x+24 (raízes 1,2,3,4 ).
(a) Parta de x_{0}=0,5 e encontre a raiz \xi_{1}=1.
(b) Deflacione p(x) por \left(x-\xi_{1}\right) via Briot-Ruffini, obtendo q(x) de grau 3 .
(c) Repita para as demais raízes, aplicando Newton+Horner a q, r, s sucessivamente.
(d) Atenção: Ao final, refine cada raiz no polinômio original p para compensar o acúmulo de erros da deflação.

Passo 1

O enunciado fornece o polinômio
p(x)=x^{4}-10x^{3}+35x^{2}-50x+24
e diz que as raízes são \;1,2,3,4\;. As tarefas pedidas são:
  • (a) Aplicar o Método de Newton partindo de x_0=0,5 para encontrar a raiz \xi_1=1.
  • (b) Deflacionar p(x) por (x-\xi_1) via Briot–Ruffini (divisão sintética), obtendo um polinômio q(x) de grau 3.
  • (c) Repetir Newton+Horner para encontrar as raízes seguintes usando, sucessivamente, q(x), r(x), s(x) (cada deflação reduz o grau em 1).
  • (d) Ao final, refinar cada raiz no polinômio original p para compensar erro de deflação.
Informações relevantes dadas:
  • Coeficientes de p: a_4=1,\;a_3=-10,\;a_2=35,\;a_1=-50,\;a_0=24.
  • Ponto inicial para a primeira raiz: x_0=0,5.
  • Deve ser usada avaliação de p(x_k) e p'(x_k) via Horner duplo (ou seja, Horner simultâneo para o polinômio e sua derivada).
  • Depois de achar cada raiz aproximada, usar Briot–Ruffini (divisão sintética) para deflacionar e obter o polinômio da próxima etapa.

Passo 2

Explicando o método (o que vai ser usado e por quê), bem devagar e com exemplo concreto.
  1. Método de Newton (fórmula)
x_{k+1}=x_k-\frac{p(x_k)}{p'(x_k)}.
Aqui p(x) é o polinômio e p'(x) sua derivada. A ideia: aproximamos a função por sua reta tangente em x_k e pegamos a interseção dessa reta com o eixo x.
  1. Horner para avaliação de p(x)
    Se p(x)=a_n x^n + a_{n-1} x^{n-1} +\cdots + a_0, o Horner calcula eficientemente p(x) com o esquema
\begin{aligned} b_n &= a_n,\\\ b_{j} &= a_{j} + x\, b_{j+1}\quad (j=n-1,\dots,0), \end{aligned}
e então p(x)=b_0.
  1. Horner duplo (avaliação simultânea de p(x) e p'(x))
    Há um truque simples: definimos também
c_n=0,\qquad c_j = b_{j+1} + x\,c_{j+1}\quad (j=n-1,\dots,0),
então p'(x)=c_0. Ou seja, na mesma passada de Horner obtemos os b_j (que levam a p(x)) e os c_j (que levam a p'(x)). Vou usar exatamente esse esquema em cada iteração de Newton — isso é o que se chama “Horner duplo”.
  1. Briot–Ruffini (divisão sintética)
    Para dividir p(x) por (x-\alpha) basta usar os coeficientes e fazer a tabulação:
  • traz-se o a_n para baixo como primeiro coeficiente do quociente,
  • multiplica-se por \alpha, soma-se ao próximo coeficiente, etc.
    No final o resto é p(\alpha). Se \alpha é (aprox.) raiz simples e o resto for (aprox.) zero, os coeficientes formam o polinômio deflacionado.
Observação prática: como as raízes são inteiras e simples, quando encontrarmos \xi_1\approx 1 e o resto for (aprox.) zero, a divisão por (x-1) dará coeficientes inteiros exatos.

Passo 3

Aplicação prática: começar por x_0=0,5. Vou executar uma iteração completa de Horner duplo para x_0 detalhadamente (isto serve de exemplo do procedimento; nas próximas iterações uso o mesmo método).
Coeficientes de p: [\,a_4,a_3,a_2,a_1,a_0\,]=[1,-10,35,-50,24].
Horner duplo em x_0=0{,}5:
\begin{aligned} b_4 &= a_4 = 1, & c_4&=0,\\\ b_3 &= a_3 + x_0 b_4 = -10 + 0{,}5\cdot 1 = -9{,}5, & c_3 &= b_4 + x_0 c_4 = 1 + 0{,}5\cdot 0 = 1,\\\ b_2 &= a_2 + x_0 b_3 = 35 + 0{,}5\cdot(-9{,}5) = 35 - 4{,}75 = 30{,}25, & c_2 &= b_3 + x_0 c_3 = -9{,}5 + 0{,}5\cdot 1 = -9{,}0,\\\ b_1 &= a_1 + x_0 b_2 = -50 + 0{,}5\cdot 30{,}25 = -50 + 15{,}125 = -34{,}875, & c_1 &= b_2 + x_0 c_2 = 30{,}25 + 0{,}5\cdot(-9{,}0) = 30{,}25 - 4{,}5 = 25{,}75,\\\ b_0 &= a_0 + x_0 b_1 = 24 + 0{,}5\cdot(-34{,}875) = 24 - 17{,}4375 = 6{,}5625, & c_0 &= b_1 + x_0 c_1 = -34{,}875 + 0{,}5\cdot 25{,}75 = -34{,}875 + 12{,}875 = -22{,}0. \end{aligned}
Resultado: \;p(x_0)=b_0=6{,}5625,\qquad p'(x_0)=c_0=-22{,}0.
Aplicando Newton:
x_1 = x_0 - \frac{p(x_0)}{p'(x_0)} = 0{,}5 - \frac{6{,}5625}{-22} = 0{,}5 + 0{,}2982954545\ldots = 0{,}7982954545\ldots
Anotações didáticas curtas:
  • Note que a mesma tabela de Horner (os b_j) já representa a divisão sintética por (x-x_0) parcial; o vetor (b_4,b_3,b_2,b_1) é usado quando deflacionarmos por uma raiz exata.
  • O Horner duplo economiza trabalho porque avaliamos p e p' numa única passada.

Passo 4

Iterações seguintes (cada avaliação feita por Horner duplo; mostro os resultados numéricos das iterações — as contas internas são as mesmas do Passo 3, repetidas com o novo x_k). Vou mostrar iterações até convergência prática para a raiz 1.
Usando Horner duplo e Newton repetidamente (todos os p(x_k) e p’(x_k) avaliados via Horner duplo):
  • Iteração 1 (já feita): x_0=0{,}5 x_1\approx 0{,}7982954545454546.
  • Iteração 2: avaliar p e p' em x_1 via Horner duplo e aplicar Newton → obtém-se
x_2 \approx 0{,}951291141238\ldots
  • Iteração 3: repetir →
x_3 \approx 0{,}988690403610\ldots
  • Iteração 4: repetir →
x_4 \approx 0{,}999635128728\ldots
  • Iteração 5: repetir →
x_5 \approx 0{,}999999982175\ldots
  • Iteração 6: repetir →
x_6 \approx 1{,}000000000000\ldots
Comentário didático: Newton converge muito rápido (convergência quadrática) porque estamos perto de uma raiz simples. Em poucas iterações já temos precisão numérica de máquina em geral. Aqui, após 5–6 iterações chegamos a um valor que, para todos os propósitos práticos, é exatamente 1. Ou seja, a raiz encontrada é \xi_1=1.

Passo 5

Agora fazemos a deflação de p(x) por (x-\xi_1). Como \xi_1=1 é raiz exata (e o resto numérico é nulo dentro da precisão), aplicamos Briot–Ruffini (divisão sintética) com \alpha=1.
Coeficientes iniciais: [1,\,-10,\,35,\,-50,\,24].
Tabela de Briot–Ruffini com \alpha=1:
  • Trazer 1 (coef. líder).
  • Multiplicar por 1, somar ao próximo coeficiente: -10 + 1 = -9.
  • Multiplicar -9 por 1, somar: 35 + (-9)=26.
  • Multiplicar 26 por 1, somar: -50 + 26 = -24.
  • Multiplicar -24 por 1, somar: 24 + (-24) = 0 (resto zero, confirma raíz).
Os coeficientes do quociente q(x) (grau 3) são [1,\,-9,\,26,\,-24], ou seja
q(x)=x^{3}-9x^{2}+26x-24.
Observação: agora q tem as demais raízes 2,3,4.

Passo 6

Repetir Newton+Horner para q(x) para achar a próxima raiz. Vou escolher um ponto inicial razoável para convergir à raiz 2; por exemplo x_0^{(q)}=1{,}5. O procedimento é o mesmo: Horner duplo aplicado a q (agora grau 3) para obter q(x_k) e q'(x_k), e aplicar Newton.
Apenas os resultados das iterações (cada avaliação feita por Horner duplo):
  • Partindo de x_0^{(q)}=1{,}5, após poucas iterações de Newton obtemos:
\text{raiz de }q:\quad \xi_2 \approx 2{,}0000000000\ldots
Ou seja, converge para \xi_2=2.
Agora deflacionamos q por (x-2) via Briot–Ruffini. Coeficientes de q: [1,-9,26,-24].
  • Trazer 1.
  • 1\cdot 2 = 2;\\\ -9+2=-7.
  • -7\cdot 2 = -14;\\\ 26-14=12.
  • 12\cdot 2 = 24;\\\ -24+24=0 (resto zero).
Quociente r(x) (grau 2) tem coeficientes [1,-7,12], ou seja
r(x)=x^{2}-7x+12.
Sabendo fatoração, r(x)=(x-3)(x-4).

Passo 7

Agora aplicar Newton+Horner a r(x)=x^{2}-7x+12 para encontrar uma das raízes, por exemplo \xi_3=3. Escolhendo x_0^{(r)}=2{,}5 e iterando:
  • Após poucas iterações de Newton (Horner duplo em grau 2 é trivial) chega-se a
\text{raiz de }r:\quad \xi_3 \approx 3{,}0000000000\ldots
Deflacionando r por (x-3) via Briot–Ruffini (ou observando fatoração) obtemos o polinômio linear s(x)=x-4.

Passo 8

Finalmente, a última raiz óbvia de s(x)=x-4 é \xi_4=4. Se desejarmos, podemos aplicar uma última iteração de Newton ao polinômio original p para “refinar” cada raiz encontrada e compensar qualquer pequeno erro numérico acumulado na deflação. O refinamento de uma raiz aproximada \tilde{\xi} é simplesmente uma atualização de Newton usando p e p' (avaliados via Horner duplo) no polinômio original:
Refinamento (exemplo genérico)
\tilde{\xi}_{\text{novo}} = \tilde{\xi} - \frac{p(\tilde{\xi})}{p'(\tilde{\xi})}.
No nosso caso, como cada deflação foi feita com raízes inteiras exatas (e os restos deram zero dentro da precisão), essas correções são nulas dentro da precisão numérica — ou seja, após o refinamento obtemos exatamente
\;1,\;2,\;3,\;4\; (na prática numérica, as atualizações são da ordem de erros de máquina e desaparecem).

Passo 9

Resumo do procedimento (fluxo que você deve repetir na prova):
  • Para cada raiz a ser encontrada:
    1. Escolher um chute inicial razoável x_0.
    2. Avaliar p(x_k) e p'(x_k) via Horner duplo (faça a tabela dos b_j e c_j).
    3. Atualizar x_{k+1}=x_k - p(x_k)/p'(x_k).
    4. Repetir até a convergência desejada.
    5. Quando \tilde{\xi} for raiz (ou aproximar-se muito de uma), deflacionar via Briot–Ruffini (divisão sintética) para obter o polinômio da próxima etapa.
    6. No fim, refinar cada raiz candidata aplicando uma ou duas iterações de Newton usando o polinômio original p.
Dica prática: use Horner duplo sempre — ele dá p e p' numa passagem só e os coeficientes intermediários servem direto para a divisão sintética quando a raiz for exata.

Resposta

1
2
3
4

Exercícios relacionados