називають вирішальним рівнянням, а коефіцієнт цього рівняння при невідомому, виключається з решти рівнянь, - дозволяючими (або головним) елементом. Помножимо дозволяюче рівняння (2.1) на а 21 і віднімемо отримане рівняння з другого рівняння системи (2.2). Аналогічно перетворимо інші рівняння. У результаті цих операцій отримаємо систему:
(2.3)
Де
(j=2,3, ... n).
Природно, що якщо який-небудь з коефіцієнтів aij виявиться рівним нулю, то j-е рівняння системи (2.1) увійде в систему (2.3) без змін.
Тепер, залишивши без зміни перше рівняння системи (2.3), можна зробити друге рівняння дозволяючими і застосувати описану процедуру до системи з n - 1 рівнянь, виключивши невідоме х 2 з третьої і наступних рівнянь. Отримаємо систему:
(2.4)
де
Продовжуючи надалі аналогічні обчислення, наведемо систему (2.1) до еквівалентної системи
(2.5)
в якій матриця коефіцієнтів має трикутний вигляд. На цьому закінчується прямий хід вирішення системи лінійних рівнянь методом Гаусса.
При зворотному ході відбувається послідовне виключення невідомого х n, починаючи з (nl)-oгo рівняння і закінчуючи першим.
Отримуємо
(2.6)
Потім виключаємо невідоме х п - 1 з рівнянь з номером j (j=n - 2, ... 1) і т.д. Обчислення закінчуються рішенням системи, що має вигляд
.1.2 Метод Хука-Дживса
На розробку методів прямого пошуку для визначення мінімуму функцій і змінних було витрачено багато зусиль. Методи прямого пошуку є методами, в яких використовуються тільки значення функції. Ми розглянемо докладно лише один з них. Практика показала, що цей метод ефективний і застосуємо для широкого числа додатків. Розглянемо функцію двох змінних. Її лінії постійного рівня на малюнку 2, а мінімум лежить в точці (x1 *, x2 *). Найпростішим методом пошуку є метод покоординатного узвозу. З точки А ми виробляємо пошук мінімуму уздовж напрямку осі і, таким чином, знаходимо точку В, в якій дотична до лінії постійного рівня паралельна осі. Потім, роблячи пошук з точки В напрямку осі, отримуємо точку С, виробляючи пошук паралельно осі, отримуємо точку D, і т. д. Таким чином, ми приходимо до оптимальної точці. Очевидним чином цю ідею можна застосувати для функцій n-змінних.
Малюнок 2
Теоретично даний метод ефективний у випадку єдиного мінімуму функції. Але на практиці він виявляється занадто повільним. Тому були розроблені більш складні методи, використовують більше інформації на підставі вже отриманих значень функції.
Метод Хука-Дживса був розроблений в 1961 році, але до цих пір є досить ефективним і оригінальним. Пошук складається з послідовності кроків исследующего пошуку навколо базисної точки, за якою у разі успіху слід пошук за зразком. Він застосовується для вирішення завдання минимизирования функції без врахування обмежень.
Опис цієї процедури представлено нижче:
А. Вибрати початкову базисну точку b 1 і крок довжиною h 1 для кожної змінної xj, j=1, 2, ..., n. У наведеній нижче програмі для кожної змінної використовуєт...
