корень уравнения с помощью метода неподвижной точки. У нас есть функция f :: a -> a, и нам нужно
найти решение уравнения:
f x = x
Можно начать с какого-нибудь стартового значения, и подставлять, подставлять, подставлять его в f до
тех пор, пока значение не перестанет изменяться. Так мы найдём решение.
x1 = f x0
x2 = f x1
x3 = f x2
...
до тех пор пока abs (x[N] - x[N-1]) <= eps
Первое наблюдение: функция принимает не произвольные значения, а те для которых имеет смысл опе-
рации: минус, поиск абсолютного значения и сравнение на больще/меньше. Тип нашей функции:
f :: (Ord a, Num a) => a -> a
Ленивые вычисления позволяют нам отделить шаг генерации решений, от шага проверки сходимости.
Сначала мы сделаем список всех подстановок функции f, а затем найдём в этом списке два соседних элемента
расстояние между которыми достаточно мало. Итак первый шаг, генерируем всю последовательность:
Пример ленивых вычислений | 151
xNs = iterate f x0
Мы воспользовались стандартной функцией iterate из Prelude. Теперь ищем два соседних числа:
converge :: (Ord a, Num a) => a -> [a] -> a
converge eps (a:b:xs)
| abs (a - b) <= eps
= a
| otherwise
= converge eps (b:xs)
Поскольку список бесконечный мы можем не проверять случаи для пустого списка. Итоговое решение:
roots :: (Ord a, Num a) => a -> a -> (a -> a) -> a
roots eps x0 f = converge eps $ iterate f x0
За счёт ленивых вычислений функции converge и iterate работают синхронно. Функция converge запра-
шивает новое значение и iterate передаёт его, но только одно! Найдём решение какого-нибудь уравнения.
Запустим интерпретатор. Мы ленимся и не создаём новый модуль для такой “большой” функции. Опреде-
ляем её сразу в интерпретаторе.
Prelude> let converge eps (a:b:xs) = if abs (a-b)<=eps then a else converge eps (b:xs) Prelude> let roots eps x0 f = converge eps $ iterate f x0
Найдём корень уравнения:
x( x − 2) = 0
x 2 − 2 x = 0
1 x 2 = x
2
Prelude> roots 0.001 5 (\x -> x*x/2)
Метод завис, остаётся только нажать ctrl+c для остановки. На самом деле есть одно условие для сходи-
мости метода. Метод сойдётся, если модуль производной функции f меньше единицы. Иначе есть возмож-
ность, что мы будем бесконечно генерировать новые подстановки. Вычислим производную нашей функции:
d 1 x 2 = x
dx 2
Нам следует ожидать решения в интервале от минус единицы до единицы:
Prelude> roots 0.001 0.5 (\x -> x*x/2)
3.0517578125e-5
Мы нашли решение, корень равен нулю. В этой записи Ne-5 означает N · 10 − 5
9.5 Краткое содержание