що призводить до простішого вигляду системи (3.5) (див. Малюнок 4 і Малюнок 5), а, отже, до більш швидкого способу її вирішення.
Грунтуючись, на результатах роботи [7] було вирішено заміряти часи роботи двох методів для декількох тестових завдань і вибрати найбільш швидкий з них.
В
Малюнок 8. Час роботи SQP для повного і неповного гессіан (тестова задача 4)
В
Малюнок 9. Час роботи SQP для повного і неповного гессіан (тестова задача 5)
В результаті чисельних експериментів в якості гессіан було вирішено вибрати матрицю Гаусса-Ньютона, як показала менший час роботи алгоритму.
Асимметричное блочне розкладання
В якості першого способу розв'язання системи (3.5) розглянемо метод асиметричного блочного розкладання описаний в [3].
Нехай є система з матрицею блочного порядку два
В
і нехай матриця системи - позитивно визначена.
Тоді існує єдине розкладання матриці (розкладання Холецкого) виду:
,
де і - множники Холецкого відповідно для матриць і, а.
Запишемо два алгоритму знаходження матриці у вигляді таблиць:
Таблиця 1. Блочне розкладання для позитивно певної матриці
Номер шагаСімметрічная схемаАсімметрічная схема1 2 3 як просте твір матріцВместо перемноження спочатку обчислюють , потім отримують 4 5
В [3] показано, що якщо матриця має спеціальну розріджену структуру, то число операцій для обчислення - менше, а, отже, швидкість розкладання вище.
Запишемо аналогічні формули для випадку, коли матриця не є позитивно визначеною:
В
Формула (3.37) - формула LDL розкладання - використовується замість розкладання Холецкого в випадках не позитивно визначеності матриці.
Таблиця 2. Блочне розкладання для НЕ позитивно певної матриці
Номер шагаСімметрічная схемаАсімметрічная схема123 як просте твір матріцВместо перемноження спочатку обчислюють, потім отримують 45Чісленние досліди показали, що даний підхід не призводить до збільшення швидкості рішення системи (3.5). Такий результат обумовлений наступним фактором: початкова матриця - розріджена і розкладання блоку також призводить до розрідженим матрицям і. Однак, обчислення твори, як в симетричній схемі, так і в асиметричною, призводить до заповненої матриці і її розкладання займає багато часу. p align="justify"> Вибір методу рішення
Останнім питанням, розглянутим у цій роботі, стало питання про вибір методу розв'язання системи рівнянь (3.5).
Як було показано вище в якості лівого верхнього блоку матриці (3.5) - був обраний неповний гессіан лагранжіан...
