Численные методы. Соснин (2005) (1160462), страница 13
Текст из файла (страница 13)
Докажем оценку на первую производную. Для этого снова фиксируем некоторое i и произвольное x из сегмента [xi−1 ; xi ]. Обозначим r(x) = f (x) − S3 (x) и заметим, что, согласно построениюсплайна, r(xi−1 ) = r(xi ) = 0. Так как r(x) — дважды дифференцируемая функция, то мы можемприменить теорему Ролля:∃ξ ∈ [xi−1 ; xi ] : r0 (ξ) = 0.Теперь применим в тождестве|r0 (x)| = |r0 (x) − r0 (ξ)|формулу Лагранжа:|r0 (x)| = |r00 (ζ)(x − ξ)| 6 |r00 (ζ)|h = |f 00 (ζ) − S300 (ζ)|h,ζ ∈ [xi−1 ; xi ].Согласно только что доказанному неравенству для вторых производных,∀x ∈ [a; b] |S300 (x) − f 00 (x)| 6 M4 h2 .Отсюда следует, что ∀x ∈ [xi−1 ; xi ] |S 0 (x) − f 0 (x)| 6 M4 h2 · h = M4 h3 .Взяв максимум по всем сегментам, получим неравенство для норм:||f 0 (x) − S 0 (x)||C[a; b] 6 M4 h3 .Т.
е. мы доказали второе утверждение теоремы.(3). Теперь докажем оценку на погрешность приближения сплайном самой функции. Точно также возьмем произвольное x из интервала (xi−1 ; xi ). Определим на этом сегменте вспомогательнуюфункцию:g(t) = f (t) − S3 (t) − K(t − xi−1 )(t − xi ),66Глава 4. ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИЙгде K — константа. Можно подобрать K так, чтобы g(x) = 0 :f (x) − S3 (x) − K(x − xi−1 )(x − xi ) = 0.Отсюда получаем K =f (x) − S3 (x), поэтому(x − xi−1 )(x − xi )g(t) = f (t) − S3 (t) −f (x) − S3 (x)(t − xi−1 )(t − xi ).(x − xi−1 )(x − xi )Заметим, что, согласно построению сплайна, g(xi−1 ) = g(xi ) = 0.
Таким образом, функция g(t)дважды дифференцируема на [a; b] и обращается в нуль в трех точках. Дважды применив теоремуРолля, получим, что существует такая точка ξ, что g 00 (ξ) = 0.g 00 (t) = f 00 (t) − S300 (t) − 2K, поэтомуg 00 (ξ) = 0 ⇐⇒ f 00 (ξ) − S300 (ξ) − 2f (x) − S3 (x)=0(x − xi−1 )(x − xi )Отсюда выводится выражение для погрешности в точке x :f (x) − S3 (x) =f 00 (ξ) − S300 (ξ)(x − xi−1 )(x − xi ).2Взяв обе части равенства по модулю, получим цепочку неравенств:|f (x) − S3 (x)| =M4 h 2 · h · h1 00|f (ξ) − S300 (ξ)||(x − xi−1 )(x − xi )| 66 M4 h 4 .22В силу произвольности выбора x и i это верно для любого x ∈ [a; b].
Из этого следует неравенстводля нормы:||f (x) − S3 (x)||C[a; b] 6 M4 h4 .Это неравенство доказывает первое утверждение теоремы.Теорема полностью доказана.Следствие. При n −→ ∞ последовательность сплайнов S3 (x), построенных для соответствующихn, сходится к функции f (x) по норме || · ||C[a; b] .4.2Наилучшее приближение табличной функцииВ предыдущих разделах были рассмотрены примеры интерполяции функции f (x) многочленамиЛагранжа и сплайнами. ИнтерполянтаΦ(x) = a0 ϕ0 (x) + a1 ϕ1 (x) + . .
. + am ϕm (x).обычно содержала m+1 неизвестный коэффициент, которые определялись из n+1 условия совпаденияс табличными значениями (m = n при интерполяции многочленами и m > n — сплайнами).Теперь обсудим случай, когда m < n (узлов, в которых известно значение функции, больше, чемнеизвестных коэффициентов). В этом случае возникает понятие наилучшего приближения: мыотказываемся от требования совпадения значения интерполянты и табличной функции, а требуемминимизировать некоторый функционал от, к примеру, вектора погрешностей в узлах сетки:~r = (Φ(x0 ) − f (x0 ), Φ(x1 ) − f (x1 ), . . . , Φ(xn ) − f (xn )) ,4.2. НАИЛУЧШЕЕ ПРИБЛИЖЕНИЕ ТАБЛИЧНОЙ ФУНКЦИИ67где x0 , .
. . , xn — точки, в которых нам задана функция f (x). В качестве функционала рассмотримнорму этого вектора, которую можно задавать по-разному:! 21nX||~r||(1) =(Φ(xi ) − f (xi ))2 ;i=0||~r||(2)=max |Φ(xi ) − f (xi )|.iВ каждом случае мы пытаемся подобрать коэффициенты ai в задании Φ(x) так, чтобы минимизировать эту норму. Эту задачу называют поиском наилучшего среднеквадратичного приближения (а метод ее решения — методом наименьших квадратов) или поиском наименьшегоравномерного приближения соответственно. Приведем пример решения такой задачи.Пример 4.2.Пусть функция f (x) задана в точках x0 , x1 = x0 + h, x2 = x0 + 2h (то есть n = 2), а приближениемее будет функцияΦ(x) = a0 ϕ0 (x) + a1 ϕ1 (x)— m будет равно 1.
Функции ϕ0 (x) и ϕ1 (x) будут полиномами — степени 0 и 1 соответственно:ϕ0 (x) = 1; ϕ1 (x) = x − x1 .Таким образом, Φ(x) = a0 + a1 (x − x1 ), и для ~r будет верно представление:~r = (a0 − a1 h − f0 , a0 − f1 , a0 + a1 h − f2 )T .Минимизировать будем норму ||~r||(1) , а точнее, ее квадрат:||~r||2(1) = F (a0 , a1 ) =2Xri2 = (a0 − a1 h − f0 )2 + (a0 − f1 )2 + (a0 + a1 h − f2 )2 .i=0Необходимым условием экстремума этой, очевидно, дифференцируемой функции будет равенствонулю всех частных производных:∂F (a0 , a1 )(= 0;2(a0 − a1 h − f0 ) + 2(a0 − f1 ) + 2(a0 + a1 h − f2 ) = 0;∂a0⇐⇒⇐⇒2(a0 − a1 h − f0 )(−h) + 2h(a0 + a1 h − f2 ) = 0. ∂F (a0 , a1 ) = 0.∂a1f0 + f1 + f2(; a0 =3a0 = f0 + f1 + f2 ;3⇐⇒f2 − f02a1 h2 = f2 h − hf0 . a1 =.2h— это единственные возможные решения, и, как несложно проверить, именно при таких значенияхa0 , a1 функция F (a0 , a1 ) будет достигать минимума.
Теперь запишем получившееся выражение дляинтерполянты:f0 + f1 + f2f2 − f0Φ(x) =+(x − x1 ).32hОценим приблизительно погрешность нашего приближения. Сначала посчитаем ||~r||2(1) :||~r||2(1) =nXri2 = (a0 − a1 h − f0 )2 + (a0 − f1 )2 + (a0 + a1 h − f2 )2 =i=0==f0 + f1 + f2f2 − f0−− f032162 (−f0+ 2f1 − f2 )2 +1= (f0 − 2f1 + f2 )( 36+19132 (f0+136 )2+f0 + f1 + f2− f13− 2f1 + f2 )2 +=162 (−f0(f0 − 2f1 + f2 )2.62+f0 + f1 + f2f2 − f0+− f232+ 2f1 − f2 )2 =2=68Глава 4.
ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИЙДопустим, что f (x) ∈ C 2 [x0 ; x2 ]. Тогда запишем f0 и f2 по формуле Тейлора:h2,2h2f2 = f (x1 + h) = f1 + f10 h + f 00 (ζ) ,2f0 = f (x1 − h) = f1 − f10 h + f 00 (ξ)ξ ∈ [x0 ; x1 ];ζ ∈ [x1 ; x2 ].Таким образом,||~r||2(1)Обозначим M2 =21(f 00 (ξ) + f 00 (ζ))2 h4h20000==(f (ξ) + f (ζ)).6224max |f 00 (x)|, тогда получим такое неравенство:x∈[x0 ; x2 ]||~r||2(1) 64M22 h4h4= M22 .246Итак, в случае дважды дифференцируемой функции для нормы вектора погрешности справедливатакая оценка:M2 h 2||~r||(1) 6 √6— это, в общем, неплохое приближение.Теперь перейдем к более общей постановке.Наилучшее приближение в гильбертовом пространствеpПусть H — евклидово пространство функций с нормой ||f || = hf, f i, а ϕi (i = 0, n)— его линейнонезависимые элементы.
Нашей задачей будет поиск наилучшего приближенияϕ = c0 ϕ0 + . . . + cn ϕn ,ci ∈ R,для элемента f ∈ H. Оценкой точности будет служить величина погрешности ||f − ϕ||.Определение. Элемент ϕ,e доставляющий минимум этой норме (для которого верно равенствоmin ||f − ϕ|| = ||f − ϕ||),eназывается элементом наилучшего приближения.ϕПокажем, что такой элемент существует и единствен. В качестве примера можно взять пространствоL2 [a; b] (пространство функций, интегрируемых со своими квадратами) и в нем некоторую функциюf.
В качестве скалярного произведения берут обычное в L2 :1Zbhg, f iL2 =Zbf (x)g(x) dx,соответственно ||f ||L2 =a22f (x) dx .aПродолжим рассуждения в общем виде. Наша задача — это минимизировать ||f − ϕ||, подобравсоответствующую функцию ϕ. Приведем эту норму (будем работать с ее квадратом) к более удобномувиду:*+nnXX2||f − ϕ|| = hf − ϕ, f − ϕi = f −cl ϕl , f −ck ϕk == hf, f i −nXcl hϕl , f i −l=0= ||f ||2 − 2nXl=0l=0nXk=0ck hϕk , f i +k=0cl hϕl , f i +n XnXl=0 k=0n XnXl=0 k=0cl ck hϕl , ϕk i =cl ck hϕl , ϕk i =4.2. НАИЛУЧШЕЕ ПРИБЛИЖЕНИЕ ТАБЛИЧНОЙ ФУНКЦИИ= { Введем обозначения= ||f ||2 − 2nXl=0cl fl +Rb fl= hϕl , f i = akl= hϕk , ϕl i =n XnX69f (x)ϕl (x) dx;aRb} =ϕk (x)ϕl (x) dx.ack cl akl =l=0 k=0 c = (c0 , c1 , .
. . , cn )T ;= { Обозначимf = (f0 , f1 , . . . , fn )T ; } =A = (akl ).= ||f ||2 − 2 c, f + hAc, ci = ||f ||2 + F (c).Соединив первое и последнее равенство, получим:||f − ϕ||2 = ||f ||2 + F (c).(4.18)Таким образом, задача о минимизации ||f − ϕ|| свелась к задаче минимизации функции F (c) отвектора переменных c.Из определения матрицы A следует, что она симметрична. Покажем, что она положительно определена, то есть∀c 6= 0 hAc, ci > 0.Если взять в равенстве (4.18) f ≡ 0, то получим, что hAc, ci = ||ϕ||2 > 0.
Предположим, чтосуществует вектор y 6= 0 такой, что hAy, yi = 0. Но это будет означать, что ||ϕ|| = 0. Так как ϕ —линейная комбинация линейно независимых элементов ϕi , то это возможно тогда и только тогда, когдаэта комбинация тривиальна — то есть yi = 0 для всех i. Отсюда делаем вывод, чтоy = 0 =⇒ ∀c 6= 0hAc, ci > 0.Таким образом, матрица A положительно определена. Это позволяет воспользоваться следующейтеоремой.Теорема 4.4. Пусть даны матрица A такая, что A = AT > 0, и f — некоторый вектор (соответствующей размерности). Тогда у функцииF (c) = hAc, ci − 2 f , cвекторного переменного c точка минимума существует и единственна, причем элемент c реализует этот минимум тогда и только тогда, когда он является решением системы:Ac = f .(4.19)Доказательство.
Сначала докажем утверждение об эквивалентности.Достаточность. Пусть c — решение системы (4.19). Покажем, что для любого ненулевого вектораv F (c + v) > F (c) :F (c + v) = hA(c + v), c + vi − 2 f , c + v = hAc, ci + hAc, vi + hAv, ci + hAv, vi − 2 f , c − 2 f , v == {A = AT =⇒ hAc, vi = hAv, ci} = F (c) + hAv, vi + 2 v, Ac − f = F (c) + hAv, vi .Так как A > 0, то hAv, vi > 0. Это означает, что c — точка минимума .
Достаточность доказана.Необходимость. Пусть c — точка минимума F (c). Фиксируем произвольный ненулевой векторy и положим v = λy (λ — параметр). Тогда, согласно проведенным в доказательстве достаточностипреобразованиям,F (c + v) = F (c) + hAv, vi + 2 v, Ac − f = F (c) + λ2 hAy, yi + 2λ y, Ac − f .(4.20)70Глава 4. ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИЙОбозначим выражение, стоящее в правой части равенства, за g(λ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
