Численные методы - задача Дирихле

[yanvladimirovich]

Привет!

Скажите, есть специалист по численным методам решения задачи Дирихле?

Есть сетка. Задана граница, пусть по узлам сетки. Граница произвольная.

Нужно численно решить дифур $d^2f/dx^2+d^2y/dy^2$=0.

Пока я нашёл решение - прогонка усреднения по четырём соседям. Но такой метод сойдётся на большой сетке не быстро. Если сетка nxn, то нужно как минимум n/2 итераций.

А хочется, чтобы быстро.

У меня пока пришла в голову одна идея. Огрубить, скажем, сетку в 8 раз по обоим направлениям. Сделать несколько итераций. Потом - интерполировать результат на сетку, огрублённую в 4 раза. Взять его за старт, сделать несколько итераций. И так далее.

Скажите, этот метод рабочий?

[ewert]

В принципе, такая идеология используется; правда, я с ней никогда не работал. В любом случае в методе простых итераций качественно сходимость не ускоришь -- так и останется порядка $q^k$ с $q\sim1-Ch^2$. Погуглите на "метод релаксации" или "метод дробных шагов" (он же "схема переменных направлений"). Оба варианта дают ускорение на порядок -- до $q\sim1-Ch$; тоже медленно, конечно, но всё же во много раз быстрее. (Последняя схема сложнее, но зато абсолютно устойчива.)

[TOTAL]

yanvladimirovich в сообщении #575044 писал(а):

Пока я нашёл решение - прогонка усреднения по четырём соседям.

Что такое "прогонка усреднения по четырём соседям"?
Сколько узлов в "большой сетке"?

[ewert]

TOTAL в сообщении #575057 писал(а):

Что такое "прогонка усреднения по четырём соседям"?

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

[TOTAL]

ewert в сообщении #575062 писал(а):

TOTAL в сообщении #575057 писал(а):

Что такое "прогонка усреднения по четырём соседям"?

Просто метод Якоби;

Если Якоби, то пусть хотя бы на Зейделя поменяет.

Вот похожая тема http://dxdy.ru/topic45576.html, где используется метод стабилизирующей поправки (правая часть второго шага там записана с ошибкой)

[yanvladimirovich]

Цитата:

Сколько узлов в "большой сетке"?

Вообще, это часть другого алгоритма, который используется в обработке изображений. Нужно по значениям на краях "залить дырку". Таким образом, несколько миллионов может быть, около 1000 на 1000, например.

-- 23.05.2012, 13:49 --

Цитата:

Если Якоби, то пусть хотя бы на Зейделя поменяет

Это можно сделать, но оно не решит проблему принципиально, и сделает программу несколько более недетерменируемой при парралельной обработке, насколько я понимаю.

Сейчас совершенно не важна точность решения, 10 процентов хватит с головой.

Вместе с тем, решение должно работать очень, очень быстро.

Кстати, а существует неитерационное решение задачи? Если посчитать точные значения для каких-то "опорных" точек внутри контура, и потом уже итерационно "отталкиваться" от них?

[TOTAL]

Попробуйте вот такую схему при больших $\tau.$ Прогонки можно выполнять параллельно.

$(1-\tau\Lambda_{xx})\xi^{n+1/2}=\tau(\Lambda_{xx}+\Lambda_{yy})f^n$
$(1-\tau\Lambda_{yy})\xi^{n+1}=\xi^{n+1/2}$
$f^{n+1}=f^n+\xi^{n+1}$

здесь $\Lambda_{xx}, \; \Lambda_{yy}$ - трехточечные аппроксимации вторых производных


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

А вдруг так полученное начальное поле уже годится для "заполнения дырки"?

[yanvladimirovich]

Поправьте, если я не прав.

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

А это в нашем случае, повторюсь, слишком долго.

Я всё-таки удивлён, нужели никто и нигде не исследовал мультимасштабный подход?

[ewert]

TOTAL в сообщении #575083 писал(а):

Скорость сходимости к стационарному решению зависит от начальных данных.

Нет.

yanvladimirovich в сообщении #575108 писал(а):

нужели никто и нигде не исследовал мультимасштабный подход?

Кто-то где-то когда-то использовал. Только качественного ускорения он всё равно не даст.

[yanvladimirovich]

Цитата:

Кто-то где-то когда-то использовал. Только качественного ускорения он всё равно не даст.

Хм... А это не мультисеточные методы?

Пишут, что быстрее.

http://www.csa.ru/~stan/multigrid/mm1.html

[TOTAL]

yanvladimirovich в сообщении #575108 писал(а):

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

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

[ewert]

TOTAL в сообщении #575455 писал(а):

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

Практически не дойдут. А что ничтожная их доля всё-таки дойдёт -- на качестве счёта никак не скажется. Точность схемы для уравнения теплопроводности не связана с её явностью или неявностью.