К вопросу об условиях разрешимости трехдиагональных систем

УДК 519.61

К вопросу об условиях разрешимости трехдиагональных систем

[1]

Национальный исследовательский Иркутский государственный технический университет,

664074, Иркутск, .

Трехдиагональные системы имеют широкое практическое применение – используются в алгоритмах сплайновых аппроксимаций, при решении краевых задач для дифференциальных уравнений второго порядка, а также в разностных методах решения задач математической физики. Для установления однозначной разрешимости таких систем обычно используют условие диагонального преобладания. Это условие является достаточно жестким. Целью работы было его ослабление, чего удалось достичь в одном достаточно частном случае, когда все поддиагональные, наддиагональные и диагональные элементы равны между собой. Выполнен численный эксперимент и дана геометрическая интерпретация.

Библиогр. 6 назв.

Ключевые слова: система линейных алгебраических уравнений; трехдиагональная матрица; определитель; вычислительный эксперимент.

ON CONDITIONS FOR THE SOLVABILITY OF THE TRIDIAGONAL SYSTEMS.

E. Boltvina

National Research Irkutsk State Technical University,

83, Lermontov St, Irkutsk, 664074.

The present paper is devoted to the study of tridiagonal systems, notably the problem of their solvability conditions is treated. As a result the conditions are obtained not being the ones of diagonal dominance; they make it possible to prove the unique solvability of the given systems in some special cases.

6 sources

Keywords: the system of linear algebraic equations, tridiagonal matrix, determinant, computational experiment.

О трехдиагональных системах

У трехдиагональной матрицы все элементы, кроме элементов главной и примыкающих к ней диагоналей, равны нулю: , если ( и ) [1, стр. 45] (это частный случай треугольной матрицы [2]):

[3, стр. 23].

Для таких систем специального вида, содержащих много нулевых элементов, существуют более быстрые (по сравнению со стандартными) методы решения [4]. Первый из этих алгоритмов использует факторизацию системы и называется прогонкой (или алгоритмом Томаса). Метод прогонки (и его модификации: прогонка с выбором ведущего элемента, встречная прогонка, прогонка для систем с диагональным преобладанием по столбцам, потоковая прогонка и т. д. [3]) является наиболее важным частным случаем метода Гаусса. Второй алгоритм (редукция) использует последовательное бинарное исключение уравнений из системы; он менее известен и более сложен, однако обладает очень высокой устойчивостью и меньшим накоплением погрешности в процессе счета. При использовании метода прогонки, чтобы не возникало деления на нуль в формулах прямого хода, и исходная система имела единственное решение, обычно предполагается выполнение условия преобладания диагональных элементов [4]. Это условие является достаточно жестким, целью данного исследования является его ослабление в одном частном случае.

Приложения

Трехдиагональные системы или матрицы имеют приложения во многих областях. Они используются в теории ортогональных многочленов, к которым сводятся современные алгоритмы сплайновых аппроксимаций. Полиномиальная интерполяция не всегда дает удовлетворительные результаты при аппроксимации зависимостей, повышение степени интерполяционного полинома в некоторых случаях приводит не к уменьшению, а к увеличению погрешности. Возникает так называемое явление волнистости. Поэтому для проведения гладких кривых через узловые значения функции используют упругую металлическую линейку, совмещая её с узловыми точками. Математическая теория подобной аппроксимации развита с 70–х гг. XX в. и называется теорией сплайн–функций (от англ. слова spline – рейка, линейка).

Сплайном называется функция, которая вместе с несколькими производными непрерывна на всем заданном отрезке , а на каждом частичном отрезке в отдельности является некоторым алгебраическим многочленом [5]. Один из наиболее распространенных вариантов – интерполяция кубическими сплайнами.

«Системы разностных уравнений являются прекрасным примером приложения теории матриц, и в значительной степени – именно трехдиагональных» [3, стр. 162]. Системы с трехдиагональными матрицами часто встречаются при решениях краевых задач для дифференциальных уравнений второго порядка [4, стр. 133]. Можно рассмотреть систему линейных алгебраических уравнений следующего специального вида:

(1)

где – неизвестные, – заданные числа, причем

(2)

Задача (1) называется краевой задачей для трехточечного разностного уравнения или просто разностной краевой задачей [5].

Эти матрицы играют большую роль в такой области, как разностные методы решения задач математической физики. Линейные системы с трехдиагональной матрицей возникают при реализации решений параболических или эллиптических уравнений в одномерном случае либо в многомерном при покоординатном расщеплении решения.

Во многих случаях прикладные задачи приводят к трехдиагональным системам с диагональным преобладанием (причем хотя бы для одного имеет место неравенство) [4].

Рекуррентные соотношения

В процессе исследования трехдиагональных систем для выявления закономерностей делается следующее упрощающее предположение: и , , . Тогда определители -го порядка примут вид:

;

;

и т. д. При :

, , , …, .

Таким образом, каждый определитель порядка (где ) можно представить в виде

,

(аналогичное равенство приведено в [3]).

Пусть (это преобразование и дальнейшие рассуждения в [3] отсутствуют), соответственно, ; . Тогда из равенства следует, что , . Рекуррентная последовательность и будет предметом исследования. Схожая (но несколько иная) последовательность рассматривалась ранее в § 1 монографии [6].

Численный эксперимент

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

1. Для пар значений , удовлетворяющих условию положительности дискриминанта :

	3		1		2,618034		0,381966		2,236068
	1	2	3	4	5	6	7	8	9
	2,666667	2,625	2,619048	2,618182	2,618056	2,618037	2,618034	2,618034	2,618034

	3		-1		3,302776		-0,30278		3,605551
	1	2	3	4	5	6	7	8	9
	3,333333	3,3	3,30303	3,302752	3,302778	3,302775	3,302776	3,302776	3,302776

	-3		-1		0,302776		-3,30278		3,162278
	1	2	3	4	5	6	7	8	9
	-3,33333	-3,3	-3,30303	-3,30275	-3,30278	-3,30278	-3,30278	-3,30278	-3,30278

	-3		1		-0,38197		-2,61803		3,162278
	1	2	3	4	5	6	7	8	9
	-2,66667	-2,625	-2,61905	-2,61818	-2,61806	-2,61804	-2,61803	-2,61803	-2,61803

2. Равенства нулю дискриминанта  :

	2		1		1		1		0
	1	2	3	4	5	…	8	9	10
	1,5	1,333333	1,25	1,2	1,166667	…	1,111111	1,1	1,090909
	11	12	13	14	15	…	18	19	20
	1,083333	1,076923	1,071429	1,066667	1,0625	…	1,052632	1,05	1,047619

3. Отрицательности дискриминанта  :

	2		2						<0
	1	2	3	4	5	6	7	8	9
	1	0	del/0

Очевидно, что при значение стремится к одному из корней квадратного уравнения (полученное из ), а именно к или . При сходимости не наблюдается.

Геометрическая интерпретация

Полученные численные результаты можно представить геометрически для всех трех вышерассмотренных случаев в поле параметров и. Решая графически уравнение (в общем виде ), получаем левую часть - прямую и правую часть - гиперболу. Исследуя взаимное расположение прямой и гиперболы, получаем три возможных случая (см. ниже). Анализируя эти случаи можно заключить, что последовательность будет монотонной, если прямая и гипербола имеют общие точки только на одной из ветвей гиперболы. При этом последовательность будет убывать, если и ( - стационарное значение), и возрастать в противном случае.

Будет две подпоследовательности (возрастающая и убывающая) в случае, если прямая пересекает обе ветви гиперболы . И последовательность не будет иметь предельное значение при отсутствии пересечений прямой и гиперболы :

1. Первый: пересечение прямой двух ветвей гиперболы
при и , имеющих разные знаки (, ), и
при и , имеющих одинаковые знаки (, ), и

2. Второй: пересечение прямой одной ветви гиперболы
при и , имеющих разные знаки (, ), и
частный второй случай, когда прямая является касательной к гиперболе при и , имеющих одинаковые знаки (, ), и

3. Третий: отсутствие пересечений прямой и гиперболы
при и , имеющих разные знаки (, ), и

Анализ построенных графиков и численный эксперимент позволяют сделать следующие выводы:

1) при определитель трехдиагональной матрицы заведомо отличен от нуля;

2) при определитель трехдиагональной матрицы может обратиться в нуль;

3) при анализ разрешимости системы затруднен, однако прогонка, по-видимому, будет неустойчивой (т. к. последовательность расходится).

Разумеется, данные суждения носят предварительный характер. Для того чтобы сделать окончательные выводы, необходимо провести подробный анализ свойств определителей , аналогичный тому, который сделан в [6, §1] для определителей сильно разреженных матриц иной (не трехдиагональной) структуры.

Заключение

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

Библиографический список

1. , Гулин методы: учеб. пособие для вузов. М.: Наука, 1989. 432 с.

2. Гантмахер матриц. 5-е изд. М.: ФИЗМАТЛИТ, 2004. 560 c.

3. , Кузнецов матрицы и их приложения. М.: Наука., 1985. 208 с.

4. Калиткин методы. М.: Наука. 1978.

5. Волков методы: учеб. пособие для вузов. 2-е изд., испр. М.: Наука, 1987. 248 с.

6. , Казаков задача Коши и ее приложения. Новосибирск, Наука. 2006. 399 с.

[1] , студентка, *****@***com

Boltvina Ekaterina, Cybernetics Department Student,  *****@***com