O método Heron (“dividir e fazer média”), um método antigo para aproximação de raiz quadrada de qualquer número inteiro
, pode ser formulado como:
A aplicação do método consiste em aplicação o método de forma iterativa:
Deste modo, deve-se escolher um valor inicial para
, dito
, e a partir deste encontrar os valores aproximados para
: usa-se
para encontrar
, usa-se
para encontrar
, usa-se
para encontrar
e assim por diante. Como exemplo, vamos estimar
, usando uma estimativa inicial
.
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
com pelo menos
significativos.
b. Usando o algoritmo da questão (a), escreva um programa no Octave que receba como parâmetro o valor
e o
e retorne um valor aproximado para
, com pelo menos
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.
|
|
|
|
| 0 | 7 | 5.285714 |
| 1 | 5.285714 | 5.007722 |
| 2 | 5.007722 | 5.000005 |
| 3 | 5.000005 | 5.000000 |
b. Usando o algoritmo da questão (a), escreva um programa no Octave que receba como parâmetro o valor
c. Compare o algoritmo que você propôs para o cálculo de raiz com o método de Horn. Para isso, verifique:
Passo 1
O enunciado pede três coisas principais:
- (a) Projetar um algoritmo que, usando o método de Heron (a iteração
), encontre uma aproximação para com pelo menos algarismos significativos. - (b) Implementar em Octave um programa que receba
e como parâmetros e retorne a aproximação pedida. - (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 é
. - Deve-se atingir pelo menos
dígitos significativos. Vou usar como critério prático (explicado depois) o critério de erro relativo:
- 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
. - Uma forma simples e prática que usamos em programação e em provas: exigir que o erro relativo seja menor que
, isto é
Isto garante que a aproximação difere da verdadeira por menos de uma parte em
, 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 é
. Erro relativo é
. 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
. Queremos solução de . - O método de Newton para
dá
que é exatamente o método de Heron. Então Heron é Newton aplicado a
.
- Convergência: perto da raiz verdadeira
, o método de Newton converge quadraticamente, o que significa que o erro se reduz aproximadamente como o quadrado do erro anterior:
para uma constante
dependente de
. 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
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:
- Defina
. - Escolha intervalo inicial
que contenha a raiz: - Se
então uma escolha conveniente é (porque ). - Se
escolha .
- Se
- Verifique
. Aqui e ; com as escolhas acima isso estará garantido. - Repetir para
: - Calcule
. - Se
então a nova bissecção é senão . - Registre
(a aproximação atual). - Pare quando o critério da questão estiver satisfeito:
mas, como é desconhecido durante a execução real, em prática use critério equivalente baseado no tamanho do intervalo: Uma prática comum (sem conhecer ) é usar com . Assim garantimos o critério relativo desejado.
- Calcule
- Observe que o número de iterações
necessário para garantir largura de intervalo menor que satisfaz
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:
- Escolher uma estimativa inicial
. Sugestão rápida: ou se , ou se . Outra sugestão comumente boa: . - Repetir:
- Calcule erro absoluto
e erro relativo . - Parar quando
(o critério usado aqui). - Nota prática: como
é desconhecido em execução, podemos usar erro estimado entre iterações:
e parar quando
. Para métodos quadráticos (como Heron) isso é robusto: quando
já está perto de
, 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:
Cole o código abaixo no Octave (arquivo, por exemplo, sqrt_compare.m). O código implementa:
- Função principal que recebe
e ; - 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);
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;
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®;
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 (LL - a)(mm - a) < 0
U = m;
else
L = m;
end
end
bisect_iters = length(xb);
% 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 (LL - 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®;
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);
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;
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;
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.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.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
% 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
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
para garantir o critério relativo.
Passo 8
Como executar e interpretar os resultados (passo a passo para a prova/experimento):
- Salve o código em arquivo chamado, por exemplo,
sqrt_compare.m. - No Octave execute:
res = sqrt_compare(25,6);para testarcom .
- O programa vai mostrar:
- O valor verdadeiro
. - 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.
- O valor verdadeiro
- 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
,
):
- Verdadeira raiz
. - Critério: erro relativo menor que
, isto é erro absoluto menor que . - Bissecção: largura inicial
. Queremos (o fator 2 vem porque o erro máximo ao tomar midpoint é metade da largura), ou seja Então precisa de iterações (aprox). - Heron: pela tabela do enunciado já vimos que com
as iterações convergem assim: , , , . 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
no resultado). - Compare diretamente: Heron geralmente precisa de muito menos iterações que bissecção para a mesma tolerância relativa.
- Reporte o número de iterações retornado por cada algoritmo (campo
- 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.
- No gráfico semilogy do erro absoluto você verá:
- 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
para evitar iterações ruins (porém para e 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
. - Explicar que critério de parada prático para Heron pode ser
e para bissecção usar . - Mostrar resultados experimentais com um par de exemplos (
, e talvez , ) para reforçar.
Resposta
(a) Algoritmo proposto: método da bissecção aplicado a
com parada quando
(garante
); para Heron usar parada prática
.
(b) Programa Octave fornecido no Passo 7 (função
(c) Comparação resumida: Heron (Newton) converge quadraticamente e tipicamente precisa de muito menos iterações (por exemplo, para com
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.
(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