Численные методы. Соснин (2005) (1160462), страница 12
Текст из файла (страница 12)
Разобьем этот отрезок на частичные сегменты, обозначив узлы сетки за xi :a = x0 < x1 < . . . < xn = b.Считая, что нам известны только значения f (xi ) = fi , будем приближать нашу функцию функциейSm (x), которая на разных сегментах состоит из полиномов степени m :Sm (x) = Pim (x) = ai0 + ai1 x + . . . + aim xm ,x ∈ [xi−1 ; xi ], i = 1, n.Потребуем, чтобы в узлах сетки (в точках xi ) функция Sm (x) была непрерывна вместе с l-й производной:(l)(l)Pim (xi ) = P(i+1)m (xi ), l = 0, m − 1, i = 1, n − 1.(4.5)Такая функция будет называться сплайном степени m на [a; b].Легко заметить, что для задания функции Sm (x) нам необходимо задать по m + 1 коэффициентудля каждого полинома — всего n(m+1) штук.
Однако, условия (4.5) дают только (n−1)m уравнений.4.1. ИНТЕРПОЛИРОВАНИЕ КУБИЧЕСКИМИ СПЛАЙНАМИ61Чтобы количество уравнений совпадало с количеством неизвестных, введем дополнительные условияна Sm (x) : равенство с функцией f (x) на концах сегментов:Sm (xi ) = f (xi ),i = 0, n.Это n + 1 условие позволяет нашему сплайну называться интерполяционным.Теперь не хватает всего m − 1 условия. Обычно их некоторым образом «распределяют» междуконцами отрезка [a; b], потребовав там гладкость, дифференцируемость, или что-то другое.В итоге, для определения коэффициентов aij мы получим систему из n(m + 1) уравнений — частоиз нее можно однозначно определить сплайн-функцию Sm (x).Кубические сплайныВ курсе «Численные методы» в III семестре рассматривались кубические сплайны (m беретсяравным 3), причем, как было показано, удобнее представлять полиномы на i-м сегменте следующимобразом:cidiS3 (x) = Pi3 (x) = ai + bi (x − xi ) + (x − xi )2 + (x − xi )3 .(4.6)26Таким образом, если делить отрезок [a; b] на n частей, то для определения неизвестных коэффициентов необходимо брать как минимум 4n уравнений.
Они получаются следующим образом:• n + 1 условие равенства исходной функции и сплайна в узлах сетки:S3 (xi ) = f (xi ),i = 0, n.• 3(n − 1) условия из требования непрерывности вместе со второй производной:(l)(l)Pi3 (xi ) = P(i+1) 3 (xi ),i = 1, n − 1, l = 0, 2.• 2 условия из требования нулевой кривизны на концах отрезка:S300 (a) = S300 (b) = 0.Примечание. Далее кубическим сплайном для функции f (x) мы будем называть сплайн, удовлетворяющий именно этим условиям.Было показано, что из этих условий можно получить такую систему для нахождения коэффициентов ci :fi+1 − fifi − fi−1hi ci−1 + 2(hi + hi+1 )ci + hi+1 ci+1 = 6−, i = 1, n − 1;(4.7)hi+1hic0 = cn = 0,где fi — значения функции на концах сегментов, а hi — длина сегмента [xi−1 ; xi ].
Это система с трехдиагональной матрицей, которая решается методом прогонки. После этого оставшиеся коэффициентынаходятся просто:ci − ci−1;di =hici hih2ifi − fi−1b=−d+, i = 1, n;ii26hiai = fi .Процесс построения сплайна достаточно трудоемкий (нужно решать систему уравнений, причеминогда большой размерности), причем при малейшем изменении значений функции все коэффициентыприходится пересчитывать заново.62Глава 4. ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИЙСходимость процесса интерполяции кубическими сплайнамиНашей задачей будет показать, что наш процесс интерполяции сходится с увеличением n — то естьпо мере увеличения количества узлов сетки сплайн приближает функцию f (x) все лучше.Сначала введем некоторые обозначения и определения.
МножествоΩn = {xi = ai + h, i = 0, n, h =b−a}nназовем равномерной сеткой на отрезке [a; b]. Доказывать сходимость мы будем именно на равномерной сетке — это проще.Введем две новые нормы (требовать соответствие аксиомам не будем: оно тут не нужно):||g(x)||C[a; b]=||gi ||C(Ωn )=max |g(x)|;x∈[a; b]max |gi |— норма на равномерной сетке.i=0, nНаконец, особо обозначим максимум четвертой производной нашей функции:M4 = ||f (4) (x)||C[a; b] .Прежде чем доказать основную теорему, сформулируем и докажем лемму об оценке погрешности|f 00 (x) − S 00 (x)| в узлах сетки.Лемма. Пусть f (x) ∈ C 4 [a; b], а S3 (x) — соответствующий ей кубический сплайн, построенныйна равномерной сетке Ωn .
Тогда справедливо неравенство:||f 00 (xi ) − S300 (xi )||C(Ωn ) 63M4 h 2 .4(4.8)Доказательство. Из (4.6) легко получить, что S300 (xi ) = ci . Обозначим zi = S300 (xi ) − f 00 (xi ), в этомслучае ci = zi + f 00 (xi ). Теперь заметим, что систему (4.7) можно переписать следующим образом:ci−1 + 4ci + ci+1 = 6fxx,i , i = 1, n − 1;(4.9)c0 = cn = 0,i +fi−1— вторая разностная производная для f (x).где fxx,i = fi+1 −2fh2Подставив только что полученное выражение для ci в систему, получим:zi−1 + 4zi + zi+1 = ψi , i = 1, n − 1;z0 = zn = 0,0000где ψi = 6fxx,i − (fi−1+ 4fi00 + fi+1).По-другому первое уравнение можно переписать так:4zi = −zi−1 − zi+1 + ψi .Взяв значения по модулю, получим такую цепочку неравенств:4|zi | 6 |zi−1 | + |zi+1 | + |ψi | 6 2 max |zi | + max |ψi |.i=0, ni=1, n−1Теперь возьмем максимум от |zi | по всем узлам сетки и получим выражение для норм (учитывая,что z0 = zn = 0):4||zi ||C(Ωn ) 6 ||2zi ||C(Ωn ) + ||ψi ||C(Ωn ) .Отсюда следует, что||zi ||C(Ωn ) 61||ψi ||C(Ωn ) .2(4.10)4.1.
ИНТЕРПОЛИРОВАНИЕ КУБИЧЕСКИМИ СПЛАЙНАМИ63Таким образом, для доказательства (4.8) достаточно показать, что||ψi ||C(Ωn ) 63M4 h 2 .2Для этого распишем выражение для ψi :0000ψi = 6fxx,i − (fi−1+ 4fi00 + fi−1) = 6(fxx,i − fi00 ) − h20000fi−1− 2fi00 + fi+1.2hДробь представляет собой вторую разностную производную функции f 00 (x).
Тогда получим, что00ψi = 6(fxx,i − fi00 ) − h2 fxx,i.(4.11)Теперь рассмотрим отдельно составляющие этой разности:fxx,i − fi00 =11(fi−1 − 2fi + fi+1 ) − fi00 = 2 (f (xi − h) − 2f (xi ) + f (xi + h)) − f 00 (xi ).h2hРазложим f (xi − h) и f (xi + h) в ряд Тейлора (одну функцию как сумму двух) и получим:fxx,i − fi00 =1h2h3 (3) h3 (3)h4(fi + fi − hfi0 + hfi0 + 2 fi00 − fi + fi + 2 f (4) (ξi ) − 2fi ) − fi00 .2h26624Сократив, получим, чтоfxx,i − fi00 = f (4) (ξi )h2.1200Теперь получим схожую оценку на fxx,i:1 00100(fi+1 − 2fi00 + fi−1) = 2 (f 00 (xi − h) − 2f 00 (xi ) + f 00 (xi + h)) =2hh1h2(3)(3)= {аналогичное разложение в ряд} = 2 (2fi00 + fi h − fi h + 2f (4) (ζi ) − 2fi00 ) = f (4) (ζi ).h200=fxx,iВ итоге, подставив полученные равенства в (4.11), получимψi =1 (4)f (ξi )h2 − h2 f (4) (ζi ),2ξi , ζi ∈ [xi−1 ; xi+1 ].Отсюда следует оценка сверху:|ψi | 6h2 (4)33|f (ξi )| + h2 |f (4) (ζi )| 6max |f (4) (x)|h2 = M4 h2 .22 x∈[a; b]2Переходя к максимуму по узлам сетки, получим требуемое неравенство:||ψi ||C(Ωn ) 63M4 h 2 .2Согласно (4.10), из этого следует утверждение леммы.Теорема 4.3 (о сходимости интерполирования сплайнами).
Пусть f (x) ∈ C 4 [a; b] и для этой функциина равномерной сетке Ωn построен кубический сплайн S3 (x). Тогда будут справедливы следующиеоценки:||f (x) − S3 (x)||C[a; b] 6 M4 h4 ;(4.12)||f 0 (x) − S30 (x)||C[a; b] 6 M4 h3 ;(4.13)||f 00 (x) − S300 (x)||C[a; b] 6 M4 h2 .(4.14)64Глава 4. ИНТЕРПОЛЯЦИЯ И ПРИБЛИЖЕНИЕ ФУНКЦИЙДоказательство. (1). Из (4.6) следует, что для x из сегмента [xi−1 ; xi ] справедлива формула:S300 (x) = ci + di (x − xi ).Как уже говорилось, после вычисления коэффициентов ci мы находим di по следующему правилу:di =ci − ci−1.hПодставим это выражение в формулу для S300 (x) :S300 (x) = ci + cix − xix − xix − (xi − h)x − xix − xi−1xi − x− ci−1= ci− ci−1= ci+ ci−1.hhhhhhОбозначив αi (x) =x − xi−1xi − x, а βi (x) =, получим, чтоhhS300 (x) = ci αi (x) + ci−1 βi (x).(4.15)Заметим, что αi (x) + βi (x) ≡ 1. Воспользуемся этим, чтобы написать тривиальное тождество:0000f 00 (x) = (αi (x) + βi (x))f 00 (x) + αi (x)fi00 + βi (x)fi−1− αi (x)fi00 − βi (x)fi−1.где fi00 = f 00 (xi ).
Воспользовавшись представлением (4.15), получим такое выражение:0000f 00 (x) − S300 (x) = αi (x)(fi00 − ci ) + βi (x)(fi−1− ci−1 ) + αi (x)(f 00 (x) − fi00 ) + βi (x)(f 00 (x) − fi−1).Отсюда следует неравенство для модулей:0000|f 00 (x) − S300 (x)| 6 αi (x)|fi00 − ci | + βi (x)|fi−1− ci−1 | + |αi (x)(f 00 (x) − fi00 ) + βi (x)(f 00 (x) − fi−1)|. (4.16)Оценим отдельно первые два модуля:00αi (x)|fi00 − ci | + βi (x)|fi−1− ci−1 | 6 (αi (x) + βi (x)) max |fi00 − ci | = max |fi00 − ci |.iiЗаметив, что ci = S300 (xi ), мы можем применить только что доказанную лемму. Тогда получим:00αi (x)|fi00 − ci | + βi (x)|fi−1− ci−1 | 6 ||f 00 (xi ) − S300 (xi )||C(Ωn ) 63M4 h 2 .400Разложим в (4.16) fi00 и fi−1в ряд Тейлора:1= f 00 (x) − (f 00 (x) + f (3) (x)(xi − x) + f (4) (ξi )(x − xi )2 =21 (4)2(3)= f (x)(x − xi ) − f (ξi )(x − xi ) , ξi ∈ [xi−1 ; xi ].2100000000f (x) − f (xi−1 ) = f (x) − (f (x) + f (3) (x)(xi−1 − x) + f (4) (ζi )(xi−1 − x)2 =21 (4)(3)= f (x)(x − xi−1 ) − f (ζi )(xi−1 − x)2 , ζi ∈ [xi−1 ; xi ].2f 00 (x) − f 00 (xi )(4.17)4.1.
ИНТЕРПОЛИРОВАНИЕ КУБИЧЕСКИМИ СПЛАЙНАМИ65Теперь последнее слагаемое в (4.16) примет следующий вид:00|αi (x)(f 00 (x) − fi00 ) + βi (x)(f 00 (x) − fi−1)| =αi (x)f (4) (ξi )(x − xi )2βi (x)f (4) (ζi )(xi−1 − x)2−|=22xi − x(x − xi )(x − xi−1 )(xi − x)(x − xi−1 )x − xi−1; βi (x) =} = |f (3) (x)+ f (3) (x)−= {αi (x) =hhhh(x − xi−1 )(x − xi )2 (4)(xi − x)(xi−1 − x)2 (4)−f (ξi ) −f (ζi )| =2h2h= {сокращаем первые слагаемые} == |αi (x)f (3) (x)(x − xi ) + βi (x)f (3) (x)(x − xi−1 ) −=|(x − xi−1 )(x − xi ) (xi − x)f (4) (ξi ) + (x − xi−1 )f (4) (ζi ) | 62h(x − xi−1 )(xi − x)· 2M4 h =6 {нам известна оценка на четвертую производную} 6 max x∈[xi−1 ; xi ] 2hhxi−1 + xixi−1 + xiM4 h 2= {максимум достигается в точке x = xi − } = M4− xi−1.xi −=2224Подставим эту оценку и (4.17) в (4.16):∀ x ∈ [xi−1 ; xi ] |f 00 (x) − S300 (x)| 6 M4 h2 .Мы выбирали сегмент произвольно, поэтому можем перейти к максимуму по всем i, получив неравенство для нормы:||f 00 (x) − S300 (x)||C[a; b] 6 M4 h2 .Таким образом, мы доказали третье утверждение теоремы.(2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
