Алгоритмирование вычислительных процессов
МИНИСТЕРСТВО
ТРАНСПОРТА И СВЯЗИ УКРАИНЫ
Днепропетровский
Национальный Университет железнодорожного транспорта имени академика В.
Лазаряна
Кафедра:
«КИТ»
Лабораторная
работа №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. Алгоритм задачи (схема
Насси-Шнайдермана)
Ввод
значений функций x, y
|
L
= 0
|
i
є [1, N]
|
|
Lg
= 1
|
|
j
є [1, N]
|
|
|
i
!= j
|
|
|
Lg
= (Lg*(x - x[j]))/(x[i] - x[j])
|
|
|
j
= j +1
|
|
|
L
= L + y[i]*Lg
|
|
|
i
= i + 1
|
|
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. Вывод
интерполирование функция полином
лагранж
При выполнении работы я изучил основы
интерполирования функций, научился использовать метод Ла-Гранжа для
интерполирования функций, освоил построение интерполяционных графиков, а также
узнал о значительном недостатке данного метода - значения крайних точек графика
чаще всего очень разные с реальными значениями.