Алгоритмирование вычислительных процессов

Алгоритмирование вычислительных процессов

МИНИСТЕРСТВО ТРАНСПОРТА И СВЯЗИ УКРАИНЫ

Днепропетровский Национальный Университет железнодорожного транспорта имени академика В. Лазаряна

Кафедра: «КИТ»

Лабораторная работа №1

по дисциплине: «Алгоритмирование вычислительных процессов»

по теме:

«Интерполирование функций»

Выполнил: студент 935 группы

Рябека А. А.

Проверила:

Шаповал И. В.

Днепропетровск

Лабораторная работа №1.

Тема:

«Интерполирование функций»

Цель:

Научиться интерполировать функции методом Ла-Гранжа. Написать программу, которая будет интерполировать заданную функцию этим методом.

План

1.       Теория

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

.        Алгоритм задачи (схема Насси-Шнайдермана).

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

.        Визуальная оболочка.

.        Пример работы.

.        Вывод.

1. Теория

Интерполирование

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

Задача интерполяции может возникнуть в практике при:

интерполировании табличных данных;

получении функциональной зависимости по экспериментальным данным, представленным в табличной форме;

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

при дифференцировании и интегрировании.

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

Пусть на отрезке [x0,xn] заданы n+1 точки x0, x1, x2,...,xn, называемые узлами интерполяции, и значения некоторой интерполируемой функции y=f (x) в этих точках, т.е. имеется таблица экспериментальных значений функции y=f (x): y0, y1, y2.....yn.

= f (x0); y1=f (x1); . . .; yn=f (xn). (1.1)

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

(x0)=f (x0)=y0,

......................... (1.2)

..........................(xi)=f (xi)=yi , где i = 0,1,2, ... , n.

Такую задачу называют задачей интерполирования. Точки xi называются узлами интерполяции, функция f (x) - интерполируемой функцией, многочлен Pm(x) - интерполяционным многочленом. Задачей интерполяции, в узком смысле слова, считают нахождение приближенных значений табличной функции при аргументах x, не совпадающих с узловыми. Если значение аргумента x расположено между узлами x0<=x<=xn, то нахождение приближенного значения функции f (x) называется интерполяцией , если аппроксимирующую функцию вычисляют вне интервала [x0,xn], то процесс называют экстраполяцией . Происхождение этих терминов связано с латинскими словами inter - между, внутри, pole - узел, extra - вне.

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

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

При решении задачи интерполирования обычно принимается, что:

интерполируемая функция непрерывна на отрезке [a, b] и в каждой точке имеет конечные производные любого порядка;

узлы интерполирования отличны друг от друга.

Интерполяционный полином в форме Лагранжа

Вывод формулы

Итак, мы ищем полином Ln(x) степени не выше n, значения которого совпадают со значениями yk заданной функции ƒ(x) в узлах xk, где k=1,2,...,n+1 и все узлы различны.

Одним из способов записи интерполяционного полинома является форма Лагранжа. Предположим, что для k=1,2,...,n+1 функции Фn(x) являются полиномами степени n, которые обладают следующим свойством

Тогда полином

будет как раз тем, который нам и нужен, поскольку это полином степени не выше n и Ln(xk) = yk для всех k=1,2,...,n+1.

Функции Фn(x) строятся легко. Действительно, функция

является полиномом степени n, который обращается в ноль для всех xj не равных xk. В точке xk она принимает значение

Тогда

или, что то же самое:

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

Исходные данные:

таблица значений произвольных функций.

Необходимо построить аналитическое выражение, которое сопоставит значения с табличнозаданными в некотором конечном количестве точек.

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

узлами интерполирования, а само полученное выражение - интерполяционным многочленом. Существует несколько способов интерполяции функций:

1)      Параболическое интерполирование.

При интерполяции методом Ла-Гранжа функция строится на основе базиса xn, где n = 0, 1, 2,… .

 , где

Фk(x) - базисная функция.

3.      Алгоритм задачи (схема Насси-Шнайдермана)

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

.h

//---------------------------------------------------------------------------

#ifndef Unit1H

#define Unit1H

//---------------------------------------------------------------------------

#include <Classes.hpp>

#include <Controls.hpp>

#include <StdCtrls.hpp>

#include <Forms.hpp>

#include <Chart.hpp>

#include <ExtCtrls.hpp>

#include <Grids.hpp>

#include <Series.hpp>

#include <TeEngine.hpp>

#include <TeeProcs.hpp>

//---------------------------------------------------------------------------TForm1 : public TForm

{

__published:        // IDE-managed Components*StringGrid1;*Chart1;*Edit1;*Label1;*Series1;*Series2;*Button1;*Button2;*Button3;__fastcall Button3Click (TObject *Sender);__fastcall Button1Click (TObject *Sender);__fastcall Button2Click (TObject *Sender);:    // User declarations:                // User declarations

__fastcall TForm1 (TComponent* Owner);Langrang (double*x, double*y, double xt, int N)

{L, Lg;i, j;= 0;(i = 0; i < N; i++)

{= 1;(j = 0; j < N; j++)

{(i != j)*= (xt-x[j])/(x[i]-x[j]);

}= L + y[i]*Lg;

}L;

}

};

//---------------------------------------------------------------------------PACKAGE TForm1 *Form1;

//---------------------------------------------------------------------------

#endif.cpp

//---------------------------------------------------------------------------

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma resource "*.dfm"*Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1 (TComponent* Owner)

: TForm (Owner)

{

}

//---------------------------------------------------------------------------__fastcall TForm1::Button3Click (TObject *Sender)

{-> Cells[0][0] = "x";-> Cells[1][0] = "y";-> RowCount = StrToInt (Edit1 -> Text) + 1;-> Visible = true;

}

//---------------------------------------------------------------------------__fastcall TForm1::Button1Click (TObject *Sender)

{i;(i = 1; i <= StrToInt (Edit1 -> Text); i++)

{x = StrToFloat (StringGrid1 -> Cells[0][i]);y = StrToFloat (StringGrid1 -> Cells[1][i]);-> AddXY (x, y, ' ', clRed);

}

}

//---------------------------------------------------------------------------__fastcall TForm1::Button2Click (TObject *Sender)

{N = StrToInt (Edit1 -> Text);*ax;= new double [N];*ay;= new double [N];(int i = 0; i < N; i++)

{[i] = StrToFloat(StringGrid1 -> Cells[0][i+1]);[i] = StrToFloat(StringGrid1 -> Cells[1][i+1]);

}h = (ax[N-1]-ax[0])/(2*N);(double x = ax[0]; x <= ax[N-1]; x = x + h)

{y = Langrang( ax, ay, x, N);-> AddXY (x, y, ' ', clGreen);

}

//---------------------------------------------------------------------------

5.      Визуальная оболочка

6.     
Пример работы

Начальный вид при запуске:

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

Вводим 5.

Нажимаем кнопку создать таблицу и вводим в нее произвольные данные:Y

3

5

7

6

5

Нажимаем кнопку построить график, в результате чего получаем:

Нажимаем кнопку интерполяция и в результате получаем:

Полученный график является верным.

7.      Вывод

интерполирование функция полином лагранж

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