Бабенко - Основы численного анализа (947491), страница 49
Текст из файла (страница 49)
Й -Ь 1. В том случае, когда и =. Д(х ), О =- О, 1, ..., и — 1) правая часть формулы (4) называется и — 1-й разделенной раоностпью функции у и обозначается а1(7"; хо, ..., ти 1). Таким образом, Глава Я. Элементы теории ири»лг>и>сепий Поэтому интерполяционный полипом Лагранжа могкно представить в ви- де п — 1 р(х; У) = ~~' (х — хе) (х — хь 1)ыФ хе, л>ь), (6) 1 — О называемом ньютоновской >)>1>рлее>17 иип>ерполлцг>оиноео еиногг> лена.
2. Основные свойства разделенных разностей. Остановимся на свойствах разделенных разностей. 11режде всего докажем, что и>(7> ХО ., Хп) = [и>(У:. Хм, Хп) — и>Ж ХО,: Хп 1);>>(Хи — ХО) (7) В самом деле, если обозначить через Х правую часть последней формулы, то на основании (о) и и — и-1 п — 1 л -1*.-'>'[е >г >[П> *>) Ели>[П>* *>) ) >=1 Ь-..> >=о 1.—.
О >Ф> Когда > ф О, и коэффициент при 7'(х .) очевидно равен и — е — 1 — 1 г*.-"> '([Пг' -г>) -[П> -'>) )= 1=1 >=О и — 1 ,— 1 =>* -и>л(П>* -'>) >>* -'.г'-гь -"> '> = 1=1 =(Пг' -*>) и, стало быть. имеет требуемый вид. При >' = О, и этот коэффициент 1 — 1 соответствонноравен ~ П(х. — х>)( и ~ П (х, — х>)~ .ПоэтомуХ = (У' тм . ) На основании (7) процедура вычисления разделенной разнос'ти становится довсн>ьно простой. С этой цельк> достаточно вычислить треугольную таблицу вида и>(Г:, Ха) '3(>',, ХО т>) ° ° ° и>Ф ХО ° ° ° .
Х вЂ” 1) и>(Г' ХО ° ° ° Хп) ' '((: х>) и>(7: х>, хе) .,.и>(>л; х>....., х ) и>(.> Хп — 1) и>(> Хи — 1 .тп) Фх ) в которой в первом столбце стоят значения функции в узлах, так какг согласно (5), и>(Д; х, ) .—. 7(х ). О роли разделенных разностей мы будем говорить ниже. 'Ос1.
ХХнтерполлииоснсий лаамочлен в форме Ньмтосса 229 Разделенная разность (зс; хо,..., хп !) обладает одним исключительно важным свойством . она является симметрической функцией своих аргументов хо, ..., хп !. В самом деле, интерполяционньш многочлен Лагранжа (1.13) не зависит от порядка нумерации узлов, т.е.
он инвариантен относительно любой перестановки величин го, ..., хп Следовательно, этим же свойством ооладает и его старший коэффициент, который в силу формул (4), (5) совпадает с рассматриваемой разделенной разностью. Для гладких функций разделенные разности допускангт красивое интегральное представление. Положим Ьх, .— х, ! — х, (с .—... О, 1,...).
Предложение 1. Пусть 1" й С"[1) и узлы х, (~ =- О, 1,..., и) принадлежа!в отрезку 1. Тогда ы(Х! хо| хп) = с„ = / ~. / 1" (хо+1ссххо+ +Сп11хп — !)д1с...с(2,. (8) о о о Доклзлткльстио. Будем проводить его индукцией по и. Для первой разделенной разности имеем '(У; хо, т!) = (у(х!) — У(хо)) = / Х (хо+асЬхо)41!. х! — хо С '(,С ХО Хп) С" (У; Х» — ! ° со ° °; Х» — 2~ Хп) 1 ,СО(С ХО: Хп — 2 Хп) ОС(У; тп — С ° ХО ° ° ° Хп — 2)! = Ьхп .! ' 1 [СО(С; г'0 Хп- 2 'Гп) ОС(,С С О!о~ ~ Хп.— !)]. 21х„ Используя предположение индукции, отсюда получим ! с, с., / / / У (хо Э сссххо -'.
о о о 1 '(1; хо,, х ) .=. ~хп — ! с, с .. + 1»,(11хп 2+ С), и,)) д2!... д2„! — 1 1... ~ Х<"-"(хо+ о о о !!санхо Ссс — !с~хе г)с11!...саги -!) Допустим, что формула (8) справедлива для разделенных разностей по- рядка и — 1. В силу формулы (7) и свойства симметричности разделенных разностей имеем 230 Глава Я. Элементы теории прибливюений Замечая,что («-'«з: -«) !«1 («'о -ь !«еххо — « * †«(«хз: - г †, '«хх -«))— ,Г (хо е«'лхо 1 ° ° 1 ев-«елхп — 2)! « Г~ (то т !«1«хо — ' — , '~,„— «етх —.г+ «вГ«хо — )г«! «в« о получим интегральное представление (8).
Следствие 1. 11рименим к интегралу (8) теорему о среднем. '!огда получим е„ (Г ) — Г (Г) Г Г 3Г .—.. 00 (9) и! о о о где «, е 1. Следствие 2. Если Г е И'" (М; 1), то ~ы(Г; х., х„) <М!и.' Доклзлткльство. Если Г я С"[1) н Г«"!~ < М, го (10) вытекает из соотношения (9). Поскольку множество таких функций плотно в И'ч (Л1: !), то неравенство (10) справедливо в общем случае. Б Следствие 3. Разделенная разность порядка и от много мена степени т < и р«вна нулю, а при т = и равна старшему коэффициенту.
Эти утверждения очевидным образом вытекают из формулы (9). 3. Хонечные разности и их свойства. Особенно простой и изящный вид приобретает формула (6) для равноотстояц«их узлов, когда х,т« — х, —.. !«(« = О, 1,...). Согласно общепринятой терминологии, величину !«будем называть шагом интерполяции (или шагом таблицы, если речь идет о построении интерполяционной формулы по табличным« значениям Г(х,) (« = О, 1,...) функции Г(х,)). Учитывая, что х, = хо+ -Ь«!«(« .= 1, 2,...), и подставляя эти выражения в формулу (5), в которой предварительно сделаем замеяу и — п+ 1, получим с"- ( — 1)" 'Х(хо+а!«) «(Г; хо, "., х.) = 2 1,„,~( «=о а4.
Игппгуполлпионннй лпюгочлеп о форме Ньюп оно 231 поскольку П(х — х~) =- ( — 1)" оу'! (п -- 1)!. Отсюда ~=а !ф-з (Пг,",*О=„„'„,~(,"]ЕП -'Лс ~ ) ' о=а Если правую часть формулы (1Ц умножить на 6"п), то получим выражение, которое называется п-й конечной разностью с шагом и функции Д(х) е точке ха и обозначается Л~п, ~(ха). В З 4 гл. 2 мы встречались с оператором Ьь, который был элементом кольца операторов.
Таким образом, мы вновь встретились со степенями оператора Ьь. Очевидно, что п онпп=г.(.)Е'Г 'УП +Я) о=а (12) Конечные разности в численном анализе игракгт колоссальную роль. Их свойства непосредственно вьпекают из свойств разделенных разностей. Из соотношения (7) следует, что гнпп Зл(та) = ~Ь(л Ьгг(та)) = уЗ7|(Ха -' с) г1ЬХ(Ха), (18) причем Ла~)'(ха) = )'(ха). Соотношение (8) влечет равенство ь и й — 1 гзьу(ха) — ' и' ~ / / Х ~(ха+11-,', с )о1И...о11, (14) а а а выполняющееся для у е с" ]1]. Для конечных разяостей можно указать еще одно интегральное представление: ЯХ(ха) = /.
~фрб(ха пь 1п, +1п)оПю йео, (15) а а которое элементарно доказывается индукцией по и. Из соотношения (1)) получаем сну(ха) = и"у~"' (4), ( е (ха, ха пй), у е С" ]Е], (16) и, .если у' Е 14'",(М; 1), из (10) получаем неравенство ль|(ха)] Е лфп . ,2 ь пьУ(ха) = и! йпсп. (18) Наконец, отметим, что если у Е М (т < и), то Л"„Д(ха) =.
О, а если т = и чв, '1, Д(х) = спхп -с сп 1хп 1+,. ч то Глава Я. Элементы теории арибличеений и 1(хе -, пй) =- ~ ~"'1 Л„"У(хо). (19) В самом деле, в правую часть формулы (19) подставим вместо ехеД(ха) сумму (12), а затем поменяем порядок суммирования. Тогда по- лучим поскольку и поэтому 4. Конечные разности н влгеабраический интерполяционный многочлен. В ~4 гл. 2 были введены факториальпые многочлены х — ", оци являнется фундаментальными многочленамн оператора елп Эти многочлены линейно независимы и образуют базис в лкебом пространстве многочленов Зг„.
Напомним, что х— а =х(х — 1)... (х — ил-1), и =1, 2,... Разложеяие этого многочлена по стопеням т имеет вид (20) ,н ~~, ( 1)и — ь [п~ ь ь=о где [г] число, Стирлинга первого рода, Наоборот, разложение х ' по /и1 , ь многочленам (20) представляется в виде и — 1 х =~~.) —,, 1=0,1,,п, 1=1 3 З~ (22) ~И где е . ~ -- числа Стирлинга второго рода.
Ы Если заданы последовательные разности Л~,~(хо) (у = О, 1,...,п), то значение функции у в узле хо + иб может быть выражено в виде линейной комбинации ее последовательных разностей: 'з'1, Интперполлцоанннй ленагачлен о форме Ньтотпотта 233 ~~: (х — хо)й 36Яхо) ь=о (23) Этот же мпогочлен можно записать еще и в таком виде: р(х; Х) = 2 с (х — хо)" (т — хо — (6 — 1)6) Ьлф(хо) () в=о 5. Конечные разности н аппроксимация производных функций. Интерполяционным многочленом в форме Ньютона удобно пользоваться при аппроксимации производных функций конечными разностями. Применяя теорему 9 3 3 к функции у е 14'и (М; 1) и отрезку ; 'то, хо + (и -- 1)6) с 1, получим соотношение оо ф е1ьУ(хо) н — 1 + ~ ((х — хо) ь=,-1 ' (х — хо — (6 — 1)6)) '' + езьХ(хо) йьй~ 64(п — 1)'6" (и — е)! где )д, ( с 1, 0 ( е < п — 1, х Е [хо., хо+(и — 1)6]. Как и следовало ожидать, главным членом при аппроксимации деф(х)ееухе является 6 ееЦ1(хо), а остаточные члены существенным образом зависят от значения х.
Так, например, при и .—.. 4, е .—... 1 в общем случае имеем .,(,) ~ь|(хо), р 61 Яф(хо), ф'(х) = 6 (," 2.) 6 — (3(х — хо) — 86(х — хо) — 26 1 ° з е О 2 о '-~ьт(хо) а при х =.. хо м —. а АЛхо) ~ь|(хо) „М, з 2 6 246 2 3 в д а ч и. 1. Покажите, как использовать схему Горнера Лля вычисления значения интерпеляоионного многочлена Лагранжа, считая известными В частном случае равноотстоящих узлов формула (6) для интерполяционного многочлена Лагранжа переходит в формулу (2.4.8), .установленную при 6 =- 1. Общий случай произвольное 6 получаем заменой переменных. Итак, Глава Я.
Элементы теории првблиамвиий его значения в тачаю Подсчитайте число операции и сравните его с оптимальным числом операпнй. 2. Докажите следунлцие тождества для чисел Стирлипга: [~)=(п — Ц[ )т[ ~, ( )=( ) — ', ( ), а>0, [1) ( )( — Ц = ( — Ц"д„,„, ~ ~( ) [ 1( — Ц =- ( — Ц "д„ 3 5. Интерполяция функций многих переменных Р(х) е ф~ а=-:> Р(х) —.. ~~~ аьх~, )ь)<т где ~а = а1 ... + 12.
Подсчитаем размерность пространства +и Предложение 1. (та -г 1)! г)1п1 7ь а (2) Доказлтчдльстно. Пусть с11шф~т = ЛХО„; ясно, что ЛХ1т = тв т 1. Допустим, что 1 < 2; раскладывая произвольный миогочлен Р(х) е рн„, по степеням хб получим т Р(х) = ~ ~х~ аь(хы ..., х~ ~). Ь.-:. О где аь е ф~ 1 „, ь.
Поэтому ЛХ = ~~~ ЛХ Ь=О (3) Введем производящую функцию последовательности (ЛХ~ ): ул(з) — 2„Л4 . Тогда из соотношения (3) вытекает, что ~р~( ) т=е = (1 — я) ~д 1(з). '1ак как д1( ) = (1 — з) ~, то ~ру( ) = (1 — з) 1. Алгебраическая интерполяции функций многих переменных. Перейдем теперь к наиболее трудному и мало разработанному вопросу теории интерполяции интерполировании> функций многих перс" манных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
