Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Описанная выше ситуация типична для начала решения задачи, когда взятая из каких-то соображений точка начального приближения х грубо нарушает условия (26). Какое-то число первых итераций процесса тратится на определение допустимой точки х. Значение /° на этом этапе обычно растет.
5.2. Пусть точка х допустима и точка х + Ьх тоже удовлетворяет всем условиям с погрешностью Ce. При этом погрешность ТГ] вычисляется только по индексу і = 0. Здесь могут представиться разные ситуации.
а) Д/°<0, т.е. при выполнении условий с погрешностью Cti
происходит уменьшение /°. В этом случае пересчитывается шаг 5 (так же, как это было описано выше), точка х заменяется на х + Ьх и процесс продолжается с операции 5.1 (конечно, вычисления /' в точке X + Ьх не повторяются, они уже известны).
б) 6/° < 0, но Af0 > 0. Это означает, что шаг 5 слишком велик. Поэтому итерация «отменяется», шаг S уменьшается (например, вдвое) и задача линейного программирования решается заново.
в) 6/° > 0 и точность линейного приближения удовлетворительна (т]«0.1, например). Решение задачи линейного программирования приводит к росту /°. Такая ситуация обычно связана не с погрешностью линеаризации, а с тем, что условия (26) в точке х + Ьх выполнены с большей точностью, чем условия в точке X. Улучшение ТОЧКИ X + Ьх получено ценой некоторого увеличения
/°, хотя обе точки удовлетворяли условиям (26) с погрешностью Ct. В этом случае величина С уменьшается настолько, что точка х становится «недопустимой». Задача линейного программирования заново не решается, но анализ проводится заново, при новых требованиях к точности выполнения условий (26).
Вышеописанное решение об изменении С основано на следующем простом соображении. He следует с самого начала требовать очень точного выполнения условий (26) (для всех промежуточных результатов): это приводит к слишком малому шагу. Точность вы-
428
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч, II
полнения условий (26) должна быть «согласована» с желаемым ходом вычислительного процесса. Если при колебаниях значений /' в пределах Се-погрешности происходит монотонное понижение /°, все «идет так, как надо».
Конечно, мы могли бы с самого начала задать слишком малое значение С и завысить требования к точности выполнения условий. Эту ситуацию можно распознать по слишком малой величине Yj (шаг 5 слишком мал, точность линейного приближения излишне высока). В этом случае значение С несколько увеличивается. Ограничимся этим не очень строгим и не исчерпывающе полным описанием. Стремление к точному описанию алгоритма затруднило бы понимание основных идей. Здесь же мы ставим целью не безупречность описания, а подготовку читателя к знакомству с более точным изложением.
Для иллюстрации сказанного выше приведем пример решения не очень сложной модельной задачи. Она входит в набор тестов, принятых для оценки фактической эффективности алгоритмов. Задача имеет следующий вид (і = 1, 2, ..., 5):
10 5 5 5
f°(x) = — + 2) 2 CijX\0+iXW+j fi^xIO+/'
і = 1 і = І / = 1 і = 1
10 5
f‘(x) = 2 OljXj - 2 2 ctJxl0+J - 3diX}0+i - er /=1 /=1
Кроме того, поставлены условия Xj ^ 0 (г = 1, 2, ..., 15).
Таким образом, мы имеем в задаче 15 неизвестных и 5 условий-равенств. В качестве начального вектора берется X1 = 60, остальные Xi = 0. Требуемая точность выполнения условий определялась числами Zi = IO-5, С = IO6, 5 = 1.3. Значения параметров, входящих в выражения для функций, можно найти в известной монографии Д. Химмельблау «Прикладное нелинейное программирование» (см. задачу 18).
Процесс решения задачи иллюстрирует табл. 16. Поясним обозначения: V — номер шага (итерации); г = max |/'(*v)l — характеристика погрешности выполнения условий (і = 1, 2, ..., 5); S — шаг варьирования; Yj — характеристика погрешности линейного
приближения; К — число вычислений функций /' (вычисление /' для каждого отдельного і увеличивает счетчик К на единицу).
Каждый шаг процесса стоит примерно шести вычислений /', /'.. На некоторых шагах приходится повторять вариацию меньшим шагом; поэтому Kv w 1.35 (/ + I) V . При yj = 0 условия (26) выполнены с допустимой на данном этапе погрешностью. Эта погрешность есть 10 при V ^ 32. После 32-й итерации допустимая погрешность
ПОИСК МИНИМУМА
429
есть 0.45, после 41-й — 0.02, после 61-й — 5-Ю 4. Фактическая точность заметно выше. Расчет требует около минуты работы
Таблица 16
V /° г 5 tI о •о О < К
0 2400. 48 1 0.7 -20.3 -20.2 18
1 2380. 43 0.19 0.4 -3.3 4.6 24
2 2384. 44 0.14 0.14 -15.8 -13.4 30
3 2371. 32 0.17 0.19 -17.5 -16.5 36
4 2355. 35 0.21 0.13 -25.5 -23.2 42
9 1757.6 7.2 24.0 0 -86.6 -86.4 96
10 1671.2 3 1.7 0 ‘ -74.1 -68.5 108
11 1602.8 3.8 0.99 0 -98.3 -92.7 114
19 829.3 7.4 1.1 0 -135.7 -125.3 168
20 704.0 5 1.3 0 -150.6 -146.5 174
21 557.48 2.4 1.5 0 -186.7 -180.6 180
24 108.90 5 1 0 -74.5 -72.6 204
25 36.29522 1.2 1.2 0 -2.7 -2.8 216
26 35.51306 3.4 0.3 0 -2.73 -1.72 222
30 32.62674 0.06 0.18 0 -0.36 -0.20 246
31 32.42416 0.6 0.15 0 -0.39 -0.35 252
