Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 61
Текст из файла (страница 61)
Занумеруем узлы таблицы в следующем порядке: хо = 1.2, х1 = 1.3, хт = = 1.1, хз = 1.4, х4 = 1.0, т. е. в порядке возрастания расстояния до точки х = =- 1.23. Соответствующие этой нумерации разделенные разности приведены в табл. 11.8 (мы используем только подчернутые разности). Вычисления на 6-разрядной десятичной ЭВМ дают следующие значения: Ро(х) = 0.182322, Р1(х) = Ро(х) + Х(хо' х1) ы~(х) 0.182322 + + 0.80042'(1 23 — 1 2) ~ 0.206335 ео = 1 Р~(х) — Ро(х)! - 2,4 1О-г Рт(х) = Р~(х) + ~(хо, х1; хт) ыт(х) ~ 0.206335 — 0.3485(1.23 — 1.2)(1.23— — 1.3) ~ 0.207067, е~ = !РАЙ(х) — Рт(х) ~ = 7 3'10 ~.
Аналогично получаются значения Рз(х) 0.207020, ет = 4.7 10 ~, Р4(х) ~з ~ 0 207014 ез 6'10 е. Если бы задача состояла в определении значения 1п (1.23) с точностью е = = 10 4, то вычисления следовало бы окончить после получения ет < Результат был бы таким: 1п (1.23) Рт(х) ~ 0.2071. 321 Заметим, что в случае, когда величина ~ х„~ — х~ мала, а функция 1 достаточно гладкая, справедливо приближенное равенство 2. Интерполяция с использованием симы Эйтт<ена. Рассмотрим один из алгоритмов решения задачи интерполяции. Предполагается, что задана таблица значений функции ~ Требуется при заданном х вычислить с помощью интерполяции значение Г (х) с заданной точностью а либо с максимально возможной при имеющейся информации точностью.
Считается, что функция ~достаточно гладкая. Обозначим через Р< < «,< ...,<~ (х) интерполяционный многочлен степени т — 1 с узлами интерполяции х<,, хан ..., х . В частности, положим Р< <,> (х) = у<,, В этих обозначениях справедливо равенство В самом деле, правая часть представляет собой многочлен степени т + 1 — Й. Непосредственная проверка показывает, что этот многочлен совпадает с у; в точках х = х, для < = Й, Й+ 1, ..., т + 1 и, значит, по определению равен Р< < ...,и (х). Удобный и экономичный способ вычисления значения многочлена Р4х) = Р<о < „< (х), лежащий в основе рассматриваемого алгоритма, дает схема Э<1шкека'.
Она заключается в последовательном вычисле- нии с помощью формулы (11.56) элементов следующей таблицы: Таблица 11.9 Р< о> (х) = уо Р«>(х) = у< Р<ю(х) = уг Р< о,<> (х) Р< 1,2) (х) Р< о,<,т > (х) ;Р< о,<,...,ю (х) Р< -<,а) (х) Р«<> (х) — уа < Александр Крэг Эйткен (1895 — 1967) — английский математик. 322 Для решения поставленной задачи интерполяции прн заданном значении х узлы нумеруют в порядке возрастания их расстояния ~ х — х«~ до точки х. Затем последовательно вычисляют значения Р<(х), ео, Рг(х), е<, ..., Р„,<(х), е«<, .... Если при некотором <т< оказывается, что ен ~ е, то полагают У(х) н Р„(х).
Если же е,„> я для всех т, то полагают ~(х) и Р1(х), где Ь вЂ” степень, при которой достигается минимум оценки погрешности: еъ = ш1п ен. тЭО Пример 11.9. Для решения задачи из примера 11.8 воспользуемся схемой Эйткеиа. В этом случае (как и в примере 11.8) хь = 1.2, х1 = 1.3, хг = 1.1, хч = 1.4, х~ = 1.0. После завершения вычислений табл. 11.9 принимает следующий вид: Т а б л и ц а 11.10 0.182322 0.206335 0.262364 0.207020 0.203895 0.199814 0.095310 0.336472 0.206752 Подчеркнутые числа дают те же, что и в примере 11.8, значения Ръ(х), Ь = О, 1, 2, 3. Естественно, что теми же окажутся и значения е~,. Рп(х) =. Рп(хо + Ь1) = уо + — ~ 1 + — ~ Ф (1 — 1) + ~г„ (11.57) 3' ,~з„ ,и~ ну Многочлен (11.57) называется интерполяционным мноъочленои Нъютона с конечныли раэностя.ии для интерполяции вперед. Заметим, что в формуле (11.57) используются только конечные разности, расположенные в верхней косой строке табл.
11.2. Можно использовать конечные разности, расположенные и в нижней косой строке табл. 11.2, записав многочлен в виде интерполяционноъо .ино1очлена Ньютона с конечны ии раэностя ии для интерполяции наэад: 323 3. Интерполяционный многочлен Ньютона с конечными разностями. Пусть интерполируемая функция задана на таблице с постоянным шагом Ь (т. е. х; = хо + 1Ь, 1 = О, 1, ..., и). В этом случае, используя формулу (11.51) связи между разделенными и конечными разностями и вводя безразмерную переменную 1 = (х — хо)/Ь, многочлен Ньютона (11.52) можно записать в следующем виде: Ь2Уп 2 Рп(х) = Рп(хп+ аУ) = Уп+ 1~ Ч+ ~~ Ч Й+ 1) + (11,58) + — и: Д (Д+ 1НЯ+ 2) + ...
+ —, Ф И+ 1)...(Ч+ и -1). ~ Уп-в Дп1В Здесь в = (х — хп)/Ь. $11.10. Обсуждение глобалыюй полиномиалыюй интерполяции. Понятмв о кусочно-полиномиальной инте1июл лекции Пусть функция интерполируется на отрезке [а, 6]. Метод решения этой задачи с помощью интерполяции единым для всего отрезка многочленом Рп(г) называют юлобалъной полино.ииалъной интерполяцией. При первом знакомстве с интерполяцией этот подход кажется привлекательным.
В самом деле, неплохо иметь один многочлен, пригодный для приближения функции ~ во всех точках х Е [а, Ь]. В то же время известные результаты теории аппроксимации позволяют надеяться на то, что удасться приблизить функцию с любой требуемой точностью е с помощью соответствующего выбора степени многочлена и узлов интерполяции на отрезке [а, о]. Приведем один такой классический результат. Т е о р е м а 11.6 (аппроксимационная теорема Вейерштрасса').
Пусть функция 1 непрерывна на отрезке [а, в], То1да для любого а > О сУи1ествУет полино и Рп(х) степени и = и (ь) такой, что шах ]~(х) — Рп(х)] ( в. [а,Я Заметим, что теорема Вейерштрасса не дает конструктивного способа построения соответствующего многочлена. Несмотря на приведенные выше аргументы, существуют весьма веские причины, по которым глобальнан интерполяция многочленами высокой степени в вычислительной практике, как правило, не используется. Обсудим некоторые из этих причин. 1 Карл Теодор Вильгельм Вейерштрасс (1815 — 1897) — немецкий математик, один из основоположников современного математического анализа и теории аналитических функций. 324 иитерполя((конно(о массива — треугольной таблицы (о) о х()) х'') о х(г) х(г) х(г) о ( г х(п) х(п) х(п) х(п) ) г '" п в каждой строке которой все х(.") различны и х(.") е [а, Ь].
Вудем говорить, что при заданной стратегии выбора узлов мегпод интерполя(1ии сходится, если гпах ~~(х) — Рп(х) ~ - О при и а. [а, Ь] Рассмотрим сначала простейшую стратегию, состоящую в равномерном распределении на отрезке [а, Ь] узлов интерполяции, т. е.
в выборе х("' = а + (Л (1 = О, 1, ..., и), где Л = (Ь вЂ” а)/и. Следующий пример показывает, что такая стратегия не может обеспечить сходи- мость интерполяции даже для очень гладких функций. Пример 11.10 (и р н и е р Р у н г е(). Используем глобальную полиномиальную интерполяцию с равномерным распределением узлов для приближения на отрезке [-1, 1] следующей функции: 1 ~() =1+ 25~ (11.59) Вычисления показывают, что при больших и интерполяция дает превосходные результаты в центральной части отрезка. В то же время вопреки ожиданиям последовательность Рп(х) расходится при и ~ со для 0.73 ( ~ х~ 4 1.
Соответст- вующая иллюстрация приведена на рис. 11.5. ) Карл Давид Тольме Рунге (1856 — 1927) — немецкий физик и математик. 325 1. Сходимость при увеличи(ни числа узнав. Всегда ли можно добиться повышения точности интерполяции благодаря увеличению числа узлов (и соответственно степени и интерполяционного многочлена)? Хотя положительный ответ на этот вопрос напрашивается сам собой, не будем торопиться с выводами. Уточним постановку задачи.
Для того чтобы реализовать процесс интерполяции функции ~ многочленами возрастающей степени и, необходимо указать стратегию выбора при каждом п набора узлов интерполяции х'"), х("), ..., х(") . Такая стратегия задается указанием Рис 11.б Равномерное распределение узлов интерполяции для функции Рунге (11.59) оказалось неудачным. Однако проблема сходимости для зтой функции исчезает, если в качестве узлов интерполяции брать корни многочлена чебышева Т„,~(х). Существует ли единая для всех непрерывных на отрезке [а, Ц функций 1 стратегия выбора узлов ин- 326 3 а м е ч а н и е.
Практическая реализация стратегии выбора узлов интерполяции (11.43) возможна и оправдана в довольно редких случаях и просто невозможна тогда, когда приходится иметь дело с заданной таблицей значений функции. 2. Чувствительность интерполяционного многочлеиа к погрешностям входных данных. Помимо погрешности, которая возникает от приближенной замены функции 1 интерполяционным многочленом, возникает еще дополнительная погрешность, связанная с тем, что значения интерполируемой функции также задаются с погрешностью. Пусть заданные в узлах х; значения у,". содержат погрешности х;.
п Тогда вычисляемый по этим значениям многочлен Р„*(х) = Е у*1„(х) э'=о содержит погрешность (11.60) Р„( )-Р„*() =Е 1„(). >=о Например, при линейной интерполяции по приближенно заданным значениям справедливо равенство Р~(х) — Р, (х) = ~Йо(х) + х~1н(х)> где ~ Жорж Фабер (1877 — 1966) — швейцарский математик. терполяции, гарантирующая ее сходимость? Отрицательный ответ на этот вопрос дает следующая теорема. Т е о р е и а 11.7 (теорема Фабера'). Какова бм ни бмла стратеьия выбора узлов интерполяции, найдется непрерывная на отрезке [а, 6] функция ~ для которой гпах ] 1" (х) — Р„(х) ~ -~ оо при и ~ со. [а, о] Теорема Фабера отрицает существование единой для всех непрерывных функций стратегии выбора узлов интерполяции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
