Будем искать интерполяционный многочлен в виде

ВАНДЕРМОНД АЛЕКСАНДР ТЕОФИЛЬ (Vandermonde Alexandre Theophill; 1735-1796)- французский математик, чьи основные работы относятся к алгебре. В. заложил основы и дал логическое изложение теории детерминантов (определитель Вандермонда), а также выделил ее из теории линейных уравнений. Он ввел правило разложения детерминантов с помощью миноров второго порядка.

Здесь 1.(х) - многочлены степени л, так называемые ЛАГРАНЖЕ- ВЫ МНОГОЧЛЕНЫ ВЛИЯНИЯ, удовлетворяющие условию

Последнее условие означает, что любой многочлен l t (x) равен нулю при каждом х-у кроме х. у т. е. х 0 у x v ...» х { _ v x i + v ...» х п - корни этого многочлена. Следовательно, лагранжевы многочлены Ifjx) имеют вид

Так как по условию 1.(х.) = 1, то

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

а интерполяционный многочлен (2.5) запишется в виде

ЛАГРАНЖ ЖОЗЕФ ЛУИ (Lagrange Joseph Louis; 1736- 1813) - выдающийся французский математик и механик, наиболее важные труды которого относятся к вариационному исчислению, к аналитической и теоретической механике. В основу статики Л. положил принцип возможных (виртуальных) перемещений. Он ввел обобщенные координаты и придал уравнениям движения механической системы форму, названную его именем. Л. получил ряд важных результатов в области анализа (формула остаточного члена ряда Тейлора, формула конечных приращений, теория условных экстремумов); в теории чисел (теорема Лагранжа); в алгебре (теория непрерывных дробей, приведение квадратичной формы к сумме квадратов); в теории дифференциальных уравнений (отыскание частного решенияу изучение обыкновенного дифференциального уравнения первого порядка, линейного относительно искомой функции и независимой переменной, с переменными коэффициентами, зависящими от производной от искомой функции); в теории интерполирования (интерполяционная формула Лагранжа).

Интерполяционный многочлен в форме (2.6) называется ИНТЕРПОЛЯЦИОННЫМ МНОГОЧЛЕНОМ ЛАГРАНЖА. Перечислим основные достоинства этой формы записи интерполяционного многочлена.

  • Число арифметических операций, необходимых для построения многочлена Лагранжа, пропорционально п 2 и является наименьшим для всех форм записи.
  • Формула (2.6) в явном виде содержит значения функций в узлах интерполяции, что бывает удобно при некоторых вычислениях, в частности, при построении формул численного интегрирования.
  • Формула (2.6) применима как для равноотстоящих, так и для неравноотстоящих узлов.
  • Интерполяционный многочлен Лагранжа особенно удобен, когда значения функций меняются, а узлы интерполяции неизменны, что имеет место во многих экспериментальных исследованиях.

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

Введем функцию ю л f , = (х - х 0)(х - Xj)...(x - х п) = fl (* “ *;)

Отметим, что ш п + : (х) есть многочлен степени п + 1. Тогда формулу (2.6) можно записать в виде

Приведем формулы линейной и квадратичной интерполяции по Лагранжу:


Многочлен Лагранжа является в формуле (2.8) многочленом 1-й и в формуле (2.9) - многочленом 2-й степени.

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

4.3 Интерполяция функции многочленами Лагранжа

Рассмотрим другой подход к приближению функции многочленами. Пусть функция y = f(x) определена на отрезке и известны значения этой функции в некоторой системе узлов x i Î , i = 0, 1, … , n. Например, эти значения получены в эксперименте при наблюдении некоторой величины в определенных точках или в определенные моменты времени x 0 , x 1 , … , x n . Обозначим эти значения следующим образом: y i = f(x i), i = 0, 1, … , n. Требуется найти такой многочлен P(x) степени m,

P(x) = a 0 + a 1 x + a 2 x 2 + … + a m x m , (4.5)

который бы в узлах x i , i = 0, 1, … , n принимал те же значения, что и исходная функция y = f(x), т. е.

P(x i) = y i , i = 0, 1, … , n. (4.6)

Многочлен (4.5), удовлетворяющий условию (4.6), называется интерполяционным многочленом.

Другими словами, ставится задача построения функции y = P(x), график которой проходит через заданные точки (x i , y i), i = 0, 1, … , n (рис. 4.1).

Объединяя (4.5) и (4.6), получим:

a 0 + a 1 x i + a 2 x + … + a m x = y i ,i = 0, 1, … , n. (4.7)

В искомом многочлене P(x) неизвестными являются m +1 коэффициент a 0 , a 1 , a 2 , …, a m . Поэтому систему (4.7) можно рассматривать как систему из n +1 уравнений с m +1 неизвестными. Известно, что для существования единственного решения такой системы необходимо, чтобы выполнялось условие: m = n. Таким образом, систему (4.7) можно переписать в развернутом виде:

a 0 + a 1 x 0 + a 2 x + … + a n x = y 0

a 0 + a 1 x 1 + a 2 x + … + a n x = y 1

a 0 + a 1 x 2 + a 2 x + … + a n x = y 2 (4.8)

a 0 + a 1 x n + a 2 x + … + a n x = y n


Вопрос о существовании и единственности интерполяционного многочлена решает следующая теорема:

Теорема 4.1. Существует единственный интерполяционный многочлен степени n, удовлетворяющий условиям (4.6).

Имеются различные формы записи интерполяционного многочлена. Широко распространенной формой записи является многочлен Лагранжа

L n (x) = = . (4.9)

В частности, для линейной и квадратичной интерполяции по Лагранжу получим следующие интерполяционные многочлены:

L 1 (x) = y 0+ y 1,

L 2 (x) = y 0 +y 1 + y 2 .

Пример 4.3.

Построим интерполяционный многочлен Лагранжа по следующим данным:

0 2 3 5
1 3 2 5

Степень многочлена Лагранжа для n +1 узла равна n. Для нашего примера многочлен Лагранжа имеет третью степень. В соответствии с (4.9)


L 3 (x) = 1+3 + 2 + 5 = 1 + x – x 2 + x 3 .

Пример 4.4.

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

Для функции y = sinx известны следующие данные.

0 p/6 p/3 p/2
0 ½ 1

Вычислим y(0.25).

Найдем многочлен Лагранжа третьей степени:

L 3 (x) = 0 + +

+ 1.

При x = 0.25 получим y(0.25) = sin 0.25 » 0.249.

Погрешность интерполяции. Пусть интерполяционный многочлен Лагранжа построен для известной функции f(x). Необходимо выяснить, насколько этот многочлен близок к функции в точках отрезка , отличных от узлов. Погрешность интерполяции равна |f(x) – P n (x)|. Оценку погрешности можно получить на основании следующей теоремы.

Теорема 4.2. Пусть функция f(x) дифференцируема n +1 раз на отрезке , содержащем узлы интерполяции x i Î , i = 0, 1, … , n. Тогда для погрешности интерполяции в точке x Î справедлива оценка:

|f(x) – L n (x)|£ |w n+ 1 (x)|, (4.10)

M n+ 1 = |f (n+1) (x)|,

w n+ 1 (x) = (x – x 0)(x – x 1)…. (x – x n).

Для максимальной погрешности интерполяции на всем отрезке справедлива оценка:

|f(x) – L n (x)| £ |w n (x)| (4.11)

Пример 4.5.

Оценим погрешность приближения функции f(x) = в точке x = 116 и на всем отрезке , где a = 100, b = 144, с помощью интерполяционного много члена Лагранжа L 2 (x) второй степени, построенного с узлами x 0 = 100, x 2 = 144.

Найдем первую, вторую и третью производные функции f(x):

f "(x)= x – 1/2 , f "(x)= – x –3/2 , f"""(x)= x –5/2 .

M 3 = | f"""(x)| = 100 –5/2 = 10 –5 .

В соответствии с (4.9) получим оценку погрешности в точке x = 116.

n - количество узлов.

Задача интерполяции - найти функцию , принимающую в точках те же значения .

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

Функция называется интерполянтом функции .

Если значение ищется на интервале [ , то эту задачу принято называть задачей интерполяции, а если за пределами этого интервала, то это задачей экстраполяции.

Задача имеет много решений, т.к. через заданные точки, i=0, 1,..., n, можно провести бесконечно много кривых, каждая из которых будет графиком функции, для которой выполнены все условия (1.2).

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

Условие интерполяции:

(1.2)

Где а – вектор неизвестных коэффициентов.

Обычно вид известен заранее. Чтобы решить задачу интерполяции необходим коэффициент .

Решить задачу интерполяции - значит найти при заданных и .

В общем виде система представляет систему нелинейных уравнений и при больших n часто не имеет решений.

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

Простейшим и наиболее часто применяемым функцией является полином:

(1.3)

где , , , …, – коэффициент полинома,

m – степень аппроксимирующего многочлена.

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

Все методы интерполяции можно разделить на локальные и глобальные. В случае глобальной интерполяции отыскивается единый полином на всем интервале [ . Методы глобальной интерполяции обычно применяют для функций, заданных небольшим количеством точек, т. к. при увеличении количества точек увеличивается порядок интерполирующего многочлена, что отрицательно сказывается на гладкости получаемой функции. Многочленная аппроксимация, использующая сразу все узлы таблицы (глобальная интерполяция) имеет существенный недостаток – возможность появления больших экстремумов в промежутках между узлами сетки. Т.е. интерполяционный полином может иметь колебания, не свойственные исходным данным. Кроме того, с ростом степени полинома происходит быстрое накопление ошибок округления. Чтобы избежать этих нежелательных эффектов, на практике применяют локальную интерполяцию. . В случае локальной интерполяции на каждом интервале строится отдельный полином. Для локальной интерполяции количество узлов большого значения не имеет.

Рассмотрим некоторые виды локальной и глобальной интерполяции.

Локальная интерполяция:

1. Кусочно-линейная интерполяция

2. Интерполяция сплайнами

Глобальная интерполяция:

1. Полином Лагранжа

2. Многочлен Ньютона

ГЛОБАЛЬНАЯ ИНТЕРПОЛЯЦИЯ

Интерполяция полиномом Лагранжа

При глобальной интерполяции на всем интервале строится единый многочлен. Одной из форм записи интерполяционного многочлена для глобальной интерполяции является многочлен Лагранжа:

Интерполяционный полином Лагранжа n-ой степени есть линейная комбинация базисных полиномов Лагранжа:

То есть многочлен Лагранжа:

(2.3)

Многочлен удовлетворяет условию

Это условие означает, что многочлен равен нулю при каждом кроме , то есть , , … , – корни этого многочлена. Таким образом, степень многочлена равна n и при в сумме обращаются в нуль все слагаемые, кроме слагаемого с номером i=j, равного .

Принимает значение 1 в точке и 0 в остальных узлах интерполяции. Следовательно в точке исходный полином принимает значение

(2.4)

Выражение (2.1) применимо как для равноотстоящих, так и для не равноотстоящих узлов.

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

2.2. Многочлен Ньютона

Пусть функция g(x) задана с произвольным шагом и точки таблицы значений занумерованы в произвольном порядке.

Многочлен Ньютона во многом опирается на понятие разделенных разностей.

Разделенные разности нулевого порядка совпадают со значениями функции в узлах. Разделенные разности первого порядка определяются через разделенные разности нулевого порядка:

Разделенные разности k-го порядка определяются через разделенную разность порядка :

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

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

ЛОКАЛЬНАЯ ИНТЕРПОЛЯЦИЯ

3.1. Кусочно-линейная интерполяция.

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

(3.3)
(3.4)

Кусочно-линейная интерполяция является самой простой, и поэтому довольно часто применяется для расчета значений между узлами интерполяции. Для построения интерполирующей зависимости, используемой в дальнейших научных и инженерных расчетах, обычно используются более сложные методы интерполяции.

3.2. Интерполяция сплайнами

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

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

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

Разобьём отрезок на N равных отрезков [ , ], где , i=0,1,…,N-1.

Если в узлах , , заданы значения , которые принимает кубический сплайн, то на частичном отрезке [ , ] он принимает вид:

(3.3)

В самом деле, это легко проверить, рассчитав и в точках ,

Можно доказать, что если многочлен третьей степени, принимает в точках , значения , и имеет в этих точках производные, соответственно, , , то он совпадает с многочленом (3.3).

Таким образом, для того, чтобы задать кубический сплайн на отрезке, необходимо задать значения , i=0,1…,N в N+1 в узле .

ОШИБКА ИНТЕРПОЛЯЦИИ

При интерполяции функции всегда получают ошибку состоящую из погрешности самого метода и ошибок округления.

Ошибка приближения функции интерполяционным полиномом n-й степени в точке xопределяется разностью.

Здесь – производная (n+1) порядка функции в некоторой точке, а функция определена как

то для погрешности интерполяции следует оценка.

(4.4)

Конкретная величина погрешности в точке x зависит, очевидно, от значения функции в этой точке. Качественный характер зависимости показан на рисунке 2.

Из рисунка видно, что погрешность интерполяции тем выше, чем ближе точка x лежит к концам отрезка. За пределами отрезка интерполяции (т.е.

при экстраполяции) быстро растет, поэтому погрешность возрастает существенно.

Рисунок 2

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

5. ПРИМЕР ИНТЕРПОЛЯЦИИ ФУНКЦИИ МНОГОЧЛЕНАМИ ЛАГРАНЖА И НЬЮТОНА

Для нахождения многочлена, принимающего в конкретных точках нужные значения, может использоваться пакет Mathcad. В качестве примера рассмотрим задачу на нахождение многочлена Лагранжа удовлетворяющего приведенным исходным данным.

Построим многочлен Лагранжа в пакете Mathcad:

Исходные данные:

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

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

1. Интерполяционная формула Лагранжа

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

где ˗ степень полинома ;

˗ значение значения интерполирующей функции в точке ;

˗ базисные полиномы (множитель Лагранжа), которые определяются по формуле:

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

Многочлен в форме Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. К недостаткам этой формы записи можно отнести то, что при построении полинома степени n+1 полностью теряется информация о предыдущем полиноме степени n, т.е. с изменением числа узлов приходится все вычисление выполнить заново.

2. Погрешность интерполяционного полинома в форме Лагранжа

Рассмотрим функцию f (x ), которая непрерывна и дифференцируема на рассматриваемом отрезке . Интерполяционный полином L (x) в форме Лагранжа принимает в точках заданные значения функции . В остальных точках интерполяционный полином L (x) отличается от значения функции f (x ) на величину остаточного члена , который определяет абсолютную погрешность интерполяционной формулы Лагранжа:

А бсолютную погрешность интерполяционной формулы Лагранжа определяют следующим образом:

где n ˗ степень полинома

Переменная представляет собой верхнюю границу значения модуля (n +1)-й производной функции f(x) на заданном интервале

Погрешность интерполяции методом Лагранжа зависит от свойств функции f (x ), а также от расположения узлов интерполяции и точки x . В случае если погрешность не достигает нужной точности, то нужно разбить отрезок на части и интерполировать каждую часть в отдельности – кусочная интерполяция.

Выбор узлов интерполяции

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


В качестве узлов следует взять корни этого многочлена, то есть точки:

3. Методика вычисления полинома в форме Лагранжа

Алгоритм вычисления полинома в форме Лагранжа позволяет разделить задачи определения коэффициентов и вычисления значений полинома при различных значениях аргумента:

1. В качестве исходных данных задается выборка из n -точек, которая включает в себя значения функции и значения аргумента функции.

2. Выполняется вычисление полинома n-степени в форме Лагранжа по следующей формуле:

Алгоритм вычисления полинома в форме Лагранжа представлен на рисунке 1.

Методика вычисления полинома в форме Лагранжа

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

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

При решении задачи в этом случае вместо функции
оперируют с функцией Ф(x). Задача построения такой функции Ф(x) называется задачей интерполирования. Чаще всего интерполирующую функцию Ф(x) отыскивают в виде алгебраического полинома.

    1. Интерполяционный полином

Для каждой функции
, определенной на [a,b ], и любого набора узлов x 0 , x 1 ,....,x n (x i
[a,b ], x i x j при ij) среди алгебраических многочленов степени не выше n существует единственный интерполяционный многочлен Ф(x), который может быть записан в форме:

, (3.1)

где
- многочлен n-ой степени, обладающий следующим свойством:

Для интерполяционного полинома многочлен
имеет вид:

Этот многочлен (3.1) и решает задачу интерполирования и называется интерполяционным полиномом Лагранжа.

В качестве примера рассмотрим функцию вида
на интервале
заданную табличным способом.

Необходимо определить значение функции в точке x-2.5. Воспользуемся для этого полином Лагранжа. Исходя из формул (3.1 и 3.3) запишем этот полином в явном виде:

(3.4).

Тогда подставляя в формулу (3.4) исходные значения из нашей таблицы получим

Полученный результат соответствует теории т.е. .

    1. Интерполяционная формула Лагранжа

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

(3.5)

Запись полинома в виде (3.5) более удобна для программирования.

При решении задачи интерполяции величина n называется порядком интерполирующего полинома. При этом, как видно из формул (3.1) и (3.5), число узлов интерполирования всегда будет равно n+1 и значение x, для которого определяется величина
, должно лежать внутри области определения узлов интерполяции т.е.

. (3.6)

В некоторых практических случаях общее известное число узлов интерполяции m может быть больше, чем порядок интерполирующего полинома n .

В этом случае, прежде чем реализовывать процедуру интерполяции согласно формуле (3.5), необходимо определить те узлы интерполяции, для которых справедливо условие (3.6). При этом следует помнить, что наименьшая погрешность достигается при нахождении значения x в центре области интерполяции. Для обеспечения этого предлагается следующая процедура:


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