• Метод координатного спуска

Идея всех методов спуска состоит в том, чтобы исходя из начального приближения - точки  Dⁿ (Dⁿ - область определения функции) перейти в следующую точку D так, чтобы значение  уменьшилось, т.е. .

Рассматриваем функцию при фиксированных значениях как функцию одной переменной . Находим одним из описанных выше методов . Значение  доставляющий минимум обозначаем . 

После нахождения точки минимума по координате  переходим к нахождению минимума по координате  от новой точки и так далее по всем оставшимся координатам.

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

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

• Градиентный метод

Пусть функция  непрерывно дифференцируема на , а 

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

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

Пусть  выбрано. Тогда градиентный метод заключается в построении последовательности {} по правилу ,  , .- длина шага или просто шаг градиентного метода.

Если , то шаг можно выбрать так, чтобы . Если , то - точка минимума функции . В этом случае итерационный процесс прекращается.

Существуют различные способы выбора величины в градиентном методе. В зависимости от способа выбора можно получить различные варианты градиентного метода.

На луче, направленном по антиградиенту, введем функцию одной переменной , и определим  из условий .

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

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

Тема лекции № 12. Дифференциальные уравнения в частных производных

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

Математические модели сплошной среды приводят к уравнениям в частных производных, которым удовлетворяют упомянутые средние величины. Например, изменение температуры в неподвижном теле описывается уравнением теплопроводности

Гдеu u— температура, с — теплоемкость, k— коэффициент теплопроводности и q — плотность источников тепла.

К уравнениям в частных производных приводят задачи газодинамики, теплопроводности, переноса излучения, распространения нейтронов, теории упругости, электромагнитных полей, процессов переноса в газах, квантовой механики и многие другие.

Независимыми переменными в физических задачах обычно являются время t и координаты, бывают и другие переменные, например, скорости частиц v в задачах переноса. Решение требуется найти в некоторой области изменения независимых переменных.

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

Если одной из переменных является t, то чаще всего рассматривают области вида

т. е. решение ищут в некоторой пространственной области и на отрезке времени. В этом случае дополнительные условия, заданные при t=t₀ называют начальными, а дополнительные условия, заданные на границе области - граничными или краевыми.

Задачу, у которой имеются только начальные условия, называют задачей Коши. Например, для уравнения теплопроводности (1) в неограниченном пространстве можно поставить задачу с начальными условиями

Если u— кусочно-непрерывная ограниченная функция, то решение задачи (1), (3) единственно в классе ограниченных функций (при некоторых ограничениях на коэффициенты уравнения).

Задачу с начальными и граничными условиями называют смешанной краевой задачей или нестационарной краевой задачей. Для уравнения (1) дополнительные условия такой задачи могут иметь, например, вид

Для этого уравнения допустимы и другие граничные условия, например, содержащие нормальную производную решения.

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

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

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

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

Напомним классификацию таких уравнений. Они имеют следующий вид (для простоты мы ограничиваемся случаем двух переменных):

Коэффициенты уравнения (5), вообще говоря, зависят от u, х, у. Если коэффициенты не зависят от переменных, то это линейное уравнение с постоянными коэффициентами. Если F линейно зависит от u, а остальные коэффициенты от и не зависят, то это линейное уравнение с переменными коэффициентами. Если коэффициенты зависят от u, то уравнение (5) называется квазилинейным.

Если А=В=С=0 то уравнение (5) имеет первый порядок и называется уравнением переноса.

Уравнения второго порядка классифицируются по знаку дискриминанта D=B²-AC. У гиперболических уравнений дискриминант положителен, у параболических — равен нулю, у эллиптических — отрицателен.

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

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

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

К таким методам относятся метод распространяющихся волн, метод разделения переменных, метод функций источника и другие.

К параболическим уравнениям приводят задачи теплопроводности, диффузии и ряд других. Типичной полной постановкой одномерной задачи является, например, первая краевая задача для случая линейной теплопроводности в однородной среде: (16)

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

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

соответствуют заданию тепловых потоков через границы.

Условия третьего рода

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

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

Строго говоря, параболическое уравнение лишь приближенно описывает процесс теплопроводности. На самом деле скорость распространения тепла конечна и не превышает (при молекулярной или электронной теплопроводности) тепловой скорости частиц. Влияние же удаленных точек, как видно из выражения для функции Грина (5), ослабевает очень быстро.

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

2. Семейство неявных схем.

Рассмотрим простейшие, но хорошие разностные схемы для уравнения теплопроводности (1) с постоянным коэффициентом:

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

Здесь записано меньше уравнений, чем имеется неизвестных. Недостающие два уравнения находим из краевых условий; например, краевые условия первого рода (2) дают соотношения

Рис. 1.

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

Если, то схема (6) существенно неявна. Перепишем ее в следующем виде:

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

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

Замечание 1. Схема (6) использует только четыре точки шаблона и называется чисто неявной. Схему называют схемой с полусуммой или симметричной (имеется в виду симметрия по времени, ибо схема (6) симметрична по пространству при любом а).

Аппроксимация. Разложим решение в узлах шаблона рис. 1 по формуле Тейлора, выбирая за центр разложения точку Тогда получим

где все производные отнесены к центру разложения. Подставляя эти разложения в выражение невязки схемы (6а), получим

Отсюда видно, что симметричная схема имеет более хорошую аппроксимацию

Надо проверить аппроксимацию не только уравнения, но и начальных и краевых условий. Начальное условие (16) и краевые условия первого рода (2) мы аппроксимировали точно, положив. Аппроксимация краевых условий второго или третьего рода уже не была бы точной, а содержала бы некоторую погрешность.

Замечание 2. Для k = const за счет специального выбора веса и правой части можно построить схемы повышенной точности. Для решения дифференциального уравнения (1а) справедливо соотношение

Подставляя его в (9), преобразуем невязку:

Если положить

то обе квадратные скобки в (10) обратятся в нуль и погрешность аппроксимации схемы (6), (11) уменьшится. Удерживая в формуле Тейлора (8) большее число членов, можно показать, что невязка (10) при этом уменьшится.

Замечание 3. Можно заменить в (11) второй пространственной разностью, получая следующее выражение для правой части:

Этот вариант схемы повышенной точности имеет аппроксимацию также.

Замечание 4. Приведенные оценки аппроксимации справедливы, если непрерывны те производные решения, которые входят в выражение главного члена невязки.

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

Следовательно, схема (6) устойчива, если при любом q выполняется условие (2). Нетрудно проверить, что это справедливо при

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

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

Оно более жестко, чем условие (14), но в случае явной и чисто неявной схем из него следует сделанное выше утверждение.

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

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

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

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

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

Таким образом, неявные схемы монотонны только при очень малом шаге по времени. Единственное исключение — чисто неявная схема, которая монотонна при любых шагах.

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

Замечание. Монотонные схемы для параболического уравнения могут иметь второй порядок точности по пространству. Но, как и для уравнения переноса, для параболического уравнения не известно ни одной монотонной схемы, которая имела бы второй порядок точности по времени (хотя никаких теорем о невозможности построения таких схем не доказано).

Рис. 2

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

Плохие качества явных схем обусловлены одним принципиальным ограничением: явная схема для параболического уравнения может сходиться, только при определенных условиях. В самом деле, пусть решение в точке нового слоя выражается через n точек исходного слоя, т. е. через отрезок длиной H (рис. 3). Тогда оно выражается через отрезок нулевого слоя длиной H b этот отрезок будет зоной влияния. Для точного решения зона влияния бесконечна. Значит, сходимость к точному решению возможна, только если дополнительно  выполняются условия сходимости, что и требовалось доказать.

Рис. 3.

Двусторонняя схема бегущего счета, как показывает более детальный анализ, сходится со скоростью

Сходимость для своего доказательства требует оценок аппроксимации. Это связано с громоздкими выкладками, поэтому приведем только окончательный результат.

Монотонность схемы имеет место при достаточно малом шаге по времени:

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

Замечание. Коэффициенты разностной схемы вычисляются с некоторыми ошибками, что может привести к искажению решения. Устойчивость разностного решения относительно изменения коэффициентов называется коэффициентной устойчивостью (ко-устойчивостью).

Тема лекции № 13. Задачи линейного программирования