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

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

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) на отрезке [х 0 , х„], который разбит на п одинаковых отрезков (случай равноотстоящих значений аргумента): Ax=h = const. Для каждого узла х 0 , х, =х 0 + /г, ..., х„ =х () + п h определены значения функции в виде

Введем понятие конечных разностей.

Конечные разности первого порядка

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

Конечные разности функций удобно располагать в таблицах, которые могут быть диагональными (табл. 5.1) или горизонтальными (табл. 5.2).

Диагональная таблица

Таблица 5.1

Горизонтальная таблица

Таблица 5.2

						а 5 у,
						А 5 Уо
					а 4 у.

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

Пусть для функции у=/(х) заданы значения у, =/(х,) для равностоящих значений независимых переменных:

где h - шаг интерполяции.

Необходимо найти полином Р„{х) степени нс выше п, принимающий в точках (узлах) х, значения:

Интерполирующий полином ищется в виде:

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

Полагаем в (5.13) х=х 0 , т. к. второе, третье и другие слагаемые равны 0, то

Найдем коэффициент а { .

Приэс=Х1 получим:

Для определения а 2 составим конечную разность второго порядка. При х=х 2 получим:

Аналогично можно найти другие коэффициенты. Общая формула имеет вид:

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

где х„ у х - узлы интерполяции; х - текущая переменная; h - разность между двумя узлами интерполяции; h - величина постоянная, т. е. узлы интерполяции равно отстоят друг от друга.

Этот многочлен называют интерполяционным полиномом Ньютона для интерполяции в начале таблицы (интерполирование «вперед»), или первым полиномом Ньютона.

Для практического использования этот полином записывают в преобразованном виде, вводя обозначение t=(х - x 0)/h, тогда

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

Блок-схема алгоритма метода Ньютона для интерполирования «вперед» приведена на рис. 5.3, программа - в приложении.

Пример 5.3. Дана таблица значений теплоемкости вещества в зависимости от температуры C p =f{T) (табл. 5.3).

Таблица 5.3

Воспользуемся формулой (5.16):

Рис. 5.3.

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

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

Пример 5.4. В табл. 5.3.1 приведены значения теплоемкости в зависимости от температуры. Определить значение теплоемкости в точке Г=450 К.

Воспользуемся первой интерполяционной формулой Ньютона. Конечные разности рассчитаны в предыдущем примере (табл. 5.3.2), запишем интерполяционный многочлен при х=450 К:

Таким образом, теплоемкость при температуре 450 К будет

Значение теплоемкости при Г=450 К получили такое же, что и рассчитанное по формуле Лагранжа.

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

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

Коэффициенты а 0 , а ь ..., а„ определяем из условия:

Полагаем в (5.18) х=х„, тогда

Полагаем х =х„_|, тогда следовательно,

Если x = x n - 2 i то

Аналогично можно найти другие коэффициенты многочлена (5.18):

Подставляя эти выражения в формулу (5.18), получим вторую интерполяционную формулу Ньютона, или многочлен Ньютона для интерполирования «назад»:

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

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

Это вторая формула Ньютона для интерполирования «назад».

Пример 5.5. Вычислить теплоемкость (см. табл. 5.3) для температуры Г=550 К.

Воспользуемся второй формулой Ньютона (5.19) и соответствующими конечными разностями (см. табл. 5.4):

Следовательно, значение теплоемкости при температуре 550 К равно

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

Для работы нам понадобятся: ext4_unpacker_exe.zip ext2explore-2.2.71.zip
Разбираем прошивку Android Распаковываем *.zip архив с прошивкой в любую папку.Запускаем утилиту ext4_unpacker.exe и выбираем файл system.img.

После открытия файла, нажимаем на кнопку сохранить как.

Пишем имя файла с расширением .ext4 (например system.ext4 ).

После завершения распаковки запустите утилиту ext2explore.exe от имени администратора (важно! ).В вкладке File выб…

Программа разделена на два потока в одном из которых выполняется сортировка, а в другом перерисовка графического интерфейса. После нажатия на кнопку «Сортировать», в программе вызывается метод «RunSorting», в котором определяется алгоритм сортировки и создается новый поток с запущенным в нем процессом сортировки.
private void RunSo…

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

Ниже несколько фото сделанных во время сборки устройства.

Катушка намотана проводом 0,08 мм примерно 2000 витков на ПВХ трубе диаметром 50 мм и высотой 200 мм.

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

Первый вариант питался от блока питания старого компьютера, напряжением 12 В. Затем же был сделан отдельный блок питания, напряжением в 30 В и со встроенным охлаждением.

Схема устройства:

Совместное использование ресурсов (CORS) — это спецификация W3C, которая позволяет осуществлять междоменную связь в браузере. Создавая поверх объекта XMLHttpRequest, CORS позволяет разработчикам работать с одинаковыми идиомами как запросы с одним доменом. Вариант использования для CORS прост. Представьте, что на сайте alice.com есть некоторые данные, которые сайт bob.com хочет получить. Этот тип запроса традиционно не допускается в соответствии с той же политикой происхождения браузера. Однако, поддерживая запросы CORS, alice.com может добавить несколько специальных заголовков ответов, которые позволяют bob.com получать доступ к данным. Как видно из этого примера, поддержка CORS требует координации между сервером и клиентом. К счастью, если вы являетесь разработчиком на стороне клиента, вы защищены от большинства этих деталей. В остальной части этой статьи показано, как клиенты могут выполнять запросы с кросс-началом и как серверы могут настраивать себя для поддержки CORS. Продолжени…

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

Интерполяционные формулы используются также при вычислении интегралов, при написании разностных аппроксимаций для дифференциальных уравнений, на основе интегральных тождеств.
Часто требуется восстановить функцию f(x) на отрезке a ≤ x ≤ b , если известны её значения в некотором конечном числе точек этого отрезка.

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

В таблице 1 приведены данные временной сложности алгоритмов.

Таблица 1

Входные данные:
x — координата, в которой необходимо вычислить.
n – Количество узлов.
Step – шаг интерполяции
Множество MasX – Значения x .
Множество MasY – Значения f(x) .

Выходные данные:
res – значение полинома в точке x .

Алгоритмическая модель метода Ньютона:
Множество mas мощностью |n + 2, n + 1|; Для всех i от 0..2: Для всех j от 0..n+1: Если i = 0: masi,j = MasXj; иначе Если i = 1: masi,j = MasYj; m = n; Для всех i от 2..n+2: Для всех j от 0..m: masi,j = mas(i-1),(j+1) – mas(i–1),j; m = m-1; Множество dy0 мощностью |n + 1|; Для всех i от 0..n+1: dy0i = mas(i + 1),0; res = dy00; Множество xn мощностью |n|; xn0 = x - mas0,0; Для всех i от 1..n: ans = xni - 1 * (x - mas0, i); xni = ans; ans = 0; m1 = n + 1; fact = 1; Для всех i от 1..m1: fact = fact * i; res = res + (dy0i * xni - 1) / (fact * stepi);

На рисунке 1 изображена схема интерполяции метода Ньютона.


Рисунок 1 — интерполяция метода Ньютона

// x - координата, в которой необходимо вычислить значение полинома Ньютона; n - количество узлов; MasX - массив x; MasY - массив значений x; step - шаг public double Newton(double x, int n, double MasX, double MasY, double step) { double[,] mas = new double; for (int i = 0; i < 2; i++) { for (int j = 0; j < n + 1; j++) { if (i == 0) mas = MasX[j]; else if (i == 1) mas = MasY[j]; } } int m = n; for (int i = 2; i < n + 2; i++) { for (int j = 0; j < m; j++) { mas = mas - mas; } m--; } double dy0 = new double; for (int i = 0; i < n + 1; i++) { dy0[i] = mas; } double res = dy0; double xn = new double[n]; xn = x - mas; for (int i = 1; i < n; i++) { double ans = xn * (x - mas); xn[i] = ans; ans = 0; } int m1 = n + 1; int fact = 1; for (int i = 1; i < m1; i++) { fact = fact * i; res = res + (dy0[i] * xn) / (fact * Math.Pow(step, i)); } return res; }

Составим таблицу значений для f(x) = x^3.

Найдем полимер в точке 2.1: f(2.1) = 2.1^3=9,261

С помощью программной функции мы получили такой же результат (Рисунок 2).


Рисунок 2 — применение функции

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

Мы построили математическое описание методов, после чего приступили к разработке схемы программы.

Разработали программу реализующую интерполяцию метода Ньютона, на языке C# в Visual Studio 2012.

Протестировали программу, все тесты на основе заданных нами данных были успешно пройдены.

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

P n (x) = a 0 + a 1 (x-x 0) + a 2 (x-x 0)(x-x 1) + ... + a n (x-x 0)(x-x 1)...(x-x n-1).

Задача состоит в отыскании коэффициентов a i полинома P n (x). Коэффициенты находят из уравнения:

P n (x i) = y i , i = 0, 1, ..., n,

позволяющего записать систему:

a 0 + a 1 (x 1 - x 0) = y 1 ;

a 0 + a 1 (x 2 - x 0) + a 2 (x 2 - x 0)(x 2 - x 1) = y 2 ;

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

a 0 +... + a n (x n - x 0)(x n - x 1) ... (x n - x n-1) = y n ;

Используем метод конечных разностей. Если узлы x i заданы через равные промежутки h, т.е.

x i+1 - x i = h,

то в общем случае x i = x 0 + i×h, где i = 1, 2, ..., n. Последнее выражение позволяет привести решаемое уравнение к виду

y 1 = a 0 + a 1 ×h;

y 2 = a 0 + a 1 (2h) + a 2 (2h)h;

- - - - - - - - - - - - - - - - - - -

y i = a 0 + a 1 ×i×h + a 2 ×i×h[(i-1)h] + ... + a i ×i!×h i ,

откуда для коэффициентов получаем

где Dу 0 – первая конечная разность.

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

где D 2 у 0 - вторая конечная разность, представляющая собой разность разностей. Коэффициент а i можно представить в виде:

Поставляя найденные значения коэффициентов а i в значения для P n (x), получим интерполяционный полином Ньютона:

Преобразуем формулу, для чего введем новую переменную , где q – число шагов, необходимых для достижения точки х, двигаясь из точки х 0 . После преобразований получаем:

Полученная формула известна как первая интерполяционная формула Ньютона, или формула Ньютона для интерполирования "вперед". Ее выгодно использовать для интерполирования функции y = f(x) в окрестности начального значения х – х 0 , где q мало по абсолютной величине.

Если записать интерполяционный многочлен в виде:

то аналогичным образом можно получить вторую интерполяционную формулу Ньютона, или формулу Ньютона для интерполирования "назад":

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

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

Если интерполирование осуществляется с одинаковым шагом, то формула для остаточного члена видоизменяется. В частности, при интерполировании "вперед" и "назад" по формуле Ньютона выражение для R(x) несколько отличаются друг от друга.

Анализируя полученную формулу, видно, что погрешность R(x) представляет собой, с точностью до постоянной произведение двух множителей, из которых один, f (n+1) (x), где x лежит внутри , зависит от свойств функции f(x) и не поддается регулированию, а величина другого,

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

При неудачном расположении этих узлов верхняя граница модуля |R(x)| может быть весьма большой. Поэтому возникает задача о наиболее рациональном выборе узлов интерполирования x i (при заданном числе узлов n) с тем, чтобы полином П n+1 (х) имел наименьшее значение.