Системы линейных алгебраических уравнений
Back Home Up Next

адача 3. Системы уравнений. Составить рекурсивную программу-функцию решения системы линейных алгебраических уравнений вида:

A × x = b ,                                                               (12)

где A = (Ai,j) (i, j = 0 .. n-1) - квадратная невырожденная матрица размером n´n, a b = (bi)T, и x = (x)(i = 0 .. n-1) - соответственно векторы свободных членов и неизвестных. Использовать LU или LUP-разложения A.

Решение. Пусть получено LU-разложение A. Тогда уравнение (12) равносильно системе L×Ux=b, которую, учитывая специфическую структуру L и U, можно решать в два приема следующим способом:

Из системы L×y=b с нижней треугольной матрицей L найдем y, последовательно вычисляя yi (i = 0 .. n-1), начиная от начального уравнения и дальше;

Из системы U×x=y с верхней треугольной матрицей U найдем x, последовательно вычисляя xi (i = n-1 .. 0), начиная от конечного уравнения и выше.

Соответствующие вычислительные процессы называются прямым и обратным ходом алгоритма Гаусса и осуществляются с трудоемкостью Q(n2) операций. Их можно реализовать рекурсивными программами-функциями rig(L,b,n) и rev(U,y,n,k). Система (12) решается головной функцией syslu(A,b), предварительно находящей LU-разложение A, а затем уже использующей rig() и rev(). Вспомогательный параметр k в rev(U,y,n,k) служит счетчиком количества рекурсивных обращений и его начальное значение должно быть равно единице.

                     (13)

                            (14)

                                      (15)

 Рекурсивные функции rig(L,b,n) и rev(U,y,n,k) можно использовать и для решения системы уравнений (12) при наличии LUP-разложения матрицы A (P×A=L×U). В этом случае (12) можно переписать в виде L×U×x=P×b. Следовательно, как и в случае с LU-разложениями, опять все сводится к решению двух систем с треугольными матрицами. Только здесь роль свободного члена b играет вектор P×b. Исходя из сказанного, соответствующая модификация головной программы syslu(A,b) могла бы выглядеть так:

                                    (16)

 Контрольный пример.

Home Содержание Схемы ООД Доска объявлений Поиск