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

Обновлено: 05.07.2024

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Аннотация

Введение

Анализ задания Математическая модель задачи Программирование функции формулы Ньютона Обзор литературных источников Разработка программы по схеме алгоритма Инструкция пользования программой Текст программы Исходные данные и результат решения контрольного примера Заключение Список использованных источников

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пусть и" отрезке задана сетка со

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

являются вполне определенными числами, поэтому выражение (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). В результате получим

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

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

Для вычисления Р удобно использовать рекуррентную формулу внутри цикла по (24, "https://referat.bookap.info").

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

Function POlinom (n: integer; d: real; x, y: per):real;

for k:=1 to n do begin

for i:=0 to (n-k) do begin

n — количество узлов

x[i], y[i] - табличные значения функции

D — точка, в которой необходимо вычислить значение l

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

1. Численные методы

Численные методы являются одним из мощных математических средств решения задачи. Простейшие численные методы мы используем всюду, например" извлекая квадратный корень на листке бумаги. Есть задачи, где без достаточно сложных численных методов не удалось бы получить ответа; классический пример—открытие Нептуна по аномалиям движения Урана.

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

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

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

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

2. Турбо Паскаль

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

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

Схематически программа представляется в виде последовательности восьми разделов:

1. Заголовок программы

2. Описание внешних модулей, процедур и функций

3. Описание меток

4. Описание констант

5. Описание типов переменных

6. Описание переменных

7. Описание функций и процедур

8. Раздел операторов

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

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

Program — Заголовок программы

Uses — раздел подключения модулей

Begin — открывающая логическая скобка

End — закрывающая логическая скобка

Crt — (Cathod ray tube — электронно-лучевая трубка) один из наиболее часто используемых модулей. Он содержит процедуры обслуживания процессов вывода информации на экран, ввода с клавиатуры, а также процедуры и функции вывода звуковых сигналов, работы с окнами на экране и вывода цветных текстовых строк на экран.

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

Var — раздел описания переменных

Writeln, Write — операторы вывода информации

Readln, Read — операторы ввода информации

If then - оператор условного перехода

For := to do - оператор цикла с параметром

Repeat until - оператор цикла с постусловием

Clrscr — очистка экрана

Initgraph — процедура инициализации графического режима

Closegraph — процедура закрытия графического режима

Line (x1, y1, x2, y2) — соединение двух точек отрезком

Putpixel (x, y, c) — построение точки (x, y) цветом с

Readkey — оператор считывание кода клавиш

Outtextxy (x, y, st) — вывод строки st, начиная с точки (x, y)

Getmaxx — результатом этой функции будет max значение x в данном видеорежиме

Goto — перейти к

+ - арифметическая операция сложения

— - арифметическая операция вычитания

* - арифметическая операция умножения

/ - арифметическая операция деления

Описание переменных и констант используемых в алгоритме

n — количество узлов в таблице, не считая начальную точку ;

— значения узлов записанных в одномерные массивы;

D — переменная, используемая для нахождения значения полинома Ньютона в этой точке;

L — переменная значения полинома Ньютона

k, step — константы используемые для построения графика полинома;

u — переменная шага деления графика;

Для описания алгоритма в данной курсовой работе были пронумерованы символы.

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

Для запуска программы необходимо дважды щелкнуть на ярлыке с именем Niton.exe. После этого на экран будет выведен титульный лист. Чтобы продолжить надо нажать клавишу Enter.

На экран будет выведена введённая таблица значений. Затем пользователю будет предложено «Введите x «. Нужно ввести x для которого необходимо найти приближённое значение. После этого программа вычислит значение и предложит найти значения для другого x.

Дальше программа попросит ввести шаг деления графика. После ввода шага программа построит график полинома. Для продолжения нужно нажать Enter.

, (1)

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

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

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

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

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

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

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

, ,.

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

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

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

. (3)

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

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

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

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

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

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

. (1)

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

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

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

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

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

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

(4)

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

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

(5)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Требуется построить интерполянту — функцию />, совпадающую с функцией />в узлах сетки:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где />, />, /> — степень многочлена.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Function POlinom(n: integer; d:real; x,y :per):real;

for k:=1 to n do begin

for i:=0 to (n-k) do begin

n – количество узлов

x[i],y[i] – табличные значения функции

D – точка, в которой необходимо вычислить значение l

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

1. Численные методы

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

2. Турбо Паскаль

Схематически программа представляется в виде последовательности восьми разделов:

Описание внешних модулей, процедур и функций

Описание типов переменных

Описание функций и процедур

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

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

Program — Заголовок программы

Uses – раздел подключения модулей

Begin – открывающая логическая скобка

End – закрывающая логическая скобка

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

Var – раздел описания переменных

Writeln, Write – операторы вывода информации

Readln, Read – операторы ввода информации

If then – оператор условного перехода

For := to do – оператор цикла с параметром

Repeat until — оператор цикла с постусловием

Clrscr – очистка экрана

Initgraph – процедура инициализации графического режима

Closegraph – процедура закрытия графического режима

Line (x1, y1, x2, y2) – соединение двух точек отрезком

Putpixel (x, y, c) – построение точки (x, y) цветом с

Readkey – оператор считывание кода клавиш

Outtextxy (x, y, st) – вывод строки st, начиная с точки (x,y)

Getmaxx – результатом этой функции будет max значение x в данном видеорежиме

Goto – перейти к

+ — арифметическая операция сложения

— — арифметическая операция вычитания

* — арифметическая операция умножения

/ — арифметическая операция деления

Описание переменных и констант используемых в алгоритме

n – количество узлов в таблице, не считая начальную точку />;

/>— значения узлов записанных в одномерные массивы;

D – переменная, используемая для нахождения значения полинома Ньютона в этой точке;

L – переменная значения полинома Ньютона

k, step – константы используемые для построения графика полинома;

u – переменная шага деления графика;

Для описания алгоритма в данной курсовой работе были пронумерованы символы.

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

Читайте также: