Решение слау методом Гаусса.

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

а₁₁x₁+a₁₂+…+a_1nx_n=b₁

а₂₁x₁+a₂₂+…+a_2nx_n=b₂ (1)

………………………

a_n1x₁+a_n2+…+a_nnx_n=b_n

И ли матричной форме А* а = b (2)

A =( a,i,j), i,j=1,…,n; x = ; b =

Будем считать, что матрицы системы 1 будут невырожденной. Суть метода Гаусса состоит в преобразовании системы 1 к равносильной ей системе с треугольной матрицей, из которой затем последовательно получаются значения всех неизвестных. Метод Гаусса относится к точным методам, как и метод Крамера/

Подвергнем систему 1 следующим преобразованиям, считая, что а₁₁ не равно 0 разделим на а₁₁ коэффициенты первого уравнения, получим:

x₁+ а₁₂/ а₁₁* x2+…+ а_1n/ а₁₁* x_n= b_1n/ а_11, преобразуем:

x₁+ ά₁₂* x2+…+ ά_1n * x_n= ß₁ (3)

Пользуясь уравнением 3 легко исключить неизвестные x₁ из остальных уравнений системы. Для этого достаточно из каждого уравнения вычесть уравнение 3 умноженное на соответствующий коэффициент при x₁. Затем оставим первое уравнение в покое, над остальными совершаем аналогичные преобразования. Выбираем из их числа уравнение с ведущим элементом (элемент на главной диагонали) и исключаем с его помощью из остальных уравнений неизвестное x₂, повторяя этот процесс вместо системы x₁ получим равносильную ей систему с треугольной матрицей

x₁+ ά₁₂* x2+…+ ά_1n * x_n= ß₁ (4)

x₂+ ά₂₂* x2+…+ ά_2n * x_n= ß₂

……………………………..

x_n+ ά_n2* x2+…+ ά_nn * x_n= ß_n

Из системы 4 находятся значения неизвестных.

x_n, x_n-1, …, x₂, x₁

Таким образом, процесс решения системы 1 по методу Гаусса разбивается на 2 этапа:

1. Последовательное исключение неизвестных называется прямым ходом

2. Нахождение значений неизвестных называется обратным ходом.

При выполнения прямого хода используют следующие преобразования:

1. Умножение или деление коэффициентов свободных членов на одно и то же число.

2. Сложение и вычитание уравнений.

3. Перетасовка уравнений системы.

4. Исключение из системы уравнений, в которых все коэффициенты при неизвестных равны нулю.

Билет№17 Решение систем линейных алгебраических уравнений. Прямые методы. Метод Крамера

П усть дана системаA*x = b ;A = (a_ij) x = ; b =

i,j = 1, …, n

Метод Крамераприменим только в том случае, когда detA≠ 0

Вычисляется detA – главный определитель

∆x_i – определители которые получаются заменой соответствующих столбцов в главном определители на столбец свободных членов

– Определитель системы

, ……….

Короче формулы Крамера можно записать в виде:

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

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

а₁₁x₁+a₁₂+…+a_1nx_n=b₁

а₂₁x₁+a₂₂+…+a_2nx_n=b₂ (1)

………………………

a_n1x₁+a_n2+…+a_nnx_n=b_n

с/ п равносильных преобразований приведем эту систему к виду:

x₁=ά₁₂* x2+…+ ά_1n * x_n+ß₁ (2)

x₂=ά₂₂* x2+…+ ά_2n * x_n+ß₂

……………………………..

x_n=ά_n2* x2+…+ ά_nn * x_n+ ß_n

о ситеме 2 говорят, что она приведена к норм.виду

и спользуя правую часть норм.системы 2 и выбрав начальную точку:

x⁰( ; ; ; …; ) – начальная точка.

М ожно построить итерационную последовательность точек:

x⁰, x¹,x², … , xⁿ,...(3)

при определенных условиях итерационная последовательность 3 сходиться к решению системы 2 и тем самым системы 1.

Сформулируем эти условия. Решение этого вопроса зависит от способа метризации пространства, т.е определения расстояния между двумя его точками. Существует несколько способов метризации.

П усть x(x₁, x₂,...,x_n) и y (y₁, y₂,…, y_n) две точки пространства для применения метода простой итерации СЛАУ удобно поместить в пространство с одной из 3- х метрик:

1. ρ ₁(x ,y) = max (4)

1 ≤ i ≤ n

2. ρ ₂(x ,y) = (5) евклидова метрика

3. ρ ₃(x ,y) = (6)

Условия сходимости последовательности 3 в пространствах с метриками ρ₁, ρ₂, ρ₃выражается через коэффициенты α_ij.

1. В пространстве с метрикой ρ₁:

γ₁ = max (7)

1 ≤ i ≤ n

Т.еmax из сумм модулей коэффициентов взятых по строкам должны быть меньше 1.

2. С метрикой ρ₂:

γ₂ = max (8)

1 ≤ i ≤ n

Т.еmax из сумм модулей коэффициентов взятых по столбцам должны быть меньше 1.

3. С метрикой ρ₃:

γ₃ = (9)

т.е корень из суммы квадратов всех коэффициентов должны быть меньше 1.

Замечание: Каждая из условий (7)-(9) является достаточным, но не является необходимым для результативности метода итераций, т.е итерационная последовательность 3 может оказаться сходящейся и при не выполнение не одного из этих уловий.

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

Результатом установления одного из условий (7)-(9) является получение значения γ которое затем используется для оценки погрешности:

ρ (x^(k); x^(k-1)) ≤ (10), где ρ – метрика по которой была установлена сходимость и выбрано значение γ.

Практика по методу простой итерации:

Решить систему методом простой итерации

(2)

α₁₁ =0; α₁₂ = -2; α₁₃ = 8; β₁ =2;

α₂₁ =3; α₂₂ = 0; α₂₃= ; β₂ = ;

α₃₁ =2; α₃₂ = 16; α₃₃ = 0 ;β₃ = - 5;

т.к , то

для этого систему 1 приводим к виду с преобладающими диагональными коэффициентами:

(2)

α₁₁ =0; α₁₂ = ; α₁₃ = ; β₁ = ;

α₂₁ = ; α₂₂ = 0; α₂₃= ; β₂ = ;

α₃₁= ; α₃₂ = ; α₃₃ = 0 ; β₃ = - ;

γ₁<1; γ₂<1; γ₃<1;

γ₁ = = { }

γ₂= = { }

γ₃= =

т .к для всех γ; выполняется условие γ<1, то для критерия сходимости мы можем выбрать любую γ и соответствующую ей метрику; выберем γ₁ в качестве начальной точки выберем столбец ρ; x⁽⁰⁾ = ,для нахождения точки x⁽¹⁾ воспользуемся системой вида 2 в которую подставим значение x⁽⁰⁾

x ₁⁽¹⁾ = = = ;

x ₂⁽¹⁾ = =

x₃⁽¹⁾ =

ρ (x^(k); x^(k-1)) ≤

ρ₁ (x^(k); x^(k-1)) ≤

ρ₁ (x⁽¹⁾; x⁽⁰⁾)≤ max = =

( + )

Ответ: корень уравнения с заданной точностью

(x₁=5/24;x₂=55/192;x₃= -31/192)

Е сли неравенство оказалось неверным, то находим следующее приближение x²( ; ; ).

ρ ₁ (x⁽²⁾; x⁽¹⁾) ≤

ρ₁ = max

Билет № 19 Элементы линейного программирования. Постановка задачи

Линейные задачи оптимизации – задачи поиска минимума (максимума) линейной функции многих переменных при наличии ограничений в виде линейных равенств или неравенств.

В общем случае задачу линейного программирования (ЗЛП) можно записать в следующем виде:

Найти min при ограничениях:

A*x = b – ограничение равенства.

D*x ≤ d – ограничение неравенства.

Где х (х₁, х₂,… х_n) – вектор неизвестных;

с (с₁, с₂,… с_n) – вектор заданный.

= ( с; х ) - целевая функция

( с; х ) - скалярное произведение (с(а₁,b₁) и x(а₂,b₂)) а₁ * а₂ + b₁ * b₂

Матрица А имеет не более n строк. В А и D строк и столбцов равно n. Вектора b и d заданны. Ограничение равенства могут отсутствовать, а ограничения неравенства должны быть.

Решением задачи (т.min) называется такая точка (вектор) координаты которой удовлетворяют всем ограничениям и при этом значения целевой функции min.

Система ограничений формирует область допустимых решений (ОДР). То есть множество точек (векторов), координаты которых удовлетворяют всем ограничениям.

Именно среди них нужно искать точку минимума. Если ограничения противоречивы, то таких точек нет, ОДР есть пустое множество и задача не имеет решения. Если ОДР не пустое множество, то это не означает, что задача имеет решение. Возможна ситуация при которой в пределах ОДР целевая функция может неограниченно убывать. Это возможно только тогда, когда ОДР неограниченны. Если наличие или отсутствие решений полностью определяется ОДР, то количество точек минимума зависит и от ОДР и от целевой функции. ОДР – выпуклое множество при любых значениях элементов матриц А и D.

Линии уровня целевой функции – это линии на каждой из которых целевая функция постоянно в линейном программировании целевая функция линейна и линии уровня – параллельные прямые. Каждые линии уровня соответствует свое значение целевой функции. Уравнение (с; х) = const.

Вектор с – ортогонален (перпендикулярен) всем линиям уровня.

Геометрический смысл ЗЛП:

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