Raiz quadrada de um número positivo

Consideremos o problema de calcular a raiz quadrada de um número positivo , isto é, tal que e .

Como é que um computador calcula raízes quadradas? A maneira usual é usarmos o método de Newton para determinar a solução da equação . Começando com uma aproximação inicial para o valor da raiz quadrada de , conseguimos obter uma melhor aproximação calculando a média aritmética de e de .

Consideremos o cálculo de . Tomando o valor como aproximação inicial, obtemos a tabela:

Aproximação         Quociente         Média

1                   2/1               (2+1)/2=1.5

1.5                 2/1.5=1.3333      (1.3333+1.5)/2=1.4167

1.4167              2/1.4167=1.4118   (1.4167+1.4118)/2=1.4142

1.4142              ...

Continuando com este processo iremos obter de cada vez melhores aproximações ao valor de .

Este algoritmo na sua presente forma foi descoberto por Herão de Alexandria no século um A.C.

A forma recursiva está implementada na função em GNU/Octave heron.m

function y=heron(x,y,tol)
  while(abs(x-y.^2)>tol)
    y=heron(x,(y+x/y)/2,tol);
  endwhile;
endfunction;

O cálculo de uma aproximação à raiz quadrada de que corresponde ao comando heron(2,1,.001) é de facto a composição seguinte (processo definido por recorrência linear):

> heron(2,1,.001)
> heron(2,heron(2,3/2,.001),.001)
> heron(2,heron(2,heron(2,17/12,.001),.001),.001)
577/408