|
|
| Строка 1: |
Строка 1: |
| - | == Введение ==
| |
| | | | |
| - | === Постановка математической задачи ===
| |
| - |
| |
| - | Одной из значения функции <tex>y(x)</tex>, равные <tex>y(x_0)=y_0,\cdots,y(x_i)=y_i,\cdots,y(x_n)=y_n</tex>. Требуется построить ''иносновных задач численного анализа является задача об интерполяции функций.
| |
| - | Пусть на отрезке <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>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>x</tex> соответствует вектору <tex>\{c_i\}</tex>, вектор <tex>F</tex> поэлементно равен правой части уравнения {{eqref|6}}, а матрица <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},</tex></p>
| |
| - |
| |
| - | где <tex>A_i=h_i, i=2, \cdots, n, B_i = h_{i+1}, i=1, \cdots, n-1</tex> и <tex>C_i=2(h_i+h_{i+1}), i =1, \cdots, n</tex>.
| |
| - |
| |
| - | === Метод прогонки ===
| |
| - |
| |
| - | '''Метод прогонки''', основан на предположении, что искомые неизвестные связаны рекуррентным соотношением:
| |
| - |
| |
| - | {{ eqno | 8 }}
| |
| - | <p align="center"><tex>x_i = \alpha_{i+1}x_{i+1} + \beta_{i+1}\, i=1,\cdots,n-1</tex></p>
| |
| - |
| |
| - | Используя это соотношение, выразим <tex>x_{i-1}</tex> и <tex>x_i</tex> через <tex>x_{i+1}</tex> и подставим в i-e уравнение:
| |
| - | <p align="center"><tex>\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</tex></p>,
| |
| - |
| |
| - | где <tex>F_i</tex> - правая часть i-го уравнения. Это соотношение будет выполняться независимо от решения, если потребовать
| |
| - | <p align="center"><tex>A_i\alpha_i\alpha_{i+1} + C_i\alpha_{i+1} + B_i = 0</tex></p>
| |
| - | <p align="center"><tex>A_i\alpha_i\beta_{i+1} + A_i\beta_i + C_i\beta_{i+1} - F_i = 0</tex></p>
| |
| - | Отсюда следует:
| |
| - | <p align="center"><tex>\alpha_{i+1} = {-B_i \over A_i\alpha_i + C_i}\</tex></p>
| |
| - | <p align="center"><tex>\beta_{i+1} = {F_i - A_i\beta_i \over A_i\alpha_i + C_i}</tex></p>
| |
| - | Из первого уравнения получим:
| |
| - | <p align="center"><tex>\alpha_2 = {-B_1 \over C_1}</tex></p>
| |
| - | <p align="center"><tex>\beta_2 = {F_1 \over C_1}</tex></p>
| |
| - | После нахождения прогоночных коэффициентов <tex>\alpha</tex> и <tex>\beta</tex>, используя уравнение (1), получим решение системы. При этом,
| |
| - | <p align="center"><tex>x_n = {F_n-A_n\beta_n \over C_n+A_n\alpha_n} </tex></p>
| |
| - |
| |
| - | == Числовой пример ==
| |
| - | Построим интерполянту для для функции <tex>f</tex>, заданной следующим образом:
| |
| - | [[Изображение:Interpolation_data.png|thumb|300px|Вводные значения для задачи интерполяции ]]
| |
| - |
| |
| - | {| class="wikitable"
| |
| - | |-
| |
| - | ! <tex>x</tex>
| |
| - | ! <tex>f(x)</tex>
| |
| - | |-
| |
| - | | 1
| |
| - | | 1.0002
| |
| - | |-
| |
| - | | 2
| |
| - | | 1.0341
| |
| - | |-
| |
| - | | 3
| |
| - | | 0.6
| |
| - | |-
| |
| - | | 4
| |
| - | | 0.40105
| |
| - | |-
| |
| - | | 5
| |
| - | | 0.1
| |
| - | |-
| |
| - | | 6
| |
| - | | 0.23975
| |
| - | |}
| |
| - |
| |
| - |
| |
| - |
| |
| - | == Рекомендации программисту ==
| |
| - |
| |
| - |
| |
| - | == Заключение ==
| |
| - |
| |
| - | == Список литературы ==
| |
| - |
| |
| - | * ''А.А.Самарский, А.В.Гулин.'' Численные методы М.: Наука, 1989.
| |
| - | * ''А.А.Самарский.'' Введение в численные методы М.: Наука, 1982.
| |
| - | * ''Костомаров Д.П., Фаворский А.П.'' Вводные лекции по численным методам
| |
| - |
| |
| - | {{stub}}
| |
| - | [[Категория:Численное интегрирование]]
| |
