2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Численные методы - задача Дирихле
Сообщение23.05.2012, 12:47 
Привет!

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

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

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

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

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

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

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

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 13:04 
Аватара пользователя
yanvladimirovich в сообщении #575044 писал(а):
Пока я нашёл решение - прогонка усреднения по четырём соседям.
Что такое "прогонка усреднения по четырём соседям"?
Сколько узлов в "большой сетке"?

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 13:12 
TOTAL в сообщении #575057 писал(а):
Что такое "прогонка усреднения по четырём соседям"?

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 13:18 
Аватара пользователя
ewert в сообщении #575062 писал(а):
TOTAL в сообщении #575057 писал(а):
Что такое "прогонка усреднения по четырём соседям"?

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

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

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 13:42 
Цитата:
Сколько узлов в "большой сетке"?


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

-- 23.05.2012, 13:49 --

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


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

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

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

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 14:00 
Аватара пользователя
Попробуйте вот такую схему при больших $\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$ (используются значения на горизонтальных границах)
минус линейная интерполяция по значениям в четырех углах

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 14:59 
Поправьте, если я не прав.

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

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

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 15:04 
TOTAL в сообщении #575083 писал(а):
Скорость сходимости к стационарному решению зависит от начальных данных.

Нет.

yanvladimirovich в сообщении #575108 писал(а):
нужели никто и нигде не исследовал мультимасштабный подход?

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение23.05.2012, 18:02 
Цитата:
Кто-то где-то когда-то использовал. Только качественного ускорения он всё равно не даст.


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

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

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

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение24.05.2012, 09:13 
Аватара пользователя
yanvladimirovich в сообщении #575108 писал(а):
Так вот, быстрее чем за 500 итераций мы не получим значение в центре этой сетки, не важно каким методом. Значения с края до центра раньше, чем за 500 шагов, просто не дойдут никак.
За одну итерацию дойдут, т.к. схема неявная.

 
 
 
 Re: Численные методы - задача Дирихле
Сообщение24.05.2012, 20:39 
TOTAL в сообщении #575455 писал(а):
За одну итерацию дойдут, т.к. схема неявная.

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

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group