69325

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

Лекция

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

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

Украинкский

2014-10-03

213 KB

12 чел.

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


 

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

3142. Металлургия стали 1.75 MB
  Курс лекций по дисциплине «Металлургия стали» предназначен для самостоятельного изучения и закрепления теоретических знаний студентами на начальном этапе обучения по специальностям металлургического направления. Подробно изложены все основные раздел...
3143. Практика применения Арбитражного процессуального кодекса Российской Федерации 734.28 KB
  Практика применения Арбитражного процессуального кодекса Российской Федерации В книге собраны наиболее часто встречающиеся на практике вопросы применения Арбитражного процессуального кодекса РФ. Работа написана в форме вопросов и ответов, что позвол...
3144. Задачи пожарно-технической экспертизы и методы их решения 1001.5 KB
  Введение В современных условиях борьбы с преступностью возрастает роль доказательственной информации, получаемой в процессе проведения судебных экспертиз. Особенно актуально это положение для расследования уголовных дел, сопряженных с пожарами, поск...
3145. Формирование стратегии и сценарный анализ в условиях неопределенности 293.34 KB
  Предисловие В разрабатываемом нами алгоритме последовательность формирования стратегического поведения к следующим четырем блокам (см. рис. 1). 1) «анализ» (оценка внешнего и внутреннего окружения, определение миссии, формулировка целей). 2) «планир...
3146. Педагогическая психология и ее особенности 1.15 MB
  В электронном учебнике представлены основные проблемы педагогической психологии: психологические особенности процесса обучения и образовательной деятельности человека, психологические особенности педагогов и обучающихся, психологические особенности ...
3147. Принципы уголовного законодательства: понятие, система, проблемы законодательной регламентации 800 KB
  Принципы уголовного законодательства: понятие, система, проблемы законодательной регламентации Предисловие До Уголовного кодекса РФ (далее - УК РФ) 1996 года ни один уголовно-правовой акт не содержал норм, закрепляющих принципы уголовного законодате...
3148. Реструктуризация и санация предприятия 1.38 MB
  В учебном пособии рассмотрены основные аспекты комплексной программы реструктуризации и санации, сущность и задачи санационной возможности, причины возникновения финансовой несостоятельности и банкротства предприятий. Последовательно раскрываются...
3149. Юридическая психология 1.28 MB
  Мы начинаем изучать курс «Юридическая психология». Эта отрасль психологической науки призвана внести значительный вклад в решение многопрофильных задач укрепления правовой основы российского государства и общества....
3150. Автомобили. Теория 3.6 MB
  Эксплуатационные свойства АТС Развитие науки об эксплуатационных свойствах АТС. Роль русских ученых в развитии науки о законах движения АТС. Основные эксплуатационные свойства и их определения. Условия эксплуатации АТС. Чуть-чуть...