Главная       Скачать       Коммерческая поддержка       FAQ       Forum       О нас       Английская версия

Полиномиальная интерполяция

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

Содержание

    1 Теория
           Барицентрическое представление полинома
           Замечания по выбору узлов
    2 Полиномиальная интерполяция
           Функции
           Примеры
    3 Полиномиальная аппроксимация
    4 Ссылки по теме

Теория

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

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

Такое представление обладает рядом удобных свойств, благодаря чему оно используется в пакете ALGLIB для работы с рациональными функциями. Та же формула может быть использована и для представления полинома, являющегося частным случаем рациональной функции. Барицентрическое представление имеет три важных преимущества перед другими способами интерполяции. Во-первых, оно более устойчиво к погрешностям, чем представление в степенном базисе. Во-вторых, после построения модели значение полинома может быть вычислено за время O(N), что быстрее, чем с использованием алгоритма типа Невилля (с трудоемкостью O(N 2)). В-третьих, в ряде важных случаев (равномерные и Чебышевские сетки) трудоемкость построения модели имеет сложность O(N).

Замечания по выбору узлов

Выбор узлов очень сильно влияет на точность интерполяции. При этом сетка с равноудаленными узлами, не смотря на свою простоту и удобство в использовании, не подходит для интерполяции по двум тесно связанным причинам.

Чтобы понять первую причину, рассмотрим график справа. На графике изображена функция

(черным цветом) и интерполяционный полином, построенный по 11 точкам на равномерной сетке (красным цветом). Можно видеть, что в центре полином очень хорошо интерполирует функцию, однако по мере приближения к краям точность интерполяции падает. Хотя полином проходит через все указанные ему точки, но между точками он очень сильно отклоняется от функции. Можно было бы ожидать, что с ростом числа точек ошибка будет падать. На самом деле наоборот - чем больше n, тем сильнее интерполяционный полином будет отклоняться от функции по мере приближения к границам отрезка. При неограниченном росте числа точек ошибка интерполяции на отрезке будет стремиться к бесконечности.

Доказано, что существует целый класс функций, которые не могут быть интерполированы полиномом на равномерной сетке. Это функции, имеющие полюса на комплексной плоскости в окрестностях отрезка интерполяции (в частности, приведенная выше функция имеет полюса в точках x = +i и x = -i). Следует понимать, что рост ошибки интерполяции с ростом числа точек - не недостаток алгоритма и не следствие естественных погрешностей при операциях с вещественными числами. Это фундаментальное свойство интерполяционного полинома - в точности проходя через все предписанные точки, он будет резко возрастать в интервале между ними.

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

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

Полиномиальная интерполяция

Функции

Для построения барицентрической модели интерполяционного полинома можно использовать следующие подпрограммы:

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

Следующие функции используются для преобразования между барицентрическим представлением, степенным базисом и базисом полиномов Чебышева:

Наконец, следующие функции можно использовать для быстрого - O(N) - вычисления значения интерполяционного полинома на одной из специальных сеток без создания барицентрической модели:

Примеры

ALGLIB Reference Manual содержит следующие примеры применения полиномиальной интерполяции:

Полиномиальная аппроксимация

Пакет ALGLIB также может использоваться для полиномиальной аппроксимации без ограничений (функция polynomialfit) или с ограничениями на значение полинома или его производной (функция polynomialfitwc). Более подробно этот вопрос рассмотрен в главе ALGLIB User Guide, посвященной аппроксимации.

Ссылки по теме

  1. 'Barycentric Lagrange Interpolation'. Jean-Paul Berrut, Lloyd N. Trefethen.

This article is intended for personal use only.

Скачать ALGLIB

C#

Исходный код на C#

Downloads page

 

C++

Исходный код на C++

Downloads page

 

C++, арифметика высокой точности

Исходный код на C++, использующий библиотеки MPFR/GMP.

Исходный код GMP доступен на сайте gmplib.org. Исходный код MPFR доступен на сайте www.mpfr.org.

Downloads page

 

FreePascal

Исходный код на Free Pascal.

Downloads page

 

Delphi

Исходный код на Delphi.

Downloads page

 

VB.NET

Исходный код на VB.NET.

Downloads page

 

VBA

Исходный код на VBA.

Downloads page

 

Python

Исходный код на Python (CPython и IronPython).

Downloads page

 

 

ALGLIB® - numerical analysis library, 1999-2017.
ALGLIB is registered trademark of the ALGLIB Project.