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

Глава 6

АППРОКСИМАЦИЯ ФУНКЦИЙ.

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

Ясно, что в этом случае следует изменить постановку задачи.

6.1Аппроксимация элементов гильбертова пространства H.

Определение гильбертова пространства начинается с введения в линейном пространстве скалярного произведения, затем определяется норма элементов и определяется метрика пространства. Если полученное нормированное пространство оказывается полным, то оно называется гильбертовым.

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

'1; '2; : : : ; 'm:

Рассмотрим линейную оболочку этих элементов L('1; : : : ; 'm), т.е. множество всех линейных комбина-

ций элементов '1; '2; : : : ; 'm:

m

X

cj'j

j=1

Упорядоченная система чисел fc1; c2; : : : ; cmg образует m-мерный вектор C.

Для заданного элемента f 2 H найти вектор C Vm, такой что

m

X

kf cj'jkH ! min :

j=1

c1;:::;cm

Ясно, что задача эквивалентна задаче минимизации функционала

m

X

J(f; C) = kf cj'jk2H:

j=1

Функционал

mm

XX

J(f; C) = (f cj'j; f ci'i) =

j=1 i=1

mm

=2[12 X cicj('i; 'j) Xci(f; 'i)] + kfk2H:

Обозначим aij = ('i; 'j) и матрицу A = faijgmi;j и вектор b = fbigmi=1 bi = (f; 'i). Тогда

J(f; C) = 2[12(AC; C) + (b; C)] + kfk2:

58

Свойства матрицы A: 1. Матрица A симметрична.

2. Столбцы матрицы A, т.е. векторы j = f('i; 'j)gmi=1 линейно независимы. Действительно, предположим противное:

3. Матрица A положительна. Действительно, положим f = 0, тогда b = 0 и J(0; C) = (AC; C) 0: Собственные числа матрицы A действительны и неотрицательны:

01 2 m:

4.Матрица A положительно определенная, т.е. 1 > 0. Действительно, если 1 = 0 и собственный вектор C0 6= 0, то AC0 = 0. Так как столбцы матрицы A линейно независимы, то det A 6= 0 и вектор C0 = 0.

Задачу минимизации квадратичной функции

1

2(AC; C0) + (b; C)

мы решили в прошлом семестре: её минимум достигается на единственном векторе C , являющемся единственным решением системы

AC = b где A = f('i; 'j)gmi;j=1; b = f(f; 'i)gmi=1

Замечание: Если система элементов f'1; : : : ; 'mg ортонормирована, то A = E и решение задачи C = b.

Элемент feназывается аппроксимацией элемента f в гильбертовом пространстве H по системе линейно независимых элементов '1; '2; : : : ; 'm. Числа (f; 'i) называются коэффициентами Фурье элемента f в разложении элемента f по элементам '1; '2; : : : ; 'm:

6.2Ортогональные полиномы.

Исходя из системы линейно независимых элементов '1; '2; : : : ; 'n гильбертова пространства H, можно построить ортонормальную систему 1; 2; : : : ; n. Метод ортогонализации системы элементов f'igni=1 состоит в построении линейных комбинаций исходной системы элементов:

Рассмотрим функции 1; x; x2; : : : ; xn на (a; b) как линейно независимые элементы гильбертова пространства H со скалярными произведением

b

Z

(f; g) = f(x)g(x)p(x)dx;

a

где p(x)- весовая функция, p(x) 0:

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

1.приведены реккурентные формулы,

2.приведено их дифференциальное представление,

3.приведены дифференциальные уравнения второго порядка с переменными коэффициентами.

59

Полиномы Лежандра Pn(x):

Полиномы Чебышева Tn(x):

3. (1 x2)y00(x) xy0(x) + ny(x) = 0:

Полиномы Лаггера Ln(x), > 1.

Полиномы Эрмита Hn(x):

1

x 2 (1; 1); p(x) = e x2 ; (f; g) = R e x2 f(x)g(x)dx:

1

1. H0(x) = 1; H1(x) = 2x;

Hn+1(x) 2xHn(x) + 2nHn 1(x) = 0:

2. Hn(x) = ( 1)ex2 dn e x2 :

dxn

3. y00(x) 2xy0(x) + 2ny(x) = 0:

Общие свойство ортогональных полиномов: все нули полиномов простые и расположены на (a; b). Рассмотренные полиномы ортогональны, но не ортонормированы. Минимизация kf(x)

приводит к аппроксимации в гильбертовом пространстве H функции f 2 H по ортогональным полиномам

0; 1; : : : ; m.

60

6.3Метод наименьших квадратов (МНК).

Постановка задачи. Пусть выбрана система линейно независимых и непрерывных на [a; b] функций

Решение этой задачи сводится к решению задачи, поставленной и решенной в x1.

Образуем вектор-столбцы j = ('j(x1); : : : ; 'j(xn)) 2 Vn. Можно считать, что они линейно независимы. (В противном случае оставим только линейно независимые столбцы) Число линейно независимых столбцов не может превосходить размерности: m n.

Обозначим вектор (f1; f2; : : : ; fn) = f 2 Vn.

Для этого вектора требуется построить вектор C 2 Vm, такой что величина

(f; i). Вектор C , на котором достигается минимум k k22 единствен и является решением СЛАУ: AC =

b.

Для построения этой системы удобно сначала построить матрицу Q(n m) со столбцами 1; :::; m, затем транспонированную матрицу QT . Тогда матрица A = QT Q, а вектор b = QT f.

Предполагается, что fi являются измеренными, вычисленными (возможно неточно) значениями неко-

m

торой функции f(x) в узлах x1; :::; xn. Поэтому функция f~ = P Cj 'j(x), построенная по методу меньших

j=1

квадратов, является аппроксимацией функции f(x) по системе функций '1(x); '2(x); :::; 'm(x): Пример. Узлы x1; x2; x3; (n = 3) и значения f1; f2; f3

x1 = x2 h; x3 = x2 + h

0 1

1 h

Выберем функции '1(x) = 1; '2(x) = x x2; m = 2: Матрица Q = @1 0 A; 1 h

Пусть значения fi = f(xi) - точные значения функции f(x), имеющей на [x1; x3] непрерывные вторые производные и jf00(x)j M2. Оценим разность r(x) = f(x) f~(x).

f1 = f(x1) = f(x2) f0(x2)h + 12f00( 1)h2;

f2 = f(x2);

f3 = f(x3) = f(x2) + f0(x2)h + 12f00( 2)h2:

61

f~ = f(x2) + 16h2[f00( 1 + 2)] + (x x2)21h[2f0(x2)h + 12h2(f00( 2) f00( 1))] f(x) = f(x2) + f0(x2)(x x2) + 12f00( 3)(x x2)2:

jr(x)j 16h22M + 12h2M2 + 12M2h2 = 43M2h2:

6.4Аппроксимация элементов в пространствах Банаха.

Банахово пространство. Рассматривается линейное множество элементов. Для каждого элемента f этого множества определяется число kfk, удовлетворяющее условиям:

1.kfk 0; если kfk = 0, то f-нулевой элемент множества.

2.k fk = j j kfk

3.kf + 'k kfk + k'k:

Далее вводится метрика: (f; ') = kf 'k: Полученное метрическое пространство называется нормированным пространством. Если нормированное пространство оказывается полным, то оно называется пространством Банаха или банаховым пространством. Норма элемента kfk обозначается kfkB. В этом параграфе будем обозначать kzkB = kzk; z 2 B

Постановка задачи. Пусть заданы линейно независимые элементы банахова пространства B:

'1; '2; : : : ; 'm:

Образуем линейную оболочку этих элементов, т.е. множество элементов вида

m

X

ck'k:

k=1

Обозначим через c вектор (c1; c2; : : : ; cm); c 2 Vm:

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

Для заданного элемента f 2 B найти вектор c, такой что величина

m

X

J(f; c) = kf ck'kk

k=1

была бы минимальной.

Лемма. Функция J(f; c) многих переменных c1; c2; : : : ; cm непрерывна.

при k ck1 ! 0:

62

Замечание: ввиду эквивалентности норм в векторном пространстве Vm можно рассматривать любую векторную норму.

Теорема. Функция J(f; c) достигает своего минимального значения на ограниченном в пространстве Vm множестве.

Доказательство. Ясно, что J(f; c) ограничена снизу: J(f; c) 0: Если рассматривать любое ограниченное в Vm множество, то на нем непрерывная функция J(f; c) достигает своего минимального значения. Наша задача показать, что минимум J(f; c) достигается только на ограниченном множестве, что почти очевидно, так как при неограниченном росте kck значения J(f; c) стремятся к бесконечности.

m

P

1. Положим f = 0: Тогда J(0; c) = k ck'kk: В Vm рассмотрим сферу S1; т.е. множество векторов c с

k=1

нормой kck = 1: Так как множество S1 ограничено, то

inf J(0; c) = min J(0; c) = :

2. Вычислим величину r0 = и рассмотрим в Vm шар Шr0 с центром в начале координат и с радиусом r0: В этом шаре функция J(f; c) достигает своего минимума

min J(f; c) = : J(f; c) ; c 2 Шr0

Шr0

и в частности, при c = 0 J(f; 0) : А так как J(f; 0) = kfk; то в шаре Шr0 значение kfk :

3. Рассмотрим векторы c вне шара Шr0 : kck > r0: Для этих векторов

m

P

Но k ck'kk = J(0; c); и при kck > r0 величина J(0; c) > r0 = 2kfk:

k=1

Тогда J(f; c) > kfk; а так как kfk ; то мы получаем что вне шара Шr0 значения J(f; c) > : Следовательно, минимум функции J(f; c) достигается внутри шара Шr0 :

Замечания:

1.Единственность вектора c ; на котором достигается минимум функции J(f; c); не утверждается.

2.В общем случае нет методов построения вектора c ; т.е. нет методов построения аппроксимации элемента f 2 B линейными комбинациями элементов '1; '2; : : : ; 'm:

63

6.5Аппроксимация функций в пространстве C[a; b].

Вэтом частном случае банахова пространства верна теорема (теорема единственности вектора c ):

Теорема Хаара. Если функции '1(x); '2(x); : : : ; 'n(x) непрерывны и линейно независимы, то существу-

ет единственный вектор c 2 Vn; такой что

Взяв в качестве системы линейно независимых функций

'k(x) = xk; k = 0; 1; : : : ; n;

получаем: среди всех полиномов Qn(x); рассматриваемых на [a; b]; существует единственный полином Pn(x); такой что для заданной функции f 2 C[a; b]

min( max jf(x) Qn(x)j) = max jf(x) Pn(x):

Этот полином называется полиномом наилучшего равномерного приближения для функции f(x) и называется Pn(f; x).

В общем случае нет конструктивных методов построения полинома Pn(f; x):

Следующая теорема дает правило для распознавания полинома наилучшего равномерного приближения к функции f(x):

Теорема Чебышева об альтернансе.

Для того чтобы полином Pn(x) был полиномом наилучшего равномерного приближения к функции f(x); необходимо и достаточно, чтобы существовало (n + 2) точки a x0 < x1 < < xn < xn+1 b; такие что

Пример. [a; b] = [0; ]; f(x) = sin(x):

Рассмотрим полином P1(x) = 0 x + 12 : Разность

Ясно, что точки x0 = 0; x1 = 2 ; x2 = являются точками чебышевского альтернанса: f(x0) P1(x0) =

12 ; f(x1) P1(x1) = 12 ; f(x2) = 12 :

Следовательно среди всех полиномов первой степени полином P1(x) является полиномом наилучшего равномерного приближения к функции f(x) = sin(x); x 2 [0; ]:

64

6.6Полиномы Бернштейна.

Для функции f(x); удовлетворяющей на [a; b] условию Липшица:

можно указать простой метод построения полинома степени n с гарантированной оценкой

max jf(x) Pn(x)j:

x2[a;b]

Рассмотрим отрезок [a; b] = [0; 1] и функции Sm(x)

n

X

Sm(x) = kmCnkxk(1 x)n k k=0

При m = 0