Нека разгледаме концепцията крайни разлики.
Нека функцията е дадена y=f(x)върху отсечката [x 0 , x„], която е разделена на Пидентични сегменти (случаят на равноотдалечени стойности на аргумент): Ax=h =конст. За всеки възел х 0,Х, =x 0 + /G, ...,Х" =x()+ н чСтойностите на функцията са определени във формуляра
Нека представим концепцията крайни разлики.
Крайни разликипърва поръчка
Крайни разлики от втори ред 
Крайните разлики от по-високи порядъци се дефинират по подобен начин: 
Удобно е крайните разлики на функции да се поставят в таблици, които могат да бъдат диагонални (Таблица 5.1) или хоризонтални (Таблица 5.2).
Диагонална маса
Таблица 5.1
Хоризонтална маса
Таблица 5.2
|
на 5 години, |
||||||
|
A 5 Uo |
||||||
|
и 4 г. |
||||||
Първата интерполационна формула на Нютон
Нека на функцията y=/(x) са дадени стойностите y, =/(x), за равни стойности на независимите променливи:
Където ч- стъпка на интерполация.
Трябва да намерим полином P„(x)градуса ns по-високи П,получаване в точки (възли) x, стойности:
Интерполиращият полином се търси във формата:
Задачата за конструиране на полином се свежда до определяне на коефициентите а,от условията:
Приемаме в (5.13) x = x 0, тъй като вторият, третият и другите членове са равни на 0, тогава 
Нека намерим коефициента A ( .
Цени = X1 получаваме:
За определяне а 2Нека направим крайна разлика от втори ред. При х=х 2получаваме:
Други коефициенти могат да бъдат намерени по подобен начин. Обща формулаима формата:
Замествайки тези изрази във формула (5.13), получаваме:
където x„ y x- интерполационни възли; х- текуща променлива; ч- разлика между два интерполационни възела; ч- стойността е постоянна, т.е. интерполационните възли са на еднакво разстояние един от друг.
Този полином се нарича Интерполационен полином на Нютонза интерполиране в началото на таблицата (интерполация напред), или Първият полином на Нютон.
За практическа употреба този полином е написан в трансформирана форма чрез въвеждане на нотацията t=(x - x 0)/h,Тогава
Тази формула е приложима за изчисляване на стойности на функции за стойности на аргументи, близки до началото на интервала на интерполация.
Блокова диаграма на алгоритъма на метода на Нютон за интерполация напред е показана на фиг. 5.3, програма - в прил.
Пример 5.3. Дадена е таблица на топлинния капацитет на веществото в зависимост от температурата C p =f(T)(Таблица 5.3).
Таблица 5.3
Нека използваме формула (5.16):
Ориз. 5.3.
След извършване на трансформациите получаваме интерполационен полином от формата:
Полиномът има трета степен и дава възможност да се изчисли стойността по намерената формула приза неизвестното Х.
Пример 5.4.В табл 5.3.1 показва стойностите на топлинния капацитет в зависимост от температурата. Определете стойността на топлинния капацитет в точка Г=450 K.
Нека използваме първата интерполационна формула на Нютон. Крайните разлики бяха изчислени в предишния пример (Таблица 5.3.2), записваме интерполационния полином при x=450 K:
По този начин топлинният капацитет при температура от 450 K ще бъде
Стойността на топлинния капацитет при Г=450 К е същата като тази, изчислена по формулата на Лагранж.
Втората интерполационна формула на Нютон
За да се намерят стойностите на функциите в точки, разположени в края на интервала на интерполация, се използва вторият интерполационен полином на Нютон. Нека запишем интерполационния полином във формата
Коефициенти a 0, a b..., а"определя се от условието:
Приемаме в (5.18) х=х„,Тогава
Ние вярваме х=x„_|, тогава следователно, 
Ако x = x n - 2 iЧе
По същия начин можете да намерите други коефициенти на полинома (5.18):
Замествайки тези изрази във формула (5.18), получаваме Втората интерполационна формула на Нютон,или полином на Нютон за "обратна" интерполация:
Нека въведем следната нотация: 
Правейки заместване в (5.19), получаваме:
Това е втората формула на Нютон за обратна интерполация.
Пример 5.5. Изчислете топлинния капацитет (вижте таблица 5.3) за температура Г=550 К.
Нека използваме втората формула на Нютон (5.19) и съответните крайни разлики (вижте таблица 5.4):
Следователно стойността на топлинния капацитет при температура 550 K е
ИНТЕРПОЛАЦИЯ
Нека функцията y = f(х) се дефинира върху решетка от еднакво разположени възли x i=х 0 +их,Където аз = 0,1, ..., П,и за него е конструирана таблица на крайните разлики в § 16.3.
В съответствие с казаното за посоката на модификация на интерполационната формула на Лагранж в началото на предишния параграф, ще изградим интерполационен полином R p(х) във формата на
P n(х)= а 0 +a 1 (х-х 0)+ а 2 (х-х 0)(х-х 1)+... + a n(х-х 0)(х-х 1) … (x-x n - 1). (17.1)
Неговата n+ 1 коефициент А 0 , А 1 , ..., a nще намерим последователно от П+1 интерполационни равенства
P n(x i)=y i, аз = 0,1, ..., П.
А именно, ако приемем аз= 0, т.е. x = x 0,в (1.23) имаме P n(х 0)= а 0 , следователно, А 0 = y 0 .
А 0 +a 1 (х- х 0)=г 1 ,
в който заместваме вече намерената стойност А 0 = y 0 . Разрешаване на това равенство по отношение на А 1 и използвайки нотацията с крайна разлика, получаваме
Чрез пълна индукция може да се покаже валидността на израза
Заместване на намерените коефициенти А 0 , А 1 ,..., и nв (17.1), получаваме полинома
което се нарича Първият интерполационен полином на Нютон.
Като се има предвид, че всеки член на полинома (17.2), започвайки от втория, съдържа фактора х-х 0 , естествено е да се предположи, че този полином е най-подходящ за интерполация в близост до възела х 0 . Ще извикаме възела х 0 основен за полинома (17.2) и опростете (17.2) чрез въвеждане на нова променлива ррайство или (което е същото) равенство х = х 0 +qh.защото
х - x i =х 0 + qh - x 0 - ih=h (q-i),
тогава в резултат на заместването на тези разлики в (17.2) стигаме до Първата интерполационна формула на Нютон като
където обозначението е P н(х 0 + qh) показва не само нстепен на полинома, но и към основния възел х 0 и свързване на променливи хИ р.
Първата формула на Нютон (17.3) обикновено се прилага за стойности | р| < 1, а именно за интерполация напред(при х Î ( х 0 , х 1), т.е. при рО (0, 1)) и екстраполиране назад(в х< х 0 тези. при р < 0).
Тъй като в действителност степените на интерполационните полиноми не са толкова големи, докато таблиците на стойностите на функциите са доста обширни и тъй като в реална числена таблица няма индекси - номера на възли, тогава основният възел за формула (17.3) х 0 може да приеме възела, който е най-близо до дадена фиксирана точка Х,ако зад него има достатъчен брой възли за конструиране на необходимите разлики. Тъй като първата формула на Нютон използва низходящи диагонали на таблицата с крайни разлики, такова изместване на възела, взет като основен, в края на таблицата ще бъде неприемливо.
Отчитането на това обстоятелство води до необходимостта от симетрична в известен смисъл формула за (17.3), която да е подходяща за интерполация в края на таблицата. За това, за разлика от (17.1), формата на интерполационния полином P n(х) вземете такъв, който предвижда алтернативно свързване на възли в обратен ред: първо последния, след това предпоследния и т.н., т.е.
Р(х)= а 0 +a 1 (x-x n)+ а 2 (x-x n)(x-x n - 1)+... + a n(x-x n)(x-x n - 1)…(х-х 1).
Коефициенти А 0 , А 1 ,..., и nна този полином се намират по същия начин, както бяха намерени за полинома (17.1), само че тук заместването на възлови точки вместо хи разглеждането на интерполационните равенства също се извършва в обратен ред.
Така получаваме Вторият интерполационен полином на Нютон
в който е основният възел x nи чиито коефициенти се определят от крайни разлики, разположени на възходящата y nдиагонали.
Нека поставим (17.4) x = xn +qh,в противен случай въвеждаме нова променлива и трансформираме в нея разликите, включени в (17.4):
х - x i =x n + qh - x 0 - ih= x 0 +nh + qh - x 0 - ih=h (q+n- i)
В резултат на това стигаме до Втората интерполационна формула на Нютон Тип
Също така е препоръчително да го използвате за стойности на | р| < 1, т.е. в окрестности узла x n за обратна интерполация(при рО (-1, 0)) и екстраполиране напред(при q>ОТНОСНО).
Наред с първата и втората формули за интерполация на Нютон, специално извлечени за началото и края на таблицата, има още няколко формули, предназначени за тяхното използване в централната част на таблицата и поради това т.нар. централни интерполационни формули. Преди да дефинираме тези формули, въвеждаме концепцията за централните разлики.
Ще приемем, че възелът х 0 се намира в средата на таблицата, а останалите възли са номерирани, започвайки от х 0, като се използват както положителни, така и отрицателни индекси, т.е. мислим x i=х 0 +их,Където аз= 0, ±1, ±2,... . Тогава централната част на таблицата с крайни разлики ще бъде индексирана, както е показано в таблицата. 1.7. Всички крайни разлики, подчертани в него (разположени с XQ,y Qв един ред и половин ред отгоре и отдолу) се наричат централни различия.
х - 3 г- 3D г - 3
х - 2 г- 3D г- 2 D 2 г- 3 D 3 г - 3
х - 1 г - 1 дг - 1 D 2 г - 2 D 3г - 2 D 4 г - 3 D 5г - 3
х 0 г 0 дг 0 D 2г - 1 D 3г - 1 D 4г - 2 D 5г - 2 D 6г - 3
х 1 г 1 D г 1 D 2 г 0 D 3 г 0 D 4 г - 1
х 2 г 2D г 2 D 2 г 1
х 3 г 3
Търсим интерполационния полином във формата
Р(х)= а 0 +a 1 (х-х 0)+ а 2 (х-х 0)(х-х 1)+ а 3 (х-х - 1) (х-х 0)(х-х 1)+
+a 4 (х-х - 1) (х-х 0)(х-х 1)(х-х 2)+… .
Търсим коефициенти както преди. Чрез въвеждане на нова променлива и изразяване чрез нея различия х - x i =ч (q-i) за всички аз= 0, ±1, ±2, ..., в резултат на заместването на тези разлики и изразите на коефициентите след трансформации води до формулата
Наречен Интерполационна формула на Стърлинг.
Нека разгледаме въпроса как остатъкът и неговите оценки могат да бъдат трансформирани по време на интерполация с крайни разлики.
Известно е, че всички конструирани тук интерполационни полиноми с крайни разлики на Нютон и Стърлинг са просто различни форми на представяне на интерполационния полином на Лагранж. Следователно за всички тези форми е валиден изразът за остатъчния член (16.7).
За първия интерполационен полином на Нютон във формата (17.3) грешката може да бъде записана както следва
За втория интерполационен полином на Нютон във формата (17.5) грешката може да бъде записана по следния начин
Извадка от експериментални данни е масив от данни, който характеризира процеса на промяна на измерения сигнал за дадено време (или спрямо друга променлива). За да се извърши теоретичен анализ на измерения сигнал, е необходимо да се намери апроксимираща функция, която ще свърже дискретен набор от експериментални данни с непрекъсната функция - интерполационен полиномн -градуси. Този интерполационен полином с n-степен може да бъде записан, например, в Нютонова форма (един от методите за представяне).
Интерполационен полином
във формата на Нютон- Това математическа функциякоето ни позволява да напишем полиномн -степен, която ще свърже всички дадени точки от набор от стойности, получени емпирично или чрез произволно вземане на проби с постоянна/променлива времева стъпка на измервания.
1. Интерполационна формула на Нютон за неравномерно разпределени стойности на аргумента
IN общ изглединтерполационен полиномвъв формата на Нютон се записва, както следва:
където n – реално число, което показва степента на полинома;
– променлива, която представлява разделената разликаk-ти ред, който се изчислява по следната формула:
Разделената разлика е симетрична функция на нейните аргументи, тоест независимо как са пренаредени, нейната стойност не се променя. Трябва да се отбележи, че за разделената разлика от k-ти ред е валидна следната формула:
Като пример, помислете за конструиране на полином във формата на Нютон от представената извадка от данни, която се състои от три дадени точки. Интерполационен полиномпод формата на Нютон, който минава през три дадени точки, ще бъдат записани в следната форма:
Разделената разлика от 1-ви ред се дава от следния израз
Разделената разлика от 2-ри ред се дава от следния израз
Трябва да се отбележи, че този израз може да бъде пренаписан в друга форма:
Формата на Нютон е удобна форма за представяне на интерполационен полином с n-степенна степен, тъй като при добавяне на допълнителен възел всички предварително изчислени членове остават непроменени и към израза се добавя само един нов член. трябва да бъде отбелязано чеИнтерполационният полином във формата на Нютон се различава само по форма от интерполационния полином във формата на Лагранж, представляващ същия интерполационен полином на дадена мрежа.
Трябва да се отбележи, че полиномът във формата на Нютон може да бъде представен в по-компактна форма (според схемата на Хорнер), която се получава чрез последователно излагане на факторите
2. Интерполационна формула на Нютон за еднакво разпределени стойности на аргумента
Ако стойностите на функцията са посочени за еднакво разпределени стойности на аргументи, които имат постоянна стъпка на измерване
, след това използвайте друга форма на запис на интерполационния полином съгласно формулата на Нютон.
За интерполиране на функция в края на разглеждания интервал ( обратна интерполация и екстраполация напред
къде са крайните разликик
Удобно е получените крайни разлики да се представят в табличен вид, под формата на хоризонтална таблица на крайните разлики. Тази формула от таблицата с крайни разлики използвагорен диагонал.
За интерполиране на функция в началото на разглеждания интервал ( интерполация напред и екстраполация назад) използвайте интерполационен полином във формата на Нютон в следната нотация:
къде са крайните разликик -поръчките се определят от следния израз
Удобно е получените крайни разлики да се представят в табличен вид, под формата на хоризонтална таблица на крайните разлики. Формулата от таблицата с крайни разлики използвадолен диагонал.
3. Грешка на интерполационния полином в Нютонова форма
Помислете за функцията f(x ), който е непрекъснат и диференцируем на разглеждания интервал. Интерполационен полиномП (x) във формата на Нютон приема точкистойности на набор от функции. В други точки интерполационният полином P(x) различна от стойността на функцията f(x) по количеството остатъчен срок , което определя абсолютната грешка на интерполационната формула на Нютон:
Абсолютната грешка на интерполационната формула на Нютон се определя, както следва:
Променлива представлява горната граница на стойността на модула (n+1)та производна на функцията f(x) на даден интервал
В случай на равноотдалечени възлиАбсолютната грешка на интерполационната формула на Нютон се определя, както следва:
Изразът е написан, като се вземе предвид следната формула:
Избор на интерполационни възли
Използвайки правилния избор на възли, можете да минимизирате стойността при оценка на грешката, като по този начин се повишава точността на интерполацията. Този проблем може да бъде решен с помощта на полинома на Чебишев:
Корените на този полином, тоест точките, трябва да се приемат като възли:
4. Метод за изчисляване на полином във форма на Нютон (директен метод)
Алгоритъмът за изчисляване на полином във формата на Нютон ви позволява да разделите задачите за определяне на коефициентите и изчисляване на стойностите на полинома за различни стойности на аргумента:
1. Образец отн -точки, което включва стойностите на функцията и стойностите на аргумента на функцията.
2. Изчислете разделени разлики от n-порядък, които ще бъдат използвани за конструиране на полином в Нютонова форма.
3. Изчислете полинома от n-степен в Нютонова форма, като използвате следната формула:
Алгоритъм за изчисляване на полином в Нютонова формапредставени на фигура 1.
анотация
Обяснителна бележка курсова работа"Интерполация на функция на една променлива по метода на Нютон" съдържа въведение, анализ на задачата с описание на входни и изходни данни, преглед литературни източници, описание на математическия модел и методите на изчислителната математика, обяснения на алгоритъма, програмен текст, инструкции. При изучаването на дисциплината "Информатика" са използвани различни литературни източници за написване на курсовата работа, които са изброени в този документ. Тази курсова работа предоставя програма, която се използва за таблична интерполация дадена функцияМетод на Нютон. Той използва метода на структурирано програмиране, за да улесни писането и отстраняването на грешки в програмата, както и да подобри нейната яснота и четливост. Целта на написването на тази работа беше да се получат и консолидират практически умения за разработване на алгоритми с помощта на различни методи. Представената програма е реализирана на езика за програмиране Pascal. Обяснителната записка съдържа 25 листа, които съдържат два чертежа, текста на програмата и описание на програмата и алгоритъма.
Въведение
Анализ на работата
Математически модел на задачата
Програмиране на функция формула на Нютон
Преглед на литературни източници
Разработване на програма по схемата на алгоритъма
Инструкции за използване на програмата
Програмен текст
Изходни данни и резултат от решаването на тестовия случай
Заключение
Списък на използваните източници
Въведение
Съвременно развитиефизиката и техниката е тясно свързана с използването на електронни компютри (компютри). В момента компютрите са станали обичайно оборудване в много институти и проектантски бюра. Това ни позволи да преминем от най-простите изчисления и оценки на различни структури или процеси към нов етап на работа - подробен математическо моделиране(изчислителен експеримент), което значително намалява необходимостта от пълномащабни експерименти, а в някои случаи може да ги замени.
Сложните изчислителни проблеми, които възникват при изучаването на физически и технически проблеми, могат да бъдат разделени на няколко елементарни, като например изчисляване на интеграл, решаване на диференциално уравнение и т.н. Много елементарни проблеми са прости и добре изучени. За тези проблеми вече са разработени методи за числено решаване и често има стандартни компютърни програми за решаването им. Има и доста сложни елементарни задачи; Сега интензивно се разработват методи за решаване на такива проблеми.
В тази връзка съвременен специалист с висше образованиетрябва да има не само високо нивообучение в профила на своята специалност, но също така да имат добри познания по математически методи за решаване на инженерни проблеми, да се фокусират върху използването на компютърни технологии и практически да овладеят принципите на работа на компютър.
Анализ на работата
Следните са използвани като входни данни:
1. Брой възли.
2. Стойности на таблицата на функцията.
Изходни данни, т.е. Резултатът от програмата е:
1. Стойности на определена от таблица функция в междинни стойности.
2. Полиномна графика.
Математически модел на задачата
При изпълнение на курсовата работа беше избран следният математически модел:
Интерполация и апроксимация на функции.
1. Постановка на проблема.
Един от основните проблеми на числения анализ е проблемът за интерполацията на функции. Често е необходимо да се възстанови функцията
за всички стойности на интервал, ако неговите стойности са известни на определен краен брой точки на този интервал. Тези стойности могат да бъдат намерени в резултат на наблюдения (измервания) в някакъв естествен експеримент или в резултат на изчисления. Освен това може да се окаже, че функцията е дадена с формула и изчисляването на нейните стойности с помощта на тази формула е много трудоемко, така че е желателно да имате по-проста (по-малко трудоемка за изчисляване) формула за функцията , което би позволило да се намери приблизителната стойност на въпросната функция с необходимата точност във всяка точка на сегмента. В резултат на това възниква следният математически проблем.Нека и" сегмент
решетка си стойностите на функцията са посочени в нейните възли
, равен.Изисква се конструиране на интерполант – функция
, съвпадаща с функцията във възлите на мрежата: .Основната цел на интерполацията е да се получи бърз (икономичен) алгоритъм за изчисляване на стойности
за стойности, които не се съдържат в таблицата с данни.2. Интерполация на Нютон
Дадена е таблична функция:
| аз | ||
| 0 | ||
| 1 | ||
| 2 | ||
| .. | .. | .. |
| н |
Точки с координати
се наричат възлови точки или възли.Броят на възлите в табличната функция е N=n+1.
Трябва да намерите стойността на тази функция в междинна точка, Например,
, и . За решаване на проблема се използва интерполационен полином.Интерполационният полином според формулата на Нютон има формата:
където n е степента на полинома,
Интерполационната формула на Нютон ви позволява да изразите интерполационния полином
чрез стойността в един от възлите и чрез разделените разлики на функцията, изградена над възлите.Първо, предоставяме необходимата информация за отделните разлики.
Пуснете възли
,стойностите на функцията са известни
. Да приемем, че сред точките , , няма съвпадащи. Разделените разлики от първи ред се наричат отношения , , .Ще разгледаме разделени разлики, съставени от съседни възли, т.е. изрази
Нека функцията y=f(x) е дадена на сегмента, който е разделен на n еднакви сегмента (случаят на равноотдалечени стойности на аргумент). x=h=const. За всеки възел x 0, x 1 =x 0 +h,..., x n =x 0 +n h стойностите на функцията се дефинират във формата: f(x 0)=y 0, f(x 1)= y 1,... ., f(x n)=y n.
Крайни разлики от първи ред y 0 = y 1 – y 0 y 1 = y 2 – y y n-1 = y n – y n-1. Крайни разлики от втори ред 2 y 0 = y 1 – y 0 2 y 1 = y 2 – y y n-2 = y n-1 – y n-2 Крайни разлики от по-високи редове се дефинират по подобен начин: k y 0 = k- 1 y 1 – k-1 y 0 k y 1 = k-1 y 2 – k-1 y k y i = k-1 y i+1 – k-1 y i, i = 0,1,...,n-k.
Нека на функцията y = f(x) са дадени стойностите y i = f(x i) за равни стойности на независимите променливи: x n = x 0 +nh, където h е стъпката на интерполация. Необходимо е да се намери полином P n (x) със степен не по-висока от n, като в точки (възли) x i се приемат стойностите: P n (x i) = y i, i=0,...,n. Нека запишем интерполиращия полином във формата:
Задачата за конструиране на полином се свежда до определяне на коефициентите a i от условията: P n (x 0)=y 0 P n (x 1)=y P n (x n)=y n
Други коефициенти могат да бъдат намерени по подобен начин. Общата формула е: Замествайки тези изрази във формулата на полинома, получаваме: където x i,y i – интерполационни възли; x – текуща променлива; h – разлика между два интерполационни възела h – постоянна стойност, т.е. интерполационните възли са на еднакво разстояние един от друг.
Особеността на интерполацията е, че интерполиращата функция стриктно преминава през възловите точки на таблицата, т.е. изчислените стойности съвпадат с табличните: y i =f(x i). Тази характеристика се дължи на факта, че броят на коефициентите в интерполиращата функция (m) е равен на числото таблични стойности(н)
4. Невъзможно е да се опишат таблични данни, в които има няколко точки с същата стойностаргумент. Тази ситуация е възможна, ако един и същ експеримент се проведе няколко пъти с едни и същи първоначални данни. Това обаче не е ограничение за използването на приближение, при което условието на графиката на функцията, преминаваща през всяка точка, не е зададено.
