Алгоритмы построения (адаптивных?) Функций

Я ищу алгоритмы для рисования стандартных 2d-графиков для функций, которые могут иметь или не иметь особенности. Цель состоит в том, чтобы написать «Мини-CAS», поэтому у меня нет априорных знаний о типах функций, которые хотят видеть пользователи.

Эта проблема очень старая, поэтому я предполагаю, что в литературе должно быть несколько стандартных алгоритмов. На этот раз у меня не было большого успеха в поиске ссылок через Google.

Я нашел один интересный алгоритм, а именно этот, из «YACAS - Книги алгоритмов» под названием «Адаптивное построение функций».

Итак, вкратце:

• Есть ли стандартные алгоритмы?
• Существует ли набор тестов для известных сложных для построения функций?
• Какие интересные статьи читать?

Я реализовал адаптивную процедуру выборки Mathematica здесь, на GitHub (это один файл C, перейдите в исходное дерево для файла заголовка). Я нашел описание рутины в большой книге по Mathematica давным-давно, и уже некоторое время использую варианты этой реализации. Он в основном делает грубую линейную выборку в интересующей области, а затем возвращается для уточнения областей высокой кривизны. Возможно, что некоторые очень острые черты отсутствуют, но на практике я нахожу это чрезвычайно редким. Этот файл также содержит параллельную версию.

Знание того, как другие CAS делают это, может вам помочь.

$f(x)$$(x(t), y(t))$$f(x)$

1. Начните с равномерно распределенной сетки точек в области построения. (В Mathematica есть параметр, чтобы контролировать, сколько взять, называется PlotPoints.)

2. $(x_1, f(x_1)),\; (x_2, f(x_2)),\; (x_3, f(x_3))$$\frac{x_1+x_2}{2}$$\frac{x_2+x_3}{2}$

3. Если мы еще не достигли предела итерации (установленного MaxRecursionв Mathematica), повторите процедуру с шага 2.

Часть этого обсуждается в книге Стэна Вагона "Математика в действии", которую вы можете увидеть здесь в Google Книгах .

Я реализовал этот алгоритм раньше, чтобы лучше контролировать, сколько раз оценивалась моя дорогостоящая функция для вычисления. Вот код Mathematica для шага 2:

nd[{points_, values_}] :=
Transpose@{(Drop[points, 1] + Drop[points, -1])/2,
Differences[values]/Differences[points]}

subdivide1d[result_, resolution_, maxAngle_: 10] :=
  Module[
    {deriv, angle, dangle, pos, nf},
    deriv = nd[result\[Transpose]];
    angle = ArcTan[#2] & @@@ deriv;
    dangle = Differences[angle];
    pos = Flatten@Position[dangle, d_ /; Abs[d] > maxAngle/180 Pi];
    pos = Union[pos, pos + 1];
    nf = Nearest[result[[All, 1]]];
    Select[deriv[[pos, 1]], Abs[# - First@nf[#]] > resolution &]
  ]

Веб-страница MathWorld на функциональных графиках содержит ссылки на несколько статей, которые, как представляется, имеют отношение к адаптивному построению функций. Цитирование страницы:

Хорошие процедуры для построения графиков используют адаптивные алгоритмы, которые отображают больше точек в регионах, где функция изменяется наиболее быстро (Wagon 1991, Math Works 1992, Heck 1993, Wickham-Jones 1994). Таппер (1996) разработал алгоритм [...]

С другой стороны, в Google я наткнулся на бумагу

www.cs.uic.edu/~wilkinson/Publications/plotfunc.pdf

это объясняет, как правильно выбрать домен и другие вещи. Я надеюсь, что они полезны для вас.

Я нашел эту тему и подумал, что должен поделиться страницей с разработчиками, чтобы добавить ее в библиотеку Julia Plots.jl. Мы попробовали несколько методов, чтобы увидеть, что даст хорошие результаты, начиная с заметок по реализации Mathematica. Добавление некоторого сокращения, небольшого возмущения, которое не начиналось точно в конечных точках интервала, предела рекурсии и оценки ошибки двойной сетки - все это было необходимо, чтобы «все было правильно». Поток также указывает на открытый исходный код для реализации. Так что потребовалось немного доработать, но добавление этих функций сделало его довольно надежным (согласно тестам, как показано в теме).