Главная > Методы обработки сигналов > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 9. О постановках задач оптимизации

Мы получили ряд формул численного интегрирования и могли бы получить еще большее количество таких формул. Возникает вопрос: можно ли получить лучшие по порядку оценки погрешности при тех же предположениях о подынтегральной функции или хотя бы улучшить константы в этих оценках? Изучение этого вопроса приводит к задаче построения квадратур с оптимальной оценкой погрешности, или, как говорят, оптимальных квадратур. В связи с этим возникает следующая проблема — чем больше способов решения задачи, тем труднее решиться выбрать какой-то из них, поскольку каждый способ может иметь свои положительные качества: простота программирования, малое время работы ЭВМ, малая загрузка памяти, простота оценки погрешности, применимость к широкому кругу задач. Таким образом, следует иметь в виду, что иногда излишняя информация о способах решения задач при большом их количестве может также и затормозить реальное решение задач. Поэтому необходима какая-то систематизация методов решения, их отбор. Естественно пытаться решить задачи наилучшим, оптимальным способом. Мы уже рассматривали некоторые модельные формулировки задач об оптимальных методах решения на примере вычисления значений функций; при этом возникают определенные математические постановки задач, требующих решения.

При рассмотрении каждой новой проблемы желательно получить ее наиболее подробное, наилучшее описание и затем решить возникшую задачу наилучшим образом. Однако обычно это не удается сделать и приходится довольствоваться меньшим: описать проблему наилучшим образом и решить ее удовлетворительно или описать проблему удовлетворительно и затем полностью решить возникшую задачу.

При рассмотрении проблемы оптимизации методов можно говорить о выборе между удовлетворительным решением проблемы оптимизации методов для классов задач, близких к реальным, или полным решением проблемы для эталонных математических классов, подобных рассматриваемому в следующем параграфе. Может вызвать недоумение высказывание об «удовлетворительном решении проблемы оптимизации методов» для каких-то классов — ведь задача оптимизации методов на классе сводится к вполне конкретной математической задаче, которую, по-видимому, можно решить окончательно, а не «удовлетворительно».

В принципе это высказывание верно, однако обычно полностью решить задачу в приемлемое для практики время не удается, так как время, необходимое для построения оптимального метода, обычно существенно превосходит время, в течение которого возникает новое, уточненное описание классов рассматриваемых задач. Также надо иметь в виду, что не всегда удается формализовать такое математическое описание класса реальных задач: имеется какое-то качественное представление о классе, имеются неплохие численные методы и интуитивно ясно, что в практическом плане оптимальность методов достигнута; в то же время нет даже четко формализованного описания класса решаемых задач. Например, реально требуется вычислить интегралы от кусочно-гладких функций, однако в течение долгого времени так и не удалось предложить описание множества таких функций, которое соответствовало бы реальной практике вычислений. Точно так же, например, при анализе физических моделей можно описать задачу с помощью сложной системы дифференциальных уравнений и решить эту систему с малой точностью или описать задачу более грубо с помощью простой системы и решить эту систему с большой точностью.

В разных случаях, в зависимости от конкретной обстановки, бывает целесообразен тот или иной подход к решению задачи. Представляется, что для прикладной науки часто более существенно не окончательное решение вариационных задач, а правильная их постановка. Обычно больший эффект дает удовлетворительное решение правильно поставленной в практическом смысле вариационной задачи, чем полное решение упрощенной задачи, не охватывающей все существенные характерные черты исходной проблемы.

Что такое оптимальный метод решения задачи?

Под оптимальным методом решения задачи можно понимать метод, требующий минимальной затраты машинного времени. Но это будет неправильная постановка, поскольку, в принципе, всякую задачу можно решить без применения машин, затратив на это очень большое количество времени.

Под оптимальным можно понимать метод, требующий минимальных затрат времени (или соответственно материальных затрат). При этом следует помнить, что время и затраты на поиск оптимального алгоритма уже входят в решение задачи.

Когда мы ставим вопрос о решении задачи оптимальным образом, мы не учитываем разных возможностей исследователей, решающих задачу. А ведь в зависимости от индивидуальных возможностей исследователя, наличия ЭВМ, библиотеки, лаборантов, сотрудников, обладающих опытом решения подобных задач, оптимальное решение, вообще говоря, будет различным.

Мы говорили об оптимальном решении каждой конкретной задачи. Такая постановка вопроса не совсем правильна также по следующей причине. На самом деле коллектив исследователей сталкивается с целой совокупностью задач. Мы можем поставить перед собой цель решить первую, вторую и т.д. задачи за кратчайшее время. Однако постановка вопроса в корне изменится, если мы зададимся целью решить с минимальными затратами целую совокупность задач. Мы можем решать первую, вторую и т. д. задачи оптимальными методами, но за это время наука уйдет вперед, и если мы не будем изучать новые методы, создавать новые алгоритмы и стандартные программы, рассчитанные на решение будущих задач, то в целом мы проиграем. При наличии большой серии задач, не требующей сверхсрочного решения, выгоднее заняться теоретическими исследованиями, создать новые алгоритмы, а затем уже решать эти задачи.

Нет однозначного ответа также на вопрос о том, кто должен заниматься оптимальным решением задач. Если мы имеем дело с единственной конкретной задачей, заведомо не требующей нового алгоритма и больших затрат машинного времени, ее лучше поручить выполнить работнику низкой квалификации. Увеличение числа задач и их сложности требует привлечения работников высокой квалификации, поскольку здесь их отдача будет наиболее полной. Конечно, важно изучить опыт решения как сложных, так и простых задач подобного типа. Для того чтобы задачу оптимизации методов можно было рассматривать как чисто математическую задачу, необходимо определить целевую функцию исследования, класс рассматриваемых задач и возможности исследователя.

Качество какого-то алгоритма на классе задач мы характеризуем его качеством на самой «плохой» для него задаче этого класса. Поэтому чем уже класс рассматриваемых задач, тем лучше качество алгоритмов на этом классе.

Казалось бы, следует построить оптимальные алгоритмы для решения возможно большего числа классов задач. Однако при излишней детализации слишком много усилий уйдет на отыскание оптимальных методов решения. В этом случае может не хватить сил и времени на реальное решение самих задач, разработку и создание стандартных программ. Конечно, эти замечания против детализации в меньшей мере относятся к случаю специализированных машин и устройств, где следует максимально сузить класс рассматриваемых задач.

При первом взгляде на проблему кажется, что в практике вычислений всегда имеют дело с конкретными задачами и никогда не рассматривают класс задач.

По этому поводу можно сказать следующее: формально при выборе метода решения задачи исследователь не относит ее к какому-либо классу; однако метод решения всегда выбирается в зависимости от некоторых типичных свойств задачи: тип дифференциального уравнения, наличие особенности у решения, число конечных производных и т. п. При выборе алгоритма исследователь учитывает эти свойства и тем самым вольно или невольно относит рассматриваемую задачу к классу задач, обладающих этими свойствами.

При анализе задач и разбиении их на классы часто возникает вопрос: какому классу задач уделить первоочередное внимание, в частности, на какой класс задач следует рассчитывать при составлении стандартной программы численного интегрирования? Пусть, например, при помощи этой программы примерно с одинаковой частотой будут вычисляться интегралы как от гладких, так и от не очень гладких функций. На какие функции нужно ориентироваться при выборе алгоритма для этой программы? Ответ на этот вопрос можно получить из следующих соображений. На гладких функциях алгоритм будет работать более эффективно, поэтому время, затрачиваемое на их решение, будет меньше времени, затрачиваемого на решение задач с негладкими функциями. 50% экономии времени при вычислении интегралов от гладких функций принесет меньшую выгоду, чем 50% экономии времени при вычислении интегралов от негладких функций. Следовательно, целесообразнее уделить внимание эффективности алгоритма в случае негладких функций. Конечно, вывод будет другим, если доля негладких функций будет мала.

При отыскании оптимального метода решения класса задач в случае, когда предполагается непосредственное внедрение алгоритма в вычислительную практику, обычно возникает следующая проблема: нам не удается сразу найти оптимальный метод решения задач рассматриваемого класса. После некоторого времени работы мы находим какой-то метод, иногда близкий к оптимальному, иногда просто лучший, чем ранее известные, а затем постепенно совершенствуем его. В какой момент надо остановиться в усовершенствовании метода и перейти к составлению стандартных программ решения этого класса задач? При ответе на этот вопрос надо учитывать следующие простые соображения. Если мы поспешим и быстро начнем внедрять только что полученный алгоритм, то, может быть, нам придется вскоре создавать новые алгоритмы из-за плохого качества этого алгоритма. Затягивание времени при составлении стандартных программ также нежелательно: при этом мы допустим большой перерасход машинного времени при решении задач по имеющимся стандартным программам.

Можно возразить, что создание совершенных стандартных программ приведет к большой экономии машинного времени в будущем. Однако при анализе этого возражения в свою очередь следует учесть, что машинное время становится все менее дефицитным и более дешевым.

Кроме того, чем раньше мы решим ту или иную задачу, тем большую реальную пользу получит общество в целом.

Нужно учитывать также важность быстрого внедрения вновь созданных алгоритмов для самой задачи отыскания оптимальных методов решения. Дело в том, что анализ результатов расчетов может указать на необходимость изменения класса рассматриваемых задач и открыть путь для новых теоретических исследований. Мы видим, что подход к проблеме оптимальности должен носить динамический характер: должны строиться оптимальные или близкие к ним методы для все новых классов задач, предъявляемых наукой и техникой, при изменении возможностей, предоставляемых ЭВМ.

При этом необходима как текущая работа, так и работа по доведению предложенных ранее постановок до окончательного решения. Для вычислительной математики, как и для всякой прикладной науки, характерна следующая обстановка. Обычно задачи новых типов предъявляются сначала в незначительном количестве и требуется срочное их решение любой ценой, не считаясь ни с какими затратами. На первом этапе применяется первый попавшийся приемлемый метод. Далее эти задачи поступают в большом количестве, производится более или менее удовлетворительная постановка задачи оптимизации методов и находится некоторое ее решение. Затем задача переводится на поток, т. е. решение задач этого типа производится при помощи пакетов соответствующих стандартных программ. Не следует думать, что на этом этапе полностью кончается исследование данного типа задач — чтобы создавать эффективные методы решения новых задач, нужно осмысливать те задачи, которые остались несколько позади, и проводить их теоретическое изучение. Иногда бывает целесообразно работу по быстрому решению первых поступивших задач серии и перспективную работу по созданию эффективных методов решения с самого начала организовать параллельно.

Соотношение между текущей и перспективной работой также является важнейшим фактором жизнедеятельности любой научной организации. В каждый момент времени организации предъявляются некоторые требования, выполнение которых необходимо для ее существования: самоокупаемость в случае хозрасчетных организаций, своевременная отчетность по годовому плану и т. п. Однако существуют и критические моменты времени, когда предъявляются повышенные требования к работе, например, необходимость своевременного решения новых классов задач. Поэтому при планировании работы должны предусматриваться какие-то теоретические разработки впрок, резервы людей, машинного времени.

Вернемся к вопросу об оптимизации методов.

Часто математик, создав оптимальный или близкий к нему метод решения задачи, сетует на то, что этот метод плохо внедряется в вычислительную практику. Ответ на этот вопрос может быть самым разным. Часто это происходит вследствие консерватизма практических работников, их желания работать старыми, привычными методами.

Иногда это объясняется недостатками самого метода. Например, случается, что кроме (и даже вместо) оптимальности метода желательны и существенны простота метода и возможность надежного контроля точности получаемых результатов. Может случиться, что сам класс рассмотренных задач не совпадает с классом, к которому относится большинство задач, поступающих для решения.

Конечно, нужно учитывать также вопрос о том, насколько широк возможный круг решаемых задач рассматриваемого класса. Если сейчас и в перспективе ожидается решение небольшого числа задач рассматриваемого класса, разработка оптимальных алгоритмов и создание стандартных программ решения задач этого класса могут себя не оправдать. В то же время изучение задачи оптимизации методов на различных классах часто полезно тем, что при решении возникают новые методы, которые затем находят применение и при решении задач из других классов.

<< Предыдущий параграф Следующий параграф >>
Оглавление