Алгоритмы и программы для решения систем линейных уравнений прямыми методами

Страницы работы

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.

Фрагмент текста работы

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

2. Метод Гаусса

Метод Гаусса основан на замене исходной системы (1) на эквивалентную (т.е. имеющую то же решение ), но с матрицей U верхней треугольной формы:

                                                    (2)

или в развернутом виде:

                               (2а)

Матрица U получается путем преобразования исходной матрицы A, а вектор  - из вектора . Так как матрица U - треугольная, все компоненты вектора , начиная с , легко находятся последовательно.

Алгоритм метода Гаусса состоит из двух этапов:

Преобразование A à U и . à  - прямой ход;

Последовательное  вычисление  (i = n, n-1, ..., 1) – обратный ход.

Далее приводится словесно-формульное описание алгоритмов прямого и обратного хода метода Гаусса. Обоснование проводимых операций можно найти в соответствующей литературе /1,2/.

Процедура прямого хода осуществляется за n шагов (n - порядок СЛАУ). На k-том шаге формируется k-тая строка матрицы U и k-тый компонент вектора .

Каждый шаг состоит из двух частей. На первой вычисляются искомые элементы матрицы U и компоненты вектора :

                                                         (3)

Примечание: Индекс вверху (в скобках) означает индекс шага, от которого следует взять соответствующие значения элементов и компонентов. Он необходим, так как на каждом шаге матрица A и вектор  преобразуются. Индекс k = 0 соответствует исходным элементам и компонентам. В дальнейшем будет видно, что этот индекс является фиктивным, т.е. при программировании не порождает соответствующий индекс массивов. Но при алгебраической записи формул в литературе он обычно приводится.

На второй части шага оставшаяся часть матрицы A (ниже k-той строки и правее k-того столбца) и вектора  (ниже k-того компонента) пересчитываются по формулам:

                               (4)

При k = n  вторая часть шага не выполняется, т.к. пересчитывать больше нечего.

Обратный ход начинается с определения , которое следует из (2а):

                                           (5)

Затем последовательно находятся   по формуле:

                           (6)

Эта формула следует из обобщения уравнений, которые получаются при умножении матрицы U на вектор  из (2а) и рассмотрении их в последовательности снизу вверх.

Действия с компонентами векторов  и  в (3) и (4) совпадают с аналогичными действиями над элементами матриц A и U, поэтому в алгоритме Гаусса часто присоединяют эти вектора в качестве дополнительного (n+1)-го столбца соответствующих матриц. При этом алгоритм и реализующая его программа становятся более компактными и красивыми.

3.  Метод  LU-разложения

Метод LU-разложения основан на том, что матрица A может быть представлена в виде произведения двух матриц:

                                                                (7)

где       L - нижняя треугольная матрица,

U - верхняя треугольная матрица с единичной  главной диагональю.

При этом разложении исходная система (1) разлагается на две, но с треугольными матрицами:

                                                                (8а)

                                                               (8б)

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

Алгоритм разложения  (факторизации)  матрицы  A на две треугольных также

Похожие материалы

Информация о работе

Уважаемые коллеги! Предлагаем вам разработку программного обеспечения под ключ.

Опытные программисты сделают для вас мобильное приложение, нейронную сеть, систему искусственного интеллекта, SaaS-сервис, производственную систему, внедрят или разработают ERP/CRM, запустят стартап.

Сферы - промышленность, ритейл, производственные компании, стартапы, финансы и другие направления.

Языки программирования: Java, PHP, Ruby, C++, .NET, Python, Go, Kotlin, Swift, React Native, Flutter и многие другие.

Всегда на связи. Соблюдаем сроки. Предложим адекватную конкурентную цену.

Заходите к нам на сайт и пишите, с удовольствием вам во всем поможем.