Г.М. Кобельков - Курс лекций по численным методам (1160467), страница 4
Текст из файла (страница 4)
Можно доказать это немного изящнее: ∆ := inf kf − vk. Выберем последовательность vn , дляv∈Vкоторой kf − vn k ց ∆. Можно считать, что последовательность kvn k ограничена, так как для достаточнобольших n будет выполненоkvn k 6 kf k + kvn − f k 6 kf k + ∆ + 1.(46)Выберем из неё сходящуюся подпоследовательность (так как ограниченное множество в Rn предкомпактно). Еёпредел и есть искомый элемент.Определение. Пространство R называется строго нормированным, если из того, что kf + gk = kf k + kgkследует, что элементы f и g пропорциональны.Теорема 2.6. В строго нормированном пространстве элемент наилучшего приближения единствен. Допустим, что функция F достигает минимума в двух точках c′ и c′′ .
Рассмотрим 1 ∆ ∆X c′j + c′′j 1 XX′′′ 6 f −gf−cg+f−cg+ .(47)=jjjjj 22222Но в нашем случае имеет место равенство, потому что этоPэлемент наилучшегоприближения. Поскольку проPстранство является строго нормированным, получаем f − c′j gj = α f − c′′j gj . Если α = 1, то всё доказано.P ′(cj −αc′′j )gjА если α 6= 1, то f =, то есть f раскладывается по базису {gj }, а разложение по базису всегда1−αоднозначно. Задача 2.1. Гильбертово пространство является строго нормированным.Получим более или менее явный вид для коэффициентов ci . Рассмотрим функцию2 XXXΦ(c) = f −cj g j = f −cj g j , f −cj g j .Можно доказать, что у функции Φ только один экстремум, являющийся минимумом.Задача 2.2.
Доказать этот факт.∂ΦНайдём коэффициенты, используя необходимое условие экстремума ∂c= 0. Дифференцируя, имеемk−gk , f −X Xci g i + f −ci gi , −gk = 0,12k = 1, . . . , n.(48)Положим G = (gij ), где gij = (gi , gj ). Получаем систему линейных уравнений с матрицей G и некоторымстолбцом свободных членов.Матрица G называется матрицей Грама системы функций g1 , . . . , gn .Утверждение 2.7. Матрица G является положительно определённой.PP2 Имеем k cj gj k = (c · g, c · g) =ci cj gij = (Gc, c) > 0.
При этом если выражение справа равно нулю,i,jто и норма слева равна нулю, а это означает, что либо векторы g1 , . . . , gn линейно зависимы, что невозможно,либо c = 0. Это и означает положительную определённость. Однако число обусловленности матрицы Грама для многочленов gj = xj−1 на отрезке [−1, 1] растёт оченьбыстро с ростом n. Именно,√( 2 + 1)2nλmax (G)∼ const ·, b > 0.λmin (G)nb2.4.2.
Наилучшее приближение многочленами. Чебышёвский альтернансТеперь мы будем рассматривать пространство непрерывных функций C[a, b] с чебышёвской нормой. В качеnPстве базисных векторов выберем многочлены: Qn (x) =ak xk .k=0Через Q0n обозначим многочлен наилучшего равномерного приближения функции f . Также будем обозначать∆n (f ) := f − Q0n 6 kf − Qn k , Qn ∈ R[x]6n ,(49)µ := min |f (xi ) − Qn (xi )| .iТеорема 2.8 (Валле – Пуссен). Пусть существуют n + 2 точки x0 < . . .
< xn+1 , для которыхsgn f (xi ) − Qn (xi ) · (−1)i = const .Тогда ∆n (f ) > µ. Если µ = 0, то доказывать нечего. Пусть теперь µ > 0. Допустим, что µ > ∆n (f ). Рассмотримsgn f (x) − Qn (x) − f (x) − Q0n (x) .|{z} |{z}D(50)(51)D0Так как |D0 | 6 ∆n (f ), по нашему предположению при x = xi имеем |D| > |D0 |. Значит, при вычитании D0 изD знак не поменяется, иsgn f (xi ) − Qn (xi ) − f (xi ) − Q0n (xi ) = sgn f (xi ) − Qn (xi ) .(52)Поэтому многочлен D − D0 = Qn (x) − Q0n (x) имеет n + 1 перемену знака, а с другой стороны, имеет степень невыше n. Значит, Qn ≡ Q0n , поэтому ∆n (f ) = max |f (x) − Q0n (x)| > µ = min |f (xi ) − Q0n (xi )|.
Определение. Точки x0 , . . . , xn+1 называются точками чебышёвского альтернанса.Теорема 2.9 (Чебышёв). Многочлен Qn является многочленом наилучшего равномерного приближенияна отрезке [a, b] тогда и только тогда, когда на этом отрезке существует n + 2 точки xk такие, чтоf (xk ) − Qn (xk ) = α · (−1)k kf − Qn k ,α ∈ {±1} .(53)⇐ Пусть {xk } — данные точки. Пусть L := kf − Qn k. Так как в точках xk достигается норма разности, тоL = µ (в самом деле, |f (xk ) − Qn (xk )| = |α| · kf − Qn k = kf − Qn k = L). Далее, имеемL = µ 6 ∆n (f ) 6 kf − Qn k = L.(54)Значит, L = ∆n (f ). Следовательно, Qn — многочлен наилучшего равномерного приближения.⇒ Пусть Qn — многочлен наилучшего равномерного приближения.
Рассмотрим ближайшую к a точку, вкоторой достигается норма разности, т. е. положимy1 := min {x ∈ [a, b] : |f (x) − Qn (x)| = L} .(55)Для определённости f (y1 ) − Qn (y1 ) = L. Теперь положим y2 := min {x ∈ [y1 , b] : f (x) − Qn (x) = −L}, и так далее.Если мы набрали m := n + 2 таких точек, то мы победили. Допустим теперь, что m < n + 2. По непрерывности13при k = 2, .
. . , m найдутся точки zk−1 ∈ [yk−1 , yk ] такие, что |f (x) − Qn (x)| < L при x ∈ [zk−1 , yk ). Положимz0 := a, zm = b.m−1QРассмотрим многочлен v(x) :=(zj − x). Рассмотрим отрезок [z0 , z1 ]. Имеем v(x) > 0 при x ∈ [z0 , z1 ).j=1Рассмотрим многочлен Qdn (x) := Qn (x) + dv(x), где d > 0. Мы знаем, что f (x) − Qn (x) > −L на отрезке [z0 , z1 ].Значит, при достаточно малом d будем иметь f (x) − Qdn (x) > −L на [z0 , z1 ). Кроме того, |f (z1 ) − Qdn (z1 )| == |f (z1 ) − Qn (z1 )| < L.
Значит, на всём отрезке [z0 , z1 ] имеем |f (x) − Qdn (x)| < L. Подбирая подходящее значениеd для каждого отрезка [zk−1 , zk ] и выбирая минимум по всем таким d, получаем, что многочлен Qdn доставляетлучшее приближение, чем Qn . Противоречие. Кажется, следующую теорему мы уже доказывали в общем случае.
Во всяком случае идея ровно та же самая — рассмотрение полусуммы. Кому-то может показаться, что общее доказательство не проходит, так как пространство непрерывных функцийна отрезке не гильбертово. Но мы рассматриваем только значения в узлах, поэтому фактически имеем дело с конечномернымпространством, которое, ежу ясно, строго нормированное.Теорема 2.10. Многочлен наилучшего равномерного приближения степени n для функции f единственный.
Допустим, нашлось два многочлена P и Q. Тогда f − P + Q = f − P + f − Q 6 1 kf − P k + 1 kf − Qk = ∆n (f ).(56)22222 22Значит, R := P +Qтоже является многочленом наилучшего равномерного приближения. Пусть x0 , . . . , xn+1 —2точки альтернанса многочлена R. Тогдаf (xi ) − P (xi ) + Q(xi ) = ∆n (f ),(57)2то естьНо так как f (xi ) − P (xi ) + f (xi ) − Q(xi ) = 2∆n (f ). f (xi ) − P (xi ) + f (xi ) − Q(xi ) 6 |f (xi ) − P (xi )| + |f (xi ) − Q(xi )| 6 ∆n (f ) + ∆n (f ),(58)(59)откуда следует, что |f (xi ) − P (xi )| = |f (xi ) − Q(xi )|.
Но модули можно убрать, ибо, если бы эти выраженияотличались знаком, то в левой части равенства (58) получился бы нуль. Таким образом, получаем P (xi ) = Q(xi ),то есть два многочлена степени n совпадают в n + 2 точках. Значит, P ≡ Q. Пусть задана функция f и пусть Q0n — её МНРП.Утверждение 2.11. Q0n совпадает с некоторым многочленом Лагранжа по n + 1 точке для функции f . В самом деле, если Q0n — МНРП, то по теореме Чебышёва получаем, что существуют n + 2 точкиальтернанса.
Значит, у разности f (x) − Q0n (x) имеется хотя бы n + 1 нуль. Итак, существуют точки ξ1 , . . . , ξn+1 ,для которых имеем Q0n (ξi ) = f (ξi ). Это и требуется доказать. А раз Q0n — это многочлен Лагранжа, то мы можем применить рассуждения из доказательства теоремы 2.1,и заявить, что имеет место равенствоf (x) − Q0n (x) =f (n+1) (ξx )ωn+1 (x),(n + 1)!(60)где ωn+1 (x) = (x − ξ1 ) · . . . · (x − ξn+1 ).
А поскольку аналогичная формула верна, вообще говоря, для любогомногочлена Лагранжа, а Q0n — МНРП, то имеет место оценкаmax f (n+1) (ξx )ξf − Q0n 6|ωn+1 (x)| .(61)(n + 1)!Ну а теперь справа можно выбрать в качестве ωn+1 нули многочлена Чебышёва, для которого известна оценка.Тогда получим такое неравенство:n+1 (n+1) 1b−af − Q0n 6 f··.(62)(n + 1)! 2n2Используя теперь то свойство, что многочлены Чебышёва наименее уклоняются от нуля, можно получить иобратную оценку: (n+1) n+1(x) 1b−af − Q0n > min f· n·.(63)(n + 1)!22142.4.3. Примеры многочленов наилучшего приближенияПример 4.1. Пусть мы приближаем непрерывную функцию на отрезке [a, b] многочленом нулевой степени.Пусть M := max f , m := min f .
Тогда, очевидно, Q(x) = M+m2 , а точками альтернанса (их будет 2 штуки) будуткакие-нибудь точки достижения максимума и минимума.Пример 4.2. Пусть нам дана непрерывная функция f , выпуклая (вверх) на некотором отрезке [a, b]. Тогдаеё наилучшим линейным приближением будет функция Q(x) = kx + c, где k = f (a; b). Точки a и b будут точкамиальтернанса, так как экстремум функции на отрезке может быть только один. Если функция f дифференцируема, то найдётся такая точка ξ (третья точка альтернанса), что касательная y2 (x) к графику функции fпараллельна прямой y1 (x) = k(x − a) + f (a). Число c выбирается так, что график Q(x) проходит в точности по2 (x)середине между графиками y1 (x) и y2 (x), то есть Q(x) = y1 (x)+y.2Пример 4.3. Рассмотрим функцию, у которой очень много нулей, например, f (x) = sin 10πx.
Тогда Q03 ≡ 0.Действительно, взяв нулевой многочлен, мы без труда найдём 5 точек альтернанса. Применяя теорему Чебышёва, получаем, что Q03 — МНРП.Пример 4.4. Будем приближать многочлен f (x) := x7 с помощью многочлена Q06 . Нам нужно минимизировать норму многочлена (7-й степени) g := f − Q06 . Ежу ясно, что для этой цели нужно взять приведённыймногочлен Чебышёва, потому что он наименее уклоняется от нуля.Задача 2.3.
Показать, что если приближать (на симметричном отрезке) чётную функцию, то МНРПбудет чётной функцией. Аналогично, если мы приближаем нечётную функцию, то МНРП будет нечётнойфункцией.Пример 4.5. Рассмотрим предыдущий пример, но пусть теперь нам нужно приблизить многочлен x7 многочленом 5-й степени на отрезке [−1, 1] и оценить погрешность приближения.
Если всё написать в лоб по тойформуле, которую мы вывели, то получается такая оценка:6f − Q05 6 7! · 2 = 7 .116! · 232(64)Но можно схитрить. За счёт того, что мы приближаем нечётную функцию, мы можем считать, что на самомделе мы приближаем многочленом Q06 , ибо он всё равно на самом деле окажется степени на единицу меньшев силу сформулированной задачи (много ли мы знаем многочленов 6-й степени, которые являются нечётнымифункциями?). Значит, Q05 = Q06 , а для многочленов 6-й степени оценка точнее:7f − Q06 6 7! · 2 = 1 .7! · 21364(65)Видим, что оценка получается лучше в 14 раз.2.5. Ортогональные системы и их свойства2.5.1. Гильбертовы пространства.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
