Решение системы линейных алгебраических уравнений (СЛАУ)

Система уравнений вида

a₁₁x₁+a₁₂x₂+a₁₃x₃+…+a_1nx_n=b₁

a₂₁x₁+a₂₂x₂+a₂₃x₃+…+a_2nx_n=b₂ (1)

…….

a_m1x₁+a_m2x₂+a_m3x₃…+a_mnx_m=b_m

относится к разряду систем линейных алгебраических уравнений, где x_i – неизвестные переменные (i= ), a_ij - постоянные коэффициенты при неизвестных (j= ), b_i – свободные члены уравнения.

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

Система (1) имеет единственное решение, когда система определенная, совместная и однородная. Система называется совместной, если она имеет хотя бы одно решение, и несовместной, если она не имеет решений. Система называется определённой, если она имеет единственное решение, и неопределённой, если она имеет множество решений. Система называется однородной, если все свободные члены равны 0.

Для решения СЛАУ существует две группы методов: точные и приближенные.

Точные методы дают точное решение за конечное количество шагов при условии, если вычисления выполняются без округления. Для приближенных методов количество шагов (итераций) зависит от заданной погрешности вычисления (0<ε<1).

Наиболее распространенные методы решения СЛАУ:

- метод Гаусса;

- метод Жордана-Гаусса;

- метод обратной матрицы;

- метод Крамера;

- Метод Зейделя;

- метод итерации и т.д.

С точки зрения составления алгоритма и программной реализации оптимальным является метод Гаусса (Жордана-Гаусса). Метод обратной матрицы и метод Крамера требуют большего количества операций (трудоемкость метода при увеличении числа неизвестных уравнений растет по экспоненте, поэтому их удобно реализовывать с помощью проблемно-ориентированных сред, в которых имеется инструментарий для работы с матрицей, например MS Excel или Pascal).

Метод Гаусса

Метод Гаусса (метод последовательного исключения неизвестных) основан на приведении исходной системы уравнений к ступенчатому треугольному виду:

a₁₁x₁+a₁₂x₂+a₁₃x₃+…+a_1nx_n=b₁

0+α₂₂x₂+α₂₃x₃+…+α_2nx_n=β₂

0+0+α₃₃x₃+…+α_3nx_n=β₃ (2)

…

0+0+0+0+…+α_mnx_n=β_m

Коэффициенты α_ij системы (2) определяются путем преобразования коэффициентов a_ij системы (1) по формулам:

а) для каждой из строк системы уравнений (2) вычисляется коэффициент

q=a_ik/a_kk, (3)

здесь k-номер ведущей строки;

б) для любой строки верно равенство

a_ij=a_ij-a_kj*q (4)

При приведении матрицы к ступенчатому виду допускаются следующие элементарные преобразования:

1. Перестановка уравнений местами.

2. Умножение коэффициентов и свободного члена уравнения на отличное от нуля число.

3. Сложение (вычитание) одного уравнения с другим предварительно умноженным на одно и то же, отличное от нуля число.

Данный процесс называется прямым ходом метода Гаусса. Процесс нахождения неизвестных в методе Гаусса называется обратным ходом.

Для обратного хода:

Для любого х_i выполняется следующее равенство

(5)

Алгоритм нахождения значений переменных x_i, по методу Гаусса представляет собой последовательность шагов:

1. Ввод исходных данных.

2. Проверка условия: x₁₁=0.

3. Если x₁₁=0, перестановка уравнений местами.

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

5. Нахождение корня x_n.

6.Нахождение остальных корней (обратный ход).

7. Проверка на достоверность полученных результатов.

Дата добавления: 2015-12-01