17. Интерполяционный многочлен Ньютона. Схема Эйткена.

Схема Эйткена. - метод вычисления значения интерполяционного многочлена Ln(x)по узлам х 0, х1, . . ., х п в точке х, основанный на последовательном применении формулы где L(i, i+1,.... m)(x)- интерполяционный многочлен с узлами интерполяции xi, xi+1, . . ., х т, в частности Li(x)=f(xi) (см. Интерполяционная формула). Процесс вычисления по формуле (*) можно закончить, когда в значениях двух интерполяционных многочленов последовательных степеней совпадает требуемое количество знаков. Э. с. удобно использовать для интерполяции значений таблично заданной функции, перенумеровав узлы интерполяции в порядке возрастания |x-xi|.

18. Проблемы глобальной полиномиальной интерполяции и понятие кусочно-полиномиальной интерполяции. Интерполяция сплайнами.

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

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

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

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

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

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

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

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

19. Основные формулы численного дифференцирования и их вывод. Обусловленность формул численного дифференцирования.

1. Вычисление производной по ее определению

Пусть функция y = f(x) определена в некоторой окрестности точки x0 и имеет производную в этой точке. Это означает, что существует предел отношения приращения функции к приращению аргумента при стремлении приращения аргумента к нулю:

, (1)

где .

Значение производной в точке x0 можно получить, заменяя предел выражения (1) пределом по последовательности целых чисел. Здесь

Это приращение уменьшается при увеличении числа n, где (x)0 - некоторое начальное приращение аргумента. Поскольку (y)n = f(x0 + (x)n) - f(x0), формулу (1) можно представить следующим образом:

.

При больших n получаем:

.

Условие прекращения вычислений:

.