Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 24
Текст из файла (страница 24)
На гладких функциях алгоритм буддот работать боксе эффективно, поэтому время, затрачиваел1ое на их решение, будет меньша времени, затрачиваемого на решение задач с негладкими функциями. 50% экономии времени при вычислении интегралов от гладких функций принесет меньшую вьподу, чем б0% экономии времени при вычислении интегралов от негладких функций. Следовательно, целесообразнее уделить внимание эффективности алгоритма в случае негладких функций.
Конечно. вывод будет другим, если доля негладких функций будет мала. При отыскании оптимального метода решения класса залсч в случае, когда предполагается непосредственное внедрение алгоритл1а в вычислительную практику, обычно возвикает следующая проблема: нам не удается сразу найти оптиыальный метод решония задач рассматриваемого класса. После некоторого вреыени работы мы находим какой-то метод, иногда близкий к оптимальному, иногда просто лучший, чек~ ранее известные, а затем постепенно совершенствуем его. Б какой момент надо остановиться в усовершенствовании метода и перейти к составлению стандартных программ решения этого класса за,чач? При ответе па этот вопрос надо учитывать следугощие простые соображения.
Если мы поспешим и бьк;тро начнем внедрять только что полученный алгоритм, то, может быть, нам придется вскоре создавать новые алгоритмы из-за плохого качества этого алгоритьи. Затягивание времени прн составлении стандартных программ также нежелапльно: при этоь~ мы допустим большой перерасход машинного вреыени при решении задач по имеющимся стандартным программам. Можно возразить, что сгпдание совершегшых стандартных программ приведет к большой зкономии машинного времени в будущем.
Однако при анализе этого возражения в свою очередь следует учесть, что ыашинное время сгаэювитс» все менее дефицитныы и более дегпевым. Кро- 128 Глава 3. Числеиоое ш«отрировэвиг ме пяю, чем раньше мы решим ту или иную задачу, тем болыпую реалыгую пользу получит общество в целом. Нужно учитывать также важность бьптрого внедрении вновь созданных алгоритмов для самой задачи отыскания оптимальных методов ре. щения. Дело в том, что анализ результатов расдотов может указать на необходимость изменения класса рассматриваемых задач и открыть дуть дл» новых теоретических исследований.
Ыы видим, что подход к пробзюме оптимальности должен носить Линвмический характер: долзкны строитыш оптимальные или близкие к вим ья;годы для все новых классов зздюк прсдьявляемых наукой и техникой, ггри изменении возможностей, предоставляемых ЭВЫ. При игом необходима как текущая работа, так и работг по доведению предложенных ранее посгановок до окончательногп решения. Для вычислительной математики, как и для всякой прикладной науки, характерна сведующая обстановка. Обычно задачи новых типов предъявляются сначала в незначительном количестве и требуется срочное их решеггяе любой ценой, не считаясь ни с какилги затратаыи.
На первом этапе применяется первый попавшийся приемлемый мешд. Далее зтя задачи поступают в большом количестве, производится более или менее удовлегворитсльпая постановка задачи оптимизации мотодов и находится некоторое ее решепве. Затем задача переводится па поток, т.е. решение задач этого типа производится при помощи пакетов соответствующих стандартных программ. Но следует думать, что на этом этапе полностью кончается исследование данного типа задач — чтобы создавать эффективные методы решения новых зщ~ач, нужно осмысливать те задачи, которые остались несколько позади, и проводить их теоретическое гпучеиип Иногда бывало целесообрсюно работу по быстрому репгению первых поступивших задач серии и перспективную работу по созданиго зффоктивных методов решения с самого начюга организовать параллельно.
Соотношоние между текущей и порспективяой работой также является важнейгпим фактором жизнедеггпльности лкзбой научной организации. В каждый момент времени орпгпизации предч являкпся некоторые требования, выполнение которых необходимо для ее существования: самоокупаглгость в гшучае хозрасчетных организаций, своевременная отчет ность по годовому плану и т.п. ()днако сугцесчвуют и критические моменты времени, когда предъавллюгся повышенные требования к работе, например, необходимость своевременного регпения новых «лаосов задач.
Поэтому при планировании работы должны прелусматригмться какишто теоретические разработки впрок, резервы людей, машинного времени. Вернемся к вопросу об оптиыизации методов. Часто математик, создав оптимальный или близкий к ному метод решения задачи, сетует ва то, что этот л~еп)ц плохо внедряется в вычислительную практику.
()тает на этот вопрос может быть самым разным. Часто зчо происходит вследствие консерватизма практических работни- 1гй 1 10. Посшиоввв задачи оптиланвции квахрлгур кав, их желания работать старыыи, привычными методами. Иногда это объясняется недостатками самого ьлшода. Например, случается, что кроме (и даже вместо) оптимальности мпгода желательны и существенны простота метода и возможность надежного контроля точности получаемых 1хпультатов. Может случитъся, что сам класс рассмшреиных задач ве лхлвпвдаез с классом, к которому относится больпзинство зада~, пагтупагощих для репзсния.
Конечно, нужно учитывать также вопрос о том, насколько широк возможный круг решаемых задач расгмгйривввмого класса. Бгли сейчас н в перспективе ожидается решение неболыпого числа зада*с рвссматрилаемого класса, разработка оптилиппиых алгоритмов и создание стацпартных программ решения задач втого класса могут себя ие оправдать. В чо же время изучение зада*ли оптимизации методов на различных к.пассах часто полезно тем, гш нри решении возникгппг повью методы, которые затем находят применение и при решении задач из других классов.
9 10. Постановка задачи оптимизации квадратур Рагсуждспии 1 9 показывают вежноггь изучения разли шых постановок проблемы оптимизапии методов ва кпыхвх функций. ры:смотрим зщсачу вычисления интеграла 1(.() = ( ЙР)ул(Р) йР. уа Область игпегриравания П и весовая функция р(Р) предпапапигптя фик- сированными. Класс рассматриваемых задач определим заданием класса Р падынтегральиых функций. 11огретшослпьло хепдраплррлп 1ц) = Рлу) =. т~ одру) иа кпоссс Р нвзыватт величину Лн(Р) = впр(11п'(()(, 1гл Вл (У) = 1(У) — 8ь (.().
И'п(Р) = шЕ Вп(Р) п,д где, «ак обычно, Нижняя грань называется оптимальной оцспхой пагрситости пеадраплур иа рзссмалврпеасмом клпссе. Еспи существует квадратура,,пля кптарай Вп(Р) = И'л'(Р), то такуго квадртуру ллазываюг оптимальной или иаилтлтсй по расгматриеае.иом классе. 5 ягз Глава 3. 1ислгввоо витстрироеани~ 130 Б 'З 2 была получена оценка (2.4) погрепшости квадратуры, точной для многочлеиов степени ш, через (ш+1)-ю оронзвгщиую функцви.
Эта оценка является неулучшаемой (см. задачу 2.3). Таким образом, для классов функций Р: (/( +)(я)(<А при тб(а,б) величина Вл(г) известна и задача погтроепня оптилшльпой квадратуры сводится к нахождению козффиционтов и уапов, на которых доствгиегся нижняя грань ВЛ(г').
Для ряда классов функций чту закачу удалось решить. Например, при гп = 0 гакой квадратурой звляеггя состввнаи формула прямоугольников / /(х)4х — ) /( ) с оценкой погрешности (Вк[/)( А/(4Ж). (Доказать!) !3 настоящее время оптимальные квадратуры получены двя ягбольшопз набора классов функций, в основном одвой перомепиой. Непосредственное значение зтих квадратур ддя приложений невелико, однако зто не значит, *по пе нужно заниматься построением тпсих квадратур. Построение оптимальных квадратур и дальнейпгее их рвювнтие на случай большей гладкости и болен~его числа переменных оюыалнсь цснпыыи не получением конкретных квадратурвых формул, а выяснением качественной стороны вопрога: где какие методы ау ппе, на какую точность можно рассчитывать при иглслшовании определенной информации о подынтегральной функции, какова плотность распределения узлов у «хорошейь квадратуры.
Пусть, например, при первоначальном аналнзе задачи мы решили воспользоваться инфорыацней об ограниченности первой производной )/'(х)) < А; оценка погрешности (1) нас не устраивает, поскольку для достижения нужной точигюти е требусгся слишком бовыпое число узлгяс если А/(41г') < е, то г/ > А/(4е).
Оптимальность оценки (1) указывает на необходимость сужения класса расгьштриваемых задач пучек~ учета допопнительной инфорыации о подынтегрвлыгой функции (ограниченность второй производной, тип особой точки подьштегральной функции, аналитичьюсть и т.п.) или расширения множества используемых методов интегрирования.
181 Э 11. Оптимизация распределеян» узлов 8 11. Оптимизация распределения узлов квадратурной формулы развитие методов численного интегрирования могло бы пойти но пути создания оптиыальных методов на различных классах С,(А; ]о, Ь]) и создания программ на основе этих мшодов. Здесь и далев Сг(А; ]а, Ь]) класс функцвй с кусочно-непрерывной г-й провзнодной, удовл«творяющей условию ]1 ' (х)~ < А при х е [о, ь] Вскоре после начала рассмотрении залач оптимизации меэодоэ спло ясно, что уже известные на этих классах методы с оценкой погрешности (8.7) педюзеки от оптимальных.
Как увидим в Ь' 7 гл. б, за гчет оптимизации квэдратурной формулы оценка погрепшостя (8.7) на рассматриваемых классах пе может быть улучшена по порядку. Нри этом т1кже стала ясно, гго некоторыо ьгнгоды, практически совпадаюп1ие с методами Эйлера и Грегори (см. Ь' 13), являются асимггготически оптимальными по оценке главного члена ногрешносги. Имеется в вину следующее. Дая этих методов на соответствующих классах функпий были получены оценки погрепшостн с„/17" -~- се ы /Ж' ' в то время как штя оптимальных на этик классах методов оценка по- грошности имеет вид ;,77 + С(1(Л"к Ы).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
