Это не официальный сайт wikipedia.org 01.01.2023

Приближение с помощью кривых — Википедия
Википедия

Приближение с помощью кривых

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

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

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

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

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

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

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

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

y = a x + b .  

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

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

y = a x 2 + b x + c .  

Эта функция описывает параболу. Параболу можно провести через любые три точки.

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

y = a x 3 + b x 2 + c x + d .  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Геометрическое приближение эллипсом Править

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

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

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

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

ПрограммыПравить

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

См. такжеПравить

ПримечанияПравить

  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[en]кампании. Документация: «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. ↑ Williams, 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.

ЛитератураПравить

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

  • 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] Архивная копия от 22 октября 2020 на Wayback Machine
Источник — https://ru.wikipedia.org/w/index.php?title=Приближение_с_помощью_кривых&oldid=128318888