МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ
ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
А.Н. Гудович,
Н.Н. Гудович
ЭЛЕМЕНТЫ ЧИСЛЕННЫХ МЕТОДОВ
Выпуск 1
ИНТЕРПОЛЯЦИЯ АЛГЕБРАИЧЕСКИМИ МНОГОЧЛЕНАМИ.
МНОГОЧЛЕН ЛАГРАНЖА
Учебно-методическое пособие для вузов
Издательско-полиграфический центр
Воронежского государственного университета
2012
Стр.1
§ 1. Понятие интерполяционного многочлена
Термин «интерполяция» имеет латинское происхождение. Латинское
слово interpolatio образовано с помощью приставки inter (между, внутри) и
глагола polire (восстанавливать, ремонтировать) и потому означает восстановление
фрагмента массива данных по предыдущему и последующему
фрагментам. Например, интерполяция в летописи – это восстановление
утраченного фрагмента летописи на основе анализа предшествующего и
последующего текста.
В математике под задачей интерполяции первоначально понимали восстановление
значения функции в точке, расположенной между заданными
точками a, b, по известным значениям f(a), f(b) функции в этих точках.
Пусть
− заданные точки,
x0=a, x1=b
f(x0)=f(a), f(x1)=f(b)
(1)
(2)
− заданные значения функции в этих точках, а x* – внутренняя точка отрезка
[a, b].
Для приближенного решения задачи интерполяции рассмотрим многочлен
первой степени
p1(x)=a0+a1 x
(3)
и подберем его коэффициенты a0, a1 так, чтобы в точках x0, x1 этот многочлен
принимал те же значения, что и функция f, т.е. подберем из условий
a0+a1 x0=f(x0), a0+a1 x1=f(x1).
(4)
Решая систему (4) относительно неизвестных a0, a1, подставляя полученные
значения этих коэффициентов в выражение для многочлена p1 и
вычисляя значение p1(x*), получим число, которое и принимается в качестве
приближенного значения функции f в интересующей нас внутренней
точке x*:
Описанный прием нахождения приближенных значений функции наf(x*)
≅ p1(x*).
зывают линейной интерполяцией, поскольку в качестве этих приближений
здесь используются значения многочлена (3) первой степени, т.е. значения
линейной функции. При этом сам многочлен (3) называют интерполяционным
многочленом первой степени, построенным по значениям (2) функции f
в узлах интерполяции (1).
3
Стр.3
Мы ознакомились с понятием интерполяции на простых частных случаях.
Рассмотрим теперь общую ситуацию.
Пусть f – заданная на отрезке [ a , b ] функция, а
x0, x1, ... , xn
(11)
− попарно различные точки этого отрезка.
Определение 2. Интерполяционным многочленом степени не выше n
(обозначение pn (x; {xi}i=0, ... , n; f)) называют многочлен вида
p( x ) = a0 + a1x + a2x2 +...+ anxn ,
значения которого в точках (11) совпадают со значениями функции f:
pn ( x k ; { xi }i=0, ... , n ; f )= f (x k ), k = 0, 1, ... , n;
(12)
(13)
при этом точки (11) называют узлами интерполяции, а функцию f − интерполируемой
функцией.
Замечание 3. Многочлен pn( x; {xi}, f ) как функция переменной x зависит,
во-первых, от функции f и, во-вторых, от выбора узлов интерполяции
(11), что и отражено в обозначении. В том случае, когда ясно, о каком
наборе узлов и какой функции идет речь, естественно использовать более
простое обозначение: pn(x).
Теорема 4. Для любого набора (11) попарно различных узлов интерполяции
на отрезке [a,b] и любой заданной на [a,b] функции f интерполяционный
многочлен pn( x; {xi}; f ) существует и единственен.
Доказательство. Воспользовавшись формулой (12), перепишем условия
(13) в виде:
a0 + a1xk + a2(xk)2 + ... + am(xk)m + ... + an(xk)n = f(xk), k=0,1, ... ,n.
Если набор узлов (11) зафиксировать, то соотношения (14) можно рас(14)
сматривать
как систему линейных алгебраических уравнений относительно
неизвестных коэффициентов a0, a1, ... , am, ... , an интерполяционного многочлена
pn(x; {xi}, f ), и потому вопрос о существовании и единственности
этого многочлена эквивалентен вопросу об однозначной разрешимости этой
системы при любых правых частях
f(x0), f(x1), ... , f(xk), ... , f(xn).
(15)
Матрица системы (14) имеет специальный вид: её m-тый ( m=0,1, ... ,n )
столбец составлен из m-тых степеней чисел (11). Матрицы такого типа в ал6
Стр.6
гебре называют матрицами Вандермонда; для построения матрицы B этого
класса выбирают (не обязательно различные ) числа
b0, b1, ... , bk, ... , bn,
(16)
возводят их в m-тую степень и полученный упорядоченный набор чисел
(b0)m, (b1)m, ... , (bk)m, ... , (bn)m
записывают в виде m-того столбца матрицы B. Известен способ вычисления
определителя такой матрицы: сначала следует образовать всевозможные
разности
bi – bj
чисел (16), а затем их перемножить:
det B = ∏>i j
,
i>j
( b b ) .
i −
j
(17)
(18)
В нашем случае роль чисел (16) играют числа (11): bk=xk, k=0,1, ... ,n.
В силу предположения о том, что узлы интерполяции – попарно различные
точки отрезка [a,b], разности (17), а значит, и их произведение (18) – определитель
системы (14) – отличны от нуля. Но тогда система однозначно
разрешима при любых правых частях (15), что и гарантирует существование
и единственность интерполяционного многочлена.
Замечание 5. Проведенные рассуждения указывают и способ построения
интерполяционного многочлена: по заданным узлам интерполяции (11)
и значениям (15) интерполируемой функции составляем систему (14), решаем
её относительно a0, a1, ... , an и подставляем полученные ai в (12).
Такой способ построения pn(x) называют методом неопределённых коэффициентов.
Замечание
6. Если в результате решения системы (14) для старших коэффициентов
an, an-1, ... , an-r будут получены нулевые значения, то фактическая
степень интерполяционного многочлена окажется строго меньше n (по
этой причине в определении 2 мы говорим о многочлене степени не выше n,
а не о многочлене n-ой степени).
Замечание 7. Укажем, что в определении 2 и теореме 4 не предполагается,
что крайние точки набора узлов (11) совпадают с концами отрезка [a,
b], а точки (11) занумерованы в порядке возрастания. Считается лишь, что
узлы интерполяции – попарно различные точки отрезка [a, b], в которых
известны значения функции f. Выбор набора узлов влияет на коэффициенты
7
Стр.7
интерполяционного многочлена, поскольку узлы интерполяции входят в
матрицу системы (14). Что же касается нумерации узлов в пределах выбранного
набора узлов интерполяции, то она не существенна, так как перенумерация
узлов соответствует перестановке уравнений системы, что, очевидно,
не влияет на решение.
§ 2. Погрешность интерполяции
Изучим теперь вопрос о погрешности интерполяционного многочлена.
Определение 8. Погрешностью интерполяционного многочлена в
точке x∈[a,b] (или погрешностью интерполяции в точке x ) называется величина
rn(x)
= f(x) – pn(x),
случая.
Упражнение 9. Пусть функция f есть многочлен 2-ой степени. Вывести
формулу для погрешности линейной интерполяции.
Решение. В данном случае n=1, так что имеем два узла интерполяции
x0, x1. При n=1 погрешность интерполяции (19) есть разность многочлена
второй степени f и многочлена первой степени p1. Поэтому она является
многочленом второй степени. Известны корни этого многочлена – ими являются
узлы интерполяции. Следовательно, для погрешности интерполяции
справедливо представление:
f(x)−p1(x)=K(x−x0)(x−x1),
(20)
где K – некоторая константа. Для ее нахождения дважды дифференцируем
полученное равенство (20). Тогда, поскольку вторая производная от многочлена
первой степени p1 равна нулю, а вторая производная от правой части
K (x−x0)(x−x1)=K(x2−(x0+x1)x+x0 x1)
равенства (20) равна, очевидно, K(2!), приходим к соотношению
f ( x ) ( 2! )K .
′′ =
грешности интерполяции выражение
f(x)−p1(x)=(1/2!)
(21)
(22)
Вычисляя отсюда K и подставляя результат в (20), получим для поf
( x )( x x0 )( x x ).1
8
′′
−
−
(23)
(19)
т.е. разность значений функции и многочлена в точке x.
Исследование вопроса о погрешности начнем с рассмотрения частного
Стр.8
Усложним задачу, заменив предположение о том, что приближаемая
функция f есть многочлен степени 2, более общим предположением о существовании
у этой функции непрерывных производных до второго порядка
включительно.
Теорема 10. Пусть f ∈C2[a, b], Тогда для погрешности линейной интерполяции
в любой точке x отрезка [a, b], отличной от узлов интерполяции,
справедлива формула
где ξ (x) – точка, принадлежащая наименьшему отрезку вещественной оси,
содержащему точку x и узлы интерполяции:
ξ(x)∈[ min{x, x0, x1}, max{x, x0, x1} ] ⊆ [a,b].
2!
f ( x ) p ( x ) 1
−
1
=
(25)
Доказательство. При проведении доказательства нам придется различать
точку x*, в которой оценивается погрешность интерполяции, и переменную
x, по которой будут дифференцироваться функции.
Итак, зафиксируем отличную от узлов интерполяции точку x∗ и по аналогии
с (20) подберем константу K* так, чтобы выполнялось равенство
f(x∗) – p1(x∗) = K∗(x∗−x0)(x∗−x1).
(26)
Для этого, очевидно, следует взять в качестве константы K* величину
K∗= ( f(x∗) – p1(x∗) ) / (x∗−x0)(x*−x1)
Отметим, что отличие формул (20) и (26) состоит в том, что константа
K в формуле (20) (случай многочлена степени 2) – одна и та же для всех x,
тогда как константа в формуле (26) (случай дважды непрерывно дифференцируемой
функции) зависит от выбора точки x*, что и отражено в обозначении
этой константы.
Составим теперь вспомогательную функцию переменной x
h(x) = f(x) – p1(x) – K ∗(x – x0)(x – x1) .
(27)
Равенство (26) означает, что в точке x* функция (27) обращается в ноль.
Кроме того, она равна нулю и в узлах интерполяции x0, x1, поскольку при
подстановке в формулу (27) вместо x узла интерполяции третье слагаемое в
правой части этой формулы обратится в ноль, а разность f−p1 окажется равной
нулю в силу совпадения в узле интерполяции значения функции и интерполяционного
многочлена. Переобозначим эти три корня функции h
9
f ( ( x ))( x x0 )( x x ),
′′ ξ
−
− 1
(24)
Стр.9
символами yi
набор корней
(0), i=0, 1, 2, чтобы получить упорядоченный по возрастанию
y0
(0) < y1
(0) < y2
В случае же x0
Стр.10