Составить программу , используя интерполяционный многочлен Ньютона - Free Pascal
Формулировка задачи:
Помогите, пожалуйста.
Функция f=sin(x) задана таблично. Вычислить значение интерполяционного многочлена Ньютона для интерполирования назад в точке x=0.15, сравнить его со значением функции f(x) в данной точке. Узлы интерполирования приведены в таблице:
| x0 | x1 | x2 | x3 | x4 |
| 0 | 0.05 | 0.1 | 0.2 | 0.25 |
Интерполяционный многочлен Ньютона для случая неравноотсоящих узлов записывается с применением разделённых разностей.
Пусть функция f задана на (связном) множестве X, и фиксированы попарно различные точки
Тогда разделённой разностью нулевого порядка функции f в точке xj называют значение f(xj), а разделённую разность порядка k для системы точек
определяют через разделённые разности порядка (k-1) по формуле
в частности,
Обычно разделённые разности записывают в виде таблицы (пример для 5 узлов интерполяции):
С помощью разделённых разностей функции f для узлов (x0, ..., xn) можно записать как интерполяционный многочлен Ньютона «вперёд»:
так и интерполяционный многочлен Ньютона «назад»:
Преимущества интерполяционного многочлена Ньютона:
Хотя обе формулы ("вперёд" и "назад") по всем параметрам равноценны, целесообразно применять ту, для которой меньше разность между точкой интерполяции и точкой, в которой в конечной формуле вычисляется разделённая разность нулевого порядка, то есть, "вперёд", если x ближе к x0, и "назад", если x ближе к xn.
| Порядок разделённых разностей | |||||
| 0 | 1 | 2 | 3 | 4 | |
| x0 x1
x2x3
x4
|
f(x0) f(x1) f(x2)f(x3) f(x4) |
f(x0; x1) f(x1; x2) f(x2; x3)f(x3; x4)
|
f(x0; x1; x2) f(x1; x2; x3) f(x2; x3; x4) |
f(x0; x1; x2; x3) f(x1; x2; x3; x4)
|
f(x0; x1; x2; x3; x4) |
- для вычислений разделённых разностей требуется действий (деления), что меньше, чем в других алгоритмах;
- вычислять значения интерполяционного многочлена можно по схеме Горнера за O(n) действий (умножения);
- хранения требуют (n+1) узел и (n+1) разность, причём разности можно хранить (получить) в тех же ячейках, где были заданы значения f(xk), поскольку этот многочлен использует только верхнюю("вперёд") или только нижнюю ("назад") строку таблицы разделённых разностей, хотя для вычисления этой строки необходимы и все остальные элементы таблицы;
- по сравнению с интерполяционным многочленом Лагранжа упрощено добавление нового узла.
Решение задачи: «Составить программу , используя интерполяционный многочлен Ньютона»
textual
Листинг программы
const m = 4;
type arr = array [0..m] of extended;
const x: arr = (0, 0.05, 0.1, 0.2, 0.25); //узлы интерполяции
xp: extended = 0.15; //целевая точка
var f: arr; //разделённые разности
i, k: integer; //счётчик, порядок разделённых разностей
p, sx: extended; //Pn(x), sin(x)
begin
for i := 0 to m do f[i] := sin(x[i]); //вычисление разделённых разностей порядка 0
for k := 1 to m do //цикл по порядкам разделённых разностей
for i := 0 to m - k do //цикл вычисления всех разделённых разностей порядка k
f[i] := (f[i + 1] - f[i]) / (x[i + k] - x[i]); //вычисление разделённой разности порядка k
//вычисление интерполяционного многочлена Ньютона по схеме Горнера
p := f[0];
for i := 1 to m do p := p * (xp - x[i]) + f[i];
//печать результатов
writeln(' P(', xp:0:2, ') = ', p:20:17);
sx := sin(xp);
writeln('sin(', xp:0:2, ') = ', sx:20:17);
writeln(' Ошибка = ', p - sx:20:17);
readln
end.
Объяснение кода листинга программы
- Объявлены константы и типы переменных — m = 4 - количество узлов интерполяции — arr = array [0..m] of extended - массив для хранения узлов интерполяции — x = (0, 0.05, 0.1, 0.2, 0.25) - узлы интерполяции — xp = 0.15 - целевая точка — f = array of extended - разделённые разности — i, k = integer - счётчики для циклов — p, sx = extended - интерполяционный многочлен Ньютона и sin(x)
- Вычисление разделённых разностей порядка 0 — Цикл for i := 0 to m выполняет вычисление разделённых разностей порядка 0 для всех узлов интерполяции — f[i] = sin(x[i])
- Вычисление разделённых разностей порядка k — Цикл for k := 1 to m выполняет вычисление разделённых разностей порядка k для всех узлов интерполяции — Цикл for i := 0 to m — k выполняет вычисление разделённых разностей порядка k для всех узлов интерполяции — f[i] = (f[i + 1] — f[i]) / (x[i + k] — x[i])
- Вычисление интерполяционного многочлена Ньютона по схеме Горнера — p = f[0] — Цикл for i := 1 to m выполняет вычисление интерполяционного многочлена Ньютона по схеме Горнера — p = p * (xp — x[i]) + f[i]
- Печать результатов — Выводится значение интерполяционного многочлена Ньютона — Выводится значение sin(xp) — Выводится ошибка интерполяционного многочлена Ньютона (разница между p и sx)
- Ввод/вывод данных — Введены значения для узлов интерполяции (x) — Вычислены значения разделённых разностей порядка 0 (f) — Вычислены значения интерполяционного многочлена Ньютона (p) — Вычислены значения sin(x) (sx) — Выведена ошибка интерполяционного многочлена Ньютона (p — sx)
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д