Xreferat.com » Рефераты по информатике и программированию » Интерполяция функции одной переменной методом Ньютона

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

Аннотация


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

Содержание


Введение

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

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

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

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

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

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

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

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

Заключение

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

Введение


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

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

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


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


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

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

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

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

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

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

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


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

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

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

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

Пусть и» отрезке Интерполяция функции одной переменной методом Ньютона задана сетка со


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


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


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


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


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


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

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

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

i

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

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

0

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

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

1

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

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

2

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

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

.. .. ..
n

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

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


Или


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


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

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

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

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


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


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

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

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

Пусть в узлах


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


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


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


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


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


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


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

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

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


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


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


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

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


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


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

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


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


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

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

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

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







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




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

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


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





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

•

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

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

• • •

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

■ • • •

• • •

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



• •

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




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

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






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


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


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


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


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


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


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

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


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


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

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


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

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

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


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

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


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


где

Интерполяция функции одной переменной методом Ньютона– значение табличной функции (1) для Интерполяция функции одной переменной методом Ньютона.

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


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


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


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

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


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

var

l:real;

k,i:integer;

p: real;

begin

L:=y[0];

P:=1;

for k:=1 to n do begin

P:=P*(D-X[k-1]);

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

Y[i]:=(y[i+1]-y[i])/(x[i+k]-x[i]);

end;

L:=L+P*y[0];

end;

Polinom:=l;

end;


где

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

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

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


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


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

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

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

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

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

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

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

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

Похожие рефераты: