Целесообразность построения экономичных алгоритмов.

    При исследовании алгоритмов желательно иметь ответы на следующие вопросы:

ü Устойчив ли алгоритм к возмущению входных данных;

ü Какова оценка погрешности алгоритма;

ü Какова трудоемкость алгоритма;

ü Какова робастность алгоритма – качество алгоритма и программы его реализующей;

ü Каковы емкостные оценки потребности алгоритма.

До сих пор вопрос о реализации на ЭВМ не рассматривался, т.е. не говорилось как лучше решать полученные в результате аппроксимации сеточные уравнения.

Рассмотрим модельную задачу.

Задачу Дирихле для уравнения Пуассона в прямоугольнике:

В области  требуется найти решение уравнения:

(1) ,

если заданы граничные условия:

(2) .

Построим сетку

,

.

  Непрерывную задачу (1), (2) будем аппроксимировать разностной задачей:

(3) ,

(4) .

Для простоты будем считать, что .

  За счет переформулирования задачи: корректировки правой части в приграничных узлах, ее можно свести к задаче с однородными граничными условиями.

  Приведем краткую сводку методов решения задачи (3), (4) и асимптотических оценок их трудоемкости. Будем рассматривать двухслойные методы решения.

(5) ,

 - оператор стабилизатор,

 - итерационный параметр,

s – номер итерации.

Считаем, что , т.е. сходится к .

В операторном виде задача запишется как .

ü Метод Якоби.

Если ,

.

Здесь, как и далее  - достигаемая точность. .

(6) ,   - вектор невязки.

    Если , то считаем, что нужная точность достигнута и прекращаем итерационный процесс.

Для модельной задачи считаем с большой степенью точности .

Число итераций, необходимое для решения модельной задачи (3), (4) методом Якоби  оценивается следующим образом:

.

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

 

ü Метод Зейделя.

    Формально он не на много лучше метода Якоби.

    Если ,  - строго нижняя и верхняя части оператора , .

Счет по формуле (5) начинается из левого нижнего узла сетки.

.

Если матрица  имеет строгое диагональное преобладание, то метод Зейделя существенно лучше метода Якоби.

 

ü Метод верхней релаксации.

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

1. по методу Зейделя делают итерацию в данной точке , находят ,

2. затем, не сдвигаясь в другую точку, уточняют .

Асимптотика метода: .

Арифметическая работа  операций.

 

ü Явный чебышевский метод.

    Этот метод получается из (5), если , а  определяется специальным образом из условия минимизации нормы операторного полинома к-ой степени.

, - полином (s+1)-ой степени относительно А, обозначим его через .

, но для этого надо точно знать оценки для .

Асимптотика метода:

.

Арифметическая работа  операций.

    Итак, мы рассмотрели все простые методы. Улучшения достигаются переходом к градиентному или попеременно-треугольному (ПТМ) методам.

В схеме (5) оператор .

 

ü Попеременно-треугольный метод (ПТМ), метод переменных направлений,

    .

    В этом методе каждая итерация состоит из двух полуитераций.

Сначала из нижнего левого угла перемещаемся в верхний правый и наоборот.

ПТМ с чебышевским ускорением имеет более лучшую оценку для числа операций чем метод верхней релаксации (МВР), т.е.

.

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

    Таким образом, число операций, приходящихся на один узел сетки для одной итерации, применительно к задаче (3), (4), если не брать итерационный метод типа МПН, есть величина от  до .

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

 

Опр. 1   Экономичных методов.

 

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

Примеры экономичных методов.

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

,

.

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

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