Інтерполювання функцій (реферат)

Реферат на тему:

Інтерполювання функцій

Задача про інтерполяцію функцій є однією з основних задач чисельного аналізу. Формулюється вона таким чином.

Нехай на $$\left[a,b\right]$$ задано сітку w= { ax0<x1<.<xnb}, у вузлах якої відомо значення функції $$u\left(x\right)\mathrm{:}u\left(x_i\right)=u_i,$$ $$i=\stackrel{}{\mathrm{1,}n}$$. Потрібно побудувати інтерполянту-функцію $$v\left(x\right)$$, значення якої співпадають у вузлах сітки із заданими значеннями.

$$v\left(x\right)$$, $$i=\stackrel{}{\mathrm{0,}n}$$. (1).

Основна мета інтерполяції - одержати швидкий (економічний) алгоритм обчислення значень $$v\left(x\right)$$, де $$\mathit{x^I}\left[a,b\right]$$ .

Основне питання: як вибрати $$v\left(x\right)$$ та як оцінити похибку $$v\left(x\right)-u\left(x\right)?$$ Інтерполянти, як правило, будуються у вигляді узагальнених поліномів.

$$$$ $$v\left(x\right)=\underset{k=0}{\overset{n}{}}{}_k{v}_k\left(x\right)$$ ,.

де $$\left\{v_k\left(x\right)\right\}$$ — фіксовані лінійно незалежні функції, $${}_k$$ -невідомі параметри.

З умов (1) одержуємо систему ЛАР відносно $${}_k$$ :

$$\underset{i=1}{\overset{n}{}}$$ $$i=\stackrel{}{\mathrm{0,}n}$$ .

Як вiдомо, необхідною і достатньою умовою існування єдиного роз’язку цієї системи, або єдиної інтерполянти для будь-якого набору вузлів $$x_0,x_1,\text{.}\text{.}\text{.},x_n$$, є вимога щоб система функцій $$\left\{v_k\left(x\right)\right\}$$ була системою Чебишова на $$\left[a,b\right]$$ .

Базовими системами $$\left\{v_k\left(x\right)\right\}$$ найчастіше обирають степеневі функції $$v_k\left(x\right)=x^k$$ (в цьому випадку $$v\left(x\right)=P_n\left(x\right)$$ — поліном степеня $$n$$) або тригонометричні функції $$(v_k\left(x\right)=\left\{\text{cos}\text{kx}\text{, sin}\text{kx}\right\},\begin{array}{cc}& v\end{array}$$ $$$$ — тригонометричний поліном). Використовуються також раціональні функції $$(\underset{i=0}{\overset{s}{}}{}_i{v}_i(x))/(\underset{j=0}{\overset{t}{}}{}_j{v}_j(x))$$ .

Розглянемо алгебраїчні поліноми. Відома теорема Вейєрштрасса стверджує, що будь-яку неперервну на $$\left[a,b\right]$$ функцію $$v\left(x\right)-u\left(x\right)?$$ можна як завгодно точно наблизити поліномом степеня $$n$$. Тобто для будь-якого $$e\text{.}>0$$ $$$$ існує поліном $$P_n\left(x\right)$$ степеня $$n$$, $$n=n\left(e\right)$$ такий, що.

$$\underset{\mathit{x^I}\left[a,b\right]}{\text{max}}|u(x)-P_n(x)|<e$$ .

Якщо і вдається побудувати такий многочлен, то, як правило, його степінь така висока, що практичне застосування його стає неможливим. Крім того, ця теорема не дає відповіді на питання про існування прийнятого інтерполяційного многочлена для заданої множини точок $$\left\{x_i-u_i\right\}$$ та способи його побудови.

Якщо шукати ІП увигляді.

$$P_n=\underset{k=0}{\overset{n}{}}{}_k{x}^k,$$.

то система ЛАР.

$$\underset{k=0}{\overset{n}{}}{}_k{x}_i^k=u_i$$, $$i=\stackrel{}{\mathrm{0,}n}$$.

має своїм визначником визначник Вандермонда $$\underset{i\mathrm{^1}k}{}(x_k-x_i)\mathrm{^10}$$, і, отже, єдиний розв’язок. Звідси випливає існування та єдиність інтерполяційного полінома (2). Відомо багато форм запису інтерполяційного поліному. Розглянемо побудову так званого інтерполяційного поліному Лагранжа.

Для обчислень більш зручним в поріванянні з базисом $$\left\{x^k\right\}$$ є базис поліномів Лагранжа $$$$ $$\left\{l_k\left(x\right)\right\}$$ $$$$ $$$$ степеня $$n$$ (коефіцієнти або фундаментальні поліноми Лагранжа):

$$l_k\left(x_i\right)=\{\begin{array}{c}\mathrm{0,}\begin{array}{cc}& i\mathrm{^1}k\end{array}\\ \mathrm{1,}\begin{array}{cc}& i=k\text{.}\end{array}\end{array}$$.

Безпосередньою перевіркою можна впевнетись, що поліном степеня $$n$$.

$$l_k\left(x\right)=l_k^{\left(n\right)}\left(x\right)$$ = $$\frac{(x-x_0)(x-x_1)\text{.}\text{.}\text{.}(x-x_{k-1})(x-x_{k+1})\text{.}\text{.}\text{.}(x-x_n)}{(x_k-x_0)(x_k-x_1)\text{.}\text{.}\text{.}(x_k-x_{k-1})(x_k-x_{k+1})\text{.}\text{.}\text{.}(x_k-x_n)}$$.

задoвольняє цій умові і визначається єдиним чином. Cправді, якщо існує ще один поліном $${\stackrel{}{l}}_n(x)$$, то різниця $${\stackrel{}{l}}_k(x)$$ — $$l_k\left(x\right)=l_k^{\left(n\right)}\left(x\right)$$ (поліном степеня не вище $$n$$) обертоється в нуль в $$n$$ +1 точці, тобто $${\stackrel{}{l}}_k(x)$$ — $$l_k\left(x\right)$$ 0.

Поліном $$l_k\left(x\right)=l_k^{\left(n\right)}\left(x\right)$$ $$u_k$$ приймає значення $$u_k$$ в точцi $$x_k$$ і дорівнює нулю у всіх інших вузлах. З цього випливає, що ІП.

$$\underset{k=0}{\overset{n}{}}{l}_k(x)u_k=\underset{i\mathrm{^1}k}{}\frac{x-x_i}{x_k-x_i}=\underset{k-0}{\overset{n}{}}{u}_k\frac{{\mathrm{}}_{n+1}(x)}{{\mathrm{}}_{n+1}^{\text{'}}(x)(x-x_k)},$$, (3).

де $${\mathrm{}}_{n+1}(x)$$ = $$\underset{i=o}{\overset{n}{}}(x-x_i)$$ має степінь не вище $$n$$ +1 i $$P_n\left(x_i\right)=u_i$$ .

Многочлен (3) називають інтерполяційним многочленом Лагранжа.

Величина $$u\left(x\right)-v\left(x\right)$$ називається похибкою інтерполяції многочленом Лагранжа або залишковим членом формули Лагранжа.

При практичному використанні інтерполяційних многочленів важливим є знання похибки, яка виникає при інтерполяції.

Оцінимо величину залишкового члену формули Лагранжа. Існують різні форми запису залишкового члена. Так, якщо $$u\left(x\right){\mathit{^IC}}_{n+1}\left[a,b\right]$$ то існує $$\mathit{z^I}\left[a,b\right]$$ така, шо.

$$R\left(x\right)=u\left(x\right)-v\left(x\right)=\frac{u^{\left(n+1\right)}\left(z\right)}{\left(n+1\right)!}{\mathrm{}}_{n+1}\left(x\right)\text{.}$$.

Одержимо цю формулу.

Для цього розглянемо функцію.

$$m\left(z\right)=u\left(z\right)-L_n\left(z\right)\text{-`A}{\mathrm{}}_{n+1}(z)\text{.}$$ (4).

У вузлах інтерполяції $$m\left(z\right)=0$$. Якщо і в точці $$x$$, де ми оцінюємо похибку, $$m\left(z\right)=0$$, то величина $$\mathrm{`A}{\mathrm{}}_{n+1}(x)$$ дає оцінку. З цього випливає, що.

$$m\left(z\right)=u\left(z\right)-L_n\left(z\right)\text{-`A}{\mathrm{}}_{n+1}(z)\text{.}$$.

За теоремою Ролля $$\mathit{m}\left(z\right)$$ має не менше $$$$ $$n+1$$ нуль, а $$m^{\left(n+1\right)}\left(z\right)$$ обертається в нуль в деякій точці $$\mathit{z^I}\left[a,b\right]$$, де $$a=\text{min}\left(x_0,x_1,\text{.}\text{.}\text{.},x_n,x\right)$$, $$a=\text{min}\left(x_0,x_1,\text{.}\text{.}\text{.},x_n,x\right)$$ .

Використовуючи (4), одержимо.

$$m^{\left(n+1\right)}\left(z\right)=u^{\left(n+1\right)}\left(z\right)\text{-`A}\left(n+1\right)!$$.

і внаслідок того, що з умови $$m^{\left(n+1\right)}\left(z\right)$$ випливає $$\text{`A=}{u}^{\left(n+1\right)}\left(z\right)/\left(n+1\right)\text{!,}$$ з (4) маємо.

$$u\left(x\right)-L_n\left(x\right)=\frac{}{}$$ (5).

Використовуючи рівномірну метрику, одержимо з (5) оцінку.

$$u-L_n<=\frac{M_{n+1}}{\left(n+1\right)!}\underset{\mathit{x^I}\left[a,b\right]}{\text{max}}|{\mathrm{}}_{n+1}\left(x\right)|,$$ (6).

де $$M=\underset{\mathit{x^I}\left[a,b\right]}{\text{max}}|u^{\left(n+1\right)}\left(x\right)|\text{.}$$.

Покращити оцінку (6) можна вибравши вузли інтерполяції $$x_0,x_1,\text{.}\text{.}\text{.},x_n$$ таким чином, щоб $$\underset{\mathit{x^I}\left[a,b\right]}{\text{max}}|{\mathrm{}}_{n+1}\left(x\right)|,$$ був мінімальним. Видно, що поліном $${\mathrm{}}_{n+1}(x)$$ має старшим коефіцієнтом одиницю. Таким чином, ми приходимо до необхідності розв’язати задачу: серед усіх многочленів степеня $$n+1$$ із старшим коефіцієнтом рівним одиниці знайти той, максимальне відхилення якого від нуля на проміжку $$\left[a,b\right]$$ буде мінімальним.

Чебишевим були побудовані многочлени.

$$\stackrel{}{T_n}=2^{1-n}{T}_n\left(x\right),$$.

які називають поліномами, що найменше відхиляються від нуля на проміжку $$\left[-\mathrm{1,1}\right]$$. Тут $$T_n\left(x\right)=\text{Cos}\left(\text{narcCosx}\right),|x|<=1$$ поліноми Чебишева першого роду.

Враховуючи, що $$T_0\left(x\right)=\mathrm{1,}{T}_1\left(x\right)=1$$ і використовуючи тригонометричну тотожність.

$$\text{Cos}\left(n+1\right)q=2\text{Cos}q\text{Cosn}q-\text{Cos}\left(n-1\right)q,$$.

одержимо рекурентне співвідношення для $$T_n\left(x\right)$$ :

$$T_{n+1}(x)=2{\text{xT}}_n\left(x\right)-T_{n-1}(x),T_0(x)=\mathrm{1,}{T}_1(x)=x\text{.}$$.

З цього співвідношення видно, що $$T_n\left(x\right)$$ — це дійсно поліном із коефіцієнтом при $$x^n$$ рівним $$2^{n-1}$$ .

П.Л.Чебишов довів, що з усіх поліномів $$P_n\left(x\right)$$ $$$$ iз старшим коефіцієнтом 1 поліном $$\stackrel{}{T_n}\left(x\right)$$ має на $$\left[a,b\right]$$ найменшу верхню грань абсолютних значень, тобто найменше відхиляється від нуля. При цьому.

$$\underset{\mathit{x^I}\left[-\mathrm{1,1}\right]}{\text{max}}|\stackrel{}{T_n}\left(x\right)|=\frac{1}{2^{n-1}}\text{.}$$.

Дійсно, різниця $$\stackrel{}{T_n}\left(x\right)$$ — $$P_n\left(x\right)$$ є поліном степеня $$n$$ -1. $$\stackrel{}{T_n}\left(x\right)$$ маючи на $$\left[a,b\right]$$ $$n$$ різних коренів, набуває на цьому проміжку екстремальні значення $$n$$ +1 раз, причому по черзі ці значення будуть додатніми та від'ємними. Якщо екстремальні значення $$P_n\left(x\right)$$ менші ніж у $$\stackrel{}{T_n}\left(x\right)$$, то різниця цих поліномів в данних $$n$$ +1 точках буде по черзі додатньою та від'ємною. Отже поліном $$\stackrel{}{T_n}\left(x\right)$$ — $$P_n\left(x\right)$$ степеня $$n$$ -1 матиме $$n$$ коренів. Це можливо лише у випадку, коли $$\stackrel{}{T_n}\left(x\right)$$ — $$P_n\left(x\right)$$ 0.

Лінійною заміною змінної.

$$x=\frac{1}{2}\left[\left(b-a\right)z+\left(b+a\right)\right]-z=\frac{1}{b-a}\left[2x-b-a\right]$$.

довільний відрізок $$\left[a,b\right]$$ можна звести до $$\left[a,b\right]$$ .

Повертаючись до оцінки (6), бачимо, що.

$${\mathrm{}}_{n+1}\left(x\right)\mathrm{^3}{\left(b-a\right)}^{n+1}{2}^{-\left(2n+1\right)},$$.

де права частина співвідношення — це максимальне значення зміщеного на $$\left[a,b\right]$$ полінома $$\stackrel{}{T_n}\left(x\right)$$ :

$${\stackrel{}{T}}_{n+1}^{\left[a,b\right]}\left(x\right)=\frac{{\left(b-a\right)}^{n+1}}{2^{2n+1}}{T}_n\left(\frac{2x-\left(b+a\right)}{b-a}\right)\text{.}$$.

Отже, якщо вузлами інтерполяції взяти вузли.

$$$$ $$x_k=\frac{b+a}{2}+\frac{b-a}{2}\text{Cos}\frac{p\left(k+1/2\right)}{n+1},k=\stackrel{}{\mathrm{0,}n},$$.

то.

$${\mathrm{}}_{n+1}(x)={\stackrel{}{T}}_{n+1}^{\left[a,b\right]}\left(x\right)$$ $${\mathrm{}}_{n+1}={\left(b-a\right)}^{n+1}{2}^{-\left(2n+1\right)}\text{.}$$.

При одержанні оцінки (6) максимум добутку замінено на добуток максимумів множників. Тому може виникнути ідея одержати кращу оцінку похибки. Але ці намагання будуть даремними, в чому можна впевнитись, розглянувши функцію $$u\left(x\right)={}_{n+1}{x}^{n+1}+\text{.}\text{.}\text{.}+\mathit{}+{}_0$$ .

Маємо $$u^{\left(n+1\right)}\left(z\right)={}_{n+1}\left(n+1\right)!=\text{const}$$, тому нерівність (6) обертaється в рівність. Враховуючи що.

$$\underset{\left[a,b\right]}{\text{max}}|{\mathrm{}}_{n+1}\left(x\right)|\mathrm{^3}\underset{\left[a,b\right]}{\text{max}}|{\stackrel{}{T}}_{n+1}^{\left[a,b\right]}\left(x\right)|=\frac{{\left(b-a\right)}^{n+1}}{2^{2n+1}}$$.

при будь яких вузлах інтерполяції, маємо.

$$u-L_n\mathrm{^3}\frac{u^{\left(n+1\right)}{\left(b-a\right)}^{n+1}}{\left(n+1\right)!2^{2n+1}}=|{}_{n+1}|\frac{{\left(b-a\right)}^{n+1}}{2^{2n+1}}$$ .

ЗАВДАННЯ ДЛЯ САМОСТІЙНОЇ РОБОТИ.

1. 1. Записати формулу Лагранжа для рівновіддалених вузлів інтерполяції.

2. 2. Довести інваріантність коефіцієнтів Лагранжа відносно лінійної підстановки x=at+b.

3. 3. Порівняти наближення на $$\left[a,b\right]$$ функції f (x) інтерполяційним многочленом, побудованим по оптимальних вузлах інтерполяції та відрізком ряду Тейлора.

4. 4. Записати формулу коренів полінома Tn+1(x).

5. 5. Записати формулу для визначення координат точок, де Tn (x) досягає максимума.