|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Alexandr Brezgin 2:5010/220.80 13 Mar 2002 02:10:00
To : Pavel Timofeev
Subject : сплайны
--------------------------------------------------------------------------------
11 Mar 02 19:25, Pavel Timofeev -> All:
PT> "Разработать стандартную процедуру построения кубического
PT> интерполяционного сплайна". Что такое сплайн и как это делать я
PT> понятия не имею :( (кривая?)
Это кривая проходящая через все точки, между точками она описывается
кубическим уравнением q = k3*x^3 + k2*x^2 + k1*x + k0, и имеет минимальную
потенциальную энергию деформированного тела (надо понимать минимум
интеграла модуля второй производной).
В кубическом уравнении 4 неизвестных параметра.
Итак, дано n точек => надо найти (n-1)*4 неизвестных параметров.
Имеем:
1. уравнения кривых (они должны проходить через точки, левая и правая)
(n-1)*2
2. уравнения средних точек (в точках 1 и 2 производные соседних кривых равны)
(n-2)*2
Итого: 4*n-6, а надо 4*n-4.
Остались крайние точки, т.е. 4 параметра, из них 2 независимых.
Вот руля этими 2 независимыми мы и ищем сабж.
Задаем в начальной точке первую и вторую производную и тем самым полностью
определяем кривую и получаем ее оценку, далее применив к этой функции
двумерный поиск экстремума(минимума) найдем (будем надеятся) сплайн.
PT> Подскажите, пожалуйста, из какой это вообще области?
Аппроксимация.
PT> И как это примерно делать?
Стояла аналогичная задача, но была упрощена. Сплайном считалась кривая
имеющая в крайних точках нулевую вторую производную.
Т.к. параметры были заданы в разных точках, то пришлось решать САУ .
--- task_#3.c
#include <stdio.h>
#include <math.h>
#include <conio.h>
#include <graphics.h>
#define ELSIZE 5 /* аргумент, значение, три производных */
/* расчет параметров кривой 3 порядка, ее оценка */
double calc_line3(double q[][ELSIZE], int n, double init)
{
int i;
double dt;
q[0][2]=init;
q[0][3]=0;
for (i=0; i < (n-1); i++) {
dt = q[i+1][0] - q[i][0];
q[i][4] = 6 * (q[i+1][1] - q[i][1] - q[i][2]*dt - q[i][3]*dt*dt/2) /
(dt*dt*dt);
q[i+1][2] = q[i][2] + q[i][3]*dt + q[i][4]*dt*dt/2;
q[i+1][3] = q[i][3] + q[i][4]*dt;
}
return q[n-1][3];
}
/* расчет сплайнов 3 порядка, выбор кривой, решение САУ методом хорд */
double calc_spline3(double q[][ELSIZE], int n, double eps)
{
double a= -300., b= +300., c, fa, fb, fc;
fa = calc_line3(q, n, a);
fb = calc_line3(q, n, b);
if (fa*fb > 0) return 2*eps; /* методу хорд необходим верный начальный
интервал (a,b) */
do {
c = a - fa * (b-a) / (fb-fa);
fc = calc_line3(q, n, c);
if (fa*fc > 0) {a=c;fa=fc;}
else {b=c;fb=fc;}
} while(fabs(fc) >= eps);
return fc;
}
/* расчет точки сплайна */
double get_value3(double q[][ELSIZE], int n, double x)
{
int i;
double dt;
/* выбор участка */
for (i=0; (i<(n-1)) && !((x>q[i][0]) && (x<q[i+1][0])); i++);
if (i == (n-1)) return 777.; /* гаданием (экстраполяцией) не занимаемся */
dt = x - q[i][0];
return (q[i][1] + q[i][2]*dt + q[i][3]*dt*dt/2 + q[i][4]*dt*dt*dt/6);
}
/* Программа */
int main()
{
int i, driver=VGA, mode=VGAHI;
/* отсортированные по аргументу точки */
double points[4][ELSIZE] = { {1., -7., 0., 0., 0.},
{3., 5., 0., 0., 0.},
{4., 8., 0., 0., 0.},
{6., 14., 0., 0., 0.} };
initgraph(&driver,&mode,"");
printf("\n Аппроксимация сплайнами."); /* Приветствие */
/* расчет и выдача результата с использованием аппроксимирующей ф-ии и
исходных данных */
calc_spline3(points, 4, 0.001); /* расчет параметров сплайна */
for (i=0; i<600; i++) putpixel(i, 240-10*get_value3(points, 4, i/100.), 1);
for (i=0; i<4; i++) putpixel(100*points[i][0], 240-10*points[i][1], 15);
/* no comments :-) */
printf("\n Посмотрели результат? Теперь нажмите любую клавишу...");
getch();
closegraph();
return 0; /* сообщаем ОС об успешном выполнении */
}
---
* Origin: Origin disabled (2:5010/220.80)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
| Тема: |
Автор: |
Дата: |
|
сплайны |
Pavel Timofeev |
11 Mar 2002 20:25:56 |
 Hа: сплайны |
Ђ«ҐЄбҐ© „. |
12 Mar 2002 16:05:00 |
  сплайны |
Alexander Lezin |
12 Mar 2002 23:25:49 |
|
сплайны |
Aleksey Malov |
12 Mar 2002 22:22:10 |
|
сплайны |
Alexandr Brezgin |
13 Mar 2002 02:10:00 |
|
Re: сплайны |
Sergiy Kanilo |
13 Mar 2002 06:09:11 |
 сплайны |
Dmitry Pankov |
13 Mar 2002 15:49:48 |
 Re: сплайны |
Sergiy Kanilo |
13 Mar 2002 19:59:26 |
|
сплайны |
Dmitry Zhadanoff |
13 Mar 2002 09:14:55 |
|
сплайны |
Alexandr Brezgin |
15 Mar 2002 04:42:00 |
|
сплайны |
Dmitry Zhadanoff |
15 Mar 2002 08:55:44 |
|
сплайны |
Alexandr Brezgin |
16 Mar 2002 17:09:00 |
|
сплайны |
Yuri Y. Lesnichenko |
14 Mar 2002 12:15:16 |
|
Re: сплайны |
Sergiy Kanilo |
15 Mar 2002 08:42:06 |
|
Re: сплайны |
Max Vikulov |
12 Mar 2002 23:08:28 |
|
сплайны |
Ilia Kantor |
12 Mar 2002 22:12:58 |
|
сплайны |
Stanislav Shwartsman |
13 Mar 2002 22:34:16 |
|
сплайны |
Ilia Kantor |
14 Mar 2002 02:28:16 |
|
Re: сплайны |
Sergiy Kanilo |
14 Mar 2002 02:26:42 |
|
сплайны |
Ilia Kantor |
15 Mar 2002 21:55:40 |
|
сплайны |
Yuri Y. Lesnichenko |
14 Mar 2002 12:19:14 |
|
Re: сплайны |
Sergiy Kanilo |
15 Mar 2002 08:44:10 |
|
сплайны |
Alexander Lezin |
16 Mar 2002 01:06:48 |
|
Re: сплайны |
Sergiy Kanilo |
17 Mar 2002 02:05:00 |
|
сплайны |
Alexander Lezin |
17 Mar 2002 23:29:13 |
|
сплайны |
Yuri Y. Lesnichenko |
16 Mar 2002 21:53:49 |
|
Re: сплайны |
Sergiy Kanilo |
29 Mar 2002 04:10:00 |
|
Re: сплайны |
Kirill Uvaev |
29 Mar 2002 15:13:54 |
|
|
