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

Начинаем с приближения  . Используя первое уравнение, находим для новое значение при условии .

 

      (30)

 

Беря это значение и из второго уравнения, находим , далее из третьего уравнения находим , . Эти три величины дают новое приближение и можно повторить цикл с начала, получаем: , , и т.д. Итерации продолжаются до выполнения неравенства .

Общий алгоритм метода Гаусса-Зейделя  имеет вид:

Пусть

 

      (31)

 

где у матрицы  - все диагональные элементы отличны от нуля, т.е. (если , тогда переставляем строки так, чтобы добиться условия ). Если -ое уравнение системы (31) разделить на , а затем все неизвестные кроме - перенести в правую часть, то мы придём к эквивалентной системе вида:

 

      (32)

 

где , ,

 

     (33)

 

Метод Гаусса-Зейделя состоит  в том, что итерации производятся по формуле:

 

     (34)

 

где - номер итерации, а .

Замечание: для сходимости метода (34) достаточно выполнения хотя бы одного из условий:

а)

 

,     (35)

б) - симметричная и положительно-определённая матрица. 

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

 

Если  - симметричная и положительно-определённая матрица, то задача решения линейной системы уравнений:

 

       (36)

 

эквивалентна задаче нахождения точки минимума функции многих переменных:

 

    (37)

 

где скалярные произведения понимаются в смысле , т.е.

 

      (38)

 

Иначе говоря, решение системы  линейных уравнений (36) доставляет минимум  функции многих переменных:

 

     (39)

 

И наоборот, точка минимума функции (39) является решением системы  линейных уравнений (36).

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

 

2.4. Решение  системы линейных уравнений с  трехдиаганальной матрицей методом  прогонки Томаса

 

При решении задач конечно-разностными  методами или методом конечных элементов, часто решение задачи сводится к  решению линейной системы уравнений  с трехдиаганальной матрицей коэффициентов, т.е. с матрицей, где все элементы нули, кроме трех диагоналей (в окрестности  главной диагонали); рассмотрим систему  с трехдиаганальной матрицей:

 

  (40)

 

для решения этой линейной системы уравнений, конечно, можно  применять метод Гаусса, но тогда  пришлось бы делать много необязательных операций с нулями. Чтобы сэкономить время вычислений и не работать лишний раз с нулями, Томас (1949г.) разработал специальный алгоритм расчета. Рассчитывая  по алгоритму Томаса элементы получаемой треугольной матрицы, мы следуем  методу Гаусса, с уточнением, что  с нулями никаких действий не производим; алгоритм Томаса называют – методом  прогонки.

Для решения системы (40) методом  прогонки – Томаса действуем следующим  образом:

а) прямой ход:

    (41)

 

Замечание: после проведения прямого хода предполагается, что  все  , и - неизменны (что очевидно).

б) обратный ход:

 

    (42)

 

Таким образом, для системы  линейных уравнений с трехдиаганальной матрицей наиболее экономным является алгоритм прогонки – Томаса, который  является «отфильтрованным» методом  Гаусса.

Метод минимизации невязки  для решения линейной системы  уравнений (метод наименьших квадратов).

При проведении экспериментов, часто приходится решать следующую  задачу: определить известных ,которые непосредственно не измеряются, а измеряются величины связанные с определяемыми переменными . Измерения не свободны от случайных ошибок, которыми нельзя пренебречь.

Число наблюдаемых величин  больше числа неизвестных  . Пусть известно, что величины связаны между собой линейной зависимостью:

, , .   (43)

 

Коэффициенты  - считаются известными и неотягощенными случайными ошибками. Система (43) называется системой условных уравнений.

Если бы все числа  были точными, то неизвестные , могли бы быть определены из любых - уравнений системы . Но так, как - определены с ошибками, то система условных уравнений несовместна (переопределена, т.к. ), существуют «невязки»:

 

,    (44)

 

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

В методе наименьших квадратов, в качестве нормы рассматривают  дискретную норму Гаусса:

 

    (45)

 

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

      (46)

 

Условия существования минимума для функций специального вида имеют вид:

 

, ,        (47)

 

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

Для примера рассмотрим уравнений с тремя неизвестными, система условных уравнений имеет вид:

 

    (48)

 

Тогда система соответствующих  нормальных уравнений имеет вид:

 

  (49)

 

Решение системы (49) дает решение  задачи (48) наилучшим приближением, в смысле дискретной нормы Гаусса.

 

3. Замечания

1) классический метод  Гаусса, метод Гаусса с выбором  главного элемента, метод Якоби  и метод минимизации невязки  являются общими методами и  применяются для определения  решения невырожденных систем  линейных уравнений, когда ведущие  (большие по модулю) элементы матрицы  системы расположены в окрестности  главной диагонали (система хорошо  обусловлена), если же система  плохо обусловлена, тогда нужно  менять соответствующую модель, чтобы она приводила к приемлемой  системе уравнений;

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

3) для нужд разностных  уравнений разработаны специальные  алгоритмы прогонки Томаса, которые  являются «экономными» методами  Гаусса для трехдиагональных  матриц системы линейных уравнений.

 

2. Практическая часть

 

Задача №1.

Решить систему:

• по формулам Крамера,
• выполнить проверку.

Решение.

, ,

, ,

где А - определитель основной матрицы системы;

∆x₁, ∆х₂, ∆х₃ - определители, полученные из основной матрицы заменой 1-го, 2-го и 3-го столбцов столбцом свободных членов.

Тогда , ,

Проверка:

           

Ответ: = 3, = -1, = 0.

Задача №2.

Решить задачу линейного  программирования графическим методом:

Решение.

В прямоугольной системе  координат х₁Ох₂  строим прямые (см. рис. 1):

               по точкам    

 

 

 

 

Нанесем штриховку на каждую линию в соответствии со знаком неравенства:

Выпуклый многоугольник  ABCDЕ – решение системы неравенств (1).

Строим вектор целевой  функции: N = {2; 3}.

Строим линию уровня (опорную  прямую):  (F) 2х₁ + 3х₂ = а, например

2х₁ + 3х₂ = 0 по точкам: (0; 0), (3; -2).

Для нахождения минимума F перемещаем линию уровня против направлению вектора N = {2; 3} до входа из многоугольника ABCD.

Минимум  функции F будет достигнут в точке D – точке пересечения прямой (1) и оси ох₁.

Найдем координаты т. D:

     

Из системы получим: координаты т. D(2; 0) и значение целевой функции в этой точке равно F_min = F(2; 0) = 2∙2 + 3∙0 = 4.

Ответ: X = (х₁ = 2; х₂ = 0), при котором F_min = 4.

Задача №3.

Предприятие предполагает выпускать  два вида продукции А₁ и А₂, для производства которых используется сырье трех видов. Производство обеспечено сырьем каждого вида в количествах: 330, 800, 745 кг. На изготовление единицы изделия А₁ требуется затратить сырья каждого вида 3, 2, 5 кг, соответственно, а для единицы изделия А₂ – 1, 8, 6 кг. Прибыль от реализации единицы изделия А₁ составляет 33 д. ед., для единицы изделия A₂ - 24 д. ед.

Требуется составить план производства изделий А₁ и A₂, обеспечивающий максимальную прибыль предприятия от реализации готовой продукции.

Необходимо:

• составить математическую модель задачи;
• решить задачу симплекс-методом.

Решение.

Составим математическую модель задачи:

Пусть требуется произвести х₁ единиц  изделий А₁ и х₂ единиц изделий А₂. 

Максимизируем целевую функцию  f(x) = 30х₁ + 44х₂ при ограничениях:

            (1)

Приведем систему (1) к  каноническому виду, добавив новые  неотрицательные переменные х₃>0, х₄>0, х₅>0:

Заполним симплекс-таблицу.

 

 

 

 

Последняя индексная строка не содержит отрицательных элементов, т.е. мы пришли к оптимальному решению.

X = (х₁ = 50; х₂ = 120), при котором f_max = 30∙50 + 44∙120 = 6780 д. ед.

Проверка: найденные значения переменных подставляем в систему (1)

 

Ответ: X_опт. = (50; 120), f_max = 6780 д. ед.

 

Задача №4.

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

Пункт отправления	В1	В2	В3	B4	В5	Запасы, аi (тонн)
А1	3	10	14	15	6	175
А2	2	22	4	12	9	165
А3	8	5	11	15	7	180
Потребности, bj (тонн)	90	120	110	130	70	520

 

Решение.

1. Составим опорный план (первое базисное решение) методом минимальной стоимости

Строим начальное опорное  решение методом минимальной  стоимости:

1. среди элементов c_ij (стоимость перевозок) выбираем наименьшую: c₃₁=3 и записываем в клетку (3; 1) максимально возможную перевозку x₃₁ = min(70, 230) = 70. Запасы 3-ей базы становятся а₃’ = 230 – 70 = 160, потребности 1-го потребителя удовлетворены полностью, его исключаем из рассмотрения.
2. продолжаем аналогично п. 1) и заполняем всю таблицу.

Таблица 2. Исходное решение

Пункт отправления	В1		В2		В3		В4		В5		Запасы, аi (тонн)
А1	-	14	10	8	-	17	-	5	110	3	120
А2	-	21	75	10	105	7	-	11	-	6	180
А3	70	3	35	5	-	8	125	4	-	9	230
Потребности, bj (тонн)	70		120		105		125		110		530

 

Проверим правильность заполнения таблицы. Число занятых клеток должно быть равно N = m + n – 1 = 3 + 5 – 1 = 7. Так как у нас заполнено 7 клеток, следовательно, план опорный.

Значение целевой функции (стоимость перевозок) при начальном  плане:

Z(X₀) = 70∙3 + 10∙8 + 75∙10 + 35∙5 + 105∙7 + 125∙4 + 110∙3 = 2780 д. ед.

Найдем оптимальный план.

Первый цикл:

Ц₁ = (1, 4) – (3, 4) – (3, 2) – (1, 2)

k₁γ₁ = -2γ₁

k₁ = 10 ед.

Пересчитаем транспортную таблицу  с учетом приведенного цикла.

Таблица 3. Первый цикл

 

Пункт отправления	В1		В2		В3		В4		В5		Запасы, аi (тонн)
А1	-	14	-	8	-	17	10	5	110	3	120
А2	-	21	75	10	105	7	-	11	-	6	180
А3	70	3	45	5	-	8	115	4	-	9	230
Потребности, bj (тонн)	70		120		105		125		110		530