LEM - библиотека поисковой машины: математическая часть (численные методы)

Размещение

Исходные тексты для "математики" ищите в LEM\Math (пространство имен lem::Math), объявления собраны в Lem\Include\Math. Примеры использования процедур численных методов вместе с тестами, содержащими реперные числа для задач с известным решением, можно отыскать в проектах в LEM\Demo\Math. Многие из собранных там программ являются готовыми примерами решений типичных "студенческих" задач - от систем линейных уравнений методами Гаусса и прогонки до систем дифференциальных уравнений в частных производных методами конечных разностей.

Кроме этого, специально для решения математических задач объявлены некоторые контейнеры (BaseArray, BaseMatrix, BasePolynome, BaseVector).

Эффективность библиотеки и ленивые вычисления

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

A=B*C+D

где аргументы - матрицы, будет создано 2 временных объекта типа матрица, что безусловно вызывает напрасную трату всех ресурсов. Вероятно, этот недостаток будет устранен в обозримом будущем (с применением известного метода генерации шаблонов для ленивых вычислений). Подборка математических процедур не отличается полнотой - все они были реализованы по мере необходимости (курсовые-дипломный проект-диссертация). Однако все исходники хорошо документированы - включая перечень источников (литературы), где описан метод решения или откуда переведен код (часто это были программы на Фортране).

Тестовые примеры

Кроме процедур численных методов, библиотека содержит очень большое количество тестовых задач, на которых различные методы проверяются. Решение этих тестовых задач либо известно аналитически, либо есть верифицированные данные (например, для специальных функций). Все тесты собраны в подкаталоге LEM\Demo\Math.

Решение дифференциальных уравнений (задачи Коши, краевые задачи)

Функции объявлены в: lem\include\math\differ.h

Реализованы:

• Метод Рунге-Кутта разного порядка с постоянным и адаптивным шагом

• Расчет по формулам Милна, Батчера

• Предиктор-корректор по методу Эйлера

• Решение систем ОДУ методом Рунге-Кутта с адаптивным шагом

• Решение некоторых краевых задач

Аппроксимация, в том числе - интерполяция данных, сплайны

Функции объявлены в: lem\include\math\approxim.h

Реализованы методы и формулы:

• линейная интерполяция

• квадратичная интерполяция

• интерполяция полиномом Лагранжа

• интерполяция полиномом, построенным методом наименьших квадратов (МНК)

• кубические B-сплайны (на плоскости и в пространстве)

• квадратичные B-сплайны (на плоскости и в пространстве)

• Кривые Безье (на плоскости и в пространстве)

• Кривые Катрома-Милля (на плоскости и в пространстве)

Немного статистической обработки

Функции объявлены в: lem\include\math\statkeep.h

Поиск экстремумов и корней (нулей) функций

Функции объявлены в: lem\include\math\extremum.h

Реализованы методы:

• поиск экстремумов методом дихотомии

• поиск корней (нулей) методом дихотомии

• поиск корней действительного полинома методом последовательностей Штурма (regula-falsi)

• поиск корней методом Ньютона

• поиск корней квадратного уравнения с контролем точности

• поиск экстремума 2х-мерной трансцендентной функции методом Монте-Карло

Специальные функции

Функции объявлены в: lem\include\math\specifun.h

Реализованы функции:

• Эйри

• Бесселя

• Интегральный синус и косинус

• Полиномы Чебышева, Эрмита

• Ошибок

• Гамма-функция

Поиск нулей функций

Функции объявлены в: lem\include\math\zeroin.h

Численное интегрирование

Функции объявлены в: lem\include\math\integral.h

Реализованные методы:

• прямоугольников (1 и 2х мерные случаи)

• трапеций (для таблично и аналитически заданной функции)

• Симпсона (включая метод с улучшение точности по формуле Рунге) - 1 и 2 мерные случаи

• Уэддля, Ньютона-Котеса (с динамическим построением формулы заданного порядка)

• Гаусса (квадратурные формулы до 96 порядка)

• Лаггера и Эрмита для интегралов с одним или двумя бесконечными пределами

• Лобатто (до 10 порядка)

• Эрмита

• Чебышева (до 9 порядка)

• Метод Монте-Карло для 1, 2 и 3 измерений

• Метод Эйлера (при аналитически известных производных подинтегральной функции)

Решение задач на собственные числа и вектора

Функции объявлены в: lem\include\math\eigena.h.

Решение систем линейных уравнений

Функции объявлены в: lem\include\math\linsolve.h

Реализованы методы:

• Приведение к верхнетреугольному виду методом Гаусса

• Решение СЛУ методом Гаусса-Жордана с выбором ведущего элемента

• Решение СЛУ и вычисление детерминанта с использованием LU-разложения и с улучшением решения

• Итерационное решение

• Вычисление детерминанта по формуле Крамера

• Методы правой и левой прогонки для трехдиагональной матрицы

• Метод прогонки для 5-ти диагональной матрицы

Генераторы псевдослучайных чисел

Объявлены в: lem\include\lem_rand.h

Реализованы несколько "классических" мультипликативных генераторов  с равномерным законом распределением.

См. более подробное описание

[описание LEM]