69325

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

Лекция

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

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

Украинкский

2014-10-03

213 KB

17 чел.

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


 

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

38030. Каскадные таблицы стилей 63.5 KB
  Каскадные таблицы стилей Основным понятием CSS является стиль т. CSS действует другим более удобным и экономичным способом. Кроме того CSS позволяет работать со шрифтовым оформлением страниц на гораздо более высоком уровне чем стандартный HTML избегая излишнего утяжеления страниц графикой. Практическое освоение CSS Как вам уже известно информация о стилях может располагаться либо в отдельном файле либо непосредственно в коде Webстранички.
38032. Структура HTML-документа. Создание элементарной WEB-страницы 502 KB
  Для работы с этими текстами был создан специальный протокол HTTP Hyper Text Trnsfer Protocol были обозначены основные элементы языка разметки HTML. Язык HTML развился из стандартного обобщенного языка описания документов SGML и является его производной созданной для разметки текстовых документов. Существуют разные суждения о том считать HTML языком программирования или нет. С точки зрения программистов он имеет достаточно простой синтаксис и довольно легок в изучении но с другой стороны для простого пользователя иногда постижение...
38033. Форматирование текста 44.5 KB
  Форматирование текста Цель работы: используя теги разбивки текста логического и физического форматирования текста создать страницу по данному образцу. Теги разбивки текста h1 т h1 h2 т h2 h3 т h3 h4 т h4 h5 т h5 h6 т h6 заголовки стилей 1 2 3 4 5 6. Атрибут: lign= задает положение текста абзаца на строке. Значения: left выровнять текст по левому краю center выровнять текст по центру right выровнять текст по правому краю.
38034. Работа с цветом фона страницы и цветом шрифта. Задание бегущей строки 159.5 KB
  Работа с цветом фона страницы и цветом шрифта. Контейнер описания шрифта может быть помещен в любой другой контейнер. задает имя шрифта или несколько возможных шрифтов. Броузер берет последующий шрифт если у него нет предыдущего; size= задает размер шрифта.
38035. Нумерованные и маркированные списки 60.5 KB
  Сдвиг один Сдвиг другой Сдвиг сякой Хочу обратить ваше внимание что это прописано без параметра type но при помощи тэга ul : ul li Сдвиг один li ul ul ul li Сдвиг другой li ul ul ul ul ul li Сдвиг сякой li ul ul ul Списки могут быть и вложенными: как это выглядит: Код: тема 1 подтема 1 подтема 2 подподтема подтема 3 тема 2 UL LI тема 1 OL LI подтема 1 LI подтема 2 OL strt= 10 LI подподтема OL LI подтема 3 OL LI тема 2 UL Оформление списков может нумероваться...
38036. Вставка изображений на WEB-страницу 274.5 KB
  Если картинка лежит в поддиректории то ссылка на неё будет выглядеть так img src= путь к картинке название картинки.расширение картинки Для вашего удобства кладите картинку в ту же директорию что и документ тогда путаницы будет меньше и записывать короче img src= название картинки.расширение картинки Если картинка лежит на уровень выше а документ находится в поддиректории то ссылка на неё будет такой: img src= . название картинки.
38037. Гиперссылки 138.5 KB
  href= т ссылка. Атрибуты: href= задает URL адрес. Чтобы по ссылке в левом кадре открылся файл в правом кадре конструкция ссылки в файле загруженном в левый кадр должна быть такой: href= имя файлаимя метки trget= правый указатель ссылки где: имя файла имя файла загружаемого в правый кадр имя метки имя метки в этом файле. Принципы прописывания пути здесь такие же как в случае с картинками: 1 href= prf.
38038. Интегрирование мультимедиа на WEB-страницу 260.5 KB
  Если на странице обнаружен элемент embed или object то производится попытка использовать один из имеющихся плагинов для вывода мультимедиафайла в окне браузера. Применяется созданный компанией Netscpe и получивший широкое распространение элемент embed . Например: embed nme= Moviel src= moviel.com quicktime downlod embed ПРИМЕЧАНИЕ Internet Explorer 5.