Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 10
Текст из файла (страница 10)
Иногда зту задачу трактуют и как задачу наилучшей (в норме С) аппроксимации функции ГР полиномом степени не выше р — 1, Чебышевым была указана явная формула Т (!) = —,соз (рагссоз г]. (14) Правая часть, несмотря на тригонометрическую форму представления, в действительности является именно полиномом от ! степени р. Если нас интересует полипом, наименее уклоняющийся от нуля на произвольном интервале 1а, Ь], следует сделать замену переменных а+Ь Ь вЂ” а 2 / а+Ы х= — + — / г= — х —— 2 2 ' Ь-а ~ 2 которая переводит интервал — 1 и ! к 1 в а к х и Ь. Очевидно, Множитель ](Ь вЂ” а)/2]Р введен для сохранения нормировки: коэффициент при хг в тр(х) равен единице.
Легко вычислить корни полинома Чебьппева, используя его тригонометрическое представление (14): 22 — 1 2 Р Для /г = 1, 2, ..., р получаем разные корни. Их значения имеют простую геометрическую интерпретацию: полуокружность единичного радиуса нужно разделить на 2р равных частей и из каждой нечетной тачки деления опустить перпендикуляр. Отметим, что плотность корней повышается на концах интервала [ — 1, 1]. Корни чебышевского полинома на произвольном интервале (а, Ь] суть а+Ь Ь-а 22-! х = + — сов — и. 2 2 2Р Полиномы Чебьппева являются хорошим базисом в пространстве функций, заданных на каком-то интервале, для определенности на ИИТИРПОЛЯЦИЯ ФУНКЦИЙ зз1 1 — 1, 1].
Базис — важное понятие в приближенных методах. Напомним, что это система функций, обладающая свойством полноты, т.е. другие функции можно сколь угодно точно представлять конечными суммами (линейнимн агрегатами) функций базиса с числовыми коэффициентами. Кроме свойства полноты, с практической точки зрения важна «цена» (в числе операций) вычислений функций базиса, С этой точки зрения удобен степенной базис (1, г, гз, ..., гл, ...). Он является полным. Полипом с коэффициентами а„, аи ..., а„вычисляется достаточно просто, Обозначая частичные суммы через З =~ аРГ'", Р-Ь полипом зз вычисляем рекуррентно: Зь-1 = Пь-1 + Рзь К =а, л л т.е.
за л сложений и л умножений. К сожалению, степенной базис обладает серьезным дефектом: он плохо обусловлен. Плохими являются такие базисы, элементы которых котя и линейно независимы, но очень «похожи» друг на друга. Рисунок б поясняет, что имеется в виду. Точка А в плохом базисе имеет представ- л ление а,~р, + азуз с очень большими, противоположными по знаку и близкими друг к другу по модулю коэффициентами ап ИЗ.
Вычисление такой суммы сопровозкдается уже знакомым нам неприятным явлением — сокращением знаков. Итак, плохой базис — это «сплюснутый» базис. Есин читатель потрудится «нарисовать» графики функций г, гз', ..., Узз, едва ли он отличит нх друг от друга, н это заставит его насторожиться. Если читатель сможет найти аппроксимацию какой-либо нормальной функции полнномом высокого порядка, он увидит, что коэффициенты растут очень быстро при повышении степени (т.е. при уменьшении погрешности аппроксимации). При не таких уж больши:с степенях (прн р, равных 20, 30, 40) они достигают столь больших величин, что вычисление полинома на ЭВМ, имеющей 10 — 15 десятичных знаков в мантиссе машинного числа, оказывается невозможным из-эа полноуь потери точности.
Вспомннм, что совсем не так ведут себя коэффипзгеитм разложения какой-либо,функции по такому хорошему базису, как тригонометрический: коэффиппеатн Фурье «честно» убывают в соответствии со степенью гладкости функции. Хорошими базисами являются ортогональные нли близкие к ним. Это одна нз причин, определяющих основы зычислитзльноа мАтвнлтнки большую роль различных ортогональных систем функций в ириближенных мепщах. Полиномы Чебышева с этой то шн зрения хороши, Ови образуют ортогональную (правда, в специальной метрике с весом) систему функций: 1 ~ ть(с) т (с) ~ — '~ —— б'. -! Полиномы Чебышева близки к известному хорошему базнсу— тригонометрическому и, в сущности, совпадают с ним с точностью до замены независимого переменного х = агссоз С.
Дело'стало только за «ценой» вычисления Тг(с). Но и здесь ситуация достаточно блаюпрнятиая: существует удобная рекуррентная формула, позволяющая очень дешево вычислить в какой-то точке с последовательность Т (с), т,(с), ...: т,(с) = 1, т,(с) = с, ..., ть+ (с) 2с ть(с) — ть,(с). и Таким образом, вычисление ~ аь т„(с) стоит, как нетрудно под*-о считать, примерно 2р умножений и 2р сложений. $4. Вычисление определенных интегралов Речь пойдет об одной из самых распространенных в анализе опера- ций — вычислении определенного интеграла $У(с) й.
Весьма общий подход состоит в том, чтобы аппроксимировать функцию /(с) какой-то другой функцией 7(с1, для которой интеграл вычисляется аналитически. Итак, строим с'(с) с оценкой 1Лс) — 7(с)! % с, 'с с е [а, а), и полахаем приближенно ь ь $дс) ссж~7(с) й с очевидной оценкой погрешности з(Ь вЂ” и). Введем на (а, Ц сетку (сь)„"„в и таблицу У„)„" о, являющуюся ограничением подынтесральной функции 1 на сетку. Рассьн)трим несколько шюстйх вариантов 'построения /, приводящих к широко распространенным формулам. 49 Ь 41 вычнсленне опгеделенных ннтепллое 1.
Функция г(г) строится как кусочно-линейная интерполяция [у'„)» на равномерной сетке с шагом т = (Ь вЂ” а)/Ф. Очевидно, что ~ 7(г) ~й = ',~ 0.5 (у„+ У„,.,) т = О а о =т(05уо+У~+Уг+" +Ум-1+05ун). Эта формула известна как Формула транедий. Формулы такого сорта ф С„У„) называют мехпническими квадратурами, ф— коэффициентами (весами) квадратуры, г„— ее узлами.
Точность формулы трапеций зависит от гладкости У. Если У ~е Ир(С), то 1 У(г) — /(г) ) «0.5Ст и погрешность формулы трапеций не превосходит 0.5Сг(Ь вЂ” а). Если У на 1а, Ь1 имеет вторую производную, ограниченную числом С, то линейная интерполяция на каждом малом интервале есть интерполяциоиный полипом первой степени: ~Дг) — 7(г) ~ ц 0 5ггС и погрешность формулы трапеций не превосходит 0.5тгС(Ь вЂ” а). 2.
Еше более популярна формула Симпсона. Она так же строится на основе равномерной соски, содержащей четное число интервалов. Находится таблица Д„)~"' и У(1) строится как кусочно-квадратичная интерполяция, т.е. на каждой паре интервалов (гг„, гг„~н гг„+г) по значениям гг„, угв+„уг„~г строится интерполяционный полипом Лагранжа второй степени. Несложные выкладки дают аде ( у(г)д~=ъ-, у„+4!„„, +у„„). Суммируя для и= О, 1, ..., Ф вЂ” 1, получаем ь и-1 ~7(1) Ы=-, '~(У +4У „+У „) = а -о = з Уо + 4А + юг+ 4уз + " + ага-г + ага-1 + Угн) Формула легко запоминается, ее точность легко оценивается, Если функция у имеет третью производную и ~ У"'(г) ~ ц с, то ~ 7(г) — У(г) ~ ц Стг/3 и иогрелпюсть формулы Симпсона не превосходит Ст (Ь вЂ” а)/3, т= (Ь вЂ” а)/2М. Однако теоретические оценки не очень популярны среди прахтнков.'Если нужно вычислить' интеграл с погрешностью е, то мало кто основы вычислительной млтвмлтнкн 1ч.
г сначала оценит третью производную функции у и вычислит шаг сетхи т ° ((Зе/С(Ь вЂ” ' а))) ог. Дело, конечно, в том, что сама оценка завышена и тем более завышена константа С, особенно если функция У задана сложным алгоритмом. Поступают иначе. Вычисляя интеграл с небольшим числом узлов (М= 2 + 3), получают число Ю,; вычисляя интеграл с удвоен- Ч'вблнпа 5 ным У, получают, 5, Ясли модуль ~5 „— 5,~ с,е, число 5 считают ответом с требуемой точностью.
В прот(явном случае вычисляют еще 5р, и сравнивают ~5г,„— 5гл~ %~в, и т.д. Нужно иметь в виду, «то для гладких функций у ча интеграл вычисляется очень~ точно при неожиданно малом~ числе узлов. Поясним на конкретном примере полезный прием, позволяющий заметно повысить точность ответа, когда известны 5н, 5 „, ... (это так называемая экстраполяция Ричардсона). Вычислим, например, г ~ е" ~й = ег — 1 = 6.389056098. о В табл. 5 представлены (У„) и коэффициенты квадратур Симпсона С„для Ф, равных 1, 2, 4.
По таблице легко вычисляются значения Ю = б 420727761 Яг = 6.391210176 5з = б 3891937. Относительные погрешности этих величин суть 0.5, 0.03, ОЛ)02 7,'. Для многих инженерных приложений даже погрешность 0.5 % считается малой. Экстраполяция Ричардсона. Вычисление значений 5л для нескольких Ф открывает возможность в качестве «бесплатного приложения» получить значительно более точное значение интеграла. Это достигается простой процедурой экстраполяции полученных значений. Идея очень проста. Пусть для величины Я имеются приближенный метод вычисления с малым параметром т и теоретическая оценка 5=5, + Стг+ о(тг). Посюянная С, конечно, неизвестна, порядок же погрешности р иавестен.
3 41 вычислеиие опгеаелеииых иитнтллов Если вычислены две величины Ю, и Л„мы имеем два следующих соотношения: Я= Лм + С(гт)г+ о(тл), Я= Б, + Стг + о(тг), Из них можно найти о с точностью до о(тл), исключив главный член погрешности. Умножая второе уравнение на гг и вычитая из него первое, получаем 5 = (гав, — Бы)/(гг — 1) + о(тг) В табл, 6 представлены результаты: значения Я„вычисленные по формуле Симпсона, и значения Б, полученные экстраполяцией Ричардсона по значениям Яп Явл и Зол, Бом.
Для всех величин приведена погрешность (абсолютная). Выше было указано, что погрешность формулы Симпсона не превосходит о(т'), поэтому экстраполяция проводилась сначала при р= 3. Результат оказался обескураживающим: экстраполяция не только ие повысила точности, но и дала заметно худший результат. В чем же дело? Причина кроется в очень важном обстоятельстве, которое никогда не следует забывать, применяя подобную экстраполяцию. Обычно порядок погрешности р устанавливается на основе теоретиче- Таблица б скнх оценок, которые, как правило, дают завышенное значение. Завышение оценки может влиять как на коэффициент при тг, так и на саму степень.
Фактически точность может быть более высокой. Те же соображения могут быть использованы в условиях, когда не только коэффициент С в оценке погрешности, но и степень р не известны. Разумеется, теперь надо иметь три приближенных значения, чтобы исключить член Стг с двумя неизвестными. Формулы выводятся просто: б,=я+ Се" + о( ), бм = и+ г С" + о("), б„= я+2 г С. + о(. ), основы вычяслитзльноя млтвмлтихн Пренебрегая членами о(тг), имеем (Я, Ям)/(Я, Я,) 2 .