69325

Інтерполяція алгебраїчними поліномами. Інтерполяційні поліноми Лагранжа та Ньютона

Лекция

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

Таку заміну називають наближенням функції fx. Тоді при вирішенні задачі замість функції fx оперують з функцією φx а задача побудови функції φx називається задачею наближення. Такий спосіб наближення базується на теоремі Вейерштраса про наближення неперервної функції...

Украинкский

2014-10-03

213 KB

8 чел.

Лекція 10.

Інтерполяція алгебраїчними поліномами. Інтерполяційні поліноми Лагранжа та Ньютона.

Постановка задачі про наближення функцій

В обчислювальній практиці часто доводиться заміняти одну функцію і f(x) (відому, невідому або частково відому) деякою функцією φ(x), близькою до f(x), яка має визначені властивості, які дозволяють робити над нею ті чи інші аналітичні або обчислювальні операції. Таку заміну називають наближенням функції f(x). У тому випадку, якщо f(x) задана таблицею значень для деякої кінцевої множини аргументів x: f(x0),f(x1),…,f(xn), і в процесі вирішення задачі необхідно використовувати значення f(x) для проміжних значень аргументу, функцію  будують таким чином, щоб у заданих точках x0,x1,…,xn вона приймала значення, що збігаються зі значеннямиf(x0),f(x1),…,f(xn), а в інших точках відрізка [a,b], що належить області визначення f(x) , приблизно представляла функцію f(x)з тим чи іншим ступенем точності. Тоді при вирішенні задачі замість функції f(x) оперують з функцією φ(x), а задача побудови функції φ(x) називається задачею наближення.

Найчастіше функцію φ(x), яка використовується при наближенні, шукають у вигляді алгебраїчного багаточлена. Такий спосіб наближення базується на теоремі Вейерштраса про наближення неперервної функції f(x) на відрізку поліномами (функція f(x) може бути досить добре наближена за допомогою полінома деякого порядку ).

При цьому будемо називати функції виду

(5.1)

де c0,c1,…,xm — деякі постійні коефіцієнти, узагальненими поліномами (узагальненими багаточленами) порядку m. На практиці в якості базисних функцій {φi(x)} беруть послідовність ступенів x:1,x1,x2,…,xm, тобто φ0(x) = 1, φ1(x) = x, φm(x) = xm, тоді

 (5.2)

є звичайний поліном ступеня m.

Для знаходження коефіцієнтів сi , i = 0,1,…,n вираз (5.1), використовуємо вимогу до наближуючої функції, тобто рівності φi(x) = fi(x), i = 0,1,…,m, і сформуємо систему з (n + 1) лінійних алгебраїчних рівнянь:

0(x0)c0 + 1(x0)c1 + ... + n(x0)cn = f(x0),
0(x1)c0 + 1(x1)c1 + ... + n(x1)cn = f(x1),
...........................................................  (5.3)

0(xm)c0 + 1(xm)c1 + ... + n(xm)cn = f(xm)

При n = m система рівнянь (5.3) має однин розв’язок у випадку, коли вектори лінійно незалежні. Виникаюча при цьому задача наближення називається задачею інтерполяції. Якщо mn, то система рівнянь може бути вирішена методом найменших квадратів для мінімізації нев’язку. Це питання докладно буде розглядатися в підрозділі 5.10 цієї глави.

В часткову випадку вибору в якості базисних функцій {φi(x)} поліномів (5.2) для n = m коефіцієнти ci можна одержати з наступної системи рівнянь:

(5.4)

Визначник цієї системи, який називають визначником Вандермонда,

(5.5)

не перетворюється в нуль, якщо серед сукупності вузлів немає співпадаючих [2], отже, матриця системи (5.4) є невиродженою, і система має єдиний розв’язок.

Іноді в якості {φi(x)} може вибиратися також послідовність показникових функцій:

 

де i} деяка числова послідовність попарно різних дійсних чисел. Тоді

. (5.6)

Вихідну функцію f(x) і поліном φ(x)вважають близькими, якщо вони збігаються на заданій системі точок x0,x1,…,xn. Ці точки називають вузлами інтерполяції.

Якщо φ(x) і f(x) — диференційовані функції, то іноді вимагають і збігу похідних f(x) і φ(x) у вузлах до деяких порядків.

Інтерполяційний багаточлен Лагранжа

Виходячи з одиничності інтерполяційного багаточлена φ(x), можна побудувати поліном, коефіцієнти якого визначаються із системи (5.5). Позначимо задані значення f(xi) = yi. Тоді φ(x) можна записати у вигляді:

(5.7)

де Φj(x)  многочлен ступеня n, що задовольняє умовам:

Такий варіант запису багаточлена φ(x) називають інтерполяційним поліномом Лагранжа. Для пошукуΦj(x) знаходять многочлен ступеня n, що обертаєтьсяв нуль у вузлах інтерполяції xi = (i = 0,1,…,j - 1,j + 1,n) і дорівнює 1 у точці xj. Многочлен, що задовольняє цим вимогам, може бути записаний у вигляді:

.

Тоді, якщо в виразі (5.7)  визначені зазначеним вище чином, то інтерполяційний многочлен (5.7) називається інтерполяційним багаточленом Лагранжа. Позначимо його як Ln(x) для того, щоб відрізняти цю формулу від інших випадків інтерполяції, остаточно:

. (5.8)

Введення і побудова інтерполяційного многочлена Лагранжа для кожної конкретної задачі зв'язані зі значною обчислювальною роботою. Скористаємося для побудови і реалізації цієї формули засобами пакета Mathematica, визначимо функцію, що представляє відповідний інтерполяційний многочлен.

Приклад 5.1.

Визначити в Mathematica оператор, що відповідає інтерполяційній формуліЛагранжа і з його допомогою побудувати поліномЛагранжа для функції, що задана в вузлах своїми значеннями з таблиці TA:

In = TA-{{0,0},{0.5,2},{1,2.25},{1.5,3},{2,3.25},{2.5,2},
{3,6},{3.5,0.75},{4,3.75}};

Відносно залежності (5.8) опишемо функцію:

В останньому виразі операторі ta — таблиця значень функції, n —число використаних табличних значень, x — змінна полінома. Звернувшись до описаної функції lgr, отримаємо інтерполяційний поліном Лагранжа по вихідній таблиці.

Рис. 5.1. Інтерполювання функції за допомогою багаточлена Лагранжа

Отримаємо з тієї ж таблиці TA інтерполяційний поліном за допомогою наступного оператора Mathematica:

In = yp[z_]: = InterpolatingPolynomial[TA,z]

і порівняємо його з y1[z], що був отриманий вище:

In = Expand[yp[z]];
Out[78] = 14.875z-32.9583z
2 + 25.5z3-6.16667z4

Поліноми збіглися, що свідчить про правильність визначення функції.

Задача інтерполяції значно спрощується, якщо значення xi є рівновіддаленими, тобто xi = x0 + ih, (i = 0,1,…,n), тоді можна ввести позначення

 

і інтерполяційний поліном буде мати вигляд:

(5.9)

Коефіцієнти (5.9)  не залежать ні від функції f(x), ні від відстані між вузлами інтерполяції h. Їх називають коефіцієнтами Лагранжа. Розглянемо, як вони можуть бути отримані і використані при розрахунках за допомогою Mathematica.

Приклад 5.2.

Скористаємося вихідною таблицею TA з прикладу 5.1, оскільки вузли в ній розташовані регулярно. Опишемо в Mathematica функцію на підставі залежностей (5.9):

Звернення до функції і виведення результату здійснимо за допомогою команди:

t

Отримаємо:

Out[56] = 5/12(-4 + t)(-3 + t)(-2 + t)t + 0.520833(-4 + t)(-3 + t)(-1 + t)t +
5/4(-4 + t)(-2 + t)(-1 + t)t + 0.677083(-3 + t)(-2 + t)(-1 + t)t

Замінимо в отриманому виразі параметр t на значення (x - x0)/h = t будемо мати:

Out[58] = 0.833333x(-4 + 2.x)(-3 + 2.x)(-2 + 2.x) +
1.04167x(-4 + 2.x)(-3 + 2.x)(-1 + 2.x) +
2.5x(-4 + 2.x)(-2 + 2.x)(-1 + 2.x)
1.35417x(-3 + 2.x)(-2 + 2.x)(-1 + 2.x)

Побудуємо для цій функції графік, визначивши на ньому ще і початкові точки

In = Plot[ggg[x], {x, 0.2},
Frame→True, GridLines→Automatic];

Рис. 5.2 Інтерполяція поліном Лагранжа для випадку рівновіддалених вузлів

Інтерполяційні формули Ньютона

Для одержання формули Ньютона попередньо необхідно ввести поняття кінцевих і розділених різниць. Нехай є система значень заданої функції у вузлах інтерполяції f(x0),f(x1),…,f(xn). Скінченимирізницями I–го порядку називають вирази:

(5.14)

II–го порядку:

(5.15)

У загальному вигляді:

(5.16)

Розділені різниці першого порядку для f(x0), у вузлах інтерполяції мають вигляд:

(5.17)

Розділені різниці II–го порядку записують у вигляді:

(5.18)

Взагалі, якщо розділені різниці k–го порядку вже визначені, то розділені різниці (k + 1)го порядку знаходяться за допомогою формули:

(5.19)

Використовуючи розділені різниці, можна одержати формулу Ньютона для нерівних проміжків у вигляді [1]:

(5.20)

Переконаємося, що отриманий вираз дійсно є інтерполяційним поліномом, а саме:

1. поліном n–оїстепені;

2. у вузлах інтерполяції приймає задані значення:

 

Вибравши довільну точку xk, 0 ≤ kn, можна довести, що:

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

Як приклад розглянемо реалізацію методу Ньютона.

Приклад 5.4.

Визначимо функцію, що обчислює по заданій таблиці ТА (для якої раніше ми вже будували поліном Лагранжа) розділену різницю n–го порядку:

Визначимо інтерполяційний поліном Ньютона наступною формулою:

Отримаємо інтерполяційний поліном по таблиці ТА:

Q = New[TA,Lenghth[TA],x]

Після приведення подібних і побудови графіка отримуємо шуканий результат:

Expand[q]; Plot[q, {x,0,2},
Frame→True, GridLines→Automatic];
Out[76] = 14.875x-32.9583x
2 + 25.2x3-6.16667x4

Рис. 5.6. Інтерполяція функції за допомогою полінома Ньютона

Порівнюючи рис. 5.1 і 5.6, то можна переконатися, що обидва методи будують той самий інтерполяційний поліном . В тойже час формула (5.20) більш зручна, порівняно з формулою Лагранжа, тому що для обчислень можуть використовуватися не всі задані точки таблиці, а тільки їх частина. При цьому природно, що вузли, якілежать ближче до інтерполяційного значення x, впливають на інтерполяційний поліном більше, а ті, що лежать далі, менше. Формула Ньютона у вигляді (5.20) використовується для інтерполяції функції на даному відрізку [a,b], якщо шукані точки знаходяться на початку таблиці.

У тому випадку, якщо шукані точки розташовані ближче до кінця таблиці, використовується формула Ньютона для інтерполяції назад:

(5.21)

Так само, як і (5.20), ця формула є поліномом n–ої ступеня й у вузлах інтерполяції приймає задані значення.

Приведені формули (5.20)–(5.21) використовуються для довільно розташованих вузлів. Однак дуже часто ці вузли будуються регулярно. Розглянемо окремий випадок формули Ньютона для інтерполяції на початку таблиці, якщо вузли рівновіддалені. Нехай відстань між сусідніми вузлами xi - xi - 1 = h, i = 1,2,…,n. Запишемо розділені різниці в формулі (5.20) через скінчені різниці:

Розділену різницю k–го порядку замінимо співвідношенням:

Введемо заміну (x - x0)/h = t.

Тоді формула Ньютона для інтерполяції на початку таблиці з рівновіддаленими вузлами буде мати вигляд:

(5.22)

Формула Ньютона для інтерполяції наприкінці таблиці з рівновіддаленими вузлами, якщо прийняти, що t = (x - xт)/h, буде мати вигляд;

(5.23)

Якщо при обчисленні кінцевих різниць записувати їх у таблиці, то для формули (5.22) буде використовуватися верхній рядок різниць, а для формули (5.23) — нижній косий рядок різниць. Необхідно пам'ятати, що кожна з отриманих формул Ньютона є іншою формою запису багаточлена Лагранжа, і розрізняються ці формули тільки позначенням (за умови, що в них використані ті ж самі вузли інтерполяції). Вибір конкретної формули обумовлений тим, що звичайно буває зручніше вести обчислення, якщо при інтерполяції спочатку використовуються найближчі до  вузли, а потім підключаються більш віддалені. При цьому перші члени інтерполяційних формул дадуть основний внесок у шукану величину, а інші будуть давати лише невеликі виправлення. У цьому випадку легше встановити, на якій різниці варто закінчити обчислення.


 

А также другие работы, которые могут Вас заинтересовать

79661. К ВОПРОСУ О ПОРЯДКЕ И ОСОБЕННОСТЯХ РЕАЛИЗАЦИИ ЖИЛИЩНОЙ ПОЛИТИКИ В РОССИИ 149 KB
  Современное жилье как элемент материальной культуры прошло длинный исторический путь: от естественных укрытий и пещер — первых пристанищ наших предков — до современных домов-небоскребов, оборудованных сложной инженерной техникой. На разных этапах развития общества по-разному решались вопросы обеспечения граждан жильем.
79662. Moscow 21.44 KB
  Moscow is the capital of Russia, its administrative, economic, political and educational centre. It is one of Russias major cities with the population of about 9 million people. Its total area is about 900 thousand square kilometres
79663. London 22.39 KB
  London with its suburbs hs popultion of bout 11 million people. London hs been cpitl for nerly thousnd yers. The most fmous of them re the Tower of London where the crown jewels re kept Westminster bbey nd St.
79664. Krasnodar 16.57 KB
  I ws born in Krsnodr. The history of Krsnodr begn in 1793. The popultion of Krsnodr is more thn 800 000 people.
79665. The United States of America 20.59 KB
  The United Sttes is lnd of rivers nd lkes. The United Sttes re riebii nturl nd minerl resources.
79666. Education in the Russian Federation 21.38 KB
  Every boy or girl must get secondry eduction. Eduction in Russi is compulsory up to the 9th form inclusive. If pupil of secondry school wishes to go on in higher eduction he or she must sty t school for two more yers.
79667. Russia 20.03 KB
  The vst territory of Russi lies in the estern prt of Europe nd the northern prt of si. Russi is wshed by twelve ses nd three ocens. Russi borders on mny countries such s Mongoli nd Chin in the southest Finlnd nd Norwy in the northwest nd so on.
79669. New York 16.14 KB
  New York is divided into 5 prts: The Bronx Brooklyn Mnhttn Queens nd Stten Islnd. In New York mny districts nd lnd mrks is wellknown s well s bridges skyscrpers nd prks. The most fmous plces in New York is Times Squre ldquo;The crossrods of the Worldrdquo; Brodwy theter nd others.