O método Heron (“dividir e fazer média”), um método antigo para aproximação de raiz quadrada de qualquer número inteiro a, pode ser formulado como:
x=\frac{x+\frac{a}{x}}{2}
A aplicação do método consiste em aplicação o método de forma iterativa:
x_{k+1}=\frac{x_{k}+\frac{a}{x_{k}}}{2}
Deste modo, deve-se escolher um valor inicial para x, dito x_{0}, e a partir deste encontrar os valores aproximados para \sqrt{a} : usa-se x_{0} para encontrar x_{1}, usa-se x_{1} para encontrar x_{2}, usa-se x_{2} para encontrar x_{3} e assim por diante. Como exemplo, vamos estimar \sqrt{25}, usando uma estimativa inicial x_{0}=7.
k x_{k} x_{k+1}
0 7 5.285714
1 5.285714 5.007722
2 5.007722 5.000005
3 5.000005 5.000000
a. A partir do método de Horn, escreva um algoritmo que encontre o valor aproximado para \sqrt{a} com pelo menos n significativos.
b. Usando o algoritmo da questão (a), escreva um programa no Octave que receba como parâmetro o valor a e o n e retorne um valor aproximado para \sqrt{a}, com pelo menos n significativos.
c. Compare o algoritmo que você propôs para o cálculo de raiz com o método de Horn. Para isso, verifique:
  • O número de interações que cada algoritmos leva para obter uma determinada solução com a mesma quantidade de dígitos significativos.
  • Apresente um gráfico com a evolução dos erros de aproximação absolutos de cada um dos algoritmos
  • Apresente um gráfico com a evolução dos erros de aproximação relativos de cada um dos algoritmos
  • Faça uma discussão comparativa do desempenho de cada algoritmo a partir do desempenho em termos do número de interações, dos erros de aproximação absolutos e dos erros de aproximação relativos.

Passo 1

O enunciado pede três coisas principais:
  1. (a) Projetar um algoritmo que, usando o método de Heron (a iteração \displaystyle x_{k+1}=\frac{x_k+\frac{a}{x_k}}{2}), encontre uma aproximação para \sqrt{a} com pelo menos n algarismos significativos.
  2. (b) Implementar em Octave um programa que receba a e n como parâmetros e retorne a aproximação pedida.
  3. (c) Comparar o algoritmo que eu proponho com o método de Heron: contar interações para uma mesma precisão, traçar gráfico da evolução dos erros absolutos e relativos e discutir o desempenho.
Informações dadas e condicionantes importantes:
  • A iteração de Heron é \displaystyle x_{k+1}=\frac{x_k+\frac{a}{x_k}}{2}.
  • Deve-se atingir pelo menos n dígitos significativos. Vou usar como critério prático (explicado depois) o critério de erro relativo:
\text{o critério de parada:}\quad \frac{|x_k-\sqrt{a}|}{\sqrt{a}} < 10^{-n}.é
  • Deve-se apresentar algoritmo detalhado, código Octave, gráficos de erros (absoluto e relativo) para comparar com outro algoritmo que eu proponho.

Passo 2

Entendendo o que significa “n algarismos significativos” e justificando o critério de parada que vou usar (importante para a prova).
  • Vamos chamar a verdadeira raiz por \displaystyle r=\sqrt{a}.
  • Uma forma simples e prática que usamos em programação e em provas: exigir que o erro relativo seja menor que 10^{-n}, isto é
\frac{|x_k-r|}{|r|} < 10^{-n}.
Isto garante que a aproximação difere da verdadeira por menos de uma parte em 10^{n}, o que é uma definição conservadora e fácil de verificar sem arredondamentos complicados. (Há definições ligeiramente diferentes em livros, mas esta é suficiente e clara para provas/algoritmos.)
Comentário didático curto: erro absoluto é |x_k-r|. Erro relativo é \dfrac{|x_k-r|}{|r|}. Erro relativo é mais informativo quando grandezas têm escalas diferentes.

Passo 3

Relembrando e interpretando o método de Heron (Newton para a raiz quadrada) — aula curta e a intuição por trás:
  • Considere a função \displaystyle f(x)=x^2-a. Queremos solução de f(x)=0.
  • O método de Newton para f
x_{k+1}=x_k - \frac{f(x_k)}{f'(x_k)} = x_k - \frac{x_k^2-a}{2x_k} = \frac{x_k+\frac{a}{x_k}}{2},
que é exatamente o método de Heron. Então Heron é Newton aplicado a \sqrt{a}.
  • Convergência: perto da raiz verdadeira r, o método de Newton converge quadraticamente, o que significa que o erro se reduz aproximadamente como o quadrado do erro anterior:
e_k := x_k - r \quad\Rightarrow\quad e_{k+1} \approx C\; e_k^2,
para uma constante C dependente de r. Isso explica por que Heron costuma precisar de poucas iterações (número de algarismos dobra aproximadamente a cada iteração quando estamos já próximos).

Passo 4

Escolha e justificativa do algoritmo alternativo que vou propor para comparação:
  • Regras do enunciado: usar método que faça sentido para graduação em exatas; preferir métodos básicos se possível.
  • Eu proponho o método da bissecção (bisection) aplicado à função \displaystyle f(x)=x^2-a como alternativa. Motivos pedagógicos:
    • É muito simples, robusto e garante convergência (se tivermos um intervalo que contenha a raiz).
    • Convergência linear: intervalo é halved a cada iteração, então o número de dígitos corretos cresce lentamente, o que torna a comparação com Heron clara (Heron é muito mais rápido em número de iterações).
  • Observação: existe também o método da secante, que costuma convergir mais rápido que bissecção (ordem ~1,618) e não requer derivada; mas como precisamos de algo simples e garantido, escolhi bissecção. Em discussão comparativa eu menciono secante como alternativa.

Passo 5

Algoritmo detalhado do método proposto (bissecção) — passo a passo, como você faria na prova:
  1. Defina f(x)=x^2-a.
  2. Escolha intervalo inicial [L,U] que contenha a raiz:
    • Se a\ge 1 então uma escolha conveniente é [0,a] (porque \sqrt{a}\in[0,a]).
    • Se 0<a<1 escolha [0,1].
  3. Verifique f(L)\cdot f(U)\le 0. Aqui f(L)\le 0 e f(U)\ge 0; com as escolhas acima isso estará garantido.
  4. Repetir para k=0,1,2,\dots:
    • Calcule m=(L+U)/2.
    • Se f(L)\cdot f(m)\le 0 então a nova bissecção é [L,m] senão [m,U].
    • Registre x_k=m (a aproximação atual).
    • Pare quando o critério da questão estiver satisfeito: \frac{|x_k-r|}{|r|} < 10^{-n},mas, como r é desconhecido durante a execução real, em prática use critério equivalente baseado no tamanho do intervalo: \frac{(U-L)/2}{\max(1,r)} < 10^{-n}.Uma prática comum (sem conhecer r) é usar \frac{U-L}{2} < \varepsilon,com \varepsilon = 10^{-n}\cdot \max(1,\sqrt{a}). Assim garantimos o critério relativo desejado.
  5. Observe que o número de iterações k necessário para garantir largura de intervalo menor que \varepsilon satisfaz
\frac{U_0-L_0}{2^k} \le \varepsilon \quad\Rightarrow\quad k \ge \log_2\!\left(\frac{U_0-L_0}{\varepsilon}\right).
Isto permite estimar o número de iterações antes de começar.

Passo 6

Algoritmo do método de Heron (Newton) pronto para implementação — passo a passo prático e critério de parada:
  1. Escolher uma estimativa inicial x_0>0. Sugestão rápida: x_0=\max(1,a) ou x_0=a se a\ge1, ou x_0=1 se 0<a<1. Outra sugestão comumente boa: x_0=\frac{a+1}{2}.
  2. Repetir: x_{k+1}=\frac{x_k+\dfrac{a}{x_k}}{2}.
  3. Calcule erro absoluto e^{(abs)}_k=|x_k-r| e erro relativo e^{(rel)}_k=\dfrac{|x_k-r|}{|r|}.
  4. Parar quando e^{(rel)}_k < 10^{-n} (o critério usado aqui).
  5. Nota prática: como r é desconhecido em execução, podemos usar erro estimado entre iterações:
\text{est\_rel} = \frac{|x_{k+1}-x_k|}{|x_{k+1}|}
e parar quando \text{est\_rel}<10^{-n}. Para métodos quadráticos (como Heron) isso é robusto: quando x_k já está perto de r, a diferença entre iterações é uma boa proxy para o erro real.

Passo 7

Implementação Octave sugerida — código completo para os dois métodos (Heron e Bissecção), coleta de erros e geração de gráficos.
Cole o código abaixo no Octave (arquivo, por exemplo, sqrt_compare.m). O código implementa:
  • Função principal que recebe a e n;
  • Implementa Heron com parada baseada em diferença entre iterações como proxy de erro relativo;
  • Implementa bissecção com parada por largura de intervalo ajustada para critério relativo;
  • Retorna aproximações, vetores de erros absolutos e relativos e número de iterações;
  • Plota os três gráficos pedidos.
Código Octave (copiar/colar em um arquivo .m):
function result = sqrt_compare(a, n)
% sqrt_compare(a,n)
% Retorna comparacao entre Metodo de Heron (Newton) e Bisseccao para sqrt(a)
% Critério: erro relativo < 10^{-n}
if nargin < 2
error(‘Use: sqrt_compare(a,n)’);
end
% verdadeira raiz (usada apenas para avaliar erros)
r = sqrt(a);
tol_rel = 10^(-n);
% ---------- Metodo de Heron (Newton) -------------
xh = []; % guarda iteracoes
% escolha de x0
if a >= 1
x0 = a;
else
x0 = 1;
end
x = x0;
xh(end+1) = x;
maxit = 1000;
for k = 1:maxit
xnext = 0.5*(x + a/x); % iteracao de Heron
xh(end+1) = xnext;
% criterio prático baseado em diferença entre iteracoes
est_rel = abs(xnext - x)/abs(xnext);
if est_rel < tol_rel
break;
end
x = xnext;
end
heron_iters = length(xh)-1;
% calcula vetores de erros para Heron
heron_abs_err = abs(xh - r);
heron_rel_err = heron_abs_err / abs®;
% ---------- Metodo da Bisseccao ------------------
% inicializacao do intervalo
if a >= 1
L = 0;
U = a;
else
L = 0;
U = 1;
end
xb = []; % guarda midpoints
maxit_b = 2000;
% epsilon para largura do intervalo que garante criterio relativo
eps_abs = tol_rel * max(1, r); % (U-L)/2 < eps_abs garante criterio relativo
for k = 1:maxit_b
m = (L + U)/2;
xb(end+1) = m;
if (U - L)/2 < eps_abs
break;
end
if (mm - a) == 0
L = m; U = m;
break;
elseif (L
L - a)(mm - a) < 0
U = m;
else
L = m;
end
end
bisect_iters = length(xb);
% calcula vetores de erros para Bisseccao
bisect_abs_err = abs(xb - r);
bisect_rel_err = bisect_abs_err / abs®;
% ---------- Plots --------------------------------
it_heron = 0:(length(heron_abs_err)-1);
it_bisect = 1:length(bisect_abs_err);
figure;
semilogy(it_heron, heron_abs_err, ‘-o’, ‘DisplayName’,‘Heron abs err’); hold on;
semilogy(it_bisect, bisect_abs_err, ‘-s’, ‘DisplayName’,‘Bissect abs err’);
xlabel(‘Iteracao’); ylabel(‘Erro absoluto (escala log)’);
title(sprintf(‘Erro absoluto na aproximacao de sqrt(%g)’, a));
legend show; grid on;
figure;
semilogy(it_heron, heron_rel_err, ‘-o’, ‘DisplayName’,‘Heron rel err’); hold on;
semilogy(it_bisect, bisect_rel_err, ‘-s’, ‘DisplayName’,‘Bissect rel err’);
xlabel(‘Iteracao’); ylabel(‘Erro relativo (escala log)’);
title(sprintf(‘Erro relativo na aproximacao de sqrt(%g)’, a));
legend show; grid on;
% retorno
result.heron.x = xh(end);
result.heron.iters = heron_iters;
result.heron.abs_err = heron_abs_err;
result.heron.rel_err = heron_rel_err;
result.bisect.x = xb(end);
result.bisect.iters = bisect_iters;
result.bisect.abs_err = bisect_abs_err;
result.bisect.rel_err = bisect_rel_err;
result.true = r;
% imprime resumo
fprintf(‘True sqrt(%g) = %.15g\n’, a, r);
fprintf(‘Heron: x = %.15g, iters = %d, rel_err = %g\n’, result.heron.x, result.heron.iters, result.heron.rel_err(end));
fprintf(‘Biseccao: x = %.15g, iters = %d, rel_err = %g\n’, result.bisect.x, result.bisect.iters, result.bisect.rel_err(end));
end
Observações sobre o código:
  • Uso de estimativa de erro em Heron por |x_{k+1}-x_k|/|x_{k+1}| como proxy de erro relativo; isto é seguro quando já estamos na fase de convergência local quadrática.
  • Bissecção usa largura do intervalo comparada a \varepsilon = 10^{-n}\max(1,\sqrt{a}) para garantir o critério relativo.

Passo 8

Como executar e interpretar os resultados (passo a passo para a prova/experimento):
  1. Salve o código em arquivo chamado, por exemplo, sqrt_compare.m.
  2. No Octave execute:
    • res = sqrt_compare(25,6); para testar \sqrt{25} com n=6.
  3. O programa vai mostrar:
    • O valor verdadeiro \sqrt{a}.
    • A aproximação final e número de iterações para Heron e para bissecção.
    • Dois gráficos: erro absoluto (escala log) e erro relativo (escala log) comparando os métodos.
  4. Interprete os gráficos:
    • Para Heron você verá uma queda muito rápida do erro (curva que desce quase verticalmente após poucas iterações) devido à convergência quadrática.
    • Para bissecção a queda é constante na escala log (declive aproximadamente linear), porque a bissecção reduz o erro por fator ~2 a cada iteração (convergência linear).

Passo 9

Estimativa teórica do número de iterações — exemplo concreto para ajudar na prova (exemplo com a=25, n=6):
  • Verdadeira raiz \,r=\sqrt{25}=5.
  • Critério: erro relativo menor que 10^{-6}, isto é erro absoluto menor que 5\cdot10^{-6}.
  • Bissecção: largura inicial U_0-L_0=25. Queremos \frac{25}{2^k} < 2\cdot 5\cdot10^{-6} (o fator 2 vem porque o erro máximo ao tomar midpoint é metade da largura), ou seja \frac{25}{2^k} < 10^{-5} \quad\Rightarrow\quad 2^k > 2{,}5\times 10^{6} \quad\Rightarrow\quad k \gtrsim \log_2(2{,}5\times10^6)\approx 21{,}29.Então precisa de k=22 iterações (aprox).
  • Heron: pela tabela do enunciado já vimos que com x_0=7 as iterações convergem assim: x_1\approx 5{,}285714, x_2\approx 5{,}007722, x_3\approx 5{,}000005, x_4\approx 5{,}000000. Em 3–4 iterações já alcança precisão muito alta (muito menos que bissecção). Isso ilustra a diferença clara: Heron (Newton) ganha pela convergência quadrática.

Passo 10

Como apresentar e analisar os gráficos e a comparação (o que escrever na discussão):
  • Número de iterações:
    • Reporte o número de iterações retornado por cada algoritmo (campo \text{iters} no resultado).
    • Compare diretamente: Heron geralmente precisa de muito menos iterações que bissecção para a mesma tolerância relativa.
  • Erros absolutos e relativos:
    • No gráfico semilogy do erro absoluto você verá:
      • Heron: curva que cai quase vertical em poucas iterações.
      • Bissecção: curvas com declive constante, decaindo mais lentamente.
    • No gráfico semilogy do erro relativo o comportamento é análogo.
  • Discussão qualitativa:
    • Heron (Newton) tem convergência quadrática: quando próximo da raiz, o número de dígitos significativos dobra a cada iteração. Isso explica a enorme eficiência em poucas iterações.
    • Bissecção tem convergência linear: cada iteração adiciona aproximadamente uma constante fração (metade do intervalo), logo aumenta lentamente o número de dígitos.
    • Robustez: bissecção é garantida desde que exista intervalo inicial; Heron depende de uma boa escolha de x_0 para evitar iterações ruins (porém para a>0 e x_0>0 Heron normalmente é seguro).
    • Complexidade por iteração: Heron faz uma divisão e algumas operações, bissecção também; custo por iteração é similar, mas número de iterações de Heron é muito menor.
  • Conclusão prática: para computação eficiente (quando se pode garantir aproximação inicial decente), use Heron (Newton). Para garantia robusta sem conhecimento da raiz, bissecção é método seguro. Secante é um bom meio termo (mais rápido que bissecção, não requer derivada), mas aqui a comparação principal é entre Heron e bissecção.

Passo 11

Exemplos numéricos e dicas para a prova (resumo rápido do que escrever):
  • Mostrar uma pequena tabela das primeiras iterações de Heron (como no enunciado) e explicar a queda do erro.
  • Fazer uma estimativa teórica do número de iterações da bissecção usando a fórmula \,k\ge\log_2\!\big((U_0-L_0)/\varepsilon\big).
  • Explicar que critério de parada prático para Heron pode ser |x_{k+1}-x_k|/|x_{k+1}|<10^{-n} e para bissecção usar (U-L)/2<10^{-n}\max(1,\sqrt{a}).
  • Mostrar resultados experimentais com um par de exemplos ( a=25, n=6 e talvez a=2, n=8) para reforçar.

Resposta

(a) Algoritmo proposto: método da bissecção aplicado a f(x)=x^2-a com parada quando \dfrac{U-L}{2}<10^{-n}\max(1,\sqrt{a}) (garante \dfrac{|x-r|}{|r|}<10^{-n}); para Heron usar parada prática \dfrac{|x_{k+1}-x_k|}{|x_{k+1}|}<10^{-n}.
(b) Programa Octave fornecido no Passo 7 (função sqrt_compare(a,n) que implementa Heron e Bissecção, retorna aproximações, iterações, vetores de erros e plota erros absolutos/relativos).
(c) Comparação resumida: Heron (Newton) converge quadraticamente e tipicamente precisa de muito menos iterações (por exemplo, para \sqrt{25} com n=6 Heron leva cerca de 3–4 iterações enquanto bissecção cerca de 22); nos gráficos de erro absoluto e relativo Heron mostra queda muito mais rápida (curva íngreme) enquanto bissecção mostra decaimento linear (declive constante na escala log); conclusão prática — use Heron quando puder garantir boa inicialização (é muito mais eficiente), use bissecção quando precisar de robustez garantida.

Exercícios relacionados