Главная страница раздела 1
Главная страница раздела 2
Задание 4
Литература

ЛЕКЦИЯ 4

  1. Метод Гаусса решения систем линейных уравнений.
  2. Метод наискорейшего градиентного спуска.

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

   Метод Гаусса является алгоритмом последовательного исключения. Для простоты рассуждений ограничимся рассмотрением системы четырёх уравнений с четырьмя неизвестными:
            (4.1)
   Пусть а11≠ 0 (ведущий элемент). Разделив коэффициенты первого уравнения системы (4.1) на а11, получим
x1 + b12 x2 + b13 x3 + b14 x4 = b15,                 (4.2)
где
Пользуясь уравнением (4.2) можно исключить из системы (4.1) неизвестную х1. Для этого достаточно из второго уравнения системы (4.1) вычесть уравнение (4.2), умноженное на а21, из третьего уравнения системы (4.1) вычесть уравнение (4.2), умноженное на а31, и т. д. В результате получим систему из трёх уравнений:
                 (4.3)
где коэффициенты системы вычисляются по формуле
.
Разделив, далее, коэффициенты первого уравнения системы (4.3) на ведущий элемент , получим уравнение
,                (4.4)
где
Исключая теперь х2 таким же способом, каким было исключено х1, придём к следующей системе уравнений:
         (4.5)
где
.
Разделив, далее, коэффициенты первого уравнения системы (4.5) на ведущий элемент , получим уравнение
,                  (4.6)
где
Исключая теперь х3 аналогичным путём из системы (4.5) будем иметь:
,              (4.7)
где
.
Из (4.7) найдём
         (4.8)
Остальные неизвестные последовательно определяются из уравнений (4.2), (4.4), (4.6):
Таким образом, процесс решения линейной системы по методу Гаусса сводится к построению эквивалентной системы (4.2), (4.4), (4.7), (4.8), имеющей треугольную матрицу. Необходимым и достаточным условием применимости метода является неравенство нулю всех «ведущих элементов». Вычисления удобно поместить в таблицу. Приведённая в ней схема называется схемой единственного деления. Процесс нахождения коэффициентов  треугольной системы обычно называется прямым ходом, процесс получения значений неизвестных — обратным ходом.
   Прямой ход начинается с выписывания коэффициентов системы, включая свободные члены (раздел А). Последняя строка раздела А схемы представляет собой результат деления первой строки раздела на «ведущий элемент» а11. Элементы  следующего раздела схемы (раздел А1) равны соответствующим элементам aij предшествующего раздела без произведения их «проекций» на ряды раздела А, содержащие элемент 1 (т. е. первый столбец и первую строку).
   Последняя строка раздела А1 находится путём деления первой строки раздела на «ведущий элемент» . Аналогично строятся следующие разделы. Прямой ход заканчивается, когда доходят до раздела, состоящего из одной строки, не считая преобразованной (раздел А3).
   При обратном ходе используются лишь строки разделов Аi, содержащие единицы (отмеченные строки), начиная с последней. Элемент  раздела А3, стоящий в столбце свободных членов отмеченной строки раздела, даёт значение х4. Далее, все остальные неизвестные xi (i =3, 2, 1) шаг за шагом находятся с помощью вычитания из свободного члена отмеченной строки суммы произведений её коэффициентов на соответствующие значения ранее найденных неизвестных. Значения неизвестных последовательно выписываются в последний раздел В. Расставленные там единицы помогают находить для хi соответствующие коэффициенты в отмеченных строках.
   Для контроля вычислений используются «контрольные суммы»
,                (4.9)
помещённые в столбце Σ и представляющие собой сумму элементов строк матрицы исходной системы (4.1), включая свободные члены.
   Если ai6 принять за новые свободные члены в системе (4.1), то преобразованная линейная система
        (4.10)
будет иметь неизвестные , связанные с прежними неизвестными хi соотношениями
.       (4.11)
В самом деле, подставляя формулы (4.11) в уравнение (4.10), в силу системы (4.1) и формул (4.8) получим тождество
.
Если над контрольными суммами в каждой строке проделывать те же операции, что и над остальными элементами этой строки, то при отсутствии ошибок в вычислениях элементы столбца Σ равны суммам элементов соответствующих преобразованных строк. Это обстоятельство служит контролем прямого хода. Обратный ход контролируется нахождением чисел , которые должны совпадать с числами хi + 1.
x1 x2 x3 x4 b Σ Разделы схемы
1 2 - 1 8 - 8 2 А
3 - 2 1 - 1 6 7
6 1 - 3 2 14 20
-2 - 2 1 4 - 19 - 18
1 2 - 1 8 -8 2
0 -8 4 - 25 30 1 А1
0 -11 3 - 46 62 8
0 2 - 1 20 - 35 - 14
  1 - 0,5 3,125 -3,75 - 0,125
  0 - 2,5 - 11,625 20,75 6,625 А2
  0 0 13,75 -27,5 - 13,75
    1 4,65 - 8,3 - 2,65
    0 13,75 -27,5 -13,75 А3
      1 -2 -1
      1 -2 -1 В
    1   1 2
  1     3 4
1       3 4
Определитель системы 275          

Метод наискорейшего градиентного спуска

   Последующее приближение получается из предыдущего смещением в направлении градиента функции F(x). Таким образом, каждое следующее приближение ищется в виде
.
Приведённое описание не определяет алгоритм однозначно, поскольку ничего не сказано о выборе параметра δ. Например, его можно определять из условия минимума величины
В этом случае рассматриваемый метод называется методом наискорейшего градиентного спуска, или просто методом наискорейшего спуска.
   Для функции F(x) = (Ax, x) – (b, x), соответствующей системе линейных уравнений с матрицей А > 0, задача нахождения минимума решается в явном виде.
   В этом конкретном случае
grad F = 2·(Ax – b)
и
Обозначим 2·δn черех Δn тогда
,
или
откуда