Метод зейделя теория кратко. Метод Зейделя-Гаусса. Интернациональный метод

Метод итераций и метод Зейделя

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

или, короче,

. (3.8)

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

Выразим из первого уравнения , из второго , и т. д. Тогда получим эквивалентную систему:

где

Полученную систему запишем так:

(3.9)

и назовем ее системой нормального вида.

Будем решать ее методом последовательных приближений. За нулевое приближение возьмем, например, столбец свободных членов

Подставив в правую часть системы (3.9) значения , получим первое приближение:

.

Затем аналогично второе: и т.д.

Таким образом, зная - e приближение, ()-е приближение вычисляют по формуле:

(3.10)

Если последовательность приближений имеет предел

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

Описанный метод последовательных приближений называется методом итераций. Рабочие формулы метода итераций имеют вид:

(3.11)

Существование предела

гарантирует теорема о достаточном признаке сходимости процесса итераций.

Достаточным условием сходимости итерационных методов является условие

(3.12)

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

Контрольные вопросы

1. К какому виду преобразуют исходную систему для применения метода итераций?

2. В чем преимущество метода итераций перед другими методами?

3. Каковы условия применимости данного метода?

4. Какова скорость сходимости последовательности векторов к решению?

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

6. Какова общая постановка задачи решения систем линейных уравнений?

7. Что такое ранг матрицы?

8. Сформулируйте условие существования решения и условие единственности решения.

9. Что такое эквивалентное преобразование системы? Какие они бывают?

10. Почему при добавлении к строке линейной комбинации других строк решение не меняется?

11. С чем связана необходимость переставлять местами уравнения системы при решении?

12. Когда целесообразно применять метод Гаусса?

13. Какова цель прямого хода в методе Гаусса?

14. Как выполняется обратный ход метода Гаусса?

15. На каком ходе, прямом или обратном, необходимо учитывать условия применения метода Гаусса?

16. Объясните алгоритм схемы единственного деления.

17. Объясните алгоритм схемы с частичным выбором ведущего коэффициента по столбцу.

18. Расскажите о достоинствах и недостатках схемы с полным выбором ведущего коэффициента.

19. Объясните зависимость временных затрат от размера системы.

20. Объясните зависимость ошибок от размера системы.

21. Когда система линейных алгебраических уравнений имеет единственное решение?

22. Каковы недостатки решения системы уравнений по правилу Крамера?

23. Охарактеризуйте точные и приближенные численные методы решения систем линейных алгебраических уравнений.

24. Опишите метод Гаусса с выбором главного элемента.

25. Почему метод простой итерации называется самоисправляющимся?

26. Дайте определение сходимости итерационного процесса.

27. Опишите метод Зейделя.

28. Точные методы решения систем линейных уравнений

29. Приближенные методы решения систем линейных уравнений

30. Правило Крамера.

1. Преобразовать систему к виду одним из описанных способов.

2. Задать начальное приближение решения произвольно или положить , а также малое положительное число (точность). Положить .

3. Произвести расчеты по формуле (1)или (2) и найти .

(1)

4. Если выполнено условие окончания , процесс завершить и в качестве приближенного решения задачи принять . Иначе положить и перейти к пункту 3.

Решение систем нелинейных уравнений (СНУ).

Запишем систему n нелинейных уравнений с n неизвестными (СНУ) в общем виде:

f 1 (x 1 , x 2 , …, x n) = 0

f 2 (x 1 , x 2 , …, x n) = 0 (5.1)

f n (x 1 , x 2 , …, x n) = 0

Эту систему можно записать в компактной, операторной форме:

вектор-функция

вектор неизвестных

Решением системы называется набор значений ,(векторX *), при которых все функции f i равны 0 (система (5.1) обращается в тождество.)

СНУ могут иметь единственное решение, множество решений или вообще не иметь его. Поэтому численное решение СНУ проводят в два этапа:

1 этап – отделение решений.

2 этап – уточнение всех или только нужных решений.

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

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

f 1 (x 1 , x 2) = 0

f 2 (x 1 , x 2) = 0

Для этого необходимо в координатах (x 1 , x 2) построить кривые

f 1 (x 1 ,х 2) = 0, f 2 (x 1 ,х 2) = 0.

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

Имеется два решения.

D 1 – область существования первого решения.

D 1 = {a 1 < x 1 < b 1 , a 2 < x 2 < b 2 }.

Графическое отделение решений СНУ.

Для систем с большим числом неизвестных (n  3) удовлетворительных общих методов определения области существования решения нет. Поэтому при решении СНУ эта область обычно определяется при анализе решаемой задачи, например, исходя из физического смысла неизвестных.

Отделение решений позволяет:

Выявить число решений и область существования каждого из них.

Проанализировать возможность применения выбранного метода решения СНУ в каждой области.

Выбрать начальное приближение решения X (0) из области его существования, так что X (0) D.

При отсутствии информации об области существования решения СНУ выбор начального приближения X (0) проводиться методом проб и ошибок (методом “тыка”).

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

Требуется решить систему нелинейных уравнений . В координатном виде эту задачу можно записать так: , где 1 ≤ k ≤ n .

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

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

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

f 1 (x 1 , x 2 , …, x n) = 0

f 2 (x 1 , x 2 , …, x n) = 0

f n (x 1 , x 2 , …, x n) = 0 (5.1)

эквивалентной системой X=Φ(X) –(5.3) и построении итерационной последовательности

(5.4)-X (k) = Φ(X (k -1)) , где k=1,2,3,… - номер итерации,которая при k→∞ сходится к точному решению.

Здесь - итерирующая вектор-функция, X (0) D – начальное приближение решения.

В развернутом виде формула итерационного процесса (выражение для вычисления очередного k-го приближения решения) имеет вид:

x i. (k) = φ i (x 1 (k-1) , x 2 (k-1) , … , x n (k-1)), .(5.5)

Условие окончания расчета

δ≤ε (5.6)

где ε  заданная точность решения;

δ = (5.7)

Итерационный процесс (5.5) сходиться к точному решению, если в окрестности решения соблюдаются условия сходимости:

Таким образом, для уточнения решения СНУ методом простых итераций нужно найти такое эквивалентное преобразование (5.1) в (5.3), чтобы в области существования решения выполнялись условия (5.9) или (5.10).

В простейшем случае эквивалентную систему можно получать как.

Под методом Зейделя обычно понимается такое видоизменение метода простых итераций (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) последовательности векторов некоторых согласованных нормах выполняется равенство .

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

Пример:

Зададимся исходным приближением
и ε = 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/ (называемый также методом линеаризации или методом касательных) применяется для решения системы нелинейных уравнений. Он эффективен, если известно достаточно хорошее приближение к корням системы нелинейных уравнений.