69325

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

Лекция

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

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

Украинкский

2014-10-03

213 KB

9 чел.

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


 

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

5331. Історії української культури, Курс лекцій 359 KB
  Людина культури перевищує політичне та економічне буття тим, що бачить перед собою ідеал загального блага і втілює його. Культура спирається на моральний кодекс. Мораль виникла раніше законів, права. Це сталося ще у первісну добу. Моральні кодекси як цілісна система взаємин у суспільстві склалася у добу ранніх цивілізацій.
5332. Системы и модели отражения затрат на счетах 146.5 KB
  Важнейшими задачами современной практики управления являются выработка и исполнение решений, направленных на достижение финансово-экономической устойчивости и эффективности функционирования организации. Чтобы правильно реагировать на динами...
5333. Вопрос как инструмент сбора социологической информации 108 KB
  Искусство задавать вопросы, пожалуй, самое древнее и до сих пор еще самое сложное. В повседневной жизни мы убеждаемся, как бестактно поставленный вопрос ставит отвечающего в неловкое положение. Про глупые вопросы говорят, что их легче задав...
5334. Анализ финансового состояния предприятия ОАО Чайковское ППЖТ 204 KB
  Введение Анализ (от греч. - analisis) буквально означает расчленение, разложение изучаемого объекта на части, элементы, на внутренне присущие этому объекту составляющие (мысленные или реальные). Анализ выступает в диалектическом, противоречивом...
5335. Моральный вред и выплаты по его возмещению 277.5 KB
  Одним из способов защиты гражданских прав выступает возмещение морального вреда. Именно этот способ защиты гражданских прав является предметом изучения дипломной работы. Данный способ защиты состоит в возложении на нарушителя обязанности по...
5336. Вынесение приговора. И введение его в действие 290.5 KB
  Вынесение приговора Введение Каждому судье без сомнения известны слова, которыми начинается постановление Пленума Верховного Суда Российской Федерации О судебном приговоре от 29 апреля 1996 г. Судебный приговор — важнейший акт правосудия. С п...
5337. Основные права и свободы граждан 161.5 KB
  Основные права и свободы граждан Введение В Конституции сказано: Человек, его права и свободы являются высшей ценностью (Г. 2 КРФ). К сожалению, не все, что написано, имеет место быть в реальности, но, тем не менее, целью этой работы является кратко...
5338. Квалификация и наказание за убийство 460 KB
  Квалификация и наказание за убийство Введение В настоящее время наше общество переживает глубокие организационные преобразования, охватившие все сферы общественной и государственной жизни. Проблема человека постепенно возвращает объективно принадлеж...
5339. Повышение эффективности работы подвижного состава и качества транспортного обслуживание в логистической системе 434 KB
  Цель курсового проекта – повышение эффективности работы подвижного состава и качества транспортного обслуживания в логистической системе. Поставленная цель предполагает решение следующих задач: проектирование доставки грузов в лог...