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

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

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

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

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

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

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

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

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

Метод Якоби

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

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

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

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

(1)

Запишем систему (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 Когда не следует пользоваться шаблонными приемами вычислений

Алгебра

Протоколы

Системы линейных уравнений с примерами решений

Содержание:

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

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

Уравнения с двумя переменными

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

Пример:

На 22 руб. купили несколько книжек по 5 руб. и географических карт — по 3 руб. Сколько купили книжек и карт?

Решение:

Пусть купили х книжки у карт. За книжки заплатили 5х руб., а за карты — 3у руб. Всего заплатили 22 руб., то есть, 5х + Зу = 22.

Это уравнение с двумя переменными. Приведём и другие примеры таких уравнений с двумя переменными:

Уравнение вида ах + by = с, где а, b, с — данные числа, называется линейным уравнением с двумя переменными х и у. Если

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

два первых из них — уравнение первой степени с двумя переменными.

Паре чисел х = -1 и у = 9 удовлетворяет уравнение 5х + Зу -= 22, так как А пара чисел х = 1 и у = 2 этому уравнению не удовлетворяет, поскольку

Каждая пара чисел, удовлетворяющая уравнение с двумя переменными, т. е. обращающая это уравнение в верное равенство, называется решением этого уравнения.

Обратите внимание: одно решение состоит из двух чисел, на первом месте записывают значение х, на втором — у. Корнями их не называют.

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

Для примера найдем несколько решений уравнения

Если х = 1, то отсюда у = -2. Пара чисел х = 1 и у = -2 — решение данного уравнения. Его записывают ещё и так: (1; -2). Придавая переменной х значения 2, 3, 4, . , так же можно найти сколько угодно решений уравнения: (2; 1), (3; 4), (4; 7), (5; 10), . Каждое уравнение первой степени с двумя переменными имеет бесконечно много решений.

Уравнение также имеет бесконечно много решений, но сформулированную выше задачу удовлетворяет только одно из них: (2; 4).

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

Для уравнения с двумя переменными остаются справедливыми свойства, сформулированные для уравнений с одной переменной.

Обе части уравнения с двумя переменными можно умножить или разделить на одно и то же число, отличное от нуля. Любой член такого уравнения можно перенести из одной части уравнения в другую, изменив его знак на противоположный. В результате получается уравнение, равносильное данному.

Например, уравнение можно преобразовать так: . Каждое из этих уравнений равносильно друг другу.

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

Переменную у из этого уравнения выразим через х:

Будем подставлять в равенство вместо х первые натуральные числа до тех пор, пока не получим целое значение переменной у. Это можно делать устно. Если х = 2, то у = 4. Других натуральных решений уравнение не имеет. Поэтому задача имеет единственное решение: 2 книги и 4 карты.

Пример:

Решение:

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

б) Значение выражения равно нулю только при условии, когда x -3 = 0 и y = 0. Значит, уравнение имеет только одно решение: х = 3, у = 0.

Пример:

Составьте уравнение с двумя переменными, решением которого будет пара чисел (1; -5).

Решение:

Пишем любой двучлен с переменными х и у, например Если х = 1, а у = -5, то значение даного двучлена равно 28. Следовательно, уравнение удовлетворяет условие задачи.

Есть много других линейных уравнений с двумя переменными, имеющих такое же решение (1; -5).

График линейного уравнения с двумя переменными

Рассмотрим уравнение Давая переменной х значения -2, -1,0,1,2, 3. найдём соответствующие значения переменной у. Будем иметь решение данного уравнения: (-2; -б), (-1; -4,5), (0; -3),

При копировании любых материалов с сайта evkova.org обязательна активная ссылка на сайт www.evkova.org

Сайт создан коллективом преподавателей на некоммерческой основе для дополнительного образования молодежи

Сайт пишется, поддерживается и управляется коллективом преподавателей

Whatsapp и логотип whatsapp являются товарными знаками корпорации WhatsApp LLC.

Cайт носит информационный характер и ни при каких условиях не является публичной офертой, которая определяется положениями статьи 437 Гражданского кодекса РФ. Анна Евкова не оказывает никаких услуг.