Я пересматриваю некоторые из предыдущих лекций по SICP. Меня немного смущает понятие фиксированной точки. Процедура фиксированной точки: должен ли я думать об этом таким образом, «это способ найти фиксированную точку данной функции». Итак, f(2) = 2?
Также почему в этой лекции говорится, что новый функция y, отображающая x / y, является фиксированной точкой?
Согласно Фиксированная точка (математика) в Википедии:
В математике фиксированная точка (иногда сокращаемая до фиксированной точки, также известная как инвариантная точка) функции — это элемент области определения функции, который отображается функцией на себя.
Итак, как вы написали, f(2) = 2 указывает, что 2 является фиксированной точкой f.
x / y имеет две переменные. Можно говорить о неподвижных точках функции одной переменной. Один из x и y должен быть константой?
- person Joshua Taylor; 18.08.2014
Просто ответ Этье касается того, что такое фиксированная точка, но остается другая часть вашего вопроса:
Кроме того, почему новая функция y, отображающая x/y, является фиксированной точкой?
Лектор быстро говорит о том, что вы упомянули, но я думаю, что он на самом деле говорит, что x является фиксированной точкой более чем одной функции, и что очевидная функция, для которой x является фиксированной точкой,
у х / у
поскольку
х = х / х
Однако данная процедура вычисления фиксированных точек не будет работать для этой функции, поскольку ее внутренняя процедура iter зацикливается на начальном значении, а функция применяется к начальному значению. Таким образом, последовательность новых/старых значений равна (1,2), (2,1), (1,2),…
√x = x / √x отображается на себя, и таким образом попадает в бесконечный цикл (т.е. мы не сможем получить определение √x подстановкой, так как √x содержится в определении) . Но мне трудно понять, откуда взялось (1,2), (2,1), (1,2), ….
- person ; 21.03.2018
g(y) = x / y и вычисляем обработку значений повторным применением g, начиная с 1; в случае x = 2 получаем: g(1) = 2; г(2) = 1; g(1) = 2 снова, и все это просто колеблется - зацикливается между этими двумя значениями. и процедура do-until работает с парами из них - аргумент g и его результат.
- person Will Ness; 21.03.2018
Это когда вы получаете тот же результат, что и в прошлый раз в повторяемой функции. Чтобы понять это, представьте нормальную функцию для известной последовательности:
Представьте себе функцию f(x) = 2^(n+1)-1. Это называется последовательностью Мерсенна, и вы должны передать ей индекс от 0, и это делает последовательность 1, 3, 7, 15, 31, ... (в основном это на единицу меньше, чем каждая степень 2)
Теперь вы можете сделать ту же последовательность, сделав функцию итеративной. Итеративная версия f(x) = 2x + 1. Теперь x больше не будет индексом, а будет предыдущим результатом. Вы начинаете с 0 и получаете 1, 3, 7, 15, 31, ...
Теперь эта функция не имеет фиксированной точки, потому что результат ее применения всегда больше ее аргумента. Можно сказать, что он взрывается.
Чтобы ответить на ваш первый вопрос. В видео SICP они говорят о квадратном корне. Квадратный корень из n — это фиксированная точка повторяемой функции f(x) = n/x, поскольку sqrt(x^2) = x она не отображается на другие функции.
Общая функция с фиксированной точкой будет похожа на их определение фиксированной точки, и это означает, что вы выполняете итерацию функции до тех пор, пока значение, которое вы вводите в функцию, не будет равно (или достаточно близко) к следующему вычисляемому числу.
Теперь мы видим, что не смогли найти фиксированную точку из Мерсенна, и мы знаем, что нам нужно усреднить демпфирование n/x, чтобы оно сходилось, но некоторые функции на самом деле сходятся сами по себе, например, f(x) = x/4 + 1 сходятся к 3/2. Обратите внимание, что даже если вы усредните демпфирование, оно все равно станет 3/2, поэтому только функции без фиксированной точки будут вечно зацикливаться.
Вот мои два цента. Это действительно может сбивать с толку.
Во-первых, простое определение: точка x является "неподвижной точкой" функции f, если f(x) == x.
Иными словами, x = f(x).
Может ли вышеизложенное иметь какой-то смысл? Кажется маловероятным. В конце концов, он использует определяемое значение.
Однако x не обязательно простое число. Это может быть функция или ленивый бесконечный список, и f может привести к его частичному определению. Затем путем повторной оценки
x = f(x) = f( f(x)) = f( f( f(x))) = f( f( f( f(x)))) = ....
значение определяется все больше и больше. Теперь это действительно напоминает нам числовой пример вычисления фиксированной точки f(y) = (y + n/y)/2 посредством повторного вычисления,
n=25; f(1.0)=13.0; f(13.0)=7.4615383; f(7.4615383)=5.406027;
f(5.406027)=5.0152473, f(5.0152473)=5.0152473; f(5.0152473)=5.0
Важнейшая часть состоит не в том, чтобы ждать, пока закончится бесконечная цепочка оценок (она никогда не заканчивается), а в том, чтобы иметь ленивый список, записывающий последовательность шагов оценки. Затем постепенно определяется наша ценность — бесконечный список: сначала он вообще не определен; тогда его первый (головной) элемент определен, а остальные еще нет; то определены два его первых элемента; и т.д. и т.п. : [1.0,13.0,7.4615383,5.406027,5.0152473,5.000023,5.0,5.0,5.0 ...].
И точно так же, как числовые значения сходятся к некоторому числу, все ближе и ближе приближаясь к «конечному» значению (которое никогда не достигается полностью, но расстояние становится все меньше и меньше), так и бесконечный список результатов сходится к своему конечному значению. , полностью определенный бесконечный список со всеми его определенными элементами (совершенно невозможный подвиг, конечно), все ближе и ближе по определенности к этому конечному значению (проще говоря, когда его элементы определяются одним один, но математики любят сложные).
Аналогично с функциями. Если g(h,n) = n<2 -> 1 ; else -> n*h(h,n-1), то g(error) является (каррированной) функцией одного аргумента, определенной только для n < 2, так как для любого другого аргумента она будет расходиться (вызывать ошибку). Но g( g(error)) определено для всех n < 3; g( g( g(error))) - для всех n < 4 и т. д. Опять же, у нас есть последовательность значений, которая все больше и больше определяется... Итак, предел этой последовательности, "конечное значение", фиксированная точка функции g является такой функцией f, что f = g(f) определена для любого n, каким бы большим он ни был. По совпадению это факториальная функция, определенная без использования рекурсии.
