Интерполационна формула на Нютон. Интерполационните полиноми на Нютон Първата интерполационна формула на Нютон

Изпратете добрата си работа в базата знания е лесно. Използвайте формата по-долу

Студенти, докторанти, млади учени, които използват базата от знания в обучението и работата си, ще ви бъдат много благодарни.

публикувано на http://www.allbest.ru/

Москва Държавен университетприборостроене и компютърни науки клон Сергиев Посад

Резюме по темата:

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

Изпълнител: Бревчик Таисия Юриевна

Студент 2 курс група ЕФ-2

1. Въведение

2. Първата интерполационна формула на Нютон

3. Втората интерполационна формула на Нютон

Заключение

Библиография

Въведение

Интерполация, интерполация - в изчислителната математика, метод за намиране на междинни стойности на количество от съществуващ дискретен набор от известни стойности.

Много от тези, които се занимават с научни и инженерни изчисления, често трябва да работят с набори от стойности, получени емпирично или чрез произволно вземане на проби. Като правило, въз основа на тези набори, е необходимо да се конструира функция, в която други получени стойности могат да попаднат с висока точност. Този проблем се нарича апроксимация. Интерполацията е вид приближение, при което кривата на построената функция минава точно през наличните точки от данни.

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

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

Също така си струва да се спомене напълно различен тип математическа интерполация, известна като операторна интерполация.

Класическите трудове по операторна интерполация включват теоремата на Riesz-Thorin и теоремата на Marcinkiewicz, които са в основата на много други работи.

Нека разгледаме система от несъвпадащи точки () от определен регион. Нека стойностите на функцията са известни само в тези точки:

Проблемът с интерполацията е да се намери функция от даден клас функции, така че

Точките се наричат ​​интерполационни възли, а тяхната колекция се нарича интерполационна мрежа.

Двойките се наричат ​​точки от данни или базови точки.

Разликата между „съседните“ стойности е стъпката на интерполационната мрежа. Тя може да бъде променлива или постоянна.

Функцията е интерполираща функция или интерполант.

1. Първата интерполационна формула на Нютон

1. Описание на задачата.Нека на функцията са дадени стойности за еднакво разпределени стойности на независимата променлива: , където - стъпка на интерполация. Изисква се да се избере полином със степен не по-висока, като се вземат в точки стойностите

Условия (1) са еквивалентни на тези при.

Интерполационен полином на Нютон има формата:

Лесно се вижда, че полиномът (2) напълно удовлетворява изискванията на задачата. Наистина, първо, степента на полинома не е по-висока, и второ,

Обърнете внимание, че когато формула (2) се превърне в серия на Тейлър за функцията:

За практическа употреба интерполационната формула на Нютон (2) обикновено се записва в леко трансформирана форма. За да направим това, въвеждаме нова променлива, използвайки формулата; тогава получаваме:

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

Благоприятно е да се използва формула (3) за интерполиране на функцията в близост до първоначалната стойност , където е малко по абсолютна стойност.

Ако е дадена неограничена таблица с функционални стойности, тогава числото във формулата за интерполация (3) може да бъде всяко. На практика в този случай числото се избира така, че разликата да е постоянна с дадена степенточност. Всяка таблична стойност на аргумента може да бъде взета като начална стойност.

Ако таблицата с функционални стойности е крайна, тогава броят е ограничен, а именно: не може да има повече от броя на функционалните стойности, намалени с една.

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

2. Пример. Като предприемете стъпката, конструирайте интерполационния полином на Нютон за функцията, дадена от таблицата

Полученият полином дава възможност за прогнозиране. Получаваме достатъчна точност при решаване на проблем с интерполация, например, .Точността пада при решаване на проблем с екстраполация, например, .

2. Втората интерполационна формула на Нютон

Първата интерполационна формула на Нютон е практически неудобна за интерполиране на функция близо до възли на таблица. В този случай обикновено се използва .

Описание на задачата . Нека имаме последователност от функционални стойности

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

или, използвайки обобщената мощност, получаваме:

Тогава, ако равенството е валидно, получаваме

Нека заместим тези стойности във формула (1). Тогава, най-накрая, Втората интерполационна формула на Нютон има формата:

Нека въведем по-удобно обозначение за формула (2). Нека бъде тогава

Замествайки тези стойности във формула (2), получаваме:

Това е обичайният изглед Втората интерполационна формула на Нютон. За приблизително изчисляване на стойностите на функцията приемете:

Както първата, така и втората формула за интерполация на Нютон могат да се използват за екстраполиране на функция, тоест за намиране на стойности на функции за стойности на аргументи извън таблицата.

Ако е близо до, тогава е изгодно да се приложи първата интерполационна формула на Нютон, а след това. Освен това, ако е близо до, тогава е по-удобно да се използва втората интерполационна формула на Нютон.

Така първата интерполационна формула на Нютон обикновено се използва за интерполация напредИ екстраполиране назад, и втората интерполационна формула на Нютон, напротив, за интерполиране назадИ екстраполация напред.

Имайте предвид, че операцията на екстраполация, най-общо казано, е по-малко точна от операцията на интерполация в тесния смисъл на думата.

Пример. Като предприемете стъпката, конструирайте интерполационния полином на Нютон за функцията, дадена от таблицата

Заключение

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

В изчислителната математика съществена роля играе интерполацията на функциите, т.е. Използване на дадена функция, конструиране на друга (обикновено по-проста) функция, чиито стойности съвпадат със стойностите на дадената функция в определен брой точки. Освен това интерполацията има както практическо, така и теоретично значение. На практика често възниква проблемът с възстановяването непрекъсната функцияспоред неговите таблични стойности, например получени по време на някакъв експеримент. За да се оценят много функции, е ефективно да се приближат с помощта на полиноми или дробни рационални функции. Теорията на интерполацията се използва при конструирането и изследването на квадратурни формули за числено интегриране, за получаване на методи за решаване на диференциални и интегрални уравнения.

Библиография

1. В.В. Иванов. Компютърни методи за изчисление. Справочно ръководство. Издателство "Наукова думка". Киев. 1986 г.

2. Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобелков. Числени методи. Издателство "Лаборатория за базови знания". 2003 г.

3. И.С. Березин, Н.П. Жидков. Методи за изчисление. Изд. PhysMatLit. Москва. 1962 г.

4. К. Де Бор. Практическо ръководство за сплайни. Издателство "Радио и съобщения". Москва. 1985 г.

5. Дж. Форсайт, М. Малкълм, К. Моулър. Машинни методи за математически изчисления. Издателство "Мир". Москва. 1980 г.

Публикувано на Allbest.ru

...

Подобни документи

    Приложение на първата и втората интерполационни формули на Нютон. Намиране на стойности на функции в точки, които не са таблични. Използване на формулата на Нютон за неравни точки. Намиране на стойността на функция с помощта на интерполационната схема на Aitken.

    лабораторна работа, добавена на 14.10.2013 г

    Йохан Карл Фридрих Гаус е най-великият математик на всички времена. Интерполационни формули на Гаус, които дават приблизителен израз на функцията y=f(x) с помощта на интерполация. Области на приложение на формулите на Гаус. Основните недостатъци на интерполационните формули на Нютон.

    тест, добавен на 12/06/2014

    Интерполиране на функция в точка, разположена в близост до средата на интервала. Интерполационни формули на Гаус. Формула на Стърлинг като средно аритметично на формули за интерполация на Гаус. Кубичният сплайн функционира като математически моделтънък прът.

    презентация, добавена на 18.04.2013 г

    Непрекъсната и точкова апроксимация. Интерполационни полиноми на Лагранж и Нютон. Глобална интерполационна грешка, квадратична зависимост. Метод на най-малките квадрати. Избор на емпирични формули. Частично постоянна и частично линейна интерполация.

    курсова работа, добавена на 14.03.2014 г

    Методи на акорди и итерации, правило на Нютон. Интерполационни формули на Лагранж, Нютон и Ермит. Точкова квадратична апроксимация на функция. Числено диференциране и интегриране. Числено решаване на обикновени диференциални уравнения.

    курс от лекции, добавен на 11.02.2012 г

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

    тест, добавен на 06/02/2011

    В изчислителната математика интерполацията на функциите играе важна роля. Формула на Лагранж. Интерполация по схемата на Aitken. Интерполационни формули на Нютон за равноотдалечени възли. Формула на Нютон с разделени разлики. Сплайн интерполация.

    тест, добавен на 01/05/2011

    Изчисляване на производната по нейната дефиниция, като се използват крайни разлики и се основава на първата интерполационна формула на Нютон. Интерполационни полиномиЛагранж и приложението им в числова диференциация. Метод Рунге-Кута (четвърти ред).

    резюме, добавено на 03/06/2011

    Краища на различни поръчки. Връзка между терминални разлики и функции. Дискретен и непрекъснат анализ. Разбиране за разделенията. Интерполационна формула на Нютон. Актуализация на формулите на Лагранж и Нютон. Интерполация за еднакво отдалечени възли.

    тест, добавен на 02/06/2014

    Намиране на интерполационни полиноми на Лагранж и Нютон, преминаващи през четири точки на дадена функция, сравнявайки техните представителства на степенния закон. Решение на нелинейни диференциално уравнениеМетод на Ойлер. Решаване на системи алгебрични уравнения.

Лекция 4

1. Крайни разлики
2. Първа интерполационна формула
Нютон
3. Втора интерполационна формула
Нютон
4. Грешки при интерполация

Крайни разлики от 1-ви ред

Ако интерполираната функция y = f(x) е дадена в
еднакво разположени възли, така че xi = x0 + i∙h, където h е стъпката на таблицата и
i = 0, 1, … n, тогава формулите могат да се използват за интерполация
Нютон с помощта на крайни разлики.
Крайната разлика от първи ред е разликата yi
= yi+1 - yi, където
yi+1= f(xi+h) и yi = f(xi). За дадената функция
табличен в (n+1) възли, i = 0, 1, 2, …, n, крайни разлики
първият ред може да се изчисли в точки 0, 1, 2,…, n - 1:
y 0 y1 y 0,
y1 y 2 y1,
.......................
yn 1 yn yn 1.

Крайни разлики от по-висок порядък

Използвайки крайни разлики от първи ред, човек може
получете крайни разлики от втори ред 2yi = yi+1 - yi:
2 y 0 y1 y 0 ;
2 y1 y 2 y1;
..........................
2 y n 2 y n 1 y n 2 .
Крайни разлики от k-ти ред във възел номер i can
се изчислява чрез разлики от (k-1)-ти ред:
k yi k 1yi 1 k 1yi
Всички крайни разлики могат да бъдат изчислени чрез стойностите
функции в интерполационни възли, например:
2 y 0 y1 y 0 (y 2 y1) (y1 y 0) y 2 2y1 y 0 .

Таблица с крайни разлики

х
г
Δy
Δ2y
Δ3г
x0
y0 Δy0 = y1 – y0 Δ2y0 = Δy1 – Δy0 Δ3y0 = Δ2y1 – Δ2y0
x1 = x0 + h
y1 Δy1 = y2 – y1 Δ2y1 = Δy2 – Δy1
x2 = x0 + 2h
y2 Δy2 = y3 – y2
x3 = x0 + 3h
y3

Въз основа на големината на крайните разлики може
направи
заключение
О
степени
интерполация
полином,
описващ
табличен
дадено
функция.
Ако
За
маси
с
равноотдалечени
възли
финал
разликите от k-ти ред са постоянни или
тогава са съизмерими с дадена грешка
функцията може да бъде представена като полином
k-та степен.

Крайни разлики и степен на полином

Помислете например за таблицата с крайни разлики за
полином y = x2 – 3x + 2.
0
г
-0.16
2 г
0.08
3 г
0
1.2
-0.16
-0.08
0.08
0
1.4
-0.24
0
0.08
1.6
-0.24
0.08
1.8
-0.16
х
г
1.0
Крайните разлики от трети ред са равни на нула и всички
крайните разлики от втори ред са еднакви и равни на 0,08. Това
казва, че функция, дадена в таблица, може да бъде
го представи като полином от степен 2 (очакван резултат,
предвид начина на получаване на таблицата).

Нека функцията y = f(x) е определена в n+1 еднакво отдалечени възли xi, i = 0, 1,
2,...n със стъпка h. Трябва да намерим интерполационния полином Pn(x)
степен n, отговаряща на условието:
Pn(xi) = yi, i =0, 1, 2, …,n.
Ще търсим интерполационен полином във формата:
Pn(x) = a0 + a1(x-x0) + a2(x-x0)(x-x1) + … + an(x-x0)(x-x1)…(x-xn-1),
където аi, i = 0, 1, 2,…n – неизвестни коефициенти, независими от възлите
интерполация. Нека намерим тези коефициенти от условията на интерполация.
Нека x = x0, тогава Pn(x0) = y0 = a0. Следователно a0 = y0.
Нека x = x1, тогава Pn(x1) = y1 = a0 + a1(x1 - x0) = y0 + a1(x1 - x0), откъдето
a1
y1 y0 y0
.
х1 х0
ч
Сега нека x = x2, тогава:
Pn (x 2) y 2 a0 a1(x 2 -x 0) a2 (x 2 -x 0)(x 2 -x1) y 0
y 0
2h a2 2h2.
ч
Изразявайки a2 от този израз, получаваме:
y 2 2 y0 y0 y 2 2(y1 y0) y0 y 2 2y1 y 0 2 y 0
a2
.
2h2
2h2
2h2
2h2

Първата интерполационна формула на Нютон

Продължавайки заместванията, можем да получим израз за всяко
коефициент с число i:
i y 0
ai
,
аз! здрасти
i 0,1,...,n.
Замествайки намерените стойности на коефициентите в оригиналния израз,
получаваме първата интерполационна формула на Нютон:
y0
2y0
n y 0
Pn(x)y0
(x x0)
(x x 0)(x x1) ...
(x x 0)...(x x n 1).
1!ч
2!h2
n!hn
Формулата показва, че използва горния ред на таблицата
крайни разлики (слайд 4). Особеност на формулата е също
последователно увеличаване на степента на полинома при добавянето му
следващи условия. Това ви позволява да прецизирате резултатите, получени без
преизчисляване на вече взети предвид условия.

Първата интерполационна формула на Нютон

Първата интерполационна формула на Нютон може да бъде написана в
в по-компактна и удобна за софтуерна реализация форма.
Като определи
р
x x0
,
ч
x x 0 qh
и извършване на прости трансформации на формата:
x x1 x x 0 ч
q 1;
ч
ч
x xn
x x2
qn 1,
q 2;.....;
ч
ч
получаваме първата интерполационна формула на Нютон, изразена
спрямо неизвестен q:
n y 0
2y0
q(q 1)...(q n 1).
q(q 1) ...
Pn (x) Pn (x0 hq) y0 y0q
н!
2!

10. Първата интерполационна формула на Нютон

Крайни разлики от по-високи порядъци, използвани във формулата
Нютон, обикновено имат голяма грешка, свързана с грешки
закръгляване при изваждане на близки стойности. Следователно съответните
членовете на формулата също имат голяма грешка. Да намалява
техният принос към сумата, тоест към крайния резултат, трябва да бъде изпълнен
условие |q|< 1. Это обеспечивается, если точка интерполяции x находится
между първите два възела на таблицата: x0< x < x1. По этой причине
интерполация с помощта на първата формула на Нютон се нарича
интерполация в началото на таблицата или интерполация напред.

интерполация Първата интерполационна формула на Нютон взема
следната форма:
P1(x) y0 y0q.
P2 (x) y 0 y 0 q 2 y 0
q(q 1)
.
2

11. Пример за използване на първата интерполационна формула на Нютон


както в примера на слайд 6. Трябва да намерите приблизителна
стойността на функцията в точка x = 1,1 по квадрат
интерполация с помощта на първата формула на Нютон.
х
1.0
1.2
1.4
1.6
1.8
г
0
-0.16
-0.24
-0.24
-0.16
г
-0.16
-0.08
0
0.08
2г 3г
0.08 0
0.08 0
0.08
Стъпка на таблицата h = 0,2
q = (x – x0)/h = 0,5
q(q 1)
2
0.5(0.5 1)
0 (0.16) 0.5 0.08
0.09
2
P2 (x) y 0 Δy 0 q Δ 2 y 0
Резултатът съвпада
стойността на полинома
y = x2 – 3x + 2, от което
получена маса

12. Схема на алгоритъма за изчисление с помощта на първата интерполационна формула на Нютон

13. Втората интерполационна формула на Нютон

Втората формула на Нютон има подобни свойства
спрямо дясната страна на масата. За да го изградите, използвайте
полином от формата:
Pn(x) = a0 + a1(x-xn) + a2(x-xn)(x-xn-1) + … + an(x-xn)(x-xn-1)…(x-x1),
където аi, i = 0, 1, 2, … n са коефициенти, които не зависят от интерполационните възли.
За да определим коефициентите ai, ще използваме този израз един по един
заместващи интерполационни възли. Следователно за x = xn Pn(xn) = yn,
a0 = yn.
За x = xn-1 имаме Pn(xn-1) = yn-1 = a0 + a1(xn-1-xn) = yn + a1(xn-1-xn),
където
a1
yn 1 yn yn yn 1 yn 1
.
xn 1 xn xn xn 1
ч

14. Втората интерполационна формула на Нютон

Продължавайки заместванията, получаваме изрази за всички коефициенти
полином и втората интерполационна формула на Нютон:
n y 0
yn 1
2ин 2
Pn(x)yn
(x xn)
(x xn)(x xn 1)
(x xn)...(x x1).
2
н
1!ч
2 ч
n!h
Формулата показва, че използва долния диагонал на таблицата
крайни разлики (слайд 4). Както в първата формула на Нютон, добавяне
последователните термини водят до последователно повишаване на степента
полином, който ви позволява да изясните резултата, без да преизчислявате
взети под внимание условия.
Чрез въвеждане на нотацията: q
x xn
,
ч
x xn hq
и след извършване на прости трансформации получаваме втората интерполация
Формула на Нютон, изразена по отношение на заместващата променлива q:
n y 0
2ин 2
Pn (x) yn yn 1q
q(q 1) ...
q(q 1)...(q n 1).
2!
н!

15. Втората интерполационна формула на Нютон

От същите съображения, както в случая с първата формула на Нютон, за
За намаляване на изчислителната грешка е необходимо условието да е изпълнено
|q|< 1. Это обеспечивается, если точка интерполяции x находится между
последните два възела на таблицата: xn-1< x < xn. По этой причине
интерполация с помощта на втората формула на Нютон се нарича
интерполация от края на таблицата или обратна интерполация.
За специални случаи на линеен (n=1) и квадратичен (n=2)
интерполация Втората интерполационна формула на Нютон взема
следната форма:
P1 (x) y n y n 1q
2 y n 2
P2 (x) y n y n 1 q
q(q 1)
2!

16. Пример за използване на втората интерполационна формула на Нютон

Нека интерполираната функция f(x) е дадена от същата таблица,
както в примера на слайд 11. Трябва да намерите приблизителна
стойност на функцията в точка x = 1,7 по квадрат
интерполация с помощта на втората формула на Нютон.
х
1.0
1.2
1.4
1.6
1.8
г
0
-0.16
-0.24
-0.24
-0.16
г
-0.16
-0.08
0
0.08
2г 3г
0.08 0
0.08 0
0.08
Стъпка на таблицата h = 0,2
q = (x – xn)/h = -0,5
Резултатът съвпада
стойността на полинома
y = x2 – 3x + 2, от
която е получена
маса
q(q 1)
2
0.5(0.5 1)
0.16 0.08 (0.5) 0.08
0.21
2
P2 (x) y n Δy n 1 q Δ 2 y n 2

17. Схема на алгоритъма за изчисление с помощта на втората интерполационна формула на Нютон

18. Грешки при интерполация

Интерполираща функция в точки между
интерполационните възли заменят интерполирането
функция приблизително:
f(x) = F(x) + R(x), където R(x) е грешката
интерполация.
За оценка на грешката е необходимо да има
е необходимо да има определена информация за
интерполирана функция f(x). Нека се преструваме, че
f(x) е дефинирано в сегмента, съдържащ всички
възли xi и за x, принадлежащи на , има всички
производни f"(x), f""(x), … f(n+1)(x) до (n+1)th
поръчка включително.

19. Грешки при интерполация

Тогава

20. Избор на интерполационни възли по формулата на Лагранж

За фиксирана степен на полином:
х*
x0
x1
x2
x3
x4
x5
х
С последователно повишаване на степента
полином
х*
x4
x2
x0
x1
x3
x5
х

21. Практическа оценка на интерполационната грешка по формулата на Лагранж

На практика, оценяването на максималната стойност на производната на (n+1)-та
ред Mn+1 рядко е възможен при използване на формулата на Лагранж,
и следователно използвайте приблизителна оценка на грешката
R n (x) f(x) Ln (x) Ln 1 (x) Ln (x) ,
където n е броят на използваните възли.
От горната формула следва, че за оценка на грешката
необходима е интерполация с полином на Лагранж от n-та степен
допълнително изчислете стойността на полином от (n+1) степен. Ако
е дадена допустимата грешка на интерполация, тогава е необходимо да се добавят всички
нови възли, увеличете степента на полинома до модула
разлика между последните две стойности на полинома |Ln+1(x)-Ln(x)| Не
ще стане по-малко от зададената стойност.

22. Схема на алгоритъма за интерполация, използващ формулата на Лагранж с дадена точност

23. Оценка на грешките на интерполационните формули на Нютон

За интерполация
приеме следната форма.
Първата формула на Нютон:
Rn(x)h
n 1
формули
Нютон
оценки
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
2-ра формула на Нютон:
Rn(x)h
n 1
q(q 1) (q n) (n 1)
f
(n 1)!
R n (x) h n 1
q(q 1) (q n)
M n 1
(n 1)!
грешки

24. Практическа оценка на грешките в интерполационните формули на Нютон

Когато се използват интерполационните формули на Нютон, стойността
f(n+1)(ξ) може да бъде приблизително оценен от стойностите на крайните разлики:
f
(n 1)
n 1
Δy0
() n 1
ч
и в този случай формулите за оценка на грешката приемат следното
изглед:
Първата формула на Нютон:
Rn(x)
q(q 1) (q n) n 1
Δy0
(n 1)!
2-ра формула на Нютон:
Rn(x)
q(q 1) (q n) n 1
Δy0
(n 1)!

25. Интерполация по формулите на Нютон с определена точност

Сравняване на тези формули с формули
Нютон, човек може да види това, за да оцени
грешки при интерполиране с полином
n-та степен трябва да вземете допълнителен възел
и изчислете члена на (n+1)-та степен.
Ако е посочена допустимата грешка
интерполация ε, тогава е необходимо последователно
добавете нови възли и съответно
нови условия, повишаване на степента
интерполационен полином до
докато следващият член стане по-малък от ε.

анотация

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


Въведение

Анализ на работата

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

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

Преглед на литературни източници

Разработване на програма по схемата на алгоритъма

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

Програмен текст

Изходни данни и резултат от решаването на тестовия случай

Заключение

Списък на използваните източници


Въведение

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

Сложните изчислителни проблеми, които възникват при изучаването на физически и технически проблеми, могат да бъдат разделени на няколко елементарни, като например изчисляване на интеграл, решаване на диференциално уравнение и т.н. Много елементарни проблеми са прости и добре изучени. За тези проблеми вече са разработени методи за числено решаване и често има стандартни компютърни програми за решаването им. Има и доста сложни елементарни задачи; Сега интензивно се разработват методи за решаване на такива проблеми.

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


Анализ на работата

Следните са използвани като входни данни:

1. Брой възли.

2. Таблични стойности на функцията.

Изходни данни, т.е. Резултатът от програмата е:

1. Стойности на определена от таблица функция в междинни стойности.

2. Полиномна графика.


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

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

Интерполация и апроксимация на функции.

1. Постановка на проблема.

Един от основните проблеми на числения анализ е проблемът за интерполацията на функции. Често е необходимо да се възстанови функцията

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

Нека и" сегмент

решетка с

и стойностите на функцията са посочени в нейните възли

, равен.

Изисква се конструиране на интерполант – функция

, съвпадаща с функцията във възлите на мрежата: .

Основната цел на интерполацията е да се получи бърз (икономичен) алгоритъм за изчисляване на стойности

за стойности, които не се съдържат в таблицата с данни.

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

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

аз
0
1
2
.. .. ..
н
, (1)

Точки с координати

се наричат ​​възлови точки или възли.

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

Необходимо е да се намери стойността на тази функция в междинна точка, например

, и . За решаване на проблема се използва интерполационен полином.

Интерполационният полином според формулата на Нютон има формата:

където n е степента на полинома,

Интерполационната формула на Нютон ви позволява да изразите интерполационния полином

чрез стойността в един от възлите и чрез разделените разлики на функцията, изградена над възлите.

Първо, предоставяме необходимата информация за отделните разлики.

Пуснете възли

,

стойностите на функцията са известни

. Да приемем, че сред точките , , няма съвпадащи. Разделените разлики от първи ред се наричат ​​отношения , , .

Ще разгледаме разделени разлики, съставени от съседни възли, т.е. изрази

Доста често срещан метод на интерполация е методът на Нютон. Интерполационният полином за този метод има формата:

P n (x) = a 0 + a 1 (x-x 0) + a 2 (x-x 0)(x-x 1) + ... + a n (x-x 0)(x-x 1)...(x-x n-1).

Задачата е да се намерят коефициентите a i на полинома P n (x). Коефициентите се намират от уравнението:

P n (x i) = y i , i = 0, 1, ..., n,

което ви позволява да напишете системата:

a 0 + a 1 (x 1 - x 0) = y 1 ;

a 0 + a 1 (x 2 - x 0) + a 2 (x 2 - x 0)(x 2 - x 1) = y 2 ;

- - - - - - - - - - - - - - - - - - - - - - - - - - - -

a 0 +... + a n (x n - x 0)(x n - x 1) ... (x n - x n-1) = y n;

Използваме метода на крайните разлики. Ако възлите x i са дадени на равни интервали h, т.е.

x i+1 - x i = h,

след това в общ случай x i = x 0 + i×h, където i = 1, 2, ..., n. Последният израз ни позволява да редуцираме решаваното уравнение до вида

y 1 = a 0 + a 1 ×h;

y 2 = a 0 + a 1 (2h) + a 2 (2h)h;

- - - - - - - - - - - - - - - - - - -

y i = a 0 + a 1 ×i×h + a 2 ×i×h[(i-1)h] + ... + a i ×i!×h i,

откъдето получаваме коефициентите

където Dу 0 е първата крайна разлика.

Продължавайки изчисленията, получаваме:

където D 2 y 0 е втората крайна разлика, която е разликата на разликите. Коефициентът a i може да бъде представен като:

Поставяйки намерените стойности на коефициентите a i в стойностите за P n (x), получаваме интерполационния полином на Нютон:

Нека трансформираме формулата, за която въвеждаме нова променлива, където q е броят стъпки, необходими за достигане на точка x, придвижване от точка x 0. След трансформациите получаваме:

Получената формула е известна като първата интерполационна формула на Нютон или формулата на Нютон за интерполация напред. Благоприятно е да се използва за интерполиране на функцията y = f(x) в близост до началната стойност x – x 0, където q е малко по абсолютна стойност.

Ако запишем интерполационния полином във формата:

тогава по подобен начин може да се получи втората интерполационна формула на Нютон или формулата на Нютон за интерполация „назад“:

Обикновено се използва за интерполиране на функция близо до края на таблица.

Когато изучавате тази тема, е необходимо да запомните, че интерполационните полиноми съвпадат с дадена функция f(x) в интерполационните възли и в други точки, в общия случай, ще се различават. Тази грешка ни дава грешката на метода. Грешката на метода на интерполация се определя от остатъчния член, който е еднакъв за формулите на Лагранж и Нютон и който ни позволява да получим следната оценка за абсолютна грешка:

Ако интерполацията се извърши със същата стъпка, тогава формулата за остатъчния член се променя. По-специално, когато се интерполира „напред“ и „назад“, използвайки формулата на Нютон, изразите за R(x) са малко по-различни един от друг.

Анализирайки получената формула, става ясно, че грешката R(x) е, с точност до константа, продукт на два фактора, единият от които, f (n+1) (x), където x лежи вътре, зависи от свойства на функцията f(x) и не могат да бъдат регулирани, но големината на друга,

се определя единствено от избора на интерполационни възли.

Ако местоположението на тези възли е неуспешно, горната граница на модула |R(x)| може да бъде доста голям. Следователно възниква проблемът за най-рационалния избор на интерполационни възли x i (за даден брой възли n), така че полиномът П n+1 (x) да има най-малка стойност.

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

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

аз
0
1
2
.. .. ..
н

Точките с координати се наричат ​​възлови точки или възли.

Броят на възлите в табличната функция е N=n+1.

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

Интерполационният полином според формулата на Нютон има формата:

където n е степента на полинома,

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

Първо, предоставяме необходимата информация за отделните разлики.

Пуснете възли

стойностите на функцията са известни. Да приемем, че сред точките , , няма съвпадащи. Разделените разлики от първи ред се наричат ​​отношения

, ,.

Ще разгледаме разделени разлики, съставени от съседни възли, т.е. изрази

От тези разделени разлики от първи ред можем да конструираме разделени разлики от втори ред:

,

,

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

където , , е степента на полинома.

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

тези. е равна на разликата на разделените разлики от ти ред, разделена на дължината на отсечката.

Разделени различия

са добре дефинирани числа, следователно изразът (1) наистина е алгебричен полином от степен th. Освен това в полинома (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). В резултат на това получаваме

(5)

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

– разделена разлика от ти ред за участъка.



Подобни статии