Почему среднее демпфирование магически ускоряет сходимость калькуляторов с фиксированной запятой?

Question

Я читаю через SICP, и авторы оттачивают технику среднего демпфирования при вычислении фиксированных точек функций.Я понимаю, что в некоторых случаях, например, в квадратных корнях, это необходимо для ослабления колебаний функции y = x/y, однако я не понимаю, почему это волшебным образом способствует сходимости функции вычисления с фиксированной точкой.Справка?

edit

Очевидно, я несколько обдумал это.Кажется, я не могу понять, почему усреднение функции само по себе ускоряет сходимость при многократном применении.

Answer 1

Ускоряет только те функции, чьи повторяющиеся приложения «перепрыгивают» точку фиксации. Интуитивно это похоже на добавление тормоза к маятнику - он остановится раньше с тормозом.

Но не каждая функция обладает этим свойством. Рассмотрим f(x)=x/2. Эта функция будет сходиться быстрее без среднего демпфирования (логарифмическая база 2 шага против логарифмической базы (4/3) шага), потому что она приближается к точке фиксации с одной стороны.

Answer 2

Хотя я не могу ответить на ваш вопрос на математической основе, я попробую на интуитивном: Техники с фиксированной точкой нуждаются в "плоском" графе функций вокруг их ... хорошо ... точки фиксации. Это означает: если вы представите свою функцию с фиксированной точкой на графике X-Y, вы увидите, что функция пересекает диагональ (+ x, + y) точно при истинном результате. На одном шаге вашего алгоритма с фиксированной точкой вы угадываете значение X, которое должно находиться в пределах интервала вокруг точки пересечения, где первая производная находится между (-1 .. + 1), и принимаете значение Y. Выбранный вами Y будет ближе к точке пересечения, потому что начиная с пересечения, его можно достичь, следуя траектории с меньшим наклоном, чем +/- 1 , в отличие от предыдущего значения X, используется, что имеет в этом смысле точный наклон -1. Теперь ясно, что чем меньше уклон, тем больше вы продвигаетесь к точке пересечения (истинное значение функции) при использовании Y в качестве нового X. Лучшая функция интерполяции - это тривиальная константа, которая имеет наклон 0, давая вам истинное значение на первом шаге.

Извините всех математиков.