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

Видео:Решение систем линейных уравнений, урок 5/5. Итерационные методыСкачать

Решение систем линейных уравнений, урок 5/5. Итерационные методы

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.

Видео:Метод Зейделя Пример РешенияСкачать

Метод Зейделя Пример Решения

Итерационные методы решения системы линейных алгебраических уравнений

В данной статье мы расскажем общие сведения об итерационных методах решения СЛАУ, познакомим с методом Зейделя и Якоби, а также приведем примеры решения систем линейных уравнений при помощи данных методов.

Видео:Метод простой итерации Пример РешенияСкачать

Метод простой итерации Пример Решения

Общие сведения об итерационных методах или методе простой итерации

Метод итерации — это численный и приближенный метод решения СЛАУ.

Суть: нахождение по приближённому значению величины следующего приближения, которое является более точным. Метод позволяет получить значения корней системы с заданной точностью в виде предела последовательности некоторых векторов (итерационный процесс). Характер сходимости и сам факт сходимости метода зависит от выбора начального приближения корня x 0 .

Рассмотрим систему A x = b .

Чтобы применить итерационный метод, необходимо привести систему к эквивалентному виду x = B x + d . Затем выбираем начальное приближение к решению СЛАУ x ( 0 ) = ( x 1 0 , x 2 0 , . . . x m 0 ) и находим последовательность приближений к корню.

Для сходимости итерационного процесса является достаточным заданное условие В 1 . Окончание итерации зависит от того, какой итерационный метод применили.

Видео:Решение слау методом итераций. Метод простых итераций c++.Скачать

Решение слау методом итераций. Метод простых итераций c++.

Метод Якоби

Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 1-го уравнения матрицы выражаем неизвестное x 1 , из 2-го выражаем неизвестное x 2 и т.д.

Результатом служит матрица В , в которой на главной диагонали находятся нулевые элементы, а все остальные вычисляются по формуле:

b i j = — a i j / a i i , i , j = 1 , 2 . . . , n

Элементы (компоненты) вектора d вычисляются по следующей формуле:

d i = b i / a i i , i = 1 , 2 , . . . , n

Расчетная формула метода простой итерации:

x ( n + 1 ) = B x ( x ) + d

Матричная запись (координатная):

x i ( n + 1 ) = b i 1 x n 1 + b i 2 x ( n ) 2 + . . . + b

Критерий окончания в методе Якоби:

x ( n + 1 ) — x ( n ) ε 1 , где ε 1 = 1 — B B ε

В случае если B 1 / 2 , то можно применить более простой критерий окончания итераций:

x ( n + 1 ) — x ( n ) ε

Решить СЛАУ методом Якоби:

10 x 1 + x 2 — x 3 = 11 x 1 + 10 x 2 — x 3 = 10 — x 1 + x 2 + 10 x 3 = 10

Необходимо решить систему с показателем точности ε = 10 — 3 .

Приводим СЛАУ к удобному виду для итерации:

x 1 = — 0 , 1 x 2 + 0 , 1 x 3 + 1 , 1 x 2 = — 0 , 1 x 1 + 0 , 1 x 3 + 1 x 3 = 0 , 1 x 1 — 0 , 1 x 2 + 1

Выбираем начальное приближение, например: x ( 0 ) = 1 , 1 1 1 — вектор правой части.

В таком случае, первая итерация имеет следующий внешний вид:

x 1 ( 1 ) = — 0 , 1 × 1 + 0 , 1 × 1 + 1 , 1 = 1 , 1 x 2 ( 1 ) = — 0 , 1 × 1 , 1 + 0 , 1 + 1 = 0 , 99 x 3 ( 1 ) = 0 , 1 × 1 , 1 — 0 , 1 × 1 + 1 = 1 , 01

Аналогичным способом вычисляются приближения к решению:

x ( 2 ) = 1 , 102 0 , 991 1 , 011 , x ( 3 ) = 1 , 102 0 , 9909 1 , 0111 , x ( 4 ) = 1 , 10202 0 , 99091 1 , 01111

Находим норму матрицы В , для этого используем норму B ∞ .

Поскольку сумма модулей элементов в каждой строке равна 0,2, то B ∞ = 0 , 2 1 / 2 , поэтому можно вычислить критерий окончания итерации:

x ( n + 1 ) — x ( n ) ε

Далее вычисляем нормы разности векторов:

x ( 3 ) — x ( 2 ) ∞ = 0 , 002 , x ( 4 ) — x ( 3 ) ∞ = 0 , 00002 .

Поскольку x ( 4 ) — x ( 3 ) ∞ ε , то можно считать, что мы достигли заданной точности на 4-ой итерации.

x 1 = 1 , 102 ; x 2 = 0 , 991 ; x 3 = 1 ,01 1 .

Видео:Лекция 5, Итерационные методы решения систем линейных уравненийСкачать

Лекция 5, Итерационные методы решения систем линейных уравнений

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

Метод Зейделя — метод является модификацией метода Якоби.

Суть: при вычислении очередного ( n + 1 ) — г о приближения к неизвестному x i при i > 1 используют уже найденные ( n + 1 ) — е приближения к неизвестным x 1 , x 2 , . . . , x i — 1 , а не n — о е приближение, как в методе Якоби.

x i ( n + 1 ) = b i 1 x 1 ( n + 1 ) + b i 2 x 2 ( n + 1 ) + . . . + b i , i — 1 x i — 2 ( n + 1 ) + b i , i + 1 x i + 1 ( n ) +

+ . . . + b i m x m ( n ) + d i

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

Решить СЛАУ методом Зейделя. Пусть матрица системы уравнений А — симметричная и положительно определенная. Следовательно, если выбрать начальное приближение, метод Зейделя сойдется. Дополнительных условий на малость нормы некоторой матрицы не накладывается.

Решим 3 системы уравнений:

2 x 1 + x 2 = 3 x 1 — 2 x 2 = 1 , x 1 + 2 x 2 = 3 2 x 1 — x 2 = 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1

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

x 1 ( n + 1 ) = — 0 , 5 x 2 ( n ) + 1 , 5 x 2 ( n + 1 ) = 0 , 5 x 1 ( n + 1 ) + 0 , 5 , x 1 ( n + 1 ) = — 2 x 2 ( n ) + 3 x 2 ( n + 1 ) = 2 x 1 ( n + 1 ) — 1 , 2 x 1 — 0 , 5 x 2 = 3 2 x 1 + 0 , 5 x 2 = 1 .

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

Вычисляем 3 первых приближения к каждому решению:

1-ая система: x ( 0 ) = 1 , 5 — 0 , 5 , x ( 1 ) = 1 , 75 0 , 375 , x ( 2 ) = 1 , 3125 0 , 1563 , x ( 3 ) = 1 , 4219 0 , 2109

Решение: x 1 = 1 , 4 , x 2 = 0 , 2 . Итерационный процесс сходится.

2-ая система: x ( 0 ) = 3 — 1 , x ( 1 ) = 5 9 , x ( 2 ) = — 15 — 31 , x ( 3 ) = 65 129

Итерационный процесс разошелся.

Решение: x 1 = 1 , x 2 = 2

3-я система: x ( 0 ) = 1 , 5 2 , x ( 1 ) = 2 — 6 , x ( 2 ) = 0 2 , x ( 3 ) = 0 2

Итерационный процесс зациклился.

Решение: x 1 = 1 , x 1 = 2

Видео:2.2 Итерационные методы решения СЛАУ (Якоби, Зейделя, релаксации)Скачать

2.2 Итерационные методы решения СЛАУ (Якоби, Зейделя, релаксации)

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

Если А — симметричная и положительно определенная, то СЛАУ приводят к эквивалентному виду:

x = x — τ ( A x — b ) , τ — итерационный параметр.

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

x ( n + 1 ) = x ( n ) — τ ( A x n — b ) .

Здесь B = E — τ A и параметр τ > 0 выбирают таким образом, чтобы по возможности сделать максимальной величину B 2 .

Пусть λ m i n и λ m a x — максимальные и минимальные собственные значения матрицы А .

τ = 2 / ( λ m i n + λ m a x ) — оптимальный выбор параметра. В этом случае B 2 принимает минимальное значение, которое равняется ( λ m i n + λ m a x ) / ( λ m i n — λ m a x ) .

Видео:9 Метод Зейделя Ручной счет Решение системы линейных уравнений СЛАУСкачать

9 Метод Зейделя Ручной счет Решение системы линейных уравнений СЛАУ

Методы Зейделя и простой итерации

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

Методы Зейделя и простой итерации — это методы решения систем линейных алгебраических уравнений при помощи итераций.

Видео:10 Численные методы решения нелинейных уравненийСкачать

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

Методы решения систем линейных алгебраических уравнений

Методы решения систем линейных алгебраических уравнений подразделяются на прямые, являющиеся точными, и итерационные, которые являются приближёнными. Прямые методы базируются на исполнении не бесконечного количества арифметических действий. В качестве примера таких методов можно привести метод обратной матрицы, метод Гаусса, метод Гаусса-Жордана, метод прогонки для трех диагональных матриц и так далее. Сущность итерационных методов состоит в том, чтобы путём последовательных приближений найти решение системы с требуемой точностью. Наиболее распространёнными итерационными методами считаются метод простых итераций и метод Зейделя. Они фактически являются эквивалентными, но конечно имеют и отличия.

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

В итерационных методах обычно присутствуют следующие основные этапы:

  1. Приведение исходной системы вида $ ¯A * ¯x = ¯b $ к итерационной форме.
  2. Осуществление проверки условия сходимости.
  3. Реализация решения системы выбранным методом.

Видео:Лекция 4.005 по выч. методам ИВТ | Итерационные методы решения СЛАУ (форма Якоби). Метод Зейделя.Скачать

Лекция 4.005 по выч. методам ИВТ | Итерационные методы решения СЛАУ (форма Якоби). Метод Зейделя.

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

Для систем общего вида должно выполняться тождество m = n, где m — это число уравнений в системе, а n — это количество неизвестных.

То есть, нет смысла в решении не доопределенных (m меньше n) и переопределенных (m больше n) систем уравнений, так как их можно свести за счёт элементарных алгебраических преобразований к нормальным (m=n) системам линейных уравнений. Иначе говоря, когда присутствует «ненормальная» система уравнений, то перед началом использования метода простых итераций, следует преобразовать её в нормальную.

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

Систему линейных уравнений можно записать в матричной форме, где:

  • A является матрицей коэффициентов.
  • b является вектором свободных членов.
  • x является вектором неизвестных.

В качестве примера рассмотрим следующую систему:

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

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

Представим её в матричной форме:

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

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

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

Преобразование в итерационный вид может быть реализована по следующим формулам:

$c_ = -a_ / a_$ $D_i = b_i / a_$ где i, j = 1,2,3…

Необходимо заметить, что диагональные компоненты новой матрицы обнуляются, хотя должны быть равны -1. В результате для рассматриваемой системы получается:

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

Рисунок 3. Матрица. Автор24 — интернет-биржа студенческих работ

Если выполнять преобразование исходной системы к итерационной форме, то она не удовлетворит условию сходимости:

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

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

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

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

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

Рисунок 5. Матрица. Автор24 — интернет-биржа студенческих работ

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

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

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

Здесь $x_1, x_2, x_3$ являются приближениями, которые получаются на текущем шаге итерации за счет приближений, найденных на предыдущей итерации — $x^0_1, x^0_2, x^0_3$.

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

$Max|x_i – x^0_i|$ ∠ $ε$

Здесь ε является требуемой точностью.

Видео:8 Метод простой итерации Ручной счет Решение системы линейных уравнений СЛАУСкачать

8 Метод простой итерации Ручной счет Решение системы линейных уравнений СЛАУ

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

Как уже отмечалось выше, метод простых итераций и метод Зейделя, по своей сути, являются идентичными. Разница заключается в том, что в методе Зейделя вычисление вектора приближений на текущей итерации выполняется с применением данных, которые были получены ни только на предыдущей, но и на исполняемой итерации. Это означает, что элемент x1 определяется через x2 и x3, величины которых были рассчитаны на предыдущей итерации, а последующий элемент x2 уже рассчитывается на основании x1, найденного именно на текущей итерации, и x3, вычисленного на предыдущей. Иначе говоря, данные в методе Зейделя для определения вектора X используются в процессе расчётов по мере их вычисления. А в методе простых итераций применяются данные, которые были получены именно на предыдущей итерации.

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

Ниже представлена программная реализация метода Зейделя:

Procedure Zeidel(C:array of array of real;d:array of real;n:integer);

📺 Видео

6 способов в одном видеоСкачать

6 способов в одном видео

Система линейных уравнений. Общее решение. Метод ГауссаСкачать

Система линейных уравнений.  Общее решение. Метод Гаусса

Вычислительная математика, 5 семестр. Лекция 4Скачать

Вычислительная математика, 5 семестр. Лекция 4

Вычислительная математика. Лекция 4. Решение нелинейных уравнений и систем уравненийСкачать

Вычислительная математика. Лекция 4. Решение нелинейных уравнений и систем уравнений

Метод Ньютона (метод касательных) Пример РешенияСкачать

Метод Ньютона (метод касательных) Пример Решения

Метод Гуасса Зейделя, градиентный методСкачать

Метод Гуасса Зейделя, градиентный метод

Вычислительная математика 3 Итерационные методы решения СЛАУСкачать

Вычислительная математика 3 Итерационные методы решения СЛАУ

4.2 Решение систем нелинейных уравнений. МетодыСкачать

4.2 Решение систем нелинейных уравнений. Методы

2.1 Точные методы решения СЛАУ (Крамера, Гаусса, Жордана, прогонки)Скачать

2.1 Точные методы решения СЛАУ (Крамера, Гаусса, Жордана, прогонки)

Численные методы. Лекция 7Скачать

Численные методы. Лекция 7
Поделиться или сохранить к себе: