Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 8
Текст из файла (страница 8)
Наиболее часто используется рассматриваемая ниже ивтерполяция многочленами. Однако зто не единственный возможный вид интерполяции. Иногда удобяее приближать функции тригонометрн*июкими полиномами; в других задачах целесообразнее приближать ьпюгочленоьг не у(з), а !пу(х), или приближать у(х) ие многочлгном от т, а многачленоьг от !пх. Часто целесообразно использован интерполяцию дробно-рациональными функциями ). а,хд г" (к) = д(х) —— , ь 4.
В задачах плиннроеииня зкгнерьжгншое в биологии, фвзике, химии, мо|ры)иги, ыедицине н других сбластпх науки возпикаег следующая проблема. Известен вид хорошепз прибпижевия функции, например функция хорошо приближается мнагочленоы второй сгепенн. В то же время измеряемые значения функции содержат большие поВюпшости. Требуется получить павлу ппее в определенной норме приближение при минимальноы числе измерений значений функции.
б. Зшзача приближения появляется прн составлении стандартных программ вычисления эпеменчарнгях и специальных функций. Обычно такие функции обладшот свойствами, позвсляющиьш резко уменыпить объем вычислений. Возникагощая здесь проблема может быть сг(юрмулирована следующим образом. Рассматриваются все функц~ии д(х), программа вычисления которых требует некоторого фиксированного объема памяти ЭВМ, такие, что некстора» норма погрешности ((у — д(( не превосходит с. Среди всех таких функпий нужна выбрать ту, вычисление которой т!лбует минимальных затрат времени ЭВМ.
В зависимости от обстоятельств норма может выбираться по-разному. В большинстве случаев берется ((г() = впр(у(, где (о., Ь) — отрезок, на ко(,е! тороы приближается функции. Зй Глава и Интерполяция в чнслеляое диффереяцяровакае Довольно часто требуется повышенная точность в отдельных точках. Например, одна из стандарнпяк программ вычисления яо»: обеспечивает малость погрегпнасти в норме ]]у(] = епр (р(х)у(х)], р(т) = ппп(10г", х г).
(о, 121 Введение множителя р(х) вызывается требованием малгхти относительной погрешности значений юпх при малых зь Точно так же по-разному может толковаться требование минимальности затрат процессорного времени ЭВ21. Затратьь вообпге говоря, могут зависеть от точки, в коюрой еычисляеп;я значение функции. Обозяашм их через С(х). Если не змеятся информ'щяи о том, с какой частотой вычяглмотся звачелея фуякпии е тех или иных частях отрезка, то, например, можно в качестве обШей меры затрат принять Т = кор г(т).
Еглн такая ипформаци» жть, то можно принять т =. М(г(л)), где М(1(ь)) — математическое ожидание случайиой величины 1(:с). б. При задании функции графиком или сложным аналитическим выражением возникают вариационные задачи других типов. Например, тусть решено разбить отрезок ]а, Ь] гш 1 частей: (а„г, а,], е = 1,..., 1, ао = а, а~ = Ь, х на каждом отрезке [а; н щ] приближать функцию млогочленом ститени п,.
Среди таких способов приближения отыскивается оптимальный г том или ином смысле. Чаще всего заранее накладывается требование ц ы и, фиксируется число отрезков разбиения 1 и проводится оптимиюцня метода по лг,..., а~ г. В частном случае 1 = 1 возникает задача наилучшего приближения зногочленами. Об этой задаче речь пойдет в гл. 4. У. Вид приближающей функции существенно зависит от цели, с коюрой осуществляется приближение.
Предположим, гго с требуемой точюстью функция может быть приближена многочленом десятой степени |ли выражением а| я(п(ы1х+(эг) 4-оз в1п(изх+рз). Коли полученное прибликение испвпауется в теоретических исследованиях, для решения задачи га моделирующем устройстве или в технологическом щюцессе, то вторая )юрма записи может быть более удобной. Однако если значения функеии вычисляются на ЭВМ, то вторая форма азаписи может потребовать ~ри своей реализации большего числа арифметических операций. 'Далее будет конкретно рассмотрена задача иятерполирования много~ленами. Ее выделение вызвало наличием непосредственных многочи- 1 2.
Иктерполяцвоккый мнагочлен Лагрыокь 3 2. Интерполяционный многочлен Лагранжа Среди способов интерполирования наиболее распрсктравгв случай линей- ного интерполирования! приближение ищется в виде р(х;аг,..., сая] = ~ Шср,(х), =-! где ус,(х] — фиксированные функции, значения коэффициентов а, определяются ггз условия совпадения с приближаемай функцией в узлах ипсерполяции сг с ф(х ) =-2сс,ср„(хг), у = 1,..., о.
(1) =! Метод регпения зал!о!и, прн котором коэффициенты а, определяются не- посредственным решением системы (1), называется методам неопределен- ных гхзффацисктое. Как правило, в методе агапргделекпых коэффициентов числа заданных усяо- вий раева чвслу свободных (иевзвешяыт) парючгтрав, подлежащих опредгле- яюо. Наиболее изучен случай интерполирования многочленами 2 асх' с=! (2) Гасла у!с(х) = хс , г = 1,...,н, с система уравнений (1) имеет вид ах! = У(ху), у =1,..., и.
(3) Тапсе мы предполагаем, что все х, различные. Определитель этой си:темы Йес[х'. ] отличен от нуля (определитель Вандерманда). Следоваельво, система (3) всегда имеет решение, и притом единствевпсе. Та- сленвых приложений, а также и следующими обктоятсльствами! аппарат интерполирования многочленами является важнейшим аппаратом численного анап!!за; на ега основе строится большинство методов решения других задач; его роль в численном юсалсюе аналогична роли формулы Тейлора в классическом анап!ма Понутно будут рассмотрены нексгсорые другие вопросы общего характера, имеющие зиачение,пля других разделов численного анализа. Глава 2. Интереояялля я численное ляггс(нренцироевние 40 ким образом, доказано существование и единственность интерполяцнонного многочлеиа вида (2). Непосредственное наховгцение коэффициентов а, с помощью решения этой системы уже при сравнительно небольших и, напримор, прв в —.-.
20, приводит к существенному искажению коэффицнентов а, вычнглительной погрешностью. Кроме того, квк мы увцвим в гл. 4, уже сама запись мвогочлена в традицвонной форме (2) часто привсщит к большой вычислительной погрешности ргзулвгвта При теоретических исследованиях, например при конструировании алгоритмов решоиия других задач, эги обстоятельства могут не играть роли. Однако при реальных вычислевиях влияние вычислительной погрешности может быть недопустимо болыпим, и поэтому применя~отся другие виды интерповяционного многочлена и способы его записи. Можно получить явные представления интерполяционного многочлена (2), не приГюгал к непосредственному регпению системы (3). Сразу же от метим, что в другах случаях, например при интерполщюванви функций многих переменных, получение интерпсляциовнаго многочлена в явном виде затруднительно, и часто приходится прибегать к непосредственному решению светелкам уравнений типа (1).
Пусть д~ есть символ Кровекера, о1гредввяемый соотношениями 1 при ( 0 при 1туб Задача интерполирования будет решена, гели удасня гюстроить многочлевы Ф,(х:) степени не выше п — 1 такие, что Ф,(х, ) = Б~ при й1 = 1,..., и. Многочлен й (х) =) Лх,)Ф,(х:) будет искомым интерполяциониым многочленом. В саьгол~ деле, ря(х ) = 2 )(х,)Ф,(х,) = ~ 1(зч)6, = )(х,); яГ кроме того, дя(х) — многочлен степени и — 1. Поскольку Ф,(е: ) = 0 при у ~ г, то Ф,(х) делится иа х: — ху при у ~ ь Галим образом, вам известны и-1 делителей многочлена степени и — 1, поэтому Фг(х) = 1П(*-*» угы ь Из условия Ф,(хч) = 1 получаем '(х)=П,", .'., $2.
Ингерполяционный многочлен Лагранжа Интерполяционный многочлен (2), записанный в форме называют аншерноллцооннмм м»югочленом Лагрхноюо. Существуют другие формы записи того же нитерполяционного многочлгна (2), например расгматриваемая далю антерполхцвопнол формула Не<стока и ее варианты. При точных (без округлений) вычислениях значения, получаемые по различнылг ивтгрпакяционныы формулам, совпадакгг. Наличие же округлений приводит к различию в получаемых по вгим формулаы знач<лий интерполшшонглых многочленов.
Запись много- члена в форме Лагранжа, как праввло, прнводит к меньшей величине вычислительной погрешности; запись же многочлена в форме Ньютона более наглядна н позволяет лу вне проследить аналогию п1юволимых построений с основными построениями математического анализа. Кроме того, этим различным формам записи соотвсггтвунг различвге холачесгаео арифмшваческах опсулицай при вычислении с их помоаюю значений интерполяционного многочлена. Мы употребили термин <количество арифметических операций». Поясним, что имеется в виду.
Пусть рассматриваезся задача вычисления значении многочлена Р„(з ) = а„х" + оа лха ' + .. + агх + ое в точке х. Вычисления можно провозить различными способами. Например, можно поступить сведующим образом. Вычислить значение ал:с и сложить с ае. Далее вычислить значение атх и сложить с полученным результатом и т.д. На рм шаге, таким обраюм. вычислветсв значение а хг и склаДываетсЯ с Уже вычисленной сУммой азйаллй -~-а гхг Вычисление значения а.хг требует у операций умножения. Таким образом, описанный вы<не алгоритм требует для вычисления значения моногочлена (1+ 2+ + н) = п(п+ 1)/2 операций умножения и п операций ююжения. Количеспю арифметических операций (действий) в данном случае будет равно Фл = п(н-1-1)/2+ н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
