Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 9
Текст из файла (страница 9)
Ясно, что количество арифметических операций, нгобхцвимых для вычисления значения Р„(т), может быть уменьшено. Например, можно пошедовательно вычислить и запомшггь значения х<, хз,..., х". Для этого еотребуется и — 1 операций умножении.
Далее вычисляем величины а хз г л/ = 1,..., н). Это потребует и операций умножения. Складывая полученные значения (это требует и операций сложения), получаем Р„(х). В <том случае Фз = (2п — 1) -1- и и уже при н ) 2 имеет место неравенство йт < Фг. Можно пойти еще дальше. Запишем Р„(х) в виде Р„= (. ((а„х -~- а„л)х + а„з) т + ° ) х + ае. Глава 2. Интерполяпкя к чисэеквсе дифференцирование Для вычислении значения во внутренних скобках апх+ о„» требуется одна операция умножения и О»цга операции сложении.
Длн вычигления значения в следугощих скобках (о х Фо„»)х-|-а„з требуетси опять одна операции умножении и одна операция ш»оженил, чвк как с„х-~-св» уже вычислено, и т.д. Таким обраюм, вычншгение Рв(х) при помощи этого алгоритма потребует и операций ул»ножгння и и операций ш»оженнв, то есть Фз = и -~- и. Ясно, что Фз < Фэ < Ф, при и > 2. Таким образом, вычисление Рв(з»] по последнему алгоритму потребует меньше арифметических операций н, соответственно, меньше времени ЭВМ. Количество арифметических операций, которое требуется дл»» пш»учения»юзультатз, нвляетсн одной из важней»пих характеристик метода, по которой происходит сравнение методов.
Иногда до начала вьп»ислений не удается точно оценить требуемое количество арифметических операций, а удается оценить лишь г»прядок количества арпгдмстпчсскпх операций по отношению к какому-либо параметру. В рассматриваемом вылив примере Ф» = 0(п ), Фэ, Ф» = 0(п), и-степень многочлена. В последнем случае (Фз, Фз — — 0(п)) говорит, что методы имсгот одинаковый поридок количества арифметических операций. В тех случаях, когда находится порндок количества арифметических операций, бывает важно найти постоянную в главном члене.
Например, Фг = — и -~-о(п ), Фэ=Зп-~-о(п), Фз =2п. э э 2 Как правило, метод, требующий меньшего количества арифметических операций, являегсв более быстрым, и поэтому считаетсн лучшим. Выбирая метод решения сложных задач, часто ограничиваются лишь сравнением пор»гаков количества арифметических операций длв различных методов. Заметим, что значение многочлгна Р„(з) определяется параметрами ое, аг...., о и величиной т.
Поэтому в общем случае для вычисления Р„(з) потребуется не менее и арифметических операций, т.е. мы имеем оценку сн»юу дли количества арифметических операций. Таким образом, вто1юй и третий методы вычислении Р„(х] являются оптпмальнмэ»п по порядку, так как Фг, Фз = О(п) и для любого метода Ф > и.
В связи с появлением многопроцессорных вычислительных компле»пав может случиться тэк, что метод, гребу»ошнй бальшшо количества арифме»ических операций, будет быстрее лругого ь»еп»лэ с меньпжь» количеством арифме»нческнх операпий. Поэтому для случая многопроцессорной ЭВМ нельзя оценивать «ачестэо метода толыго по колэчмпеу арифметических операпий. 1 3. Оценка остаточного члена ннтерноляцнонного к~ного глена Лагранжа Ц 3. Оценка остаточного члена интериоляционного многочлена Лагранжа В предположении непрерывности (г")(х) оценим разность между 1(х) и построенным интерпшшционным многочленом д, (х). Положим х(С) = ((1) — д.(1) — К „(1), где аа(1) = (С вЂ” хг) ° (1 — з:„), а К выберем из условия дг(х) = О, где :с — точка, в которой оценивавгся погрешность.
Из уравненил Р(х) = О получаем Лх) — д (:г) гг (х) При таком выборо К функция дг(1) обрагцаьчся в нуль в (п Е1)-й точке хп..., х„, з:. На оснонании теоремы Рояля ее производная хг(1) обраща- ется в нуль по крайней мере в и точках. Применяя теорему Ролля к хг(1), получаем, что ее произнццная дге(1) обралцаетшг в нуль по крайней мере в (и — 1)-й точке. Продолжая зти рассуждения дальше, получаем, по дг1к)(1) обращается е нуль па крайней мере в одной точке О, при- надлежащей отрезку (дп дх), где дг = ппгг(хг,..., х„, х), дя = пзах(хг,..., х„, х).
Поскольку ОО(1) — (1 )р) К нз услови» 1о1а>(1) = О будем импгь ВООК) гг! Следовательно, соотношение т(х) = О можно переписать в аиде 1(х) — д„(х) =,, 1 Е (дг дя) 1'")(О (х) вающем представление остаточного члена. О 4. Разделенные разности и их свойства Как будет видно далее, интерповяционный многочлев можно рассматри° ать как обобщение отрезка ряда Тейлора. Обобщением понятия прожшодной является понятие разделенной розноснгп. Разделенные разности нулевого порядка Цхг) совпадают со знатениими фУнкции 1(хг); Разности пеРвого поРЯдка опРеделшогса Равен- :твом у( ) У(ху) — У(хг) хг — хг Глана 2.
Иигерволяци» н численное диф«(«ере!щировш!не разности вторего порядка — равенством ((хз! «с1.) — ((х„! х ) У(хн хз; хз) = хз и, вообще, разности й-го порядка Дх«!...1 хстз) определяютти чер«п разности (й — 1)-го !юрядка по формуле з (22! ° ° ° ! хщ !) ! (х1! ° ° - ! ха) ((х11... ! хе«1) = Хз! 1 — Х1 (2) иногда вместо Дх«!...!х«) исе«и!гзукт обсенммння (з)(х!!.. !с!) нли (:111... ! 21]. Лемма.
Сз«рыедлиео равенство 1(хз' . ' 22) = 2', Х( 'з) '= П(х -") (3) Доказашельсзпео будем проводить по нцлукции. При й = 1 это равенство преврвщастгн в равенство З(хз) = у(хг), при й = 2 совпцлжт с (1). Пусть (3) доказано при й < !. 'Гогзщ (,, ((:22! ' !«ч) — Х( '1; " ' х!)) Х!+1 — 'Г1 Л з) з=! П (хз х«) «Ф» ((х ) =' П ('3 - х!) 1 Х!+1 — Хз Фз 2<!<М 1 !<ой! Если у н«1, 1+1, то коэффициент при з"(х ) в правой чанги есть 1 1 П (х -х!) П(х -") *'нз Щ 2<«Ц!+1 1<яр! (хЗ- ) — (хЗ- !Р1) (х1+1 хз) П (тз' х!) чвз Х!Чг — Хз и (х;-х) яиз 1<!<Н-1 1«.!+1 45 3 5. Иитераолюгиаииая формула ныстана с разлелеи ными разностями т.е.
имеет требуемый вид; для у = 1 или у =1+ 1 значение Дт ) входит только в одно слагаемое в правой части, и козффицнент при нем также имеет требуемый вид. Доказательство закончено. Непосредственно из (3) иытекает ряд следствий. Ь При фиксированных хг,..., хт разделенная разность является лингйныьг функционалоы от функции 1: (сп11 + а212)(хн. " ', хь) = огЛ(хг:; хе) + а222(хг; "; хе). 2.
Разделенная разность есть симлтетричгская функция своих аргумыпов хп..., хе (т.е. не менясгса при любой их перестановке). Егжи функция задана в точках хм..., х„, то таблицу Ях~) У( с2) У(хп хз;хз) Х(хз 2: ) : Х(х„ ...;*.) (4) 1(хз) 1(х„п х„) Х( ) называют жаблайей разделениьгх разжхтаеа 3 5. Интерполяционная формула Ньютона с разделенными разностями При помощи разделенных разностей можно получить другую форму записи интерпозиционного многачлена (2.4). Спраееллигю равенство Х(х) -' ( )= Х(*) - ) )Х(.»К:*,'. = ;1 132 ' = П(.- хг) ° "х) + Е 2=1 тки Сравнивая с (4.3), убеждаемся, что выражение в скобках есть 1(х; хг;...; хи) Хаким образом, Х(х) — Х„(х) = 1(х; хг;...1х„)ыи(х), (1) где многочлен а„(х) определен в 3 3.
Глава 2. Интерполяция н численное лнфферениироваиие 43 Пусть Ь,(х) — интерполяционный многочлен Лагранжа с узлами интерполяции:сг,..., .с,„. Интерполяционный многочлен Лагранжа би(я] можно представить в вьще б„(х) = Ь1(х) + (Ьз(1с) — 11(х)) -1- . -1- (о„(т) — Ь 1(х)). (2) Разность 1, (т) — б, 1(1с) есть многочлен степени т — 1, обращаюзцийся в нуль в точках я1,..., хо, 1, поскольку бт 1(х ) = Ь,(тз) = 1(хг) при 1 < ) < т — 1. Следовательно, Ь (х) — Го„ 1(т) = А„, 1ю 1(а), и,„ 1(т) = (т — х1)...(х — х,„ 1), ГдЕ А„, ! = СОиа1, ПОЛаГая т = тео ПОЛУЧИМ Дт,„) — Е,о 1(зь,) = А„зю,„.
1(т,). С другой стороны, полагая в (1) и =1и — 1 и и — — х, имеем 1(х,) — б 1(и ) = 1(т; в1; ...; т 1)юю..1(з„,). Таким образом, А 1 = 1'(з11 ...; ты) и поэтому Го„(я) — Ьт .1(я) = ((в11 ...; х,„) ю„,. 1(х). Подставляя вти величины в (2), получим А (Х) Х(я1) ! У(Х1ртз)(Х вЂ” т1)+ " ! У(т1Р..1т )(т — т1)...(т.— я~ 1). (3) .(!'к) Лт! 1;".; ) = — ',, рг <Г <уз. В частности, если 1(я) — многочлен Р1(я) =-) б т' 1=-О (4) степени ! < и, ю на основвлин ягой формулы имеем при ! <и при любых то,...,:со.
ПрсдПОЛОжнМ, ЧтО ТОЧКИ Х1,..., Ко ПРОНуМЕрОВаНЫ В ПсрядКЕ ВОЗрасюния1 хг < тз « ° ° ° х . Вследствие (4) имеем т!,((я~,;...; т1,.1. ) = 11'~(бь), где яь < Гь < 1с1„..1. Повтому неличина АГ,„= яир т! (у(т11...1яьч,„)) 1<в<о-Ь Интерполяциониый многочлен. записанный в такой форме, называется иитерооллциоииы.и многочленом Ньютона с уивделениыми раз1юсо1лми. Из сравнения (1) с (3.1) глгдует важное равенство 1 5.
Имэараоляциомиэя бюрмула Е1ьютама может использоваться в качестве приближенвой оценки для величины М1™ = япр (71")(х)). Задача 1. Доказать неравенство )и — йуфм)~ < 2)УЛ ' )й гдо 5 = швх (хлэ — хл). 1<Л<я— Для упрощении вычислений янтерпшшциовного многочлена иногда используется так нэзываема» схема Эйткгма. пусть Аль,ьял 1)(х) -иитсрполяциовный мпогачдеа с узлами интерполяции ты..., хл, в частности 1(ь)(х) — — Цхл). Справедливо равапство ) (ь. 1,,1ы)(т) (х — хь) — б(л,...,л)(х)(11 — х111) блл,лы,...,ль1)(х) =; (5) Хтл — ЛЛ 11П(х) 111 л) (х) 112) (х ) 1)г,э) (х) 1(э) (х) 11 -1, )(х) 11.)(х) 1П,2,2) (х) 1(1 2 )(х) Эта схема положена в основу стомдмртпой программы решения следующей задачи.
Дана таблица звачений пежпорой функции 1(х)) требуется прп каждом значении х вычислить значение 1"(х) с заданной точностью г или с наилучшей возможной точностью при имемнцойся информации. Трудно дать четкое опредлшснво термина слламл)яртммя программа По усламавившейся традиции егандартной программой речпения задач некоторого класса мазывагл кэалифмцироваммо нэомолимую программу, ашержашую описание алгоритма решения задач данною класса. Решение конкретной задаям осуществляется подсоединением к стандартной программе имфарллавим аб этой конкретной задаче.
От стамдарэ ной программы также требуется, чтобы дапус«алось ее использование как элемемэа п)юграммы, предназначенной для решемия более сложных задач. Рассматриваемое ниже построение алгоритма решения задачи является довольно типичным для ситушлии, возникающей в ршльной практике. действительно, правая часть является миогочланаы степени 1 — я -)- 1 и совпадает с 1(х) в точках хь,..., хыл. Схема Эйткеиа вычяслепии значения 1.1,, „)(лс) заключаетсв в пошледоваттлылам вычислении с помощью формулы (5) элементов таблицы значений иптерполнционпых мна- гочленов Глава 2. Интерполяция в численное Лнффвренцировввие Нсвспможно презложять обоснованный алгоритм рсшания посчввлснной задачи для всех функций, поскольку про функцию ничего нс извссгно, кроме са значений в аздавных точках. Однако, предполагая функцию гладкой, мы выводим прзктичыкий критерий оценки погрешности и, основываясь на нсм, строим авжритм решения задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
