Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Московский государственный университет приборостроения и информатики Сергиево-Посадский филиал

Реферат на тему:

Интерполяционные формулы Ньютона

Выполнила: Бревчик Таисия Юрьевна

Студентка 2 курса группы ЭФ-2

1.Введение

2. Первая интерполяционная формула Ньютона

3. Вторая интерполяционная формула Ньютона

Заключение

Список литературы

Введение

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

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

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

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

Следует также упомянуть и совершенно другую разновидность математической интерполяции, известную под названием «интерполяция операторов».

К классическим работам по интерполяции операторов относятся теорема Рисса -- Торина (Riesz-Thorin theorem) и теорема Марцинкевича (Marcinkiewicz theorem), являющиеся основой для множества других работ.

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

Задача интерполяции состоит в поиске такой функции из заданного класса функций, что

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

Пары называют точками данных или базовыми точками.

Разность между «соседними» значениями -- шагом интерполяционной сетки. Он может быть как переменным, так и постоянным.

Функцию -- интерполирующей функцией или интерполянтом.

1. Первая интерполяционная формула Ньютона

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

Условия (1) эквивалентны тому, что при.

Интерполяционный полином Ньютона имеет вид:

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

Заметим, что при формула (2) превращается в ряд Тейлора для функции:

Для практического использования интерполяционную формулу Ньютона (2) обычно записывают в несколько преобразованном виде. Для этого введём новую переменную по формуле; тогда получим:

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

Формулу (3) выгодно использовать для интерполирования функции в окрестности начального значения , где мало по абсолютной величине.

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

Если таблица значений функции конечна, то число ограничено, а именно: не может быть больше числа значений функции, уменьшенного на единицу.

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

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

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

2. Вторая интерполяционная формула Ньютона

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

Описание задачи. Пусть имеем последовательность значений функции

для равноотстоящих значений аргумента, где - шаг интерполяции. Построим полином следующего вида:

или, используя обобщённую степень, получаем:

Тогда, при выполнении равенства, получим

Подставим эти значения в формулу (1). Тогда, окончательно, вторая интерполяционная формула Ньютона имеет вид:

Введём более удобную запись формулы (2). Пусть, тогда

Подставив эти значения в формулу (2), получим:

Это и есть обычный вид второй интерполяционной формулы Ньютона . Для приближённого вычисления значений функции полагают:

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

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

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

Заметим, что операция экстраполирования, вообще говоря, менее точна, чем операция интерполирования в узком смысле слова.

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

Заключение

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

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

Список литературы

1. В.В. Иванов. Методы вычислений на ЭВМ. Справочное пособие. Изд-во "Наукова думка". Киев. 1986.

2. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". 2003.

3. И.С. Березин, Н.П. Жидков. Методы вычислений. Изд. ФизМатЛит. Москва. 1962.

4. К. Де Бор. Практическое руководство по сплайнам. Изд-во "Радио и связь". Москва. 1985.

5. Дж. Форсайт, М.Мальком, К. Моулер. Машинные методы математических вычислений. Изд-во "Мир". Москва. 1980.

Размещено на Allbest.ru

...

Подобные документы

Применение первой и второй интерполяционной формул Ньютона. Нахождение значений функции в точках, не являющимися табличными. Bспользование формулы Ньютона для не равностоящих точек. Нахождение значения функции с помощью интерполяционной схемы Эйткена.

лабораторная работа , добавлен 14.10.2013


Иоганн Карл Фридрих Гаусс - величайший математик всех времен. Интерполяционные формулы Гаусса, дающие приближенное выражение функции y=f(x) при помощи интерполяции. Области применение формул Гаусса. Основные недостатки интерполяционных формул Ньютона.

контрольная работа , добавлен 06.12.2014


Интерполирование функции в точке, лежащей в окрестности середины интервала. Интерполяционные формулы Гаусса. Формула Стирлинга как среднее арифметическое интерполяционных формул Гаусса. Кубические сплайн-функции как математическая модель тонкого стержня.

презентация , добавлен 18.04.2013


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

курсовая работа , добавлен 14.03.2014


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

курс лекций , добавлен 11.02.2012


Осуществление интерполяции с помощью полинома Ньютона. Уточнение значения корня на заданном интервале тремя итерациями и нахождение погрешности вычисления. Применение методов Ньютона, Сампсона и Эйлера при решении задач. Вычисление производной функции.

контрольная работа , добавлен 02.06.2011


В вычислительной математике существенную роль играет интерполяция функций. Формула Лагранжа. Интерполирование по схеме Эйткена. Интерполяционные формулы Ньютона для равноотстоящих узлов. Формула Ньютона с разделенными разностями. Интерполяция сплайнами.

контрольная работа , добавлен 05.01.2011


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

реферат , добавлен 06.03.2011


Кінцеві різниці різних порядків. Залежність між кінцевими різницями і функціями. Дискретний і неперервний аналіз. Поняття про розділені різниці. Інтерполяційна формула Ньютона. Порівняння формул Лагранжа і Ньютона. Інтерполяція для рівновіддалених вузлів.

контрольная работа , добавлен 06.02.2014


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

Аннотация

Пояснительная записка курсовой работы "Интерполяция функции одной переменной методом Ньютона" содержит в себе введение, анализ задания описанием входных и выходных данных, обзор литературных источников, описание математической модели и методов вычислительной математики, пояснения к алгоритму, текст программы, инструкцию. При изучении дисциплины "Информатика" для написания курсовой работы использовались различные литературные источники, которые перечислены в настоящем документе. В данной курсовой работе приведена программа, которая применяется для интерполяции таблично заданной функции методом Ньютона. В ней был использован метод структурного программирования для облегчения написания и отладки программы, а также повышения ее наглядности и читаемости. Целью написания данной работы было получение и закрепление практических навыков разработки алгоритмов различными методами. Представленная программа реализована на языке программирования Pascal. Пояснительная записка содержит 25 листов, на которых размещено два рисунка, текст программы и описание программы и алгоритма.

Введение

Анализ задания

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

Программирование функции формулы Ньютона

Обзор литературных источников

Разработка программы по схеме алгоритма

Инструкция пользования программой

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

Исходные данные и результат решения контрольного примера

Заключение

Список использованных источников

Введение

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

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

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

Анализ задания

В качестве входных данных использованы:

1. Количество узлов.

2. Табличные значения функции.

Выходными данными, т.е. результатом программы является:

1. Значения таблично заданной функции в промежуточных значениях.

2. График полинома.

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

При выполнении курсовой работы была выбрана следующая математическая модель:

Интерполяция и приближение функций.

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

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

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

Пусть и» отрезке

задана сетка со

и в ее узлах заданы значения функции

, равные .

Требуется построить интерполянту - функцию

, совпадающую с функцией в узлах сетки: .

Основная цель интерполяции - получить быстрый (экономичный) алгоритм вычисления значений

для значений , не содержащихся в таблице данных.

2. Интерполяция по Ньютону

Дана табличная функция:

i
0
1
2
..	..	..
n

, (1)

Точки с координатами

называются узловыми точками или узлами.

Количество узлов в табличной функции равно N=n+1.

Необходимо найти значение этой функции в промежуточной точке, например,

, причем . Для решения задачи используется интерполяционный многочлен.

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

где n – степень многочлена,

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

через значение в одном из узлов и через разделенные разности функции , построенные по узлам .

Сначала приведем необходимые сведения о разделенных разностях.

Пусть в узлах

,

известны значения функции

. Предположим, что среди точек , , нет совпадающих. Разделенными разностями первого порядка называются отношения , , .

Будем рассматривать разделенные разности, составленные по соседним узлам, т. е. выражения

2. Интерполяция по Ньютону

Дана табличная функция:

i
0
1
2
..	..	..
n

Точки с координатами называются узловыми точками или узлами.

Количество узлов в табличной функции равно N=n+1.

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

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

где n – степень многочлена,

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

Сначала приведем необходимые сведения о разделенных разностях.

Пусть в узлах

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

, ,.

Будем рассматривать разделенные разности, составленные по соседним узлам, т. е. выражения

По этим разделенным разностям первого порядка можно построить разделенные разности второго порядка:

,

,

Таким образом, разделённая разность -го порядка на участке может быть определена через разделённые разности -го порядка по рекуррентной формуле:

где , , - степень многочлена.

Максимальное значение равно . Тогда и разделенная разность n-го порядка на участке равна

т.е. равна разности разделенных разностей -го порядка, разделенной на длину участка .

Разделенные разности

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

При вычислении разделенных разностей принято записывать их в виде таблицы

■

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

. (1)

Эту формулу можно доказать методом индукции. Нам потребуется частный случай формулы (1):

Интерполяционным многочленом Ньютона называется многочлен

Рассмотренная форма полинома Ньютона носит название первой интерполяционной формулы Ньютона, и используется, обычно, при интерполировании вначале таблицы.

Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции y i , i=0,1,…n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (2). Это удобно на практике и ускоряет процесс вычислений.

Программирование функции формулы Ньютона

Для построения многочлена Ньютона по формуле (1) организуем циклический вычислительный процесс по . При этом на каждом шаге поиска находим разделенные разности k-го порядка. Будем помещать разделенные разности на каждом шаге в массив Y.

Тогда рекуррентная формула (3) будет иметь вид:

В формуле Ньютона (2) используются разделенные разности -го порядка, подсчитанные только для участков т.е. разделенные разности -го порядка для . Обозначим эти разделенные разности k-го порядка как . А разделенные разности, подсчитанные для , используются для расчетов разделенных разностей более высоких порядков.

Используя (4), свернем формулу (2). В результате получим

(5)

– значение табличной функции (1) для .

– разделенная разность -го порядка для участка .

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

P n (x)=a 0 + a 1 (x-x n) + a 2 (x-x n)(x-x n-1) + …+ a n (x-x n)(x-x n-1)…(x-x 1), (6.3.3-8)

где а i , i = 0, 1, 2, …, n – коэффициенты, не зависящие от узлов интерполяции.

Для определения коэффициентов а i будем в (6.3.3-8) поочередно подставлять узлы интерполяции. При х = x n P n (x n) = y n , следовательно, a 0 = y n .

При х = x n -1 имеем P n (x n -1) = y n -1 = a 0 + a 1 (x n -1 -x n) = y n + a 1 (x n -1 -x n), откуда

Продолжая подстановку, получим выражение для всех коэффициентов многочлена (6.3.3-8) и запишем вторую интерполяционную формулу Ньютона:

Введя обозначение:

и, подставив х в (6.3.3-8), получаем формулу Ньютона для интерполяции назад:

Воспользуемся этой формулой для вычисления значения функции, заданной таблицей 6.3.3-1, в точке х = 1.7.

Точка х=1.7 расположена в конце таблицы. В качестве узлов интерполяции выберем: х 3 =1.8, х 2 =1.6 и х 1 =1.4:

Погрешности интерполяционных формул Ньютона определяются соотношением:

· для первой формулы Ньютона:

(6.3.3-11)

· для второй формулы Ньютона:

(6.3.3-12)

где - некоторое промежуточное значение между узлами интерполяции.

На практике, если интерполируемая функция y = f(x) задана таблично , полагая, что D n +1 = const, а h –достаточно мало, используют приближенные равенства:

(6.3.3-13)

Пример 6.3.3-1. Вычислить c использованием 1-й и 2-й формул Ньютона значение функции, заданной таблицей равноотстоящих узлов, в точке х=1.23.

Практическая погрешность оценивается соотношением:

e 1 = |Р 2 (х) - Р 1 (х)|=|0.206958-0.206335|=0.000623.

Решим ту же задачу с помощью 2-й формулы Ньютона. Пусть х n = 1.3; х n -1 = 1.2; х n -2 = 1.1.

Таблица конечных разностей имеет вид:

x	y	Dy	D 2 y
1.1 1.2 1.3	0.095310 0.182322 0.262364	0.087012 0.080042	-0.006970

Тогда:

6.3.4. Сплайн – интерполяция

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

Рассмотренные выше методы локальной интерполяции, по существу, являются простейшими сплайнами первой степени (для линейной интерполяции) и второй степени (для квадратичной интерполяции).

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

В общем случае для функции y = f(x) требуется найти приближение y = S(x) таким образом, чтобыf(x i) = S(x i) в точках x = x i , a в остальных точках отрезка значения функций f(x) и S(x) были близкими между собой. При малом числе экспериментальных точек для решения задачи интерполяции можно использовать один из методов построения интерполяционных полиномов. Однако при большом числе узлов интерполяционные полиномы становятся практически непригодными. Это связано с тем, что степень интерполяционного полинома лишь на единицу меньше числа экспериментальных значений функций. Можно, конечно, отрезок, на котором определена функция, разбить на участки, содержащие малое число экспериментальных точек, и для каждого из них построить интерполяционные полиномы. Однако в этом случае аппроксимирующая функция будет иметь точки, где производная не является непрерывной, т. е. график функции будет содержать точки “излома”.

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

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

Пусть интерполируемая функция f(x)задана своими значениями y i , в узлах х i,
(i = 0, 1,...,n). Обозначим длину частичного отрезка как h i =x i -x i-1 ,
(i = 1, 2,...,n). Будем искать кубический сплайн на каждом из частичных отрезков [х i-1 ;х i ] в виде:

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

Потребуем совпадения значений S(x)в узлах с табличными значениями функции f(x):

(6.3.4-2)

Число этих уравнений (2n) в два раза меньше числа неизвестных коэффициентов. Для того чтобы получить дополнительные условия, потребуем также непрерывности первой и второй производных сплайна во всех точках, включая узлы. Для этого следует приравнять левые и правые производные S"(x–0), S"(x+0), S"(x–0), S"(x+0) во внутреннем узле x i .

Вычислим выражения для производных S"(x), S"(x)последовательным дифференцированием (6.3.4-1):

S"(x) = b i + 2c i (x–x i-1) + 3d i (x–x i - l) 2 , (6.3.4-4)

S""(x) = 2c i + 6d i (x–x i - l),(6.3.4-5)

найдем правые и левые производные в узле:

S"(x i –0) = b i + 2сh i + 2d i h i ,

S"(x i +0) = b i+1 , где i = 1,2,..., n -1.

Аналогично поступаем для второй производной:

S"(x–0) = 2c i +6d i h i ,

S"(х+0) = 2с i+1 .

Приравняв левые и правые производные, получаем:

b i +1 = b i +2c i h i +2d i h i 2 (6.3.4-6)

с i+1 = с i - + 3d i h i , где i = 0, 1,..., n–1. (6.3.4-7)

Уравнения (6.3.4-6), (6.3.4-7) дают еще 2(n–1) условий. Для получения недостающих уравнений накладывают требования к поведению сплайна на концах отрезка интерполяции. Если потребовать нулевой кривизны сплайна на концах отрезка интерполяции (т. е. равенство нулю второй производной), то получим:

с i =0, c n +3d n h n = 0. (6.3.4-8)

Исключив из уравнений (6.3.4-2) – (6.3.4-3) nнеизвестных a i , получаем систе­му уравнений:

(6.3.4-9)

где i=0, 1,...., n - 1.

Система (6.3.4-9) состоит из 3(n-1)уравнений. Решив систему (6.3.4-9), получаем значения неизвестных b i , c i , d i ,определяющих совокупность всех формул для искомого интерполяционного сплайна:

где i = 0,1,...,n–1.(6.3.4-10)

Программа, реализующая метод сплайн-интерполяции, доста­точно громоздка, поэтому ограничимся обсуждением решения задачи об интерполяции синуса с помощью сплайнов, используя функции пакетов п.п. 6.3.6.

ИНТЕРПОЛИРОВАНИЕ

Пусть функция у = f (x ) задана на сетке равноотстоящих узлов x i =x 0 +ih, где i = 0,1, ..., п, и для нее построена таблица конечных разностей § 16.3.

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

Р n (х ) = а 0 +а 1 (х-х 0 ) + а 2 (х-х 0)(х-х 1)+... + а n (х-х 0)( х-х 1) … (х-х n - 1). (17.1)

Его п+ 1 коэффициент а 0 , а 1 , ..., а n будем находить последовательно из п +1 интерполяционных равенств

Р n (х i ) =y i , i = 0,1, ..., п .

А именно, полагая i = 0, т.е. х = х 0 , в (1.23) имеем Р n (х 0 ) = а 0 , следовательно, а 0 = у 0 .

а 0 +а 1 (х- х 0 )=y 1 ,

в которое подставляем уже найденное значение а 0 = у 0 . Разрешая это равенство относительно а 1 и используя обозначение конечной разности, получаем

Полной индукцией можно показать справедливость выражения

Подставляя найденные коэффициенты а 0 , а 1 , ..., а n в (17.1), получаем многочлен

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

Учитывая, что каждое слагаемое многочлена (17.2), начиная со второго, содержит множитель х- х 0 , естественно предположить, что этот многочлен наиболее приспособлен для интерполирования в окрестности узла х 0 . Будем называть узел х 0 базовым для многочлена (17.2) и упростим (17.2) введением новой переменной q райенством или (что то же) равенством x = x 0 +qh. Так как

x - x i = x 0 + qh - x 0 - ih= h (q- i ),

то в результате подстановки этих разностей в (17.2) приходим к первой интерполяционной формуле Ньютона в виде

где обозначение Р n (x 0 + qh ) указывает не только на n -ю степень многочлена, но и на базовый узел x 0 и связь переменных х и q.

Первая формула Ньютона (17.3) обычно применяется при значениях |q | < 1, а именно, для интерполирования вперед (при х Î (х 0 , x 1), т.е. при q Î (0, 1)) и экстраполирования назад (при х < х 0 т.е. при q < 0).

Так как реально степени интерполяционных многочленов бывают не так велики, в то время как таблицы значений функций достаточно обширны, и так как в реальной числовой таблице никаких индексов - номеров узлов нет, то за базовый для формулы (17.3) узел х 0 можно принимать узел, ближайший к заданной фиксированной точке х, если за ним имеется достаточное число узлов для построения необходимых разностей. Поскольку в первой формуле Ньютона используются нисходящие диагонали таблицы конечных разностей, то такое смещение узла, принимаемого за базовый, в конце таблицы будет неприемлемо.

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

Р (х ) = а 0 +а 1 (х-х n ) + а 2 (х-х n )(х-х n - 1)+... + а n (х-х n )( х-х n - 1)…(х-х 1).

Коэффициенты а 0 , а 1 , ..., а n этого многочлена находятся аналогично тому, как они находились для многочлена (17.1), только здесь подстановка узловых точек вместо х и рассмотрение интерполяционных равенств производится тоже в обратном порядке.

Таким образом, получаем второй интерполяционный многочлен Ньютона

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

Положим в (17.4) x = x n +qh, иначе, введем новую перемен и преобразуем к ней входящие в (17.4) разности:

x - x i = x n + qh - x 0 - ih= x 0 + nh + qh - x 0 - ih= h (q+n- i )

В результате приходим ко второй интерполяционной формуле Ньютона вида

Ее также целесообразно использовать при значениях |q | < 1, т.е. в окрестности узла х п для интерполирования назад (при q Î (-1, 0)) и экстраполирования вперед (при q > О).

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

Будем считать, что узел x 0 расположен в середине таблицы, и нумерация остальных узлов производится, начинаясь с х 0 , с использованием как положительных, так и отрицательных индексов, т.е. считаем x i =x 0 +ih, где i = 0, ±1, ±2,... . Тогда центральная часть таблицы конечных разностей будет проиндексирована так, как это показано в табл. 1.7. Все подчеркнутые в ней конечные разности (находящиеся с XQ,y Q в одной строке и на полстроки выше и ниже) называются центральными разностями.

x - 3 y - 3 Dy - 3

x - 2 y - 3 Dy - 2 D 2 y - 3 D 3 y - 3

x - 1 y - 1 D y - 1 D 2 y - 2 D 3 y - 2 D 4 y - 3 D 5 y - 3

x 0 y 0 D y 0 D 2 y - 1 D 3 y - 1 D 4 y - 2 D 5 y - 2 D 6 y - 3

x 1 y 1 Dy 1 D 2 y 0 D 3 y 0 D 4 y - 1

x 2 y 2 Dy 2 D 2 y 1

x 3 y 3

Интерполяционный многочлен ищем в форме

Р (х ) = а 0 +а 1 (х-х 0) + а 2 (х-х 0)(х-х 1)+ а 3 ( х-х - 1) (х-х 0)(х-х 1)+

+а 4 ( х-х - 1) (х-х 0)(х-х 1)( х-х 2)+… .

Коэффициенты ищем, как и прежде. Введя новую переменную и выразив через нее разности x - x i = h (q- i ) для всех i = 0, ±1, ±2, ..., в результате подстановки этих разностей и выражений коэффициентов после преобразований приводит к формуле

называемой интерполяционной формулой Стирлинга.

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

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

Для первого интерполяционного многочлена Ньютона в форме (17.3) погрешность может быть записана следующим образом

Для второго интерполяционного многочлена Ньютона в форме (17.5) погрешность может быть записана следующим образом