Приведение системы уравнений к нормальному виду

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

Видео:§31.1 Приведение уравнения кривой к каноническому видуСкачать

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

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

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

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

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

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

Видео:§43 Приведение уравнения плоскости к нормальному видуСкачать

Метод Якоби

Метод Якоби — один из наиболее простых методов приведения системы матрицы к виду, удобному для итерации: из 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 .

Видео:§14 Приведение уравнения прямой к нормальному видуСкачать

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

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

Суть: при вычислении очередного ( 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

Видео:Видеоурок "Приведение к каноническому виду"Скачать

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

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

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 ) .

Видео:Математика без Ху!ни. Метод Гаусса. Совместность системы. Ранг матрицы.Скачать

Отчет по лабораторной работе №2 на тему «Решение систем линейных алгебраических уравнений итерационными методами»

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

«Ижевский государственный технический университет»

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

по дисциплине «Вычислительная математика»

ст. преподаватель кафедры АСОИУ

1 ПОСТАНОВКА ЗАДАЧИ

Написать программу, реализующую алгоритмы:

а) метода простых итераций;

б) метода Зейделя.

с точностью e = 10-12.

В программе требуется:

1) предусмотреть приведение СЛАУ к виду, пригодному для итераций;

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

3) выбрать начальное приближение;

4) сделать априорную оценку количества шагов и подсчитать реальное количество шагов для достижения заданной точности указанных методов;

5) подсчитать апостериорные оценки методов.

Провести сравнительный анализ метода простых итераций и метода Зейделя.

2 МАТЕМАТИЧЕСКАЯ МОДЕЛЬ

2.1 Итерационные методы решения СЛАУ

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

Видео:13. Общие уравнения прямой в пространстве / приведение к каноническому видуСкачать

(1)

Видео:Приведение ДУ 2 порядка в частных производных к каноническому видуСкачать

Запишем систему (1) в матричном виде:

Преобразуем систему (2) тем или иным способом (таких способов существует множество; некоторые из них будут рассмотрены ниже) к эквивалентной ей системе вида:

где x – тот же вектор неизвестных, a, b — некоторые новые матрица и вектор соответственно.

Эта система называется приведенной к нормальному виду. Она пригодна для итерационного процесса.

2.2 Методы простых итераций (МПИ) решения СЛАУ

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

Итерационный процесс (4), начинающийся с некоторого вектора

x(0) =( x ,…, x)Т, будем называть методом простых итераций (МПИ).

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

(5)

Выбор начального приближения

Сходимость МПИ гарантирована при любом начальном векторе x(0). Очевидно, что итераций потребуется меньше, если x(0) ближе к решению x*. Если нет никакой информации о грубом решении задачи (3) или решении близкой задачи, то за x (0) обычно принимают вектор b свободных членов системы (3).

Способы приведения СЛАУ к нормальному виду

Для решения СЛАУ итерационными методами систему (2) нужно привести к эквивалентной ей системе (3), которая называется системой, приведенной к нормальному виду каким-либо способом. Рассмотрим их.

1. Если в матрице коэффициентов A наблюдается диагональное преобладание, т. е.

, j#i, i =1,2,…n,

то систему (3) можно получить, разделив уравнения системы на соответствующие диагональные элементы и выразив x1 через первое уравнение системы, x2 – через второе и т. д. В результате получим:

— новая матрица коэффициентов

— новый вектор свободных членов

2. Иногда выгоднее приводить систему (2) к виду (3) так, чтобы коэффициенты aii не были равны нулю.

Вообще, имея систему

, i = 1, 2, … n,

,

где # 0. Тогда исходная система эквивалентна нормальной системе:

, i =1, 2, … n,

где ; при i # j

	Вычисление это получение из входных данных нового знания
Как люди считали в старину и как считали цифры — часть 1 Математическое моделирование, численные методы Хорошо ли вы считаете? — считать приходится везде Необыкновенная арифметика — часть 1 Когда не следует пользоваться шаблонными приемами вычислений

Видео:2. Приведение уравнений второго порядка к каноническому видуСкачать

Алгебра

Видео:Семинар №9 "Приведение уравнения второго порядка к каноническому виду"Скачать

Протоколы

Видео:Математика без Ху!ни. Уравнения прямой. Часть 2. Каноническое, общее и в отрезках.Скачать

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

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

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

Видео:Решение системы уравнений методом ГауссаСкачать

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

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

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

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

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

Видео:Метод Лагранжа. Приведение квадратичной формы к каноническому и нормальному видамСкачать

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

Для систем общего вида должно выполняться тождество 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|$ ∠ $ε$

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

Видео:Математика без Ху!ни. Метод Гаусса.Скачать

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

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

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

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

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

📹 Видео

53. Приведение общего уравнения кривой к каноническому видуСкачать

Математика без Ху!ни. Кривые второго порядка. Эллипс.Скачать

5. Нормальное уравнение плоскости выводСкачать

Семинар 6. Приведение уравнения кривой II порядка к каноническому видуСкачать

Курс по ОДУ: Системы ДУ, не приведённые к нормальному виду | Занятие 20Скачать

Матричный метод решения систем уравненийСкачать

Приведение кривой второго порядка к каноническому виду. ПримерСкачать