МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ
БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
А. Н. Гудович, Н. Н. Гудович
КРАТКИЙ КУРС ЧИСЛЕННЫХ МЕТОДОВ
Выпуск 1
Приближение функций
алгебраическими многочленами
Учебное пособие
Воронеж
Издательский дом ВГУ
2017
Стр.1
Г лава 1. Интерполяция. Многочлен Лагранжа
§ 1. Понятие интерполяционного многочлена
Термин «интерполяция» имеет латинское происхождение. Латинское
слово interpolatio образовано с помощью приставки inter (между, внутри) и
глагола polire (восстанавливать, ремонтировать) и потому означает
восстановление фрагмента массива данных по предыдущему и
последующему фрагментам. Например, интерполяция в летописи - это
восстановление утраченного фрагмента летописи на основе анализа
предшествующего и последующего текста.
В математике под задачей интерполяции первоначально понимали
восстановление значения функции в точке, расположенной между
заданными точками a, b, по известным значениям f(a), f(b) функции в этих
точках.
Пусть
x0=a, x1=b
- заданные точки,
f(xo)=f(a), f(xi)=f(b)
(1.2)
- заданные значения функции в этих точках, ах* - внутренняя точка
отрезка [a, b].
Для приближенного решения задачи интерполяции рассмотрим многочлен
первой степени
p 1(x)=a0+a1 х
(1-3)
и подберем его коэффициенты ao, ai так, чтобы в точках xo, xi этот
многочлен принимал те же значения, что и функция f , т.е. подберем из
условий
3
(1-1)
Стр.3
ffa)
a
f((a+b)/2)
(a+b)/2
рис. 2
Упражнение 1.1. Функция
f принимает в точках 1, 2, 3
соответственно значения 3, 6, 11. Используя параболическую
интерполяцию, найти приближенное значение функции в точке 1,5.
Решение. Точки (1.7) есть точки 1, 2, 3, а потому система (1.8) имеет
в данном случае вид
a0+a1+a2=3, a0+2a1+4a2=6, a0+3a1+9a2=11.
(1.9)
Решаем эту систему методом последовательного исключения неизвестных.
Именно, первое уравнение оставляем без изменений, а из остальных
уравнений исключаем неизвестное a0
, вычитая из второго и третьего
уравнений первое уравнение. Тогда придем к подсистеме
a1+3a2=3, 2a1+8a2=8
или (после деления второго из полученных уравнений на 2) к подсистеме
a1+3a2=3, a1+4a2=4.
(1.10)
m
b
6
Стр.6
Далее действуем аналогичным образом: первое из уравнений подсистемы
оставляем без изменений, а из второго уравнения вычитаем первое. В
результате приходим к уравнению
a2=1.
Для нахождения a1
подставляем найденное значение a2
в первое из
уравнений подсистемы (1.10) и получаем для неизвестного a1 значение
a1=0. Наконец, подстановка найденных значений a1 и a2 в первое из
уравнений (1.9) дает a0=2.
Итак, интерполяционный многочлен имеет вид
p 2
(x)=2
+x2,
а потому приближенное значение функции в точке 1,5 равно 4,25.
Мы ознакомились с понятием интерполяции на простых частных
случаях. Рассмотрим теперь общую ситуацию.
Пусть f
- заданная на отрезке [ a , b ] функция, а
^x 0, ^x 1, ... ,
(111)
— попарно различные точки этого отрезка.
Определение 1.2. Интерполяционным многочленом степени не выше
n (обозначение pn (x; {xi}i=0>..., n; f)) называют многочлен вида
p ( x ) = a0 + a1x + a2x2 +... + anxn ,
значения которого в точках (1.11) совпадают со значениями функции f
pn ( x k ; { xi }i=0
, ..., n ; f )= f
(xк), k = 0, 1, ..., n;
(1.12)
(1.13)
при этом точки (1.11) называют узлами интерполяции, а функцию f —
интерполируемой функцией.
7
Стр.7
Замечание 1.3. Многочлен pn( x; {x}, f ) как функция переменной x
зависит, во-первых, от функции f и, во-вторых, от выбора узлов
интерполяции (1.11), что и отражено в обозначении. В том случае, когда
ясно, о каком наборе узлов и какой функции идет речь, естественно
использовать более простое обозначение: pn(x).
Теорема 1.4. Для любого набора (1.11) попарно различных узлов
интерполяции на отрезке [a,b] и любой заданной на [a,b] функции f
интерполяционный многочлен pn(x; {x}; f ) существует и единственен.
Доказательство. Воспользовавшись формулой (1.12), перепишем
условия (1.13) в виде:
a0
+ a x + a2
(xk)2 + ... + am(xk)m + ... + an(xk)n = f(xk), k=0,1, ... ,n.
(1.14)
Если набор узлов (1.11) зафиксировать, то соотношения (1.14) можно
рассматривать как систему линейных алгебраических уравнений
относительно неизвестных коэффициентов
a0
, a1
, ... , am, ... , an
интерполяционного многочлена pn(x; {xt}, f ), и потому вопрос о
существовании и единственности этого многочлена эквивалентен вопросу
об однозначной разрешимости этой системы при любых правых частях
f(xo), f ( x ) ... , f(xk), ... , f(xn).
(U 5 )
Матрица системы (1.14) имеет специальный вид: её m-тый ( m=0,1,
... ,n ) столбец составлен из m-тых степеней чисел (1.11). Матрицы такого
типа в алгебре называют матрицами Вандермонда; для построения матрицы
B этого класса выбирают ( не обязательно различные ) числа
b0, bb ..., bk, ..., bn,
возводят их в m-тую степень и полученный упорядоченный набор чисел
8
(1.16)
Стр.8
записывают в виде m-того столбца матрицы B. Известен способ
вычисления определителя такой матрицы: сначала следует образовать
всевозможные разности
bi - bj , i>>
чисел (1.16), а затем их перемножить:
det B = ^ (bi - bj ).
i>j
(118)
В нашем случае роль чисел (1.16) играют числа (1.11): bk=xk, k=0,1, ...
,n. В силу предположения о том, что узлы интерполяции - попарно
различные точки отрезка [a,b], разности (1.17), а значит, и их произведение
(1.18) - определитель системы (1.14) - отличны от нуля. Но тогда система
однозначно разрешима при любых правых частях (1.15), что и гарантирует
существование и единственность интерполяционного многочлена.
Замечание 1.5. Проведенные рассуждения указывают и способ
построения интерполяционного многочлена: по заданным узлам
интерполяции (1.11) и значениям (1.15) интерполируемой функции
составляем систему (1.14), решаем её относительно a0, a1, ... , an и
подставляем полученные am в (1.12). Такой способ построения pn(x)
называют методом неопределённых коэффициентов.
Замечание 1.6. Если в результате решения системы (1.14) для старших
коэффициентов an, an-1, ... , an-r будут получены нулевые значения, то
фактическая степень интерполяционного многочлена окажется строго
меньше n (по этой причине в определении 1.2 мы говорим о многочлене
степени не выше n, а не о многочлене n-ой степени).
Замечание 1.7. Укажем, что в определении 1.2 и теореме 1.4 не
предполагается, что крайние точки набора узлов ( 1.11) совпадают с
концами отрезка [a, b], а точки (1.11) занумерованы в порядке возрастания.
9
(1.17)
Стр.9
Считается лишь, что узлы интерполяции - попарно различные точки
отрезка [a, b], в которых известны значения функции f Выбор набора
узлов влияет на коэффициенты интерполяционного многочлена, поскольку
узлы интерполяции входят в матрицу системы (1.14). Что же касается
нумерации узлов в пределах выбранного набора узлов интерполяции, то она
не существенна, так как перенумерация узлов соответствует перестановке
уравнений системы, что, очевидно, не влияет на решение.
§2. Многочлен Лагранжа.
Недостаток изложенного выше метода неопределенных
коэффициентов заключается в необходимости решения системы уравнений
для нахождения коэффициентов интерполяционного многочлена.
Лагранжем предложен способ построения интерполяционного многочлена,
который не требует решения каких бы то ни было линейных систем. Суть
этого способа удобно изложить применительно к случаю n=2.
Упражнение 2.1. Выписать многочлен второй степени, который в
, x2
узлах x1
был бы равен нулю, а в узле x0
Решение. Многочлен
(x - x1 ) ( x - x2).
(2.1)
в узлах x1, x2 равен, очевидно, нулю. А так как узлы интерполяции
попарно различны, в точке x0
он примет ненулевое значение
( x0 - x1) ( x0 - x2).
(2.2)
Деление многочлена (2.1) на число (2.2) и дает нужный многочлен второй
степени.
Обозначим построенный многочлен через l0(2):
10
равнялся бы единице.
Стр.10