Г.М. Кобельков - Курс лекций по численным методам (1160467), страница 5
Текст из файла (страница 5)
Процесс ортогонализацииПусть H — гильбертово пространство со скалярным произведением (·, ·) и индуцированной нормойpkf k := (f, f ).Пусть p : [a, b] → R, p > 0 на [a, b], p имеет лишь конечное количество нулей и ограничена на [a, b]. ТогдаH = {f : [a, b] → C : kf k < ∞}(f, g) :=Zbpf g dxa15будет гильбертовым пространством. Проверка аксиом предоставляется читателю.Определение. Функция p называется весом.Определение. Система векторов {fi } называется ортогональной, если (fi , fj ) 6= 0 при i = j и (fi , fj ) = 0при i 6= j.Лемма 2.12 (Процесс ортогонализации Грама – Шмидта). Пусть дано гильбертово пространство H.Пусть векторы f1 , .
. . , fn (fi ∈ H) линейно независимы. Построим из них ортогональную систему g1 , . . . , gn . Поскольку все векторы fi ненулевые, возьмём g1 = f1 . Пусть на k-м шаге уже построены векторыg1 , . . . , gk−1 . Покажем, как строить очередной вектор gk . Будем искать его так, чтобы hf1 , .
. . , fk i = hg1 , . . . , gk i.Имеем условия(gk , gi ) = 0, i = 1, . . . , k − 1.Попробуем найти этот вектор gk в видеgk = λ1 g1 + . . . + λk−1 gk−1 + fk .Используя условия ортогональности, получаем при всех i = 1, . . . , k − 1:0 = (gk , gi ) = λi (gi , gi ) + (fk , gi ),2откуда λi однозначно определяется, благо (gi , gi ) = kgi k > 0. Таким образом находим очередной вектор gk .Отметим, что матрица преобразования векторов {fi } в систему {gi } является унитреугольной.
Замечание. При необходимости полученные вектора gi можно пронормировать, но сама процедура ортогонализации того не требует.2.5.2. Ортогональные многочлены и их свойстваВ дальнейшем мы будем работать с пространством вещественнозначных функций на отрезке [a, b] со скалярным произведениемZb(f, g) = pf g dx,aпотому что именно оно чаще всего используется.Пример 5.1. Можно показать, что процедура ортогонализации2 стандартного базиса в R[x]6n , а именнодаёт многочлены Чебышёва, которыесистемы многочленов 1, x, x2 , .
. . , xn , с весовой функцией p = π√1−x2удовлетворяют рекуррентной формулеTn+1 = 2xTn − Tn−1 .Как мы потом увидим, наличие такой рекуррентной формулы для ортогональных многочленов не являетсячистой случайностью.Пример 5.2. Если взять p ≡ 1, то процедура ортогонализации даёт многочлены Лежандра.Пример 5.3. Если брать весовую функцию равной p = (1 − x)α (1 + x)β (α, β > − 12 ), то при ортогонализацииполучим так называемые многочлены Якоби.Тот базис, который получается ортогонализацией Грама – Шмидта (относительно некоторого скалярногопроизведения), будем называть системой ортогональных многочленов. Будем использовать для обозначениясистемы ортогональных многочленов букву P .
Итак, P0 , P1 , . . . — ортогональные многочлены.Теорема 2.13. Всякий ортогональный многочлен Pn степени n имеет ровно n простых корней на интервале (a, b). Предположим, что это не так, и на интервале (a, b) многочлен имеет только m < n нулей нечётнойкратности, обозначим эти нули через x1 , . . .
, xm . Тогда многочленG(x) := Pn (x)Qm (x), где Qm :=mYk=1(x − xk ),не меняет знак на [a, b], значит,I :=Zbap(x)G(x) dx 6= 0.С другой стороны, I = (Pn , Qm ) = 0, потому что m < n, а все многочлены степени меньше n ортогональны Pnпо построению ортогональной системы. Противоречие. 16Теорема 2.14. Для ортогональных многочленов выполнено рекуррентное соотношение вида(66)Pn+1 (x) = (x − αn )Pn − βn Pn−1 . По определению, Pn+1 ⊥ hP0 , . . .
, Pn i. Мы докажем, что процедуру ортогонализации можно вести с использованием этой рекуррентной формулы. Пусть ортогональные многочлены P0 , . . . , Pn уже вычислены. Многочлен Pn+1 , полученный по этой формуле, имеет степень n+1. Осталось проверить, что при подходящем выборекоэффициентов αn и βn он будет ортогонален все предыдущим.Рассмотрим три случая. Пусть сначала k < n − 1. Умножая выражение для Pn+1 скалярно на Pk , получим?(67)0 = (Pn+1 , Pk ) = (xPn , Pk ) − αn (Pn , Pk ) − βn (Pn−1 , Pk ).Поймём, почему получится нуль.
Действительно, последние два слагаемых равны нулю в силу ортогональностиP1 , . . . , Pn . Далее, (xPn , Pk ) = (Pn , xPk ) = 0, потому что deg(xPk ) < n.Пусть теперь k = n − 1. Добьёмся равенства нулю за счёт выбора βn :0 = (Pn+1 , Pn−1 ) = (xPn , Pn−1 ) − αn (Pn , Pn−1 ) −βn (Pn−1 , Pn−1 ) .| {z }|{z}=0(68)>0Итак, отсюда можно определить коэффициент βn , а именноβn =(xPn , Pn−1 ).(Pn−1 , Pn−1 )(69)Подставим теперь k = n.(70)0 = (Pn+1 , Pn ) = (xPn , Pn ) − αn (Pn , Pn ) −βn (Pn−1 , Pn ) .| {z }| {z }>0=0На этот раз можно однозначно определить αn :αn =(xPn , Pn ).(Pn , Pn )(71)Теорема доказана.
Следующего утверждения на лекции доказано не было. Однако, оно используется в доказательстве того факта, что нулисоседних ортогональных многочленов перемежаются (а этот факт был по крайней мере сформулирован на лекции).Утверждение 2.15. Коэффициенты βn рекуррентного соотношения положительны. Как видно из доказательства предыдущей теоремы, достаточно доказать, что(xPn , Pn−1 ) > 0.Для этого докажем лемму.Лемма 2.16. Пусть L : H → H — самосопряжённый оператор, и пусть fn := Ln−1 f1 , причём {fn } линейнонезависимы. Пусть векторы {gn } получены из системы {fn } процедурой ортогонализации.
Тогда(Lgn , gn−1 ) > 0при всех n.(72)В силу самосопряжённости оператора L имеемn−2n−2 XX(Lgn , gn−1 ) = (gn , Lgn−1 ) = gn , Lfn−1 +λk Lfk = gn , fn +λk fk+1 = (gn , fn ).k=1k=1|{z⊥∈gn}(73)Далее, пользуясь ортогональностью, можно заменить вектор fn на вектор gn (они отличаются на вектор из gn⊥ ,поэтому скалярное произведение не поменяется). Но (gn , gn ) > 0, то есть (gn , fn ) > 0, и лемма доказана. Теперь утверждение следует из леммы, применённой к (Lf )(x) = xf (x) и f1 ≡ 1. (n) Теорема 2.17. Пусть xi— все нули ортогонального многочлена Pn . Тогда нули Pn и Pn−1 перемежаются:(n)(n−1)(n)(n−1)(n−1)a < x1 < x1< x2 < x2< . .
. < xn−1 < x(n)(74)n < b,17то есть нули перемежаются. Подставим в рекуррентную формулу для многочлена Pn−1 нули многочлена Pn . Первое слагаемое вправой части пропадёт, останется(n)(n)Pn+1 (xi ) = −βn Pn−1 (xi ).(75)(n)Таким образом, поскольку βn > 0, по предположению индукции Pn−1 (xi ) 6= 0, а это значит, что многочлен Pn+1в нулях Pn имеет значения в точности противоположного знака, чем многочлен Pn−1 . Заметим, что многочлены, полученные процессом ортогонализации из стандартного базиса, имеют старший коэффициент, равный 1.(n)Следовательно, при x > xn многочлен Pn положителен и меняет знак при переходе через каждый из своихнулей.◦◦∗a∗∗∗◦◦∗∗∗◦∗◦∗∗∗∗◦∗∗b∗◦Осталось заметить, что знаки Pn+1 и Pn−1 в концах отрезка совпадают, откуда следует, что многочлен Pn+1(n)(n)имеет по нулю на интервалах (a, x1 ) и (xn , b).
Но это означает, что мы уже всё знаем про нули Pn+1 — ведьих ровно n + 1 на интервале (a, b). 2.6. Наилучшее приближение в гильбертовых пространствахПусть Gϕ ⊂ C — множество точек, из которых отрезок [−1, 1] виден под углом α > ϕ.Теорема 2.18 (Из Бахвалова, с. 243, без доказательства).
Пусть задана некоторая функция f , ипусть последовательность многочленовnmXjP m (x) =(76)amj xj=0удовлетворяет условиямkf − P m k 6иlm :=nmX maj 6 M · 2qm ,1.2mq > 0,(77)M > 1.(78)j=0Тогда функция f может быть аналитически продолжена в область Gϕ0 , где ϕ0 := π 2q+12q+2 .1iРассмотрим функцию f (x) = 1+25x2 . Она имеет полюса в точках ± 5 . Рассмотрим такие значения угла ϕ, прикоторых полюса попадают в область Gϕ . Поскольку функция заведомо не будет голоморфной в этой области,неравенство для коэффициентов не может выполняться, а это значит, что они имеют экспоненциальную скоростьроста (порядка не меньше чем 2qm . Это означает, что при вычислении погрешность будет очень велика, еслииспользовать стандартный базис в пространстве многочленов.Значит, нужно придумать такой способ хранения данных, чтобы числа получались не очень большие.
Если E — евклидово пространство, {ek } — ортонормированный базис в E, и f ∈ E, то имеет место равенствоПарсеваля:Xkf k2 =|fk |2 .(79)ИмеемnXk=1n2X|fk | 6 (n + 1)|fk |2 = (n + 1) · kf k ,т. е. получается оценка на рост порядкаk=1nPk=1√|fk | ∼ O( n).18(80)Далее следовал рассказ лектора про задачу интерполяции в двумерном случае, возникшую из практики (построение профилейдна Охотского моря).Имеется задача, в общем случае плохо решённая. Найти разумный способ приближения функции в квадрате при условии, чтосетка задана нерегулярно, то есть в квадрат накиданы случайные точки, и в них значения функции заданы.Из формулы оценки погрешности (20) следует, что чем меньше отрезок, на котором приближается функция,тем лучше. Поэтому лучше всего делать так: разбиваем отрезок приближения на несколько частей, и на каждомотрезке приближаем интерполяционным многочленом Лагранжа.
Есть только одна проблема: такая процедурагарантирует только непрерывность функции, потому что никаких условий на согласование производной в точкахстыка у нас нет.2.7. Сплайны2.7.1. Определение сплайновОпределение. Сплайном m-го порядка для функции f называется функция Sm (x) такая, что1◦ Sm (x) ∈ Cm−1 [a, b];2◦ Sm (xj ) = f (xj );3◦ На каждом отрезке [xk−1 , xk ] Sm является многочленом степени m, причём выполнено условие гладкостина концах отрезка до порядка m − 1 включительно.Посчитаем, насколько однозначно задан сплайн. Пусть у нас N отрезков, тогда неизвестных коэффициентовмногочленов имеется N (m+1) штук. Условия гладкости дают (N −1)(m−1) уравнение (совпадение производныхво всех внутренних точках), и ещё 2N уравнений мы получаем из того, что знаем значения многочленов в концахвсех отрезков.
Таким образом, свободных неизвестных останется N m + N − N m + N + m − 1 − 2N = m − 1 штук.Заметим, что при m = 1 сплайн определён однозначно и даёт просто ломаную, соединяющую точки (xi , f (xi )).Рассмотрим функционалZbIk (s) := (s(k) )2 dx.(81)aРассмотрим класс функций, имеющих кусочно непрерывную производную на отрезке [a, b] и в узлах принимающие заданные значения.
Обозначим этот класс K1 . Сплайны доставляют экстремум функционалу I1 наRbRbданном классе. Имеем I1 (s+δ) = I1 (s)+2 s′ δ ′ dx+ (δ ′ )2 dx. Всё будет хорошо, если мы покажем, что второе слаaaгаемое обнуляется. Интегрируя по частям, получаем, чтоRbs′ δ ′ dx = 0 тогда и только тогда, когдаaRbs′′ δ dx = 0.a′′Поскольку хочется, чтобы это было верно для всех δ, то по лемме Дюбуа – Реймона получаем, что s = 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
