Участник:Айнагуль Джумабекова/Песочница

Материал из MachineLearning.

(Различия между версиями)

Версия 11:44, 26 декабря 2008

Содержание

1 Введение
- 1.1 Постановка математической задачи
2 Изложение метода
- 2.1 Интерполирование полиномами Лагранжа

Введение

Постановка математической задачи

Численное дифференцирование применяется, если функцию $y(x)$ трудно или невозможно продифференцировать аналитически - например, если она задана таблицей. Оно нужно также при решении дифференциальных уравнений при помощи разностных методов.

Изложение метода

При численном дифференцировании функцию $y(x)$ аппроксимируют легко вычисляемой функцией $\varphi(x)$ и приближенно полагают $y'(x)=\varphi'(x)$ . При этом можно использовать различные способы аппроксимации.

Интерполирование полиномами Лагранжа

Рассмотрим неравномерную сетку $\omega_h=\{a=x_0<x_1<x_2<\dots<x_N=b\}$ и обозначим за $h_i=x_i-x_{i-1}$ , $i=1,2,\dots,N$ шаги этой сетки. В качества примера получим формулы численного дифференцирования, основанные на использовании многочлена Лагранжа $L_{2,i}(x)$ , построенного для функции $u(x)$ по трем точкам $x_{i-1},x_i,x_{i+1}$ . Многочлен $L_{2,i}(x)$ имеет вид

$L_{2,i}(x)=\frac {(x-x_i)(x-x_{i+1})}{h_i(h_i+h_{i+1})}u_{i-1}-\frac {(x-x_{i-1})(x-x_{i+1})}{h_ih_{i+1}}u_i+\frac {(x-x_{i-1})(x-x_i)}{h_{i+1}(h_i+h_{i+1})}u_{i+1}$

Отсюда получим $L_{2,i}'(x)=\frac{(2x-x_i-x_{i+1})}{h_i(h_i+h_{i+1})}u_{i-1}-\frac {(2x-x_{i-1}-x_{i+1})}{h_ih_{i+1}}u_i+\frac {(2x-x_{i-1}-x_i)}{h_{i+1}(h_i+h_{i+1})}u_{i+1}$

Это выражение можно принять за приближенное значение $u'(x)$ в любой точке $x$ ∈ $[x_{i-1},x_{i+1}]$ . Его удобнее записать в виде $L_{2,i}'(x)=\frac {1}{\bar{h_i}}[(x-x_{i-\frac{1}{2}}) \frac{u_{i+1}-u_i}{h_{i+1}} + (x_{i+\frac{1}{2}}-x) \frac{u_i-u_{i-1}}{h_i}]$ , где $\bar{h_i}=0,5(h_i+h_{i+1})$ , $x_{i-\frac{1}{2}}=x_i-0,5h_i$ .

В частности, при $x=x_i$ получим $L_{2,i}'(x_i)=\frac{1}{2}(\frac{h_i}{\bar{h_i}}\frac{u_{i+1}-u_i}{h_{i+1}}+\frac{h_{i+1}}{\bar{h_i}}\frac{u_i-u_{i-1}}{h_i})$ , И если сетка равномерна, $h_{i+1}=h_i=h$ , то приходим к центральной разностной производной, $L_{2,i}'(x_i)=u_{\dot{x},i}$ . При использовании интерполяционного многочлена первой степени точно таким образом можно получить односторонние разностные производные $u_{\bar{x},i}$ и $u_{x,i}$ . Далее вычисляя вторую производную многочлена $L_{2,i}(x)$ , получим приближенное выражение для $u''(x)$ при $x$ ∈ $[x_{i-1},x_{i+1}]$ :

$u''(x)$ ≈ $L_{2,i}''(x)=\frac{1}{\bar{h_i}}(\frac{u_{i+1}-u_i}{h_{i+1}}- \frac{u_i-u_{i-1}}{h_i})$

На равномерной сетке это выражение совпадает со второй разностной производной $u_{\bar{x}x,i}$ . Ясно, что для приближенного вычисления дальнейших производных уже недостаточно многочлена $L_{2,i}(x)$ , надо привлекать многочлены более высокого порядка и тем самым увеличивать число узлов, участвующих в аппроксимации.

Порядок погрешности аппроксимации зависит как от порядка интерполяционного многочлена, так и от расположения узлов интерполирования. Получим выражение для погрешности аппроксимации, возникающей при замене $u'(x)$ выражением $L_{2,i}'(x)$ . Будем считать, что $x$ ∈ $[x_{i-1},x_{i+1}]$ и что величины $h_i, h_{i+1}$ имеют один и тот же порядок малости при измельчении сетки. По формуле Тейлора в предположении ограниченности $u^{(4)}(x)$ получим $u_{i+k}=u(x)+(x_{i+k}-x)u'(x)+\frac{{(x_{i+k}-x)}^2}{2}u''(x) +\frac{{(x_{i+k}-x)}^3}{3}u'''(x) +O(h^4)$ ,

где $k=0$ ,± $1,h=max\{h_i,h_{i+1}\}$

Отсюда приходим к следующим разложениям разностных отношений

$\frac{u_i-u_{i-1}}{h_i}=u'(x)-(x-x_{i-\frac{1}{2}})u''(x)+(\frac{{(x-x_{i-\frac{1}{2}})}^2}{2}+\frac{h_i^2}{24})u'''(x)+O(h^3)$

$\frac{u_{i+1}-u_i}{h_{i+1}}=u'(x)-(x_{i+\frac{1}{2}}-x)u''(x)+(\frac{{(x_{i+\frac{1}{2}}-x)}^2}{2}+\frac{h_{i+1}^2}{24})u'''(x)+O(h^3)$

Подставляя полученные формулы в выражение для разностной производной и приводя подобные слагаемые получим

$L_{2,i}'(x)=u'(x)-[\frac{{(x-x_i)}^2}{2}-\frac{(h_{i+1}-h_i)(x-x_i)}{3}-\frac{h_ih_{i+1}}{6}]u'''(x)+O(h^3)$ , $x$ ∈ $[x_{i-1},x_{i+1}]$ .

Отсюда видно,что разностное выражение аппроксимирует $u'(x)$ со вторым порядком.

Если подставить полученные ранее разностные отношения в выражение для второй производной многочлена $L_{2,i}(x)$ , то имеем

$L_{2,i}''(x)=u''(x)+(x_i-x + \frac{h_{i+1}-h_i}{3})u'''(x)+O(h^2)$

Из этого выражения видно, что даже на равномерной сетке,т.е. когда $h_i=h_{i+1}$ , второй порядок аппроксимации имеет место лишь в точке $x=x_i$ , а относительно других точек (например, $x=x_{i+1}$ ) выполняется аппроксимация только первого порядка. Таким образом, получим аппроксимацию лишь первого порядка.

Для того, чтобы избежать больших погрешностей в процессе приближения, весь отрезок [a,b] разбивают на частичные отрезки и на каждом из частичных отрезков приближенно заменяют функцию $f(x)$ многочленом невысокой степени (так называемая кусочно-полиномиальная интерполяция). Одним из способов интерполирования на всем отрезке является интерполирование с помощью сплайн-функций. Сплайн-функцией или сплайном называют кусочно-полиномиальную функцию, определенную на отрезке [a,b] и имеющую на этом отрезке некоторое число непрерывных производных. Преимущество сплайнов перед обычной интерполяцией является, во-первых их сходимость, во-вторых, устойчивость процесса вычислений. Построение кубического сплайна. Пусть на [a,b] задана непрерывная функция $f(x)$ . Введем сетку $a=x_0<x_1<x_2<\dots<x_N=b$ и обозначим $f_i=f(x_i)$ , $i=0,1,\dots,N$ . Сплайном соответствующим данной функции $f(x)$ и данным узлам $\{x_i\}_{i=0}^N$ называется функция $s(x)$ , удовлетворяющая следующим условиям: а) на каждом сегменте $[x_i-1,x_i]$ , $i=1,2,\dots,N$ функция $s(x)$ является многочленом третьей степени; б) функция $s(x)$ , а также её первая и вторая производная производные непрерывны на [a,b]; в) $s(x_i)=f(x_i)$ , $i=1,2,\dots,N$ ; На каждом из отрезков $[x_i-1,x_i]$ , $i=1,2,\dots,N$ будем искать функцию $s(x)=s_i(x)$ в виде многочлена третьей степени

$s_i(x)=a_i+b_i(x-x_i)+\frac{c_i}{2}(x-x_i)^2 +\frac{d_i}{6}(x-x_i)^3$

$x_i-1<=x<=x_i$ , $i=1,2,\dots,N$ , где $a_i,b_i,c_i,d_i$ - коэффициенты, подлежащие определению. Доказано, что существует единственный кубический сплайн, определяемый условиями а)-в) и граничными условиями $s''(a)=s''(b)=0$ . Для их нахождения используются следующие формулы 1) $a_i=f(x_i)$ , $i=1,2,\dots,N$

2) Для определения коэффициентов $c_i$ получаем систему уравнений

$h_ic_{i-1}+2(h_i+h_{i+1})c_i+h_{i+1}c_{i+1}=6\left(\frac{f_{i+1}-f_i}{h_{i+1}}-\frac{f_i-f_{i-1}}{h_i}\right), <tex>i=1,2,\dots,N-1$ , $c_0=c_N=0$

(система решается методом прогонки) По найденным коэффициентам $c_i$ коэффициенты $b_i$ , $d_i$ определяются с помощью явных формул

3) $d_i=\frac{c_i-c_{i-1}}{h_i},<tex>i=1,2,\dots,N$

4) $b_i=\frac{h_i}{2}c_i-\frac{h_i^2}{6}d_i+\frac{f_i-f_{i-1}}{h_i}, <tex>i=1,2,\dots,N$

Найдем производные введенного кубического сплайна, имеем $s_i'(x)=b_i+c_i(x-x_i)+\frac{d_i}{2}{(x-x_i)}^2$

$s_i''(x)=c_i+d_i(x-x_i)$

$s_i'''(x)=d_i$

Рассмотрим оценку погрешности метода, которая зависит от выбора сеток и от гладкости $f(x)$ . Для простоты изложения допустим, что сетка равномерная, т.е.

$\omega_h=\{x_i=a+ih, i=0,1,\dots,N\}$ с шагом $b=\frac{b-a}{N}$

От функции $f(x)$ будем требовать существования непрерывной на [a,b] четвертой производной, $f(x)$ $C^{(4)}[a,b]$ . Кроме того, предположим, что выполнены граничные условия $f''(a)=f''(b)=0$ и такие же условия для сплайнов. Обозначим,

$||g(x)||_{C[a,b]}=\max_{[a,b]}|g(x)|$ , $M_4=||f^4(x)||_{C[a,b]}$

Пусть $s_h(x)$ - кубический сплайн, построенный для функции $f(x)$ на сетке $\omega_h$ . В следующей теореме приведены оценки погрешности интерполяции для функции $f(x)$ и её производных $f'(x)$ , $f''(x)$

Теорема Для $f(x)$ $C^{(4)}[a,b]$ справедливы оценки

$||f(x)-s_h(x)||_{C[a,b]}<=M_4h^4$

$||f'(x)-s_h'(x)||_{C[a,b]}<=M_4h^3$

$||f''(x)-s_h''(x)||_{C[a,b]}<=M_4h^2$

Из этих оценок следует, что при $h \to 0$ (т.е. при $N \to \infty$ ) последовательности $s_h^{(i)}(x)$ , $i=0,1,2$ сходятся соответственно к функциям $f^{(i)}(x)$ $i=0,1,2$ .

Обычно дифференцирование кубического сплайна позволят определить первую и вторую производную интерполяционного многочлена с хорошей точностью. Если надо вычислить более высокие производные, то целесообразно строить сплайны высоких порядков. Из-за большей трудоемкости этот способ редко используется. Способ дифференцирования с помощью сплайновой интерполяцией теоретически мало исследован.

Не всякую функцию целесообразно приближать алгебраическими многочленами. Рассмотрим тригонометрическую интерполяцию. Если $f(x)$ - периодическая функция с периодом l, то естественно строить приближения с помощью функций

$\varphi_k(x)=a_k\cos(\frac{\pi kx}{l})+b_k\sin(\frac{\pi kx}{l}), k=0,1,\dots,n$

Таким образом, тригонометрическая интерполяция состоит в замене $f(x)$ тригонометрическим многочленом

$T_n(x)=\sum_{k=0}^n \varphi_k(x)= a_0 + \sum{k=1}^n\left(a_k\cos(\frac{\pi kx}{l})+b_k\sin(\frac{\p ikx}{l})\right)$ ,

коэффициенты которого отыскиваются из системы уравнений

$T_n(x_j)=f(x_j), j=1,2,\dots,2n+1$ ,

где $x_0<x_1<\dots<x_{2n+1},x_{2n+1}-x_0=l$

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%90%D0%B9%D0%BD%D0%B0%D0%B3%D1%83%D0%BB%D1%8C_%D0%94%D0%B6%D1%83%D0%BC%D0%B0%D0%B1%D0%B5%D0%BA%D0%BE%D0%B2%D0%B0/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

@@ Строка 57: / Строка 57: @@
 Из этого выражения видно, что даже на равномерной сетке,т.е. когда <tex>h_i=h_{i+1}</tex>, второй порядок аппроксимации имеет место лишь в точке <tex>x=x_i</tex>, а относительно других точек (например,<tex>x=x_{i+1}</tex>) выполняется  аппроксимация только первого порядка.
 Таким образом, получим аппроксимацию лишь первого порядка.
+Для того, чтобы избежать больших погрешностей в процессе приближения, весь отрезок [a,b] разбивают на частичные отрезки и на каждом из частичных отрезков приближенно заменяют функцию <tex>f(x)</tex> многочленом невысокой степени (так называемая кусочно-полиномиальная интерполяция).
+Одним из способов интерполирования на всем отрезке является интерполирование с помощью сплайн-функций. Сплайн-функцией или сплайном называют кусочно-полиномиальную функцию, определенную на отрезке [a,b] и имеющую на этом отрезке некоторое число непрерывных производных.
+Преимущество сплайнов перед обычной интерполяцией является, во-первых их сходимость, во-вторых, устойчивость процесса вычислений.
+Построение кубического сплайна.
+Пусть на  [a,b] задана непрерывная функция <tex>f(x)</tex>. Введем сетку
+<tex>a=x_0<x_1<x_2<\dots<x_N=b</tex>
+и обозначим <tex>f_i=f(x_i)</tex>, <tex>i=0,1,\dots,N</tex>.
+Сплайном соответствующим данной функции <tex>f(x)</tex> и данным узлам <tex>\{x_i\}_{i=0}^N</tex> называется функция <tex>s(x)</tex>, удовлетворяющая следующим условиям:
+а) на каждом сегменте <tex>[x_i-1,x_i]</tex>, <tex>i=1,2,\dots,N</tex>  функция <tex>s(x)</tex> является многочленом третьей степени;
+б) функция <tex>s(x)</tex>, а также  её первая и вторая производная производные непрерывны на [a,b];
+в) <tex>s(x_i)=f(x_i)</tex>,<tex>i=1,2,\dots,N</tex>;
+На каждом из отрезков <tex>[x_i-1,x_i]</tex>, <tex>i=1,2,\dots,N</tex>  будем искать функцию <tex>s(x)=s_i(x)</tex> в виде многочлена третьей степени
+<tex>s_i(x)=a_i+b_i(x-x_i)+\frac{c_i}{2}(x-x_i)^2 +\frac{d_i}{6}(x-x_i)^3</tex>
+<tex>x_i-1<=x<=x_i</tex>, <tex>i=1,2,\dots,N</tex>,
+где <tex>a_i,b_i,c_i,d_i</tex> - коэффициенты, подлежащие определению.
+Доказано, что существует единственный кубический сплайн, определяемый условиями а)-в) и граничными условиями <tex>s''(a)=s''(b)=0</tex>.
+Для их нахождения используются следующие формулы
+) <tex>a_i=f(x_i)</tex>,<tex>i=1,2,\dots,N</tex>
+) Для определения коэффициентов <tex>c_i</tex> получаем систему уравнений
+<tex>h_ic_{i-1}+2(h_i+h_{i+1})c_i+h_{i+1}c_{i+1}=6\left(\frac{f_{i+1}-f_i}{h_{i+1}}-\frac{f_i-f_{i-1}}{h_i}\right), <tex>i=1,2,\dots,N-1</tex>  ,<tex>c_0=c_N=0</tex>
+(система решается методом прогонки)
+По найденным коэффициентам <tex>c_i</tex> коэффициенты <tex>b_i</tex>, <tex>d_i</tex> определяются с помощью явных формул
+) <tex>d_i=\frac{c_i-c_{i-1}}{h_i},<tex>i=1,2,\dots,N</tex>
+) <tex>b_i=\frac{h_i}{2}c_i-\frac{h_i^2}{6}d_i+\frac{f_i-f_{i-1}}{h_i},
+<tex>i=1,2,\dots,N</tex>
+Найдем производные введенного кубического сплайна, имеем
+<tex>s_i'(x)=b_i+c_i(x-x_i)+\frac{d_i}{2}{(x-x_i)}^2</tex>
+<tex>s_i''(x)=c_i+d_i(x-x_i)</tex>
+<tex>s_i'''(x)=d_i</tex>
+Рассмотрим оценку погрешности метода, которая зависит от выбора сеток и от гладкости <tex>f(x)</tex>. Для простоты изложения допустим, что сетка равномерная, т.е.
+<tex>\omega_h=\{x_i=a+ih, i=0,1,\dots,N\}</tex>
+с  шагом <tex>b=\frac{b-a}{N}</tex>
+От функции <tex>f(x)</tex> будем требовать существования непрерывной на [a,b] четвертой производной, <tex>f(x)</tex>  <tex>C^{(4)}[a,b]</tex>. Кроме того, предположим, что выполнены граничные условия <tex>f''(a)=f''(b)=0</tex> и такие же условия для сплайнов. Обозначим,
+<tex>||g(x)||_{C[a,b]}=\max_{[a,b]}|g(x)|</tex>,    <tex>M_4=||f^4(x)||_{C[a,b]}</tex>
+Пусть <tex>s_h(x)</tex> - кубический сплайн, построенный для функции <tex>f(x)</tex> на сетке <tex>\omega_h</tex>. В следующей теореме приведены оценки погрешности интерполяции для функции <tex>f(x)</tex> и её производных <tex>f'(x)</tex>, <tex>f''(x)</tex>
+Теорема
+	Для <tex>f(x)</tex>  <tex>C^{(4)}[a,b]</tex> справедливы оценки
+		<tex>||f(x)-s_h(x)||_{C[a,b]}<=M_4h^4</tex>
+		<tex>||f'(x)-s_h'(x)||_{C[a,b]}<=M_4h^3</tex>
+		<tex>||f''(x)-s_h''(x)||_{C[a,b]}<=M_4h^2</tex>
+Из этих оценок следует, что при  <tex>h \to 0</tex>  (т.е. при <tex>N \to \infty</tex>)  последовательности  <tex>s_h^{(i)}(x)</tex>, <tex>i=0,1,2</tex> сходятся соответственно к функциям <tex>f^{(i)}(x)</tex> <tex>i=0,1,2</tex>.
+Обычно дифференцирование кубического сплайна позволят определить первую и вторую производную интерполяционного многочлена с хорошей точностью. Если надо вычислить более высокие производные, то целесообразно строить сплайны высоких порядков. Из-за большей трудоемкости этот способ редко используется. Способ дифференцирования с помощью сплайновой интерполяцией теоретически мало исследован.
+Не всякую функцию целесообразно приближать алгебраическими многочленами.
+Рассмотрим тригонометрическую интерполяцию.
+Если <tex>f(x)</tex> - периодическая функция с периодом l, то естественно строить приближения с помощью функций
+	<tex>\varphi_k(x)=a_k\cos(\frac{\pi kx}{l})+b_k\sin(\frac{\pi kx}{l}), k=0,1,\dots,n</tex>
+Таким образом, тригонометрическая интерполяция состоит в замене <tex>f(x)</tex> тригонометрическим многочленом
+<tex>T_n(x)=\sum_{k=0}^n \varphi_k(x)= a_0 + \sum{k=1}^n\left(a_k\cos(\frac{\pi kx}{l})+b_k\sin(\frac{\p ikx}{l})\right)</tex>,
+коэффициенты которого отыскиваются из системы уравнений
+<tex>T_n(x_j)=f(x_j), j=1,2,\dots,2n+1</tex>,
+где <tex>x_0<x_1<\dots<x_{2n+1},x_{2n+1}-x_0=l</tex>

Участник:Айнагуль Джумабекова/Песочница

Материал из MachineLearning.

Версия 11:44, 26 декабря 2008

Содержание

Введение

Постановка математической задачи

Изложение метода

Интерполирование полиномами Лагранжа

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты