СПЕКТРУМ в школе
Здравствуйте, дорогие друзья!
Так уж повелось в последнее время на наших страницах, предназначенных для школьников, что мы играючи осваиваем интересные численные методы решения математических уравнений, и сегодня мы хотели бы предложить Вам еще одну игру, из которой вытекают совсем не игровые последствия.
Скажите, что Вы подумаете о человеке, который предложит Вам решить ОДНО уравнение с двумя неизвестными? Наверное, что у него, как сейчас говорят, "крыша поехала". А если это будет одно уравнение с пятью неизвестными? Это невозможно, скажете Вы? А если он Вам скажет, что его не интересует абсолютно точное решение и его устроит решение с какой-то допустимой погрешностью? О, это совсем другое дело - тогда можно как-то попробовать УГАДАТЬ более-менее приличное решение, особенно если это игра.
Итак, возьмем для игры следующие значения: X = 5; Y=2;
Составим из них уравнение, например такое:
X + X*Y + X*X + Y*Y - 44 = 0
И предложим его решить кому-либо из знакомых, не открывая истинных значений X и Y. Единственное, что можно подсказать - так это то, что X находится в пределах от 0 до 20, а Y - от 0 до 10, и пусть он теперь попробует решить такое уравнение.
Что будет делать Ваш партнер? Во-первых, он попробует взять в качестве первого приближения средние значения X и Y из их возможного интервала и посмотреть, что из этого получится:
X = 10; Y = 5
10 + 50 + 100 + 25 - 44 = 139
Мы получили "невязку, равную 139, поскольку не угадали X и Y.
Надо их корректировать. Поскольку "невязка" больше нуля, значит мы где-то перебрали. Ударим опять посередине: Х = 5; Y = 2.5.
Получим:
5 + 12.5 + 25 + 6.25 - 44 = 4.75
"Невязка" стала значительно меньше, значит, мы на верном пути. Попробуем еще раз уменьшить X и Y.
X = 2.5; Y = 1.25
2.5+3.13+6.25+1.56-44 = -30.56
На сей раз мы ушли не в ту сторону. Попробуем еще раз и опять посередине: Х = 3.75; Y = 1.85
3.75+6.98+14.06+6.98-44 = - 12.23
Снова "недолет", стрельнем еще последний разок и пока хватит.
Х=4.38; Y = 2.18 4.38+9.55+19.18+4.75-44 = - 6.14 Итак, мы получили результат:
X = 4.38, a Y = 2.18 Истинный же результат, как мы помним, был: X = 5, а Y =2.
Выходит, мы решили задачу с точностью до примерно 12 процентов. Хорошо это или плохо? Ну, во-первых, это еще не предельная наша точность, ведь считали-то мы на бумажке, а если применить компьютер, то ее можно бы и повысить и как это сделать, мы еще покажем. А во-вторых, надо подумать, где такие расчеты могут использоваться?
Оказывается, они могут применяться, как правило, в двух случаях. Во-первых, в технике, когда какие-то параметры конструкции неизвестны или известны плохо. Их, конечно, можно устанавливать с помощью испытаний, экспериментов и т.п. и так и делают, но это довольно дорого, трудоемко и долго. Такой расчет позволяет во много раз снизить затраты на испытания и сэкономить месяцы и годы. К тому же, как правило, все технические устройства имеют не менее, чем 100-процентный запас надежности и точность наших расчетов вовсе не так уж и плоха.
Вторая область, когда приходится решать уравнения, в которых неизвестных больше, чем самих уравнений - экономические расчеты, типа того, как организовать транспортировку пива, нефти и подсолнечного масла между десятью регионами, спрос в которых на эти продукты точно не известен, но затратить при этом минимум средств на перевозку, хранение и обслуживание цистерн. В этих расчетах точность порядка 12 процентов - просто блестящая. В рыночной экономике надо уметь прогнозировать результаты своих действий.
Итак, мы умеем теперь решать уравнения с большим количеством неизвестных, хотя вопросов еще осталось немало. Во-первых, как приспособить к этому делу компьютер, а во-вторых, надо ему дать четкий алгоритм, потому что мы с Вами "стреляли" по собственному разумению - чуть ближе, чуть дальше, а компьютеру надо точно объяснить, куда "стрелять" в поисках нужного решения.
2
5
10
15
Давайте посмотрим на графике (рис. 1), как мы двигались к решению, начиная от Х=10, Y=5.
Y 8 ■■
6 ■■
4 -■
Как видите, мы все время "бегали" по одной прямой, пока не нашли на ней точку, близко лежащую к истинному решению. Да это и не удивительно, ведь мы все время делили отрезок пополам. Но так дело не пойдет. Это хорошо, что у нас только два неизвестных и наш график имеет две координаты X и Y (его можно изобразить на даже на плоскости). А если бы неизвестных было штук пять? Вы не представляете, что такое пятимерное пространство? Мы тоже не представляем, и как попасть прямой линией в таком пространстве в нужную точку? Это действительно трудно представить.
Для того, чтобы "освободить" себя от блуждания по одной прямой и выйти за ее пределы (например так, как показано на Рис. 2), надо "отпустить" X и Y от необходимости делить отрезок пополам при поиске нового приближения и разрешить компьютеру самому выбирать, какое приращение на X и Y он будет делать на каждом шагу. Можно даже разрешить ему это делать случайным образом. Пусть бегает где хочет, все равно мы примем только те его шаги, которые ведут к уменьшению "невязки", а все прочие отбросим.
Так наш компьютер "выйдет" за пределы роковой прямой. Если у нас пять неизвестных, то он начнет "блуждать" в пятимерном пространстве, медленно но верно подходя к приемлемому (хоть и не точному) решению.
Такой метод расчета известен в математике под названием "случайного" поиска.
Наметим алгоритм:
1. Ввод уравнения.
2. Ввод предельных значения неизвестных.
3. Выбираем первую точку в качестве средней между предельными значениями неизвестных.
4. Расчет "невязки".
5. С помощью генератора случайных чисел определяем "приращение" для каждой из координат.
6. Получаем новую точку.
7. Проверяем, не выходит ли она за пределы допустимых значений по координатам. Если да, то возвращаемся на п. 5.
8. Рассчитываем "невязку" и сравниваем ее с предыдущей "невязкой". Если она по абсолютной величине больше, чем предыдущая, то такой шаг нам не нужен, возвращаемся на п. 5.
9. Делаем новый шаг в том же "направлении", что и предыдущий случайный шаг. Теперь нам генератор случайных чисел не нужен, не стоит тратить время на случайный поиск направления, раз мы его уже нашли.
10. Проверяем не вышли ли мы за пределы допустимой области. Если да, то возврат на п. 5 (снова включаем случайный поиск).
11. Проверяем значение "невязки". Если она возросла, то шаг отменяется и возвращаемся на п. 5 для поиска нового направления, а если уменьшилась, то возвращаемся на п. 9 и шагаем в том же направлении еще раз.
Можно сделать кое-что еще. Во-первых, мы имеем здесь бесконечный цикл, поэтому надо предусмотреть окончание расчетов и выход из него по достижении какого-то значения "невязки".
Во-вторых, можно ускорить работу, если после удачного шага делать следующий шаг в том же направлении например в два раза длиннее. А после неудачного шага не бежать сразу к случайному определению нового направления, а попробовать шагнуть еще раз туда же, но в десять раз короче.
Можно повысить надежность наших расчетов, запуская одну и ту же программу несколько раз. Поскольку у нас неизвестных больше, чем количество уравнений, то может быть получено много разных пар X и Y, которые удовлетворяют решению задачи. Определив случайным образом несколько таких пар, можно подумать и выбрать среди них оптимальную.
Можно предложить еще множество разных усовершенствований и ухищрений и каждый, кому понадобится использовать метод случайного поиска для решения своей задачи сможет доработать его так, как ему надо.
От себя же добавим, что у метода случайного поиска, хоть он и работает довольно медленно, есть одна интересная особенность. Дело в том, что при применении других численных методов расчет хоть происходит и быстрее, но, встречаются ситуации, когда он заходит в тупик. Математики говорят, что расчёт "попал в яму" или "в овраг", и обычными способами из такого оврага не выбраться. А с помощью случайного поиска - пожалуйста. Поэтому применяют иные, быстроработающие методы, но когда оказывается, что "невязка" начинает уменьшаться слишком медленно, то подключают случайный поиск и он выводит из тупика.
Представьте себе, что на неровную холмистую лужайку бросили мяч. Ваша задача -закатить его в самую низкую точку этой лужайки (минимальная невязка). Если он попал на холм, то он бодро покатится туда, куда надо (работает быстрый численный метод), но если по пути он закатится в какую-либо ямку, рытвину или овраг - дело плохо, сам он оттуда не выкатится. Его надо "встряхнуть", еще раз подкинуть, чтобы он мог катиться дальше - это и сделает вовремя подключенная процедура случайного поиска.
10 REM *** Метод случайного поиска***
20 DEF FN A(X,Y) = X+X*Y+X*X+Y*Y - 44: REM Ваше уравнение.
30 LET xmax = 20: LET xmin=0: LET ymax = 10: LET ymin=0: REM ввод граничных условий.
40 LET x=(xmax+xmin)/2: LET y=(ymax+ymin)/2: REM исходная точка поиска
45 GO SUB 400:REM расчет невязки.
48 LET dif1 = dif: REM запомнили невязку.
49 GO SUB 300: REM печать.
50 LET xstep = (xmax-xmin)/10: LET ystep = (ymax-ymin)/10: REM стандартный шаг поиска.
60 GO SUB 500: REM определение случайного направления.
70 LET x1=x+dx: LET у^+dy: REM Поиск новой точки.
80 IF x1 > xmax OR x1 < xmin OR y1 > ymax OR y1 < ymin THEN GO TO 60: REM При выходе за границы зоны надо повторить поиск новой точки.
90 LET x=x1: LET y=y1: REM переход к новой точке.
100 GO SUB 400: REM расчет новой невязки.
110 IF ABS(dif) < ABS(dif1) THEN GO TO 130
120 LET x=x-dx: LET y=y-dy: GO TO 60: REM если невязка оказалась больше, чем была, то эта точка нам не нужна.
130 LET dif1 = dif: Rem запомнили новую невязку.
140 GO SUB 300: REM печать
150 IF ABS(dif1) < 1.0 THEN STOP: REM если достигнута заданная точность, то конец работы.
160 GO TO 70: REM Возврат для следующего шага.
300 PRINT "Х= ";x; TAB 10;"Y= ";y; TAB 20;"DIFF= ";dif1
310 RETURN
400 LET dif = FN A(x,y)
410 RETURN
500 LET dx=xstep*(2*RND-1):LET dy=ystep*(2*RND-1)
510 RETURN
Примечание. Здесь мы используем не функцию RND, a 2*RND-1. Это сделано потому, что RND дает результат в диапазоне 0...1, a нам нужно в диапазоне -1... + 1, иначе наш поиск будет не случайным, а все время будет уводить нас вправо и вверх.
В строке 50 мы задали параметры xstep и ystep - это как бы сила того толчка, с которой застрявший мяч выбрасывается из ямки. Мы взяли эту величину, равной одной десятой размеров "игрового поля". Если взять мало, то силы может и не хватить и мячик не найдет более удачного продолжения своему пути, а если взять слишком много, то он будет слишком долго метаться по игровому полю, а то и вообще выходить за его пределы. Можно подобрать эту величину экспериментально, а можно и сделать ее плавающей, в зависимости от того, как близко к финалу мы подошли.
Проведя расчеты по приведенной выше программе мы получили следующую тректорию
поиска.
|
N шага |
X |
Y |
Невязка |
|
1 |
10 |
5 |
141 |
|
2 |
6 |
4.2 |
78 |
|
3 |
4 |
2.5 |
-7.5 |
|
4 |
3.8 |
3.1 |
-4.9 |
|
5 |
3.5 |
3.7 |
-1.7 |
|
6 |
4.3 |
2.8 |
-1.2 |
|
7 |
5.1 |
2.0 |
0.66 |
График поиска показан на рис. 2.
Y 4
3
2
1
0 X
Результат очень близок к задуманному. Но для проверки его точности мы еще пять раз повторили поиск и получили еще пять возможных ответов.
|
X |
Y |
|
1.3 |
5.8 |
|
4.8 |
2.2 |
|
4.0 |
3.3 |
|
2.9 |
4.4 |
|
2.6 |
4.7 |
Как видите, здесь результаты уже не столь близки к задуманным, но зато мы можем сузить диапазон "возможных" значении для X и Y. Например так: XMAX = 6: XMIN = 0: YMAX = 6: YMIN = 0
_И теперь "прогон" программы еще восемь раз дал другую серию результатов:
|
X |
Y |
|
4.55 |
2.61 |
|
4.25 |
2.98 |
|
4.56 |
2.60 |
|
5.21 |
1.69 |
|
4.54 |
2.61 |
|
4.57 |
2.57 |
|
4.58 |
2.57 |
|
4.69 |
2.43 |
|
Среднее 4.65 |
2.51 |
|
Точность 7% |
25% |
А теперь, в заключение этой статьи, мы предлагаем Вам пару легенд, из которых Вы поймете, что такие "детские игры" могут в реальной жизни приводить к экономии тысяч рублей личных и миллиардов рублей государственных денег.
1.
Дело было почти 20 лет назад. СССР произвел запуск очередной межпланетной станции в дальний космос. Как на грех, сразу после пуска выясняется, что одна из ответственнейших систем вообще не работает. Причем, пока она и не нужна, а вот когда через несколько месяцев станция дойдет до конечной цели своего путешествия, то без нее не обойтись. Но меры можно предпринимать только сейчас, потом будет поздно. Надо что-то срочно делать.
Было несколько путей выхода из создавшегося положения и окончательный выбор решения лег на плечи молодого специалиста, стаж работы которого был около двух лет. Поставили срок - три дня и поручили обосновать принятое решение необходимыми расчетами.
Уже через под-дня грубых расчетов оказалось, что предсказать, что даст то или иное решение можно только решив пару уравнений размером в пол-страницы, в котором к тому же было пять неизвестных параметров. Конечно, эти параметры можно было "вытаскивать" ставя практические эксперименты, но на это нужны были бы годы и такая работа оказалась бы на уровне десятка кандидатских диссертаций.
Беглый поиск в технической библиотеке показал, что можно попробовать воевать с таким уравнением. Еще пол-дня ушло на изучение основ вариационного исчисления и теории оптимального управления, а еще через два дня после отсева всего лишнего, почерпнутого из научных трудов, родился алгоритм, немного похожий на предложенный Вам. Решение было найдено и подтверждено расчетами, благо ЭВМ ЕС-1022 в те годы уже существовала.
Дело оставалось за малым - защитить это решение перед Государственной комиссией и убедить ее в правильности предложенных мероприятий.
Начальника отдела чуть не хватил удар, когда он увидел, что решение получено из двух уравнения с кучей неизвестных. Его реакцию словами не передать, и вот тогда и началась игра, которую мы Вам описали в самом начале. Задумывались числа, составлялись уравнения, а молодой специалист "угадывал" то, что задумал начальник. Пришло еще более высокое руководство и увлеченно включилось в игру. Одним словом, вдоволь наигравшись, они вынуждены были перекреститься и согласиться на рискованное с их точки зрения решение. Их поддержка на заседании Госкомиссии решила дело. Конечно, вопрос о том, каким путем решалось уравнение там не поднимался. Военные - люди серьезные, им не до таких мелочей. Им важно знать, что будет и как будет и кто будет отвечать, если все будет не так, а иначе.
Можно ли использовать положительные результаты кабинетной игры в обоснование сложных расчетов для ответственной техники? Во всяком случае, акты и протоколы были подписаны и ответственность легла на плечи отважных начальников - их убедила именно игра!
Через четыре месяца после этого станция полностью выполнила поставленную перед ней задачу, а поведение всех систем по данным телеметрической информации совпало с расчетным с точностью до полутора процентов, так были спасены миллиарды государственных рублей, затраченных на программу полета. Восторги молодого специалиста по этому поводу можно не описывать, а отважные начальники лукаво усмехались, принимая поздравления на самом высоком уровне.
История получила, кстати, неожиданное продолжение. Мы ведь сказали, что в уравнение входило много неизвестных параметров, для определения которых требовались длительные и дорогие испытания техники. Но раз уж приближенное решение было найдено, то интересно стало поглядеть и на то, чему эти параметры оказались равны. Так вот, два из них оказались настолько далеки от того, что предсказывала теория, что это вызвало массу сомнений. Раз за разом случайным поиском искались новые решения, но эта два параметра все равно отличались от теории раза в два. Впоследствии, когда экспедиция закончилась успешно и подтвердила расчет, стали проверять теорию и выяснили, что в ее основу была положена модель начала 60-х годов, которая успела устареть. Скорректировав модель и построив новую теорию, с удивлением обнаружили, что эти параметры оказались почти такими, как показало решение уравнения со многими неизвестными.
2.
Год 1990-ый. Только что появился на свет "ИНФОРКОМ" и сразу предложил своим клиентам первый десяток методических разработок.
Встал щепетильный вопрос определения цены на каждую. Большую цену назначить нельзя. Деньги, затраченные на их подготовку и печать не вернутся и фирму ждет мгновенная смерть. Малую цену назначить нельзя, ибо если спрос превысит очень ограниченные физические возможности коллектива, то не хватит подготовленного тиража, не хватит сил и времени на транспортировку и отправку, не хватит места для хранения, сорвется подготовка новых работ. Пойдут срывы заказов, потеря доверия клиентов и в итоге тоже смерть.
Два десятка неизвестных (цена на каждую из разработок и их тиражи) вошли в несколько уравнений, увязывающих физические возможности коллектива, полиграфические мощности дружественного предприятия, почтовые возможности дружественного отделения связи и потенциальные финансовые возможности неизвестных будущих клиентов.
Расчет проводился на этот раз уже не на ЕС-1022, а на "Спектруме", что намного удобнее, по той же известной теперь Вам методике и в результате его были получены цены, которые надо назначить на ту или иную разработку и примерный ожидаемый тираж (для каждой - свой). По прошествии года исключительно ради интереса было проведено сравнение того, что дал компьютер с тем, что оказалось на самом деде. Самая грубая ошибка составила всего 35 процентов. Так еще раз удачно сработала эта увлекательная, но очень полезная игра.
В заключение хочется еще раз напомнить тем, кто нас читает - игра дело серьезное! Играйте на здоровье, но старайтесь при этом одновременно и обогащаться знаниями - кто знает, когда это пригодится!