На заседание на семинара “ИНФОРМАТИЧНО МОДЕЛИРАНЕ”,
на 04.10.2018, четвъртък, от 14:00 часа, в зала 578 на ИМИ,
доклад на тема:

Нов метод Монте Карло за линейни системи, базиран на метода ,,случайно блуждаене по уравненията

ще изнесе ас. д-р Венелин Тодоров, ИМИ-БАН.

Поканени са всички интересуващи се.

Резюме: Много научни и инженерни приложения се основават на на решаването на системи от линейни алгебрични уравнения. Времето за изчисляване на задачи от голяма размерност или за намиране на решения в реално време, може да бъде ограничено и това прави използването на много от установените алгоритми нецелесъобразно. Алгоритмите Монте Карло дават статистическа оценка на неизвестната величина, чрез използването на случайни величини, чието математическо очакване съвпада с търсеното решение.

Разработен е нов алгоритъм на Монте Карло за решаване на системи от линейни алгебрични уравнения. Алгоритъмът се основава на наскоро разработения метод Монте Карло ,, случайно блуждаене по уравненията”, базиран на недисконтирана сума на случайни траектории с поглъщане. За усъвършенстване на основния алгоритъм се прилагат няколко техники, като броене на посещенията на уравненията на линейната система и последователния метод Монте Карло на Джон Холтън. Алгоритъмът е оптимизиран чрез избиране на подходящи стойности на релаксационния параметър, което води до намаляване на изчислителната сложност и на повишаване на точността за даден брой итерации. Алгоритъмът е използван за намиране на всички компоненти на решението на реални линейни системи с голяма размерност.

Извършени са числени експерименти за примери с разредени и плътни матрици с различна размерност и за система с фундаментално приложение, взета от апроксиамция по метода на крайните елементи на модел, описващ гредова структура в конструктивната механика. Направено е сравнение с метода на спрегнатия градиент и със съществуващите досега методи Монте Карло за линейни системи. Поведението на предложения алгоритъм Монте Карло не зависи от плътността на матрицата. Предимствата на алгоритъма могат да бъдат наблюдавани особено за системи с много голяма размерност.

Благодарение на направените оптимизации новият метод дава много по-добри резултати от стандартния метод Монте Карло и е установен като един от най-бързите и точни алгоритми Монте Карло за решаване на системи от линейни алгебрични уравнения.