91136

ИНТЕРПОЛЯЦИЯ И ЭКСТРАПОЛЯЦИЯ

Лекция

Информатика, кибернетика и программирование

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

Русский

2015-07-13

377 KB

6 чел.

PAGE  11

Лекция 7

ИНТЕРПОЛЯЦИЯ и ЭКСТРАПОЛЯЦИЯ

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

Предположим, что задано  различных точек плоскости:

                        (7.1)

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

Т.е. нужно найти линию, описываемую уравнением , проходящую через  данную точку (рис.7.1).

Рис.7.1     

Заметим, что здесь приходится различать два случая:

  1.  интерполяцию (от лат. interpolar — подновлять) — восстановление промежуточных значений функции внутри интервала  по ряду известных ее значений;
  2.  экстраполяцию (лат. приставка extra означает «вне») — когда не вошедшее в исследование значение  лежит вне интервала .

Очевидно, интерполяция более надежна, чем экстраполяция.

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

                   (7.2)

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

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

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

Для решения предложенной задачи зафиксируем одну ординату , а остальные будем считать равными нулю (рис.7.2)

т.е. заданным значениям абсцисс  ставятся в соответствие значения ординат

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

делиться на каждую из  разностей:

                     

                           

                 Рис.7.2

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

                               (7.3)

(Теорема Виета.

Уравнение (многочлен) Y=ax2+bx+c 

Может быть разложено

Y=a(x-x1)(x-x2), где х1 и х2 корни уравнения)

Из условия  определим значение const

,

откуда

Const=у2/(x2-x1)(x2-x3)(x2-x4)…(x2-xn)

таким образом находим

                      (7.4)

В полученном выражении никакого особого преимущества  не имеет, мы можем приписать эту особую роль любому ,

       (7.5)

Общее решение является суперпозицией (суммой) частных решений (7.5)

                   

       

        (7.6)

Это и есть интерполяционный многочлен Лагранжа. По наборам исходных пар (7.1) формула (7.6) позволяет достаточно просто составить «внешний вид»

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

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

Пусть на отрезке  задана система равноотстоящих узлов  которыми отрезок делится на  равных частей

где

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

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

              (7.14)

Пример

Построить интерполяционный полином Лагранжа для таблично заданных точек

x

1

3

4

F(x)

12

4

6

Из таблицы следует, что при 3-х точках степень многочлена будет не выше 2.

Здесь х0=1, х1=3, х2=4

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

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

Конечные разности

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

     

     

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

     

  

где

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

Для конечных разностей -го порядка:

В результате получим таблицу конечных разностей:

                                    

                                        

                                                      

    .............

 

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

Первая интерполяционную формулу Ньютона для равноотстоящих узлов

Полином  -й степени (т.е. имеющий  корней)

перепишем в виде

где  — узлы интерполяции.

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

  1.  Полагая  найдем

Полагая  найдем

отсюда

  1.  Полагая  найдем

отсюда  и т.д.

В общем случае  и

               

                

отсюда

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

        

                   (7.15)

        

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

Часто эта формула записывается и несколько ином виде.  Введем вместо переменной x новую переменную  или  x = x0 + ht. Тогда ,   и т.д. После этого формула (4.13) примет вид

Pn(x) = Pn(x0 + th) =

   (4.14)

Формула (4.14) называется первой интерполяционной формулой Ньютона. Эта формула традиционно применяется для интерполирования в начале отрезка интерполяции, для значений t в интервале (0, 1). Первую интерполяционную формулу Ньютона называют по этой причине формулой для интерполирования вперед. Заметим, что путем переопределения узлов за начальное значение x0 можно принимать любое табличное значение аргумента x (отбросив «лишние» узлы слева).

Пример

Заданы табличные значения функции и ее конечные разности 1 и 2 го порядка

Знач X

ЗначУ

1 разность

2 разность

1.215

0,106044

0.000447

-3Е-06

1,22

0,106491

0.000444

-2Е-06

1.225

0,106935

0.000442

-1Е-06

1.23

0,107377

0.000441

-2Е-06

1.235

0,107818

0.000439

-1.388Е-17

1.24

0,108257

0.000439

-1Е-06

1.245

0,108696

0.000438

-1Е-06

1.25

0,109134

0.000437

-1.388Е-17

1.255

0,109571

0.000437

1.26

0,110008

Вычислим значение у( для х=1.2173).

Поскольку значение x = 1,2173 находится и начале таблицы, применим интерполирование вперед, при этом воспользуемся первой интерполяционной формулой Ньютона в форме (4.14). Вычислим вначале t=(1.2173 - 1.215)/0,005=0,46. Далее в соответствии с формулой (4.14) получим

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

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

(4.17)

Пример

Для таблично заданной функции вычислить значение у(1,253)

Знач X

Знач У

1 разность

2 разность

1.215

0,106044

0.000447

-3Е-06

1,22

0,106491

0.000444

-2Е-06

1.225

0,106935

0.000442

-1Е-06

1.23

0,107377

0.000441

-2Е-06

1.235

0,107818

0.000439

-1.388Е-17

1.24

0,108257

0.000439

-1Е-06

1.245

0,108696

0.000438

-1Е-06

1.25

0,109134

0.000437

-1.388Е-17

1.255

0,109571

0.000437

1.26

0,110008

Поскольку значение х находится в конце таблицы, воспользуемся вторым интерполяционным многочленом Ньютона, приняв xn 1.255. Вычислим вначале    t = (1,253-1,255)/0,005=-0,4. Далее в соответствии с формулой (4.17) получим

4.7 Экстраполяция

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

Для экстраполяции функции могут использоваться интерполяционные формулы Ньютона – и первая, и вторая. При этом вычисляются их значения для значений аргументов, лежащих за пределами таблицы. Причем, если x<x0, то t= (x-x0)/h<0, и в этом случае выгоднее применять первую интерполяционную формулу Ньютона. Если же x>xn, то t-(x-xn)/h>0 и здесь удобнее использовать вторую интерполяционную формулу Ньютона. Таким образом. По первой интерполяционной формуле Ньютона происходит интерполирование вперед и 'экстраполирование назад, а по второй интерполирование назад и экстраполирование вперед.

Пример 4.7. Для таблично заданной функции у(х) из примера 4.3 вычислим значения y(1.210) и y(1.270).

Значения аргумента х= 1.210 и х = -1.270 находятся за пределами таблицы. Для экстраполяции используем интерполяционные формулы Ньютона.

При х= 1.210 получаем t = (1,210- 1,215)/0,005 = -1. Применяем первую интерполяционную формулу Ньютона (4.14) (экстраполирование назад):

y(1.2110) = 0,106044+ (-1) 0.000447 -0,000003 = 0,105594.

При x = 1.270 получаем t = (1.2170- 1.260)/0,005 =2. Применяем вторую интерполяционную формулу Ньютона (4.17) (экстраполирование вперед):

y(1,2170) = 0.110008 + 2 * 0,000437 +(2*3)/2(-0.000001) = 0,110879.

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


 

А также другие работы, которые могут Вас заинтересовать

21324. Криптографическая защита информации 144.5 KB
  Кpиптоанализ исследование возможности расшифровывания информации без знания ключей.Шеннона €œТеория связи в секретных системах€ стала началом новой эры научной криптологии с секретными ключами. Классификация криптографических систем Тайнопись Криптография с ключом Симметричные криптоалгоритмы Шифры перестановки Шифры замены подстановки Простой замены Сложной замены Сложные составные шифры Асимметричные криптоалгоритмы Комбинированные гибридные криптосистемы Тайнопись Отправитель и получатель производят над сообщением...
21325. Симметричное и асимметричное шифрование 1.88 MB
  Шифрование это преобразование данных в нечитабельную форму используя ключи шифрования расшифрования дешифрования. Она состоит из: одного или более алгоритмов шифрования математических формул; ключей используемых этими алгоритмами шифрования; системы управления ключами; незашифрованного текста; и зашифрованного текста шифртекста. Существуют две методологии криптографической обработки информации с использованием ключей – симметричная и асимметричная. Симметричная секретная методология где и для шифрования и для расшифровки...
21326. Межсетевой экран 214 KB
  Владелец компьютера имеющего выход в Internet устанавливает межсетевой экран чтобы предотвратить получение посторонними конфиденциальных данных хранящихся на защищаемом компьютере рис. Если с другой стороны это приложение таково что по вашему мнению оно не должно взаимодействовать с другим компьютером например текстовый редактор или новая игра загруженная из Internet то скорее всего вы создадите правило которое будет блокировать передачу пакетов этим приложением. Но тем не менее самой защищенной является сеть которая...
21327. Основные понятия информационной безопасности 59 KB
  Информация и формы ее существования на объекте Информация Сведения о лицах предметах фактах событиях явлениях и процессах независимо от формы их представления закон об информации Информация это то что дает возможность получателю логически сформулировать или изменить представление о некоторой структуре образ схема модель. Информация Сведения раскрываемые технической разведкой через демаскирующие признаки объектов защиты или путем несанкционированного доступа к техническим средствам обработки информации. Справочник ВНИИ...
21328. СИСТЕМА ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ 80 KB
  Винахід (корисна модель) - це результат інтелектуальної діяльності людини в будь-якій сфері технології. Винахід (корисна модель) може бути секретним, якщо містить інформацію, віднесену до державної таємниці.
21329. Политика информационной безопасности 174 KB
  Лекция: Политика Рассмотрены вопросы политики информационной безопасности методика разработки политик создания развертывания и эффективного использования. Наверное самая неинтересная часть профессиональной работы в сфере информационной безопасности это разработка политики. Но политика имеет огромное значение для организации и вероятно является наиболее важной работой отдела информационной безопасности. Таким образом политика выполняет две основные функции: определяет безопасность внутри организации; определяет место каждого служащего...
21330. Протоколирование и аудит 94.5 KB
  Реализация протоколирования и аудита решает следующие задачи: обеспечение подотчетности пользователей и администраторов; обеспечение возможности реконструкции последовательности событий; обнаружение попыток нарушений информационной безопасности; предоставление информации для выявления и анализа проблем. Разумный подход к упомянутым вопросам применительно к операционным системам предлагается в Оранжевой книге где выделены следующие события: вход в систему успешный или нет; выход из системы; обращение к удаленной системе; операции с...
21331. Службы информационной безопасности 246.5 KB
  Службы информационной безопасности и типы атак Атаки Службы безопасности Конфиденциальность Целостность Доступность Идентифицируемость Доступа X X Модификации X X Отказ в обслуживании X Отказ от обязательств X X Конфиденциальность Служба конфиденциальности обеспечивает секретность информации. Правильно сконфигурированная эта служба открывает доступ к информации только аутентифицированным пользователям. Выполняя эту функцию служба конфиденциальности ограждает системы от атак доступа.