SICP по-русски

Pingback from SICP по-русски » Blog Archive » Сколько программистов нужно, чтобы возвести число A в степень B
Date: January 12, 2008, 11:39 pm

[…] решении упражнения 1.45 я записал процедуру power, возводящую вещественное […]

Comment from thror
Date: February 8, 2008, 9:45 pm

Ну… вообще-то есть достаточно строгое математическое рассуждение, позволяющее получить вашу гипотезу: “для сходимости процесса вычисления корня n-ой степени нужно использовать [log2(n)] торможений усреднением”.

Постараюсь привести здесь его начало, позволяющее выдвинуть такую гипотезу (есть удивительное доказательство ее, но оно слишком громоздко, чтоб уместиться здесь =)).

Итак:

Обозначим корень n-ой степени из a так: x = sqrt_n(a), и a в степени n вот так: x = a**n. Логарифм по основанию 2 от n так log2(n).

Используя метод Ньютона в случае x = sqrt_n(a) имеем

f(x) = x**n - a

функция, нуль которй и есть искомый корень n-ой степени из a. Преобразование Ньютона для нее имеет очевидно вид:

F(x) = (1 - 1/n)x + (1/n)a/(x**(n-1)) ——– [1]

[особое внимание следует обратить на коэффициенты (1-1/n) и (1/n)]

Рассмотрим теперь многократное торможение усреднением для итеративного процесса:

x -> a/(x**(n-1))

k-кратное торможение усреднением дает следующий итеративный процесс:

x -> (1-1/w)x+(1/w)a/(x**(n-1)), w=2**k ——– [2]

[особое внимание следует обратить на коэффициенты (1-1/w) и (1/w)]

Сравните теперь формулы [1] и [2].

Вот теперь, надеюсь, смысл гипотезы на поверхности, а именно, для сходимости итеративного процесса [2] он должен удовлетворять соотношению:

1/w = n

или, что эквивалентно,

k >= ceil(log2(n))

[функия ceil(x) определяется стандартно, например см. Кнут, т.1, Основные Алгоритмы, п. 1.2.4]

Очевидно, наименьшее подходящее k=ceil(log2(n)).

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

Думаю это будет хорошим упражнением для многих читателей =)

–thror

Comment from thror
Date: February 8, 2008, 9:58 pm

Ключом к доказательству является тот факт, что если модифицировать метод Ньютона, внеся определенные изменения в преобразование Ньютона (какое–не скажу =)) то его сходимость не изменится.

При этом k-кратное торможение усреднением можно представить именно таким модифицированным методом Ньютона.

Ну, вроде многие это даже на уроках проходили =)

Comment from Sergey Khenkin
Date: February 9, 2008, 12:25 am

Хм, очень даже любопытно.

Не совсем понятна мысль:
“для сходимости итеративного процесса [2] он должен удовлетворять соотношению: 1/w = n”.

Comment from thror
Date: February 9, 2008, 10:56 am

А, да, фигня получилась =)

1 / w меньше или равно 1 / n

Comment from thror
Date: February 9, 2008, 2:29 pm

Или w больше или равно n, а т.к. w=2**k, то k больше или равно ceil(log2(n))…

На самом деле рассмотрим преобразование Ньютона для функции f(x):

F(x) = x - f (x) / f ‘ (x)

Модифицируем преобразование таким способом:

G(x) = x - f(x) / (q * f ‘ (x))

Тогда для f(x) = x**n - a получим модифицированное преобразование такое:

G(x) = F(x) = (1 - 1/qn)x + (1/qn)a/(x**(n-1)) ——– [3]

Сравним полученную формулу [3] с формулой [2], и выберем множитель q из условия:

w = qn

Следовательно:

q = w / n

или

q = 2**k / n

Так вот, сходимость модифицированного метода Ньютона не нарушится, когда q больше или равно 1, или что тоже самое, w больше или равно n, или k больше или равно ceil(log2(n)).

Вот собственно и весь секрет этого упражнения.

–thror

Comment from gorilych
Date: September 29, 2008, 2:52 pm

Введём более общую функцию усреднения которая переводит f(x) в 1/m[f(x) + (m-1)x]:

(define (average-damp-m f m)
  (lambda (x) (/ (+ (f x)
                    (* (- m 1) x))
                 m)))

Очевидно, что простая функция усреднения average-damp аналогична average-damp-m с параметром m = 2, а (repeated average-damp damp-count) это то же самое, что и average-damp-m при m = 2^(damp-count)

Наш метод “улучшения” создаёт (должен создавать) последовательность чисел, приближающихся к корню n-ной степени из x.

Каждое следующее приближение равно функции улучшения, взятой от предыдущего приближения. В качестве функции улучшения у нас выступает 1/m[x/y^(n-1) + (m-1)y].

Легко показать, что если отклонение предыдущего приближения от решения x^(1/n) составляет малую величину эпсилон (eps/x^(1/n) много меньше 1), то отклонение улучшенного приближения будет приблизительно равно eps*|m-n|/m.

Соответственно, при |m-n|/m больше 1 ряд расходится, при |m-n|/m меньше 1 ряд сходится, при равенстве 1 получаются бесконечные осцилляции вокруг решения. Уточнённое условие сходимости - m > n/2, наилучшая сходимость достигается при m=n.

Comment from gorilych
Date: September 29, 2008, 3:14 pm

Используя новую функцию усреднения достаточно просто создать эффективную функцию вычисления корня n-ной степени:

(define (nth-root n x)
  (fixed-point (average-damp-m (lambda (y)
                                 (/ x (expt y (- n 1)))) n)
               1.0))

Comment from potters-owl
Date: July 6, 2010, 3:33 pm

Любопытно, как ув. thror получил
x -> (1-1/w)x+(1/w)a/(x**(n-1)), w=2**k
для многократного торможения усреднением. У меня получается что угодно, кроме этого
Жаль, что не указано средств обратной связи.

Comment from potters-owl
Date: July 6, 2010, 6:13 pm

впрочем, оказалось достаточно не подставлять сразу у -> x/ y ** (n-1) в формулу торможения усреднением и не пытаться вывести формулу для k-ого торможения, “протаскивая” попутно это отображение n-ого корня, а рассмотреть многократное применение торможения “самого по себе”, как формула сразу стала видна. ЕЩе один довод в пользу подхода, используемого в этом и предыдущем упражнениях )