Вычислительная математика лекции

3.7.1.Обсуждение способа построения кубического интерполяционного сплайна с дефектом 1.

Пусть отрезок [a,b] разбит точками a=x0 < x1 < … xn =b на n

частичных отрезков [xi-1 ,xi ], i=1,2,…,n .

P3i (x) =ai+bi(x-xi-1)+ci(x-xi-1)2+di(x-xi-1)3.

Всего n кубических полиномов и соответственно 4n

неизвестных коэффициентов ai, bi, ci, di. Для их однозначного определения необходимо сформулировать 4n условий.

Первая группа условий следует из равенства значений сплайна и сеточной функции в узлах:

P3i(xi)=yi; P3i(xi-1)=yi-1 i=1,2,…,n. Всего 2n условий

Вторая группа следует из непрерывности 1-ой и 2-ой производных во внутренних узлах:

P(1)3i(xi)= P(1)3i+1(xi); P(2)3i(xi)= P(2)3i+1(xi); i=1,2,…,n-1. Всего

2(n-1) условий.

В сумме получаем 4n-2 условия. Недостающие два условия нужно задать в паре внешних узлов x0 и xn. Возможны следующие варианты:

а) P(1)3i(x0)=γ0; P(1)3i(xn)=γn ; γ0, γn заданные числа.

б) P(2)31(x0) =η0; P(2)3n(xn)=ηn ; η0, ηn заданные числа.

в) P(2)31(x0) =0; P(2)3n(xn)=0.

В двух первых случаях γ0, γn , η0, ηn совпадают с значениями производных y(x) в соответствующих точках.

31

При выполнении условий а) или в) сплайн называют фундаментальным или естественным соответственно.

Существуют другие способы задания граничных условий.

В результате имеем линейную систему из 4n уравнений для 4n

неизвестных коэффициентов. С целью экономии машинной памяти осуществляют редукцию системы путем исключения некоторых переменных. В результате можно получить размер матрицы , равным n, и сделать ее трехдиагональной.

При использовании дополнительных условий в форме а) или

б) погрешность оценивается по формуле max | y(x) S3 (x) | CM4hmax .

x [a,b]

Для k-ой производной справедливо соотношение

max | y(k ) (x) S (k )3 (x) | CM4h4-k max .

x [a,b]

Для естественного сплайна порядок точности понижается с 4

до 2.

3.7.2.B сплайны.

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

n

согласно формуле S1(x)= yi B1i . Здесь B1i базисный сплайн в узле i.

						i 0
	B1i	=0, если x≤xi-1 и x≥xi+1
	B1i	=	x xi 1			, если xi-1 ≤ x < xi
			x x
			i	i 1
	B1i	=	xi 1	x		, если xi ≤ x xi+1 .
			x	x
			i 1	i
					32

B1i=1, если x=xi.

B1i

1

	X
Xi	Xi+1
Xi-1

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

4.Среднеквадратичное приближение

4.1.Постановка задачи для f(x).

Требуется найти приближающий полином Pm (x) ,

минимизирующий функцию расстояния между f(x) и Pm(x):

ρ(f(x),Pm(x)) → min;

m

Pm ( x) i i ( x)

i 0

φi(x) – линейно независимые базисные функции.

В качестве функции расстояния для среднеквадратического приближения используется следующий функционал

33

b

J ( 0 , 1 ,...., m ) (Pm (x) f (x))2 dx

a

Функционал – отображение из некоторого пространства

функций или векторов на числовую ось.

4.2.Постановка задачи для приближения векторов

Для векторов задача среднеквадратичного приближения ставится следующим образом. Пусть имеется вектор у R(n+1) и

m

задана линейная комбинация i i линейно независимых векторов

i 0

φi с неопределенными коэффициентами αi. Каждый из φi имеет

n

размер n+1. Нужно заменить вектор y на i i . Параметры αi

j 0

нужно найти таким образом, чтобы достичь минимума функционала:

n	m
J ( 0 , 1 ,..., m ) ( yk ( i i )k )2
k 0	i 0

Задача среднеквадратичного приближения векторов возникает,

если таблично заданную функцию yk(xk) (k=0,1,…,n) нужно аппроксимировать алгебраическим полиномом Pm(x) =

α0+α1x+…+αmxm степени m ≤ n. В этом случае имеем СЛАУ:

α0x00+α1x01+…+αix0i+…+αmx0m = y0 α0x10+α1x11+…+ αix1i +…+αmx1m = y1

……………………………

α0xi0+α1xi1+…+ αixii +…+αmxim = yi

……………………………

α0xn0+α1xn1+…+ αixni +…+αmxnm = yn

Эквивалентная форма записи этой системы:

34

α0φ0+α1φ1+…+ αiφi+…+αmφm = y , где φi = (x0i x1i…xni)T,

i = 0…m. Таким образом, в данном случае мы аппроксимируем

заданный вектор

y = (y0 y1…yn)T размера n+1 набором из m+1 базисных векторов

φi размера n+1

φi = (x0i x1i…xni)T, i = 0…m. В частном случае m = n, получаем задачу интерполирования. При m < n имеем дело с переопределенной системой.

4.3.Определения.

Определение1. Будем называть скалярным произведением функций или векторов следующие числа:

для функций v(x), y(x) x [a,b]

b

( y, v) y( x)v( x)dx

a

для векторов v,y Rn+1

n

(v, y) vi yi

i 0

Воспользовавшись ведёнными обозначениями,

соответствующие функции расстояния можно записать следующим образом ((y-v), (y-v)), где y -приближаемый вектор или функция, а v –

приближающий вектор или функция.

Пространство вещественных функций (векторов), для которых определено скалярное произведение, называется евклидовым.

Определение2. Пусть в евклидовом пространстве функций

(векторов) дана система базисных элементов φ0, φ1, …, φm. Эта система называется линейно независимой, если равенство

35

α0φ0 + α1φ1 + … + αmφm = 0 имеет место тогда и только тогда, когда все αi = 0 для i = 0, … , m.

Определение3. Определитель матрицы вида

( 0 , 0 )

( m , 0 )

( 0 , m )

называется

( m , m )

определителем Грама для системы функций или векторов.

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

базовых элементов φ0, φ1, …, φm линейно зависима.

Определение 4. Будем называть функцию ||x|| нормой вектора

или функции, отображающей вектор или функцию на числовую ось и

удовлетворяющую следующим условиям:

1)Неотрицательность ||x|| ≥ 0; ||x|| = 0 x= 0.

2)Однородность ||αx|| = |α| ||x||, где α скаляр.

3) Неравенство треугольника ||x+y|| ||x|| + ||y||. Примеры норм.

Для векторов:

n

x1 | xi |; ||x||2

i 0

n
xi ;	||x|| max | xi | .
i 0	i

Для функций:

	b				b
|| f (x) ||		| f (x) |dx; || f (x) ||				( f (x))2 dx; || f (x) ||		max | f (x) | .
1			2					[a,b]
	a				a

36

4.4.Решение задачи.

Для того, чтобы найти min(J(α0, α1, …, αm)) требуется решить систему m+1 линейных алгебраических уравнений для m+1

неизвестных α0, …, αm:

J 0,(i 0, m)

i

Такая система называется нормальной. Можно показать, что она имеет вид:

( 0 , 0 )

( m , 0 )

( 0	, m )	0				( f , 0 )
( m , m )		m				( f , m )

Здесь f приближаемая функция или вектор. Действительно,

пусть осуществляют среднеквадратическое приближение функции f(x). Тогда

	J			b	b
				[ (Pm (x) f (x))2 dx] 2 (Pm (x) f (x))			(Pm (x) f (x))dx
			i
	i			a	a	i

b

2 (Pm (x) f (x)) i (x)dx 0.

a

Отсюда следует (φi, φ0)α0+(φi, φ1)α1+…+(φi, φm)αm-(f, φi)=0, i=0,1,…,m.

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

37

5.Ортогонализация

5.1.Постановка задачи

При отсутствии специального способа выбора базисных элементов φi, (i = 0…m ) даже в случае их линейной независимости обычно уже при m > 5 нормальная система оказывается настолько плохо обусловленной, что её решение на ЭВМ практически бесполезно. В частности, такими свойствами при больших m

обладает система базисных функций 1, x, … xm. Дело в том, что,

будучи формально линейно независимой, с ростом m система базисных элементов может оказаться очень близкой к линейно зависимой.

Максимально линейно независимой оказывается система базисных элементов φ0, φ1, …, φm , ортогональных на множестве точек x0, x1, …, xn для векторов или на отрезке [a,b] для функций.

Система базисных элементов называется ортогональной, если (φi,φj)

= 0 при i ≠ j и (φi,φj) ≠ 0 при i = j.

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

Пусть задана система базисных элементов φi i = 0, 1, …, m.

Нужно построить систему соответствующих ортогональных базисных элементов ψi . Последовательно рассчитывают:

ψ0 = φ0; ψ1 = φ1 + а10ψ0;

ψ2 = φ2 + а20ψ0 + а21ψ1;

ψj = φj + aj0ψ0 + aj1ψ1 + ... + ajj-1ψj-1;

ψm = φm + am0ψ0 + am1ψ1 + … +amm-1ψm-1.

38

Коэффициенты аji i < j, i = 0,…,m отыскиваются из условия ортогональности ( ψi,ψj) = 0. Можно показать, что aji = -(ψi,φj)/ (ψi,ψi).

Например, из условия ортогональности (ψ0,ψ1) = 0 следует

(ψ0,ψ1) = (ψ0,φ1+а10ψ0,ψ0) = (ψ0,φ1) + (а10 ψ0,ψ0)= (ψ0,φ1) + а10

(ψ0,ψ0)=0.

Отсюда а10 = -(ψ0,φ1) / (ψ0,ψ0).

При использовании ортогональной системы базисных

элементов матрица нормальной системы становится диагональной

Дополнительные замечания.

1.Если в качестве базисных функций задают алгебраические

полиномы, для построения ортогональной системы можно использовать полиномы Лежандра как удобную альтернативу методу Грама-Шмидта. Полиномы Лежандра ортогональны на отрезке [-1,1]

. Для их определения используется рекуррентная формула

(n+1) n+1(t)-(2n n(t)t+n n-1(t , где 0(t , 1(t)=t.

Переход от отрезку x [a,b] к отрезку t					[-1,1] осуществляется
	a b		b a			2		a b
заменой переменных x				t;	t=		x		.
						b a
	2		2					2

2 Нормальная система имеет единственное решение, если базовые функции линейно независимы При таком условии можно говорить о существовании и единственности обобщенного полинома, удовлетворяющего критерию среднеквадратического приближения Разработаны приемы построения обобщенного полинома в случае линейной зависимости базисных функций В этом случае решение не единственно

3 Нелинейная задача метода наименьших квадратов предполагает, что приближающая функция g(x,α0,…, αm не линейна относительно искомых коэффициентов В типовых

39

программах встречаются функции следующего вида: aebx+cedx экспоненциальная аппроксимация, Qm(x)/Pn(x рациональная дробь, axb потенциальная функция

6.Равномерное приближение функций.

Постановка задачи.

Пусть f(x) заданная на отрезке [a,b] непрерывная функция.

Будем говорить, что многочлен Pn(x) приближает f(x) равномерно на

отрезке [a,b] с точностью ε, если ||f(x) - Pn(x)||∞ = max | f (x) Pn (x) | .

x [a,b]

Естественно поставить задачу следующим образом: среди всех многочленов фиксированной степени n найти многочлен Qn(x), для которого ε минимальна. Qn(x) называют многочленом наилучшего равномерного приближения.

Теорема 1. Для любой непрерывной на отрезке [a,b] функции f

многочлен наилучшего равномерного приближения Qn(x) существует и единственен.

Теорема 2.(Теорема Чебышева): для того, чтобы многочлен

Qn(x) был многочленом наилучшего равномерного приближения непрерывной на отрезке [a,b] функции f(x), необходимо и достаточно, чтобы на [a,b] нашлись по крайней мере n+2 точки x0< x1<… xn+1 такие, что

f (xi ) Qn (xi ) ( 1)i max| f (x) Qn (x)|,i 0,1,...,n 1. Здесь α

[a,b]

– постоянная, равная 1 или -1 для всех i одновременно.

Точки x0, x1,…, xn+1, удовлетворяющие условиям теоремы,

называют точками чебышевского альтернанса (alternare –

40