Різницеві інтерполяційні формули (реферат)

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

Різницеві інтерполяційні формули Як побачимо далі, ІП можна розглядати як узагальнення відрізку ряду Тейлора.

Узагальненням поняття похідної є поняття розділеної різниці (PP). Нехай у вузлах $$x_k\mathrm{^I}\left[a,b\right],k=\stackrel{}{\mathrm{0,}n},$$ відомі значення функції $$u\left(x\right)$$. Припустимо також, що $$x_i\mathrm{^1}{x}_k$$ $$$$ при $$i\mathrm{^1}k$$. Тоді РР нульового порядку $$u\left(x\right)$$ співпадають зі значеннями функції $$u\left(x_i\right)$$, РР 1- го порядку визначаються рівністю.

$$u\left(x_i-x_j\right)=\left(u\left(x_j\right)-u\left(x_i\right)\right)/\left(x_j-x_i\right)-$$.

РР 2- го порядку:

$$u\left(x_i-x_j\right)=\left(u\left(x_j\right)-u\left(x_i\right)\right)/\left(x_j-x_i\right)-$$.

і взагалі РР k-го порядку $$u\left(x\right)$$ визначаються через різниці ($$k$$ -1)-го порядку за формулою.

$$u\left(x_0-x_1-\text{.}\text{.}\text{.}-x_k\right)=\frac{u\left(x_1-x_2-\text{.}\text{.}-x_k\right)-u\left(x_0-x_1-\text{.}\text{.}\text{.}-x_{k-1}\right)}{x_k-x_0}\text{.}$$.

Лема.Справедлива рівність.

$$u\left(x_0-x_1-\text{.}\text{.}\text{.}-x_k\right)$$. (1).

Безпосередньо з (1) випливає ряд наслідків.

1. При фіксованих $$x_0,\text{.}\text{.}\text{.},x_k$$ РР є лінійним функціоналом від функції :

$$u\left(x\right)\mathrm{:}$$.

2. РР є симетричною функцією своїх аргументів $$x_0,\text{.}\text{.}\text{.},x_k$$, тобто не змінюється при їх перестановці.

Якщо функцію задано в точках $$x_0,\text{.}\text{.}\text{.},x_k$$, то таблицю.

$$\begin{array}{cccccc}& & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \\ & & & & & \end{array}$$ $$\begin{array}{cccccc}{x}_0& u\left(x_0\right)& & & & \\ & & u\left(x_0-x_1\right)& & & \\ x_1& u\left(x_1\right)& & u\left(x_0-x_1-x_2\right)& & \\ & & u\left(x_1-x_2\right)& & & \\ x_2& u\left(x_2\right)& & u\left(x_1-x_2-x_3\right)& & \\ \text{.}& \text{.}\text{.}& \text{.}& \text{.}& \text{.}& \text{.}\\ & & & & & u\left(x_0-x_1-\text{.}\text{.}\text{.}-x_n\right)\\ & & u\left(x_{n-1}-x_n\right)& & & \\ x_n& u\left(x_n\right)& & & & \end{array}$$.

називають таблицею розділених різниць.

За допомогою РР можна одержати іншу форму запису ІП Лагранжа:

$$u\left(x\right)-L_n\left(x\right)=u\left(x\right)-\underset{k=0}{\overset{n}{}}u\left(x_k\right)\underset{j\mathrm{^1}k}{}\frac{x-x_{{}_j}}{x_k-x_j}=$$ $$=\underset{k=0}{\overset{n}{}}(x-x_k)\left[\frac{u\left(x\right)}{\underset{k=0}{\overset{n}{}}\left(x-x_k\right)}+\underset{k=0}{\overset{n}{}}\frac{u\left(x_k\right)}{\left(x_k-x\right)\underset{j\mathrm{^1}k}{}\left(x_k-x_j\right)}\right]$$ .

Порівнюючи з твердженням леми, впевнюємось, що вираз в дужках дорівнює $$u\left(x\right)$$. Таким чином, можна написати.

$$u\left(x\right)-L_n\left(x\right)=u\left(x\right)-\underset{k=0}{\overset{n}{}}u\left(x_k\right)\underset{j\mathrm{^1}k}{}\frac{x-x_{{}_j}}{x_k-x_j}=$$ $$u\left(x-x_0-\text{.}\text{.}\text{.}-x_n\right)$$ $${\mathrm{}}_{n+1}\left(x\right)$$, (2).

де $${\mathrm{}}_{n+1}\left(x\right)$$ визначено нами раніше.

Нехай $$u\left(x\right)-L_n\left(x\right)=$$ — ІП Лагранжа з вузлами інтерполяції $$x_0,\text{.}\text{.}\text{.},x_k$$. Поліном Лагранжа $$L_n\left(x\right)$$ можна подати у вигляді.

$$L_m\left(x\right)$$ = $$L_n\left(x\right)$$ +($$L_n\left(x\right)$$ — $$L_n\left(x\right)$$)+…+($$L_n\left(x\right)$$ — $$L_n\left(x\right)$$). (3).

Різниця $$u\left(x\right)-L_n\left(x\right)=$$ — $$L_n\left(x\right)$$ — поліном степеня $$m$$, який обертається в нуль в точках $$x_0,\text{.}\text{.}\text{.},x_k$$, оскільки $$L_m\left(x_j\right)=L_{m-1}\left(x_j\right)=u\left(x_j\right)$$ при $$0<=j<=m-1$$. Отже,.

$$u\left(x\right)-L_n\left(x\right)=$$ — $$L_n\left(x\right)$$ = $$A_m{\mathrm{}}_m\left(x\right)-\begin{array}{cc}& {\mathrm{}}_m\end{array}=\left(x-x_0\right)\text{.}\text{.}\text{.}\left(x-x_{m-1}\right)$$ .

Покладаючи $$x=x_m$$, одержуємо.

$$L_m\left(x_m\right)-L_{m-1}\left(x_m\right)=u\left(x_m\right)-L_{m-1}\left(x_m\right)=A_m{\mathrm{}}_m\left(x_m\right)$$ .

З іншого боку, беручи в (2) $$n=m-1$$ і $$x=x_m$$, маємо.

$$L_m\left(x_m\right)-L_{m-1}\left(x_m\right)=u\left(x_m\right)-L_{m-1}\left(x_m\right)=A_m{\mathrm{}}_m\left(x_m\right)$$ .

Таким чином, $$u\left(x_m\right)-L_{m-1}\left(x_m\right)=u\left(x_0-\text{.}\text{.}\text{.}-x_{m-1}-x_m\right){\mathrm{}}_m\left(x_m\right)$$, тому.

$$L_m\left(x_m\right)-L_{m-1}\left(x_m\right)=u\left(x_m\right)-L_{m-1}\left(x_m\right)=A_m{\mathrm{}}_m\left(x_m\right)$$ .

Підставляючи це в (3), одержимо.

$$L_n\left(x\right)=u\left(x_0\right)+u\left(x_0-x_1\right)\left(x-x_0\right)+\text{.}\text{.}\text{.}+u\left(x_0-\text{.}\text{.}\text{.}-x_n\right)\left(x-x_0\right)\text{.}\text{.}\text{.}\left(x-x_{n-1}\right)$$ .

Таке представлення ІП називається формулою Ньютона з розділеними різницями. З порівняння ІП Ньютона і Лагранжа випливає важлива рівність.

$$u\left(x-x_0-\text{.}\text{.}\text{.}-x_n\right)=\frac{u^{n+1}\left(x\right)}{\left(n+1\right)!},\begin{array}{cc}& x,\mathit{x^I}\left[x_0,x_n\right]\end{array}$$. (4).

Зокрема, якщо $$u\left(x\right)$$ — поліном $$P_l\left(x\right)=\underset{j=0}{\overset{l}{}}{}_j{x}^j$$ степеня $$l<=n$$ $$$$, то на підставі (4) маємо.

$$P_l\left(x_0-\text{.}\text{.}\text{.}-x_n\right)=\{\begin{array}{c}{}_n\\ 0\end{array}\begin{array}{c}d\\ d\end{array}\begin{array}{c}l=n\\ l<n\end{array}$$ при будь-яких $$x_0,\text{.}\text{.}\text{.},x_n$$ .

Якщо $$x_0<x_1<\text{.}\text{.}\text{.}<x_n$$, то внаслідок (4) маємо.

$$m!u\left(x_k-\text{.}\text{.}\text{.}-x_{m+k}\right)=u^{\left(m\right)}\left(x_k\right),\begin{array}{cc}& x_k\end{array}<=x_k<=x_{k+m}$$ .

Тому величина $$M_m=\underset{0<=k<=n-m}{\text{sup}}m!|u\left(x_k-\text{.}\text{.}\text{.}-x_{k+m}\right)|$$ може використовуватись як наближена оцінка для величини $$M^{\left(m\right)}=\text{sup}|u^{\left(m\right)}\left(x\right)|,\begin{array}{cc}& \mathit{x^I}\left[x_0,x_n\right]\end{array}$$ .

Використання одержаних нами інтерполяційних формул для безпосереднього обчислення наближених значень інтерпольованої функції не є ефективним. Значно краще для цього використовувати схему Ейткена. Нехай $$L_{\left(k,k+\mathrm{1,}\text{.}\text{.}\text{.},l\right)}\left(x\right)$$ — ІП з вузлами $$x_k,\text{.}\text{.}\text{.},x_l$$, зокрема, $$L_{\left(k\right)}\left(x\right)=u\left(x_k\right)$$. $$$$ Справедлива рівність.

$$L_{\left(k,k+\mathrm{1,}\text{.}\text{.}\text{.},l\right)}\left(x\right)$$. (5).

Дійсно, права частина — це поліном степеня $$l-k+1$$, який співпадає з $$u\left(x\right)$$ в точках $$x_k,\text{.}\text{.}\text{.},x_l$$. Схема Ейткена обчислення значення $$L_{\left(\mathrm{0,}\text{.}\text{.}\text{.},n\right)}\left(x\right)$$ полягає в послідовному обчисленні за допомогою (5) елементів таблиці значень ІП.

$$\begin{array}{cccccc}{x}_0& u\left(x_0\right)& & & & \\ & & u\left(x_0-x_1\right)& & & \\ x_1& u\left(x_1\right)& & u\left(x_0-x_1-x_2\right)& & \\ & & u\left(x_1-x_2\right)& & & \\ x_2& u\left(x_2\right)& & u\left(x_1-x_2-x_3\right)& & \\ \text{.}& \text{.}\text{.}& \text{.}& \text{.}& \text{.}& \text{.}\\ & & & & & u\left(x_0-x_1-\text{.}\text{.}\text{.}-x_n\right)\\ & & u\left(x_{n-1}-x_n\right)& & & \\ x_n& u\left(x_n\right)& & & & \end{array}$$.

Цю схему покладено в основу стандартної програми розв’язку такої задачі: Дано таблицю значень деякоІ функції $$u\left(x\right)$$ на $$\left[a,b\right]$$, потрібно при будь-якому значенні $$\mathit{x^I}\left[a,b\right]$$ обчислити значення $$u\left(x\right)$$ з заданою точністю $$e$$ або з найкращою можливою точністю при наявній інформації,.

Побудова алгоритму, яку ми зараз розглянемо, є досить типовою для ситуації, що виникає на практиці. Неможливо запропонувати обгрунтований алгоритм розв’язку поставленої задачі для всіх функцій, якщо про функцію нічого не відомо, крім її значень в заданих точках. Але, припускаючи, що функція є досить гладкою, одержуємо практичний критерій оцінки похибки і, грунтуючись на ньому, будуємо алгоритм розв’язку задачі.

Нехай $$x$$ фіксованоперенумеруємо вузли інтерполяції в порядку зростання $$|x_i-x|$$. $$$$ ІП $$L_{\left(\mathrm{0,}\text{.}\text{.}\text{.},m\right)}\left(x\right)$$ будемо позначати як $$L_m\left(x\right)$$ .

Раніше ми одержали вираз для похибки (2).

$$u\left(x\right)-L_m\left(x\right)=u\left(x-x_0-\text{.}\text{.}\text{.}-x_m\right){\mathrm{}}_{m+1}\left(x\right)$$ ,.

а також рівність $$u\left(x\right)-L_m\left(x\right)=u\left(x-x_0-\text{.}\text{.}\text{.}-x_m\right){\mathrm{}}_{m+1}\left(x\right)$$. Якщо $$|x_i-x|$$ малі, то $$u\left(x\right)-L_m\left(x\right)=u\left(x-x_0-\text{.}\text{.}\text{.}-x_m\right){\mathrm{}}_{m+1}\left(x\right)$$ $$«u^{\left(m+1\right)}\left(x\right)/\left(m+1\right)!«$$ $$L_{m+1}\left(x\right)-L_m\left(x\right)=u\left(x_0-\text{.}\text{.}\text{.}-x_{m+1}\right){\mathrm{}}_{m+1}\left(x\right)$$ .Враховуючи це, маємо $$u\left(x\right)-L_m\left(x\right)=u\left(x-x_0-\text{.}\text{.}\text{.}-x_m\right){\mathrm{}}_{m+1}\left(x\right)$$. З цього випливає, що величину $$e_m=|L_{m+1}\left(x\right)-L_m\left(x\right)|$$ можна розглядати як наближену оцінку похибки інтерполяційної формули $$u\left(x\right)-L_m\left(x\right)«L_{m+1}\left(x\right)-L_m\left(x\right)$$. Отже, можна послідовно обчислювати значення $$L_0\left(x\right),$$ $$L_1\left(x\right),$$ $$e_0,$$ $$L_2\left(x\right),$$ $$e_1,$$ …, якщо при деякому $$m$$ буде $$e_m<=e$$, то обчислення можна припинити і покласти $$u\left(x\right)«L_m\left(x\right)$$. Якщо ця нерівність не виконується ні при якому $$m$$, то треба знайти $$e_{m_0}=\text{min}{e}_m$$ і покласти $$u\left(x\right)«L_m\left(x\right)$$. Якщо величини $$e_m=|L_{m+1}\left(x\right)-L_m\left(x\right)|$$, починаючи з деякого $$m$$, мають стійку тенденцію до збільшення, то обчислення значень $$u\left(x\right)«L_m\left(x\right)$$, $$e_m=|L_{m+1}\left(x\right)-L_m\left(x\right)|$$ припиняються.

Розглянемо тепер дещо узагальнену задачу інтерполювання. Якщо у вузлах інтерполяції відомі не лише значення шуканої функції, а й її похідних до деякого порядку, то було б нерозумним не скористатися цією додатковою інформацією.

Нехай треба побудувати поліном $$G_s\left(x\right)$$ степеня $$s$$, що задовольняє умовам:

$$G_s\left(x_0\right)=u\left(x_0\right)\begin{array}{cc},\text{.}\text{.}\text{.},& G_s^{(m_0-1)}\left(x_0\right)=u^{\left(m_0-1\right)}\left(x_0\right)\end{array}$$.

.. .. ... (6).

$$G_s\left(x_0\right)=u\left(x_0\right)\begin{array}{cc},\text{.}\text{.}\text{.},& G_s^{(m_0-1)}\left(x_0\right)=u^{\left(m_0-1\right)}\left(x_0\right)\end{array}$$ ,.

де всі $$x_i$$ різні, $$s=m_0=\text{.}\text{.}\text{.}=m_n-1$$. Такий поліном називають ІП з кратними вузлами, а числа $$s=m_0=\text{.}\text{.}\text{.}=m_n-1$$ — кратностями вузлів $$L_{m+1}\left(x\right)-L_m\left(x\right)=u\left(x_0-\text{.}\text{.}\text{.}-x_{m+1}\right){\mathrm{}}_{m+1}\left(x\right)$$ відповідно.

ІП $$G_s\left(x\right)$$ визначається єдиним чином. Справді, припустимо що існує два полінома степеня $$s$$, що задавольняють умовам (6). Тоді їх різниця $$Q_s\left(x\right)$$ задoвoльняє cпіввідношенням.

$$Q_s\left(x_0\right)=\text{.}\text{.}\text{.}=Q_s^{m_0-1}\left(x_0\right)=\mathrm{0,}\text{.}\text{.}\text{.},Q_s\left(x_n\right)=\text{.}\text{.}\text{.}=Q_s^{\left(m_n-1\right)}\left(x_n\right)=0$$ ,.

точки $$x_0,\text{.}\text{.}\text{.},x_n$$ є нулями полінома $$Q_s\left(x\right)$$ кратності $$s=m_0=\text{.}\text{.}\text{.}=m_n-1$$. Цих нулів загалом $$s$$ +1.

Далі будемо припускати, що функція $$u\left(x\right)$$ неперервно диференційовна $$s$$ +1 раз. Існування ІП $$G_s\left(x\right)$$, що задовольняє умовам (6), доведемо, одержавши для нього явний вираз. Визначимо послідовність сукупностей точок $$x_{\text{ij}}^e,$$ $$0<e<e_0,$$ $$i=\mathrm{0,}\text{.}\text{.}\text{.},n-$$ $$j=\mathrm{1,}\text{.}\text{.}\text{.},m_i,$$ що задовольняють таким умовам: при $$0<e<e_0$$ всі точки $$x_{\text{ij}}^e$$ різні, $$x_{\text{ij}}^e$$ $$->x_i$$ при $$e->0$$. Зокрема, можна покласти $$x_{\text{ij}}^e$$ .

Побудуємо ІП $$G_s^e\left(x\right)$$ степеня $$s$$, що співпадає з $$u\left(x\right)$$ в точках $$x_{\text{ij}}^e$$. Таблиця РР, відповідних цьому набору вузлів, має вигляд:

$$\begin{array}{ccccc}u\left(x_{\text{01}}^e\right)& & & & \\ & u\left(x_{\text{01}}^e-x_{\text{02}}^e\right)& & & \\ u\left(x_{\text{02}}^e\right)& & & & \\ \text{.}& \text{.}& \text{.}& \text{.}& \text{.}\\ \text{.}& \text{.}& \text{.}& \text{.}& u\left(x_{\text{01}}^e-x_{\text{02}}^e-\text{.}\text{.}\text{.}-x_{{\text{nm}}_n}^e\right)\\ u\left(x_{{\text{nm}}_n}^e\right)& & & & \end{array}$$.

Запишемо ІП Ньютона з розділеними різницями:

$$G_s^e\left(x\right)=A_0^e+A_1^e\left(x-x_{\text{01}}^e\right)+A_2^e\left(x-x_{\text{01}}^e\right)\left(x-x_{\text{02}}^e\right)+\text{.}\text{.}\text{.}+A_s^e\left(x-x_{\text{01}}^e\right)\text{.}\text{.}\text{.}\left(x-x_{{\text{nm}}_n-1}^e\right),$$.

де $$A_0^e=u\left(x_{\text{01}}^e\right),A_1^e=u\left(x_{\text{01}}^e-x_{\text{02}}^e\right),\text{.}\text{.}\text{.},A_s^e=u\left(x_{\text{01}}^e-x_{\text{02}}^e-\text{.}\text{.}\text{.}-x_{{\text{nm}}_n}^e\right)\text{.}$$.

Виражаючи РР через похідні, маємо.

$$u\left(x_{\text{il}}^e-\text{.}\text{.}\text{.}-x_{\text{im}}^e\right)=\frac{u^{\left(m-l\right)}\left(x_i\right)}{\left(m-l\right)!}\text{.}$$.

Таким чином, всі елементи таблиці мають границі, при $$e->0$$. Ми позначатимемо $$u\left(x_{\text{il}}^e-\text{.}\text{.}\text{.}-x_{\text{im}}^e\right)=\frac{u^{\left(m-l\right)}\left(x_i\right)}{\left(m-l\right)!}\text{.}$$ через $$\underset{m-l+1}{u\left(x_i-x_i-\text{.}\text{.}\text{.}-x_i\right)}$$, отже, $$\underset{m-l+1}{u\left(x_i-x_i-\text{.}\text{.}\text{.}-x_i\right)}$$ .

Якщо всі елементи таблиці мають границі, то на будь-якому відрізку поліноми $$G_s^e\left(x\right)$$ при $$e->0$$ $$$$ прямують до деякого поліному.

$$G_s^e\left(x\right)=A_0^e+A_1^e\left(x-x_{\text{01}}^e\right)+A_2^e\left(x-x_{\text{01}}^e\right)\left(x-x_{\text{02}}^e\right)+\text{.}\text{.}\text{.}+A_s^e\left(x-x_{\text{01}}^e\right)\text{.}\text{.}\text{.}\left(x-x_{{\text{nm}}_n-1}^e\right),$$.

$$A_0^e=u\left(x_{\text{01}}^e\right),A_1^e=u\left(x_{\text{01}}^e-x_{\text{02}}^e\right),\text{.}\text{.}\text{.},A_s^e=u\left(x_{\text{01}}^e-x_{\text{02}}^e-\text{.}\text{.}\text{.}-x_{{\text{nm}}_n}^e\right)\text{.}$$ ,.

$$A_i=\underset{e->0}{\text{lim}}{A}_i^e$$ .

Поліном.

$$G_s\left(x\right)=A_0+A_1\left(x-x_0\right)+A_2{\left(x-x_0\right)}^2+\text{.}\text{.}+A_s{\left(x-x_0\right)}^{m_0}\text{.}\text{.}{\left(x-x_{n-1}\right)}^{m_{n-1}}{\left(x-x_n\right)}^{m_n-1}$$.

записується у вигляді.

$$G_s\left(x\right)=\underset{i=1}{\overset{m_0}{}}\frac{u^{\left(i-1\right)}\left(x_0\right)}{\left(i-1\right)!}{\left(x-x_0\right)}^{i-1}+O\left({\left(x-x_0\right)}^{m_0}\right)$$ .

Звідси випливає, що він задовольняє умовам, заданим в точці $$x_0$$. Внаслідок єдиності ІП поліном $$G_s^e\left(x\right)$$ не зміниться, якщо переозначити $$x_0=x_j,x_j=x_0$$. Тому граничний поліном буде задовольняти заданим умовам в будь-якій точці $$x_j$$. Отже, цей поліном є шуканим.

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

1. Довести рівність.

$$u\left(x_0-x_1-\text{.}\text{.}\text{.}-x_k\right)$$ .

При доведенні можна викристати метод математичної індукції.

2. Довести, що при фіксованих $$x_0,\text{.}\text{.}\text{.},x_k$$ PР є лінійним функціоналом від функції $$u\left(x\right)$$ .

3. Довести, що РР $$k$$ -го порядку від алгебраїчного полінома $$k$$ -го степеня прийиає постійне значення, що не залежить від набору вузлів $$x_0,\text{.}\text{.}\text{.},x_n$$, РР більш високих порядків дорівнюють нулю.

4. Дать порівняльну характеристику ІП Лагранжа та Ньютона.

5. Нехай на $$\left[a,b\right]$$, звідки беруться $$x$$ та вузли інтерполювання, функція $$u\left(x\right)$$ має похідну $$u\left(x\right)$$, яка зберігає свій знак. Показати, що в цьому разі $$u\left(x-x_0-\text{.}\text{.}\text{.}-x_n\right)\begin{array}{cc}& x,\mathit{x^I}\left[x_0,x_n\right]\end{array}$$ є монотонною функцією аргумента $$x$$ на $$\left[a,b\right]$$ .

6. Показати, що $$n$$ -а РР полінома $$n$$ -го степеня дорівнює коефіцієнту при $$x$$ незалежно від вибору вузлів $$x_0,\text{.}\text{.}\text{.},x_n$$ .

7. Показати, що якщо $$u\left(x\right)$$, то $$u\left(x_0-x_1-\text{.}\text{.}\text{.}-x_n\right)$$ .

8. Показати, що якщо аргументи помножити на одну і ту ж сталу $$g$$, а значення функції залишити незмінними, то РР $$u\left(x-x_0-\text{.}\text{.}\text{.}-x_n\right)$$ помножаться на $$g$$ .