1.3.3 Funções como Métodos Gerais

Introduzimos funções compostas na seção 1.1.4 como um mecanismo para abstrair padrões de operações numéricas de modo a torná-los independentes dos números particulares envolvidos. Com funções de ordem superior, como a função integral da seção 1.3.1, começamos a ver um tipo mais poderoso de abstração: funções usadas para expressar métodos gerais de computação, independentemente das funções particulares envolvidas. Nesta seção discutimos dois exemplos mais elaborados — métodos gerais para encontrar zeros e pontos fixos de funções — e mostramos como esses métodos podem ser expressos diretamente como funções.

Encontrando raízes de equações pelo método da metade do intervalo

O método da metade do intervalo é uma técnica simples mas poderosa para encontrar raízes de uma equação $f(x)=0$, onde $f$ é uma função contínua. A ideia é que, se nos forem dados pontos $a$ e $b$ tais que $f(a) < 0 < f(b)$, então $f$ deve ter pelo menos um zero entre $a$ e $b$. Para localizar um zero, seja $x$ a média de $a$ e $b$ e calcule $f(x)$. Se $f(x) > 0$, então $f$ deve ter um zero entre $a$ e $x$. Se $f(x) < 0$, então $f$ deve ter um zero entre $x$ e $b$. Continuando dessa maneira, podemos identificar intervalos cada vez menores nos quais $f$ deve ter um zero. Quando chegamos a um ponto onde o intervalo é pequeno o suficiente, o processo para. Como o intervalo de incerteza é reduzido pela metade em cada passo do processo, o número máximo de passos necessários cresce como $\Theta(\log(L/T))$, onde $L$ é o comprimento do intervalo original e $T$ é a tolerância de erro (isto é, o tamanho do intervalo que consideraremos "pequeno o suficiente").

Aqui está uma função que implementa esta estratégia:

Exemplo de Código

function search(f, neg_point, pos_point) {
  const midpoint = average(neg_point, pos_point);
  if (close_enough(neg_point, pos_point)) {
      return midpoint;
  } else {
      const test_value = f(midpoint);
      return positive(test_value)
             ? search(f, neg_point, midpoint)
             : negative(test_value)
             ? search(f, midpoint, pos_point)
             : midpoint;
  }
}

function search(f, neg_point, pos_point) { const midpoint = average(neg_point, pos_point); if (close_enough(neg_point, pos_point)) { return midpoint; } else { const test_value = f(midpoint); return positive(test_value) ? search(f, neg_point, midpoint) : negative(test_value) ? search(f, midpoint, pos_point) : midpoint; } }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Assumimos que inicialmente recebemos a função $f$ juntamente com pontos nos quais seus valores são negativos e positivos. Primeiro calculamos o ponto médio dos dois pontos dados. Em seguida, verificamos se o intervalo dado é pequeno o suficiente e, se for, simplesmente retornamos o ponto médio como nossa resposta. Caso contrário, calculamos como um valor de teste o valor de $f$ no ponto médio. Se o valor de teste for positivo, continuamos o processo com um novo intervalo indo do ponto negativo original até o ponto médio. Se o valor de teste for negativo, continuamos com o intervalo do ponto médio ao ponto positivo. Finalmente, há a possibilidade de que o valor de teste seja 0, caso em que o ponto médio é em si a raiz que estamos procurando.

Para testar se os pontos finais estão "próximos o suficiente", podemos usar uma função similar à usada na seção 1.1.7 para calcular raízes quadradas:¹

Exemplo de Código

function close_enough(x, y) {
  return abs(x - y) < 0.001;
}

function close_enough(x, y) { return abs(x - y) < 0.001; }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

A função search é complicada para usar diretamente, porque podemos acidentalmente fornecer pontos nos quais os valores de $f$ não têm o sinal necessário, caso em que obteríamos uma resposta errada. Em vez disso, usaremos search por meio da seguinte função, que verifica quais dos pontos finais tem um valor de função negativo e qual tem um valor positivo, e chama a função search de acordo. Se a função tiver o mesmo sinal nos dois pontos dados, o método da metade do intervalo não pode ser usado, caso em que a função sinaliza um erro.²

Exemplo de Código

function half_interval_method(f, a, b) {
  const a_value = f(a);
  const b_value = f(b);
  return negative(a_value) && positive(b_value)
         ? search(f, a, b)
         : negative(b_value) && positive(a_value)
         ? search(f, b, a)
         : error("values are not of opposite sign");
}

function half_interval_method(f, a, b) { const a_value = f(a); const b_value = f(b); return negative(a_value) && positive(b_value) ? search(f, a, b) : negative(b_value) && positive(a_value) ? search(f, b, a) : error("values are not of opposite sign"); }

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

O exemplo a seguir usa o método da metade do intervalo para aproximar $\pi$ como a raiz entre 2 e 4 de $\sin x = 0$:

Exemplo de Código

half_interval_method(math_sin, 2, 4);

half_interval_method(math_sin, 2, 4);

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Aqui está outro exemplo, usando o método da metade do intervalo para procurar uma raiz da equação $x^3 - 2x - 3 = 0$ entre 1 e 2:

Exemplo de Código

half_interval_method(x => x * x * x - 2 * x - 3, 1, 2);

half_interval_method(x => x * x * x - 2 * x - 3, 1, 2);

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Encontrando pontos fixos de funções

Um número $x$ é chamado de ponto fixo de uma função $f$ se $x$ satisfaz a equação $f(x)=x$. Para algumas funções $f$ podemos localizar um ponto fixo começando com um palpite inicial e aplicando $f$ repetidamente,

$$f(x), \quad f(f(x)), \quad f(f(f(x))), \quad \ldots$$

até que o valor não mude muito. Usando esta ideia, podemos desenvolver uma função fixed_point que recebe como entradas uma função e um palpite inicial e produz uma aproximação de um ponto fixo da função. Aplicamos a função repetidamente até encontrarmos dois valores sucessivos cuja diferença é menor que alguma tolerância prescrita:

Exemplo de Código

const tolerance = 0.00001;
function fixed_point(f, first_guess) {
  function close_enough(x, y) {
      return abs(x - y) < tolerance;
  }
  function try_with(guess) {
      const next = f(guess);
      return close_enough(guess, next)
             ? next
             : try_with(next);
  }
  return try_with(first_guess);
}

const tolerance = 0.00001; function fixed_point(f, first_guess) { function close_enough(x, y) { return abs(x - y) < tolerance; } function try_with(guess) { const next = f(guess); return close_enough(guess, next) ? next : try_with(next); } return try_with(first_guess); }

Código editável · Ctrl+Enter executa · Esc solta o foco

Por exemplo, podemos usar este método para aproximar o ponto fixo do cosseno, começando com 1 como palpite inicial:³

Exemplo de Código

fixed_point(math_cos, 1);

fixed_point(math_cos, 1);

⛓ sessão — este bloco compartilha o ambiente da página: as declarações dos blocos anteriores são avaliadas antes deleCódigo editável · Ctrl+Enter executa · Esc solta o foco

Da mesma forma, podemos encontrar uma solução da equação $y = \sin y + \cos y$:

Exemplo de Código

fixed_point(y => math_sin(y) + math_cos(y), 1);

fixed_point(y => math_sin(y) + math_cos(y), 1);

Código editável · Ctrl+Enter executa · Esc solta o foco

O processo de busca de ponto fixo nos lembra o processo que usamos para encontrar raízes quadradas. Ambos são baseados na ideia de melhorar repetidamente um palpite até que o resultado satisfaça algum critério. De fato, podemos formular facilmente a computação de raiz quadrada como uma busca de ponto fixo. Calcular a raiz quadrada de algum número $x$ requer encontrar um $y$ tal que $y^2 = x$. Colocando essa equação na forma equivalente $y = x/y$, reconhecemos que estamos procurando um ponto fixo da função $y \mapsto x/y$, e podemos, portanto, tentar calcular raízes quadradas como

function sqrt(x) {
    return fixed_point(y => x / y, 1);
}

Infelizmente, esta busca de ponto fixo não converge. Considere um palpite inicial $y_1$. O próximo palpite é $y_2 = x/y_1$ e o próximo palpite é $y_3 = x/y_2 = x/(x/y_1) = y_1$. Isso resulta em um loop infinito no qual os dois palpites $y_1$ e $y_2$ se repetem indefinidamente, oscilando em torno da resposta.

Uma maneira de controlar tais oscilações é evitar que os palpites mudem tanto. Como a resposta está sempre entre nosso palpite $y$ e $x/y$, podemos fazer um novo palpite que não está tão longe de $y$ quanto $x/y$ fazendo a média de $y$ com $x/y$, para que o próximo palpite após $y$ seja $(1/2)(y + x/y)$ em vez de $x/y$. O processo de fazer tal sequência de palpites é simplesmente o processo de procurar por um ponto fixo de $y \mapsto (1/2)(y + x/y)$:

Exemplo de Código

function sqrt(x) {
  return fixed_point(y => average(y, x / y), 1);
}

function sqrt(x) { return fixed_point(y => average(y, x / y), 1); }

Código editável · Ctrl+Enter executa · Esc solta o foco

(Observe que $y = (1/2)(y + x/y)$ é uma transformação simples da equação $y = x/y$; para derivar isso, some $y$ a ambos os lados da equação e divida por 2.)

Com essa modificação, a função de raiz quadrada funciona. Na verdade, se desenrolarmos as declarações, podemos ver que a sequência de aproximações ao ponto fixo de busca de ponto fixo é precisamente a mesma sequência gerada pela nossa função de raiz quadrada original da seção 1.1.7. Este método de fazer a média de aproximações sucessivas a uma solução, uma técnica que chamamos de amortecimento médio, geralmente ajuda a convergência de buscas de ponto fixo.

Exercício 1.35

Mostre que a razão áurea $\phi$ (seção 1.2.2) é um ponto fixo da transformação $x \mapsto 1 + 1/x$, e use isso para calcular $\phi$ por meio da função fixed_point.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

A demonstração. $\phi$ satisfaz $\phi^2 = \phi + 1$ (é a raiz positiva dessa equação, por definição). Dividindo os dois lados por $\phi$: $\phi = 1 + 1/\phi$ — ou seja, $\phi$ é exatamente um ponto fixo de $x \mapsto 1 + 1/x$.

Exemplo de Código

fixed_point(x => 1 + 1 / x, 1);

fixed_point(x => 1 + 1 / x, 1);

Código editável · Ctrl+Enter executa · Esc solta o foco

O resultado, $\approx 1{,}6180$, é a razão áurea.

Resolvi o exercício 1.35

Exercício 1.36

Modifique fixed_point para que ela imprima a sequência de aproximações que gera, usando a função primitiva display mostrada no exercício 1.22. Então encontre uma solução de $x^x = 1000$ encontrando um ponto fixo de $x \mapsto \log(1000)/\log(x)$. (Use a função primitiva math_log do JavaScript, que calcula logaritmos naturais.) Compare o número de passos necessários com e sem amortecimento médio. (Observe que você não pode iniciar fixed_point com um palpite de 1, pois isso causaria divisão por $\log(1) = 0$.)

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Versão com impressão e a busca por $x^x = 1000$:

Exemplo de Código

const tolerance = 0.00001;
function fixed_point(f, first_guess) {
  function close_enough(x, y) {
      return math_abs(x - y) < tolerance;
  }
  function try_with(guess) {
      display(guess);
      const next = f(guess);
      return close_enough(guess, next)
             ? next
             : try_with(next);
  }
  return try_with(first_guess);
}

// sem amortecimento:
fixed_point(x => math_log(1000) / math_log(x), 2);

const tolerance = 0.00001; function fixed_point(f, first_guess) { function close_enough(x, y) { return math_abs(x - y) < tolerance; } function try_with(guess) { display(guess); const next = f(guess); return close_enough(guess, next) ? next : try_with(next); } return try_with(first_guess); } // sem amortecimento: fixed_point(x => math_log(1000) / math_log(x), 2);

Código editável · Ctrl+Enter executa · Esc solta o foco

Sem amortecimento a sequência oscila e leva cerca de 34 passos. Com amortecimento médio — troque a última linha por

fixed_point(x => (x + math_log(1000) / math_log(x)) / 2, 2);

— converge em cerca de 9 passos para $x \approx 4{,}5555$. O amortecimento não muda o ponto fixo (a média de $x$ com $f(x)$ coincide com $x$ exatamente quando $f(x) = x$), só doma a oscilação.

Resolvi o exercício 1.36

Exercício 1.37

a. Uma fração contínua infinita é uma expressão da forma

$$f = \frac{N_1}{D_1 + \frac{N_2}{D_2 + \frac{N_3}{D_3 + \cdots}}}$$

Como exemplo, pode-se mostrar que a expansão em fração contínua infinita com os $N_i$ e os $D_i$ todos iguais a 1 produz $1/\phi$, onde $\phi$ é a razão áurea (descrita na seção 1.2.2). Uma forma de aproximar uma fração contínua infinita é truncá-la após um dado número de termos. Tal truncamento — uma chamada fração contínua de $k$ termos — tem a forma

$$\frac{N_1}{D_1 + \frac{N_2}{\ddots + \frac{N_K}{D_K}}}$$

Suponha que n e d sejam funções de um argumento (o índice do termo $i$) que retornam os $N_i$ e $D_i$ dos termos da fração contínua. Declare uma função cont_frac tal que avaliar cont_frac(n, d, k) calcule o valor de uma fração contínua de $k$ termos. Verifique sua função aproximando $1/\phi$ usando

cont_frac(i => 1, i => 1, k)

para valores sucessivos de k. Quão grande você tem que fazer k para obter uma aproximação que é precisa em 4 casas decimais?

b. Se sua função cont_frac gera um processo recursivo, escreva uma que gere um processo iterativo. Se ela gera um processo iterativo, escreva uma que gere um processo recursivo.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

a. Recursivo — contando do termo $k$ para dentro:

Exemplo de Código

function cont_frac(n, d, k) {
  function frac(i) {
      return i > k
             ? 0
             : n(i) / (d(i) + frac(i + 1));
  }
  return frac(1);
}

cont_frac(i => 1, i => 1, 12);

function cont_frac(n, d, k) { function frac(i) { return i > k ? 0 : n(i) / (d(i) + frac(i + 1)); } return frac(1); } cont_frac(i => 1, i => 1, 12);

Código editável · Ctrl+Enter executa · Esc solta o foco

Com $1/\phi \approx 0{,}6180$, a precisão de 4 casas decimais chega com k = 11 ou 12.

b. Iterativo — construindo de trás para frente, do termo $k$ até o 1:

Exemplo de Código

function cont_frac(n, d, k) {
  function iter(i, result) {
      return i === 0
             ? result
             : iter(i - 1, n(i) / (d(i) + result));
  }
  return iter(k, 0);
}

cont_frac(i => 1, i => 1, 12);

function cont_frac(n, d, k) { function iter(i, result) { return i === 0 ? result : iter(i - 1, n(i) / (d(i) + result)); } return iter(k, 0); } cont_frac(i => 1, i => 1, 12);

Código editável · Ctrl+Enter executa · Esc solta o foco

A fração contínua se "enrola" naturalmente de dentro para fora, então a versão iterativa começa pelo último termo — um caso em que pensar na ordem de construção é o coração do exercício.

Resolvi o exercício 1.37

Exercício 1.38

Em 1737, o matemático suíço Leonhard Euler publicou um artigo De Fractionibus Continuis, que incluía uma expansão em fração contínua para $e - 2$, onde $e$ é a base dos logaritmos naturais. Nesta fração, os $N_i$ são todos 1, e os $D_i$ são sucessivamente 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, ... Escreva um programa que usa sua função cont_frac do exercício 1.37 para aproximar $e$, baseado na expansão de Euler.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ideia. Só precisamos descrever a sequência de denominadores $1, 2, 1, 1, 4, 1, 1, 6, \ldots$: nas posições $2, 5, 8, \ldots$ (isto é, $i \equiv 2 \pmod 3$) o valor é $\frac{2(i+1)}{3}$; nas demais é 1.

Exemplo de Código

function cont_frac(n, d, k) {
  function iter(i, result) {
      return i === 0
             ? result
             : iter(i - 1, n(i) / (d(i) + result));
  }
  return iter(k, 0);
}

function euler_d(i) {
  return i % 3 === 2
         ? 2 * (i + 1) / 3
         : 1;
}

2 + cont_frac(i => 1, euler_d, 20);

function cont_frac(n, d, k) { function iter(i, result) { return i === 0 ? result : iter(i - 1, n(i) / (d(i) + result)); } return iter(k, 0); } function euler_d(i) { return i % 3 === 2 ? 2 * (i + 1) / 3 : 1; } 2 + cont_frac(i => 1, euler_d, 20);

Código editável · Ctrl+Enter executa · Esc solta o foco

Com 20 termos o resultado já é $e \approx 2{,}718281828$ com todas as casas mostradas corretas.

Resolvi o exercício 1.38

Exercício 1.39

Uma fração contínua para a função tangente foi publicada em 1770 pelo matemático alemão J.H. Lambert:

$$\tan x = \frac{x}{1 - \frac{x^2}{3 - \frac{x^2}{5 - \cdots}}}$$

onde $x$ está em radianos. Declare uma função tan_cf(x, k) que calcula uma aproximação da função tangente baseada na fórmula de Lambert. A constante k especifica o número de termos a calcular, como no exercício 1.37.

💡 Mostrar solução — tente primeiro!💡 Esconder solução

Ideia. Na fórmula de Lambert, $N_1 = x$ e os demais $N_i = -x^2$ (o sinal de menos da fórmula vira sinal do numerador); os denominadores são os ímpares $1, 3, 5, \ldots$

Exemplo de Código

function cont_frac(n, d, k) {
  function iter(i, result) {
      return i === 0
             ? result
             : iter(i - 1, n(i) / (d(i) + result));
  }
  return iter(k, 0);
}

function tan_cf(x, k) {
  return cont_frac(i => i === 1 ? x : - x * x,
                   i => 2 * i - 1,
                   k);
}

display(tan_cf(1, 10));
math_tan(1);

function cont_frac(n, d, k) { function iter(i, result) { return i === 0 ? result : iter(i - 1, n(i) / (d(i) + result)); } return iter(k, 0); } function tan_cf(x, k) { return cont_frac(i => i === 1 ? x : - x * x, i => 2 * i - 1, k); } display(tan_cf(1, 10)); math_tan(1);

Código editável · Ctrl+Enter executa · Esc solta o foco

Com $k = 10$, tan_cf(1, 10) coincide com math_tan(1) $\approx 1{,}5574$ em todas as casas exibidas — a fração de Lambert converge rápido.

Resolvi o exercício 1.39

---

Notas de Rodapé

1 Usamos 0.001 como um número "pequeno" representativo para indicar uma tolerância para o erro aceitável em um cálculo. A tolerância apropriada para um cálculo real depende do problema a ser resolvido e das limitações do computador e do algoritmo. Isso é muitas vezes uma consideração muito sutil, exigindo ajuda de um analista numérico ou algum outro tipo de mago.

2 Isso pode ser feito usando error, que recebe como argumento uma string que é exibida como mensagem de erro juntamente com a informação de que o programa foi interrompido.

3 Tente isso durante um intervalo de ócio. Veja se você consegue usar isso para implementar a calculadora de ``logaritmo'' inventada pelo brincalhão mencionado na nota de rodapé da seção 1.3.3.

📝 Encontrou algo errado nesta página?

Sua ajuda é muito importante para melhorar a qualidade da tradução!

🐛 Encontrou um erro?

Se você encontrou:

• Erro de tradução (palavra incorreta, termo técnico errado)
• Erro de ortografia ou gramática
• Link quebrado
• Código de exemplo que não funciona
• Problema de formatação

Reporte um bug →

❓ Tem uma dúvida?

Se você tem:

• Dúvida sobre o conteúdo desta seção
• Pergunta sobre um conceito do SICP
• Dificuldade em entender algum exemplo
• Questão sobre a tradução de algum termo

Inicie uma discussão →

💡 Tem uma sugestão de melhoria?

Se você quer sugerir:

• Melhoria na explicação
• Exemplo adicional
• Recurso visual (diagrama, ilustração)
• Qualquer outra ideia

Sugira uma melhoria →

🌍 Quer discutir a tradução?

Se você quer debater:

• Escolha de tradução de algum termo
• Consistência de terminologia
• Nuances do português

Discussão de tradução →

Obrigado por ajudar a melhorar o SICP.js PT-BR! ✨