Повторное применение функций

Question

Чтение этот вопрос заставил меня задуматься: для данной функции f как мы можем знать, что цикл этой формы:

while (x > 2)
   x = f(x)

остановится для любого значения x?Есть ли какой-то простой критерий?

(Тот факт, что f(x) < x для x > 2, похоже, не помогает, поскольку ряды могут сходиться).

В частности, можем ли мы доказать это для sqrt а для log?

Answer 1

Для этих функций достаточно доказательства, что ceil(f(x))<x для x > 2.Вы можете сделать одну итерацию - получить целое число, а затем перейти к простой индукции.

В общем случае, вероятно, лучшая идея - использовать обоснованную индукцию длядокажите это свойство.Однако, как отметил Морон в комментариях, это может быть невозможно в общем случае, и во многих случаях найти правильный порядок довольно сложно.

Правка в ответ на комментарий Амнона:

Если вы хотите использовать обоснованную индукцию, вам придется определить другой строгий порядок, который будет обоснованным.В случае функций, которые вы упомянули, это не сложно: вы можете взять x << y тогда и только тогда, когда ceil(x) < ceil(y), где << является символом для этого нового ордера.Этот порядок, конечно, обоснован на числах больше 2, и sqrt и log уменьшаются по отношению к нему - так что вы можете применить обоснованную индукцию.

Конечно, вВ общем случае такой порядок найти гораздо сложнее.В некоторой степени это также связано с утверждениями об общей корректности в логика Хоара , где необходимо гарантировать аналогичные обязательства для каждой конструкции цикла.

Answer 2

Существует общая теорема, когда последовательность итераций будет сходиться .(Конвергентная последовательность может не останавливаться за конечное число шагов, но она приближается к цели. Вы можете подойти к цели настолько близко, насколько пожелаете, пройдя достаточно далеко в последовательности.)

Последовательность x, f (x), f (f (x)), ... будет сходиться, если f является сжатым отображением. То есть существует положительная постоянная k <1 такая, что для всехх и у, | f (x) - f (y) |<= k | xy |. </p>

Answer 3

Не существует общего алгоритма для определения, будет ли функция f и переменная x завершаться или нет в этом цикле.Проблема остановки может быть сведена к этой проблеме.

Для sqrt и log мы могли бы сделать это безопасно, потому что мы знаем математические свойства этих функций.Скажем, sqrt приближается к 1, log со временем становится отрицательным.Таким образом, условие x < 2 должно быть ложным в какой-то момент.

Надеюсь, это поможет.

Answer 4

(Тот факт, что f (x) 2, похоже, не помогает, поскольку ряды могут сходиться).

Если мы говорим о поплавках здесь, это неправда. Если для всех x > n f(x) строго меньше, чем x, в какой-то момент он достигнет n (поскольку между любыми двумя числами имеется только ограниченное число значений с плавающей запятой).

Конечно, это означает, что вам нужно доказать, что f(x) на самом деле меньше, чем x, используя арифметику с плавающей запятой (т. Е. Математически недостаточно доказать, что она меньше, чем x, потому что тогда f(x) = x все еще может быть верным с плавающими когда разница не достаточна).

Answer 5

Конечно. Для всех положительных чисел x имеет место следующее неравенство:

 log(x) <= x - 1

(это довольно простой результат реального анализа; достаточно заметить, что вторая производная log всегда отрицательна для всех положительных x, поэтому функция вогнута вниз, а x-1 является касательной к функции на x = 1). Из этого практически сразу следует, что ваш while цикл должен завершиться в течение первых ceil(x) - 2 шагов - хотя на самом деле он завершается намного, намного быстрее, чем это.

Аналогичный аргумент установит ваш результат для f(x) = sqrt(x); в частности, вы можете использовать тот факт, что:

sqrt(x) <= x/(2 sqrt(2)) + 1/sqrt(2)

для всех положительных x.

Если вы спрашиваете, верен ли этот результат для реальных программ, а не математически, ответ будет немного более нюансированным, но ненамного. По сути, многие языки на самом деле не предъявляют жестких требований к точности для функции log, поэтому, если у вашей конкретной языковой реализации была абсолютно ужасная математическая библиотека, это свойство могло бы не сохраняться. Тем не менее, это должна быть действительно, действительно ужасная библиотека; это свойство будет иметь место для любой разумной реализации log.

Answer 6

В общем случае все, что можно сказать, это то, что цикл завершится, когда он встретит x _i ≤2.Это не означает, что последовательность будет сходиться, и даже не означает, что она ограничена ниже 2. Это только означает, что последовательность содержит значение, которое не больше 2.

При этом любая последовательностьсодержащая подпоследовательность, которая сходится к значению, строго меньшему двух, (в конце концов) остановится.Это относится к последовательности x _{i + 1} = sqrt (x _i ), поскольку x сходится к 1. В случае y _{i + 1} = log (y _i ), он будет содержать значение меньше 2, прежде чем станет неопределенным для элементов R (хотя он хорошо определен на расширенной комплексной плоскости, C*, но я не думаю, что в целом она будет сходиться, за исключением любых устойчивых точек, которые могут существовать (т. Е. Где z = log (z)). В конечном итоге это означает, что вам необходимо выполнить предварительный анализпоследовательность, чтобы лучше понять ее поведение.

Стандартный тест на сходимость последовательности x _i к точке z состоит в том, что дает ε> 0, существует такое n, чтодля всех i> n, | x _i - z | <ε. <p>В качестве отступления рассмотрим набор Мандельброта , M . Тест дляконкретная точка c в C для элемента в M определяет, является ли последовательность z _{i + 1} = z _i ² + c неограничен, что происходитs всякий раз, когда есть | z _i |> 2. Некоторые элементы M могут сходиться (например, 0), но многие - нет (например, -1).

Answer 7

Я предлагаю прочитать эту запись в Википедии , которая предоставляет полезные указатели.Без дополнительных знаний о f ничего нельзя сказать.