Н.Н. Калиткин - Численные методы (1133437), страница 8
Текст из файла (страница 8)
На все наши формулы рассчитаны на переменный шаг. Отметим, чта для достижения заданной точности прямая и обратная интерполяции требуют,'вообще говоря, разного числа узлов. Важный пример обратного интерполирования — решение уравнения у(х) =О. Вычислим несколько значений функции у(х,), т. е. составим небольшую таблицу. Запишем ее в виде х,=х(у;) и при помощи интерполяции найдем приближенное значение х(О). Этот способ дает хорошие результаты, если функция достаточно гладкая, а корень лежит между рассчитанными узлами. Если корень расположен далеко от узлов, то способ ненадежен, ибо применяется экстраполяция. П р и м е р. Решим уравнение у (х) = (1 + х) еа»' — 2,5 = О.
(12) Составим таблицу 4 значений функции; первым запишем столбец значений у, ибо в дальнейших вычислениях эта величина будет аргументом. Найдем разделенные разности и произведем вычисления по верхней косой строке: «(0) х»+(Π— у«)х(у„у,)+(Π— у,)(0 — у,)х(у».
ум у»)=О 744. 1ачнае решение есть х(О) =0,732, так что ошибка получилась АППРОНСИМАЦИЯ ФУИКЦИГ1 небольпюй. Для повышения точности вэтом способе целесообразно взять новые узлы, близко расположенные к грубо найденному корню, а не увеличивать число узлов. Таблица 4 у, ) к (р, у 1) к оь, р„уп — 1,500 ~ 0 0,540 -О,О7о — 0,5?4 0,797 йо В этом курсе будут рассмотрены и другие примеры прилгенения интерполирования. б.
Интерполяциоиный многочлен Эрмита. Пусть табулирована не только функция, но и ее производные вплоть до некоторого порядка. Тогда можно потребовать, чтобы в узлах интерполяции совпадалн не только значения искомой функции р(х) и интерполяционной функции ср(х), но и значения их производных вплоть до некоторого порядка.
Такую интерполяцию будем называть зрмилдовай; если гр (х) — алгебраический многочлен а-й степени, то он называется интерполяционным многочленом Зрмита и обозначается Л'л(х). Покажем, как построить этот миогочлен'. По л+ 1 узлу построим интерполяциоиный многочлен Ньютона Ф:, (х; х„х„..., хл). Поскольку значения функции р(х) и многочлена в узлах совпадают, то их средние наклоны на участках между узлами равны. Мысленно будем приближать узел хл к узлу хл,; при этом средний наклон будет стремиться к производной. Значит, после совпадения узлов получим многочлен, который в узле х„, правильно передает не только значение функции, но и значение первой производной. Символически обозначим его как сл'л(х, х„ х,, ... ° ° ° 1 Хл-1~ Хл 1) ) Слияние трек узлов в один обеспечивает передачу не только наклона, но и кривизны„т. е.
первой и второй производных и т. д. Таким образом, многочлен (х) Ул (х' хо хе~, ~ хз~ хд хд 1 кд хр хр хр) (13) л| гл гл Р Р ~ч '„лде = и+ 1, л=о ') Чтобы отлнчагь его обозначенле от разделенной разности, мы отделяем аргумент от узлов, по которым составлен многочлен, точкой с запятой. ИИТЕРПОЛИРОВАНИЕ 37 Очевидно, если сетка имеет шаг 11, а точка х лежит между край- иил(и узлами интерполяции, то 11„(х) =0(й""); следовательно, порядок точности эрмитовой интерполяции равен и+ 1, т.
е. числу коэффициентов интерполяционного многочлена. Заметим, что обычный многочлен Ньютона с таким же числом коэффициентов (т. е. той же степени) также имеет погрешность 0(й"!'). Однако на одной и той же сетке численная величина погрешности многочлена Ньютона будет больше, чем у много- члена Эрмита: его вспомогательньш многочлеи (э„(х) содержит больше узлов, чем Й„(х), и поэтому. в него входят ббльшие сомно- жители. Очевидно также, что чем более высокие производные используются при построении интерполяционного многочлена Эрмита заданной степени, тем меньше требуемое число узлов, и тем меньше будет численная величина его погрешности (хотя порядок точности остается одним и тем же). Выражением (13) нельзя пользоваться буквально. Если фор- мально подставить в формулу Ньютона (8) совпадающие узлы, то потребуется вычислить разделенные разности, у которых неко- торые узлы являются кратными.
Выражения (6) для таких раз- ностей содержат неопределенность типа О/О. Если кратность каж- дого узла не больше чем двойная, то эту неопределенность можно раскрыть с помощью предельного перехода, например, у («„) — у («,) у (х„х„) = ! пп = у (х,), «р О ! у (х„х„х,) = [у' (х,) — у (хм х!)], (15) у (х„х„х„х,) = (, [у' (х,) — 2у (х„х,) + у' (х!)].
Если узлы имеют более высокую кратность, то удобнее дифферен- цировать формулу Ньютона (8). Например, если ее продифферен- цировать т — 1 раз, то обратятся в нуль все члены, содержащие разделенные разности порядка меньше т — 1. Затем положим х=х,=х,=...; тогда обратятся в нуль множители перед разде- ленными разностями порядка больше т — 1, и мы получим н(ъ *.." . ~(= и'" "((. 1 ( — ц (16) в узле хь правильно передает значение функции и ее производных вплоть до порядка и„— 1 и имеет минимально необходимую для этого степень.
Оценка погрешности метода (1О) в этом случае принимает следующий вид: Р (у (х) — Л „(х) (:= ( "' !. (Я„(х) ~, й„(х) = П (х — х«) А. (14) А=О лпппоксимлция оинкции 1гл, и Но узлы более чем двойной кратности почти не встречаются в практике вычислений, ибо вторые и более высокие производные искомой функции редко табулируются. Рассмотрим наиболее употребительные частные случаи интерполяцнонного многочлена Эрмита.
Первый случай — многочлен, который в одном узле х, совпадает с функцией и всеми ее заданными производными: уз„(х; хо, х,,) = =У(хо)+(х хз)У (хз)+ 2 (х хз) У (хз)+ ° ()г) Очевидно, это отрезок ряда Тейлора; в этом случае ьз„(х) = = (х — х,)"", и оценка (11) переходит в известную оценку точности ряда Тейлора.
Второй случай — многочлен, передающий в двух узлах значения функции и ее первой производной: У„(х; хо, х„х„х,) =у(х,)+(х — х,) (у'(х,)+ + (х хз) [у (хо хо хг) + (х хг) у (хз хе хт хт)1«)' (18) разделенные разности сюда надо подставить из соотношения (15). Функция »1„(х) = (х — х,)'(х — х,)' внутри интервала интерполирования не превышает ()ту2)з, так что погрешность формулы (18) не более 0,028М»Ь', эта формула имеет четвертый порядок точности. для сравнения приведем без вывода общее выражение интсрполяционного многочлена Эрмита я о» вЂ” ! а» ' '" » о«г=о з-о Х И (х — хг] г — И(х — хт) М""' и ).» /,.й ««», Оно настолько громоздко, что пользоваться им для вычислений практически невозможно. Если все г«; = 1, то обе внутренние суммы превращаются в одно слагаемое с т= о=о, и мнегочлен Эрмита переходит в многочлен Ньютона в форме Лагранжа, Если все сс;=2, то получим Р I з еЯ"з(х)= р (х — х») р»+,' 1 — 2 7 — » р» и ( «н х» — хг »=з~ !=о г=з сй» 'с - » можно провери~ь, что в случае двух узлов последнее выражение совпадает с (18) с точностью до формы записи.
Но даже и зто выражение оказывается очень громоздким. Такая ситуация довольно часто встречается в прикладной математике, Общие формулы, рассчитанные на все случаи жизни, нередко оказываются настолько сложными, что их не применяют ИНТЕРПОЛИРОВАНИЕ ни в одном конкретном случае. К тому же, в практических расчетах, как мы увидим далее, нецелесообразно использовать многочлены высоких степеней, поэтому в общих формулах нет серьезной необходимости. Трудоемкость же вычислений часто оказывается существенно меньшей при применении рекуррентных процедур типа формулы разделенных разностей (6).
7, Сходнмость интерполяции. При каких условиях погрешность метода стремится к нулю, т. е. когда и как интерполяционный многочлен сходится к у(х)? На практике мы имеем два способа перехода к пределу. Первый состоит в том, чтобы, сохраняя степень интерполяцнонного многочлена, уменьшить шаг сетки, т. е.
воспользоваться более подробными таблицами. Второй — сохраняя шаг сетки, увеличивать число используемых узлов, т. е. увеличивать степень многочлена. Уменьшение шага. Если у(х) имеет непрерывные производные вплоть до и+ 1-й, то при интерполяции многочленом У„(х) степени т.==п погрешность метода есть 0(Ь "'). В этом случае при фиксированной степени многочлена и уменьшении шага сетки погрешность ~у(х) — д' (х) ~ неограниченно убывает. Если ограничена производная, входящая в оценку ошибки, то интерполяционный многочлен равномерно сходится к у(х) на ограниченном отрезке а(х~Ь. Строго говоря, для каждого значения х выбирают свои узлы интерполяции, ближайшие (на данной сетке) к точке х, т. е. составляют свой многочлен л' (х).
При этом точка х заведомо лежит между крайними узлами интерполяции, используемыми в данном многочлене. Поэтому входящий в оценку погрешности (10) полипом ьь„(х) ограничен равномерно по Ас ) ьь (х) 1( шахах-х;~ ~'.=.(Лй)"'а', где л — шаг сетки (для неравномерных сеток — максимальный шаг). Для заданной точности е определим шаг сетки нз условия М ь,(тй) "'(е (т+1)!, где М,=шах~у'"аи(х) ~.