Интерполяция по трем точкам

Интерполя́ция, интерполи́рование (от лат. inter–polis — «разглаженный, подновлённый, обновлённый; преобразованный») — в вычислительной математике способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений [1] . Термин «интерполяция» впервые употребил Джон Валлис в своём трактате «Арифметика бесконечных» (1656).

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

Существует также близкая к интерполяции задача, которая заключается в аппроксимации какой-либо сложной функции другой, более простой функцией. Если некоторая функция слишком сложна для производительных вычислений, можно попытаться вычислить её значение в нескольких точках, а по ним построить, то есть интерполировать, более простую функцию. Разумеется, использование упрощенной функции не позволяет получить такие же точные результаты, какие давала бы первоначальная функция. Но в некоторых классах задач достигнутый выигрыш в простоте и скорости вычислений может перевесить получаемую погрешность в результатах.

Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов». К классическим работам по интерполяции операторов относятся теорема Рисса — Торина и теорема Марцинкевича (Marcinkiewicz theorem), являющиеся основой для множества других работ.

Содержание

Определения [ править | править код ]

Рассмотрим систему несовпадающих точек x i <displaystyle x_> ( i ∈ 0 , 1 , … , N <displaystyle iin <0,1,dots ,N>> ) из некоторой области D <displaystyle D> . Пусть значения функции f <displaystyle f> известны только в этих точках:

y i = f ( x i ) , i = 1 , … , N . <displaystyle y_=f (x_),quad i=1,ldots ,N.>

Задача интерполяции состоит в поиске такой функции F <displaystyle F> из заданного класса функций, что

F ( x i ) = y i , i = 1 , … , N . <displaystyle F (x_)=y_,quad i=1,ldots ,N.>

  • Точки x i <displaystyle x_

>называют узлами интерполяции, а их совокупность — интерполяционной сеткой.

  • Пары ( x i , y i ) <displaystyle (x_
  • ,y_)>называют точками данных или базовыми точками.

  • Разность между «соседними» значениями Δ x i = x i − x i − 1 <displaystyle Delta x_
  • =x_-x_>шагом интерполяционной сетки. Он может быть как переменным, так и постоянным.

  • Функцию F ( x ) <displaystyle F (x)>интерполирующей функцией или интерполянтом.
  • Пример [ править | править код ]

    1. Пусть мы имеем табличную функцию, наподобие описанной ниже, которая для нескольких значений x <displaystyle x> определяет соответствующие значения f <displaystyle f> :

    Интерполяция помогает нам узнать, какое значение может иметь такая функция в точке, отличной от указанных точек (например, при x = 2,5).

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

    Читайте также:  Дешифруйте данный текст используя таблицу ascii кодов

    2. Найти промежуточное значение (способом линейной интерполяции).

    600015.5
    6378?
    800019.2

    ? = 15.5 + ( 6378 − 6000 ) 8000 − 6000 ∗ ( 19.2 − 15.5 ) 1 = 16.1993 <displaystyle ?=15.5+<frac <(6378—6000)><8000—6000>>*<frac <(19.2-15.5)><1>>=16.1993>

    Способы интерполяции [ править | править код ]

    Интерполяция методом ближайшего соседа [ править | править код ]

    Простейшим способом интерполяции является интерполяция методом ближайшего соседа.

    Интерполяция многочленами [ править | править код ]

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

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

    Формула квадратичной интерполяции

    расчет квадратичной интерполяции по трем точкам

    Помощь на развитие проекта CAE-CUBE.ru

    Уважаемый Посетитель сайта.
    Если Вам не удалось найти, то что Вы искали — обязательно напишите об этом в комментариях, чего не хватает сейчас сайту. Это поможет нам понять в каком направлении необходимо дальше двигаться, а другие посетители смогут в скором времени получить необходимый материал.
    Если же сайт оказался Ваме полезен — подари проекту CAE-CUBE.ru всего 2 ₽ и мы будем знать, что движемся в правильном направлении.

    Спасибо, что не прошели мимо!

    I. Порядок действий при расчете квадратичной интерполяции по 3 точкам онлайн калькулятором:

    1. Для проведения интерполяции требуется ввести координаты ввести значения координат 3 точек ([X1, Y1]; [X2, Y2]; [X3, Y3]) и абсциссу (Х) той точки, значение которой необходимо вычислить.
    2. Точка X1 должна лежать левее точки X2, а точка X2 должна лежать левее точки X3 (X1 интерполяция — способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. линейная интерполяция — нахождение промежуточного значения функции по двум точкам (условно проведя прямую между ними). квадратичная интерполяция — нахождение промежуточного значения функции по трем точкам (интерполирующая функция многочлен второго порядка — парабола).

    Как построить график по n точкам? Самое простое — отметить их маркерами на координатной сетке. Однако для наглядности их хочется соединить, чтобы получить легко читаемую линию. Соединять точки проще всего отрезками прямых. Но график-ломаная читается довольно тяжело: взгляд цепляется за углы, а не скользит вдоль линии. Да и выглядят изломы не очень красиво. Получается, что кроме ломаных нужно уметь строить и кривые. Однако тут нужно быть осторожным, чтобы не получилось вот такого:

    Немного матчасти

    Восстановление промежуточных значений функции, которая в данном случае задана таблично в виде точек P1&nbsp. &nbspPn, называется интерполяцией. Есть множество способов интерполяции, но все они могут быть сведены к тому, что надо найти n&nbsp–&nbsp1 функцию для расчёта промежуточных точек на соответствующих сегментах. При этом заданные точки обязательно должны быть вычислимы через соответствующие функции. На основе этого и может быть построен график:

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

    В разных инструментах для построения графиков — редакторах и библиотеках — задача «красивой интерполяции» решена по-разному. В конце статьи будет небольшой обзор существующих вариантов. Почему в конце? Чтобы после ряда приведённых выкладок и размышлений можно было поугадывать, кто из «серьёзных ребят» какие методы использует.

    Ставим опыты

    Самый простой пример — линейная интерполяция, в которой используются полиномы первой степени, а в итоге получается ломаная, соединяющая заданные точки.
    Давайте добавим немного конкретики. Вот набор точек (взяты почти с потолка):

    Результат линейной интерполяции этих точек выглядит так:

    Однако, как отмечалось выше, иногда хочется получить в итоге гладкую кривую.

    Что есть гладкость? Бытовой ответ: отсутствие острых углов. Математический: непрерывность производных. При этом в математике гладкость имеет порядок, равный номеру последней непрерывной производной, и область, на которой эта непрерывность сохраняется. То есть, если функция имеет гладкость порядка 1 на отрезке [a;&nbspb], это означает, что на [a;&nbspb] она имеет непрерывную первую производную, а вот вторая производная уже терпит разрыв в каких-то точках.
    У сплайна в контексте гладкости есть понятие дефекта. Дефект сплайна — это разность между его степенью и его гладкостью. Степень сплайна — это максимальная степень использованных в нём полиномов.
    Важно отметить, что «опасными» точками у сплайна (в которых может нарушиться гладкость) являются как раз Pi, то есть точки сочленения сегментов, в которых происходит переход от одного полинома к другому. Все остальные точки «безопасны», ведь у полинома на области его определения нет проблем с непрерывностью производных.
    Чтобы добиться гладкой интерполяции, нужно повысить степень полиномов и подобрать их коэффициенты так, чтобы в граничных точках сохранялась непрерывность производных.

    Читайте также:  Должностная инструкция web программиста

    Традиционно для решения такой задачи используют полиномы третьей степени и добиваются непрерывности первой и второй производной. То, что получается, называют кубическим сплайном дефекта 1. Вот как он выглядит для наших данных:

    Кривая, действительно, гладкая. Но если предположить, что это график некоторого процесса или явления, который нужно показать заинтересованному лицу, то такой метод, скорее всего, не подходит. Проблема в ложных экстремумах. Появились они из-за слишком сильного искривления, которое было призвано обеспечить гладкость интерполяционной функции. Но зрителю такое поведение совсем не кстати, ведь он оказывается обманут относительно пиковых значений функции. А ради наглядной визуализации этих значений, собственно, всё и затевалось.
    Так что надо искать другие решения.

    Другое традиционное решение, кроме кубических сплайнов дефекта 1 — полиномы Лагранжа. Это полиномы степени n&nbsp–&nbsp1, принимающие заданные значения в заданных точках. То есть членения на сегменты здесь не происходит, вся последовательность описывается одним полиномом.
    Но вот что получается:

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

    В компьютерной графике очень широко применяются кривые Безье, представленные полиномами k-й степени.
    Они не являются интерполирующими, так как из k&nbsp+&nbsp1 точек, участвующих в построении, итоговая кривая проходит лишь через первую и последнюю. Остальные k&nbsp–&nbsp1 точек играют роль своего рода «гравитационных центров», притягивающих к себе кривую.
    Вот пример кубической кривой Безье:

    Как это можно использовать для интерполяции? На основе этих кривых тоже можно построить сплайн. То есть на каждом сегменте сплайна будет своя кривая Безье k-й степени (кстати, k&nbsp=&nbsp1 даёт линейную интерполяцию). И вопрос только в том, какое k взять и как найти k&nbsp–&nbsp1 промежуточную точку.
    Здесь бесконечно много вариантов (поскольку k ничем не ограничено), однако мы рассмотрим классический: k&nbsp=&nbsp3.
    Чтобы итоговая кривая была гладкой, нужно добиться дефекта 1 для составляемого сплайна, то есть сохранения непрерывности первой и второй производных в точках сочленения сегментов (Pi), как это делается в классическом варианте кубического сплайна.
    Решение этой задачи подробно (с исходным кодом) рассмотрено здесь.
    Вот что получится на нашем тестовом наборе:

    Стало лучше: ложные экстремумы всё ещё есть, но хотя бы не так сильно отличаются от реальных.

    Думаем и экспериментируем

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

    В качестве прямых, на которых лежат точки Ci&nbsp–&nbsp1 (2) , Pi и Ci (1) , целесообразно взять касательные к графику интерполируемой функции в точках Pi. Это гарантирует отсутствие ложных экстремумов, так как кривая Безье оказывается ограниченной ломаной, построенной на её контрольных точках (если эта ломаная не имеет самопересечений).

    Читайте также:  Жесткий диск не форматируется при установке виндовс

    Методом проб и ошибок эвристика для расчёта расстояния от точки интерполируемой последовательности до промежуточной контрольной получилась такой:

    Первая и последняя промежуточные контрольные точки равны первой и последней точке графика соответственно (точки C1 (1) и Cn&nbsp–&nbsp1 (2) совпадают с точками P1 и Pn соответственно).
    В этом случае получается вот такая кривая:

    Как видно, ложных экстремумов уже нет. Однако если сравнивать с линейной интерполяцией, местами ошибка очень большая. Можно сделать её ещё меньше, но тут в ход пойдут ещё более хитрые эвристики.

    К текущему варианту мы пришли, уменьшив гладкость на один порядок. Можно сделать это ещё раз: пусть сплайн будет иметь дефект 3. По факту, тем самым формально функция не будет гладкой вообще: даже первая производная может терпеть разрывы. Но если рвать её аккуратно, визуально ничего страшного не произойдёт.
    Отказываемся от требования равенства расстояний от точки Pi до точек Ci&nbsp–&nbsp1 (2) и Ci (1) , но при этом сохраняем их все лежащими на одной прямой:

    Эвристика для вычисления расстояний будет такой:

    Результат получается такой:

    В результате на шестом сегменте ошибка уменьшилась, а на седьмом — увеличилась: кривизна у Безье на нём оказалась больше, чем хотелось бы. Исправить ситуацию можно, принудительно уменьшив кривизну и тем самым «прижав» Безье ближе к отрезку прямой, которая соединяет граничные точки сегмента. Для этого используется следующая эвристика:

    Результат следующий:

    На этом было принято решение признать цель достигнутой.
    Может быть, кому-то пригодится код.

    А как люди-то делают?

    Обещанный обзор. Конечно, перед решением задачи мы посмотрели, кто чем может похвастаться, а уже потом начали разбираться, как сделать самим и по возможности лучше. Но вот как только сделали, не без удовольствия ещё раз прошлись по доступным инструментам и сравнили их результаты с плодами наших экспериментов. Итак, поехали.

    MS Excel

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

    LibreOffice Calc

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

    Есть там ещё один тип интерполяции, который мы тут не рассматривали: B-сплайн. Но для нашей задачи он явно не подходит, так как даёт вот такой результат 🙂

    Highcharts, одна из самых популярных JS-библиотек для построения диаграмм

    Тут налицо «метод касательных» в варианте равенства расстояний от точки интерполируемой последовательности до промежуточных контрольных. Ложных экстремумов нет, зато есть сравнительно большая ошибка относительно линейной интерполяции (седьмой сегмент).

    amCharts, ещё одна популярная JS-библиотека

    Картина очень похожа на экселевскую, те же два ложных экстремума в тех же местах.

    Coreplot, самая популярная библиотека построения графиков для iOS и OS X

    Есть ложные экстремумы и видно, что используется сплайн дефекта 1 на основе Безье.
    Библиотека открытая, так что можно посмотреть в код и убедиться в этом.

    aChartEngine, вроде как самая популярная библиотека построения графиков для Android

    Больше всего похоже на кривую Безье степени n&nbsp–&nbsp1, хотя в самой библиотеке график называется «cubic line». Странно! Как бы то ни было, тут не только присутствуют ложные экстремумы, но и в принципе не выполняются условия интерполяции.

    Оцените статью
    Adblock
    detector