Помислете за концепцията крайни разлики.
Нека функцията y=f(x)на отсечката [x 0, x„], която е разделена на Пидентични сегменти (случаят на равноотдалечени стойности на аргумента): ax=h= const. За всеки възел х 0,Х, \u003d x 0 + /G, ...,Х" =x()+ стр зстойностите на функциите са дефинирани във формата
Представяме концепцията крайни разлики.
Крайни разликипърва поръчка
Крайни разлики от втори ред 
Крайните разлики от по-високи порядки се дефинират по подобен начин: 
Удобно е да се подредят крайните разлики на функциите в таблици, които могат да бъдат диагонални (Таблица 5.1) или хоризонтални (Таблица 5.2).
Диагонална маса
Таблица 5.1
хоризонтална маса
Таблица 5.2
|
на 5 години, |
||||||
|
A 5 Wo |
||||||
|
и 4 в. |
||||||
Първата интерполационна формула на Нютон
Нека на функцията y \u003d / (x) са дадени стойностите y, \u003d / (x,) за равни стойности на независими променливи:
където з- стъпка на интерполация.
Трябва да се намери полином Pn(x)градуса ns по-горе P,приемане в точки (възли) x, стойности:
Интерполиращият полином се търси във формата:
Проблемът с конструирането на полином се свежда до определяне на коефициентите а,от условия:
Приемаме в (5.13) x \u003d x 0, тъй като вторият, третият и други членове са равни на 0, тогава 
Да намерим коефициента а ( .
Натиснете = X1 получаваме:
За определяне а 2Нека съставим крайната разлика от втори ред. В х=х 2получаваме:
Други коефициенти могат да бъдат намерени по подобен начин. Обща формулаизглежда като:
Замествайки тези изрази във формула (5.13), получаваме:
където x„ y x- интерполационни възли; х- текуща променлива; з- разлика между два интерполационни възела; з- стойността е постоянна, т.е. интерполационните възли са на еднакво разстояние един от друг.
Този полином се нарича Интерполационен полином на Нютонда се интерполира в началото на таблицата (интерполация напред), или Първият полином на Нютон.
За практическа употреба този полином се записва в трансформирана форма чрез въвеждане на нотацията t \u003d (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 K се получава същата като изчислената по формулата на Лагранж.
Втората интерполационна формула на Нютон
За да се намерят стойностите на функциите в точки, разположени в края на интервала на интерполация, се използва вторият интерполационен полином на Нютон. Записваме интерполационния полином във формата
Коефициенти a 0 , a b..., а"определя се от условието:
Влагаме (5.18) x=xn,тогава
Ние вярваме х\u003d x „_ |, следователно, 
Ако x = x n - 2 iтогава
По същия начин могат да се намерят и други коефициенти на полинома (5.18):
Замествайки тези изрази във формула (5.18), получаваме Втората интерполационна формула на Нютон,или полином на Нютон за "обратна" интерполация:
Нека въведем обозначението: 
Правейки промяна в (5.19), получаваме:
Това е втората формула на Нютон за обратна интерполация.
Пример 5.5. Изчислете топлинния капацитет (вижте таблица 5.3) за температура T = 550 K.
Използваме втората формула на Нютон (5.19) и съответните крайни разлики (виж Таблица 5.4):
Следователно стойността на топлинния капацитет при температура 550 K е
ИНТЕРПОЛАЦИЯ
Нека функцията y = f(х) се дефинира върху мрежата от еднакво разположени възли x i=х 0 +ih,където и = 0,1, ..., P,и за него е изградена таблицата на крайните разлики § 16.3.
В съответствие с казаното за посоката на модификация на интерполационната формула на Лагранж в началото на предишния раздел, ще построим интерполационен полином R стр(х) във формата на
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 \u003d 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) чрез въвеждане на нова променлива qобласт или (което е същото) равенство х = х 0 +qh.Като
х - x i =х 0 + qh-x 0 - h = h (q-i),
тогава в резултат на заместването на тези разлики в (17.2) стигаме до Първата интерполационна формула на Нютон като
където обозначението P н(х 0 + qh) показва не само н-та степен на полинома, но и към основния възел х 0 и връзката на променливите хи q.
Първата формула на Нютон (17.3) обикновено се прилага за стойностите | q| < 1, а именно за интерполиране напред(при х Î ( х 0 , х 1), т.е. в qО (0, 1)) и екстраполиране обратно(при х< х 0 тези. в q < 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и чиито коефициенти се определят от крайни разлики, разположени на възходящата от при nдиагонали.
Влагаме (17.4) x = x n +qh,в противен случай въвеждаме нова променлива и трансформираме разликите, включени в (17.4), към нея:
х - x i =x n + qh-x 0 -ih=x 0 + nh + qh-x 0 - h = h (q+n-i)
В резултат на това стигаме до Втората интерполационна формула на Нютон мил
Също така е препоръчително да го използвате за стойностите | q| < 1, т.е. в окрестности узла x n за интерполиране назад(при qО (-1, 0)) и екстраполиране напред(при q >О).
Наред с първата и втората формули за интерполация на Нютон, извлечени специално за началото и края на таблицата, има още няколко формули, предназначени за тяхното използване в централната част на таблицата и следователно наречени централни интерполационни формули. Преди да дефинираме тези формули, ние въвеждаме концепцията за централни разлики.
Ще приемем, че възелът х 0 разположени в средата на таблицата, а останалите възли са номерирани, започвайки от х 0 , като се използват както положителни, така и отрицателни индекси, т.е. вярвам x i=х 0 +ih,където и= 0, ±1, ±2,... . Тогава централната част на таблицата с крайни разлики ще бъде индексирана, както е показано в таблицата. 1.7. Всички крайни разлики, подчертани в него (които са XQ,yQна един ред и половин ред отгоре и отдолу) се наричат централни различия.
х - 3 г- 3D г - 3
х - 2 г- 3D г- 2 D 2 г- 3 D 3 г - 3
х - 1 г - 1 дг - 1 D2 г - 2 D3г - 2 D4 г - 3 D5г - 3
х 0 г 0 дг 0 D 2г - 1 D 3г - 1 D 4г - 2 D 5г - 2 D 6г - 3
х 1 г 1D г 1 D 2 г 0D3 г 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. Формула за интерполация на Нютон за неравномерно разположени стойности на аргумента
AT общ изглединтерполационен полиномвъв формата на Нютон се записва в следната форма:
където n – реално число, което показва степента на полинома;
е променлива, която представлява разделената разликаk-ти ред, който се изчислява по следната формула:
Разделената разлика е симетрична функция на нейните аргументи, тоест всяка пермутация от тях не променя нейната стойност. Трябва да се отбележи, че следната формула е валидна за разделената разлика от k-тия ред:
Като пример, разгледайте конструирането на полином във формата на Нютон, като се даде извадка от данни, която се състои от три дадени точки. Интерполационен полиномпод формата на Нютон, който минава през три дадени точки, ще бъде записано в следната форма:
Разделената разлика от 1-ви порядък се дава от следния израз
Разделената разлика от 2-ри ред се дава от следния израз
Трябва да се отбележи, че този израз може да бъде пренаписан в друга форма:
Формата на Нютон е удобна форма за представяне на n-степенен интерполационен полином, тъй като когато се добави допълнителен възел, всички предварително изчислени членове остават непроменени и само един нов член се добавя към израза. трябва да бъде отбелязано чеинтерполационният полином във формата на Нютон се различава само по форма от интерполационния полином във формата на Лагранж, представляващ същия интерполационен полином в дадена мрежа.
Трябва да се отбележи, че полиномът във формата на Нютон може да бъде представен в по-компактна форма (според схемата на Хорнер), която се получава чрез последователно поставяне в скоби на факторите
2. Формула за интерполация на Нютон за равноотдалечени стойности на аргумента
Ако стойностите на функцията са дадени за еднакво разположени стойности на аргументи, които имат постоянна стъпка на измерване
, тогава се използва друга форма на интерполационния полином съгласно формулата на Нютон.
За да интерполирате функцията в края на разглеждания интервал ( обратна интерполация и екстраполация напред
къде са крайните разликик
Удобно е получените крайни разлики да се представят в табличен вид, под формата на хоризонтална таблица на крайните разлики. Използва се тази формула от таблицата с крайни разликигорен диагонал.
За да интерполирате функцията в началото на разглеждания интервал ( предна интерполация и обратна екстраполация) използвайте интерполационен полином във форма на Нютон в следната нотация:
къде са крайните разликик -порядките се определят от следния израз
Удобно е получените крайни разлики да се представят в табличен вид, под формата на хоризонтална таблица на крайните разлики. Използва се формулата от таблицата с крайни разликидолния диагонал.
3. Интерполационна полиномна грешка в Нютонова форма
Помислете за функцията f(x ), която е непрекъсната и диференцируема на разглеждания сегмент . Интерполационен полиномП (x) във формата на Нютон приема точкизададени стойности на функциите. В други точки, интерполационният полином P(x) различна от стойността на функцията f(x) по сумата остатъчен член , което определя абсолютната грешка на интерполационната формула на Нютон:
Абсолютната грешка на интерполационната формула на Нютон се определя, както следва:
Променлива представлява горната граница на стойността на модула (n+1)та производна на функцията f(x) на даден интервал
В случай на еднакво разположени възлиабсолютната грешка на интерполационната формула на Нютон се определя, както следва:
Изразът се записва, като се вземе предвид следната формула:
Избор на интерполационни възли
С помощта на правилен избор на възли може да се минимизира стойността при оценка на грешката, като по този начин се подобрява точността на интерполацията. Този проблем може да бъде решен с помощта на полинома на Чебишев:
Като възли трябва да вземете корените на този полином, тоест точките:
4. Метод за изчисляване на полином под формата на Нютон (директен метод)
Алгоритъмът за изчисляване на полином във формата на Нютон ни позволява да разделим задачите за определяне на коефициентите и изчисляване на стойностите на полинома за различни стойности на аргумента:
1. Извадка отн -points, което включва стойностите на функцията и стойностите на аргумента на функцията.
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(xn)=yn.
Крайни разлики от първи ред 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) е равен на броя на стойностите на таблицата (n)
4. Интерполираща функция не може да опише таблични данни, в които има няколко точки с същата стойностаргумент. Тази ситуация е възможна, ако един и същ експеримент се проведе няколко пъти с едни и същи изходни данни. Това обаче не е ограничение за използването на апроксимация, където не е зададено условието графиката на функцията да преминава през всяка точка.
