23.2 Алгоритм «прогонка» для решения системы линейных уравнений с диагональным преобладанием.

Рассмотрим для определенности систему линейных уравнений для непериодического сплайна:

2M₁+M₂=C₁

aM₁+2M₂ +b₂M₃=C₂

...

a_n-1 ∙M_n-2+2M_n-1+b_n-1 ∙M_n=C_n-1

M_n-1+2M_n=C_n

Разрешим 1-ое уравнение относительно M₁:

M₁=p₁∙M₂+q₁ p₁₌ q₁=

Подставим M₁ во 2-ое уравнение и выразим M₂:

M₂= ∙ M₃+

p₂= q₂=

M₂= p₂∙ M₃+q₂

Продолжая процесс исключения и подставляя M_i-1= p_i-1∙ M_i+q_i-1 в уравнение

a_i ∙M_i-1+2Mi+b_i ∙M_i+1=C_i получим:

M_i = ∙ M_i+1 + , т.е. p_i и q_i равны:

p_i= _{-рекуррентные формулы для p и q. (1)}

q_i=

Продолжая этот процесс, получим для последнего уравнения:

M_n-1= p_n-1∙ M_n+q_n-1

M_n-1= -2M_n+C_n

Можно последовательно вычислить:

M_n= (2)

Далее можно последовательно вычислить:

M_n-1= p_n-1∙ M_n+q_n-1

M_n-2= p_n-2∙ M_n-1+q_n-2 (3)

и т. д.

Т.о. алгоритм «прогонка» состоит из двух частей: прямой и обратный ход.

В прямом ходе сначала задаем p₁ и q_1, затем по рекуррентным формулам вычисляем прогоночные коэффициенты.

Обратный ход: сначала по формуле (2) вычисляем M_n , а затем по формулам (3) вычисляют M_n-1, M_{n-2, …,} M_1.

Оказывается, метод «прогонка» не приводит к накоплению ошибок округления при вычислении. Такие методы называются численно устойчивыми.

Сформируем систему для случая периодического сплайна:

Из формул

M₁=M_n

a_i ∙M_i-1+2Mi+b_i ∙M_i+1=C_i , i=2,3,…,h-1.

M_n+1= M₂ (h_n=h₁)

при i=2, M₁=M_n получим:

2M₂+b₂M₃+ a₂ M_n=C₂

a₃ M₂+2M₃+ b₃ M_n=C₃

… (4)

a_n-1 M_n-2+2M_n-1+ b_n-1 M_n=C_n-1

b_n ∙M_n-2+a_n M_n-1+ 2 M_n=C_n

Эти уравнения аналогичны рассмотренному выше приему и их можно переписать:

M_i= p_i∙M_i+1 +r_i∙M_n+q_i , i=2,3,…,n-1 (5)

Прогоночные коэффициенты опять вычисляются по (1) при условии, что p_i= q_i=0:

r_i = ,r₁=1 (6)

Полагая M_i=U_i∙M_n+V_i , i=2,3,…,n-1.

U_i=p_i∙U_i+1+r_i

V_i=p_i∙V_i+1+q_i

U_n=1 V_n=0

M_n=