Введение в математическое моделирование

Компьютерное моделирование и решение линейных и нелинейных многомерных систем

Разбить на страницы
Показывать лекцию целиком

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

Математические модели таких задач представляются линейными уравнениями. Если задача многомерна, то ее математическая модель представляется системой линейных уравнений.

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

В общем виде система линейных уравнений имеет вид:

$$\left\{ \begin{array}{l} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + a_{14}x_4 + \ldots + a_{1n}x_n = b_1,\\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + a_{24}x_4 + \ldots + a_{2n}x_n = b_2,\\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + a_{34}x_4 + \ldots + a_{3n}x_n = b_3,\\ \ldots\\ a_{n1}x_1 + a_{n2}x_2 + a_{n3}x_3 + a_{n4}x_4 + \ldots + a_{nn}x_n = b_n, \end{array} \right.$$

где

aij - коэффициенты при неизвестных системы,

bi - свободные члены,

xj - неизвестные системы,

$$i=\overline{1,n}$$ - номер строки,

$$j=\overline{1,n}$$ - номер столбца,

n - порядок системы.

В матричной форме система линейных уравнений имеет вид:

$$A \cdot \overline X = \overline B,$$

где

$${A} = \left [\begin{array}{ccc} a_{11} a_{12} \ldots a_{1n}\\ a_{21} a_{22} \ldots a_{2n}\\ \ldots \ldots \ldots \ldots\\ a_{n1} a_{n2} \ldots a_{nn}\\ \end{array} \right] \text{ –матрица коэффициентов системы порядка } {(n \times n)},$$ $$\mathbf{\overline X} = \left[ \begin{array}{ccc} x_1\\ x_2\\ \ldots\\ x_n\\ \end{array} \right] \text{ – вектор неизвестных системы размерностью n},$$ $$\mathbf{\overline B} = \left[ \begin{array}{ccc} b_1\\ b_2\\ \ldots\\ b_n\\ \end{array} \right] \text{ – вектор свободных членов размерностью n}.$$

Численные методы решения систем линейных уравнений (СЛУ) можно разделить на две группы:

  • точные или прямые методы,
  • приближенные методы.
    •

    Приближенные методы реализуют на ЭВМ нахождение корней с заданной точностью и являются итерационными методами.

    Точные методы позволяют получить решение системы за конечное число итераций. К точным методам относятся:

  • правило Крамера,
  • метод Гаусса,
  • метод прогонки.
    •

    Решение систем линейных уравнений методом Гаусса

    Метод Гаусса является точным методом. Он позволяет получить решение системы за конечное число арифметических действий. В основе метода лежит идея последовательного исключения неизвестных. Метод состоит из двух этапов. На первом этапе (прямой ход) система при помощи последовательного исключения неизвестных приводится к треугольному виду. На втором этапе (обратный ход) из системы треугольного вида последовательно, в обратном порядке, начиная c n-го уравнения, находятся неизвестные системы.

    В качестве примера возьмем систему 4 порядка.

    $$\left\{ \begin{array}{l} a_{11}^{(0)}x_1 + a_{12}^{(0)}x_2 + a_{13}^{(0)}x_3 + a_{14}^{(0)}x_4 = b_1^{(0)},\\ a_{21}^{(0)}x_1 + a_{22}^{(0)}x_2 + a_{23}^{(0)}x_3 + a_{24}^{(0)}x_4 = b_2^{(0)},\\ a_{31}^{(0)}x_1 + a_{32}^{(0)}x_2 + a_{33}^{(0)}x_3 + a_{34}^{(0)}x_4 = b_3^{(0)},\\ a_{41}^{(0)}x_1 + a_{42}^{(0)}x_2 + a_{43}^{(0)}x_3 + a_{44}^{(0)}x_4 = b_4^{(0)}, \end{array} \right.$$

    Прямой ход. На первом шаге прямого хода (к=1) находим x1 из первого уравнения системы (9.1).

    $$a_{11}^{(0)}$$ - ведущий элемент первой строки.

    Если $$a_{11}^{(0)} \neq 0$$, то

    $$x_1= - \frac {a_{12}^{(0)}}{a_{11}^{(0)}} x_2 - \frac {a_{13}^{(0)}}{a_{11}^{(0)}} x_3 - \frac {a_{14}^{(0)}}{a_{11}^{(0)}} x_4 + \frac {b_1^{(0)}}{a_{11}^{(0)}},$$

    Обозначим:

    $$\frac {a_{12}^{(0)}}{a_{11}^{(0)}} = a_{12}^{(1)}; \frac {a_{13}^{(0)}}{a_{11}^{(0)}} = a_{13}^{(1)}; \frac {a_{14}^{(0)}}{a_{11}^{(0)}} = a_{14}^{(1)}; \frac {b_1^{(0)}}{a_{11}^{(0)}} = b_1^{(1)}.$$

    Подставляя (9.3) в (9.2), получим

    $$x_1 = -a_{12}^{(1)}x_2 - a_{13}^{(1)}x_3 - a_{14}^{(1)}x_4 + b_1^{(1)},$$

    где

    $$a_{1j}^{(1)} = \frac{a_{1j}^{(0)}}{a_{11}^{(0)}}, j=2,3,4 = \overline{(k+1),n}\\ b_1^{(1)} = \frac{b_1^{(0)}}{a_{11}^{(0)}}.$$

    Подставляем (9.4) во 2, 3 и 4 уравнение системы (9.1), получим:

    $$\left\{ \begin{array}{l} (a_{22}^{(0)} - a_{21}^{(0)} \cdot a_{12}^{(1)}) x_2 + (a_{23}^{(0)} - a_{21}^{(0)} \cdot a_{13}^{(1)}) x_3 + (a_{24}^{(0)} - a_{21}^{(0)} \cdot a_{14}^{(1)}) x_4 = b_2^{(0)} - a_{21}^{(0)}\cdot b_1^{(1)},\\ (a_{32}^{(0)} - a_{31}^{(0)} \cdot a_{12}^{(1)}) x_2 + (a_{33}^{(0)} - a_{31}^{(0)} \cdot a_{13}^{(1)}) x_3 + (a_{34}^{(0)} - a_{31}^{(0)} \cdot a_{14}^{(1)}) x_4 = b_3^{(0)} - a_{31}^{(0)}\cdot b_1^{(1)},\\ (a_{42}^{(0)} - a_{41}^{(0)} \cdot a_{12}^{(1)}) x_2 + (a_{43}^{(0)} - a_{41}^{(0)} \cdot a_{13}^{(1)}) x_3 + (a_{44}^{(0)} - a_{41}^{(0)} \cdot a_{14}^{(1)}) x_4 = b_4^{(0)} - a_{41}^{(0)}\cdot b_1^{(1)}, \end{array} \right.$$

    Обозначив коэффициенты при неизвестных полученной системы через $$a_{ij}^{(1)}$$, а свободные члены через $$b_i^{(1)}$$ перепишем полученную систему:

    $$\left\{ \begin{array}{l} a_{22}^{(1)} x_2 + a_{23}^{(1)} x_3 + a_{24}^{(1)} x_4 = b_2^{(1)},\\ a_{32}^{(1)} x_2 + a_{33}^{(1)} x_3 + a_{34}^{(1)} x_4 = b_3^{(1)},\\ a_{42}^{(1)} x_2 + a_{43}^{(1)} x_3 + a_{44}^{(1)} x_4 = b_4^{(1)}. \end{array} \right.$$

    где

    $$a_{ij}^{(1)} = a_{ij}^{(0)} - a_{il}^{(0)} \cdot a_{lj}^{(1)},\\ b_i^{(1)} =b_i^{(0)} -a_{il}^{(0)} b_l^{(1)},\\ i=\overline{(k+1),n}; j=\overline{(k+1),n}.$$

    Таким образом, в результате выполнения первого шага прямого хода исходная система (9.1) n-го порядка преобразована к совокупности уравнения (9.4) и системы линейных уравнений (9.5), порядок которой равен n-1.

    На втором шаге прямого хода (к=2) из первого уравнения системы (9.5) находим x2.

    $$a_{22}^{(1)}$$ -ведущий элемент первой строки системы (9.5).

    Если $$a_{22}^{(1)} \neq 0$$, то из первого уравнения системы (9.5) имеем:

    $$x_2= - a_{23}^{(2)}x_3 - a_{24}^{(2)}x_4 + b_2^{(2)},$$

    где

    $$a_{2j}^{(2)} = a_{2j}^{(1)}/ a_{22}^{(1)},\\ b_2^{(2)} = b_2^{(1)}/ a_{22}^{(1)}.\\ j=3,4=\overline{(k+1),n}$$

    Подставив выражение (9.6) во второе и третье уравнения системы (9.5), получим новую систему линейных уравнений, порядок которой равен n-2.

    $$\left\{ \begin{array}{l} a_{33}^{(2)}x_3 + a_{34}^{(2)}x_4 = b_3^{(2)},\\ a_{43}^{(2)}x_3 + a_{44}^{(2)}x_4 = b_4^{(2)}. \end{array} \right.$$

    где

    $$a_{ij}^{(2)} = a_{ij}^{(1)} - a_{i2}^{(1)} \cdot a_{2j}^{(2)}, \\b_i^{(2)} = b_i^{(1)} - a_{i2}^{(1)}b_2^{(2)},\\ i=\overline{(k+1),n}; j=\overline{(k+1),n}.$$

    Таким образом, в результате выполнения второго шага прямого хода исходная система (9.1) преобразована к совокупности уравнений (9.4), (9.6) и системы линейных уравнений (9.7),порядок которой равен n-2.

    На третьем шаге прямого хода (к=3) из системы (9.7) находим x3.

    $$a_{33}^{(2)}$$ - ведущий элемент системы (9.7).

    Если $$a_{33}^{(2)} \neq 0$$, то из первого уравнения системы (9.7) имеем:

    $$x_3= -a_{34}^{(3)}x_4 + b_3^{(3)},$$

    где

    $$a_{3j}^{(3)} = a_{3j}^{(2)}/ a_{33}^{(2)},\\ b_3^{(3)} = b_3^{(2)}/ a_{33}^{(2)},\\ j=4=\overline{(k+1),n}$$

    Подставив выражение (9.8) для x3 во второе уравнение системы (9.7) получим:

    $$a_{44}^{(3)}x_4 = b_4^{(3)},$$

    где

    $$a_{ij}^{(3)} = a_{ij}^{(2)} - a_{i3}^{(2)} \cdot a_{3j}^{(3)},\\ b_i^{(3)} = b_i^{(2)} - a_{i3}^{(2)} \cdot a_{3j}^{(3)},\\ i=\overline{(k+1),n}; j=\overline{(k+1),n}.$$

    На последнем шаге прямого хода, если $$a_{44}^{(3)} \neq 0,$$ то из уравнения (9.9) имеем:

    $$x_4 = b_4^{(4)},$$

    где

    $$b_4^{(4)} = b_4^{(3)}/ a_{44}^{(3)}.$$

    В результате выполнения всех шагов прямого хода исходная система (9.1) приводится к системе треугольного вида, полученной объединением уравнений (9.4), (9.6), (9.8), (9.10):

    $$\left\{ \begin{array}{l} x_1= -a_{12}^{(1)}x_2 - a_{13}^{(1)}x_3 - a_{14}^{(1)}x_4 + b_1^{(1)},\\ x_2= -a_{23}^{(2)}x_3 - a_{24}^{(2)}x_4 + b_2^{(2)},\\ x_3= -a_{34}^{(3)}x_4 + b_3^{(3)},\\ x_4= b_4^{(4)}. \end{array} \right.$$

    При построении алгоритма прямого хода вычисление организуем в цикле по шагам, т.е. $$k=\overline{1,(n-1)}$$.

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

    $$b_n=\frac{b_n}{a_{nn}}.$$

    В процессе выполнения всех шагов прямого хода все преобразования коэффициентов и свободных членов проводим по полученным ранее рекуррентным формулам:

    $$b_k^{(k)}= b_k^{(k-1)}/a_k,k^{(k-1)},\\ b_i^{(k)}= b_i^{(k-1)}/a_i,k^{(k-1)} \cdot b_k^{(k)},\\ a_{k,j^{(k)}}= a_{k,j^{(k-1)}}/a_{k,k^{(k-1)}},\\ a_{i,j^{(k)}}= a_{i,j^{(k-1)}}-a_{i,k^{(k-1)}} \cdot a_{k,j^{(k)}},$$

    где

    $$k=\overline{1,(n-1)}$$ – номер шага прямого хода,

    $$i=\overline{(k+1),n}$$ - номер уравнения систем (9.5), (9.7)

    $$j=\overline{(k+1),n}$$

    В процессе обратного хода из системы (9.12) неизвестные находятся в обратном порядке. Значение корня х4 находят из последнего уравнения системы (9.12). Далее х4 используется для отыскания корня х3 из 3-го уравнения, далее х3 и х4 используются отыскания х2 из 2-го уравнения системы (9.12), и, наконец, х2, х3 и х4 используются для отыскания х1 из 1-го уравнения системы (9.12).

    Все вычисления обратного хода проводим в цикле по i, где

    $$i=\overline{(n-1)},1$$ по рекуррентным формулам:

    $$b_i={b_i – x_j \cdot a_{ij}} , \\ \overline i=(n-1),\overline {1,j}=(i+1),n$$

    xi= bi.

    Рассмотренный выше простейший вариант метода Гаусса, называемый схемой единственного деления, обладает следующим недостатком: если ведущий элемент akk какой-либо строки окажется равным нулю, то этот метод формально непригоден, хотя система может иметь единственное решение. Из этих соображений в схеме алгоритма добавлен поиск ненулевого ведущего элемента.

    На рисунке 9.1 представлена укрупнённая схема алгоритма (блок-схема) метода Гаусса. На рисунках 9.2 - 9.6 представлены алгоритмы отдельных блоков метода.

    (рис 9.1) Укрупнённая схема алгоритма (блок-схема) метода Гаусса

    Блок 2. С помощью двух вложенных циклов с управляющими переменными i=1,n и j=1,k организуем ввод коэффициентов ai,j и свободных членов bi исходной системы. Для того, чтобы в дальнейшем можно было выполнить в блоке 9 проверку результата, в алгоритме предусмотрено сохранение значений ai,j и bi исходной системы с помощью переприсвоений: cij=aij и di=bi

    (рис 9.2)

    Блок 3. Организуем цикл по k, внутри которого производится вычисление по всем шагам прямого хода. Последний п-й шаг прямого хода выводим из цикла.

    Блок 4. На каждом шаге прямого хода выполняем поиск ненулевого ведущего элемента.

    (рис 9.3)

    Поиск ненулевого ведущего элемента ведётся в следующем порядке:

    а) На каждом k-ом шаге прямого хода ведущий элемент каждой строки сравнивается с нулём;

    б) Если в k-ой строке имеется нулевой ведущий элемент, то в k-ом столбце в цикле осуществляется поиск ненулевого элемента.

    в) Если в какой-то строке kn такой ненулевой элемент найден, то строки kn и k поэлементно, в цикле по k1=(k+1),n, меняем местами. Для перестановки элементов используется рабочая переменная R.

    г) Если ненулевой ведущий элемент не найден, то коду ошибки kо присваиваем значение 1 и расчёт прекращается.

    Блок 5 - шаг прямого хода. На каждом шаге прямого хода проводим исключение неизвестных путём преобразования коэффициентов и свободных членов системы по полученным ранее рекуррентным формулам.

    (рис 9.4)

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

    xn=bn/an,n

    Блок 7 - обратный ход. В процессе обратного хода метода Гаусса из системы треугольного вида последовательно в обратном порядке в цикле по i=(n-1),1,-1 находим неизвестные системы по рекуррентной формуле

    bi= bi - xj.ai,j , i=(n-1),1, j=(n+1),n.

    При этом в цикле по j=(i+1),n использован приём последовательного вычитания xj.ai,j из bi,после чего вводится переприсвоение bi =хi.

    (рис 9.5)

    Блок 9 - проверка результата. В этом блоке подставляя значения полученных неизвестных в исходную систему и используя сохранённые значения коэффициентов системы ci,j и свободных членов di, проводим проверку решения задачи по формуле

    $$F_i = -d_i + \sum \limits_{j=1}^{n}C_{ij} \cdot x_j$$

    Если корни системы найдены, то Fi – это число, близкое к нулю.

    Блок 9 в алгоритме метода Гаусса рекомендуется использовать только в процессе отладки метода.

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

    (рис 9.6)
    Страницы:

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

    Математические модели таких задач представляются линейными уравнениями. Если задача многомерна, то ее математическая модель представляется системой линейных уравнений.

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

    В общем виде система линейных уравнений имеет вид:

    $$\left\{ \begin{array}{l} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 + a_{14}x_4 + \ldots + a_{1n}x_n = b_1,\\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 + a_{24}x_4 + \ldots + a_{2n}x_n = b_2,\\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 + a_{34}x_4 + \ldots + a_{3n}x_n = b_3,\\ \ldots\\ a_{n1}x_1 + a_{n2}x_2 + a_{n3}x_3 + a_{n4}x_4 + \ldots + a_{nn}x_n = b_n, \end{array} \right.$$

    где

    aij - коэффициенты при неизвестных системы,

    bi - свободные члены,

    xj - неизвестные системы,

    $$i=\overline{1,n}$$ - номер строки,

    $$j=\overline{1,n}$$ - номер столбца,

    n - порядок системы.

    В матричной форме система линейных уравнений имеет вид:

    $$A \cdot \overline X = \overline B,$$

    где

    $${A} = \left [\begin{array}{ccc} a_{11} a_{12} \ldots a_{1n}\\ a_{21} a_{22} \ldots a_{2n}\\ \ldots \ldots \ldots \ldots\\ a_{n1} a_{n2} \ldots a_{nn}\\ \end{array} \right] \text{ –матрица коэффициентов системы порядка } {(n \times n)},$$ $$\mathbf{\overline X} = \left[ \begin{array}{ccc} x_1\\ x_2\\ \ldots\\ x_n\\ \end{array} \right] \text{ – вектор неизвестных системы размерностью n},$$ $$\mathbf{\overline B} = \left[ \begin{array}{ccc} b_1\\ b_2\\ \ldots\\ b_n\\ \end{array} \right] \text{ – вектор свободных членов размерностью n}.$$

    Численные методы решения систем линейных уравнений (СЛУ) можно разделить на две группы:

  • точные или прямые методы,
  • приближенные методы.
    •

    Приближенные методы реализуют на ЭВМ нахождение корней с заданной точностью и являются итерационными методами.

    Точные методы позволяют получить решение системы за конечное число итераций. К точным методам относятся:

  • правило Крамера,
  • метод Гаусса,
  • метод прогонки.
    •

    Решение систем линейных уравнений методом Гаусса

    Метод Гаусса является точным методом. Он позволяет получить решение системы за конечное число арифметических действий. В основе метода лежит идея последовательного исключения неизвестных. Метод состоит из двух этапов. На первом этапе (прямой ход) система при помощи последовательного исключения неизвестных приводится к треугольному виду. На втором этапе (обратный ход) из системы треугольного вида последовательно, в обратном порядке, начиная c n-го уравнения, находятся неизвестные системы.

    В качестве примера возьмем систему 4 порядка.

    $$\left\{ \begin{array}{l} a_{11}^{(0)}x_1 + a_{12}^{(0)}x_2 + a_{13}^{(0)}x_3 + a_{14}^{(0)}x_4 = b_1^{(0)},\\ a_{21}^{(0)}x_1 + a_{22}^{(0)}x_2 + a_{23}^{(0)}x_3 + a_{24}^{(0)}x_4 = b_2^{(0)},\\ a_{31}^{(0)}x_1 + a_{32}^{(0)}x_2 + a_{33}^{(0)}x_3 + a_{34}^{(0)}x_4 = b_3^{(0)},\\ a_{41}^{(0)}x_1 + a_{42}^{(0)}x_2 + a_{43}^{(0)}x_3 + a_{44}^{(0)}x_4 = b_4^{(0)}, \end{array} \right.$$

    Прямой ход. На первом шаге прямого хода (к=1) находим x1 из первого уравнения системы (9.1).

    $$a_{11}^{(0)}$$ - ведущий элемент первой строки.

    Если $$a_{11}^{(0)} \neq 0$$, то

    $$x_1= - \frac {a_{12}^{(0)}}{a_{11}^{(0)}} x_2 - \frac {a_{13}^{(0)}}{a_{11}^{(0)}} x_3 - \frac {a_{14}^{(0)}}{a_{11}^{(0)}} x_4 + \frac {b_1^{(0)}}{a_{11}^{(0)}},$$

    Обозначим:

    $$\frac {a_{12}^{(0)}}{a_{11}^{(0)}} = a_{12}^{(1)}; \frac {a_{13}^{(0)}}{a_{11}^{(0)}} = a_{13}^{(1)}; \frac {a_{14}^{(0)}}{a_{11}^{(0)}} = a_{14}^{(1)}; \frac {b_1^{(0)}}{a_{11}^{(0)}} = b_1^{(1)}.$$

    Подставляя (9.3) в (9.2), получим

    $$x_1 = -a_{12}^{(1)}x_2 - a_{13}^{(1)}x_3 - a_{14}^{(1)}x_4 + b_1^{(1)},$$

    где

    $$a_{1j}^{(1)} = \frac{a_{1j}^{(0)}}{a_{11}^{(0)}}, j=2,3,4 = \overline{(k+1),n}\\ b_1^{(1)} = \frac{b_1^{(0)}}{a_{11}^{(0)}}.$$

    Подставляем (9.4) во 2, 3 и 4 уравнение системы (9.1), получим:

    $$\left\{ \begin{array}{l} (a_{22}^{(0)} - a_{21}^{(0)} \cdot a_{12}^{(1)}) x_2 + (a_{23}^{(0)} - a_{21}^{(0)} \cdot a_{13}^{(1)}) x_3 + (a_{24}^{(0)} - a_{21}^{(0)} \cdot a_{14}^{(1)}) x_4 = b_2^{(0)} - a_{21}^{(0)}\cdot b_1^{(1)},\\ (a_{32}^{(0)} - a_{31}^{(0)} \cdot a_{12}^{(1)}) x_2 + (a_{33}^{(0)} - a_{31}^{(0)} \cdot a_{13}^{(1)}) x_3 + (a_{34}^{(0)} - a_{31}^{(0)} \cdot a_{14}^{(1)}) x_4 = b_3^{(0)} - a_{31}^{(0)}\cdot b_1^{(1)},\\ (a_{42}^{(0)} - a_{41}^{(0)} \cdot a_{12}^{(1)}) x_2 + (a_{43}^{(0)} - a_{41}^{(0)} \cdot a_{13}^{(1)}) x_3 + (a_{44}^{(0)} - a_{41}^{(0)} \cdot a_{14}^{(1)}) x_4 = b_4^{(0)} - a_{41}^{(0)}\cdot b_1^{(1)}, \end{array} \right.$$

    Обозначив коэффициенты при неизвестных полученной системы через $$a_{ij}^{(1)}$$, а свободные члены через $$b_i^{(1)}$$ перепишем полученную систему:

    $$\left\{ \begin{array}{l} a_{22}^{(1)} x_2 + a_{23}^{(1)} x_3 + a_{24}^{(1)} x_4 = b_2^{(1)},\\ a_{32}^{(1)} x_2 + a_{33}^{(1)} x_3 + a_{34}^{(1)} x_4 = b_3^{(1)},\\ a_{42}^{(1)} x_2 + a_{43}^{(1)} x_3 + a_{44}^{(1)} x_4 = b_4^{(1)}. \end{array} \right.$$

    где

    $$a_{ij}^{(1)} = a_{ij}^{(0)} - a_{il}^{(0)} \cdot a_{lj}^{(1)},\\ b_i^{(1)} =b_i^{(0)} -a_{il}^{(0)} b_l^{(1)},\\ i=\overline{(k+1),n}; j=\overline{(k+1),n}.$$

    Таким образом, в результате выполнения первого шага прямого хода исходная система (9.1) n-го порядка преобразована к совокупности уравнения (9.4) и системы линейных уравнений (9.5), порядок которой равен n-1.

    На втором шаге прямого хода (к=2) из первого уравнения системы (9.5) находим x2.

    $$a_{22}^{(1)}$$ -ведущий элемент первой строки системы (9.5).

    Если $$a_{22}^{(1)} \neq 0$$, то из первого уравнения системы (9.5) имеем:

    $$x_2= - a_{23}^{(2)}x_3 - a_{24}^{(2)}x_4 + b_2^{(2)},$$

    где

    $$a_{2j}^{(2)} = a_{2j}^{(1)}/ a_{22}^{(1)},\\ b_2^{(2)} = b_2^{(1)}/ a_{22}^{(1)}.\\ j=3,4=\overline{(k+1),n}$$

    Подставив выражение (9.6) во второе и третье уравнения системы (9.5), получим новую систему линейных уравнений, порядок которой равен n-2.

    $$\left\{ \begin{array}{l} a_{33}^{(2)}x_3 + a_{34}^{(2)}x_4 = b_3^{(2)},\\ a_{43}^{(2)}x_3 + a_{44}^{(2)}x_4 = b_4^{(2)}. \end{array} \right.$$

    где

    $$a_{ij}^{(2)} = a_{ij}^{(1)} - a_{i2}^{(1)} \cdot a_{2j}^{(2)}, \\b_i^{(2)} = b_i^{(1)} - a_{i2}^{(1)}b_2^{(2)},\\ i=\overline{(k+1),n}; j=\overline{(k+1),n}.$$

    Таким образом, в результате выполнения второго шага прямого хода исходная система (9.1) преобразована к совокупности уравнений (9.4), (9.6) и системы линейных уравнений (9.7),порядок которой равен n-2.

    На третьем шаге прямого хода (к=3) из системы (9.7) находим x3.

    $$a_{33}^{(2)}$$ - ведущий элемент системы (9.7).

    Если $$a_{33}^{(2)} \neq 0$$, то из первого уравнения системы (9.7) имеем:

    $$x_3= -a_{34}^{(3)}x_4 + b_3^{(3)},$$

    где

    $$a_{3j}^{(3)} = a_{3j}^{(2)}/ a_{33}^{(2)},\\ b_3^{(3)} = b_3^{(2)}/ a_{33}^{(2)},\\ j=4=\overline{(k+1),n}$$

    Подставив выражение (9.8) для x3 во второе уравнение системы (9.7) получим:

    $$a_{44}^{(3)}x_4 = b_4^{(3)},$$

    где

    $$a_{ij}^{(3)} = a_{ij}^{(2)} - a_{i3}^{(2)} \cdot a_{3j}^{(3)},\\ b_i^{(3)} = b_i^{(2)} - a_{i3}^{(2)} \cdot a_{3j}^{(3)},\\ i=\overline{(k+1),n}; j=\overline{(k+1),n}.$$

    На последнем шаге прямого хода, если $$a_{44}^{(3)} \neq 0,$$ то из уравнения (9.9) имеем:

    $$x_4 = b_4^{(4)},$$

    где

    $$b_4^{(4)} = b_4^{(3)}/ a_{44}^{(3)}.$$

    В результате выполнения всех шагов прямого хода исходная система (9.1) приводится к системе треугольного вида, полученной объединением уравнений (9.4), (9.6), (9.8), (9.10):

    $$\left\{ \begin{array}{l} x_1= -a_{12}^{(1)}x_2 - a_{13}^{(1)}x_3 - a_{14}^{(1)}x_4 + b_1^{(1)},\\ x_2= -a_{23}^{(2)}x_3 - a_{24}^{(2)}x_4 + b_2^{(2)},\\ x_3= -a_{34}^{(3)}x_4 + b_3^{(3)},\\ x_4= b_4^{(4)}. \end{array} \right.$$

    При построении алгоритма прямого хода вычисление организуем в цикле по шагам, т.е. $$k=\overline{1,(n-1)}$$.

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

    $$b_n=\frac{b_n}{a_{nn}}.$$

    В процессе выполнения всех шагов прямого хода все преобразования коэффициентов и свободных членов проводим по полученным ранее рекуррентным формулам:

    $$b_k^{(k)}= b_k^{(k-1)}/a_k,k^{(k-1)},\\ b_i^{(k)}= b_i^{(k-1)}/a_i,k^{(k-1)} \cdot b_k^{(k)},\\ a_{k,j^{(k)}}= a_{k,j^{(k-1)}}/a_{k,k^{(k-1)}},\\ a_{i,j^{(k)}}= a_{i,j^{(k-1)}}-a_{i,k^{(k-1)}} \cdot a_{k,j^{(k)}},$$

    где

    $$k=\overline{1,(n-1)}$$ – номер шага прямого хода,

    $$i=\overline{(k+1),n}$$ - номер уравнения систем (9.5), (9.7)

    $$j=\overline{(k+1),n}$$

    В процессе обратного хода из системы (9.12) неизвестные находятся в обратном порядке. Значение корня х4 находят из последнего уравнения системы (9.12). Далее х4 используется для отыскания корня х3 из 3-го уравнения, далее х3 и х4 используются отыскания х2 из 2-го уравнения системы (9.12), и, наконец, х2, х3 и х4 используются для отыскания х1 из 1-го уравнения системы (9.12).

    Все вычисления обратного хода проводим в цикле по i, где

    $$i=\overline{(n-1)},1$$ по рекуррентным формулам:

    $$b_i={b_i – x_j \cdot a_{ij}} , \\ \overline i=(n-1),\overline {1,j}=(i+1),n$$

    xi= bi.

    Рассмотренный выше простейший вариант метода Гаусса, называемый схемой единственного деления, обладает следующим недостатком: если ведущий элемент akk какой-либо строки окажется равным нулю, то этот метод формально непригоден, хотя система может иметь единственное решение. Из этих соображений в схеме алгоритма добавлен поиск ненулевого ведущего элемента.

    На рисунке 9.1 представлена укрупнённая схема алгоритма (блок-схема) метода Гаусса. На рисунках 9.2 - 9.6 представлены алгоритмы отдельных блоков метода.

    (рис 9.1) Укрупнённая схема алгоритма (блок-схема) метода Гаусса

    Блок 2. С помощью двух вложенных циклов с управляющими переменными i=1,n и j=1,k организуем ввод коэффициентов ai,j и свободных членов bi исходной системы. Для того, чтобы в дальнейшем можно было выполнить в блоке 9 проверку результата, в алгоритме предусмотрено сохранение значений ai,j и bi исходной системы с помощью переприсвоений: cij=aij и di=bi

    (рис 9.2)

    Блок 3. Организуем цикл по k, внутри которого производится вычисление по всем шагам прямого хода. Последний п-й шаг прямого хода выводим из цикла.

    Блок 4. На каждом шаге прямого хода выполняем поиск ненулевого ведущего элемента.

    (рис 9.3)

    Поиск ненулевого ведущего элемента ведётся в следующем порядке:

    а) На каждом k-ом шаге прямого хода ведущий элемент каждой строки сравнивается с нулём;

    б) Если в k-ой строке имеется нулевой ведущий элемент, то в k-ом столбце в цикле осуществляется поиск ненулевого элемента.

    в) Если в какой-то строке kn такой ненулевой элемент найден, то строки kn и k поэлементно, в цикле по k1=(k+1),n, меняем местами. Для перестановки элементов используется рабочая переменная R.

    г) Если ненулевой ведущий элемент не найден, то коду ошибки kо присваиваем значение 1 и расчёт прекращается.

    Блок 5 - шаг прямого хода. На каждом шаге прямого хода проводим исключение неизвестных путём преобразования коэффициентов и свободных членов системы по полученным ранее рекуррентным формулам.

    (рис 9.4)

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

    xn=bn/an,n

    Блок 7 - обратный ход. В процессе обратного хода метода Гаусса из системы треугольного вида последовательно в обратном порядке в цикле по i=(n-1),1,-1 находим неизвестные системы по рекуррентной формуле

    bi= bi - xj.ai,j , i=(n-1),1, j=(n+1),n.

    При этом в цикле по j=(i+1),n использован приём последовательного вычитания xj.ai,j из bi,после чего вводится переприсвоение bi =хi.

    (рис 9.5)

    Блок 9 - проверка результата. В этом блоке подставляя значения полученных неизвестных в исходную систему и используя сохранённые значения коэффициентов системы ci,j и свободных членов di, проводим проверку решения задачи по формуле

    $$F_i = -d_i + \sum \limits_{j=1}^{n}C_{ij} \cdot x_j$$

    Если корни системы найдены, то Fi – это число, близкое к нулю.

    Блок 9 в алгоритме метода Гаусса рекомендуется использовать только в процессе отладки метода.

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

    (рис 9.6)
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^