Интерполяционная схема Эйткена

Пусть функция f(x) и расположение узлов x₀, x₁, …, x_n на отрезке интерполяции [a, b] таковы, что имеет место сходимость процесса интерполяции, т.е. R_n(x) ® 0 при n ® ¥. Пусть требуется найти не общее выражение L_n(x), а лишь его значения при конкретных x, т.е. решается частная задача вычисления отдельных приближенных значений функции f(x) с помощью вычисления соответствующих им значений интерполяционного многочлена Лагранжа L_n(x). Для построения эффективного способа решения такой частной задачи интерполяции учтем следующее:

1) использование многочлена Лагранжа в виде (2.3) неудобно из-за его громоздкости, что ведет к большим вычислительным затратам;

2) заранее не известно, многочлены какой степени нужно использовать для интерполирования данной функции с требуемой точностью. А постепенное улучшение точности за счет вычислений L_n(x) с большим показателем степени n невыгодно, т.к. L_n-1(x) плохо перестраивается в L_n(x);

3) функция f(x) задается таблицей своих приближенных значений. Процесс сходимости L_n(x) к f(x) при больших значениях n будет нарушен влиянием на результат исходных ошибок.

Построим вычислительную схему для получения приближенного значения сеточной функции f(x) в заданной точке , в основу которой будет положена интерполяция Лагранжа на сетке узлов x₀, x₁, …, x_n. Организация вычислений по этой схеме будет иметь итерационный характер. Каждый шаг заключается в вычислении некоторого определителя второго порядка.

Пусть даны две точки на кривой y=f(x): (x₀, y₀) и (x₁, y₁). Построим функцию P_0,1(x):

.

.

Т.е. P_0,1(x) совпадает с интерполяционным многочленом Лагранжа первой степени, построенным по двум данным точкам (сравните с 2.3).

Построим через определитель функцию P_1,2(x) для точек (x₁, y₁), (x₂, y₂):

.

.

Она тоже является многочленом Лагранжа первой степени, построенным по двум точкам (x₁, y₁) и (x₂, y₂).

Если на кривой y=f(x) заданы три точки (x₀, y₀), (x₁, y₁), (x₂, y₂), то, используя введенные линейные функции P_0,1(x) и P_1,2(x) образуем новую функцию:

.

Покажем, что эта функция есть многочлен второй степени. Учитывая, что

P_0,1(x₀)=P_1,2(x₁)=y₀,

P_0,1(x₁)=y₁, P_1,2(x₂)=y₂,

подставляя в P_0,1,2(x) поочередно значения x=x₀, x₁, x₂, получим:

P_0,1,2(x₀)=y₀; P_0,1,2(x₁)=y₁; P_0,1,2(x₂)=y₂.

Т.о., функция P_0,1,2(x) – это многочлен второй степени, решающий задачу параболической интерполяции по трем точкам (x₀, y₀), (x₁, y₁), (x₂, y₂). Но такой многочлен единственный, следовательно, P_0,1,2(x)=L₂(x), где L₂(x) – многочлен Лагранжа.

Продолжая процесс рассуждения, получим рекуррентное задание последовательности интерполяционных многочленов Лагранжа, которое составляет суть интерполяционной схемы Эйткена:

, (3.1)

где i=1, 2, …, n и по определению P₀(x)=y₀, P₁(x)=y₁.

Схема Эйткена легко реализуется на ЭВМ. Организация вычислений по формуле (3.1) должна быть такова, что если заранее неизвестна степень интерполяционного многочлена, который нужно использовать для вычисления y(x), то должно происходить постепенное повышение степени k интерполирующих ее многочленов за счет подключения новых узлов. Счет ведется до тех пор, пока идет уточнение приближенного значения y(x).

Об этом можно судить по уменьшению величины |P_{i, i+k-1}(x)-P_{i, i+k}(x)| при увеличении k и подходящем фиксировании i.

Пример. Пусть некоторая функция y=y(x) задана таблицей своих значений, округленных до двух знаков после запятой:

xi	0.0	0.2	0.4	0.6	0.8	1.0	1.2	1.4
yi	1.00	1.02	1.08	1.12	1.34	1.54	1.81	2.15

Рассмотрим процесс вычисления двух значений этой функции по схеме Эйткена в точках: а) ; б) . Результаты промежуточных вычислений (в которых один знак запасной) сведем в табл. 3.1, 3.2. Числа в столбцах, помеченных посредством , представляют собой значения многочленов Лагранжа k -ой степени, построенных по узлам от i -го до (i+k) -го рекуррентно по формуле:

, (3.2)

где k=1, 2, …, , в соответствии с интерполяционной схемой Эйткена. Порядок получения этих значений показан проставленными в каждой клетке номерами.

Таблица 3.1.

Вычисление по схеме Эйткена значения y(0.1)

		1.00	1	1.01	3	1.005	6	1.001	10	0.991
	0.2	1.02	2	0.99	5	0.983	9	0.920
	0.4	1.08	4	1.02	8	1.358
	0.6	1.12	7	0.57
	0.8	1.34
	1.0	1.54
	1.2	1.81
	1.4	2.15

Таблица 3.2

Вычисление по схеме Эйткена значения y(0.25)

		1.00
	0.2	1.02	1	1.035	3	1.038	6	1.048
	0.4	1.08	2	1.050	5	1.169
	0.6	1.12	4	0.735
	0.8	1.34
	1.0	1.54
	1.2	1.81
	1.4	2.15

Процесс вычисления значений многочленов Лагранжа ведется до тех пор, пока идет уточнение приближенного значения , т.е. уменьшается величина при увеличении k и подходящем фиксировании i.

Например, для подсчета приближенного значения данной функции в точке , расположенной между узлами x₀=0.0 и x₁=0.2, целесообразно в качестве основной последовательности значений многочленов Лагранжа брать строку таблицы 3.1, соответствующую значению i=0, т.е. числа , и т.д.

Вычислив разности между последующими и предыдущими числами этой строки, а именно:

0.005 0.004 0.010,

видим, что дальнейший счет бессмыслен; разность перестала уменьшаться. Т.е. по данной информации о функции y(x) более точное значение y(0.1), чем y(0.1)=1.001, получаемое с помощью L₃(0.1), найти не удастся.

В случае б) вычисление по схеме Эйткена дает следующий результат: y(0.25)»1.038, полученный с помощью L₃(0.25).

ВАРИАНТЫ ЗАДАНИЙ НА ЛАБОРАТОРНУЮ РАБОТУ

"ИНТЕРПОЛЯЦИЯ"

Функция y=f(x) задана таблицей значений:

Вариант	x	5	10	15	20	25	30	35	40
	y	2,236	3,162	3,873	4,472	5,000	5,477	5,916	6,325
	y	1,710	2,154	2,466	2,714	2,924	3,107	3,271	3,420
	y	7,071	10,000	12,247	14,142	15,811	17,321	18,708	20,000
	y	3,684	4,642	5,313	5,848	6,300	6,694	7,047	7,368
	y	7,937	10,000	11,447	12,599	13,572	14,422	15,183	15,874
	y	0,200	0,100	0,067	0,050	0,040	0,033	0,029	0,025
	y	19,635	78,540	176,720	314,160	490,870	706,860	962,100	1256,600
	y	15,710	31,420	47,120	62,830	78,540	94,250	109,960	125,700
	y	1,609	2,303	2,708	2,996	3,219	3,401	3,555	3,689

Вариант	x	50	100	150	200	250	300	350	400
	y	0,087	0,174	0,259	0,342	0,423	0,500	0,534	0,643
	y	0,996	0,985	0,966	0,940	0,906	0,866	0,819	0,766
	y	0,088	0,176	0,268	0,364	0,466	0,577	0,700	0,839

Указания. Для вариантов 10 – 12 значения аргумента x предварительно перевести из градусов в радианы.

Даны контрольные значения аргумента x₁=12; x₂=26; x₃=42.

1. Написать подходящие для приближенного вычисления значений y₁=f(x₁), y₂=f(x₂), y₃=f(x₃) интерполяционные многочлены Лагранжа первой и второй степени. Получить эти значения.

2. Составить алгоритм и написать программу на языке высокого уровня, реализующую схему Эйткена вычисления с максимально возможной точностью значения y=f(x) в произвольной точке x промежутка
[x₀, x_n+(x_n-x_n-1)]. Пользуясь этим алгоритмом, вычислить приближенные значения y₁, y₂, y₃.

3. Сделать анализ результатов заданий 1, 2.

СОДЕРЖАНИЕ ОТЧЕТА ПО ЛАБОРАТОРНОЙ РАБОТЕ

В отчете по лабораторной работе должны быть представлены следующие разделы:

1. Постановка задачи.

2. Математическая модель.

3. Текст программы.

4. Результаты работы.

5. Выводы.

Лабораторная работа выполняется на любом языке высокого уровня.

Отчет по лабораторной работе, включая рукописный текст программы, без результатов работы, предварительно должен быть представлен преподавателю до выхода на компьютер.

СПИСОК ЛИТЕРАТУРЫ

1. Вержбицкий В.М. Численные методы (математический анализ и обыкновенные дифференциальные уравнения). – М.: Высшая школа, 2000.

2. Демидович Б.П., Марон И.А. Основы вычислительной математики. – М.: Наука, 1970.

3. Брадис В.М. Вычислительная работа в курсе математики средней школы.– М.: Изд. АПН РСФСР, 1962.