Чем отличается полином лагранжа от полинома ньютона
Перейти к содержимому

Чем отличается полином лагранжа от полинома ньютона

  • автор:

3. Интерполяция

Пусть функция задана набором точек на интервале :

, , (3.1)

Задача интерполяции – найти функцию , принимающую в точках те же значения . Тогда, условие интерполяции:

(3.2)

При этом предполагается, что среди значений нет одинаковых. Точки называют узлами интерполяции.

Если ищется только на отрезке – то это задача интерполяции, а если за пределами первоначального отрезка, то это задача экстраполяции.

Задача нахождения интерполяционной функции имеет много решений, так как через заданные точки можно провести бесконечно много кривых, каждая из которых будет графиком функции, для которой выполнены все условия интерполяции. Для практики важен случай интерполяции функции многочленами:

, (3.3)

При этом искомый полином называется интерполяционным полиномом.

При построении одного многочлена для всего рассматриваемого интервала для нахождения коэффициентов многочлена необходимо решить систему уравнений, построенную на основе полинома (3.3). Данная система содержит уравнение, следовательно, с ее помощью можно определить коэффициент. Поэтому максимальная степень интерполяционного многочлена , и многочлен принимает вид

, (3.4)

3.2. Локальная и глобальная интерполяция

Если задан узел интерполяции, то на этих узлах можно построить один интерполяционный многочлен n-й степени, многочленов первой степени и большой набор многочленов степени меньше n, опирающиеся на некоторые из этих узлов.

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

Если функция интерполируется на отрезке с помощью единого многочлена для всего отрезка, то такую интерполяцию называют глобальной. В случае локальной интерполяции на каждом интервале строится отдельный интерполяционный полином невысокой степени.

3.3. Кусочно-линейная интерполяция

Простейшим и часто используемым видом локальной интерполяции является линейная (или кусочно-линейная) интерполяция. Она заключается в том, что узловые точки соединяются отрезками прямых (рис.3.1), то есть через каждые две точки и проводится прямая, то есть составляется полином первой степени:

, при (3.5)

Рис. 3.1. Кусочно-линейная интерполяция

Коэффициенты и разные на каждом интервале , и находятся из выполнения условий интерполяции на концах отрезка:

(3.6)

Из системы уравнений (3.6) можно найти коэффициенты:

, (3.7)

При использовании кусочно-линейной интерполяции сначала нужно определить интервал, в который попадает значение x, а затем подставить его в выражение (3.5), используя коэффициенты для данного интервала.

3.4. Кусочно-квадратичная интерполяция

В случае квадратичной интерполяции, для каждых трех узловых точек , , , строится уравнение параболы:

, при (3.8)

Рис.3.2. Кусочно-квадратичная интерполяция

Здесь коэффициенты , и разные на каждом интервале и определяются решением системы уравнений для условия прохождения параболы через три точки:

(3.9)

Из системы уравнений (3.9) можно найти коэффициенты:


(3.10)

3.5. Многочлен Лагранжа

При глобальной интерполяции на всем интервале строится единый многочлен. Одной из форм записи интерполяционного многочлена для глобальной интерполяции является многочлен Лагранжа:

(3.11)

где – базисные многочлены степени n:

(3.12)

То есть многочлен Лагранжа можно записать в виде:

(3.13)

Многочлен удовлетворяет условию . Это условие означает, что многочлен равен нулю при каждом кроме , то есть – корни этого многочлена. Таким образом, степень многочлена равна n и при обращаются в ноль все слагаемые суммы, кроме слагаемого с номером , равного .

Выражение (3.11) применимо как для равноотстоящих, так и для не равноотстоящих узлов. Погрешность интерполяции методом Лагранжа зависит от свойств функции , от расположения узлов интерполяции и точки x. Полином Лагранжа имеет малую погрешность при небольших значениях n (n<20). При больших n погрешность начинает расти, что свидетельствует о том, что метод Лагранжа не сходится (то есть его погрешность не убывает с ростом n).

Многочлен Лагранжа в явном виде содержит значения функций в узлах интерполяции, поэтому он удобен, когда значения функций меняются, а узлы интерполяции неизменны. Число арифметических операции, необходимых для построения многочлена Лагранжа, пропорционально и является наименьшим для всех форм записи. К недостаткам этой формы записи можно отнести то, что с изменением числа узлов приходится все вычисления проводить заново.

Кусочно-линейная и кусочно-квадратичная локальные интерполяции являются частными случаями интерполяции многочленом Лагранжа.

3.6. Многочлен Ньютона

Другая форма записи интерполяционного многочлена – интерполяционный многочлен Ньютона с разделенными разностями. Пусть функция задана с произвольным шагом, и точки таблицы значений пронумерованы в произвольном порядке.

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

(3.14)

Разделенные разности второго порядка определяются через разделенные разности первого порядка:

(3.15)

Разделенные разности k-го порядка определяются через разделенные разности порядка :

(3.16)

Используя понятие разделенной разности интерполяционный многочлен Ньютона можно записать в следующем виде:

(3.17)

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

Научный форум dxdy

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

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

Про полином Ньютона и Лагранжа

Про полином Ньютона и Лагранжа
26.05.2011, 22:23

Правильно ли я понимаю что для одинаковых функциях и с одинаковыми узлами Эти полиномы будут равны.И отличаются они только способом вычисления?

Re: Про полином Ньютона и Лагранжа
26.05.2011, 22:48

Заслуженный участник

Это — проблема терминологии, которая действительно не во всех книжках удачна. Не существует «многочлена Ньютона» и «многочлена Лагранжа». Существуют лишь многочлен в форме Ньютона и многочлен в форме Лагранжа. Грамотно — именно так. Сами же многочлены, естественно, совпадают.

И это — не просто придирка. В данном случае терминологическая неграмотность затушёвывает принципиальный факт — единственность интерполяционного многочлена (ну и смежные вопросы).

Страница 1 из 1 [ Сообщений: 2 ]
Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Интерполяция полиномами Лагранжа и Ньютона

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

Метод решения задачи

Полином Лагранжа

Представим интерполяционную функцию в виде полинома

где — полиномы степели n вида:

Очевидно, что принимает значение 1 в точке и 0 в остальных узлах интерполяции. Следовательно в точке исходный полином принимает значение
Таким образом, построенный полином является интерполяционным полиномом для функции на сетке .

Полином Ньютона

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

где — полиномы Лагранжа степени i ≤ n.
Пусть
. Этот полином имеет степень i и обращается в нуль при .
Поэтому он представим в виде:
, где — коэффициент при . Так как не входит в , то совпадает с коэффициентом при в полиноме . Таким образом из определения получаем:

Препишем формулу в виде

Рекуррентно выражая пролучам окончательную формулу для полинома:

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

Погрешность интерполирования

Поставим вопрос о том, насколько хорошо интерполяционный полином приближает функцию на отрезке [a,b].
Рассмотри м остаточный член:
, x ∈ [a, b].
По определению интерполяционного полинома
поэтому речь идет об оценке при значениях .
Пусть имеет непрерывную (n+1) производную на отрезке [a, b].
Тогда погрешность определяется формулой:
,
где ,
— точка из [a, b].
Так как точка наизвестна, то эта формула позволяет только оценить погрешность:

где
Из вида множетеля следует, что оценка имеет смысл только при . Если это не так, то при интерполяции используются полиномы низких степеней (n = 1,2).

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

Так как от выбора узлов завист точность интерполяции, то возникает вопрос о том, как их выбирать. С помощью выбора узлов можно минимизировать значение в оценке погрешности. Эта задача решается с помощью многочлена Чебышева [1]:

В качестве узлов следут взять корни этого многочлена, то есть точки:

Пример

В качастве примера рассмотрим интерполяцию синуса. Возьмем равномерную решетку x = [-3,-1.5,0,1.5,3];
Интерполяция полиномом Лагранжа:

Ошибка(максимальное отклонение от sin(x) на отрезке):0.1423
Интерполяция полиномом Ньютона:
Ошибка:
Возьмем решетку x с узлами в корнях полинома Чебышева= [-2.8531,-1.7632,0,1.7634,2.8532];
Интерполяция полиномом Лагранжа:

Ошибка: 0.0944
Интерполяция полиномом Ньютона:
Ошибка:

Рекомендации программисту

Выводы

Литература

  1. Самарский А.А. Гулин А.В. Численные методы 1989г.
  2. Костомаров Д.П., Фаворский А.П. Вводные лекции по численным методам

Смотри также

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Интерполяционный многочлен на произвольных функциях

Приветствую, уважаемые читатели! Сегодня предлагаю поразмышлять о следующей задачке:

Дано пар точек на плоскости . Все различны. Необходимо найти многочлен такой, что , где

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

«Почему окольными путями?» — спросите вы. Ответ традиционный: это статья является продолжением серии статей дилетантского характера про математику, целью которых является популяризация математического мира.

Процесс

Для начала стоит отметить, что некоторое кол-во интерполяционных многочленов уже, разумеется, существует. Оные полиномы как раз предназначены для решения искомой задачи. Среди них особенно известны такие как полином Лагранжа и Ньютона.

А также необходимо внести ясность, что такое «произвольные функции» (термин приходит из названия текущей статьи). Под ними понимается любая унарная функция, результат которой есть биективное отображение аргумента.

В рамках статьи предлагаю за такую функцию взять десятичный логарифм и следующие точки:

Представляя их на плоскости, должно получится нечто следующее:

image

Нетрудно заметить, что сейчас кол-во пар точек равно .

При решении данной задачи приходит на ум некая системы уравнений, где кол-во линейно-независимых строк равно . Что же это за система уравнений такая?

Давайте попробуем функцию записать в виде суммы десятичных логарифмов с коэффициентами про оных (да так, чтобы кол-во коэффициентов было равно ):

Аргументы при различные чтобы избежать линейной зависимости строк в будущем (можно придумать другие). А также, учитывая, что область определения функции как минимум (на основе заданных условием точек), мы таким образом обеспечиваем существование области значений для функции в этой области определения.

Так как нам известны пар точек, то обратимся к ним для того, чтобы построить следующую тривиальную систему:

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

Собственно решая данную систему относительно получим следующее решение:

На этом задача естественным образом подходит к концу, остается только записать это в единую функцию:

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

image

Также, ради наглядности, можно привести аппроксимированную систему решений:

Тогда аппроксимированный вид функции будет следующий:

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

Различные примеры

На десерт аналогично построим функцию в радикалах:

Составим систему уравнения для нахождения коэффициентов:

Её решение единственно и выглядит следующим образом:

Тогда готовая функция выглядит следующим образом:

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

image

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

Где — коэффициенты которые предстоит найти через систему уравнений (СЛАУ), а — некоторые функции, которые обеспечат линейную независимость при нахождении коэффициентов.

А дальше — по алгоритму выше, всё совершенно аналогично. Не забывая о том, что должны быть определены на заданных условием точках.

К примеру можно показать функцию, состоящую из полностью различных базовых функций:

Дабы удовлетворить заданному набору точек, коэффициенты будут в таком случае следующие (найдены строго по алгоритму из статьи):

А сама функция будет такой:

График же будет выглядит практически также как предыдущий (на области заданных точек).
Если хочется более «гладкий» график, то можно посмотреть в сторону факториальной формы, например такой:

Подставим оные в готовую функцию:

image

А также полюбуемся очень хорошим графиком:

Зачем это нужно?

image

Да хотя бы для того, чтобы представить себе пучок веревок, стянутых пластиковыми хомутами 🙂

(* Тут мы просто наложили все графики друг на друга)

На этом в рамках текущей статьи все, рекомендую поиграться самостоятельно.

Всего наилучшего,
с вами был Петр.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *