§3. Интерполирование по однократным узлам. Интерполяционные многочлены Лагранжа и Ньютона

Рассмотрим случай, когда требуется обеспечить прохождение алгебраической кривой через заданные точки P₀ (x₀y₀), P₁ (x₁ ,y₁),...,P_n (x_n,y_n), (условия типа 1). На производные в данных точках никаких условий не накладывается. Узлы этого типа называют однократными, поскольку в них задано одно геометрическое условие. Такая задача на практике возникает в тех случаях, когда 1) требуется провести степенную кривую через набор точек либо 2) заменить функцию f ( х ) произвольного вида

51

степенной L(х) при заданных положениях узлов x₀, x₁ ,..., x_n .

В математической форме задачу интерполирования по однократным узлам можно сформулировать следующим образом. В узлах x_i , (i = 0,1 ,...,n; x_i  x_j при i j) заданы значения у(x_i)=у_i. Требуется построить полином L(x) минимально возможной степени, для которого L( x_i) = у_i , (i = 0,1 ,...,n).

Решение задачи существует и единственно (доказатель-ство этого факта выходит за рамки курса), хотя сам много-член может быть представлен в разных видах. Наряду с каноническим представлением (2.5) в задаче интерпо-лирования по однократным узлам он может быть представ-лен в виде полиномов Лагранжа и Ньютона.

Так как общее число геометрических условий в задаче равно n+1, то искомый интерполяционный полином имеет степень не выше n (при этом число его неизвестных коэффициентов C₀, C₁, …, C_n равно n+1). Примеры, в которых степень полинома меньше расчётной, рассмотре-ны в §2.

Для дальнейшего анализа рассмотрим полином (х), принимающий нулевые значения только в узлах интерполирования x₀, x₁ ,..., x_n и имеющий единичный коэффициент при старшей степени х. Его можно представить в виде :

(х)= (x-x₀)*(x- x₁)*...*(x- x_n ).

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

При подстановке в производную узловой точки x_i все слагаемые кроме i-го обнуляются и получается произве-дение, в котором отсутствует i-тый сомножитель:

( x_i) = (x_i -x₀)*( x_i - x₁)*...*( x_i - x_i-1 )* (x_i - x_i+1)*…* (x_i - x_n).

52

Рассмотрим выражение

(х)/(x-x_i)=(x -x₀)*( x - x₁)*...*( x - x_i-1 )* (x - x_i+1)*…* (x - x_n).

Используя правило дифференцирования произведений, получим его производную в следующем виде:

В узле х=x_i значение производной равно

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

Построение каждой функции Ф_i (x) можно представить следующим образом. Полином, принимающий нулевые значения в узлах x₀, x₁,..., x_i-1, x_i+1,… x_n и имеющий единич-ный коэффициент при старшей степени имеет вид:

(х)/(x-x_i)=(x -x₀)*(x -x₁)*...*(x - x_i-1 )* (x - x_i+1)*…* (x - x_n).

В узле х=x_i значение его равно некоторой константе

( x_i) = (x_i -x₀)*( x_i - x₁)*...*( x_i - x_i-1 )* (x_i - x_i+1)*…* (x_i - x_n),

которая в общем случае может принять любое значение (как по величине так и по знаку). Для того, чтобы искомая функция в узле х=x_i стала равной единице, необходимо (х)/(x-x_i) разделить на ( x_i):

(2.9)

53

Полученные функции Лагранжа Ф_i (x) обладают всеми требуемыми свойствами. Интерполяционный многочлен Лагранжа имеет вид:

(2.10)

Выражение (2.10) в векторной форме можно представить как скалярное произведение:

L _n (x)=(Ф(х),Y), (2.10а)

где Y=( y₀ , y₁ , . . . , y_n) ; Ф(х)=(Ф₀ (х) , Ф₁ (х) , . . . , Ф_n (х) ).

Текст функции lag вычисления интерполяционного многочлена Лагранжа, а также отладочная программа представлены в Приложении.

Рассмотрим простейший случай интерполирования на отрезке [x₀, x₁]. В его граничных точках заданы по одному геометрическому условию: у(x₀) = у₀ , у(x₁) = у₁ . Наи-меньшая степень полинома S(x) равна единице. Явное решение для S(x) даёт следующий многочлен Лагранжа:

S(x)= у₀ (x₁ –x)/(x₁ -x₀)+ у₁ (x-x₀) /(x₁ -x₀ ). (2.11 а)

В векторной форме:

S(x) = (Ф(x),Y);

Ф(x) = ( (x₁ –x) / (x₁ -x₀), (x-x₀) / (x₁ -x₀ )); Y= ( у₀ , у₁ ).

Переходя к безразмерной нормированной переменной t=(x-x₀) / (x₁ -x₀ ), у которой t(x₀)=0; t(x₁)=1, получим более простые выражения для функций Лагранжа: Ф₁ (t)=1-t; Ф₂ (t) = t. Введём также векторT ¹ степеней t порядка 1 и матрицу М_Л, задающую переход отT ¹ к вектору значений функций Лагранжа (Ф₁ (t); Ф₂ (t)) :

54

При этом вектор значений функций Лагранжа и полином S(t) можно представить в виде :

Данное представление помогает унифицировать интер-поляцию кривой отрезком прямой на произвольном интервале и используется при сплайновом интерполи-ровании.

Рассмотрим иное представление интерполяционного мно-гочлена. Допустим, рассматривается задача интерпо-лирования некоторых значений у(x_i)=у_i на однократных узлах x₀, x₁ , ... , x_n .

Определение. Разделёнными разностями (разностными отношениями) по узлам интерполирования x₀, x₁ ,..., x_n порядка 1, 2, 3, …, n называются следующие величины

f(x₁, x₀) = (у₁ - у₀)/( x₁ - x₀ );

f(x₂, x₁, x₀) = (f(x₂, x₁) - f(x₁, x₀))/( x₂- x₀ );

f(x₃, x₂, x₁, x₀) = (f(x₃ ,x₂, x₁) - f(x₂, x₁, x₀))/( x₃- x₀ );

. . .

f(x_n, . . . , x₀) = (f(x_n , . . ., x₁) - f(x_n-1, . . ., x₀))/( x_n- x₀ ).

C помощью разделённых разностей, которые являются некоторыми постоянными величинами, рассчитываемыми по значениям x_i , у_i ( i = 0,1 , ... ,n), многочлен можно представить в следующем виде:

L^N_n (x)= у₀+( x - x₀ ) f(x₁, x₀) + ( x- x₀ )( x- x₁ ) f(x₂, x₁, x₀) + . . .+ (x - x₀)(x- x₁)*. . . * ( x - x_n-1 ) f(x_n, . . . , x₀). (2.12)

55

Формула (2.12) называется интерполяционным много-членом Ньютона. У обоих полиномов порядок узлов в формулах может быть выбран любым способом.

Пример. На множестве однократных узлов x₀ = - 1 ; x₁ = 2; x₂ =4 заданы значения функции у(x): у(x₀) = у₀ = - 2; у(x₁) = у₁ = 1; у(x₂) = у₂ = 5.

Построить:

1. функции и многочлен Лагранжа,

2. разделённые разности и многочлен Ньютона.

Решение. 1. Вспомогательный полином (х) имеет вид :

(х)= (x-x₀)(x- x₁)(x- x₂ )= (x+1)(x-2)(x-4 ).

Функции Лагранжа строим по формуле (2.9):

Многочлен Лагранжа строим по формуле (2.10):

В векторной форме: L ₂ (x)=(Ф(х),Y), гдеФ(х) = (Ф₀(х) , Ф₁ (х), Ф₂(х))=

Y = ( y₀ , y₁ , y₂) = ( -2 , 1 , 5).

2. Рассчитаем разделённые разности :

f(x₁, x₀) = (у₁ - у₀)/( x₁ - x₀ )=(1-(-2)) / (2-(-1)) = 1;

f(x₂, x₁) = (у₂ - у₁)/( x₂ - x₁ )=(5-1) / (4-2) = 2;

f(x₂,x₁,x₀)=(f(x₂, x₁) - f(x₁,x₀))/(x₂-x₀)=(2–1) / (4-(-1)) = 1 / 5.

Многочлен Ньютона строим по формуле (2.12):

L^N₂ (x)= у₀+( x - x₀ ) f(x₁, x₀) + ( x- x₀ )( x- x₁ ) f(x₂, x₁, x₀) =

- 2 +( x +1 ) + ( x +1 )( x- 2 ) / 5.

56

Правильность обоих многочленов можно проверить не-посредственной подстановкой в них значений x₀ = - 1 ; x₁ = 2 ; x₂ =4.

Задачи.

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

а) задача 1.в из §2,

б) n=2; х₀ = 1 ; х₁ = 2 ; х₂ =3 ;

у(х₀) = - 2 ; у (х₁)= 1 ; у(х₂) = - 4 ;

в) n=3; х₀ = -1 ; х₁ = 0 ; х₂ =1 ; х₃ = 2 ;

у(х₀) = 10 ; у (х₁) = 5 ; у(х₂) = - 1 ; у(х₃) = 1 .

2. Найти разделённые разности и построить интерполяционные полиномы Ньютона для геометрических условий из задач 1 а), 1 б), 1в).