Довольно распространенным методом интерполирования является метод Ньютона. Интерполяционный полином для этого метода имеет вид:
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 (х) имел наименьшее значение.
Всем привет. Довольно недавно я столкнулся с проблемой на своем новом телефоне, для решения которой мне нужно было достать из прошивки некоторые 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 ) задана на сетке равноотстоящих узлов 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) погрешность может быть записана следующим образом
Пусть задана функция y=f(x) на отрезке , который разбит на n одинаковых отрезков (случай равноотстоящих значений аргумента). x=h=const. Для каждого узла x 0, x 1 =x 0 +h,..., x n =x 0 +n h определены значения функции в виде: f(x 0)=y 0, f(x 1)=y 1,..., f(x n)=y n.
Конечные разности первого порядка y 0 = y 1 – y 0 y 1 = y 2 – y y n-1 = y n – y n-1. Конечные разности второго порядка 2 y 0 = y 1 – y 0 2 y 1 = y 2 – y y n-2 = y n-1 – y n-2 Аналогично определяются конечные разности высших порядков: k y 0 = k-1 y 1 – k-1 y 0 k y 1 = k-1 y 2 – k-1 y k y i = k-1 y i+1 – k-1 y i, i = 0,1,...,n-k.
Пусть для функции y = f(x) заданы значения y i = f(x i) для равностоящих значений независимых переменных: x n = x 0 +nh, где h - шаг интерполяции. Необходимо найти полином P n (x) степени не выше n, принимающий в точках (узлах) x i значения: P n (x i) = y i, i=0,...,n. Запишем интерполирующий полином в виде:
Задача построения многочлена сводится к определению коэффициентов а i из условий: P n (x 0)=y 0 P n (x 1)=y P n (x n)=y n
Аналогично можно найти другие коэффициенты. Общая формула имеет вид. Подставляя эти выражения в формулу полинома, получаем: где x i,y i – узлы интерполяции; x – текущая переменная; h – разность между двумя узлами интерполяции h – величина постоянная, т.е. узлы интерполяции равноотстоят друг от друга.
Особенностью интерполяции являлось то, что интерполирующая функция строго проходит через узловые точки таблицы, т. е. рассчитанные значения совпадали с табличными: y i =f(x i). Эта особенность обуславливалась тем, что количество коэффициентов в интерполирующей функции (m) было равно количеству табличных значений (n)
4. Интерполирующей функцией невозможно описать табличные данные, в которых есть несколько точек с одинаковым значением аргумента. Такая ситуация возможна, если один и тот же эксперимент проводится несколько раз при одних и тех же исходных данных. Однако это не является ограничением для использования аппроксимации, где не ставится условие прохождения графика функции через каждую точку.
Выборка экспериментальных данных представляет собой массив данных, который характеризует процесс изменения измеряемого сигнала в течение заданного времени (либо относительно другой переменной). Для выполнения теоретического анализа измеряемого сигнала необходимо найти аппроксимирующую функцию, которая свяжет дискретный набор экспериментальных данных с непрерывной функцией - интерполяционным полиномом n -степени. Данный интерполяционный полином n-степени может быть записан, например, в форме Ньютона (один из способов представления).
Интерполяционный многочлен
в форме Ньютона
– это математическая функция позволяющая записать полином
n
-степени, который будет соединять все заданные точки из набора значений, полученных опытным путём или методом случайной выборки с постоянным/переменным временным шагом измерений.
1. Интерполяционная формула Ньютона для неравноотстоящих значений аргумента
В общем виде интерполяционный многочлен в форме Ньютона записывается в следующем виде:
где n – вещественное число, которое указывает степень полинома;
– переменная, которая представляет собой разделенную разность
k-го порядка, которая вычисляется по следующей формуле:
Разделённая разность является симметричной функцией своих аргументов, то есть при любой их перестановке её значение не меняется. Следует отметить, что для разделённой разности k-го порядка справедлива следующая формула:
В качестве примера, рассмотрим построение полинома в форме Ньютона по представленной выборке данных, которая состоит из трех заданных точек . Интерполяционный многочлен в форме Ньютона, который проходит через три заданных точки, будет записываться в следующем виде:
Разделенная разность 1-го порядка определяется следующим выражением
Разделенная разность 2-го порядка определяется следующим выражением
Следует отметить, что данное выражение может быть переписано в другом виде:
Форма Ньютона является удобной формой представления интерполяционного полинома n-степени, так как при добавлении дополнительного узла все вычисленные ранее слагаемые остаются без изменения, а к выражению добавляется только одно новое слагаемое. Следует отметить, что интерполяционный полином в форме Ньютона только по форме отличается от интерполяционного полинома в форме Лагранжа, представляя собой на заданной сетке один и тот же интерполяционный полином.
Следует отметить, что полином в форме Ньютона может быть представлен в более компактном виде (по схеме Горнера), которая получается путем последовательного вынесения за скобки множителей
2. Интерполяционная формула Ньютона для равноотстоящих значений аргумента
В случае если значения функции заданы для равноотстоящих значений аргумента, которые имеют постоянный шаг измерений
, то используют другую форму записи интерполяционного многочлена по формуле Ньютона.
Для интерполирования функции в конце рассматриваемого интервала (интерполирование назад и экстраполирование вперед
где конечные разности k
Получаемые конечные разности удобно представлять в табличной форме записи, в виде горизонтальной таблице конечных разностей. В этой формуле из таблицы конечных разностей используются верхней диагонали.
Для интерполирования функции в начале рассматриваемого интервала (интерполирование вперед и экстраполирование назад ) используют интерполяционный полином в форме Ньютона в следующей записи:
где конечные разности k -порядка определяются по следующему выражению
Получаемые конечные разности удобно представлять в табличной форме записи, в виде горизонтальной таблице конечных разностей. В формуле из таблицы конечных разностей используются нижней диагонали.
3. Погрешность интерполяционного полинома в форме Ньютона
Рассмотрим функцию f (x ), которая непрерывна и дифференцируема на рассматриваемом отрезке . Интерполяционный полином P (x) в форме Ньютона принимает в точках заданные значения функции . В остальных точках интерполяционный полином P (x) отличается от значения функции f (x ) на величину остаточного члена , который определяет абсолютную погрешность интерполяционной формулы Ньютона:
Абсолютную погрешность интерполяционной формулы Ньютона определяют следующим образом:
Переменная представляет собой верхнюю границу значения модуля (n +1)-й производной функции f(x) на заданном интервале
В случае равноотстоящих узлов абсолютная погрешность интерполяционной формулы Ньютона определяют следующим образом:
Выражение записано с учетом следующей формулы:
Выбор узлов интерполяции
С помощью корректного выбора узлов можно минимизировать значение в оценке погрешности, тем самым повысить точность интерполяции. Данная задача может быть решена с помощью многочлена Чебышева:
В качестве узлов следует взять корни этого многочлена, то есть точки:
4. Методика вычисления полинома в форме Ньютона (прямой способ)
Алгоритм вычисления полинома в форме Ньютона позволяет разделить задачи определения коэффициентов и вычисления значений полинома при различных значениях аргумента:
1. В качестве исходных данных задается выборка из n -точек, которая включает в себя значения функции и значения аргумента функции.
2. Выполняется вычисление разделенных разностей n-порядка, которые будет использоваться для построения полинома в форме Ньютона.
3. Выполняется вычисление полинома n-степени в форме Ньютона по следующей формуле:
Алгоритм вычисления полинома в форме Ньютона представлен на рисунке 1.
