Приближение с помощью кривых: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Следующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
Перевод статьи "Curve fitting" с английского
(нет различий)

Версия от 13:11, 21 июня 2016

Приближение кривой, имеющей шум (случайные отклонения), с помощью модели асимметричного пика с итеративным процессом (Алгоритм Гаусса - Ньютона[англ.]* с переменным коэффициентом затухания α).
Сверху: исходные данные и модель.
Снизу: изменение нормализованной суммы квадратов отклонений.

Приближение с помощью кривых [1][2] — это процесс построения кривой или математической функции, которая наилучшим образом огибает заданные точки [3] с возможными ограничениями на кривую [4]. Для построения огибающей может использоваться либо интерполяция [5], где требуется точное прохождение кривой через точки, либо сглаживание[англ.] [6][7], когда "сглаживающая" функция огибает точки приближённо. Связанный раздел — регрессионный анализ [8][9], который фокусируется, главным образом, на вопросах статистического вывода, таких как, какая неопределённость заключена в кривой, которая приближает данные с некоторыми случайными ошибками. Огибающие кривые могут быть использованы для визуализации данных [10][11], для вычисления значений функции в точках, в которых значение не задано [12] и для определения связи между двумя и более переменными [13]. Экстраполяция означает использование огибающей кривой за пределами области определения данных наблюдения [14] и порождает некоторую неопределённость [15], поскольку может отражать метод построения кривой.

Различные типы приближения с помощью кривых

Приближение заданных точек функциями

Чаще всего ищется приближение в виде y=f(x).

Приближение заданных точек линейными и полиномиальными функциями

Основная статья: Полиномиальная регрессия
См. также: Интерполяция алгебраическими многочленами
Приближение синуса полиномиальными функциями
Приближение точек, сгенерированных функцией синуса, полиномиальными функциями.
Красная прямая — многочлен первой степени , зелёная линия — второй степени , оранжевая линия — третьей степени , а синяя — четвёртой степени

Начнём с многочлена первой степени:

Это прямая с угловым коэффициентом a. Прямая соединяет любые две точки, так что многочлен первой степени проходит через любые две точки с различными x координатами.

Если порядок уравнения увеличить до многочленов второй степени, получим:

Кривая проходит через три точки.

Если увеличить порядок многочлена до третей степени, получим:

Кривая проходит через четыре точки.

Более общее утверждение гласит: кривая будет удовлетворять в точности четырём ограничениям. Каждое ограничение может быть точкой, углом, или кривизной (которая является обратной величиной от радиуса соприкасающейся окружности). Ограничения в виде угла и кривизны чаще всего добавляется к концам кривой, и такие ограничения часто называются граничными условиями. Одинаковые конечные условия часто используются для обеспечения гладкого сопряжения полиномиальных кривых внутри сплайна. Ограничения более высокого порядка, такие как "скорость изменения кривизны ", также могут быть заданы. Это, например, может быть использовано в строительстве автострадных развязок для расчёта скорости изменения сил, действующих на автомобиль (см. рывок) во время прохождения развязки и расчёта максимальной допустимой скорости.

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

Если имеется более чем n + 1 ограничений (где n будет степенью многочлена), полиномиальная кривая может продолжать удовлетворять этим условиям. Точная аппроксимация не гарантируется (но может получиться, например, в случае приближения многочленом первой степени трёх коллинеарных точек). В общем случае, однако, нужны некоторые методы осуществления приближённой аппроксимации. Метод наименьших квадратов является одним из способов сравнения отклонений.

Имеется несколько причин для получения приближённого решения, когда просто увеличение степени многочлена дало бы точное прохождение через точки:

  • Даже если точное решение существует, из этого не следует, что его легко найти. В некоторых алгоритмах можем получить расходящуюся последовательность и точное решение может оказаться невычислимым, в других случаях может потребоваться слишком много компьютерного времени для нахождения точного решения. В этих ситуациях может оказаться более приемлемым приближённое решение.
  • Может быть более приемлем эффект усреднения ненадёжных данных в выборке, а не выгибание кривой для точного следования точкам выборки.
  • Феномен Рунге: при интерполяции полиномами высоких степеней может возникнуть эффект нежелательных осцилляций. Если кривая проходит через точки A и B, от кривой ожидается, что она пройдёт где-то близко к середине отрезка AB. Это может оказаться неверным в случае многочленов высокой степени — отклонение может быть очень велико. Для многочленов малой степени кривая, скорее всего, пройдёт рядом с серединой отрезка (а в случае многочлена первой степени обязательно пройдёт через центр).
  • Многочлены низкой степени обычно гладкие, а многочлены высокой степени, как правило, "волнистые". Говоря точнее, максимальное число точек перегиба полиномиальной кривой равно n-2, где n — порядок многочлена. Точка перегиба — это точка, где кривизна меняет знак. Заметим, что многочлены высокой степени только "могут" быть волнистыми, они также могут быть и ровными, но нет никаких гарантий ровности, в отличие от многочленов малого порядка. Многочлен пятнадцатой степени может иметь, как максимум, тринадцать точек перегиба, но может иметь двенадцать, одиннадцать, и так далее до нуля.

Степень многочлена, более высокая, чем необходимо для точного прохождения кривой через точки, нежелательна по всем перечисленным выше причинам, но, кроме того, приводит к бесконечному числу решений. Например, многочлен первой степени (прямая) с ограничением одной точкой вместо обычных двух приводит к бесконечному числу решений. Отсюда вырастает проблема — как сравнивать и выбрать только одно решение, и это может стать проблемой как для программ, так и для людей. По этой причине лучший выбор — как можно меньшая степень для точного выполнения всех ограничений, и, может быть, даже меньшая степень, если приближённое решение допустимо.

Приближение заданных точек другими функциями

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

В спектроскопии данные могут быть приближены нормальным распределением, распределением Коши, контуром Фойгта[англ.] и связанными функциями.

Алгебраическое приближение и геометрическое приближение кривыми

Для алгебраического анализа данных, "приближение" обычно означает поиск кривой, минимизирующей вертикальное (по оси y) отклонение точки от кривой (к примеру, метод наименьших квадратов). Для графических приложений и при работе с изображениями геометрическое приближение ищет наилучшее визуальное приближение, что, обычно, означает попытку минимизировать расстояние до кривой (к примеру, метод наименьших полных квадратов?!) или минимизируется отклонения по обеим координатам. Геометрическое приближение непопулярно, поскольку, обычно, вовлекает нелинейные и/или итеративные вычисления, хотя оно и даёт эстетически более приемлемый и геометрически более аккуратный результат [16][17][18].

Приближение заданных точек плоскими кривыми

Если функция не может быть задана в виде , можно попытаться приблизить с помощью плоской кривой[англ.]*.

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

В случае параметрической кривой эффективно рассматривать каждую координату как отдельную функцию от длины кривой. Если исходные данные можно упорядочить, можно использовать длину хорды [19].

Приближение заданных точек геометрически

Приближение окружностью по методу Куупа (Coope). Точки соответствуют дуге окружности с центром в (1, 1) и радиусом 4.
Различные модели приближения эллипсом
Приближение эллипсом с минимизацией алгебраического расстояния (метод Фитцгиббона).

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

Приближение эллипсом геометрически

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

Приложение к поверхностям

Подробнее см. Представление поверхностей в компьютерах

Заметим, что хотя до сих пор обсуждение относилось к двумерным кривым, большинство результатов распространяется на трёхмерные поверхности, каждый кусочек которых определяется сеткой кривых в двух параметрических направлениях. Поверхность может состоять из одного и более кусков в обоих направлениях.

Программы

Множество пакетов обработки статистических данных[англ.], таких как R, и пакетов программ численного анализа[англ.], таких как GNU Scientific Library, MLAB?!,DataMelt?!, Maple, MATLAB, SciPy и OpenOpt включают средства приближения кривыми в различных сценариях. Существуют также программы, специально написанные для приближения кривыми. Их можно найти в статьях «Пакеты обработки статистических данных[англ.]» и «Пакеты программ численного анализа[англ.]».

См. также

Примечания

  1. ↑ Arlinghaus, 1994.
  2. ↑ Kolb, 1984.
  3. ↑ Halli, Rao, 1992, с. 165.
  4. ↑ Silver, 2012.
  5. ↑ Kiusalaas, 2005, с. 21.
  6. ↑ Guest, 2012, с. 349.
  7. ↑ См. также: Сглаживающий оператор?!
  8. ↑ Пакет Prism[англ.]кампании. Документация: «Fitting Models to Biological Data Using Linear and Nonlinear Regression» (Harvey Motulsky, Arthur Christopoulos).
  9. ↑ Freund, Wilson, Sa, 2006, с. 269.
  10. ↑ Daud, Sagayan, Yahya, Najwati, 2009, с. 689.
  11. ↑ Hauser, 2009, с. 227.
  12. ↑ Marton, 1976, с. 150.
  13. ↑ Salkind, 2010, с. 266.
  14. ↑ Klosterman, 1990, с. 1.
  15. ↑ Yoe, 1996, с. 69.
  16. ↑ Ahn, 2008.
  17. ↑ Chernov, Ma, 2011, с. 285–302.
  18. ↑ Liu, Wang, 2008, с. 384–397.
  19. ↑ Ahlberg, Nilson, Walsh, 1967, с. 51.
  20. ↑ Coope, 1993, с. 381.
  21. ↑ Sheer, 1997.

Литература

  • Sandra Lach Arlinghaus. Practical Handbook of Curve Fitting. — CRC Press, 1994. — ISBN 0849301434.
  • William M. Kolb. Curve Fitting for Programmable Calculators. — 3. — Syntec, Incorporated, 1984. — ISBN 0943494028.
  • John R. Hauser. Numerical Methods for Nonlinear Engineering Models. — Springer, 2009. — ISBN 978-1-4020-9919-9.
  • I.D. Coope. Circle fitting by linear and nonlinear least squares // Journal of Optimization Theory and Applications. — 1993. — Т. 76, вып. 2. — С. 381. — doi:10.1007/BF00939613.
  • Encyclopedia of Research Design / Neil J. Salkind. — SAGE Publications, 2010. — Т. 1. — ISBN 978-1-4129-6127-1.
  • Rudolf J. Freund, William J. Wilson, Ping Sa. Regression Analysis / Statistical Modeling of a Response Variable. — 2. — Elsevier, 2006. — ISBN 0-12-088597-2.
  • Jaan Kiusalaas. Numerical Methods in Engineering with MATLAB®. — Cambridge University Press, 2005. — ISBN 0-521-85288-9.
  • Richard E. Klosterman. Community Analysis and Planning Techniques. — Rowman & Littlefield Pub Inc, 1990. — ISBN 084767651X.
  • Hanita Daud, Vijanth Sagayan, Noorhana Yahya, Wan Najwati. Visual Informatics: Bridging Research and Practice (IVIC 2009) / Halimah Badioze Zaman, Peter Robinson, Maria Petrou, Patrick Olivier, Heiko Schröder, Timothy K. Shih. — Berlin, Heidelberg, NewYork: Sprintger, 2009. — Т. 5857. — (Lecture Notes in Computer Science). — ISBN 3-642-05035-2.
  • An Introduction to Risk and Uncertainty in the Evaluation of Environmental Investments / Charles E. Yoe. — West Chester, Pensylvania: The Greeley-Polhemus Group, Inc., 1996.
  • P. G. Guest. Numerical Methods of Curve Fitting. — Cambridge Academ, 2012. — ISBN 978-1-107646-5-7.
  • S.S. Halli, K.V. Rao. Advanced Techniques of Population Analysis. — 1992. — С. 165. — ISBN 0306439972.
  • Sung-Joon Ahn. Geometric Fitting of Parametric Curves and Surfaces // Journal of Information Processing Systems. — Vol. 4. — Вып. 4. — doi:10.3745/JIPS.2008.4.4.153.
  • J. H. Ahlberg, E. N. Nilson, J. L. Walsh. The theory of splines and their applications. — New York, London: Academic Press, 1967.
  • N. Chernov, H. Ma. Computer Vision / Sota R. Yoshida. — Nova Science Publishers, 2011. — С. 285–302. — ISBN 9781612093994.
  • Nate Silver. The Signal and the Noise: Why So Many Predictions Fail-but Some Don't. — Penguin Group, 2012. — ISBN 978-1-59-420411-1.
  • Dudley Williams. Spectroscopy / Claire Marton.. — Academic Press, 1976. — Т. 13, Part 1. — (Methods of Experimental Physics). — ISBN 0124759130.
  • Yang Liu, Wenping Wang. Advances in Geometric Modeling and Processing / F. Chen, B. Juttler. — 2008. — Т. 4975. — С. 384–397. — ISBN 978-3-540-79245-1. — doi:10.1007/978-3-540-79246-8_29.
  • P. Sheer. A Software Assistantfor Manual Stereo Photometrology. — University of the Witwater-srand, 1997.

Литература для дальнейшего чтения

  • N. Chernov (2010), Circular and linear regression: Fitting circles and lines by least squares, Chapman & Hall/CRC, Monographs on Statistics and Applied Probability, Volume 117 (256 pp.). [1]
Источник — https://ru.wikipedia.org/w/index.php?title=Приближение_с_помощью_кривых&oldid=79112018