книги / Численные методы. Ч. 1

являющееся полиномом степени п со старшим коэффициентом, равным I. Иначе говоря, получена задача Чебышёва. рассмотренная ранее. Искомый полином имеет на отрезке [а.Ь] корчи

Ь+ а	Ь - а cos 2к + 1 Я, к = 0,п.
*к = 2~	2~	2(п + 1)

Оценка модуля полинома, наименее уклоняющего от нуля.

( ь - * Г

х22л+1

Оценка погрешности полинома Ньютона (Лагранжа) при использовании узловых точек, соответствующих корням полинома Чебышева, имеет вид

	Цу-ро| = тах(у(х)-Ра(х)|<	м.„	(ь -)-
		(п + 1)!	22"*1
Сходимость интерполяционного процесса
Множество точек а < х0 <х, <... < xn < b		назовем сеткой на отрезке [а. Ь]
обозначим	Пп. Рассмотрим последовательность сеток		..... Пп,... Построим
на отрезке	[а.Ь] последовательность полиномов Рп(х), аппроксимирующих с помощью

сеток £2Пфункцию у(х).

Интерполяционный процесс сходится в точке х* e[a.b], если существует предел lim Pn(x*) = у|х#j (определение поточечной сходимости).

Интерполяционный процесс сходится равномерно на отрезке [а, Ь], если

Ь - р.1= ^ у(х) - Р . И - т т ^ 0

Теорема 4.1 (Фабера1)- Какова бы ни была последовательность сеток Пп-, найдется непрерывная на [а.Ь] функция у(х) такая, что последовательность интерполяционных полиномов Рп(х) не сходится к у(х) равномерно на этом отрезке.

| Фабер Георг [5.4.1877 1966] - немецкий маюматпк. был профессором Высшей технической

школы в Мюнхене с 1916 года

На рис. 4.1 приведен пример аппроксимации непрерывной функции f(x) = |х| на

последовательности сеток с равноотстоящими узлами.

Рис. 4.1. Аппроксимация на отрезке [-1. I] функции f(x) = |х| полиномами Р„. построенными с использованием равномерных сеток

На рис. 4.2 представлен график погрешности аппроксимации функции f(x) = |.\| полиномамм на равномерных сетках в зависимости от числа отрезков сеточной области.

Ilf-Pnll

Рис. 4.2. Погрешность аппроксимации на отрезке [-1, 1] функции f(x) = |х| в зависимости от числа отрезков равномерной сетки

Теорема 4.2. Если функция у(х) непрерывна на отрезке [а,Ь], то найдется такая

последовательность сеток, для которой интерполяционный процесс сходится равномерно на этом отрезке.

На рис. 4.3 приведен пример аппроксимации непрерывной функции f(x) = |х| на последовательности неравномерных (чебышевских) сеток. На рис. 4.4 представлен график погрешности аппроксимации функции f(x) = |х| полиномом Р„ на чебышевской сетке в зависимости от числа отрезков сеточной области.

Рис. 4.3. Аппроксимация на отрезке [-1. 1] функции f(x) = |х| полиномами Рп, построенными с использованием чебышёвских сеток

Интерполяционный многочлен Эрмшпа1
Пусть заданы значения ук функции и некоторых	ее производных	в точках
хк, к = 0,п отрезка [а,Ь]. Если потребовать от полинома	Рп(х) совпадения	не только

значений функции (4.1), но и значений производных в заданных точках, интерполяция носит название эрмитовой, а сам полином обозначается как Нр(х).

1 Эрмит Шарль [24.12.1822 - 14.1.1901] - французский математик. С 1856 года		являлся членом
Парижской академии наук, с 1857 года	иностранным члспом-корреспондеитом	Петербургской

академии наук. С 1869 года был профессором Парижского университета. С 1873 юла пал членом

Лондонского королевского общества. С 1895	избран иностранным почешы.м
Петербургской академии наук.

у(*о.х.) =

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

у(хо)-у(х,)

х„-х .

Однако с помощью предельного перехода можно установить, что

l i m y ^ . x ,^	^ Х|^ = у'(х,).
Т..4Т. Х ' T.^f.	V _ Т	' '

l|f-Pn||

Рис. 4.4. Погрешность аппроксимации функции f(x) = |х| на отрезке [-1, 1] в зависимости от числа отрезков чебышёвской сетки

Иными словами, первая разделенная разность, что уже отмечалось ранее, совпадает со значением первой производной в точке х0. Это будет означать также, что полином Эрмита Нр(х) позволяет правильно передавать значения производных.

Разделенные разности более высоких порядков определяются с учетом этого

следующим образом:

х«, Х|

„Л, _ „ . ч_У(*о.*в.Х|)-у(х».Х|.х,)_У'(*.)-2у(хо.Х|) +У'(х1)

Д А0’Л0»Х1»Х1) ~ -------------------------------- ” ----------------------------------•

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

В общем случае имеет место формула:

у|*о.*о

Оценку точности аппроксимации выполним с ипользованием формулы (4.7):

|у0 0 - н . ( Ф т^ | ® ( 4		i m k = n +i,
Vn + V-	k-0	k->0

где р - число точек интерполяции, mk - число значений функции и ее производных в

точке хк . Такой выбор функции а>(х) обеспечивает обращение в нуль не только g(s). но

и ее производных g"4 (xk) .

На рис. 4.5 приведены приближения функции Г(х) = х + sin(x) полиномами Эрмита

Нз(х). Hs(x), Н^х), НИх) (на рисунке аппроксимация ННх) практически совпадает с самой функций) и полиномом Лагранжа РНх) для отрезка [0, 25] на равномерных сеточных множествах.

Рис. 4.5. Графики интерполяционных полиномов Эрмита и Лагранжа

Сплайн способ аппроксимации функции, заданной таблично, с помощью

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

EIu,v = q(x),

где Е - модуль упругости, I - момент инерции поперечного сечения, и - функция прогиба. q(x) распределенная нагрузка. В случае отсутствия нагрузки получаем однородное уравнение

u,v =0,

имеющее решение, представляемое кубическим полиномом, и = С„ + С,х + С,х: + С3х3.

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

Построение кубического сплайна

Пусть на отрезке [а,Ь] задана сетка а = х() <х, < ...< х п = Ь; известны табличные значения функции f(xk), к = 0,п в узлах этой сетки.

Потребуем, чтобы сплайн S(x) удовлетворял следующим условиям:

а) на каждом сегменте [хк_,,хк ], к = 1,п являлся полиномом третьей степени;

б) был непрерывен вместе с первой S'(x) и второй S"(x) производными на [а,Ь];

в) совпадал со значениями аппроксимируемой функции в узлах сетки.

1spline (англ.) - гибкая линейка.

Сплайн S(x) на каждом сегменте [хк_,,хк]отрезка [a,b] строится в виде

Sk(x) = ak +bt (x -x t )+ ^ -(x -x k)2+ ^ ( x - x k)3, k = l,n

(4.8)

Первые и вторые производные:

Sk(x) = Ьк + ск(х -х к) + ^ - ( х - х к)2

Sk (x) = ck +dk(x -x k),

двух ‘ соседних” сплайнов Sk(x) и Sk+i(x) в общей точке должны удовлетворять условию б), откуда получаем систему уравнений (условия непрерывности сплайна и его производных):

Sk(xk)~Si ,(xk).ak - a k4 + bl.,(xt - x t.,)

i2+^ ( x k - x k.,)!,k =

S^(xk) = SU,(xk). bk = bk+, +ck+1|	+ !W (xk - x ktl)2,
(*к -*ы )	2

1 I c II

Sk(xk) = S^,(xk),	ck =cktl+dk+1(xk - x k+l)>	k = l,n - l.
И. наконец, условия в) дают выражения:
Sk(xk) = ak = f(xk), k = l,n.
Обозначим hk+1=xk+I- x k	длины отрезков. Теперь	предыдущие выражения

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

коэффициентов ak.b k.ck,d k,		k = l,n:
ak= ak+l- ^L+l^k+l +~y“^k+l			^^k+l * к = 1,П-1,		(4.9)
	bk = bkt| - c w hk+1 + - y Lht.f,2,			k = l,n - l,	(4.10)
	ck = cu i - ^t+ibk.|,		к = l,n - 1,		(4.11)
		at = f(xk),	к = l,n .		(4.12)
Система (4.9)	(4.12)	содержит ( 4п - 3)		уравнения с (4п)	неизвестными,
Учтем дополнительно, что для точки х„ = а имеет место соотношение

S,(xo)-a,+b,(x0

2 (xo Xfc) +"^"(xo *k) ^ o ) •

Используя соотношения (4.12), в последнем выражении и уравнениях (4.9) можно исключить “лишние” неизвестные ак. к = 1,п, а сами уравнения записать в форме

fk =	- b k+1hk+, + ^ h	k+l2 - ^ - h k+l3, k = 0 ^ > .	(4.13)
В результате система (Зп-2) уравнений (4.10), (4.11) и (4.13) содержит Зп
неизвестных bk,ck,d k,	к = 1,п.
Для “замыкания” этой системы уравнений положим
	00	и о	(4.14)
	S"(b) = 0,		(4.15)

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

Условие (4.14) с помощью выражения (4.8) удобно представить в форме
s iW	= ci - d ihi = °-
а формулу (4.15) - в виде
s;'(x„)=cn=о.
что позволяет переписать уравнения (4.11)
dkhk = ck -	k -l,n ; с0 = 0; сп = 0.	(4.16)
В итоге получена система (Зп+1) уравнений (4.10), (4.13), (4.16), содержащих
(Зп+1) неизвестную величину.
Рассмотрим два уравнения вида (4.13)
bt hk - ^ h k2+ ^ h k3 = fk - f k,
bk+1hk+1 - “~ h	k+)2 + “~ " h t+13 = fk+1 —fk.

b

= Ls—! k i+ £k.h

k

- i - h j 1,

k

hv

2

6

k

b

_

f>H

. CH.I (.

d t .l

h

2

Dk*i “ .

+

,

n k*l

,

n k*l

hk4

2

6

Подставим полученные выражения для

bk, bk+1 в уравнения (4.10):

ck^!^k>i

!^*hk+,

= Ьк+, - Ьк =

_ f(»t.i)-f(xt )

,с М11

dtt, h

!

f(xt )-f(x t.,) ct h

| dt

hk

- ^ - h k+ ^ h t!.

2 1

6 k

<,A ., « A -

\ ^ K

: - i d A 1 ■

к = 1,n —1.

Формулы (4.16) позволяют получить выражения

dkhk =(ск - c k_,)hk,

dk+Ihk+, =(cw - c k)hk+l,

благодаря чему предыдущая формула преобразуется к виду

Ck*|hk*l +Ck^k ~у(Сь.|~Ck)^k+l “ j(Ck“Ck-l)^k =

j f(xM)- f(x t )

f(xt )- f(x t_,)j

R = —

v

hk+1

hk

J

Приводя подобные слагаемые и учитывая условия (4.14) и (4.15), получаем

ck-,hk+2ck(hk+ hkJ + c k+1hk4l =

/

f(Xk- ') - f(xk)

f(xk)-f(x k- ,) \

k = ] ^ n

(4.17)

ч

hk<.,

hk

/

cn =0,

c = 0.

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

неизвестных величин ск. к = 0,п определяются остальные коэффициенты сплайнов:

hk

ak = fk,

bt = ^ h k - ^ +l ^ . k = U .

2

6

n k

Покажем, что при неограниченном увеличении числа п узлов на отрезке [а,Ь] последовательность сплайн-функций сходится к интерполируемой функции.

Для упрощения рассмотрим последовательность сеток с равномерными расположениями узлов:

п

В этом случае система уравнений (4.17) принимает более простой вид

с0 =0, сп = 0.

Пусть аппроксимируемая функция f(x) непрерывна вместе со своими производными вплоть до четвертого порядка, то есть f eC (4)[a,b], а также имеют

место равенства
	f "(а) = 0, f"(b) = 0 .
Обозначим:
	чебышевская норма на отрезке [а,Ь];
H L = ^ ч > (хк)1	- чебышевская норма на сеточной области Qn;
f„.k = ^ ( f ( * k,) - 2 f(x k) + f(xk„))	- разностный аналог второй производной
	аппроксимируемой функции f(x);

Теперь система уравнений (4.17) выглядит следующим образом:

ck_, +4ск +ck+1 = 6fxxk, к = 1,п-1,

(4.18)

1со = 0, сп = 0.

Лемма 4.1. Для всех f(x) eC (4)[a,b] справедлива оценка ||f" -S "]^ < ^ M 4h2.