Участник:Lr2k/Песочница

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

< Участник:Lr2k(Различия между версиями)
Перейти к: навигация, поиск
Текущая версия (09:31, 30 декабря 2009) (править) (отменить)
(Полностью удалено содержимое страницы)
 
(22 промежуточные версии не показаны)
Строка 1: Строка 1:
-
== Введение ==
 
-
=== Постановка математической задачи ===
 
-
 
-
Одной из основных задач численного анализа является задача об интерполяции функций.
 
-
Пусть на отрезке <tex>a\le \x\le \b</tex> задана сетка <tex>\omega=\{x_i:x_0=a<x_1<\cdots<x_i<\cdots<x_n=b\}</tex> и в её узлах заданы значения функции <tex>y(x)</tex>, равные <tex>y(x_0)=y_0,\cdots,y(x_i)=y_i,\cdots,y(x_n)=y_n</tex>. Требуется построить ''интерполянту'' — функцию <tex>f(x)</tex>, совпадающую с функцией <tex>y(x)</tex> в узлах сетки:
 
-
{{ eqno | 1 }}
 
-
<p align="center"><tex>f(x_i)=y_i, i=0,1,\cdots,n.</tex></p>
 
-
 
-
Основная цель интерполяции — получить быстрый (экономичный) алгоритм вычисления значений <tex>f(x)</tex> для значений <tex>x</tex>, не содержащихся в таблице данных.
 
-
 
-
Интерполируюшие функции <tex>f(x)</tex>, как правило строятся в виде линейных комбинаций некоторых элементарных функций:
 
-
<p align="center"><tex>f(x)=\sum_{k=0}^N {c_k\Phi_k(x)},</tex></p>
 
-
 
-
где <tex>\{\Phi_k(x)\}</tex> — фиксированный линейно независимые функции, <tex>c_0, c_1, \cdots, c_n</tex> — не определенные пока коэффициенты.
 
-
 
-
Из условия {{eqref|1}} получаем систему из <tex>n+1</tex> уравнений относительно коэффициентов <tex>\{c_k\}</tex>:
 
-
<p align="center"><tex>\sum_{k=0}^N {c_k\Phi_k(x_i)}=y_i, i=0,1,\cdots,n.</tex></p>
 
-
 
-
Предположим, что система функций <tex>\Phi_k(x)</tex> такова, что при любом выборе узлов <tex>a<x_1<\cdots<x_i<\cdots<x_n=b</tex> отличен от нуля определитель системы:
 
-
<p align="center"><tex>\Delta(\Phi) = \begin{vmatrix} \Phi_0(x_0) & \Phi_1(x_0) & \cdots & \Phi_n(x_0) \\\Phi_0(x_1) & \Phi_1(x_1) & \cdots & \Phi_n(x_1)\\ \cdots & \cdots & \cdots & \cdots \\\Phi_0(x_n) & \Phi_1(x_n) & \cdots & \Phi_n(x_n)\end{vmatrix}</tex>.</p>
 
-
 
-
Тогда по заданным <tex>y_i (i=1,\cdots, n)</tex> однозначно определяются коэффициенты <tex>c_k (k=1,\cdots, n)</tex>.
 
-
 
-
== Изложение метода ==
 
-
Интерполяция кубическими сплайнами является частным случаем кусочно-полиномиальной интерполцией. В этом специальном случае между любыми двумя соседними узлами функция интерполируется кубическим полиномом. его коэффициенты на каждом интервале определяются из условий сопряжения в узлах:
 
-
<p align="center"><tex>f_i=y_i,
 
-
 
-
f'(x_i-0)=f'(x_i+0),
 
-
 
-
f''(x_i-0)=f''(x_i+0), i=1, 2, \cdots, n-1.</tex></p>
 
-
 
-
Кроме того, на границе при <tex>x=x_0</tex> и <tex>x=x_n</tex> ставятся условия
 
-
{{ eqno | 2 }}
 
-
<p align="center"><tex>f''(x_0)=0, f''(x_n)=0.</tex></p>
 
-
 
-
Будем искать кубический полином в виде
 
-
 
-
{{ eqno | 3 }}
 
-
<p align="center"><tex>f(x)=a_i+b_i(x-x_{i-1})+c_i(x-x_{i-1})^2+d_i(x-x_{i-1})^3, x_{i-1}\le \x\le \x_i.</tex></p>
 
-
 
-
Из условия <tex>f_i=y_i</tex> имеем
 
-
{{ eqno | 4 }}
 
-
<p align="center"><tex>f(x_{i-1})=a_i=y_{i-1},
 
-
 
-
f(x_i)=a_i+b_ih_i+c_ih_i^2+d_ih_i^3=y_i,
 
-
 
-
h_i=x_i-x_{i-1}, i=1, 2, \cdots, n-1.</tex></p>
 
-
 
-
Вычислим производные:
 
-
 
-
<p align="center"><tex>f'(x)=b_i+2c_i(x-x_{i-1})+3d_i(x-x_{i-1})^2,
 
-
 
-
f''(x)=2c_i+6d_i(x-x_{i-1}), x_{i-1}\le \x\le \x_i,</tex></p>
 
-
 
-
и потребуем их непрерывности при <tex>x=x_i</tex>:
 
-
{{ eqno | 5 }}
 
-
<p align="center"><tex>b_{i+1}=b_i+2c_ih_i + 3d_ih_i^2,
 
-
 
-
c_{i+1}=c_i+3d_ih_i, i=1, 2, \cdots, n-1.</tex></p>
 
-
 
-
Общее число неизвестных коэффициентов, очевидно, равно <tex>4n</tex>, число уравнений {{eqref|4}} и {{eqref|5}} равно <tex>4n-2</tex>. Недостающие два уравнения получаем из условия {{eqref|2}} при <tex>x=x_0</tex> и <tex>x=x_n</tex>:
 
-
<p align="center"><tex>c_1=0, c_n+3d_nh_n=0.</tex></p>
 
-
 
-
Выражение из {{eqref|5}} <tex>d_i=\frac{c_{i+1}-c_i}{3h_i}</tex>, подставляя это выражение в {{eqref|4}} и исключая <tex>a_i=y_{i-1}</tex>, получим
 
-
<p align="center"><tex>b_i=\[\frac{y_i-y_{i-1}}h_i\]-\frac{1}{3}h_i(c_{i+1}+2c_i), i=1, 2, \cdots, n-1,
 
-
 
-
b_n=\[\frac{y_n-y_{n-1}}h_n\]-\frac{2}{3}h_nc_n,.</tex></p>
 
-
 
-
Подставив теперь выражения для <tex>b_i, b_{i+1}</tex> и <tex>d_i</tex> в первую формулу {{eqref|5}}, после несложных преобразований получаем для определения <tex>c_i</tex> разностное уравнение второго порядка
 
-
{{ eqno | 6 }}
 
-
<p align="center"><tex>h_ic_i+2(h_i+h_{i+1})c_{i+1}+h_{i+1}c_{i+2}=s\left(\frac{y_{i+1}-y_i}{h_{i+1}} - \frac{y_{i+1}-y_i}{h_{i+1}}\right), i=1, 2, \cdots, n-1.</tex></p>
 
-
 
-
С краевыми условиями
 
-
{{ eqno | 7 }}
 
-
<p align="center"><tex>c_1=0, c_{n+1}=0.</tex></p>
 
-
 
-
Условие <tex>c_{n+1}=0</tex> эквивалентно условию <tex>c_n+3d_nh_n=0</tex> и уравнению <tex>c_{i+1} = c_i+d_ih_i</tex>. Разностное уравнение {{eqref|6}} с условиями {{eqref|7}} можно решить методом прогонки, представив в виде системы линейных алгебраических уравнений вида <tex>~A*x=F</tex>, где матрица <tex>~A</tex> имеет следующий вид:
 
-
<p align="center"><tex>A = \begin{pmatrix} C_1 & B_1 & 0 & 0 & \cdots & 0 & 0
 
-
\\ A_2 & C_2 & B_2 & 0 & \cdots & 0 & 0
 
-
\\ 0 & A_3 & C_3 & B_3 & \cdots & 0 & 0
 
-
\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots
 
-
\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots
 
-
\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & B_{n-1}
 
-
\\ 0 & 0 & 0 & 0 & \cdots & A_{n} & C_{n}
 
-
\end{pmatrix}, где A_i=h_i, i=2, \cdots, n, B_i = h_{i+1}, i=1, \cdots, n-1 и C_i=2(h_i+h_{i+1}), i =1, \cdots, n</tex></p>
 
-
 
-
 
-
 
-
 
-
=== Метод прогонки ===
 
-
 
-
'''Трёхдиагональной матрицей''' называют [[Матрица (математика)|матрицу]] следующего вида:
 
-
 
-
: <math>A = \begin{pmatrix} C_1 & B_1 & 0 & 0 & \cdots & 0 & 0
 
-
\\ A_2 & C_2 & B_2 & 0 & \cdots & 0 & 0
 
-
\\ 0 & A_3 & C_3 & B_3 & \cdots & 0 & 0
 
-
\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots
 
-
\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots
 
-
\\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & B_{n-1}
 
-
\\ 0 & 0 & 0 & 0 & \cdots & A_{n} & C_{n}
 
-
\end{pmatrix}
 
-
</math>.
 
-
 
-
[[Система линейных алгебраических уравнений|Системы линейных алгебраических уравнений]] с такими матрицами встречаются при решении многих [[задача|задач]] математики и физики. Краевые условия <math>x_1</math> и <math>x_n</math>, которые берутся из контекста задачи, задают первую и последнюю строки. Так краевое условие первого рода <math>F(x=x_1)=F_1</math> определит перую строку в виде <math>C_1=1</math>, <math>B_1=0</math>, а условие второго рода <math>dF/dx(x=x_1)=F_1</math> будет соответствовать значениям <math>C_1=-1</math>, <math>B_1=1</math>.
 
-
 
-
Для решения систем вида <math>~A*x=F</math> используется '''метод прогонки''', основанный на предположении, что искомые неизвестные связаны рекуррентным соотношением:
 
-
 
-
: <math>x_i = \alpha_{i+1}x_{i+1} + \beta_{i+1}\,\!
 
-
</math>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;, где&nbsp;<math>~i=1,n-1</math><font face="Courier New"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(1)</font>
 
-
Используя это соотношение, выразим x<sub>i-1</sub> и x<sub>i</sub> через x<sub>i+1</sub> и подставим
 
-
в i-e уравнение:
 
-
: <math>
 
-
\left(A_i\alpha_i\alpha_{i+1} + C_i\alpha_{i+1} + B_i\right)x_{i+1} + A_i\alpha_i\beta_{i+1} + A_i\beta_i + C_i\beta_{i+1} - F_i = 0
 
-
</math>,
 
-
где F<sub>i</sub> - правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать
 
-
: <math>\begin{matrix}
 
-
A_i\alpha_i\alpha_{i+1} + C_i\alpha_{i+1} + B_i = 0\end{matrix}</math>
 
-
: <math>\begin{matrix}
 
-
A_i\alpha_i\beta_{i+1} + A_i\beta_i + C_i\beta_{i+1} - F_i = 0
 
-
\end{matrix}</math>
 
-
Отсюда следует:
 
-
: <math>
 
-
\alpha_{i+1} = {-B_i \over A_i\alpha_i + C_i}\,\!
 
-
</math>
 
-
 
-
 
-
: <math>
 
-
\beta_{i+1} = {F_i - A_i\beta_i \over A_i\alpha_i + C_i}
 
-
\,\!</math>
 
-
Из первого уравнения получим:
 
-
: <math>
 
-
\alpha_2 = {-B_1 \over C_1}
 
-
\,\!</math>.
 
-
: <math>
 
-
\beta_2 = {F_1 \over C_1}
 
-
\,\!</math>.
 
-
После нахождения прогоночных коэффициентов <math>\alpha</math> и <math>\beta</math>, используя уравнение (1), получим решение системы. При этом,
 
-
: <math>
 
-
x_n = {F_n-A_n\beta_n \over C_n+A_n\alpha_n} \,\!
 
-
</math>
 
-
 
-
== Числовой пример ==
 
-
Вычислим по формулам прямоугольников и трапеций при <tex>n=2</tex> интеграл
 
-
 
-
{{ eqno | 14 }}
 
-
<p align="center"><tex>I=\int_{0}^{\pi/2}{\sin(x)dx} = 1</tex></p>
 
-
 
-
В данном случае
 
-
 
-
 
-
<p align="center"><tex>P_2=\frac{\pi}{4}(\sin(\frac{\pi}{8})+\sin(\frac{3\pi}{8}))=1.026172</tex></p>
 
-
 
-
<p align="center"><tex>T_2=\frac{\pi}{4}(\frac{1}{2}\sin(0)+\sin(\frac{\pi}{4})+\frac{1}{2}\sin(\frac{\pi}{2}))=0.948059</tex></p>
 
-
 
-
Зная точный ответ (14), найдем погрешности
 
-
 
-
{{ eqno | 15 }}
 
-
<p align="center"><tex>\alpha_2=-0.026172,\beta_2=0.051941</tex></p>
 
-
 
-
Вторая производная функции <tex>\sin(x)</tex> на отрезке <tex>[0,\pi/2]</tex> отрицательна, ее модуль не превышает единицы: <tex>M_2=1</tex>. Величина погрешностей (15) удовлетворяет неравенствам (9) и (13):
 
-
 
-
<p align="center"><tex>|\alpha_2|\le \frac{1}{96}(\frac{\pi}{2})^3<0.041,|\beta_2|\le \frac{1}{48}(\frac{\pi}{2})^3<0.081</tex></p>
 
-
 
-
== Рекомендации программисту ==
 
-
 
-
=== Автоматический выбор шага интегрирования ===
 
-
 
-
Величина погрешности численного интегрирования зависит как от шага сетки <tex>h</tex>, так и от гладкости подынтегральной функции <tex>f(x)</tex>. Например, в оценку (11), наряду с <tex>h</tex>, входит величина
 
-
 
-
<p align="center"><tex>M_{2,i}=\underset{x\in [x_{i-1},x_i]}{max}|f''(x)|,</tex></p>
 
-
 
-
которая может сильно меняться от точки к точке и, вообще говоря, заранее неизвестна. Если величина погрешности велика, то ее можно уменьшить путем измельчения сетки на данном отрезке <tex>[x_{i-1},x_i]</tex>. Для этого прежде всего надо уметь апостериорно, т.е. после проведения расчета, оценивать погрешность.
 
-
 
-
Апостериорную оценку погрешности можно осуществить ''методом Рунге''. Пусть какая-то квадратурная формула имеет на частичном отрезке порядок точности <tex>m</tex>, т.е. <tex>I_i-I_{h,i}\approx c_i h_i^m</tex>. Тогда
 
-
 
-
<p align="center"><tex>I_i-I_{h/2,i}\approx c_i (\frac{h_i}{2})^m,</tex></p>
 
-
 
-
откуда получим
 
-
 
-
{{ eqno | 16 }}
 
-
<p align="center"><tex>I_i-I_{h,i}\approx 2^m (I_i-I_{h/2,i}),</tex></p>
 
-
 
-
{{ eqno | 17 }}
 
-
<p align="center"><tex>I_i-I_{h/2,i}\approx \frac{I_{h/2,i}-I_{h,i}}{2^m-1}</tex></p>
 
-
 
-
Возможность апостериорно оценивать погрешность позволяет вычислять интеграл (1) с заданной точностью <tex>\epsilon >0</tex> путем автоматического выбора шага интегрирования <tex>h_i</tex>. Пусть используется составная квадратурная формула
 
-
 
-
<p align="center"><tex>I\approx I_h=\sum_{i=1}^N{I_{h,i}}</tex></p>
 
-
 
-
где <tex>I_{h,i}</tex> - квадратурная сумма на частичном отрезке, причем на каждом частичном отрезке используется одна и та же квадратурная формула (например, формула трапеций). Проведем на каждом частичном отрезке <tex>[x_{i-1},x_i]</tex> все вычисления дважды, один раз - с шагом <tex>h_i</tex> и второй раз - с шагом <tex>0.5h_i</tex> и оценим погрешность по правилу Рунге (17).
 
-
 
-
Если для заданного <tex>\epsilon >0</tex> будут выполняться неравенства
 
-
 
-
{{ eqno | 18 }}
 
-
<p align="center"><tex>|I_i-I_{h/2,i}|\approx \frac{|I_{h/2,i}-I_{h,i}|}{2^m-1} \le \frac{\epsilon h_i}{b-a},i=1,2,...,N,</tex></p>
 
-
 
-
то получим
 
-
 
-
<p align="center"><tex>|I-I_h/2|\le \frac{\epsilon}{b-a}\sum_{i=1}^N{h,i}=\epsilon,</tex></p>
 
-
 
-
т.е. будет достигнута заданная точность <tex>\epsilon</tex>.
 
-
 
-
Если же на каком-то из частичных отрезков оценка (18) не будет выполняться, то шаг на этом отрезке надо измельчить еще в два раза и снова оценить погрешность. Измельчение сетки на данном отрезке следует проводить до тех пор, пока не будет достигнута оценка вида (18). Заметим, что для некоторой функции <tex>f(x)</tex> такое измельчение может продолжаться слишком долго. Поэтому в соответствующей программе следует предусмотреть ограничение сверху на число измельчений,а также вожможность увеличения <tex>\epsilon</tex>.
 
-
 
-
Таким образом, автоматический выбор шага интегрирования приводит к тому, что интегрирование ведется с крупным шагом на участках плавного изменения функции <tex>f(x)</tex> и с мелким шагом - на участках быстрого изменения <tex>f(x)</tex>. Это позволяет при заданной точности <tex>\epsilon</tex> уменьшить количество вычислений значений <tex>f(x)</tex> по сравнению с расчетом на сетке с постоянным шагом. Подчеркнем, что для нахождения сумм <tex>I_{h/2,i}</tex> не надо пересчитывать значения <tex>f(x)</tex> во всех узлах, достаточно вычислять <tex>f(x)</tex> только в новых узлах.
 
-
 
-
== Заключение ==
 
-
 
-
== Список литературы ==
 
-
 
-
* ''А.А.Самарский, А.В.Гулин.''&nbsp; Численные методы М.: Наука, 1989.
 
-
* ''А.А.Самарский.''&nbsp; Введение в численные методы М.: Наука, 1982.
 
-
 
-
{{stub}}
 
-
[[Категория:Численное интегрирование]]
 

Текущая версия

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