Дьяченко В.Ф. Основные понятия вычислительной математики (Дьяченко В.Ф. Основные понятия вычислительной математики.djvu), страница 3
Описание файла
DJVU-файл из архива "Дьяченко В.Ф. Основные понятия вычислительной математики.djvu", который расположен в категории "". Всё это находится в предмете "компьютерный практикум по специальности" из 11 семестр (3 семестр магистратуры), которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр DJVU-файла онлайн
Распознанный текст из DJVU-файла, 3 - страница
Идеализируем задачу и будем считать, что (30) Уз = г" (х„), й = О, 1, 2, В этом случае точность восстановления Г (х) будет определяться тем, насколько таблица подробна, насколько хорошо она описывает детали поведения функции Р (х) и, конечно, способом восстановления. Пусть, например, способ — самый грубый и состоит в том, что мы каждое значение ~» распространяем на весь прилегающий интервал х» х(х»е (рис.
3), т. е. для вычисления Р (х) используем кусочно-постоянную функцию Р» (х) = ~», х» а х ( х»ам й = О, 4, 2, ... (31) Чтобы оценить величину ошибки, Р, (х) — Р (х), нужно иметь какую-либо дополнительную информацию о функции Р (х), кроме (30). Будем считать, что Р (х) — гладкая х а и Рис. 8. Рис. 4. функция, имеющая непрерывную производную.
Тогда на интервале (х», х»~ ) ее можно представить в виде Р (х) = Р (х») + Р' (з (х)) (х — х„). Отсюда сразу следует, что на этом интервале ~ Рэ (х) — Р (х) ( ( шах ~ Р' ~ (х»+» — х»). т. е. ошибка порядка величины шага таблицы. Более точным представляется способ вычисления Р (х) с помощью линейной интерполяции, т. е. путем построения (вместо (3$)) кусочно-линейной функции, использующей и левое ~», и правое ~».ь аначения Р на каждом интервале (рис. 4), вида Р» (х) = /» + (х — х»), х»(х а 'х»со (33) )»ы 1» *»+1 » Можно проводить интерполяцию с.помощью квадратичных, кубичных и т. д. функций, используя для их построения тройки, четверки и т.
д. точек таблицы. Рассмотрим общий случай. $8 Имеется и + 1 точка хь, х, ..., х„— уаам интериолл»»ии, которым соответствуют значения /ь, гд, ..., ~„. Построим полинам и-го порядка Р„(х) = ~~'~ а,„х, (34) принимающий в точках х, (д = О, 1, ..., и) значения»». Полагая в (34) х = х„получим систему и -(- 1 уравнений для определения и -~- 1 неизвестных — коэффициентов полинома ,Я а хГ =Л 1= 0,1,...,и. (35) т ь Определитель этой линейной системы ~х» ~ (определитель Ван-дер-Монда) равен Ц(х,— х»), т.е.отличенотнуля, »л так как все х, различны, Следовательно, система (35) имеет единственное решение — набор а .
Мы доказали, что существует единственный полинам и-го порядка (не выше), принимающий в и + 1 точке заданные значения. Он называется интериоляционным иолиномом. Конкретная форма записи его может быть различна. Вид (34) малоупотребителен из-за громоздкости выражения коэффициентов а через х», 7». Запишем интерполяционный полинам в форме Лаеранзса Ро(х) =Х У» '~,.~ д (36) где 9» (х) = = (х — хь) (х — хд) ...
(х — х; д) (х — х»+д)... (х — х„). Так как»7» (хь) = 0 при д+»»,то, очевидно, Р„(х„) = Уь. С другой стороны, каждое»7» (х) — полинам степени и. Следовательно, их линейная комбинация (36) есть интерполяционный полинам. Для случаи и = 1 формула (36) превращается в е хд х — ео Рд (х)»о +»д (37) — формулу линейной интерполяции (ср. с (33)). 19 Оценим точность, с которой интерполяционный полипом воспроизводит функцию Р (х). Так как разность Р„(х) — Р (х) в узлах интерполяции х„х„..., х„обращается в нуль, то частное от деления этой равности на функцию д (х) = (х — х,) (х — хд) ...
(х — х„) (38) есть ограниченная функция, и мы можем написать Р (х) = Р„ (х) + В (х) д (х). (39) Оценим В (х). Для этого рассмотрим вспомогательную функцию и ($) = К (з) — Р„($) — В (х)д (з) = (В ($) — В (х)) д(з). (40) Очевидно, функция и ($) обращается в нуль по крайней мере в и -(- 2 точках х„х, ..., х„, х.
Следовательно, найдется хотя бы одна точка $ (х), где обращается в нуль (и + 1)-я производная от и ($), рааумеется, если эта производная существует и непрерывна. Дифференцируя (40) п +1 раз и подставляя $ = $ (х), получим 0 = Р<"+ю ($ (х)) — В (х) (п + 1)(, поскольку (и + 1)-я производная от полинома и-й степени Р„(з) есть нуль, а д ($) — полипом вида $"+'-(- ...
Итак, о(н+П (~ ( .й (о + 1)! и мы получаем выражение для ошибки интерполяции Р(х) — Р„(х) = +, Р~"'и $(х)) д( ). (41) Зависимость $ (х) остается, конечно, неопределенной. Если шаг таблицы не превосходит некоторого Ь, т. е. х„,,— х„<Ь, Ь=0,1, ..., и — 1, то д (х) Ь"" и из (41) следует ! Р (х) — Р„(х) ) ( с„шах ( Р<"+н (х) ( Ь"+', (42) х где с„— некоторая константа. Отсюда заключаем, что при Ь-» 0 ошибка убывает как Ь"". 20 Зависимость величины ошибки от степени интерполяцнонного полинома а более сложная.
На практике интерполяционные формулы со сколько-нибудь большим и употребляются крайне редко. Причины этого следующие. Во-первых, как видно из (42), увеличение степени поли- нома может привести к уменьшению ошибки интерполяции лишь для очень гладких функций, имеющих достаточно большое число производных. Но такой информацией о свойствах Р (х) мы, как правило, не обладаем. Вовторых, зачения ~» являются всегда приближенными значениями для Р (х„), хотя бы иа-аа округления. Поэтому полиномы, построенные по ~а и Р (ха), в лучшем случае будут отличаться друг от друга на величину порядка у„— г" (х„). К тому же ошибки, содержащиеся в ~, носят всегда случайный характер, а это можно интерпретировать как сильную негладкость представляемой ими функции.
Описанный способ восстановления функции Р (х) по таблице х„, ~„путем построения интерполяционного полинома не является единственно возможным. Мы строили Р„(х) (34) с помощью системы степенных функций х (т = 0,1, ...). Но для атой цели годятся и многие другие системы у (х). В этом случае вместо (34) следует рассмотреть Ф„(х) =,~~~~ а $ (х) (43) и проиавести соответствующее исследование возможности и качества аппроксимации. Можно идти еще дальше— конструировать аппроксимирующую функцию в виде какой-либо нелинейной комбинации опорных функций р (х). Но, разумеется, это имеет смысл делать только при достаточно обоснованной необходимости, так как выигрыш на этом пути может достигаться лишь за счет сужения области применимости метода и использования существенной дополнительной информации о Р (х), кроме таблицы ее значений.
К вопросу о восстановлении функции по набору ее значений можно подойти и по-другому. При построении интерполяционной функции мы требовали точного совпадения ее значений в узлах х„с ~„. Но часто можно ограничиться требованием минимальности отклонения этих значений оттабличных. Например, если ~ заведомо содержат значительные ошибки, или простой вид аппроксими- рующбй функцйи дйя нас важнее точности аппроксимации, то такой подход аакономерен. Опишем один из способов такого рода — оноооб наименьших квадратов. Имеем таблицу хк, ~к (й = О, $, ..., п). Требуется построить функцию м Фм(х) =,~~~ а Ч> (х), (44) — о где ор (х) — заданная система функций (например, ср (х) = х ), так, чтобы величина Х (Фм (хк) — Ук)о = Ь (45) была минимальной.
Если М к п, то задача решается построением интерполяционной функции (44), для которой б = О. Нас интересует случай М ( и. Весь произвол заключается в выборе коэффициентов а„а, ..., ам, поэтому Ь есть функция от них. Для нахождения минимума функции Ь (а, а„..., ам) приравняем нулю производные этой функции по а, ак, ..., ам — получим систему уравнений м а В ,Я~ а,,'!~~ Ч~,„(хк)'р1 (хк) = Х Ф„(хк)1» л»=О,(,...,М. ~=о к=о к-о Решив эту систему линейных уравнений, найдем значения а„а„..., ам, полностью определяющие функцию Фм (х) (44), которая наилучшим образом среди функций этого вида аппраксимирует таблицу хк, /к, если за меру отклонения принять (45).
Остановимся на некоторых применениях полученных результатов. Тот или иной способ соответствия между таблицей и функцией дает возможность совершать над таблицей различные функциональные операции — интегрирование, дифференцирование. Так, если требуется вычислить интеграл от функции, заданной таблицей хк, ~» (й = О, $, ..., К), то используя на каждом интервале (хк, хо+») формулу линейной интерполяции (ЗЗ), будем иметь *кок Рк( ) Йх = (хкы — хк). ((б) ~к+)к+ Суммируя эти выражения по всем интервалам, получаем способ вычисления интеграла.
Для случая, когда шав таблицы постоянен, хзег — хз = Ь, имеем хк 1 ~ Р,()й.= ( —,~.+~.+~.+...+~ + —,~ ) Ь (47) — известную кеадратурную формулу трапеций. Можно оценить точность, с которой формула (47) дает величину интеграла от функции Р (х). Ошибка интерполяции в силу (41) при п = 1 есть з(х) =- — Р" ($(х))(х — х„)(х — хьы), х„~х (хе+,. (48) Отсюда "з+1 ! е (х) е(х ~ (сопзВ шах ~ Р" ~ (хьп — хз)з. хз хз~х ~»зы Суммируя это неравенство по всем интервалам, учитывая, что КЬ = хк — хо, получим хк ~ е(х) дх~~сопзВ шах )Р ~Ьз, (49) е»ах»лк т. е. формула трапеций (47) имеет точность порядка Ь'.
Используя другие интерполяционные функции Р, (х), Р, (х) и т. д., получим квадратурные формулы прямоугольников, Симпсона и т. д. Столь же просто решается вопрос о вычислении производных от табличной функции. Используя, например,линейную интерполяцию (33), получим ае ар~ ~а+1 1з — — х„» х(х„ы. (50) т+1 з Дифференцируя выражение для ошибки интерполяции (43), имеем ое т — = — Р"' (з (х)) $' (х) (х — хз) (х — хьы) + + — Р' (з (х)) (2 — — „„). Второе слагаемое в правой части порядка х„+, — х„, т. е. й. Такова точность вычисления производной по формуле (50). Исключением является центральная точка интервала х = (х„+ х„+,)/2. В ней второе слагаемое обращается в нуль и, следовательно, формула (50) дает значение производной в этой точке с точностью йэ.
Попытка определения с помощью линейной интерполяции второй производной приводит к оэР езР1 — — — =0 лзз охэ что, очевидно, непригодно. Это согласуется с тем, что овс — „,, = Р" Я (х)) +..., т. е. ошибка конечна, не убывает с уменьшением Ь. Для вычисления старших производных необходимо использовать интерполяцию более высокой степени. Мы рассмотрели только случай функции одного переменного. При переходе к многомерным задачам принципиальная сторона изложенных методов сохраняется, но появляется масса новых проблем.