объясните на пальцах метод прогонки (3-диаг. матр.)

[cf2009]

Дано:
8 пар значений x и y.
x[0]; ...; x[7]; //упорядочены по возрастанию
y[0]; ...; y[7].

Формулы:
$cubicspline(t):=a_i+b_i*(t-x_i_-_1)+c_i*(t-x_i_-_1)^2+d_i*(t-x_i_-_1)^3$;

$i:=1..7$
$h_i:=x_i-x_i_-_1$


$c_1:=0; c_7_+_1:=0$ //естественный сплайн
$i:=2..7$
$h_i_-_1*c_i_-_1+2(h_i_-_1+h_i)*c_i+h_i*c_i_+_1=3[\frac{y_i-y_i_-_1} {h_i}-\frac {y_i_-_1-y_i_-_2} {h_i_-_1}]$


Объясните, пожалуйста, на пальцах, как найти неизвестные $c_i$ на примере $c_1$; $c_7$ и какого-нибудь промежуточного (для особо сообразительных) методом прогонки трёхдиагональной матрицы.

[мат-ламер]

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

[TOTAL]

мат-ламер в сообщении #225471 писал(а):

Вы уверены, что тут получается трёхдиагональная матрица?

Он выписал систему, там три диагонали (пропущен множитель $c_i$ перед $2(h_i + h_{i-1})$)

[cf2009]

мат-ламер в сообщении #225471 писал(а):

задача не для особо сообразительных, а для компьютера

Так мне надо и на C++ сделать, и в mathcad, чтобы преподше показать это для сравнения.

[TOTAL]

Что в мотоде трехточечной прогонки непонятно?

[мат-ламер]

В какой-то книге по сплайнам (возможно, Завьялова и др.) в конце было дано описание метода прогонки. Но если непонятно, то можно представить матрицу в виде произведения двудиагональной и транспонированной к ней (метод Холецкого).

[TOTAL]

мат-ламер в сообщении #225486 писал(а):

можно представить матрицу в виде произведения двудиагональной и транспонированной к ней (метод Холецкого).

Нельзя представить в виде такого произведения.

[мат-ламер]

В методе Холецкого ещё требуется положительная определённость. Но прогонка тоже, вроде, этого требует (хотя тут я не уверен).

[Утундрий]

ВотЪ

[worm2]

Утундрий в сообщении #225499 писал(а):

ВотЪ

В порядке пустого трёпа:
полистамши забугорные википедии, с удивлением узнал, что оне называют метод прогонки Tridiagonal matrix algorithm или Thomas algorithm, хотя русская уверяет, что он должен быть наречён Shuttle algorithm. Странно...

[ewert]

мат-ламер в сообщении #225471 писал(а):

Вы уверены, что тут получается трёхдиагональная матрица?

Уверены. Для глобального кубического сплайна система получается ровно трёхдиагональная.

Утундрий в сообщении #225499 писал(а):

ВотЪ

Уфф, накрутили-навертели. Хотя метод прогонки -- это и всего-то навсего обычный метод Гаусса с обратным ходом и без перестановок. Кто учился на 1-м курсе (именно учился, а не просто сдал его) -- моментально напишет рабочие формулы.

[cf2009]

Спасибо за ссылку (и за вашу, и за ту, что на странице по ссылке ), и за оперативность.

Я вот ещё нашёл в разжёванном виде (и блок-схемы, и программы).
("лежала" у меня не там, где остальные книги, поэтому несколько дней её не замечал. Вот так бывает...)

Computing for Numerical Methods Using Visual C++

Pdf (изображение достаточно чёткое, но, например, в текстах программ левые символы - не редкость)
6,080,559 bytes

Providing a bridge between a problem and its solution through visualization, this book covers the most talked about problems currently available.
Presenting a new approach that allows the reader to work by designing C++ programs directly using Windows interface in one book, the text provides ready to run codes.
...

1. Modeling and Simulation
2. Fundamental Tools for Mathematical Computing
3. Numerical Interface Designs
4. Curve Visualization
5. Systems of Linear Equations
6. Nonlinear Equations
7. Interpolation and Approximation
8. Differentiation and Integration
9. Eigenvalues and Eigenvectors
10. Ordinary Differential Equations
11. Partial Differential Equations
Index

* Pub. Date: December 2007

[AKM]

ewert в сообщении #225534 писал(а):

Кто учился на 1-м курсе (именно учился, а не просто сдал его) -- моментально напишет рабочие формулы.

А вот и нет. Бывают и кто именно учился, но тугодум. Или времени много прошло, сноровка потерялась. Или...

[cf2009]

В mathcad всё работает.
для фунцкции $y=x^2$, x - целый, от 0 и больше.

С пропуском x=3:
spline(4)=15.961;
spline(4.5)=20.214;
spline(4.9)=24;
spline(6.5)=42.439.

spline(5)=spline(5) при i=4 и i=5, т. е. склеиваются, что и должно быть.

Для прогонки воспользовался ссылкой "метод прогонки" на странице по ссылке, которую выше привели.

Ещё раз спасибо.

[worm2]

ewert в сообщении #225534 писал(а):

Уфф, накрутили-навертели. Хотя метод прогонки -- это и всего-то навсего обычный метод Гаусса с обратным ходом и без перестановок. Кто учился на 1-м курсе (именно учился, а не просто сдал его) -- моментально напишет рабочие формулы.

Вот я сейчас попробовал написать - формулы разные получаются. Сравните:

Метод Гаусса:

$$\left( \begin{array}{ccc} 3&1&0\\ 1&3&1\\ 0&1&3 \end{array} \right) \left( \begin{array}{c} x_1\\ x_2\\ x_3 \end{array} \right)= \left( \begin{array}{c} 1\\ 1\\ 1 \end{array} \right)$$

$$\left( \begin{array}{ccc} 3&1&0\\ 0&8/3&1\\ 0&0&21/8 \end{array} \right) \left( \begin{array}{c} x_1\\ x_2\\ x_3 \end{array} \right)= \left( \begin{array}{c} 1\\ 2/3\\ 3/4 \end{array} \right)$$

$$\begin{array}{rcl} x_3&=&\frac{3/4}{21/8}=\frac 2 7\\ x_2&=&\frac 3 8 \left(\frac 2 3 - \frac 2 7\right)=\frac 1 7\\ x_1&=&\frac 1 3 \left(1 - \frac 1 7\right) = \frac 2 7 \end{array}$$

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

$$\alpha_2=-\frac 1 3,\,\beta_2=\frac 1 3$$

(в прямом ходе метода Гаусса этих дробей не видать)

$$\alpha_3 = -\frac 3 8,\,\beta_3 = \frac 1 4$$

(в методе Гаусса этих дроби появляются только на обратном ходе, и то неявно).

$$x_3=\frac{3/4}{21/8}=\frac 2 7$$

(совпадает)

$$x_2=-\frac 3 8\cdot \frac 2 7+\frac 1 4$$

(совпадает, но только если раскрыть скобки, т.е. формально разные формулы)

$$x_1=-\frac 1 3\cdot\frac 1 7+\frac 1 3$$

(аналогично).


При вычислениях на компьютере погрешности округления будут накапливаться по-разному.