Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




Рассмотрим случай, когда требуется обеспечить прохождение алгебраической кривой через заданные точки ` P0 (x0y0), ` P1 (x1,y1),..., ` Pn (xn,yn), (условия типа 1). На производные в данных точках никаких условий не накладывается. Узлы этого типа называют однократными, поскольку в них задано одно геометрическое условие. Такая задача на практике возникает в тех случаях, когда 1) требуется провести степенную кривую через набор точек либо 2) заменить функцию f (х) произвольного вида


степенной L(х) при заданных положениях её узлов x0, x1,..., xn.

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

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

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

Для дальнейшего анализа рассмотрим полином w(х), принимающий нулевые значения только в узлах интерпо-лирования x0, x1,..., xn и имеющий единичный коэффи-ци-ент при старшей степени х. Его можно представить в виде:

w(х)= (x-x0)× (x- x1)×... × (x- xn).

 
 

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

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

w¢(xi) = (xi -x0) × (xi - x1)×... × (xi - xi-1 )× (xi - xi+1)× …× (xi - xn).


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

w(х)/(x-xi)=(x -x0) × (x - x1)×... × (x - xi-1 )× (x - xi+1)× …× (x - xn).

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

 
 

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

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

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

w(х)/(x-xi)=(x -x0)× (x -x1) ×... × (x - xi-1 )× (x - xi+1)× …× (x - xn).

В узле х=xi значение его равно некоторой ненулевой константе: w¢(xi) = (xi -x0)× (xi - x1)×...× (xi - xi-1 )× (xi - xi+1)× …× (xi - xn), которая в общем случае может принять любое значение (как по величине так и по знаку). Для того, чтобы искомая функция в узле х=xi стала равной единице, необ-ходимо w(х)/(x-xi) разделить на w¢(xi):

(2.9)


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

(2.10)

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

L n (x)=(`Ф(х),`Y), (2.10а)

где `Y=(y0 , y1 ,..., yn); `Ф(х)=(Ф0 (х), Ф1 (х),..., Фn (х)).

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

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

S(x)= у0 (x1 –x)/(x1 -x0)+ у1 (x-x0) /(x1 -x0 ). (2.11 а)

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

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

`Ф(x) = ((x1 –x) / (x1 -x0), (x-x0) / (x1 -x0 )); `Y= (у0, у1).

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


 
 

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

(2.11.б)

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

Рассмотрим иное представление интерполяционного многочлена. Допустим, рассматривается задача интерпо-лирования некоторых значений у(xi)=уi на однократных узлах x0, x1,..., xn.

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

f(x1, x0) = (у1 - у0)/(x1 - x0 );

f(x2, x1, x0) = (f(x2, x1) - f(x1, x0))/(x2- x0 );

f(x3, x2, x1, x0) = (f(x3,x2, x1) - f(x2, x1, x0))/(x3- x0 );

...

f(xn,..., x0) = (f(xn,..., x1) - f(xn-1,..., x0))/(xn- x0 ).

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

LNn (x)= у0+(x - x0 ) f(x1, x0) + (x- x0 )(x- x1 ) f(x2, x1, x0) +...+ (x - x0)(x- x1) ×... × (x - xn-1) f(xn,..., x0). (2.12)


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

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

Построить:

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

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

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

w(х)= (x-x0)(x- x1)(x- x2 )= (x+1)(x-2)(x-4).

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

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

В векторной форме: L 2 (x)=(`Ф(х),`Y), где `Ф(х) = (Ф0(х), Ф1 (х), Ф2(х))=

`Y = (y0 , y1 , y2) = (-2, 1, 5).

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

f(x1, x0) = (у1 - у0)/(x1 - x0 )=(1-(-2)) / (2-(-1)) = 1;

f(x2, x1) = (у2 - у1)/(x2 - x1 )=(5-1) / (4-2) = 2;

f(x2,x1,x0)=(f(x2, x1) - f(x1,x0))/(x2-x0)=(2–1) / (4-(-1)) = 1 / 5.

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

LN2 (x)= у0+(x - x0 ) f(x1, x0) + (x- x0 )(x- x1 ) f(x2, x1, x0) =

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


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

Задачи.

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

а) Задача 1 в) из п.2.2,

б) n=2; х0 = 1; х1 = 2; х2 =3;

у(х0) = - 2; у (х1)= 1; у(х2) = - 4;

в) n=3; х0 = -1; х1 = 0; х2 =1; х3 = 2;

у(х0) = 10; у (х1) = 5; у(х2) = - 1; у(х3) = 1.

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

 

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...