Samarskij A.A. Vvedenie v chislennye metody (ru)(400dpi)(T) (969542), страница 11
Текст из файла (страница 11)
Рлзпостп!1Г ъ'Равна!!ня Рассмотрим формулы прогонки у; = а,е,у;,, — ,'- !1„„уя == О, 1 =- 1, 2, ..., 1'т — 1, а1 а; — а,.ы а,.р,. + ~т,.а !1ае1= — '' ', !1, — — О, 1= 1,2,..., Л вЂ” 1. а — а аы 1 При условиях (7) имеем !11;,! «1 и м я !у !~!у - !+!!11.- !~!у. !+ Х !р.!= Х !р,!. а=-ы1 Вводя функцкю а;р, — 11а 1Н1лучаем Ч11 1 =- (1Р ' й 1Г ) ы ы п !Ц»!-=!ЦА!+йа! !Я=!Ч !+ Х й'! ! А=1 так что ! 1'а "' ! - а ' 1ю1 'эА1 В результате получаем для решения аадачи априорную оценку а 8 !ф!,( ~ й — ~~ Ь )1РА! < — аа й ~~' Ь )1ГА! ПРВ а,)~С,>0. 1 ич 1 %А аА а1 а=.1 А.=А Втой оценкой мы воспользуемся при изучении сходимо- сти ревностных схем.
Глава 11 ИНТЕРПОЛЯЦИЯ И ЧИСЛЕННОЕ ИНТЕГРИРОВАНИЕ й 1. Иптерполнцня н приближение функций 1. Постановка вадачн. Одной пз основных задач численного анализа является задача об интерполяции функций. т1асто требуется восстановить функцию /(х) для всех аначепий х на отрезке а ~ х ( 6, если известны ее значения в некотором конечном числе точек етого отрезка, '-)ти значенкя могут быть найдены в результате кабак»лений (измерений) в каком-то натурном эксперименте, либо в результате вычислений. Нроме того, может оказаться, что функция /(х) задается формулой п вычисления ее значений по этой формуле очень трудоемки, поэтому желательно иметь для функции более простую (менее трудоемкук> для вычислений) формулу. которая позволяла бы находить приближенное значение рассматриваемой функции с требуемой точпостьн» в любой точке отрезка.
В результате возникает следук»п(ая математическая задача. Пусть па отрезке а ~ х ( Ь задана сетка е» (х„ = а ( х, (... ( х„= б) и в ее узлах заданы значения функции у(х), равные у(х„) = у„, ..., у(х,) . у,...., у(х„) у„, Требуется построить интерполяпту — функцию /(х), совпадающую с функцией у(х) в узлах сетки; /(х) у„( 0,),...,п, (1) Основная цель интерполяции — получить быстрый (экономичный) алгоритм вычисления значений /(х) для аначений х, не содержащихся в таблице данных, Осковнои вопрос: как выбрать ннтер~олянту /(х) и как оценить петре»пность у(х) — /(х)? Иктерполирующие функции /(х), как правило, строятся в виде линейных комбинаций некоторых элементарных функций: М /(х) ~ с»сР» (х), »-» где (Ф,(х)) — фиксированные линейно независимые функ- ции, с„с„..., с.
— не определенные пока козффициенты. 02 гл. 11. пт1тггполппил и чпсдгнпог иитГггпгонлнггн Из условий (1) иолу шм сщ,тему и+! уравнений относительно коэффициентов (с„): в ~ с~Ф~, (х;) -= ун 1 = О, 1,..., и. а.=о Предположптц что система функций Ф„(х) такова, что прн любом выборе узлов а = х„( х, (... ( х„= и отличен от нуля определитель системы: Л (Ф) —.:.: е ( г) г (~а) в (тт) Р„(т) — ~ с»х", а-и (2) *) См. н»пример, Ияып| В. А., Позняк Э. Г., Основы математического анализа, ч. П. — 51,; Наука, 1980, с. 50, Тогда по заданным у, И = О, 1, „и) однозначно определяются коэффициенты с„(й = О, 1, ..., и), В качестве системы линейно пезавпспмык функций (Ф,(хИ чаще всего выбирают: степенные функции Ф„(х) =х" (в этом случае (= Р,.(х) — полипом степени л): тригонометрические функции (Ф,(х) = со» йх, »(п )сх) () — тригонометрический низином). Используются также рациональные функции и -',— и х — ' ...
Л. и х'" в ' 1 '' '' м ()„л)),~'. "' ,()„~" и другие виды шперполирующпк функций. Мы рассмотрим ннтерполяциоиные по»пионы и силайп-интерполяцию — случай кусочно-полнномиальший интерполяции. 2. Полнномнальная интерполяция. Известно, что лкм бая непрерывная па отрезке (а, 6) функция )(т) может быть хорошо проб;ищ'еиа некоторым полппомом Р„(х)а); Теорем» Бей ершт расс». (ля любого е) О существует полинам Р„(х) сттени п=и(е), такой, что гиок ) /(х) — Р„(х)((е.
хнрьь) Однако эта теорема ие дает ответа на нопрос о существовании ворожего иитерполяцпо~гиого полииома для заданного множества точек ((хь у,)). Итак, будем искать интерполяцмоиный полинам в виде а !. интегноляция н пг!1гтнгнгянг Функции я где с! — иеонределеииью коэффициенты.
Полагая )(х,) = = уо получаем систему лннейнык уравнений со+ сгхо -- ° + с хо = уо со+ с,х, ... + сох, =- р<, о со + с,х, + ... + со.<о = у, Определителем этой системы нвляется отличный от ну!ни определитель Вандермонда: П о о ''' *о о ! х!''1 "х! Ц (хо — хо,) Ф О. о -Иэп О Отсюда следует, что интери<мационный молином (2) су- ществует и едннствон (форм заинсн его существует много). В качестве базиса (<Р„(х)) мы взяли ба<но из одночле- нов 1, х, х'-', ..., х". Для вычислений б<ыео удобным яв- ляется базис иолииомов 1)агранока (1<(х)) степени и или яоо<1<<Ри<(иснгое,<1иг1<анхса: !'1, если ! = 1<, 1<( ) (О, если <~1, <, о = 0,1, ..., и, !(струнко видеть, что но!ионом стенеии я 1<, (х) —.- 1<, (х) .— ( ")( — !)".
(' -'-)( -оо-!)" ('- ) (хо о) ( о - !) ('<, хо-!) (хо — хо !) (*о хо) у:<ов.<етворяет этим условинм. Но;пщом 1<(х), очевидно, оиределнется единственным образом. В самом деле, пусть существует ещо одни полипом 1„(х); тогда ик разность Т,(х) — 1,(х) =<1„(х) есть молином степени я, обращающийся н нуль в л -(-1 точняк х, (! = О, 1, ..., п). Ото возтникно только при 1„(х) — 1о(х) ==-О. По.и!нам 1,(х)<<о иРнннмает зиачоипе Р, в точке .хо и равен ну:по во всех остальных узлах х, нри )ам 1ь Отсюда следует, что интерноляционный полянок и Р«(х) = д< 1о (х) э'< . ~о ро Ц Р) о о о=-о 3< Х' е4 гл.
~. ЯнтГРполяппя н чпслгнноа пнтвГРНРОВ1нит имеет степень не выше и и Р„(х,) = уь Формулу (3) называют формугоК Логронзга. Число арифметических действий для вычисления по (3) пропорционально и', Для оценки близости полииома Р„(х) к функции Дх) предполагают, что существует п + 1-я непрерывная производная 1'"+О(х). тогда имеет место формула для погрешности <ь,1>(1) ь11 1(') — Р ( ) =- ,„ „, П ( — ';), ь — ! , д! г 1 3.
Интерполяционная формула Ньютона. При вычис- лениях на ЗВМ удобна интерпогя1(ионная 4орчу,га Нью- тона. Для ее записи надо ввести так называемые разде- ленные разности: разделенная разность первого порядки: у(хь хг) (у(х,) — у(х;))Пх; — х,); разделенная разность второго порядка: у(х„ хь х„) = (у(хь хг) — у(хь х„))/(х, — х,) и т. д. Если у(х) = = Р„(х) — полипом степени п, то для него первая разде- ленная разность Р(х, х„) (Р(х) — Р(х,)!I'х — х,) есть ко- лином степени и — 1, вторая равность Р(х, х„х,) — поли- пом степени и — 2 и т. д., так что (и+ 1)-я разделенная разность равна нулю.
Из определения разделенныл разностей следует: Р(х) = Р(х„) + (х — х„)Р(х, х„), Р(х, .е„) Р(х„, х,) + (х — х,)Р(х, х„, х,), Р(х. х„, х,) = Р(х„х„х„) + (х — хь)Р(х, х„, х„х,) и т. д. Отсюда получим для Р(х) формулу Р(х) Р(х„) + + (х — х,)Р(х„, х,) + (х — х„)(х — х,)Р(хо х„х,) +... ...+(х — х,)(х — х,)...(х — х,)Р(х„хо..., х ). (с1) Если Р(х) — интерполяцнонный полипом для функции у(х), то его значения в узлах сеток совпадают со значениями функции у(х), а значит, совпадают и разделенные разности. Позтому вместо (4) мокино написать ь 1 (х) = у, + 3г (х — х„) (х — .т,)...
А:1 (х гд-1) у (з'г х11 " ° 1 за) (полипом Ньютона), После того как вычислены разделеи- х ь инткгполяцпя и пгикшжхннк финикии ез ные разности, вычислять полинам Ньютона удобно по схеме Горнера: )(х) = у(х ) + (х — х )(у(х„,х ) + (х — х )1у(х„ х„х ) + .. 11. Вычисление 1(х) для каждого х требует а умножение и 2и сложений нли вычитаний. Существуют и другие формулы интерполяции, Среди них наиболее употребительна эрмитова интерполяция.
Здесь задача ставится так. Заданы и уалов (х;), и значений функции (у;1 и и значений производной (у,(; требуется найти по:шном максимальной степени 2а — 1, тако(|, что Р (х;) = у„Р'(х;) = у„( =- 1, 2, ..., п. 1(роме того, на границе прп х = х, и х = х„ставятся условия (" (х,) О, 1" (х„) О. (5) Будем искать кубический полинам в виде ((х) а~+ Ь;(х — х;,) + с,(х — х;,)'+ а,(х — х,—,)'", х,,~х~х,. (6) 11з условия (, = у, имеем 1(х; т)=а~ уз и / (х,) = а; + Ь;Ь; + с,Ь( + И,Ь,'- = уь й,=х; — х; о (=1,2...,,п — 1. (7) Если все х; различны, то существует единственное решение, которое находится способом, аналогичным методу Лагранжа. Следует иметь в виду, что применение полинома высокой степенп мо;кет приводить к трудным проблемам, связанным с ошибками округления.
4. Сплайн-интерполяция. 1'ассмотрим специальный случай кусочно-полинами альной интерполяции, когда между любыми соседними узлами сетки функция интер- полируется кубическим полиномом (кубичсская салайииитерполяйия). Его козффпциенты на каждом интервале определяются пз условий сопряжения в узлах: /, = уь У'(х,— 0) =('(х,+0), ("(х; — О)=("(х,+О), 1 1, 2, ..., я — 1, се гл.
и. интивноляция и числкннок интхгеиеовхнггн Бычггслгггг производные: <" (х) = 6, + 2с,(х — х,,) + Зг),<х — х,,)', У" (х)= с,+Ог<х-х,,), и потребуем пх непрерывности прн х хл 6; ., =- 6, -;- 2с,)г, -,'- Зг(гй'н с;,, == с;+ Зг)г)гь < 1,2,..., и — !. (8) Обшее число неизвестных козффш(иентов, очевидно, равно йо, число уравнений (7) и (8) равно йгг — 2. 11едостакнцпе деа уравнения получаем пз условию (5) прп х х„ гг х=х<к с,-О, с„+Ы„Ь,=О. Выраэгган пз (8) г), = <сн, — с,)ээЗЬ„ггодсгавлягг зто выражекпе в (7) и исключая а; у; „получим 6, = = ((рг — р;,) 'Уг;) — —,, Ь; (с, э г + 2с;), г =-1, 2, ..., и — 1, г 2 6и ((<<~~ рй — г) )г! з 6|эс 1 ° с краевымп услоннямн с, == О, с„,, = О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
