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) — нижній косий рядок різниць. Необхідно пам'ятати, що кожна з отриманих формул Ньютона є іншою формою запису багаточлена Лагранжа, і розрізняються ці формули тільки позначенням (за умови, що в них використані ті ж самі вузли інтерполяції). Вибір конкретної формули обумовлений тим, що звичайно буває зручніше вести обчислення, якщо при інтерполяції спочатку використовуються найближчі до  вузли, а потім підключаються більш віддалені. При цьому перші члени інтерполяційних формул дадуть основний внесок у шукану величину, а інші будуть давати лише невеликі виправлення. У цьому випадку легше встановити, на якій різниці варто закінчити обчислення.


 

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

57380. Складання таблиць додавання та віднімання числа 3. Задачі на збільшення та зменшення числа на кілька одиниц 31.5 KB
  Мета: розкрити принцип укладання таблиць додавання й віднімання числа 3; вдосконалювати навички усної лічби; розвивати вміння розв’язувати задачі на збільшення та зменшення числа на кілька одиниць...
57381. Вправи та задачі на засвоєння таблиць додавання й віднімання числа 3. Розв’язання задач на знаходження суми. Вимірювання довжини відрізка 29.5 KB
  Мета: вправляти учнів у розв’язанні прикладів й задач використовуючи таблиці додавання й віднімання числа 3; вдосконалювати навички усної лічби; продовжити роботу над формуванням в учнів уміння креслити вимірювати відрізки; розвивати логічне мислення.
57382. Складання задачі, яка містить поняття стільки ж. Задачі на знаходження остачі. Вправи на задачі на засвоєння таблиць додавання й віднімання числа 3 31.5 KB
  Мета: закріплювати знання учнями таблиць додавання й віднімання 3; формувати вміння розв’язувати задачі на знаходження остачі й задачі що містять у собі поняття стільки ж; вдосконалювати навички усної лічби...
57384. Задачі на знаходження суми й остачі. Вправи на засвоєння таблиць додавання й віднімання. Вимірювання довжини сторін многокутника. Побудова чотирикутника за зразком 28 KB
  Обладнання: предметні малюнки таблиці для усної лічби геометричні фігури. Робота з індивідуальними картками Повторення знань про геометричні фігури: вчитель показує фігуру учні її називають.
57386. Вправи на засвоєння таблиць додавання й віднімання числа 5. Розв’язання задач і прикладів 29 KB
  І в нашій казці гостям мухи спочатку потрібно пройти через випробування а вже потім потрапити на бал. А цей гість Мухи-Цокотухи Незнайко не може віднайти будиночок де живе хазяйка. А найвищий будинок це житло Мухи-Цокотухи. До Мухи поспішає Колобок.