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

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

В общем виде систему линейных алгебраических уравнений записывают в виде:

Ax = f,

где А – матрица n xn;

x = (x₁, x₂, …, x_n) – искомый вектор;

f = (f₁, f₂, …, f_n) – заданный вектор.

Предполагается, что определитель Δ ≠ 0, следовательно решение х существует и единственно.

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

1. по формулам Крамера;

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

Известное из курса высшей алгебры правило Крамера для решения систем линейных алгебраических уравнений (СЛАУ) на практике применяется крайне редко, т.к. требует порядка m! · m арифметических операций для решения системы с m неизвестными.

Используемые практически методы решения СЛАУ можно разделить на две большие группы: так называемые точные методы и методы последовательных приближений (или итерационные).

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

При этом, конечно, предполагается, что коэффициенты и правые части системы известны точно, а все вычисления производятся без округлений.

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

Чаще всего точные методы включают в себя два этапа:

I этап – система преобразуется к тому или иному простому виду (прямой ход);

II этап – решается упрощенная система и находятся значения неизвестных (обратный ход).

Итерационные методы характеризуются тем, что с самого начала задаются какими-то приближенными значениями неизвестных. Из этих приближенных значений тем или иным способом получают новые " улучшенные" приближенные значения. С новыми приближенными значениями поступают точно так же и т.д.

При выполнении определенных условий можно прийти, вообще говоря, после бесконечного числа шагов к точному решению.

Алгоритмы итерационных методов, как правило, очень просты, что объясняет их применимость для решения систем с большим (до 10⁶ и более) числом неизвестных.

Метод Гаусса

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

Метод Гаусса рассматривается в школьном курсе математики как один из основных методов решения систем линейных уравнений. Существует несколько модификаций этого метода.

Рассмотрим схему единственного деления.

Пусть дана система линейных уравнений:

(1)

Будем полагать, что а₁₁ < > 0 (путем перестановки переменных и уравнений всегда можно добиться выполнения этого условия, поскольку определитель ∆ ≠ 0, и, следовательно, всегда найдется уравнение, в котором а_ij ≠ 0).

Из первого уравнения системы (1) выразим х₁:

х₁ = α ₁₂х₂ + α ₁₃х₃ + α ₁₄, (2)

где

α _1k =‑ (k = 2, 3, 4).

Подставляя (2) во второе и третье уравнения системы (1), придем к следующей системе уравнений:

Полагая теперь, что , выразим х₂ из первого уравнения системы (3):

х₂= α ₂₃х₃ + α ₂₄, (4)

где

α _2k =‑ (k = 3, 4).

где

Из (5) определим х₃:

х₃ = α ₃₄, (6)

где

уравнение (6) является итоговым в прямом ходе.

Объединяя уравнения (2), (4) и (6), получим треугольную систему:

из которой легко найти значения переменных.

Приведение исходной системы (1) к треугольному виду (7) называется прямым ходом; вычисление значений переменных по формулам (7) – обратным.

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

Одной из форм заключительного контроля является непосредственная проверка полученного решения путем подстановки найденных значений неизвестных в исходную систему уравнений (1).

Если все вычисления были точными, то в результате подстановки должны получиться нули.

Если же в процессе вычислений допускались округления, то будут получаться числа d₁, d₂, d₃, отличные от нуля и называемые невязками.

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

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