Модели и алгоритмы решения задач математической физики на ориентированных графах и их приложение в квантовой механике тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат физико-математических наук Степовой, Дмитрий Владимирович

• Степовой, Дмитрий Владимирович
• кандидат физико-математических наук
• 1998

Оглавление диссертации кандидат физико-математических наук Степовой, Дмитрий Владимирович

Содержание

Введение

Глава 1. Гармонические и субгармонические функции на

ориентированных графах

1.1. Основные понятия и определения

1.2. Принцип максимума

1.3. Формулы Грина

1.4. Задача Дирихле

Глава 2. Спектр оператора Лапласа

2.1. Некоторые оценки спектра лапласиана

2.2. Декомпозиция задачи нахождения спектра лапласиана

Глава 3. Функция Грина оператора Лапласа

3.1. Некоторые сведения из общей теории графов

3.2. Обобщенно-гармонические функции

3.3. Потенциальный оператор

3.4. Функция Грина и ее связь с амплитудой Грина комплексной марковской цепи

3.5. Нахождение амплитуды вероятности

Глава 4. Дискретные аналоги классических уравнений

математической физики

4.1. Волновое уравнение на ориентированных графах

4.2. Уравнение теплопроводности на орграфах

Приложения

Приложение 1. Матрицы, ассоциированные с графами . 73 Приложение 2. Нахождение границы конечных оргра -

фов

Приложение 3. Решение задачи Дирихле на конечных

графах

Приложение 4. Листинги программ

Список литературы

Введение диссертации (часть автореферата) на тему «Модели и алгоритмы решения задач математической физики на ориентированных графах и их приложение в квантовой механике»

Введение

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

Оператор Лапласа на графах возникает в нескольких различных контекстах. Например, если граф в q-peгyляpный и А - матрица смежности О, тогда лапласиан Д=(1/я)А - I. Рассматривая А, как простое случайное блуждание на в, получаем аналог оператора Лапласа-Бельтрами в теории броуновского движения.

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

Приведем обзор наиболее существенных работ и результатов в них.

Так, например, в [46] рассматривается отношение между спектром лапласиана А и геометрией бесконечного неориентированного графа в, а также существование гармонических, суб- и супергармонических функций с некоторыми дополнительными условиями. В этой работе показывается, что наименьшее собственное значение лапласиана ко на бесконечном неориентированном графе С=(Х,и) (X - множество вершин, и- множество дуг) относится к геометрии графа в посредством дискретной версии неравенства Чигера (Cheeger). Константа Чигера графа в задается равенством

h = h(G) = M®,

v J YczX S(Y)

здесь L(dY) и S(Y) дискретные аналоги длины границы и площади для подможества Y с X.

L(m = \{[у,х] \уе¥,.хеХ\ У}|; S(Y) = £

xbY

где d(jc) - степень вершины х.

Там же доказана теорема о том, что для любого бесконечного связного графа G справедливо равенство

к2

<Лп <h<\.

2

Далее, если М(/) - площадь шара радиуса / с центром в вершине jc , то числа у, р, определяемые ниже, задают меру роста графа G.

y=y(G)= lim inf M(l)1/1, p=p(G)= lim sup M(Z)111.

/->00 /—>00

Доказано неравенство Xo< h< 1-1/y.

В частности, если G имеет субэкспоненциальный рост (р=1), то

Xo=h=0.

В работе [49] выявлена связь между спектром оператора Лапласа на конечном неориентированном графе G=(X,U), |х| =п, и спектром лапласиана на подграфах графа G. Так, все собственные значения лапласиана на графе G удовлетворяют неравенству

X k - к-ое собственное значение.

Пусть Gi ...Gr произвольные подграфы графа G такие, что intGj =0, а Л'к- к-ое собственное значение лапласиана на Gt. В работе

доказана теорема о том, что число Х= min {Л!к} не меньше, чем к-ое соб-

i

ственное значение оператора Лапласа на всем графе G.

В работе [50] приводятся оценки спектра лапласиана на неориентированном графе Gen вершинами. Доказана следующая теорема.

Пусть G=(X,U) конечный связный граф, |х | =п, и пусть к >2 целое такое, что кХп. Тогда

A¿(G) >2-2cos(7t/(2m+l)), где m=[n /к].

В случае, когда к | п справедливо неравенство Лк(0)>Щп1к)-\ + вк), где функция Р определяется следующим образом: для целого к и <9е(0,1], Р{к + в) равно первому собственному значению лапласиана на пути длины к с граничным ребром веса 0.

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

А именно. Пусть h(G) константа Чигера, определим hю =lim h(G~K),

К.

где К пробегает по всем конечным подграфам графа G. Известно, что 0<h<hM <1.

Обозначим спектр лапласиана Spec(A), а существенный спектр Ess(A). Доказана теорема: = 1 тогда и только тогда, когда Ess(A)= {1}. Пусть Т- бесконечное дерево. Фиксируем вершину реТи рассмотрим K{r) = inf{d+ (x) |jc e T, p{p,x) > r},

здесь d+ (x)- степень исхода вершины x, p-расстояние.

Если Т такое дерево, что lim К (г) = со, то дерево Т называют быстро

Г-> 00

ветвящимся.

Следствие к теореме: если Т- быстро ветвящееся дерево, то Ess(A)= {1}.

Также доказано следующее утверждение. Если Т бесконечное дерево и d+(jc)> 2, для всех jc еТ, и если 1- собственное значение, то оно имеет бесконечную кратность.

Дополнительные сведения об оценке спектра оператора Лапласа см. в [44,48,51,53,55], а свойства собственных функций см. в [56].

Из отечественной литературы хотелось бы отметить многочисленные работы авторов Воронежского государственного университета [1-3,1618,20,22,23,32-35,42]. Хотя в большинстве из них говорится о краевых задачах на графах, на самом деле все эти работы посвящены исследованию указанных задач на топологической сети, которая имеет лишь геометрическое сходство с графом в его классическом понимании.

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

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

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

предложен новый метод нахождения амплитуды вероятности для дискретного аналога теории Фейнмана на ориентированном графе.

Изложим содержание диссертации по главам.

В первой главе вводится понятие границы орграфа, рассматриваются классический лапласиан и его обобщение на орграфах, определяются понятия гармонической, суб- и супергармонической функций. Формулируется и доказывается принцип максимума для субгармонических функций на орграфах. Также получена оценка значений субгармонической функции внутри графа. Приводятся дискретные аналоги первой и второй формул Грина. Основным результатом главы является доказательство теоремы существования и единственности решения задачи Дирихле, порожденной оператором Лапласа на ориентированных графах.

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

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

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

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

Работа выполнена на кафедре алгебры и дискретной математики Ростовского государственного университета. Автор выражает свою благодарность кандидату физико-математических наук, доценту Хейфицу А. И. за идею и постановку проблемы. Также автор от души благодарит своего научного руководителя кандидата физико-математических наук, доцента Ерусалимского Я. М. за постоянную заботу и помощь при работе над диссертацией.

Список литературы диссертационного исследования кандидат физико-математических наук Степовой, Дмитрий Владимирович, 1998 год

Литература

1. Абдульмаджид М. О положительности функции Грина разрывной задачи Дирихле на графе/ Воронеж, ун-т. - Воронеж, 1992. - 8 с. - Деп. в ВИНИТИ 27. 07. 92, N 2472 -В92.

2. Аль- Турк М. О невырожденных негладких краевых задачах на графах/ Воронеж, ун-т. - Воронеж, 1994. - 6 с. - Деп. в ВИНИТИ 08. 11. 94, N2518-B94.

3. Аль- Турк М., Прядиев В. JI. О функции Грина негладкой задачи Дирихле на графе/ Воронеж, ун-т. - Воронеж, 1994. - 11 е.- Деп. в ВИНИТИ 08. 11. 94, N 2520 - В94.

4. Белов В.В. и др. Теория графов/ В.В. Белов, Е.М. Воробьев, В.Е. Шаталов. - М.: Высш. школа, 1976. - 390 с.

5. Берж К. Теория графов и ее применения: Пер. с фр. A.A. Зыкова. - М.: Изд. иностр. лит., 1962. - 319 с.

6. Блохинцев Д. И. Основы квантовой механики. -М.: Наука, 1976. - 664 с.

7. Владимиров B.C. Уравнения математической физики.-М.: Наука, 1967. -436 с.

8. Волков В. Е. Асимптотически быстрые приближенные методы решения разностного уравнения Лапласа в кубе// Журн. вычисл. математики и мат. физики. - 1996. - т. 36, N 5. - с. 90-97.

9. Гулд X., Тобочник Я. Компьютерное моделирование в физике: В 2 ч./ Пер. с англ. А.Н. Помодова, В.А. Панченко. -М.: Мир, 1990. - Ч. 1. -349 с, Ч. 2. - 399 с.

10. Дульнев Г.Н. и др. Применение ЭВМ для решения задач теплообмена: Учеб. пособие/ Г.Н. Дульнев, В.Г. Парфенов, A.B. Сигалов. -М.: Высш. шк., 1990.-260 с.

11. Дульнев Г.Н. Тепло- и массообмен в радиоэлектронной аппаратуре: Учеб. для вузов. -М.: Высш. шк., 1984. - 247 с.

12. Евграфов М.А. Аналитические функции: Учеб. пособие для вузов. - М.:

Наука, 1991.-448 с.

13. Ерусалимский Я. М., Степовой Д. В. Волновое уравнение и уравнение теплопроводности на конечных ориентированных графах/ Азово-Черномор. гос. агроинж. акад. -Зерноград, 1996. - 11с. -Деп. в ВИНИТИ 07. 02. 97, N 374- В97.

14. Ерусалимский Я. М., Степовой Д. В. Гармонические функции на ориентированных графах и краевые задачи математической физики// Тез. докл. Междунар. конф. „Нелокальные краевые задачи и родственные проблемы математической биологии, информатики и физики". -Нальчик, 1996.

15. Ерусалимский Я. М., Степовой Д. В. Дискретный оператор Лапласа на орграфах и некоторые его приложения // Тез. докл. Y междунар. конф. „Математика. Экономика", 26 мая - 1 июня 1997 г. Ростов н/Д, 1997.

16. Завгородний М. Г. Спектральная полнота корневых функций краевой задачи на графе// Докл. Рос. АН. -1994. - т. 335, N3. - с. 281-283.

17. Завгородний М. Г. и др. Геометрическая кратность собственных значений задачи Дирихле на графе/ Завгородний М. Г., Аль-Обейд А., Пря-диев В. Л.: Воронеж, ун-т. - Воронеж, 1992. - 8 с. Деп. в ВИНИТИ

22. 09.92, N2821-В92.

18. Завгородний М. Г., Кулаев Р. Ч. О кратности собственных функций краевой задачи на графе// Тез. докл. Воронеж, весен, мат. шк. „Соврем, методы в теории краев, задач" Понтряг. чтения-7, 17-23 апр. 1996 -Воронеж, 1996.

19. Зарубин B.C. Инженерные методы решения задач теплопроводности. -М.: Энергоатомиздат, 1983. - 326 с.

20. Изотова И. В. Устойчивость линейных дискретных краевых задач// Тез. докл. Воронеж, весен, мат. шк. "Соврем, методы в теории краев, задач" Понтряг. чтения-7, 17-23 апр. 1996. - Воронеж, 1996.

21. Исаченко В.П. и др., Теплопередача: Учеб. для втузов/ В.П. Исаченко, В.А. Осипова, A.C. Сукомел. -М.: Энергоиздат, 1981. - 417 с.

22. Карелина И. Г. Об одной нелинейной краевой задаче на графе//

Тез. докл. Воронеж, зим. мат. шк. „Соврем, методы теории функций и смежн. пробл. прикл. мат. и мех." 25 янв. -1 февр., 1995. -Воронеж, 1995.

23. Карелина И. Г., Покорный Ю. В. О функции Грина краевой задачи на графе// Дифференц. уравнения. -1994. - т. 30, N1. - с. 41-47.

24. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа: Учеб. для ун-тов. -М.: Наука, 1989. - 623 с.

25. Кунин С. Вычислительная физика/ Пер. с англ. - М.:Мир, 1992. - 518 с.

26. Курбатов В. Г. О функции Грина дифференциально-разностного уравнения// Дифференц. уравнения. - 1988. - т. 24, N 3. - с. 525 - 527.

27. Лекции по теории графов: Для студентов по спец.,, Математика" и „Прикл. математика"/В. А. Емеличев, О. И. Мельников. В. И. Сарва-нов, Р. И. Тышкевич. -М.: Наука, 1990. - 382 с.

28. Матсон Э.А., Конструкции и технологии микросхем: Учеб. пособие для вузов. -Минск: Вышейш. шк., 1985. - 207 с.

29. Мерков А. Б. Практические уравнения на графах/ МГУ. - М., 1986. -25 с. - Деп. в ВИНИТИ 22. 04.86, N 2938-В.

30. Митюшев В. В. Уравнение теплопроводности и волновое уравнение на графах//Дифференц. уравнения, 1988. -т. 24, N 9.- с. 1591 - 1599.

31. Мудров А. Е. Численные методы для ПЭВМ на языке Бейсик, Фортран и Паскаль. -Томск: МП „Раско", 1992. - 272 с.

32. Мустафокулов Р. Об одном классе краевых задач для дифференциального уравнения четвертого порядка на графе// Тез. докл. Воронеж, зим. мат. шк. „Соврем, методы теории функций и смежн. пробл. прикл. мат. и мех.", 25 янв. -1 февр. 1995. -Воронеж, 1995.

33. О краевых задачах на пространственных сетях. Фундам. пробл. мат. и мех. Ч. 1. Мат. / Завгородний М. Г., Мартыненко Г. В., Пенкин О. М., Покорный Ю. В., Прядиев В. Л. -М.: Изд-во МГУ, 1994.

34. Покорный Ю. В. и др. Об уравнениях на пространственных сетях/ Покорный Ю. В., Пенкин О. М., Прядиев В. Л.// Успехи мат. наук. -1994.

- т. 49, вып. 4. - с. 140.

35. Прядиев В. JL, О невырожденности разрывных краевых задач на графе/ Прядиев В. Л., Абдульмаджид М., Фитискина Ж.Ю.; Воронеж, ун-т. -Воронеж, 1992. - 10 с. - Деп. в ВИНИТИ 15. 04.92, N 1289- В92.

36. Степовой Д.В. Оператор Лапласа на конечных ориентированных графах/ Азово-Черномор. гос. агроинж. акад. -Зерноград, 1996. - 12 с.-Деп. в ВИНИТИ 27.09.96, N 2899.

37. Степовой Д. В., Ерусалимский Я. М. Некоторые оценки спектра оператора Лапласа на ориентированных графах/ Азово-Черномор. гос. агроинж. акад. -Зерноград, 1997. - 10 с. - Деп. в ВИНИТИ 24. 12. 97,

N 3740 - В97.

38. Степовой Д. В., Ерусалимский Я. М. Потенциальный оператор, функция Грина на ориентированных графах и некоторые их приложения в квантовой механике/ Азово-Черномор. гос. агроинж. акад. -Зерноград, 1997.- 13 с.-Деп. в ВИНИТИ 11.04. 97, N 1172-В97.

39. Теория тепломассообмена / Под ред. А.И. Леонтьева. - М.: Высш. шк., 1979.- 495 с.

40. Теплин А. Л. О знаке разностной функции Грина// Изв. вузов Математика. - 1988, N 4. - с. 33 - 40.

41. Фридрихов С.А., Мовин С.М. Физические основы электронной техники: Учеб. для вузов. - М.: Высш. шк., 1982. - 608с.

42. Функция Грина разрывной задачи Дирихле на графе/ Покорный Ю. В., Абдульмаджид М., Прядиев В. Л., Фитискина Ж. Ю.: Воронеж, ун-т -Воронеж, 1992. - 8 с. - Деп. в ВИНИТИ 03. 06. 92, N 1836 - В92.

43. Abu-Jaradeh Nafiz, Powers David L. Heat conduction on graphs// Discrete Appl. Math. - 1994. - vol. 52. - N1. -c. 1-16.

44. Brand Clemens, Seifter Norbert. Eigenvalues and domination on graphs// Math. slov. -1996. - vol. 46, N1.

45. Cvetkovic D., Doob M., Sachs H., Spectra of Graphs: Theory and Application/ Pure Appl. Math. 87, Academic Press, New York, 1979.

46. Dodziuk J., Karp L. Spektral and function theory for combinatorial Laplacians// Contemporary Mathematics. - 1988. - vol. 73. - c. 25 - 40.

47. Dodziuk J. Laplacian on manifolds and analogous difference operator for graphs// Contemp. Math. - 1986. - vol. 49. - c. 45-49.

48. Friedman J. The spectra of infinite hypertrees// SIAM J. Comput. - 1991.-vol. 20.-c. 951-961.

49. Friedman J. Some geometric aspects of graphs and their eigenfunctions// Duke Math. J. - 1993. - vol. 69, N3. - c. 487-525.

50. Friedman J. Minimum higher eigenvalues of Laplacians on graphs// Duke Math. J. - 1996. - vol. 83, N 1. - c. 1-18.

51. Fujiwara K. The Laplacian on rapidly branching trees// Duke Math. J. -1996.-vol. 83, N l.-c. 191-202.

52. Fujiwara K. Growth and spectrum of the Laplacian of infinite graph// Tohoku Math. J. - 1996. - vol. 48, N2. - c. 293-302.

53. Fujiwara K. Convergence of the eigenvalues of Laplacians in a class of finite graphs. Geom. Spectrum: Jt Summer Res. Conf. Seattle, Wash., July 17-23, - 1993.

54. Quantum mechanics on graphs/ Gratus J., Lambert C. J., Robinson S. J., Tucker R. W.// J. Phys. A. - 1994.- vol 27, N20. - c. 6881-6892.

55. Grone R., Merris R., Sunder V. S., The Laplacian spectrum of a graph. SIAM J. Matrix Anal, and Appl. -1990. -11, N2. - c. 218-238.

56. Koranyi A., Picardello M.A. Boundary behaviour of eigenfunctions of the Laplace operator on trees// Ann. Scuola Norm. Sup. Pisa, ser. 4, 1986. - c.

389-399.

57. Killingbeck J.P. Microcomputer Quantum Mechanics/ Adam Hilger. - 1983.

58. Merrill J.R. Using Computers in Physics/ Houghton Mifflin Co., - 1976.

59. Pagliacci Mauro, Heat and wave equations on homogeneous trees// Boll. Unione Mat. ital. - 1993.A., - vol. 7, N1. - c. 37-45.