Метод зейделя решения слау. Метод Зейделя-Гаусса

Метод Зейделя (второе название - Гаусса-Зейделя) - это классический интернациональный метод, при помощи которого можно решать различные системы Сейчас мы расскажем об этом более детально.

Суть работы

Данный способ является своеобразной упрощенной модификацией метода Якоби. Инновация состоит в том, что новое значение (і) используется сразу же после получения, а не после очередной итерации. Помимо этого, четко определены условия сходимости и окончания, нарушение которых приведет к неправильному ответу уравнения. Метод Зейделя, пример которого мы предоставили на картинке, не только упрощает процесс решения, но также ускоряет его. Поэтому он активно используется программистами для создания и решения сложных систем.

Метод Зейделя. "Паскаль"

Ни одна программист не обходится без математических формул и уравнений. А это значит, что метод Зейделя активно используется в программе "Паскаль" для получения опыта роботы с базовыми элементами. Выглядит все довольно-таки просто: в листе программы создается новый документ, с самого начала вводится условие уравнения и его границы, затем объясняются дополнительные сменные элементы (при условии их наличия), после этого прописывается проверка на совместимость. Если она положительна, то выводится сам алгоритм решения, а уже потом вывод могут включать несколько этапов решения, каждая часть которого имеет свой алгоритм, обязательные составные, сменные элементы и базовые формулы. Все это записывается исключительно на английском языке, без возможных аналогов. Решение уравнения будет выводиться в виде готовой формулы или числа после сохранения всех данных.

"С++"

Метод Зейделя также широко используется в программе "С++", но здесь все совсем иначе, чем в "Паскале". Уравнение в "С++" начинается не с условия всей задачи, а с условия окончания, которое прописывается в три-четыре этапа с конечным выводом результата. Далее прописывается сам ход решения при помощи данного метода, детально описывая все неизвестные, после чего выводится формула для того, чтобы доказать равенство между двумя результатами уравнения. Условием есть то, что каждое значение предыдущего является необходимым для решения последующего. Учетные записи здесь также ведутся на английском языке, который заменить невозможно. "С++" значительно сложнее "Паскаля", поэтому, не имея базовых знаний, ее не следует использовать изначально.

Подведем итоги

Итак, метод Зейделя - это специальный способ, благодаря которому можно решать системы линейных уравнений любой сложности. Чаще всего он является базовым для таких программ, как "Паскаль" и "С++". Это своеобразная улучшенная модификация метода Якоби, которая исключает вариант использования дополнительных формул, но при этом имеет четкие условия сходимости и окончания. Строго установленные критерии упрощают весь процесс работы, так как в случае невыполнения одного из условий программа, будь то или "Паскаль", или "С++", просто-напросто откажется от дальнейшего решения задачи.

Метод Зейделя представляет модификацию метода простой итерации. Идея состоит в том, что на каждой к-й итерации при вычислении значения переменной используются значения переменных
, . . . . ,
, уже подсчитанных на этой же к-й итерации.

Пример:

Зададимся исходным приближением
и ε = 0,001.

Делаем первую итерацию по методу Зейделя

Занесем результаты расчетов в таблицу

№ итерации (к )

Метод Зейделя, имеет, как правило, лучшую сходимость, чем метод простой итерации. И сходится в ряде случаев даже тогда, когда метод простой итерации не обеспечивает сходимость. Но (значительно реже) бывает и наоборот.

Преимущества и недостатки итерационных методов

Преимущества:

    имеют простую вычислительную процедуру;

    не требуют сложных специальных процедур для экономии памяти ЭВМ под нулевые элементы матрицы коэффициентов, как метод Гаусса;

    самоисправление ошибок.

Недостатки:

    не всегда могут решить систему уравнений (требуется выполнение условий сходимости)

    сходимость итерационных процессов может быть медленной;

    корни системы могут быть определены только приближенно с точностью ε.

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

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

Р г i иQ г i - активная и реактивная мощности, генерируемые вi -м узле;

Р нi иQ н i - активная и реактивная мощности нагрузки вi -м узле;

Р уi иQ у i - активные и реактивные потоки мощности из узлаj к узлуj .

Уравнения балансов активных и реактивных мощностей в узле i

;

,

где
означает, что узелj ‚ принадлежит множеству всех узлов, которые связаны с узломi .

Формулы для потоков активной и реактивной мощностей от узла к узлу j следующие:

Применяются две системы координат, в которых могут проводиться расчеты:

    прямоугольная система координат (в комплексном виде);

    полярная система координат (через тригонометрические функции).

В полярной системе координат выражения для потоков мощности имеют следующий вид:

Y – заданные проходимости схемы замещения системы;

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

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

Для решения систем нелинейных уравнений используются только итерационные методы. В том числе для решения систем нелинейных уравнений могут использоваться методы простой итерации и Зейделя при условии их сходимости.

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

;

.

Приведем к виду удобному для итерации

;

Результаты расчетов обоими методами сведем в таблицу (ε=0,001)

Метод простой итерации

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

№ итерации

№ итерации

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

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

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

Системой m линейных уравнений с n неизвестными называется система вида:

где aij и bi (i=1,…,m; b=1,…,n) – некоторые известные числа, а x1,…,xn – неизвестные. В обозначении коэффициентов aij первый индекс i обозначает номер уравнения, а второй j – номер неизвестного, при котором стоит этот коэффициент.

Коэффициенты при неизвестных будем записывать в виде матрицы, которую назовём матрицей системы.

Числа, стоящие в правых частях уравнений, b 1 ,…,b m называются свободными членами.

Совокупность n чисел c 1 ,…,c n называется решением данной системы, если каждое уравнение системы обращается в равенство после подстановки в него чисел c 1 ,…,c n вместо соответствующих неизвестных x 1 ,…,x n .

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

1. Система может иметь единственное решение.

2. Система может иметь бесконечное множество решений. Например,

решением этой системы является любая пара чисел, отличающихся знаком.

3. И третий случай, когда система вообще не имеет решения. Например,

если бы решение существовало, то x 1 + x 2 равнялось бы одновременно нулю и единице.

Система линейных уравнений, имеющая хотя бы одно решение, называется совместной. В противном случае, т.е. если система не имеет решений, то она называется несовместной.

Рассмотрим один из способов нахождения решений системы.

Метод Зейделя для решения СЛАУ

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

с квадратной невырожденной матрицей A, необходимо предварительно преобразовать эту систему к виду

Здесь B – квадратная матрица с элементами b ij (i, j = 1, 2, …, n), c – вектор-столбец с элементами c ij (i = 1, 2, …, n).

В развернутой форме записи система имеет следующий вид:

x 1 = b 11x1 + b 12x2 + b 13x3 + … + b 1nxn + c 1

x 2 = b 21x1 + b 22x2 + b 23x3 + … + b 2nxn + c 2

. . . . . . . . . . . . . . . . .

x n = b n1x1 + b n2x2 + b n3x3 + … + b nnxn + c n

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

Самый простой способ приведения системы к виду, удобному для итераций, состоит в следующем. Из первого уравнения системы выразим неизвестное x1:

x 1 =а 11–1 (b 1 – a 12x2 – a 13x3 – … – a 1nxn),

из второго уравнения – неизвестное x2:

x 2 = a21–1 (b 2 – a 22x2 – a 23x3 – … – a 2nxn),

и т. д. В результате получим систему

x 1 = b 12x2 + b 13x3 +… + b 1,n–1xn–1 + b 1nxn + c 1 ,

x 2 = b 21x1 + b 23x3 +… + b 2,n–1xn–1 + b 2nxn + c 2 ,

x 3 = b 31x1 + b 32x2 + … + b 3,n–1xn–1 + b 3nxn + c 3 ,

. . . . . . . . . . . . . . . . . . . . . . .

x n = b n1x1 + b n2x2 +b n3x3 +… + b n,n–1xn–1 + c n ,

в которой на главной диагонали матрицы B находятся нулевые элементы. Остальные элементы выражаются по формулам

b ij = –a ij / a ii , c i = b i / a ii (i, j = 1, 2, …, n, j ≠ i)

Конечно, для возможности выполнения указанного преобразования необходимо, чтобы диагональные элементы матрицы A были ненулевыми.

Описание метода. Введем нижнюю и верхнюю треугольные матрицы

0 0 0 … 0 0 b 12 b 13 … b 1 n

b 21 0 0 … 0 0 0 b 23 … b 2 n

B 1 = b 31 b 32 0 … 0 , B­­ 2 = 0 0 0 … b 3 n

. . . . . . . . . . . . . .

b n 1 b n 2 b n 3 …0 0 0 0 … 0

Заметим, что B = B 1 + B 2 и поэтому решение x исходной системы удовлетворяет равенству

x = B 1x + B 2 x + c .

Выберем начальное приближение x(0) = T . Подставляя его в правую часть равенства при верхней треугольной матрице B 2 и вычисляя полученное выражение, находим первое приближение

x(1) = B 1x (0) + B 2x (1)

Подставляя приближение x(1), получим

x(2) = B 1x (1) + B 2x (2)

x(k+1) = B 1 (k+1) + B 2 (k) + c

или в развернутой форме записи

x 1 (k +1) = b 12 x 2 (k ) + b 13 x 2 (k ) + … + b 1 n x n (k ) + c 1 ,

x 2 (k +1) = b 21 x 1 (k +1) + b 23 x 3 (k ) + … + b 2 n x n (k ) + c 2 ,

x 3 (k +1) = b 31 x 1 (k +1) + b 32 x 2 (k +1) + … + b 3 n x n (k ) + c 3 ,

. . . . . . . . . . . . . . . . . . . . . . . . . .

x n (k +1) = b n 1 x 1 (k +1) + b n 2 x 2 (k +1) + b n 3 x 3 (k +1) + … + c n .

Объединив приведение системы к виду, удобному для итераций и метод Зейделя в одну формулу, получим

xi(k+1) = xi(k) – aii–1(∑j=1i–1 aijxj(k+1) + ∑j=1n aijxi(k) – bi).

Тогда достаточным условием сходимоти метода Зейделя будет

∑j=1, j≠i n | aij | < | aii |

(условие доминированния диагонали).

Метод Зейделя иногда называют также методом Гаусса-Зейделя, процессом Либмана, методом последовательных замещений.

Этот метод является модификацией метода простых итераций и в некоторых случаях приводит к более быстрой сходимости.

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

Теорема о достаточном условии сходимости метода Зейделя . Если для системы какая-либо норма матрицы меньше единицы, т.е. ,то процесс последовательных приближений (10.15) сходится к единственному решению исходной системы при любом начальном приближении .

Записывая (1) в матричной форме, получаем

где являются разложениями матрицы

Преобразуя (2) к виду , получаем матричную форму итерационного процесса метода Зейделя:

Тогда достаточное, а также необходимое и достаточное условия сходимости будут соответственно такими:

Замечания:

1. Для обеспечения сходимости метода Зейделя требуется преобразовать систему к виду с преобладанием диагональных элементов в матрице А (метод простых итераций).

2. Процесс (2) называется последовательным итерированием, так как на каждой итерации полученные из предыдущих уравнений значения подставляются в последующие. Как правило, метод Зейделя обеспечивает лучшую сходимость, чем метод простых итераций (за счет накопления информации, полученной при решении предыдущих уравнений). Метод Зейделя может сходиться, если расходится метод простых итераций, и наоборот.

3. Преимуществом метода Зейделя, как и метода простых итераций, является его "самоисправляемость".

4. Метод Зейделя имеет преимущества перед методом простых итераций, так как он всегда сходится для нормальных систем линейных алгебраических уравнений, т.е. таких систем, в которых матрица А является симметрической и положительно определенной. Систему линейных алгебраических уравнений с невырожденной матрицей А всегда можно преобразовать к нормальной, если ее умножить слева на матрицу . Система является нормальной.

Под методом Зейделя обычно понимается такое видоизменение метода простых итераций (6.3) решения СЛАУ, приведенных к виду (6.2), при котором для подсчета -й компоненты -го приближения к искомому вектору используются уже найденные на этом, т.е. -м шаге, новые значения первых компонент. Это означает, что если система (6.1) тем или иным способом сведена к системе (6.2) с матрицей коэффициентов и вектором свободных членов , то приближения к ее решению по методу Зейделя определяются системой равенств

(6.12)

где , a – компоненты заданного (выбранного) начального вектора .

Остановимся подробнее на случае, когда приведение системы (6.1) к виду (6.2) основано на представлении (6.7), т. е. когда метод Зейделя есть модификация метода Якоби. Запись соответствующих расчетных формул здесь сводится к верхней индексации системы (6.10) по типу (6.12):

(6.13)

где ; задается.

Для анализа сходимости метода Зейделя (6.13) обратимся к его векторно-матричной форме. Легко видеть, что если неявный вид метода Якоби, вытекающий из представления (6.7) системы (6.1), есть

(сравните с (6.9)),

то равнозначный (6.13) неявный вид метода Зейделя в векторно-матричных обозначениях суть

.

Следовательно, тот же вектор ,который фигурирует в левой части совокупности равенств (6.13), может быть получен по формуле

(6.14)

Последнее выражение определяет не что иное, как МПИ (6.3) для системы вида (6.2), где

т. е. результат применения одного шага метода Зейделя (6.13), полученного на основе – разложения матрицы ,можно расценивать, как шаг МПИ для эквивалентной (6.1) задачи о неподвижной точке

(разумеется, если треугольная матрица обратима). Эта связь между методом Зейделя и методом простых итераций позволяет легко переформулировать некоторые утверждения о сходимости МПИ применительно к методу Зейделя (6.13).

Теорема 6.5. Для сходимости метода Зейделя (6.13) необходимо и достаточно, чтобы все корни уравнения

(6.16)

были по модулю меньше единицы.

Прямым следствием теоремы 6.2 для метода Зейделя (6.13) является следующая теорема.

Теорема 6.6. Пусть . Тогда при любом начальном векторе метод Зейделя (6.13) сходится к решению системы (6.1) и справедливы оценки погрешности

Ясно, что для непосредственного использования оценок (6.17) нужно предварительно выполнить обращение треугольной матрицы и перемножить матрицы и . В таком случае частично теряется смысл в поэлементной реализации метода Зейделя (6.13) ;вместо этого можно проводить итерации по формуле (6.14) до тех пор, пока не выполнится условие , где – требуемая точность. В частности, такой подход может быть рекомендован при решении СЛАУ методом Зейделя на компьютерах с векторной обработкой информации.

Более подходящие для использования оценки погрешности метода Зейделя (6.13) можно получить, разлагая матрицу (см. (6.11)) в сумму двух строго треугольных матриц, т.е. полагая

,где

, .

С ними эквивалентное (6.1) уравнение (6.2) приобретает вид ,

т.е. для решения будет точным равенство ,

а метод Зейделя (6.13) – соответственно .

Из двух последних равенств получаем следующее:

Это равенство, записанное в виде (6.18)

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

Теорема 6.7 .Пусть . Тогда метод Зейделя (6.13) определяет сходящуюся последовательность при любом начальном векторе , и имеет место оценка

Как и у предыдущей, у этой теоремы имеются свои недостатки, затрудняющие ее применение: нужно знать меру близости начального приближения к решению . Ценность ее скорее в том, что в ней фигурирует легко вычисляемый коэффициент связи ошибок результатов двух соседних итерационных шагов, характеризующий быстроту сходимости метода Зейделя (6.13). При организации практических вычислений по формулам (6.13) целесообразнее ориентироваться на следующий результат.

Теорема 6.8. Пусть , (где матрица (6.11)). Тогда для определяемой методом Зейделя (6.13) последовательности приближений справедлива апостериорная оценка погрешности

.

Из теоремы 6.8 вытекает следующая, более удобная на практике, формулировка.

Следствие 6.1. Пусть –первое из натуральных чиселk , с которым при заданном для генерируемой процессом Зейделя (6.13) последовательности векторов некоторых согласованных нормах выполняется равенство .

Отчет по

ЧИСЛЕНННЫМ МЕТОДАМ

Выполнил: студент

Сулейманова Д.И.

Проверила: доцент каф. хим.

кибернетики Кошкина Л.Ю.

Казань, 2012


Тема 1. «Численное решение систем линейных алгебраических уравнений». 3

Постановка задачи. 3

Прямые (точные) методы.. 3-4

Итерационные методы.. 5

Листинг программ. 4

Результаты.. 5

Выводы.. 5

Список литературы.. 5

ТЕМА 2. «ЧИСЛЕННОЕ РЕШЕНИЕ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ»

Постановка задачи

Решить систему линейных алгебраических уравнений:

0,5 1,7 0,3 -0,24
1,6 1,5 -2,3 4,3
3,7 -2,5 3,2 6,5

0,5х 1 +1,7х 2 +0,3х 3 =-0,24

1,6х 1 +1,5х 2 -2,3х 3 =4,3

3,7х 1 -2,5х 2 +3,2х 3 =6,5

Для решения уравнения использовали следующие методы:

1. метод обратной матрицы,

2. метод Крамера,

3. метод Гаусса,

4. метод простых итераций,

5. метод Гаусса-Зейделя.

Решение:

Прямые (точные) методы

1) Метод обратной матрицы: (х=А -1 *В – формула данного метода, где В-вектор свободных членов, А -1 -обратная функция)

А) Для реализации данного метода в электронных таблицах воспользовались математической функцией =МОБР(А1:С3) для определения коэффициента А:

0,3 4,3 1,5 -2,3 6,5 -2,5 3,2 0,5 -0,24
Ввод n, a, b FOR k=1 TO n-1 FOR i=k+1 TO n m=a ik /a kk FOR j=k+1 TO n a ij =a ij -m*a kj b i =b i -m*b k x n =b n /a nn FOR i=n-1 TO 1 шаг - 1 FOR j=i+1 TO n S=∑a ij *x i x i =(b i -s)/a ii Печать x i

Прямой ход

Обратный ход


Выбор главного элемента и перестановка уравнений


1) Метод простых итераций:

А) Выразим х 1 , х 2 , х 3 из уравнений главного определителя, тогда получим:

x 1 =(b 1 -a 12 x 2 -a 13 x 3)/a 11

x 2 =(b 2 -a 21 x 1 -a 23 x 3)/a 22

x 3 =(b 3 -a 31 x 1 -a 32 x 2)/a 33

Б) Зададим начальное (нулевое) приближение x 1 (0) , x 2 (0) , x 3 (0) . Подставляя их, получаем новое приближение.

В) Обозначим k-номер итерации, тогда для n уравнений итерационные формулы можно записать так:

x i (k) = (k-1))

Итерации проводятся до тех пор, пока не будет выполнено условие

|x i (k)-x i (k-1) |

2) Метод Гаусса-Зейделя:

Этот метод представляет собой модификацию метода простых итераций, когда на k-той итерации при j

x i (k) = (k) - (k-1))

Итерационный процесс продолжается до тех пор, пока не будет выполнено условие

|x i (k)-x i (k-1) |

Если условие не выполняется, итерации повторяются, приняв x i (k-1) = x i (k)

Алгоритм метода Гаусса-Зейделя

n-количество уравнений; e-точность; a(n,n)-массив коэффициентов; b(n)-массив свободных членов; x(n)-массив решения. Вводится начальное приближение x(n).


Листинг программ


Sub metod_g()

Dim a(1 To 3, 1 To 3)

a(i, j) = Worksheets("Лист2").Cells(i, j).Value

b(i) = Worksheets("Лист2").Cells(i, 5).Value

For k = 1 To n - 1

For i = k + 1 To n

If Abs(a(i, k)) > Abs(a(g, k)) Then g = i

z = a(g, j): a(g, j) = a(k, j): a(k, j) = z

z = b(g): b(g) = b(k): b(k) = z

For i = k + 1 To n

m = a(i, k) / a(k, k)

For j = k + 1 To n

a(i, j) = a(i, j) - m * a(k, j)

b(i) = b(i) - m * b(k)

x(n) = b(n) / a(n, n)

For i = n - 1 To 1 Step -1

For j = i + 1 To n

s = s + a(i, j) * x(j)

x(i) = (b(i) - s) / a(i, i)

Worksheets("Лист2").Cells(i, 9).Value = x(i)

Sub MPI_SLAY()

Dim a(1 To 3, 1 To 3)

x2 = (b(2) - a(2, 1) * x10 - a(2, 3) * x30) / a(2, 2)

x3 = (b(3) - a(3, 1) * x10 - a(3, 2) * x20) / a(3, 3)

Loop While c > e

With Worksheets("Лист2")

Range("J1").Value = x1

Range("J2").Value = x2

Range("J3").Value = x3

Range("J5").Value = k

Sub GausZeid()

Dim a(1 To 3, 1 To 3)

a(i, j) = Worksheets("Лист3").Cells(i, j).Value

b(i) = Worksheets("Лист3").Cells(i, 5).Value

x10 = 0: x20 = 0: x30 = 0

x1 = (b(1) - a(1, 2) * x20 - a(1, 3) * x30) / a(1, 1)

x2 = (b(2) - a(2, 1) * x1 - a(2, 3) * x30) / a(2, 2)

x3 = (b(3) - a(3, 1) * x1 - a(3, 2) * x2) / a(3, 3)

c = Abs(x1 - x10) + Abs(x2 - x20) + Abs(x3 - x30)


Loop While c > e

With Worksheets("Лист2")

Range("K1").Value = x1

Range("K2").Value = x2

Range("K3").Value = x3

Range("K5").Value = k

Для запуска программ нажать на кнопку или на Run .

Полученный результат находится на Листе 2.

Результаты

Выводы

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

Итерационные методы применяют главным образом для решения задач большой размерности, когда использование прямых методов невозможно из-за ограничений в доступной оперативной памяти ЭВМ или из-за необходимости выполнения чрезмерно большого числа арифметических операций.

В данной работе мы рассмотрели 5 методов решения линейных алгебраических уравнений: метод обратной матрицы, Крамера, Гаусса, простой итерации и Гаусса-Зейделя. Первые 3 метода составляют группу прямых методов. Это аналитические методы, в них отсутствует погрешность метода, но погрешность вычислений неизбежна. Тем не менее, методы обратной матрицы и Крамера достаточно просты в алгоритме, тем более нами было найдено решение трехмерной матрицы (небольшая размерность), значения неизвестных сошлись. Что касается метода Гаусса, алгоритм данного метода достаточно громоздкий. Каждая следующая формула вычисления коэффициентов при преобразовании матрицы содержит результат предыдущей формулы, а значит и ее ошибку при вычислении. Наибольшее влияние на эту ошибку оказывает величина знаменателя (коэффициенты главной диагонали) – она не должна быть равна 0 и малой по абсолютной величине. В нашем случае таких предпосылок нет, метод Гаусса был осуществлен с выбором главного элемента, что дает малые невязки.