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

§ 10. Построение численных методов с помощью вариационных принципов

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

1. Метод Ритца.

Рассмотрим краевую задачу из §8:

Ее решение является точкой экстремума функционала

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

Задаются некоторым N и выбирают совокупность функций , с ограниченным интегралом условиям

Приближенное решение ищется в виде

Имеем

здесь

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

где А — матрица с элементами , — вектор с компонентами .

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

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

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

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

где М не зависит от .

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

где — не очень большое число. В случаях (4), (5), как правило, удается так организовать процесс решения системы (3), что суммарная вычислительная погрешность будет порядка .

В ряде случаев нетрудно построить системы функций, удовлетворяющие условию (4), но, как правило, для них матрица А является полностью заполненной. Для задачи (1) такой системой является

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

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

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

2. Метод Бубнова-Галеркина.

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

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

Задаются некоторой линейно независимой системой функций и требуют выполнения интегральных соотношений

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

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

Точно так же в случае нелинейного уравнения метод Бубнова-Галеркина сводится к решению нелинейной системы

3. Вариационно-разностный вариант метода Ритца.

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

Рис. 9.10.1

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

Это равносильно тому, что решение ищется в виде

при (см. рис. 9.10.1).

Система уравнений (3)

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

где

4. Вариационно-разностный вариант метода Бубнова-Галеркина.

Если умножим (1) на произвольную функцию и проинтегрируем первое слагаемое в выражении

по частям, то получим интегральное тождество

Будем искать решение в виде (9): потребуем, чтобы (13) обращалось в нуль для всех функций вида

— произвольные числа. Поскольку выражение линейно по , то получаем систему уравнений

В данном случае эта система уравнений совпадает с (3).

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

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

уже не являющуюся задачей на экстремум некоторого функционала. Умножим (15) скалярно на и проинтегрируем некоторые из слагаемых по частям; получим

Приближение вида (9) находим из системы уравнений

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

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

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

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

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

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

Заметим, что вариационно-разностные и проекционно-разностные методы называют также методами конечных элелшнтов.

5. Построение разностных схем путем аппроксимации функционала.

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

здесь .

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

Поделив предыдущее соотношение на , где , получим конечно-разностную схему

совпадающую со схемой (8.3) в случае равномерной сетки.

Выражение в (18) является многочленом второй степени от переменных оно записывается в виде

выше учтено то, что . Из (18) видно, что первые две суммы в неотрицательны. Поэтому

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

Задача 1. Доказать, что при матрица А положительно определена.

Чтобы проведенные рассуждения о неотрицательности матрицы А были справедливы, целесообразно строить аппроксимации функционала, приближая выражения, стоящие под знаком квадрата, не раскрывая скобок.

Пусть, например, исходная задача является задачей на экстремум функционала:

Интеграл от первого слагаемого приближаем выражением

от второго — так же, как в (18). Все проведенные выше рассуждения остаются в силе, и поэтому соответствующая матрица А неотрицательна. Если раскрыть скобки в , а потом аппроксимировать интеграл, то может случиться, что условие при крупных шагах будет нарушено.

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

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

6. Случай невариационной задачи.

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

для любой функции . Имеем

Полагая и собирая коэффициенты при одних и тех же , получим

где определено формулой (19). Выражение равно нулю для любой сеточной функции , если все . Полученная система уравнений совпадает с системой уравнений (19).

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