Интерполяция многочленами .

                                  Введение
    Если задана функция y(x),  то  это  означает,  что  любому  допустимому
значению х сопоставлено значение у. Но нередко оказывается,  что  нахождение
этого значения очень трудоёмко. Например, у(х)  может  быть  определено  как
решение  сложной  задачи,  в  которой  х  играет  роль  параметра  или  у(х)
измеряется в дорогостоящем эксперименте. При этом можно вычислить  небольшую
таблицу значений функции, но прямое нахождение  функции  при  большом  числе
значений  аргумента  будет  практически  невозможно.  Функция   у(х)   может
участвовать  в  каких-либо  физико-технических  или   чисто   математических
расчётах, где её приходится многократно вычислять.  В  этом  случае  выгодно
заменить функцию у(х) приближённой формулой,  то  есть  подобрать  некоторую
функцию  ((х),  которая  близка  в  некотором  смысле  к   у(х)   и   просто
вычисляется. Затем при всех значениях аргумента полагают у(х)(((х).
    Большая  часть  классического  численного   анализа   основывается   на
приближении многочленами, так как с ними легко работать. Однако  для  многих
целей используются и другие классы функций.
    Выбрав узловые точки  и  класс  приближающих  функций,  мы  должны  ещё
выбрать одну определённую функцию из  этого  класса  посредством  некоторого
критерия — некоторой меры приближения  или  «согласия».  Прежде  чем  начать
вычисления, мы должны решить также, какую точность мы хотим иметь  в  ответе
и какой критерий мы изберём для измерения этой точности.
    Всё изложенное можно сформулировать в виде четырёх вопросов:
    1. Какие узлы мы будем использовать?
    2. Какой класс приближающих функций мы будем использовать?
    3. Какой критерий согласия мы применим?
    4. Какую точность мы хотим?
    Существуют 3 класса или группы функций, широко применяемых в  численном
анализе. Первая группа включает в себя линейные  комбинации  функций  1,  х,
х2, …, хn, что совпадает с классом всех многочленов степени n (или  меньше).
Второй класс образуют функции cos aix, sin aix. Этот класс  имеет  отношение
к рядам Фурье и интегралу Фурье. Третья группа  образуется  функциями  e-az.
Эти функции встречаются в реальных  ситуациях.  К  ним,  например,  приводят
задачи накопления и распада.
    Что касается критерия  согласия,  то  классическим  критерием  согласия
является  «точное  совпадение  в  узловых  точках».  Этот   критерий   имеет
преимущество простоты теории и выполнения вычислений,  но  также  неудобство
из-за  игнорирования  шума  (погрешности,  возникающей  при  измерении   или
вычислении значений в узловых точках). Другой относительно хороший  критерий
— это «наименьшие квадраты». Он означает, что сумма квадратов  отклонений  в
узловых точках  должна  быть  наименьшей  возможной  или,  другими  словами,
минимизирована.  Этот  критерий  использует  ошибочную   информацию,   чтобы
получить некоторое сглаживание шума. Третий критерий  связывается  с  именем
Чебышева. Основная идея его состоит  в  том,  чтобы  уменьшить  максимальное
отклонение до минимума. Очевидно, возможны и другие критерии.
    Более конкретно ответить на поставленные 4 вопроса можно лишь исходя из
условий и цели каждой отдельной задачи.

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

  Методы интерполяции Лагранжа и Ньютона
    Один из подходов к задаче интерполяции — метод Лагранжа. Основная  идея
этого метода состоит в том, чтобы  прежде  всего  найти  многочлен,  который
принимает значение 1 в одной  узловой  точке  и  0  во  всех  других.  Легко
видеть, сто функция
      
является требуемым многочленом степени n; он равен 1, если x=xj и  0,  когда
x=xi, i(j. Многочлен Lj(x)(yj принимает значения yi в i-й  узловой  точке  и
равен 0 во всех других узлах. Из этого следует,  что    есть  многочлен
степени n, проходящий через n+1 точку (xi, yi).
    Другой подход — метод Ньютона (метод разделённых разностей). Этот метод
позволяет получить аппроксимирующие значения функции без построения в  явном
виде аппроксимирующего полинома. В результате получаем формулу для  полинома
Pn, аппроксимирующую функцию f(x):
                P(x)=P(x0)+(x-x0)P(x0,x1)+(x-x0)(x-x1)P(x0,x1,x2)+…+
                     (x-x0)(x-x1)…(x-xn)P(x0,x1,…,xn);

       — разделённая разность 1-го порядка;
       — разделённая разность 2-го порядка и т.д.
    Значения Pn(x) в узлах совпадают со значениями f(x)
    Фактически формулы Лагранжа и Ньютона порождают один и тот же  полином,
разница только в алгоритме его построения.

  Сплайн-аппроксимация
    Другой метод  аппроксимации  —  сплайн-аппроксимация  —  отличается  от
полиномиальной  аппроксимации  Лагранжем  и  Ньютоном.  Сплайном  называется
функция, которая вместе с несколькими  производными  непрерывна  на  отрезке
[a,  b],  а  на  каждом  частном  интервале  этого  отрезка  [xi,  xi+1]   в
отдельности являются некоторым многочленом невысокой  степени.  В  настоящее
время применяют кубический сплайн, то есть  на  каждом  локальном  интервале
функция приближается к полиному 3-го порядка. Трудности такой  аппроксимации
связаны с низкой степенью полинома, поэтому сплайн плохо аппроксимируется  с
большой первой производной. Сплайновая интерполяция  напоминает  лагранжевую
тем, что требует только значения в узлах, но не её производных.

  Метод наименьших квадратов
    Предположим, что требуется заменить некоторую  величину  и  делается  n
измерений, результаты которых равны xi=x+(i (i=1, 2, …, n),  где  (i  —  это
ошибки (или шум) измерений,  а  х  —  истинное  значение.  Метод  наименьших
квадратов утверждает, что наилучшее приближённое значение   есть  такое
число, для которого минимальна сумма квадратов отклонений от :
      
    Один из наиболее общих случаев применения этого метода состоит  в  том,
что имеющиеся n наблюдений (xi, yi) (i=1,  2,  …,  n)  требуется  приблизить
многочленом степени m