Решить систему уравнений методом гаусса зейделя

1.2.3. Метод Зейделя (метод Гаусса-Зейделя, метод последовательных замещений)

Метод Зейделя представляет собой некоторую модификацию метода простой итерации. Основная его идея заключается в том, что при вычислении (k+1)-го приближения неизвестной xi учитываются уже вычисленные ранее (k+1) – е приближения неизвестных x1, х2, .

В этом методе, как и в методе простой итерации, необходимо привести систему к виду (3), чтобы диагональные коэффициенты были максимальными по модулю, и проверить условия сходимости. Если условия сходимости не выполняются, то нужно произвести элементарные преобразования (см. п. 4). Пусть дана система из трех линейных уравнений. Приведем ее к виду (3). Выберем произвольно начальные приближения корней: х1(0), х2(0), х3(0), стараясь, чтобы они в какой-то мере соответствовали искомым неизвестным. За нулевое приближение можно принять столбец свободных членов, т. е. х(0) = b

(т. е. x1(0)=b1, x2(0)=b2, x3(0)=b3). Найдем Первое приближение х(1) по формулам:

Следует обратить внимание на особенность метода Зейделя, которая состоит в том, что полученное в первом уравнении значение х1(l) сразу же используется во втором уравнении, а значения х1(1), х2(1) – в третьем уравнении и т. д. То есть все найденные значения х1(1) подставляются в уравнения для нахождения хi+1(1) [6, 8].

Рабочие формулы для метода Зейделя для системы трех уравнений имеют следующий вид:

Запишем в общем виде для системы n-уравнений рабочие формулы:

Заметим, что теорема сходимости для метода простой итерации справедлива и для метода Зейделя.

Зададим определенную точность решения e, по достижении которой итерационный процесс завершается, т. е. решение продолжается до тех пор, пока не будет выполнено условие для всех уравнений: где i=1,2,3,…,n.

Пример №2. Методом Зейделя решить систему с точностью e = 10-3:

1. Приведем систему к виду:

2. В качестве начального вектора х(0) возьмем элементы столбца свободных членов, округлив их значения до двух знаков после запятой:

3. Проведем итерации методом Зейделя. При k = 1

.

При вычислении х2(1) используем уже полученное значение х1(1) =

.

При вычислении х3(1) используем значения х1(1) и х2(1):

Наконец, используя значения х1(1), х2(1), х3(1), получаем:

Аналогичным образом ведем вычисления при k=2 и k=3. При k= 2:

Найдем модули разностей значений при k = 2:

Они меньше заданного числа e, поэтому в качестве решения возьмем: x1 = 0,80006, x2 = 1,00002, x3 = 1,19999, x4 = 1,40000.

Метод Гаусса–Зейделя

Одним из самых распространенных итерационных методов, отличающийся простотой и легкостью программирования, является метод Гаусса–Зейделя.

Проиллюстрируем сначала этот метод па примере решения системы

(2.27)

Предположим, что диагональные элементы а11, а22, а33отличны от нуля (в противном случае можно переставить уравнения). Выразим неизвестные х1, х2и х3 соответственно из первого, второго и третьего уравнений системы (2.27):

(2.28)

(2.29)

(2.30)

Зададим некоторые начальные (нулевые) приближения значений неизвестных: Подставляя эти значения в правую часть выражения (2.28), получаем новое (первое) приближение для х1:

Используя это значение для x1 и приближение для х3, находим из (2.29) первое приближение для х2:

И наконец, используя вычисленные значения находим с помощью выражения (2.30) первое приближение для х3:

На этом заканчивается первая итерация решения системы (2.28) — (2.30). Теперь с помощью значений х1(1), х2(1)и х3(1)можно таким же способом провести вторую итерацию, в результате которой будут найдены вторые приближения к решению: х1 = х1 (2), х2 = х2(2)и х3 = х3(2)и т.д.

Приближение с номером kможно вычислить, зная приближение с номером k– 1, как

Итерационный процесс продолжается до тех пор, пока значения х1(k), х2(k)и х3(k)не станут близкими с заданной погрешностью к значениям х1(k-1), х2(k-1)и х3(k-1).

Пример. Решить с помощью метода Гаусса – Зейделя следующую систему уравнений:

Легко проверить, что решение данной системы следующее: х1 = х2 = х3 = 1.

Решение. Выразим неизвестные х1, х2и х3соответственно из первого, второго и третьего уравнений:

В качестве начального приближения (как это обычно делается) примем х1= 0, х2 = 0, х3 = 0. Найдем новые приближения неизвестных:

Аналогично вычислим следующие приближения:

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

Рассмотрим теперь систему п линейных уравнений с п неизвестными. Запишем ее в виде

Здесь также будем предполагать, что все диагональные элементы отличны от нуля. Тогда в соответствии с методом Гаусса – Зейделя k-e приближение к решению можно представить в виде

(2.31)

Итерационный процесс продолжается до тех пор, пока все значения не станут близкими к , т.е. критерием завершения итераций является одно из условий (2.21) – (2.24).

Для сходимости итерационного процесса (2.31) достаточно, чтобы модули диагональных коэффициентов для каждого уравнения системы были не меньше сумм модулей всех остальных коэффициентов (преобладание диагональных элементов):

(2.32)

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

Алгоритм решения системы п линейных уравнений методом Гаусса – Зейделя представлен на рис.2.6. В качестве исходных данных вводят п, коэффициенты и правые части уравнений системы, погрешность ε, максимально допустимое число итераций М, а также начальные приближения переменных xi(i=1,2,…,n).Отметим, что начальные приближения можно не вводить в компьютер, а полагать их равными некоторым значениям (например, нулю). Критерием завершения итераций выбрано условие (2.22), в котором через δобозначена максимальная абсолютная величина разности и :

Для удобства чтения структурограммы объясним другие обозначения: k— порядковый номер итерации; i– номер уравнения, а также переменного, которое вычисляется в соответствующем цикле; j– номер члена вида или в правой части соотношения (2.31). Итерационный процесс прекращается либо при δ Будет полезно почитать по теме:

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

Вы будете перенаправлены на Автор24

Решение системы уравнений методом Гаусса-Зейделя — это решение системы уравнений при помощи последовательных замещений, которые считаются стандартным итерационным методом решения системы линейных уравнений.

Введение

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

• Точные методы.
• Итерационные методы.

Точные методы решения, такие как, к примеру, метод Гаусса, способны определить точные значения корней СЛАУ, причём при правильной организации программы точность может определяться лишь погрешностями, которые сопряжены с округлениями и представлениями чисел в электронных вычислительных машинах (ЭВМ).

Итерационные методики решения СЛАУ могут быть охарактеризованы тем фактом, что точное решение системы они способны определить только в качестве предела определённой бесконечной очерёдности векторов. Исходное приближение при этом должно быть найдено каким-нибудь иным методом или задано произвольно. При исполнении заданных требований может быть получен оперативно сходящийся к решению итерационный процесс. К данному типу методологий могут быть отнесены метод итераций и метод Зейделя.

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

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

Рисунок 1. Система уравнений. Автор24 — интернет-биржа студенческих работ

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

Готовые работы на аналогичную тему

Приведённая выше система уравнений может быть записана в матрично-векторной форме:

Здесь А является матрицей коэффициентов системы, которая содержит n строк и n столбцов. В является заданным вектором правых частей. Х является искомым вектором.

Метод Гаусса базируется на известном из обычного школьного курса алгебры методе исключений. Путём комбинирования каким-нибудь образом уравнений системы, можно добиться того, что во всех уравнениях, кроме одного, исключается одна неизвестная. Далее исключаются следующая неизвестная, третья и так далее.

Пусть имеется система уравнений размера n х n. Алгоритм Гауссова исключения имеет в своём составе несколько шагов. Если система записана в указанном выше исходном виде, то первым шагом станет исключение х из последних n-1 уравнений. Это может быть достигнуто путём вычитания из второго уравнения первого, умноженного на $а_ <21>/ а_<11>$, из третьего уравнения первого, умноженного на $а_ <31>/ а_<11>$, и так далее. В результате этого процесса получается преобразованная система уравнений.

Рисунок 2. Преобразованная система уравнений. Автор24 — интернет-биржа студенческих работ

Если теперь применить такой же самый процесс к последним n-1 уравнениям данной системы, то можно исключить $х_2$ из последних n — 2 уравнений и так далее, пока вся система не превратится в треугольную форму. В этой форме верхние индексы показывают, какое количество раз менялись соответствующие коэффициенты. Этим завершается фаза, которая считается прямым исключением (или приведением к треугольной форме) алгоритма гауссова исключения. Решение треугольной системы может быть легко получено на фазе обратной подстановки, при которой уравнения, приведённой выше системы, могут решаться в обратном порядке.

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

Метод Зейделя является некоторой модификацией метода простой итерации. Главная его идея состоит в том, что при вычислении (k+1)-го приближения неизвестной xi должны учитываться уже вычисленные ранее (k+1) – е приближения неизвестных $х_1, х_2, . х_$. В данном методе, аналогично методу простой итерации, следует привести систему к определённому виду, чтобы диагональные коэффициенты были максимальными по модулю, а далее нужно проверить условия сходимости. Условия сходимости метода Зейделя можно сформулировать в следующем виде. Для того чтобы итерационный процесс удовлетворял условиям сходимости, необходимо и достаточно, чтобы суммарная величина абсолютных значений компонентов каждой строки (за исключением диагональной строки) была меньше, чем абсолютное значение диагонального компонента соответствующей строки.

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

при этом они должны хотя бы в какой-то мере соответствовать искомым неизвестным. За нулевое приближение может быть принят столбец свободных членов, то есть х(0) = b, а именно x1(0)=b1, x2(0)=b2, x3(0)=b3. Определим первое приближение х(1) по формулам:

Рисунок 3. Формулы. Автор24 — интернет-биржа студенческих работ

Необходимо учитывать особенность метода Зейделя, состоящую в том, что найденное в первом уравнении значение х1(l) сразу же применяется во втором уравнении, а значения х1(1), х2(1) применяются в третьем уравнении и так далее. То есть все найденные значения х1(1) необходимо подставить в уравнения для определения хi+1(1).

Действующие формулы метода Зейделя для системы трех уравнений будут иметь следующий вид:

Рисунок 4. Формулы. Автор24 — интернет-биржа студенческих работ

Для системы из n-уравнений рабочие формулы имеют следующий вид:

Рисунок 5. Формулы. Автор24 — интернет-биржа студенческих работ

Необходимо отметить, что теорема сходимости для метода простой итерации является справедливой и для метода Зейделя. Следует задать необходимую точность решения «e», при достижении которой итерационный процесс должен быть завершён. То есть, решение необходимо осуществлять до тех пор, пока не будет исполнено условие для каждого из уравнений:

Рисунок 6. Формула. Автор24 — интернет-биржа студенческих работ