Por que o amortecimento médio acelera magicamente a convergência de calculadoras de ponto fixo?

Question

Estou lendo o SICP e os autores escovam a técnica de amortecimento médio no calcário dos pontos fixos das funções. Entendo que é necessário em certos casos, ou seja, raízes quadradas para diminuir a oscilação da função y = x/y No entanto, não entendo por que isso ajuda magicamente a convergência da função de cálculo de pontos fixo. Ajuda?

editar

Obviamente, eu pensei isso um pouco. Parece que não consigo entender por que a média de uma função por si só aceleraria a convergência quando aplicado repetidamente.

Answer 1

Ele apenas acelera as funções cujos aplicativos repetidos "pularem" o ponto de fixação. Intuitivamente, é como adicionar um freio a um pêndulo - ele parará mais cedo com o freio.

Mas nem todas as funções têm essa propriedade. Considerar f(x)=x/2. Essa função convergirá mais cedo sem o amortecimento médio (base de log de 2 etapas versus base de log (4/3)), porque se aproxima do ponto de fixação de um lado.

Answer 2

Embora eu não possa responder à sua pergunta de forma matemática, tentarei uma intuitiva: as técnicas de correção precisam de um gráfico de funções "planas" em torno do seu ... bem .. Fixpoint. Isso significa: se você imaginar sua função Fixpoint em um gráfico XY, verá que a função cruza a diagonal (+x,+y) exatamente no resultado verdadeiro. Em uma etapa do seu algoritmo de ponto de fixação, você está adivinhando um valor X que precisa estar dentro do intervalo em torno do ponto de interseção em que a primeira derivada está entre (-1 ..+1) e assuma o valor y. O y que você levou estará mais perto do ponto de interseção porque A partir da interseção, é acessível seguindo um caminho que tem uma inclinação menor que +/- 1 , em contraste com o valor X anterior que você utilizou, que tem nesse sentido, a inclinação exata -1. Fica imediatamente claro agora que quanto menor a inclinação, mais a maneira como você faz para o ponto de interseção (o verdadeiro valor da função) ao usar o y como novo X. A melhor função de interpolação é trivialmente uma constante, que tem inclinação 0, dando -lhe o verdadeiro valor na primeira etapa.

Desculpe a todos os matemáticos.