Поиск неподвижной точки повторным преобразованием
Многократное применение одного преобразования превращает его результат в следующее входное значение, а явный подсчет шагов делает условие остановки наблюдаемым.
Что означает поиск значения, которое преобразование оставляет неизменным?
- Работа с преобразованием как со значением процедуры
- Передача каждого преобразованного результата в следующую итерацию
- Использование фиксированного числа шагов как явного правила остановки
- Проверка последовательных приближений для выбранного начального значения
Неподвижная точка функции f представляет собой значение x, для которого f(x) равно x. Преобразование x ↦ 1 + 1/x имеет золотое сечение в качестве неподвижной точки, поэтому его многократное применение начиная с 1.0 порождает приближения, которые колеблются вокруг этого значения.
fixed-point не скрывает решение об остановке внутри ненаблюдаемой погрешности. Она принимает преобразование, текущее приближение и оставшееся число шагов как свое полное состояние. Версия с историей записывает ту же передачу данных, поэтому чередующиеся приближения остаются видимыми.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает 1.6180257510729614 после двенадцати преобразований. Вторая возвращает (1.0 2.0 1.5 1.6666666666666665 1.6 1.625 1.6153846153846154).
Проследите за improve как за обычным значением процедуры, затем наблюдайте, как каждое возвращенное число становится следующим приближением по мере уменьшения remaining. Полные трассы выполнения фиксируют каждый шаг выбранных запусков в пределах фиксированных ограничений времени выполнения.
Измените программу и сравните результат.
Измените число преобразований в первой программе с двенадцати на восемь. До запуска сделайте предположение, окажется результат больше или меньше значения после двенадцати шагов.
Показать подсказку
Приближения чередуются вокруг неподвижной точки, поэтому следите за тем, четным или нечетным является число шагов.