Метод Простой Итерации с подбором оптимального параметра

[Sboy]

Всем добрый день.

Возникла необходимость реализовать МПИ с подбором оптимального параметра. Собственно проблему вызвал именно подбор параметра. По определению он будет равен
$\tau = \frac{2}{\lambda_{n}-\lambda_{1}}$
где $\lambda_{n}, \lambda_{1}$ наибольшее и наименьшее собственные числа СЛУ. Проблема возникла в том как наиболее быстро найти эти значения. У меня возникли две идеи: Или в лоб Гауссом считать, либо както применять теорему Гершгорина, правда последняя дает только оценку того какими могут быть собственные числа, а мне нужны точные значения. Метод я применяю для решения задачи Дирихле для уравнения Пуассона, возможно для этого случая есть какойто более простой способ, т.к. матрица имеет специальный вид(блочно-трехдиагональная) и в каждой строке вобщемто одни и теже значения встречаются. Вобще матрицу я не храню, т.ч. Гаусс отпадает сразу...
Ктонибудь может предложить какойнибудь метод для решения это проблемы?
Заранее спасибо.

[ewert]

Sboy в сообщении #565448 писал(а):

Проблема возникла в том как наиболее быстро найти эти значения.

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

В общем, шаг подбирается только методом научного тыка.

[мат-ламер]

Книга была. Хейгеман, Янг. Прикладные итерационные методы.

[Sboy]

А тот факт, что все собственные числа матрицы у меня лежат либо внутри, либо на границах кругов Гершгорина с центром в точке $-2(\frac{1}{h^{2}}+\frac{1}{k^{2}})$ и радиусами:
$2(\frac{1}{h^{2}}+\frac{1}{k^{2}})$,
$\frac{1}{h^{2}}+\frac{1}{k^{2}}$,
$\frac{1}{h^{2}}+\frac{2}{k^{2}}$,
$\frac{2}{h^{2}}+\frac{1}{k^{2}}$
не дает никакой информации о том какие значения стоит перебирать? И как вобще по этим данным можно проводить оценку?

[ewert]

Ну то, что верхняя граница спектра асимптотически равна $\dfrac8{h^2}$ -- это святое. И это действительно можно и нужно использовать. А вот про нижнюю границу ничего определённого не скажешь, кроме того, что она порядка единицы. Ну можно грубо оценить её через наименьшее собственное число настоящего лапласиана в прямоугольнике похожих размеров.

[Sboy]

В книге, которую посоветовал мат-ламер(отдельное спасибо за неё), описывается, что для равномерной по x и y сетки (шаг по обоим размерностям примем за h) на еденичной квадратной области минимальное и максимальное собственное число можно вычислить при помощи формул:
$m(A)=8\sin^2 (\frac{\pi h}{2})$
$M(A)=8\cos^2 (\frac{\pi h}{2})$
Надо полагать что при обобщении этих выкладок на сетку с различными шагами по x и y(пускай будут h и k соответственно), формулы примут вид:
$m(A)=min \left\{\begin{matrix}{8\sin^2 (\frac{\pi h}{2})} \\ {8\sin^2 (\frac{\pi k}{2})} \end{matrix}\right.$
$M(A)=max \left\{\begin{matrix}{8\cos^2 (\frac{\pi h}{2})} \\ 8\cos^2 (\frac{\pi k}{2}) \end{matrix}\right.$

Или я ошибаюсь?
А вот каким образом обобщить эти выкладки на область:
$x \in [0; a]$
$y \in [0; b]$

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

[Sboy]

выше я не правильно написал...

Я представил разностную схему в операторном виде:
$\Lambda_{1}u_{m,l}+\Lambda_{2}u_{m,l}=f_{m,l} $
где $\Lambda_{i}$ центральный разностный оператор по х и по у.
Нашел собственные функции и собственные числа для каждого из них, получил такие собственные числа:
$\frac{4}{h^2}\sin(\frac{p\pi}{2M})$
$\frac{4}{k^2}\sin(\frac{q\pi}{2N})$
для первого и второго оператора соответственно, где M,N - число узлов по соответствующей размерности, h,k -шаг, p,q -номер с.ч.
Обозначил:$\Lambda = \Lambda_{1} + \Lambda_{2}$
В лоб подставив и проверил что для нового оператора собственными числами и ф-и имею сумма с.ф. и с.ч. уже найденных.
Нашел наименьшее и наибольшее с.ч. нового оператора:
$\lambda_{min}\approx 2\pi^{2}$
$\lambda_{max}\approx 4(M^2+N^2)$
и соответственно:
$\tau_{оптимальное}=\frac{1}{\pi^2+2(M^2+N^2)} $
Такая оценка похожа на правду? Или я гдето серьезно ошибся?
Вродибы для прямоугольной сетки подходит, но что делать в случае, когда в сетке есть вырез?