INFONKO.RU

Интерполяционный многочлен Эрмита

Пусть на отрезке [a;b] задана совокупность точек t1; t2; … tn (необязательно равномерно), и пусть задана гладкая непрерывная функция f(t), и пусть известны значения произвольных от функции в заданных точках до некоторого порядка: f’(t1); f’(t2); … f’(tn).

Тогда алгебраический многочлен H(t) – интерполяционный многочлен Эрмита, если в узлах интерполирования совпадает не только значение f(t) и H(t), но и значения их производных до некоторого порядка.

f(ti) = H(ti)

f’(ti) = H′(ti)

f’’(ti) = H″(ti)

Многочлен Эрмита можно получить на основании многочлена Ньютона. При этом многочлен Эрмита будет иметь минимальную для этого степень.

Сравнивая оценку погрешности многочленов Ньютона и Эрмита, получим, что порядок точности обоих многочленов равен (n+1), но численная величина погрешности у многочлена Ньютона больше.

Если сетка равномерная, то введем шаг h = ti+1 - ti , .

В этом случае погрешность интерполирования приблизительно равна hn+1 (при условии h<1).

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

Интерполирование сплайнами

Это новое направление в теории интерполирования – наилучшее средство построения гладких восполнений сеточных функций на заданных классах функции.

Пусть нам задан отрезок [a; b], и на нем своими значениями задана f(t) (в узлах интерполяции).

Разобьем данный отрезок на частичные отрезки - границы частичных отрезков.

На каждом частичном отрезке строим свой интерполяционный многочлен.

С увеличением числа частичных отрезков точность увеличивается.

Такое интерполирование – кусочный многочлен (кусочно-полиномиальное).

Sm(t) – многочленный (полиномный) сплайн степени m дефекта гладкости k ( 0

1. Sm(t) имеет на [a; b] непрерывные производные до (m-k)го порядка включительно.

2. На каждом частичном отрезке Sm(t) – многочлен степени не выше m. Точки - узлы сплайна.

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

При построении многочленов на частичных участках некоторые коэффициенты многочленов выбираются произвольно ( количество условий меньше количества коэффициентов).

В технике наиболее употребительны сплайны, являющиеся многочленом третьей степени (кубические сплайны).

Интерполяция сплайнами целесообразно применять, когда сетка недостаточно подробна для Лагранжа или Ньютона, но не настолько редка, чтобы можно было применять нелинейную интерполяцию.

Если интерполяционная функция меняется резко за один шаг сетки, то интерполирование сплайнами не дает хорошей точности.



Сходимость интерполяционного процесса.

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

Сходимость интерполяционного процесса: ранее считали, что число узлов n зафиксировано. Рассмотрим последовательность сеток с разными числами узлов интерполирования.

Ωn (t1, t2, … tn) – совокупность точек на отрезке [a;b]; t1

Пусть сетка состоит из одной точки Ω1(t1). Построим полином P1(t).

Ω2 (t1,t2); P2(t)

Ω3 (t1,t2,t3); P3(t)

…………………

Ωn (t1,t2…tn); Pn(t)

Интерполяционный процесс сходится в t* є [a;b], если существует lim Pn(t*)=f(t*) – поточечное определение сходимости, при n→∞

Чем больше узлов интерполирования, тем меньше погрешность.

Кроме поточечной рассмотрим равномерную сходимость на [a;b]:
max

Свойство сходимости интерполяционного процесса зависит как от выбора последовательности сеток, так и от гладкости f(t). Существуют функции, для которых интерполяционный процесс расходится.

Например:

1. последовательность интерполяционных многочленов построена для непрерывной по равностоящим узлам на t є [-1;1] не сходится к ни в одной точке отрезка [-1;1] кроме точек –1; 0; 1.

2. Функция для которой многочлен не сходится, функция Рунге -

Теорема Марцинкевича: для заданной непрерывной функции можно добиться сходимости интерполяционного процесса за счет выбора расположения узлов интерполяции; если f(t) непрерывна на [a;b], то найдется такая последовательность сеток, для которых интерполяционный процесс равномерно сходится на [a;b].

Стоить такие последовательности сложно, следовательно, на практике избегают пользоваться интерполяционными многочленами высокой степени. Вместо этого используют кусочно-полиномиальное интерполирование (сплайнами).

Выбор узлов интерполирования

В тех случаях, когда узлы интерполирования не заданы, возникает вопрос, как выбирать эти узлы, чтобы минимизировать погрешность.

Проанализируем формулу остаточного члена полинома Лагранжа:

Один из множителей, входящий в эту формулу зависит от свойств f(t) и не поддается регулированию.

ωn(t) = (t-t1)(t-t2)…(t-tn) – зависит только от выбора узлов.

Если сконцентрировать эти узлы около одного из концов данного отрезка, то погрешность будет большая. Надо выбирать так, чтобы погрешность была минимальная.

Эта задача была решена П.Л. Чебышевым. Он доказал, что наилучший выбор узлов интерполирования определяется формулой:

, где

, i = 0, 1, 2, …n

- корни полиномов Чебышева.

Полиномы Чебышева:

Tn+1(t)=2tTn(t) – Tn-1(t)

T0(t)=1

T1(t)=t

T2(t)=2t2-1

T3(t)=4t3-3t

T4(t)=8t4-8t2+1

……………

Эти полиномы попеременно четные и нечетные. При таком выборе узлов ωn(t)=min.

Такие узлы интерполирования не равностоящие. Сгущаются около концов отрезка.

Практическая часть

1. Программная реализация алгоритма интерполирования с использованием интерполяционного полинома Лангранжа

1. #include "stdafx.h"

2. #include

3. #include

4. #include

5. #include

6. using namespace std;

8. double lagrange(double* t, double* f,int n, double at);

11. int main (int argc, char *argv[])

12. {

13. setlocale(LC_ALL, "Russian");

14. int n;

15. int z;

16. double c, d;

17. double h, r;

18. int i;

20. cout << "Введите количество узлов:";

21. cin >> n;

23. double *t = new double[n];

25. cout << "отрезок интерполирования:";

26. cin >> c;

27. cin >> d;

29. //cout << "\n c = " << c << "\n d = " << d << "\n";

30. h = (d - c) / (n - 1);

32. t[0] = c;

33. t[n-1] = d;

35. for (i = 1; i < n-1; i++) {

36. t[i] = t[i-1] + h;

37. }

40. double *f = new double[n];

41. for (i = 0; i < n; i++) {

42. f[i] = exp(-2*t[i]);

43. }

45. cout << "Введите шаг:";

46. cin >> r;

47. z = fabs((d - c)/r);

49. double *fi = new double[z];

50. double *at = new double[z];

51. cout << setprecision(10);

52. at[0] = c;

53. at[z-1] = d;

55. for (i = 1; i < z-1; i++) {

56. at[i] = at[i-1] + r;

57. }

59. cout << "\n"<<"Значения функции"<<"\n";

60. for (i = 0; i < z; i++) {

61. fi[i] = exp(-2*at[i]);

62. cout << fi[i] << "\n";

63. }

64. cout << "\n" << "Значения полинома" << "\n";

65. for (i=0;i

66. cout << lagrange(t, f, n, at[i]) << "\n";

67. }

68. cout << "\n" << "Погрешность" << "\n";

69. double *pog = new double[z];

70. for (i = 0; i < z; i++) {

71. pog[i] = fabs(lagrange(t, f, n, at[i]) - fi[i]);

72. cout << pog[i] << "\n";

73. }

74. _getch();

75. return 0;

76. }

79. double lagrange(double* t, double* f,int n, double at)

80. {

81. double a,P;

82. P=0;

83. for (int i=0; i

84. a=1;

85. for (int j=0;j

86. if (j!=i)

87. a*=(at-t[j])/(t[i]-t[j]);

88. }

89. P+=a*f[i];

90. }

91. return P;

92. }

Максимальная погрешность при n = 8 равна:

max|f(t)-g(t)|=762655571e-007

Максимальная погрешность при n = 15 равна:

max|f(t)-g(t)|=776356839e-015



infonko.ru/okoteya-hvostataya-rozovoe-derevo.html infonko.ru/o-kotoroj-ti-dazhe-ne-podozreval.html infonko.ru/okrashivanie-koronok-zubov-v-zheltij-cvet.html infonko.ru/okrashivanie-londa-professional-1gr-23-rub.html infonko.ru/okrashivanie-wella-professional-1gr-38-rub.html infonko.ru/okraska-ofakturivayushimi-visokonapolnennimi-sostavami.html infonko.ru/okraska-vnutrennih-poverhnostej-obshie-svedeniya.html infonko.ru/okremi-polozhennya-shodo-zastosuvannya-mitnogo-rezhimu-reeksportu.html infonko.ru/o-krestovih-pohodah-pervij-krestovij-pohod.html infonko.ru/o-krestyanskom-fermerskom-hozyajstve.html infonko.ru/o-krishna-hranitel-zhivih-sushestv-ot-uchitelej-v-cepi-uchenicheskoj-preemstvennosti-ya-uznal-o-tom-chto-tot-kto-razrushaet-semejnie-uzi-na-veki-vechnie-poselyaetsya-v-adu.html infonko.ru/okruzhayushaya-sreda-i-eyo-vozdejstvie-na-rea.html infonko.ru/okruzhayushaya-sreda-i-zdorove-cheloveka.html infonko.ru/okruzhayushaya-sreda-marketinga.html infonko.ru/okruzhayushaya-sreda-marketinga-torgovli.html infonko.ru/okruzhayushaya-sreda-mestnaya-pogoda-smena-vremen-goda.html infonko.ru/okruzhayushij-mir-chelovek-i-priroda.html infonko.ru/okruzhnaya-gramota-knyazya-dm-pozharskogo-1612g.html infonko.ru/okruzhnogo-voenno-patrioticheskogo-festivalya.html infonko.ru/oksidnie-i-fosfatnie-zashitnie-plenki.html