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

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

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

Версия 11:06, 13 октября 2008

Содержание

1 Введение
- 1.1 Постановка математической задачи
2 Изложение метода
- 2.1 Метод прогонки
3 Числовой пример
4 Рекомендации программисту
- 4.1 Автоматический выбор шага интегрирования
5 Заключение
6 Список литературы

Введение

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

Одной из основных задач численного анализа является задача об интерполяции функций. Пусть на отрезке $a\le \x\le \b$ задана сетка $\omega=\{x_i:x_0=a<x_1<\cdots<x_i<\cdots<x_n=b\}$ и в её узлах заданы значения функции $y(x)$ , равные $y(x_0)=y_0,\cdots,y(x_i)=y_i,\cdots,y(x_n)=y_n$ . Требуется построить интерполянту — функцию $f(x)$ , совпадающую с функцией $y(x)$ в узлах сетки:

( 1 )

$f(x_i)=y_i, i=0,1,\cdots,n.$

Основная цель интерполяции — получить быстрый (экономичный) алгоритм вычисления значений $f(x)$ для значений $x$ , не содержащихся в таблице данных.

Интерполируюшие функции $f(x)$ , как правило строятся в виде линейных комбинаций некоторых элементарных функций:

$f(x)=\sum_{k=0}^N {c_k\Phi_k(x)},$

где $\{\Phi_k(x)\}$ — фиксированный линейно независимые функции, $c_0, c_1, \cdots, c_n$ — не определенные пока коэффициенты.

Из условия (1) получаем систему из $n+1$ уравнений относительно коэффициентов $\{c_k\}$ :

$\sum_{k=0}^N {c_k\Phi_k(x_i)}=y_i, i=0,1,\cdots,n.$

Предположим, что система функций $\Phi_k(x)$ такова, что при любом выборе узлов $a<x_1<\cdots<x_i<\cdots<x_n=b$ отличен от нуля определитель системы:

$\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)\\ \hdots{4} \\\Phi_0(x_n) & \Phi_1(x_n) & \cdots & \Phi_n(x_n)\end{vmatrix}$ .

Тогда по заданным $y_i (i=1,\cdots, n)$ однозначно определяются коэффициенты $c_k (k=1,\cdots, n)$ .

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

Интерполяция кубическими сплайнами является частным случаем кусочно-полиномиальной интерполцией. В этом специальном случае между любыми двумя соседними узлами функция интерполируется кубическим полиномом. его коэффициенты на каждом интервале определяются из условий сопряжения в узлах:

$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.$

Кроме того, на границе при $x=x_0$ и $x=x_n$ ставятся условия

( 2 )

$f''(x_0)=0, f''(x_n)=0.$

Будем искать кубический полином в виде

( 3 )

$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.$

Из условия $f_i=y_i$ имеем

( 4 )

$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.$

Вычислим производные:

$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,$

и потребуем их непрерывности при $x=x_i$ :

( 5 )

$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.$

Общее число неизвестных коэффициентов, очевидно, равно $4n$ , число уравнений (4) и (5) равно $4n-2$ . Недостающие два уравнения получаем из условия (2) при $x=x_0$ и $x=x_n$ :

$c_1=0, c_n+3d_nh_n=0.$

Выражение из (5) $d_i=\frac{c_{i+1}-c_i}{3h_i}$ , подставляя это выражение в (4) и исключая $a_i=y_{i-1}$ , получим

$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,.$

Подставив теперь выражения для $b_i, b_{i+1}$ и $d_i$ в первую формулу (5), после несложных преобразований получаем для определения $c_i$ разностное уравнение второго порядка

( 6 )

$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.$

С краевыми условиями

( 7 )

$c_1=0, c_{n+1}=0.$

Условие $c_{n+1}=0$ эквивалентно условию $c_n+3d_nh_n=0$ и уравнению $c_{i+1} = c_i+d_ih_i$ . Разностное уравнение (6) с условиями (7) можно решить методом прогонки, представив в виде системы линейных алгебраических уравнений вида $~A*x=F$ , где

Метод прогонки

Трёхдиагональной матрицей называют матрицу следующего вида:

<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>     , где <math>~i=1,n-1</math>                                     (1)

Используя это соотношение, выразим x_i-1 и x_i через x_i+1 и подставим в 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_i - правая часть 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>

Числовой пример

Вычислим по формулам прямоугольников и трапеций при $n=2$ интеграл

( 14 )

$I=\int_{0}^{\pi/2}{\sin(x)dx} = 1$

В данном случае

$P_2=\frac{\pi}{4}(\sin(\frac{\pi}{8})+\sin(\frac{3\pi}{8}))=1.026172$

$T_2=\frac{\pi}{4}(\frac{1}{2}\sin(0)+\sin(\frac{\pi}{4})+\frac{1}{2}\sin(\frac{\pi}{2}))=0.948059$

Зная точный ответ (14), найдем погрешности

( 15 )

$\alpha_2=-0.026172,\beta_2=0.051941$

Вторая производная функции $\sin(x)$ на отрезке $[0,\pi/2]$ отрицательна, ее модуль не превышает единицы: $M_2=1$ . Величина погрешностей (15) удовлетворяет неравенствам (9) и (13):

$|\alpha_2|\le \frac{1}{96}(\frac{\pi}{2})^3<0.041,|\beta_2|\le \frac{1}{48}(\frac{\pi}{2})^3<0.081$

Рекомендации программисту

Автоматический выбор шага интегрирования

Величина погрешности численного интегрирования зависит как от шага сетки $h$ , так и от гладкости подынтегральной функции $f(x)$ . Например, в оценку (11), наряду с $h$ , входит величина

$M_{2,i}=\underset{x\in [x_{i-1},x_i]}{max}|f''(x)|,$

которая может сильно меняться от точки к точке и, вообще говоря, заранее неизвестна. Если величина погрешности велика, то ее можно уменьшить путем измельчения сетки на данном отрезке $[x_{i-1},x_i]$ . Для этого прежде всего надо уметь апостериорно, т.е. после проведения расчета, оценивать погрешность.

Апостериорную оценку погрешности можно осуществить методом Рунге. Пусть какая-то квадратурная формула имеет на частичном отрезке порядок точности $m$ , т.е. $I_i-I_{h,i}\approx c_i h_i^m$ . Тогда

$I_i-I_{h/2,i}\approx c_i (\frac{h_i}{2})^m,$

откуда получим

( 16 )

$I_i-I_{h,i}\approx 2^m (I_i-I_{h/2,i}),$

( 17 )

$I_i-I_{h/2,i}\approx \frac{I_{h/2,i}-I_{h,i}}{2^m-1}$

Возможность апостериорно оценивать погрешность позволяет вычислять интеграл (1) с заданной точностью $\epsilon >0$ путем автоматического выбора шага интегрирования $h_i$ . Пусть используется составная квадратурная формула

$I\approx I_h=\sum_{i=1}^N{I_{h,i}}$

где $I_{h,i}$ - квадратурная сумма на частичном отрезке, причем на каждом частичном отрезке используется одна и та же квадратурная формула (например, формула трапеций). Проведем на каждом частичном отрезке $[x_{i-1},x_i]$ все вычисления дважды, один раз - с шагом $h_i$ и второй раз - с шагом $0.5h_i$ и оценим погрешность по правилу Рунге (17).

Если для заданного $\epsilon >0$ будут выполняться неравенства

( 18 )

$|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,$

то получим

$|I-I_h/2|\le \frac{\epsilon}{b-a}\sum_{i=1}^N{h,i}=\epsilon,$

т.е. будет достигнута заданная точность $\epsilon$ .

Если же на каком-то из частичных отрезков оценка (18) не будет выполняться, то шаг на этом отрезке надо измельчить еще в два раза и снова оценить погрешность. Измельчение сетки на данном отрезке следует проводить до тех пор, пока не будет достигнута оценка вида (18). Заметим, что для некоторой функции $f(x)$ такое измельчение может продолжаться слишком долго. Поэтому в соответствующей программе следует предусмотреть ограничение сверху на число измельчений,а также вожможность увеличения $\epsilon$ .

Таким образом, автоматический выбор шага интегрирования приводит к тому, что интегрирование ведется с крупным шагом на участках плавного изменения функции $f(x)$ и с мелким шагом - на участках быстрого изменения $f(x)$ . Это позволяет при заданной точности $\epsilon$ уменьшить количество вычислений значений $f(x)$ по сравнению с расчетом на сетке с постоянным шагом. Подчеркнем, что для нахождения сумм $I_{h/2,i}$ не надо пересчитывать значения $f(x)$ во всех узлах, достаточно вычислять $f(x)$ только в новых узлах.

Заключение

Список литературы

А.А.Самарский, А.В.Гулин. Численные методы М.: Наука, 1989.
А.А.Самарский. Введение в численные методы М.: Наука, 1982.

Это незавершённая статья. Вы поможете проекту, исправив и дополнив её.

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:Lr2k/%D0%9F%D0%B5%D1%81%D0%BE%D1%87%D0%BD%D0%B8%D1%86%D0%B0»

Категории: Незавершённые статьи | Численное интегрирование

@@ Строка 19: / Строка 19: @@
 Предположим, что система функций <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)\\ \hdotsfor{4}  \\\Phi_0(x_n) & \Phi_1(x_n) & \cdots & \Phi_n(x_n)\end{vmatrix}</tex>.</p>
+<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)\\ \hdots{4}  \\\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>.
@@ Строка 25: / Строка 25: @@
 == Изложение метода ==
 Интерполяция кубическими сплайнами является частным случаем кусочно-полиномиальной интерполцией. В этом специальном случае между любыми двумя соседними узлами функция интерполируется кубическим полиномом. его коэффициенты на каждом интервале определяются из условий сопряжения в узлах:
-<p align="center"><tex>\begin{multline}f_i=y_i,
+<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.\end{multiline}</tex></p>
+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> ставятся условия
@@ Строка 37: / Строка 37: @@
 Будем искать кубический полином в виде
-{{ eqno | 2 }}
+{{ eqno | 3 }}
-<p align="center"><tex>f''(x_0)=0, f''(x_n)=0.</tex></p>
+<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},
-[[Изображение:Integral_rect.png|thumb|200px|Рис.2]]
+f(x_i)=a_i+b_ih_i+c_ih_i^2+d_ih_i^3=y_i,
-Заменим интеграл {{eqref|3}} выражением <tex>f(x_{i-1/2})h</tex>, где <tex>x_{i-1/2}=x_{i}-0.5h.</tex>
+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>\int_{x_{i-1}}^{x_i}{f(x)dx}\approx f(x_{i-1/2})h,</tex></p>
+<p align="center"><tex>b_{i+1}=b_i+2c_ih_i + 3d_ih_i^2,
-которая называется ''формулой прямоугольников на частичном отрезке'' <tex>[x_{i-1},x_i].</tex>
+c_{i+1}=c_i+3d_ih_i, i=1, 2, \cdots, n-1.</tex></p>
-Погрешность метода {{eqref|5}} определяется величиной
+Общее число неизвестных коэффициентов, очевидно, равно <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>
-<p align="center"><tex>\psi_{i}=\int_{x_{i-1}}^{x_i}{f(x)dx}-f(x_{i-1/2})h</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,
-которую легко оценить с помощью формулы Тейлора. Действительно, запишем <tex>\psi_{i}</tex> в виде
+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>\psi_{i}=\int_{x_{i-1}}^{x_i}{(f(x)-f(x_{i-1/2}))dx}</tex></p>
+<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>
-и воспользуемся разложением
-<p align="center"><tex>f(x)=f(x_{i-1/2})+(x-x_{i-1/2})f'(x_{i-1/2})+\frac{(x-x_{i-1/2})^2}{2}f''(\xi),</tex></p>
-где <tex>\xi_i=\xi_i(x)\in [x_{i-1},x_i]</tex>. Тогда из {{eqref|6}} получим
-<p align="center"><tex>\psi_{i}=\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}f''(\xi_i)dx}</tex></p>
-Обозначая <tex>M_{2,i}=\underset{x\in [x_{i-1},x_i]}{max}|f''(x)|</tex>, оценим <tex>\psi_i</tex> следующим образом:
-<p align="center"><tex>|\psi_i|\le M_{2,i} \int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}dx}=\frac{h^3}{24}M_{2,i}</tex></p>
-Таким образом, для погрешности формулы прямоугольников на частичном отрезке справедлива оценка
+С краевыми условиями
 {{ eqno | 7 }}
-<p align="center"><tex>|\psi_i|\le \frac{h^3}{24}M_{2,i}</tex></p>
+<p align="center"><tex>c_1=0, c_{n+1}=0.</tex></p>
-т.е. формула имеет погрешность <tex>O(h^3)</tex> при <tex>h\rightarrow0</tex>.
-Заметим,что оценка (7) является неулучшаемой, т.е. существует функция <tex>f(x)</tex>, для которой (7) выполняется со знаком равенства. Действительно, для <tex>f(x)=(x-x_{i-1/2})^2</tex> имеем <tex>M_{2,i}=2, f(x_{i-1/2})=0</tex> и
-<p align="center"><tex>\int_{x_{i-1}}^{x_i}{f(x)dx}-f(x_{i-1/2})h=\frac{h^3}{24}M_{2,i}</tex></p>
-Суммируя равенства (5) по <tex>i</tex> от <tex>1</tex> до <tex>N</tex>, получим ''составную формулу прямоугольников''
-{{ eqno | 8 }}
-<p align="center"><tex>\int_{a}^{b}{f(x)dx}\approx \sum_{i=1}^N{f(x_{i-1/2})h}</tex></p>
-Погрешность этой формулы
-<p align="center"><tex>\Psi=\int_{a}^{b}{f(x)dx}-\sum_{i=1}^N{f(x_{i-1/2})h}</tex></p>
-равна сумме погрешностей по всем частичным отрезкам,
-<p align="center"><tex>\Psi=\sum_{i=1}^N{\psi_i}=\sum_{i=1}^N{\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1/2})^2}{2}f''(\xi_i)dx}}</tex></p>
-Отсюда, обозначая <tex>M_2=\underset{x\in [a,b]}{max}|f''(x)|</tex>, получим
-{{ eqno | 9 }}
-<p align="center"><tex>|\Psi|\le\frac{M_2Nh^3}{24}=\frac{h^2(b-a)}{24}M_2</tex></p>
-т.е. погрешность формулы прямоугольников на всем отрезке есть велицина <tex>O(h^2)</tex>.
-В этом случае говорят, что квадратурная формула имеет ''второй порядок точнотси''.
-=== Формула трапеций ===
-[[Изображение:Integral_trap.png|thumb|200px|Рис.3]]
-На частичном отрезке эта формула имеет вид
-{{ eqno | 10 }}
-<p align="center"><tex>\int_{x_{i-1}}^{x_i}{f(x)dx}\approx \frac{f(x_{i-1})+f(x_i)}{2}h</tex></p>
-и получается путем замены подынтегральной функции <tex>f(x)</tex> интерполяционным многочленом первой степени,постоенным по узлам <tex>x_{i-1},x_i</tex>, т.е. функцией
-<p align="center"><tex>L_{1,i}(x)=\frac{1}{h}((x-x_{i-1})f(x_i)-(x-x_i)f(x_{i-1})).</tex></p>
-Для оценки погрешности достаточно вспомнить,что
-<p align="center"><tex>f(x)-L_{1,i}(x)=\frac{(x-x_{i-1})(x-x_i)}{2}f''(\xi_i(x)).</tex></p>
-Отсюда получим
-<p align="center"><tex>\psi_i=\int_{x_{i-1}}^{x_i}{f(x)dx}-\frac{f(x_{i-1})+f(x_i)}{2}h=\int_{x_{i-1}}^{x_i}{(f(x)-L_{1,i}(x))dx}=\int_{x_{i-1}}^{x_i}{\frac{(x-x_{i-1})(x-x_i)}{2}f''(\xi_i(x))dx}</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>, где
-{{ eqno | 11 }}
-<p align="center"><tex>|\psi_i|\le \frac{M_{2,i}h^3}{12}</tex></p>
+=== Метод прогонки ===
-Оценка (11) неулучшаема, так как в ней достигается равенство, например, для <tex>f(x)=(x-x_i)^2</tex>.
+'''Трёхдиагональной матрицей''' называют [[Матрица (математика)|матрицу]] следующего вида:
-''Составная формула трапеций'' имеет вид
+: <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>.
-{{ eqno | 12 }}
+[[Система линейных алгебраических уравнений|Системы линейных алгебраических уравнений]] с такими матрицами встречаются при решении многих [[задача|задач]] математики и физики. Краевые условия <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>.
-<p align="center"><tex>\int_{a}^{b}{f(x)dx}\approx \sum_{i=1}^N{\frac{f(x_{i-1})+f(x_i)}{2}h}=h(0.5f_0+f_1+...+f_{N-1}+0.5f_N),</tex></p>
-где <tex>f_i=f(x_i),i=0,1,...,N,hN=b-a</tex>.
+Для решения систем вида <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>
-{{ eqno | 13 }}
-<p align="center"><tex>|\Psi|\le \frac{h^2(b-a)}{12}M_2,M_2=\underset{x\in [a,b]}{max}|f''(x)|</tex></p>
-Таким образом, формула трапеций имеет, так же как и формула прямоугольников, второй порядок точности,<tex>\Psi=O(h^2)</tex>, но ее погрешность оценивается величиной в два раза большей.
+: <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>
 == Числовой пример ==

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

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

Версия 11:06, 13 октября 2008

Содержание

Введение

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

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

Метод прогонки

Числовой пример

Рекомендации программисту

Автоматический выбор шага интегрирования

Заключение

Список литературы

Просмотры

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

Навигация

Поиск

Инструменты