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

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

или, короче,

. (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. Правило Крамера.

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

ЗЕЙДЕЛЯ МЕТОД

Итерационный метод решения системы линейных алгебраич. уравнений Ах=b. Решение системы х* находится как последовательности вычисляемой по правилу

i=l, 2, ..., п,

где a ij - элементы матрицы А, b i - компоненты вектора b;диагональные элементы матрицы Апредполагаются отличными от нуля. Вычисления (*) отличаются от простой итерации метода лишь тем, что на k-м шаге при вычислении i-й компоненты учитываются вычисленные k-в приближения первых (i-1) компонент.

В матричной записи 3. м. представляется следующим образом. Если А=В+С, где

то соотношение (*) соответствует матричному соотношению x (k) =- В -1 Сх (k-1 ) +В -1 b. З . м. равносилен методу простой итерации, примененному к системе x=-B -1 Cx+B -1 b, эквивалентной исходной. Для сходимости 3. м. необходимо и достаточно, чтобы все собственные значения матрицы В -1 С по модулю были меньше 1. Иначе, чтобы все корни уравнения det(C+Вl)=0 были по модулю меньше 1.

На практике более удобны следующие достаточные условия сходимости 3. м. 1) Пусть при всех i,

д<1. Тогда 3. м. сходится и для

скорости сходимости имеет место оценка:

2) Пусть А- эрмитова положительно определенная . Тогда 3. м. сходится.

З. м. относится к классу релаксации методов, наиболее употребительным из к-рых является сверхрелаксации метод.

Известны модификации 3. м., использующие предварительное исходной системы в эквивалентную ей систему x=Mx+f (см. ).

Метод предложен Л. Зейделем в .

Лит. : Seidеl L., "Abhandl. Bayer. Akad. Wiss. Math.-naturwiss. Kl.", 1874, Bd 11, №3, S. 81 - 108; Бахвалов H. С, Численные методы, 2 изд., М., 1975; Березин И. С, Жидков Н. П., Методы вычислений, 3 изд., т. 1, М., 1966; И Фаддеев Д. К., Фаддеева В. Н., Вычислительные методы линейной алгебры, 2 изд., М.- Л., 1963.

Г. Д. Ким.

Математическая энциклопедия. - М.: Советская энциклопедия . И. М. Виноградов . 1977-1985 .

Смотреть что такое "ЗЕЙДЕЛЯ МЕТОД" в других словарях:

У этого термина существуют и другие значения, см. метод покоординатного спуска. Метод Гаусса Зейделя является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод … Википедия

Метод Гаусса Зейделя является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия

Метод Гаусса Зейделя является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия

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

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

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

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

(2.28)

(2.29)

(2.30)

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

Используя это значение для x 1 и приближение для х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.21) – (2.24).

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

(2.32)

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

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

Для удобства чтения структурограммы объясним другие обозначения: k - порядковый номер итерации; i – номер уравнения, а также переменного, которое вычисляется в соответствующем цикле; j – номер члена вида или в правой части соотношения (2.31). Итерационный процесс прекращается либо при δ < ε , либо при k = М. В последнем случае итерации не сходятся, о чем выдается сообщение. Для завершения цикла, реализующего итерационный процесс, используется переменная l , которая принимает значения 0, 1 и 2, соответственно, при продолжении итераций, при выполнении условия δ < ε и при выполнении условия k = М .

Рис. 2.6. Алгоритм решения системы n линейных уравнений методом Гаусса–Зейделя

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

Суть работы

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

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

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

"С++"

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

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

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

Главная » Части речи » В чем заключается метод зейделя. Метод зейделя решения слау