Page 55 - 4387

Крок 2, що є основним кроком алгоритму, проводиться

послідовно для r=0, 1, 2, ... і т.д. Якщо на деякому кроці, в

результаті послідовного виконання операцій (7.6) та (7.7), будуть

отримані однакові вектори оцінок, то знайдений розв'язок є

оптимальним. Операції, що визначаються співвідношеннями (7.6)

та (7.7), називаються операціями зворотного та прямого пошуку

відповідно. У кожному із цих співвідношень у першу чергу

виконується узагальнена операція додавання.

Пояснимо детальніше, як відбувається процедура

зворотного та прямого пошуку. Що стосується співвідношення

(7.6), то спочатку в рядку 2+1 визначається вектор 2+1 (це
1 1,
можливо тому, що N-й стовпець матриці L складається з векторів,

усі елементи яких збігаються з ∞, а отже, враховуючи

співвідношення (7.4), права частина рівняння (7.6) фактично від

d 2r+1 1 не залежить). Потім, за співвідношенням (7.6) визначається

2+1 2+1 (це можливо тому,
другий від кінця у рядку 1 вектор 1,−1
що N-1-й стовпець матриці L складається з векторів, серед яких

тільки у вектора останнього рядка матриці L деякі з елементів

можуть бути не рівні ∞, а отже, права частина співвідношення

(7.6) фактично залежить лише від вектора 2+1 , який уже був
1,
обчислений на попередньому кроці). Далі, за співвідношенням

(7.6) визначаються вектори 2+1 , 2+1 і т.д. до визначення усіх
1,−2 1,−3
2+1 (див. приклад 7.1). Таким чином, за
векторів рядка 1
допомогою співвідношення (7.6) можна визначити всі вектори

2+1 , якщо починати з останнього та закінчувати першим
рядка 1
елементом. Це дозволяє назвати обчислення за допомогою

співвідношення (7.6) процедурою зворотного пошуку. Аналогічно

за допомогою співвідношення (7.7) можна визначити всі вектори

54